全部习题第一章绪论求时间复杂度练习题（1）i←1 ; j←0while i+j<=n doif i>j thenj←j+1elsei←i+1endifendwhile（2）for i←1 to n dofor j←1 to n dofor k←1 to j dox←x+1endforendforendfor（3）for i←1 t o n dofor j←1 to i dofor k←1 to j dox←x+1endforendforendfor（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-10. 什么情况下用顺序表比链表好？6-11. 不带头结点的单链表head为空的判定条件是。

(1) head=NULL (2) head→next=NULL(3) head→next=head (4) head!=NULL6-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)/26-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个元素的算法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运算的算法。

已知，由单链表表示的线性表中，含有三类字符的数据元素（如：字母字符，数字字符和其它字符），试编写算法构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。

第八章栈和队列8-1. 一个栈的入栈序列是a,b,c,d,e，则栈不可能的输出序列是。

(1)edcba (2)decba (3)dceab (4)abcde8-2. 若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为。

(1) i (2) n=i (3) n-i+1 (4) 不确定8-3. 循环队列用数组A[0,m-1]存放其元素值，已知其头尾指针分别是front 和rear，则当前队列中的元素个数是。

(1) (rear-front+m)%m (2) rear-front+1(3) rear-front-1 (4) rear-front8-4. 栈和队列的共同点是。

(1) 都是先进先出(2) 都是先进后出(3) 只允许在端点处插入和删除元素(4) 没有共同点8-5. 为增加内存空间的利用率和减少发生上溢的可能性，由两个栈共享一片连续的内存空间时，应将两栈的分别设在这片内存空间的两端，这样，只有当时，才产生上溢。

8-6. 向量、栈和队列都是结构，可以在向量的位置插入和删除元素；对于栈只能在插入和删除元素；对于队列只能在插入元素和删除元素。

8-7. 设有编号为1,2,3,4的四辆列车，顺序进入一个栈式结构的站台。

具体写出这四辆列车开出车站的所有可能的顺序。

8-8. 试证明：若借助栈由输入序列12…n得到输出序列为p1p2...pn(它是输入序列的一个排列)，则在输出序列中不可能出现这样的情形：存在着i<j<k 使pj<pk<pi。

8-9. 对于循环向量中的循环队列，写出求队列长度的公式。

8-10. 用单链表实现队列如图8-17所示，并令front=rear=NULL表示队列为空，编写实现队列的如下五种运算的函数。

SETNULLQ：将队列置成空队列FRONTQ：取队头结点数据ENQUEUEQ：将元素x插入到队列的尾端DEQUEUEQ：删除队列的第一个元素EMPTYQ：判定队列是否为空图8-17 用单链表实现队列8-11. 设单链表中存放着n个字符，试编写算法，判断该字符串是否有中心对称关系，例如xyzzyx、xyzyx都算是中心对称的字符串。

要求用尽可能少的时间完成判断。

(提示：将一半字符先依次进栈。

)8-12. 设计算法判断一个算术表达式的圆括号是否正确配对。

(提示：对表达式进行扫描，凡遇'('就进栈，遇')'就退掉栈顶的'('，表达式被扫描完毕，栈应为空。

)8-13. 两个栈共享向量空间V[m],它们的栈底分别设在向量的两端，每个元素占一个分量，试写出两个栈公用的栈操作算法：push(i,x),pop(i)和top(i)，其中i为0或1，用以指示栈号。

8-14. 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点(注意不设头指针)，试编写相应的置空队、入队列和出队列的算法。

8-15. 试设计算法判断字符串是否中心对称，要求利用栈作存储结构。

8-16. 假设以数组sequ[m]存放循环队列的元素，同时设变量rear和quelen 分别指示循环队列中队尾元素的位置和内含元素的个数。

试给出判别此循环队列的队满条件，并写出相应的入队列和出队列的算法(在出队的算法中要返回队头元素)。

第七章数组和串7-1. 串是一种特殊的线性表，其特殊性体现在。

(1)可以顺序存储(2)数据元素是一个字符(3)可以连接存储(4)数据元素可以是多个字符7-2. 设有两个串p,q，求q在p中首次出现的位置的运算称作。

(1)连接(2)模式匹配(3)求子串(4)求串长7-3. 串的两种最基本的存储方式是和。