数据结构第二章习题课.doc

数据结构第二章习题课 本资源摘要信息主要围绕数据结构第二章的习题课，涵盖了链表、顺序表、单链表、双链表、单循环链表等数据结构概念。下面是相关知识点的详细说明： 1. 头指针、头结点、开始结点的区别： 头指针是指向链表开始结点的指针，头结点是人为地在链表开始结点之前附加的一个结点。头指针和头结点的作用是使得对链表的第一个位置上的操作与在表其他位置上的操作一致。 2. 何时选用顺序表、何时选用链表作为线性表的存储结构为宜： 在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构。通常有基于空间的考虑和基于时间的考虑。如果要求存储的线性表长度变化不大，易于事先确定其大小时，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。假设线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，假设需要对线性表进行频繁地插入或删除等操作时，宜采用链表做存储结构。 3. 在顺序表中插入和删除一个结点需平均移动多少个结点： 在等概率情况下，顺序表中插入一个结点需平均移动 n/2 个结点，删除一个结点需平均移动 (n-1)/2 个结点。具体的移动次数取决于顺序表的长度 n 以及需插入或删除的位置 i。 4. 为什么在单循环链表中设置尾指针比设置头指针更好： 尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便。设一带头结点的单循环链表，其尾指针为 rear，则开始结点和终端结点的位置分别是 rear->next->next 和 rear, 查找时间都是 O(1)。假设用头指针来表示该链表，则查找终端结点的时间为 O(n)。 5. 在单链表、双链表和单循环链表中，假设仅知道指针 p 指向某结点，不知道头指针，能否将结点*p 从相应的链表中删去： 在单链表中，无法删去该结点。双链表中，可以删除该结点，时间复杂度为 O(1)。单循环链表中，可以删除该结点，时间复杂度为 O(n)。 6. 下述算法的功能是什么： 该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。 7. 不带头结点的单链表 head 为空的判定条件是： head=NULL 8. 在一单链表中，已知 q 所指的结点是 p 所指结点的前驱结点，假设在 q 和 p 之间插入 s结点： 执行 q->next=s;s->next=p; 9. 在一个单链表中，假设 p 所指的结点不是最后结点，在 p 之后插入 s 结点： 执行 s->next=p->next;p->next=s; 10. 在一个单链表中，假设删除 p 所指结点的后续结点： 执行 p->next=p->next->next; 本资源摘要信息涵盖了数据结构第二章的习题课，涉及链表、顺序表、单链表、双链表、单循环链表等数据结构概念，并对每个问题进行了详细的解释和分析。