全部习题.doc

第一章绪论求时间复杂度练习题（1）i1 ; j0while i+j=n do if ij then jj+1 else ii+1 endifendwhile（2）for i1 to n do for j1 to n do for k1 to j do xx+1 endfor endforendfor（3）for i1 to n do for j1 to i do for k1 to j do xx+1 endfor endforendfor（4）一个算法的执行时间为1000n，另一个算法约为2n(2的n次方)。这两个算法的时间复杂度分别是多少？哪个高？当问题的规模n13时，选用哪个算法合适？（5）已知有实现同一功能的两个算法，其时间复杂度分别为O(2n)和O(n10)，假设现实计算机可连续运行的时间约100天，又每秒可执行基本操作为105次。试问在此条件下，这两个算法可解决问题的规模（即n的范围）各为多少？哪个算法更合适？试说明理由。 （6）给出费氏数列(fibonacci数列)前n项的递归与非递归的算法，试分析它们的算法复杂度(注：费氏数列指fibonacci数列)；试用time或clock函数实际测试n=100时，机器的实际运行时间，并分析结果。第六章 线性表习题6-1. 一个向量的第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是 。6-2. 在一个长度为n的向量的第i个元素(1in+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) headnext=NULL(3) headnext=head (4) head!=NULL6-12. 在一个单链表中，若指针p所指结点不是最后结点，在p之后插入指针s所指结点，则执行 。(1) snext=p;pnext=s; (2) snext=pnext;pnext=s;(3) snext=pnext; p=s; (4) pnext=s;snext=p;6-13. 在循环双链表的指针p所指结之后插入指针s所指结点的操作是 。(1) pnext=s;sprior=p;pnextprior=s;snext=pnext;(2) pnext=s; pnextprior=s;sprior=p;snext=pnext;(3) sprior=p;snext=pnext;pnext=s; pnextprior=s; (4) sprior=p;snext=pnext;pnextprior=s;pnext=s;6-14. 从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较的结点个数是 。(1) n (2)n/2 (3)(n1)/2 (4)(n1)/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个元素的算法（假设顺序表的长度足以容纳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. 循环队列用数组A0,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. 试证明：若借助栈由输入序列12n得到输出序列为p1p2.pn(它是输入序列的一个排列)，则在输出序列中不可能出现这样的情形：存在着ijk使pjpkpi。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. 两个栈共享向量空间Vm,它们的栈底分别设在向量的两端，每个元素占一个分量，试写出两个栈公用的栈操作算法：push(i,x),pop(i)和top(i)，其中i为0或1，用以指示栈号。8-14. 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点(注意不设头指针)，试编写相应的置空队、入队列和出队列的算法。8-15. 试设计算法判断字符串是否中心对称，要求利用栈作存储结构。8-16. 假设以数组sequm存放循环队列的元素，同时设变量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按行优先方式存储，元素M85的起始地址与当M按列优先方式存储时的 元素的起始地址一致。7-12. 数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数是 。若数组按行存放时，元素A85的起始地址为 。7-13. 稀疏矩阵一般的压缩存储方法有两种，即 和 。7-14. 二维数组Amn采用行序为主存储，每个元素占k个存储单元，并且A00的存储地址是200，则A612的地址是 。7-15. 已知三维数组M23,-42,-14，且每个元素占用2个存储单元，起始地址为100，按行下标优先顺序存储，求：(1)M所含的数据元素个数；(2)M2,2,2，M3,-3,3的存储地址。7-16. 设三对角矩阵Ann按行优先顺序，压缩存储在数组B3*n-2之中，求：(1)用i,j表示k的下标变换公式；(2)用k表示i,j的下标变换公式。7-17. 设A是一个上三角矩阵，重复元素c可共享一个存储空间，其余元素压缩存储到An*(n+1)/2+1中，重复元素存放在最后一个分量中。试求：数据元素Ak与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. 设对于二维数组Amn，其中m80，n80，读入数组的全部元素，对如下三种情况分别编写相应函数：(1)求数组A靠边元素之和；(2)求从A00开始的互不相邻的个元素之和；(3)当m=n时，分别求两条对角线上的元素之和，否则打印出mn的信息。7-25. 若在矩阵Amn中存在一个元素Ai-1j-1满足：Ai-1j-1是第i行元素中最小值，且又是第j列元素中最大值，则称此元素为该矩阵的一个马鞍点。假设以二维数组存储矩阵Amn，试设计求出矩阵中所有马鞍点的算法，并分析所设计算法在最坏情况下的时间复杂度。7-26. 已知稀疏矩阵用三元组表示，编写C=A*B的算法。7-27. 已知A和B为两个nn阶的对称矩阵，输入时，对称阵只输入下三角元素，存入一维数组，如图7-15所示。编写一个计算对称矩阵A和B的乘积的函数。 图7-15 矩阵的存储转换形式第九章树9-1. 树最适合用来表示 。(1)有序数据元素 (2)无序数据元素 (3)元素数据之间具有分支层次关系的数据 (4)元素之间无联系的数据9-2. 对一棵满二叉树，m个树叶，n个结点，深度为h，则 。(1) n=hm (2) hm=2n (3) m=h1 (4) n=2h19-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. 已知二叉树的先序序列与中序序列分别存放在preodn和inodn数组中，并且各结点的数据值均不相同。请写出构造该二叉链表结构的非递归算法。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-2710-10. 对图10-28所示的连通网络，请分别用Prim算法Kruskal算法构造该网络的最小生成树。10-11. 对图10-29所示的有向图，试利用Dijkstra算法求从顶点v1到其它各顶点的最短路径，并写出执行算法过程中每次循环的状态。 图10-28 图10-2910-12. 对图10-29所示的有向图，试利用Floyd算法求出各对顶点之间的最短路径，并写出执行过程中路径长度矩阵和路径矩阵的变化过程。10-13. 对图10-30所示的AOV网，列出全部可能的拓扑序列，并给出使用TOPOSORTB算法求拓扑排序时的入度域的变化过程和得到的拓扑排序序列。10-14. 对10-31所示的AOE网求出：(1) 各活动的最早开始时间与最迟开始时间；(2) 所有的关键路径；(3) 该工程完成的最短时间是多少?(4) 是否可通过提高某些活动的速度来加快工程的进度? 图10-30 图10-3110-15. 编写一个函数根据用户输入的偶对（以输入0表示结束）建立其有向图的邻接表。10-16. 利用图的深度优先搜索和广度优先搜索各写一个算法，判别以邻接表方式表示的有向图中是否存在由顶点vi到顶点vj的路径(ij) 。10-17. 已知一个以邻接表方式存储的网络及网络中两个顶点。试设计一个算法：(1) 求出这两个顶点之间的路径数目；(2) 求出这两个顶点之间的某个已知长度的路径数目。10-18. 利用深度优先搜索遍历，编写一个对AOV网进行拓扑排序的算法。编写一个函数，求出无向图中连通分量的个数。第十一章 索引和散列11-1. 索引结构的检索分两步完成，第一步是 ，第二步是 。11-2. 稠密索引是指 ，稀疏索引是指 。11-3. 分块查找的基本思想是 ，其查找效率由 决定的。11-4. 倒排表的内容是 ，倒排表检索速度快，但修改维护较难。(1) 一个关键字值和关键字的记录地址(2) 一个属性值和该属性的一个记录地址(3) 一个属性值和该属性的全部记录地址(4) 多个关键字值和它们相对应的某个记录的地址11-5. 散列存储的基本思想是根据 来决定 。11-6. 冲突指的是 ，装填因子越 ，发生冲突的可能性越大。处理冲突的两类主要方法是 和 。11-7. 采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分 个结点最佳。(1) 10 (2) 25 (3) 6 (4) 62511-8. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是 。11-9. 散列函数有一个共同性质，即函数值应当以 取其值域的每个值。(1) 最大概率 (2) 最小概率 (3) 平均概率 (4) 同等概率11-10. 设散列地址空间为0m-1，k为关键字，用p去除k，将所得的余数作为k的散列地址，即H(k)=k MOD p。为了减少发生的冲突的频率，一般取p为 。(1) 小于m的最大偶数 (2) m (3) 大于m的最小素数 (4) 小于m的最大素数11-11. 设有一组职工数据，每个记录有如下格式：职工