全部习题

第一章绪论
求时间复杂度练习题令数组全部的值为0
（1）
i←1  ;  j←0
while i+j<=n do
    if i>j then
        j←j+1
    else
        i←i+1
    endif
endwhile
（2）
for i←1 to n do
    for j←1 to n do
        for k←1 to j do
            x←x+1
        endfor
    endfor
endfor
（3）
for i←1 to n do
    for j←1 to i do
        for k←1 to j do
            x←x+1
        endfor
    endfor
endfor
（4）一个算法的执行时间为1000n，另一个算法约为2^n(2的n次方)。这两个算法的时间复杂度分别是多少？哪个高？当问题的规模n≤13时，选用哪个算法合适？
（5）已知有实现同一功能的两个算法，其时间复杂度分别为O(2^n)和O(n^10)，假设现实计算机可连续运行的时间约100天，又每秒可执行基本操作为10^5次。试问在此条件下，这两个算法可解决问题的规模（即n的范围）各为多少？哪个算法更合适？试说明理由。
（6）给出费氏数列(fibonacci数列)前n项的递归与非递归的算法，试分析它们的算法复杂度(注：费氏数列指fibonacci数列)；试用time或clock函数实际测试n=100时，机器的实际运行时间，并分析结果。
第六章    线性表习题
6-1. 一个向量的第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是        。
6-2. 在一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动的元素个数是          。
6-3. 在线性表的顺序存储结构中，逻辑上相邻的元素在物理位置上        。
6-4. 对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时大约要移动表中的      个元素，删除一个元素时大约要移动表中的      个元素。
6-5. 线性表顺序存储的特点是                                                。
6-6. 若线性表中元素的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么若采用顺序存储结构是否合适？为什么？
6-7. 根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为        和        ；而根据指针的连接方式，链表又可分为          和          。
6-8. 试描述头指针、头结点及开始结点的区别，并说明头指针和头结点的作用。
6-9. 有哪些链表可由一个尾指针来唯一确定？(即从尾指针出发能访问到链表上任何一个结点)
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为指向链表中某个结点的指针，试编写算法删除结点*s的直接前趋结点。
6-30. 设有一个双向链表，每个结点中除有prior，data和next三个域外，还有一个访问频度域freq，在链表被启用之前，其值均初始化为零。每当在链表中进行一次LOCATE(L,x)
运算时，令元素值为x的结点中freq域的值增1，并使此链表中结点保持按访问频度递减的顺序排列，以便使频繁访问的结点总是靠近表头，试编写符合上述要求的LOCATE运算的算法。
已知，由单链表表示的线性表中，含有三类字符的数据元素（如：字母字符，数字字符和其它字符），试编写算法构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。

第八章  栈和队列

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。