全部习题.doc

: .
全部习题
LT
表上任何一个结点)
6-10. 什么情况下用顺序表比链表好？
6-11. 不带头结点的单链表head为空的判定条件是 。
(1) head=NULL (2) head→next=NULL
(3) head→next=head (4) head!=NULL
6-12. 在一个单链表中，若指针p所指结点不是最后结点，在p之后插入指针s所指结点，则执行 。
(1) s→next=p;p→next=s; (2) s→next=p→next;p→next=s;
(3) s→next=p→next; p=s; (4) p→next=s;s→next=p;
6-13. 在循环双链表的指针p所指结之后插入指针s所指结点的操作是 。
(1) p→next=s;s→prior=p;p→next→prior=s;s→next=p→next;
(2) p→next=s; p→next→prior=s;s→prior=p;s→next=p→next;
(3) s→prior=p;s→next=p→next;p→next=s; p→next→prior=s;
(4) s→prior=p;s→next=p→next;p→next→prior=s;p→next=s;
6-14. 从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较的结点个数是 。
(1) n (2)n/2 (3)(n－1)/2 (4)(n＋1)/2
6-15. 给定有n个元素的向量，建立一个有序单链表的时间复杂度是 。
(1) O(1) (2)O(n) (3)O(n2) (4)O(nlog2n)
6-16. 线性表采用链表存储时，其地址 。
(1)必须是连续的 (2)部分地址必须是连续的
(3)一定是不连续的 (4)连续不连续都可以
6-17. 试用顺序存储结构设计一个算法，仅用一个辅助结点，实现将线性表中的结点循环右移k位的运算，并分析算法的时间复杂度。
6-18. 已知一顺序表递增有序，试设计一算法，将x插入到表中的适当位置，以保持顺序表的有序性。
6-19. 设有两个顺序表A和B，元素的个数分别是m和n，若表中的数据都是由小到大顺序排列的，且这(m+n)个数据中没有相同的。试设计算法将A和B合并成一个线性表C，并存储到另一个向量中。
6-20. 设有一个顺序表中，写出在其值为x的元素之后插入m个元素的算法（假设顺序表的长度足以容纳m个元素）。
6-21. 设有一线性表E={e1,e2,…,en-1,en)，试设计一个算法，将线性表逆置，即使元素排列次序颠倒过来，成为逆线性表E¢={en,en-1,…,e2,e1)，要求逆线性表占用原线性表空间，并且用顺序和单链表两种方法表示，写出不同的处理过程。
6-22. 已知带头结点的动态单链表L中的结点是按整数值递增排列的，试写一算法将值为x的结点插入表L中，使L仍然有序。
6-23. 试编写在带头结点的动态单链表上实现线性表操作LENGTH(L)的算法，并将长度写入头结点的数据域中。
6-24. 已知一个带头结点的单链表，设计算法将该单链表复制一个拷贝。
6-25. 设指针la和lb分别指向两个无头结点单链表的首元结点，试设计从表la中删除自第i个元素起共len个元素后，将它们插入到表lb中第i个元素之前的算法。
6-26. 设计算法将一个带头结点的单链表A分解为两个链表A、B，使得A表中含有原表中的序数为奇数的结点，而B表中含有序数为偶数的结点，且保持结点间原有的相对顺序。
6-27. 假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，试编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许值相同）排列的线性表C，并要求利用原表（即A表和B表）的结点空间存放表C。
6-28. 设线性表A、B和C递增有序，试在A表中删除既在B中出现又在C中出现的那些元素，且A、B和C分别以两种存储结构（顺序和链式）存储。
6-29. 假设在长度大于1的单循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写