算法基础复习:选择题解析与链表操作

需积分: 0 2 下载量 31 浏览量 更新于2024-09-15 收藏 112KB DOC 举报
"算法复习题" 这篇资料是关于2012年的算法复习题目,涵盖了算法分析、数据结构、链表操作、栈和队列等核心概念。以下是这些题目涉及的知识点详解: 1. 算法分析的目的是为了评估和改进算法的效率。选项C(分析算法的效率以求改进)正确。算法分析关注的是时间和空间复杂性,以优化算法性能。 2. 逻辑地址和物理地址相同且连续的存储结构指的是顺序存储结构,如数组。选项B(顺序存储结构)正确。 3. 在一个具有n个结点的单链表中查找值等于x的结点,平均情况下需要比较的结点数是(n+1)/2。选项C正确。 4. 如果线性表最常用的操作是在最后一个元素之后插入和删除第一个元素,采用仅有尾指针的单循环链表最节省运算时间。这样可以快速定位到链表尾部进行插入和删除操作。选项D正确。 5. 删除单链表中节点m之后的节点,需要先将m的next指针指向其后继节点的下一个节点,然后删除后继节点。所以操作应为A:p->next=p->next->next。 6. 在单链表中,在q和p之间插入s结点,应先让s的next指针指向p,然后让q的next指针指向s。选项B正确:q->next=s; s->next=p。 7. 在顺序栈中,做出栈处理时,栈顶指针top会向下移动一个单位,即top--。选项C正确。 8. 判断顺序存储的循环队列是否满的条件是队尾指针rear加1后与队头指针front相等,即(rear+1)%n==front。选项B正确。 9. 队列遵循先进先出(FIFO)原则,即最先入队的元素最先出队。选项A正确。 10. 串S='software'的子串数目包括空串和所有由S中的字符组成的非空子串。S有9个字符,因此子串数目为2^9 - 1 = 511,但选项中没有这个答案,最接近的是B,可能是由于题目或选项有误。 11. 选项A(串是一种特殊的线性表)是正确的,因为串是由同一类型元素组成的线性序列。其他选项错误:串的长度可以为零,表示空串;串中的元素可以是任意字符。 以上是题目涉及的算法和数据结构基础知识,对于准备算法考试或复习这些概念非常有帮助。