全部习题

第一章绪论

求时间复杂度练习题 （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运算的算法。

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

第八章 栈和队列

8-1. 一个栈的入栈序列是a,b,c,d,e，则栈不可能的输出序列是 。 (1)edcba (2)decba (3)dceab (4)abcde

8-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-front

8-4. 栈和队列的共同点是 。

(1) 都是先进先出 (2) 都是先进后出 (3) 只允许在端点处插入和删除元素 (4) 没有共同点

8-5. 为增加内存空间的利用率和减少发生上溢的可能性，由两个栈共享一片连续的内存空间时，应将两栈的 分别设在这片内存空间的两端，这样，只有当 时，才产生上溢。 8-6. 向量、栈和队列都是 结构，可以在向量的 位置插入和删除元素；对于栈只能在 插入和删除元素；对于队列只能在 插入元素和 删除元素。

8-7. 设有编号为1,2,3,4的四辆列车，顺序进入一个栈式结构的站台。具体写出这四辆列车开出车站的所有可能的顺序。

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

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. 串的两种最基本的存储方式是 和 。

7-4. 两个串相等的充分必要条件是 。 7-5. 空串是 ，其长度为 。

7-6. 设S=“I am a teacher.”，其长度为 。

7-7. 子串定位函数的时间复杂度在最坏情况下为 。 7-8. 快速匹配算法的最大特点是 。

7-9. 令s=“aaab”，t=“abcabaa”，试分别求出它们的next函数值。

7-10. 若S=“(XYZ)+*”，T=“(X+Z)*Y”，试利用连接、求子串和置换等基本运算将S转化为T。

7-11. 二维数组M的成员是6个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要 个字节；M的第8列和第5行共占 个字节；若M按行优先方式存储，元素M[8][5]的起始地址与当M按列优先方式存储时的 元素的起始地址一致。

7-12. 数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数是 。若数组按行存放时，元素A[8][5]的起始地址为 。 7-13. 稀疏矩阵一般的压缩存储方法有两种，即 和 。

7-14. 二维数组A[m][n]采用行序为主存储，每个元素占k个存储单元，并且A[0][0]的存储地址是200，则A[6][12]的地址是 。 7-15. 已知三维数组M[2…3,-4…2,-1…4]，且每个元素占用2个存储单元，起始地址为100，按行下标优先顺序存储，求： (1)M所含的数据元素个数；

(2)M[2,2,2]，M[3,-3,3]的存储地址。

7-16. 设三对角矩阵An×n按行优先顺序，压缩存储在数组B[3*n-2]之中，求： (1)用i,j表示k的下标变换公式； (2)用k表示i,j的下标变换公式。

7-17. 设A是一个上三角矩阵，重复元素c可共享一个存储空间，其余元素压缩存储到A[n*(n+1)/2+1]中，重复元素存放在最后一个分量中。试求：数据元素A[k]与aij对应关系。

7-18. 若x和y是两个采用顺序结构存储的串，编写一个比较两个串是否相等的函数。

7-19. 若s一个采用顺序结构存储的串，编写一个函数，要求从s中删除从第i个字符开始的，长度为j的一个子串。 7-20. 若x是采用单链表存储的串，编写一个函数将其中的所有字符c替换成s字符。

7-21. 采用顺序存储结构串，遍写一个实现串通配符匹配的函数pattern_index()，其中的统配符只有′? ′，它可以和任一字符匹配成功。 7-22. 采用顺序结构存储串，编写一个函数计算一个子串在一个字符串中出现的次数，如果该子串不出现则为0。 7-23. 若s和t是两个单链表存储的串，编写一个函数找出s中第一个不在t中出现的字符。

7-24. 设对于二维数组A[m][n]，其中m≤80，n≤80，读入数组的全部元素，对如下三种情况分别编写相应函数：

(1)求数组A靠边元素之和；

(2)求从A[0][0]开始的互不相邻的个元素之和；

(3)当m=n时，分别求两条对角线上的元素之和，否则打印出m≠n的信息。 7-25. 若在矩阵Am×n中存在一个元素A[i-1][j-1]满足：A[i-1][j-1]是第i行元素中最小值，且又是第j列元素中最大值，则称此元素为该矩阵的一个马鞍点。假设以二维数组存储矩阵Am′n，试设计求出矩阵中所有马鞍点的算法，并分析所设计算法在最坏情况下的时间复杂度。 7-26. 已知稀疏矩阵用三元组表示，编写C=A*B的算法。 7-27. 已知A和B为两个n×n阶的对称矩阵，输入时，对称阵只输入下三角元素，存入一维数组，如图7-15所示。编写一个计算对称矩阵A和B的乘积的函数。

图7-15 矩阵的存储转换形式

第九章树

9-1. 树最适合用来表示 。

(1)有序数据元素 (2)无序数据元素

(3)元素数据之间具有分支层次关系的数据 (4)元素之间无联系的数据 9-2. 对一棵满二叉树，m个树叶，n个结点，深度为h，则 。 (1) n=h＋m (2) h＋m=2n (3) m=h－1 (4) n=2h－1 9-3. 在如图10.32的4棵二叉树中， 不是完全二叉树。

（1） （2） （3） （4） 图9-32 4棵二叉树

9-4. 已知一棵树边的集合为{ (i, m), (i, n), (e, i), (b,e), (b,d), (a,b), (g,j), (g,k), (c,g), (c,f), (h,l), (c,h), (a,c) }。画出该树，并回答下列问题: (1) 根结点是 。

(2) 叶子结点有 。 (3) g的双亲结点是 。

(4) g的祖先结点有 。 (5) g的孩子结点有 。

(6) b的子孙结点有 。 (7) f的兄弟结点是 。

(8) 树的深度是 ，b为根的子树的深度是 。 (9) 结点c的度是 ，树的度是 。

9-5. 指出树和二叉树的三个主要差别。

9-6. 一棵度为2的树与一棵二叉树的区别是 。

9-7. 一个深度为L的满k叉树有如下性质：第L层上的结点均为叶子，其余各层上每个结点均有k棵非空子树。如果按层次顺序从1开始对全部结点编号，问：(1) 各层的结点数目是多少？

(2) 编号为n的结点的双亲结点（若存在）的编号是多少？

(3) 编号为n的结点的第i个孩子结点（若存在）的编号是多少？ (4) 编号为n的结点有右兄弟的条件是什么？右兄弟的编号是多少？

9-8. 已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，…，nm个度为m的结点，问该树中有多少个叶子结点 ？

9-9. 写出图9-33所示二叉树的先序、中序和后序遍历序列。

9-10. 试找出分别满足下面条件的所有二叉树： (a) 先序序列和中序序列相同； (b) 中序序列和后序序列相同； (c) 先序序列和后序序列相同。

9-11. 已知先序遍历二叉树的结果为ABC，试问有几种不同的二叉树可得到这一遍历结果？

9-12. 设二叉树的存储结构如下图所示：

其中t为根结点指针，left、right分别为结点的左右孩子指针域，data为的数据域。请完成下列各题：

(1) 画出二叉树的逻辑结构 (2) 画出二叉树的后序线索树

9-13. 已知一棵二叉树的中序序列和后序序列分别为D, G, B, A, E, C, H, F和G, D, B, E, H, F, C, A，画出这棵二叉树。

9-14. 假设用于通信的电文由十种不同的符号来组成，这些符号在电文中出现的频率为8, 21, 37, 24, 6, 18, 23, 41, 56, 14，试为这十个符号设计相应的哈夫曼编码。

9-15. 试对结点序列{21, 18, 37, 42, 65, 24, 19, 26, 45, 25} 画出相应的二叉排序树，并且画出删除了结点37后的二叉排序树。 9-16. 一棵n个结点的完全二叉树以向量作为存储结构，试编写非递归算法实现对该树进行先序遍历。 9-17. 以二叉链表作存储结构，试编写非递归的先序遍历算法。

9-18. 已知二叉树的先序序列与中序序列分别存放在preod[n]和inod[n]数组中，并且各结点的数据值均不相同。请写出构造该二叉链表结构的非递归算法。

9-19. 在二叉树中查找值为x的结点，试编写算法打印值为x的结点的所有祖先。假设值为x的结点不多于1个。提示：利用后序遍历非递归算法，当找到值为x的结点时打印栈中有关内容。

9-20. 已知二叉树采用二叉链表存储结构，指向根结点存储地址的指针为t。试编写一算法，判断该二叉树是否为完全二叉树。

9-21. 已知二叉树采用二叉链表存储结构，试编写一算法交换二叉树所有左、右子树的位置，即结点的左子树变成结点的右子树，右子树变为左子树。

已知二叉树采用二叉链表存储结构，根结点存储地址为T。试编写一算法删除该二叉树中数据值为x的结点及其子树。 第十章 图

10-1. 在一个无向图中，所有顶点的度数之和等于所有边数的 倍。 10-2. n个顶点的连通图至少有 条边。 10-3. 对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为 ，所有邻接表中的结点总数是 。 10-4. 已知一个图的邻接矩阵表示，计算第i个结点的入度的方法是 。 10-5. 已知一个图的邻接矩阵表示，删除所有从第i个结点出发的边的方法是 。 10-6. 判定一个有向图是否存在回路除了可以利用拓扑排序的方法外，还可以利用 。 (1) 求关键路径的方法 (2) 求最短路径的方法

(3) 广度优先遍历算法 (4) 深度优先遍历算法

10-7. 对n个顶点的无向图G，采用邻接矩阵表示，如何判别下列有关问题： (1) 图中有多少条边?

(2) 任意两个顶点vi和vj是否有边相连? (3) 任一顶点的度是多少?

10-8. 给定有向图如图10-26示，试回答以下问题： (1) 每个顶点的入度与出度; (2) 相应的邻接矩阵与邻接表; (3) 强连通分量。

10-9. 给定一无向图如图10-27示，画出它的邻接表，写出用深度优先搜索和广度优先搜索算法遍历该图时，从顶点v1出发所经过的顶点和边序列。

图10-26 图10-27

10-10. 对图10-28所示的连通网络，请分别用Prim算法Kruskal算法构造该网络的最小生成树。

10-11. 对图10-29所示的有向图，试利用Dijkstra算法求从顶点v1到其它各顶点的最短路径，并写出执行算法过程中每次循环的状态。

本文来源：https://www.bwwdw.com/article/w493.html