自考算法基础复习题

算法基础复习题

试题结构一、单项选择题二、简答题三、算法应用题四、完成算法题试题集一、单项选择题1.1对整数序列5，3，15，1，10，4作从小到大排序，经排序算法一次处理后，该序列变成4，3，1，5，10，15则在以下四种供选择的排序方法中，能实现这个要求的排序方法是A.插入排序B.快速排序C.选择排序D.归并排序1.2对整数序列5，4，16，3，6，1，作从小到大的堆排序，堆排序算法首先对该序列构造最大堆的初始堆，所构造的初始堆序列是A.16、6、5、3、4、1B.16、4、5、6、3、1C.1、3、4、5、6、16D.1、3、5、4、6、161.3用以下四种方法检索线性表，比较适宜于动态检索的是A.分块检索 B.顺序检索C.二分法检索 D.插值检索1.4对于长度为n的线性表，采用顺序检索法查找，每个元素的平均查找时间为A.n/2B.nC.(n-1)/2D.(n+1)/21.5与图的深度优先遍历类似的二叉树的遍历是A.层次B.前序C.中序D.后序1.6某棵完全二叉树的第3层有4个叶子结点（设根结点是第0层），则这棵二叉树的最多结点个数是A、11 B、23 C、27 D、251.7在回溯法中，为了确保算法能够终止，调整时，要确保A.所有可能的候选解都应被检验B.只有哪些最终成为解的候选解才被检验C.可能的候选解能被重复检验D.曾被放弃的候选解不会被再次检验1.8索引表中每个索引项对应数据表中一个记录的索引结构是A.稀疏索引B.动态索引C.稠密索引D.线性索引1.9购物找零钱时，为使找出的零钱硬币数最少，售货员从最大面值的币种开始，按递减的顺序考虑各种硬币，先尽量用大面值的硬币，当不够大面值硬币的金额时才去考虑下一种较小面值的硬币。售货员采用的算法是A.贪婪法B.递推法C.试探法D.动态规划法1.10m路搜索树的高度为h，有最多结点数的搜索树是除叶结点之外，每个结点都有m个子树，高度为h的一棵m路搜索树中，最多关键码数为A.mh+1-1B.mh-1+1C.mh+1D.mh-11.11若希望尽可能快地对整数数组进行稳定的排序，则在以下四种供选择的排序方法中，能实现这个要求的排序方法是A.插入排序B.快速排序C.堆排序D.选择排序1.12设有100个元素组成的线性表，用二分法检索，最大的比较次数是A.100B.10C.7D.501.13任何一个连通无向图，其最小生成树A.有一棵或多棵B.一定有多棵C.可能不存在D.只有一棵1.14迭代算法求方程的根时，如方程有解，但迭代算法还是找不到解，在下列供选择的原因中，是可能原因之一的是A．在程序中没有对迭代次数给予检测B.近似根的初始值选择不合理C.计算机速度不够快D.方程根的精度要求太低。1.15对可能是解的许许多多候选解，按某一种顺序进行逐一枚举和检验，从中找出那些符合要求的候选解作为问题的解。这类算法统称为A.穷举搜索法B.试探法C.贪婪法D.分治法1.16将问题的求解过程分成若干个步骤，在每一步直接根据当前状态，确定下一步骤，而不顾及未来的整体情况。这类算法统称为A.试探法B.动态规划法C.贪婪法D.分治法

1.17对数据量很大的文件，数据增删动态变化也大，频繁作随机查找和顺序查找，宜采用的索引结构为

A、AVL树B、多路动态索引结构C、B+树D、B树1.18当数据表中的记录按记录的加入顺序存放，而不是按关键码有序存放时，这种数据表的索引表必须采用A.稀疏索引结构B.非线性索引结构C.线性索引结构D.稠密索引结构1.19通常，在支持递归算法执行的环境中，采用的数据结构是A.队列B.二叉树C.链表D.栈1.20对整数序列

5，4，9，3，8，2作从小到大排序，经排序算法一次处理后，该序列变成

2，4，9，3，8，5则在以下四种供选择的排序方法中，能实现这个要求的排序方法是A.插入排序B.快速排序C.选择排序D.归并排序1.21在执行操作过程中，将路径上所遇到的结点都直接挂到根结点之下，称作路径压缩，该操作是

A.UnionB.FindC.InsertD.Delete1.22一个有向图所有顶点的入度之和等于所有顶点的出度之和的多少倍

A.4B.2C.1D.1/21.23迭代算法求方程的根时，为了防止方程无解，宜采用的措施是A.在程序中增加对迭代次数给予检测和限制的代码B.自动选择新的初始根C.选择速度更快的计算机D.降低方程根的精度要求1.24把大问题分解成一些较小的问题，然后，由小问题的解答构造出大问题的解答，这类算法统称为A.试探法B.迭代法C.贪婪法D.分治法1.25一种反复扩展、检验，或回溯、检验找问题解的算法，这类算法统称为A.递推法B.动态规划法C.试探法D.贪婪法1.26下列排序算法中，哪一个排序算法在每趟排序后不一定能选出一个元素放到其排序好的序列的正确位置上。A．冒泡排序B．堆排序C．直接插入排序D．选择排序1.27若一个栈的进栈元素序列是1、2、3、4、5，出栈序列的第一个元素是5。则第2个出栈元素是A．3B.4C.2D.不能确定1.28下列有关线性表的叙述中，正确的是A.线性表中任何一对元素之间存在线性关系B.线性表中任何一个元素有且仅有一个直接前趋C.线性表中任何一个元素有且仅有一个直接后继D.线性表中前后元素之间存在线性关系1.29下列关于串的叙述中，正确的是A.空串是全由空格符组成的串B.一个串的字符个数称作该串的长度C.所有串的长度都大于0。D.两个串若所有对应字符不相同，则称这两个串不同1.30在下列内排序方法中，平均比较次数最少的是A.插入排序B.选择排序C.冒泡排序D.快速排序1.31在内排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列中的方法称为A.希尔排序 B.冒泡排序C.插入排序D.选择排序1.32、在长度为n的顺序表中，若在第k（1≤k≤n）位置插入一个元素，则表中元素的移动次数为A、k-1 B、n-k C、k D、n-k+11.33、对整数序列26，43，38，18，19，41，17，31作从小到大的排序，经排序算法一趟处理后，序列变成41，31，43，26，17，38，18，19。试问这是采用何种排序方法A、堆排序 B、选择排序

C、shell排序 D、基数排序

1.34、对整数序列26，12，38，18，29，51，17，11作从小到大的排序，经排序算法一趟处理后，序列变成51，11，12，26，17，38，18，29。试问这是采用何种排序方法A、堆排序

B、计数排序

C、基数排序

D、shell排序1.35、一棵查找二叉树，其结点A、B、C、D、E、F。如果该查找二叉树的根结点为C，则在以下供选择的4个序列中，可能是它的层次遍历序列的是A、CAFDBE B、CADEBF C、CABDFE D、CAFBED1.36、若循环队列以数组Q[0..m-1]作为其存储结构，变量rear表示循环队列中队尾元素在队列数组中的下标，其增1修改按rear=(rear+1)%m计算，变量length表示队列中的元素个数，则循环队列中队首元素在队列数组中的下标是A、(rear-length+m)%m B、(1+rear-length+m)%m C、m-length D、rear-length1.37、对整数序列5，3，15，1，13，4作从小到大排序，经排序算法一次处理后，该序列变成3，5，15，1，13，4则在以下四种供选择的排序方法中，能实现这个要求的排序方法是

A、快速排序 B、插入排序

C、选择排序 D、归并排序

1.38、一棵查找二叉树，其结点A、B、C、D、E、F。如果该查找二叉树的根结点为D，则它的一种可能的前序遍历为

A、DABCFE B、DAFCEB C、DAFCBE D、DACEBF

1.39、把复杂问题分解出一系列子问题，为不重复求相同子问题，把新的子问题的解答暂存于一个数组中，待再次解同样子问题时，就从数组中取出该子问题的解答。这类算法通称A、试探法 B、迭代法

C、动态规划法 D、贪婪法

1.40、一棵查找二叉树，其结点A、B、C、D、E、F依次存放在一个起始地址为n(假定地址以字节为单位顺序编号)的连续区域中，每个结点占4个字节：前二个字节存放结点值，后二个字节依次存放左指针、右指针。如果该查找二叉树的根结点为E，则它的一种可能的前序遍历为(1)，相应的层次遍历为(2)。在以上两种遍历情况下，结点C的左指针的存放地址为(3)，该地址中的内容为(4)。结点A的右指针的内容为(5)(1)A．EAFCBDB．EFACDBC．EABCFDD．EACBDF(2)A．EAFCBDB．EFACDBC．EABCFDD．EACBDF(3)A．n+9B．n+10C．n+12D．n+13(4)A．n+4B．n+8C．n+12D．n+16(5)A．n+4B．n+8C．n+12D．n+16二、简答题2.1把一些虽非关键码，但又经常搜索的属性称为次关键码2.2算法分析的目的就是估算出问题规模与算法的效率或开销的函数关系2.3递归算法的执行过程分哪两个阶段。在前一阶段，把较复杂的问题的求解递推到比原问题简单一些的若干子问题的求解。在后一阶段，当获得最简单情况的解后，依次获得稍复杂的问题的解递推、回归2.4若待排序的结点序列中，每个结点都包含有许多其他信息，则插入排序、选择排序和冒泡排序三种排序算法中，最适宜的排序方法是选择排序2.5将问题的求解过程分成若干个步骤，在每一步骤直接根据当前状态，确定下一步骤，而不顾及未来的整体情况，这类求解方法统称为贪婪法2.6在回溯算法中，为了确保算法能够终止，回溯调整时，必须保证曾被检验而放弃过的候选解不被再检验2.7设4路搜索树的高度为3，有最多结点数的搜索树是除叶结点之外，每个结点都有4个子树。所以，最多结点数是852.8在B树上进行搜索，若搜索成功，则所需读取结点的次数取决于关键码所在B树的层次2.9设有如下定义的递归函数p()，则函数调用p(4)所计算的数学式子(不要求计算结果)是

doublep(intt){if(t==1)return2.0;return2.0+t/p(t-1);}2.0+4/（2.0+3/（2.0+2/2.0））2.10对关键字序列（55、57、35、56、31、27、68、22）进行快速排序，并设在快速排序过程中作分划的基准数为分划序列的第一个数。这样，进行一次分划后，得到的关键字序列为22，27，35，31，55，56，68，572.11在插入排序、选择排序、归并排序和基数排序这四种排序方法中，最好和最坏情况下的时间复杂度均为O(nlbn)，且稳定的排序方法是归并排序2.12通过何种遍历二叉检索树，可以得到一个排好序的结点序列。中序遍历2.13迭代算法求方程的根时，为了防止方程无解，宜在迭代算法的程序中增加对什么给予检测和限制的代码迭代次数2.14一种反复扩展、检验，或回溯、检验找问题解的算法。这类算法统称为试探法2.15m路搜索树的根结点最多有m棵子树，结点中的关键码个数是mh+1-12.16在B+树上能进行的搜索方法有顺序、随机2.17有向图G用邻接矩阵存储，其第K列的所有元素之和等于顶点K的入度2.18用代码writeN1(12345)调用以下递归函数，递归函数的输出结果是

voidwriteN1(intn){if(n<10)printf(“%d”,n);else{writeN1(n/10);printf(“%d”,n%10);}}123452.19用代码writeN2(12345)调用以下递归函数，递归函数的输出结果是

voidwriteN2(intn){if(n<10)printf(“%d”,n);else{printf(“%d”,n%10);writeN2(n/10);}}543212.20对于具有n个顶点、e条边的图，若采用邻接表存储结构，则按深度优先遍历图的时间复杂性为O(n+e)2.21若待排序的整数序列是已排好序的，用插入排序、选择排序和冒泡排序三种排序算法对该序列作排序处理，则能最快结束排序的排序方法是插入排序2.22一种利用结点的关键码值,确定结点在数据结构中的位置的技术,称为散列技术2.23对关键字序列：

47、20、52、11、59、15、18、50、54、15进行快速排序，并设在快速排序过程中作分划的基准数为分划序列的第一个数、中间数和末位置数，这三个数中的中间大小的哪一个数，并在确定基准数的同时，将最小的数放于数列的最前端，最大的数放在数列的最后端。划分时，先将基准数存于划分序列最后(数列最后第二个位置)。这样，进行一次分划后，得到的关键字序列为。15，20，18，11，15，47，52，50，54，59

2.24有向图G用邻接矩阵存储,其第K行的所有元素之和等于顶点K的出度2.25用Dijkstra算法求某顶点出发到其他所有顶点的最短路径是按路径长度的什么次序求得的。递增2.26检查解答树的过程中，为提高检查速度，被利用的解答树性质是：解答树中任一棵子树，只要该子树的根结点不满足条件，它就不会含有什么。因而可以不必考虑这棵子树。解2.27索引表中每个索引项对应数据表中一个记录的索引结构是稠密索引2.28写出使用归并排序法对下列数据进行从小到大排序的中间过程和最后结果。{83，40，63，13，84，35，96，57，39，79，61，15}{40，83，13，63，35，84，57，96，39，79，15，61}

{13，40，63，83，35，57，84，96，15，39，61，79}

{13，35，40，57，63，83，84，96，15，39，61，79}

{13，15，35，39，40，57，61，63，79，83，84，96}

2.29对于一个栈，如果输入序列为A、B、C，试给出全部可能的输出序列。ABC、ACB、BAC、BCA、CBA2.30为以下模式求出各位置字符的失败链接值。XYAXAXYAZAAXAYAAZAAXAZ-10-10-101-10123-1-1-1-10-1012-12.31、设散列表长度为11，散列函数是h(x)=x%7，采用开地址法，并用线性探查法解决冲突。试将关键字序列（22、10、15、11、4、18、20）按上述规则填入以下散列表中。0123456789102215101118202.32、用树表示离散集合{0、1、2、3、4、5}，并用数组存储，又设初始时，每个元素均独立是一个集合，给出连续执行并操作union(3,2);union(3,5);union(1,3)后，数组各元素的值。约定，union(s1,s2)是s2所在集合合并至s1所在集合。012345-1-131-132.33、已知关键字序列（58、32、40、27、18、28、25、19、26）是一个最大堆，从堆删除最大元，并使删除最大元后的序列重新调整成最大堆，给出调整后的最大堆的序列。40、32、28、27、18、26、25、192.34、对关键字序列（215、328、457、123、149、265）进行基数排序，需作多遍计数排序处理。分别给出第一遍和第二遍处理之后得到的关键字序列。

2.35、以下是一棵3阶B树，对这棵B树删除关键码85，试画出删除后的B树。012345123215265457328149215123328149457265删除后

2.36、对于给定的一组关键字序列{19,13,45,20,7,26,34,17,35}，写出冒泡排序的各趟冒泡结果。第一趟：7,19,13,45,20,17,26,34,35第二趟：7,13,19,17,45,20,26,34,35第三趟：7,13,17,19,20,45,26,34,35第四趟：7,13,17,19,20,26,45,

34,35第五趟：7,13,17,19,20,26,45,

34,35第六趟：7,13,17,19,20,26,34,45,35第七趟：7,13,17,19,20,26,34,35,45第八趟：7,13,17,19,20,26,34,35,452.37、采用BM算法，用模式“UVWXVWXY”对正文作匹配，先要求各字符的d函数值。d[Z]、d[Y]和d[W]的值依次是d[Z] =8d[Y] =8d[W] =2

三.算法理解题3.1、设T为二叉检索树，K为检索关键码，试说出检索的主要步骤。1、如果T为空，检索失败2、T的根结点的关键码等于K，检索成功3、T的根结点的关键码大于K，检索T的左子树4、T的根结点的关键码小于K，检索T的右子树3.2、输入一组记录构造一棵二叉检索树，设输入记录的关键字依次为10，18，3，9，7，6，8，25，2，8，20试画出按所给出的顺序输入记录，所构造的一棵二叉检索树。3.3、对下图所示二叉检索树，画出执行删除关键字78结点后的二叉检索树。删除后的二叉检索树3.4、输入一组记录构造一棵AVL树，设输入记录的关键字依次为50，30，20，40，55，46，42，48，45试画出按所给出的顺序输入记录，所构造的一棵AVL树。3.5、简述利用m路B+树，随机搜索一个给定键值为k的记录的地址的查找过程，与B树上搜索的查找过程的主要区别。3.6、试述二叉检索树的定义,并举一例。3.7、什么叫动态检索?3.8、在m路B树上查找一个给定键值k的记录的地址时，如果当前结点有n个键值，它的键值序列是k1，k2，…，kn。查找时需考虑哪几种情况，又分别作何处理？3.9、试指出m路搜索树结点的结构。3.10、试指出一般的m路搜索树与B树的区别。3.11、试指出B树与B+树的区别。3.12、试指出KMP算法与简单匹配算法的改正之处。3.13、指出BM算法与KMP算法的主要差异。3.14、对于下列图，分别写出按深度优先搜索（从顶点A出发）和按广度优先搜索（从顶点F出发）的顶点访问序列。设顶点按字母顺序编号，要求按该图的邻接矩阵进行遍历。

3.15、对于下列带权有向图，画出其相应的邻接矩阵和邻接表。

A15E2114818BD207C3.16、对于下列2图,分别采用Kruskal算法构造最小生成树，画出构造各步骤的全过程。(1)(2)3.17、采用Prim算法构造下图的最小生成树，画出构造各步骤全过程(以A为起始顶点)。

A27F203225D28BE263524C3.18、试按Dijkstra算法，给出下列3图从顶点（A）出发到其它各顶点最短路经的求解过程。DistPathB70,50,45A->B,A->C->B,A->C->D->BC25

A->CD---,30----,A->C->DE40,35A->E,A->C->D->E

3.19、对关键字序列（48、30、63、54、58、27、37）进行SHELL排序，设第一次取间隔g为3，则进行第一趟处理之后得到的结果为3.20、设输入记录的关键码依次为:8，14，3，7，16，5，6，构造一棵3阶B树。试画出按所给出的关键码顺序输入记录，从空的B树开始，构造一棵3阶B树的构造过程。3.21、整数序列{9，4，6，2，3，5}是一个最大堆，要在这个堆中插入7，并使序列继续是一个最大堆，试给出插入7后的新序列。3.22、设用BM算法进行字符串匹配，如果模式字符串为shanghai，试给出字符xshai的d函数的值。d(x)=8,d(s)=7,d(h)=2,d(a)=1,d(i)=8。函数d定义方法如下：(1)若x不在模式S中出现，或是模式中最后出现（x=sm-1），但x≠sj(0<=j<m-1)，定义d(x)=m；(2)其余情况，这里j=max{j，sj=x，x≠sj(0<=j<m-1)}，定义d(x)=m-1-j。3.23、某系统在通信联系中将出现7个字符：a,b,c,d,e,f,g，其概率分别是0.09,0.20,0.05,0.08,0.15,0.22,0.21，试设计7个字符的赫夫曼编码。并说明其过程。a:100b:111c:1010d:1011e:110f:01g:003.24、下图是一棵AVL树，给出在这棵AVL树上插入13后的新AVL树。3.25、下图是一棵3阶B树，画出对该树删除关键码50以后的3阶B树。3.26、下图是一棵4阶B+树，叶子结点的m1=5,画出对该树加入关键码28后的B+树。3.27、下图是一棵4阶B+树，叶子结点的m1=5,画出对该树删除关键码33以后的B+树。四．完成算法题4.1顺序将数字1至n进栈(中间可以任意插入退栈)，求所有可能的出栈顺序。引入栈S和队列Q。将1至n顺序进到栈S，出栈的元素存入队列Q。当全部元素都进入队列时，就找到了一个可能的出栈序列，将队列中的元素依次输出。采用递归方法，并设函数有以下模型：voidf(intn,intins,intsn,intqn)n：还能进栈的元素个数ins：下一个进栈元素sn：当前栈中元素个数qn:当前队列中的元素个数。算法要完成的工作分这样多种情况：当全部元素都进入队列时，将队列的元素顺序输出，结束递归；当还有元素可进栈时，将下一个元素进入栈S，继续递归找解；当栈非空时，可将栈顶元素退栈，并将该元素存入队列Q，并继续递归，在递归返回后恢复递归之前栈顶元素的值。voidf(intn,intins,intsn,intqn){intk;if(n==0&&___(1)___){/*元素已全部进入队列*/for(k=0;k<qn;k++)/*顺序输出队列中的元素*/printf("%6d",Q[k]);printf("\n");return;}if(n>0){/*有元素可进栈*/___(2)___;/*欲进栈的元素进栈*/f(n-1,ins+1,___(3)___,qn);/*递归找解*/}if(sn>0){/*栈中有元素可出栈进入队列*/Q[qn]=___(4)___;/*当前栈顶元素退栈进队列*/f(n,ins,___(5)___,qn+1);/*递归找解*/S[sn-1]=Q[qn];/*恢复原来栈的状态*/}}sn==0S[sn]=inssn+1S[sn-1]sn-14.2这里给出的是Shell排序的一个实现，设待排序的序列有n个元素，首先取一个整数g=n/2作为间隔，将全部待排序元素分为g个子序列，依次间隔g个位置的元素为一个子序列。对每一个子序列分别施行直接插入排序，然后缩小间隔g，取g=g/2，重复上述的子序列划分和子序列排序工作，直到最后取g为1,对整个集合作一次插入排序。使整个序列变成有序。voidshellSort(inte[],intn){intg;inti,j;intt;g=n;do{g=g/2;for(__(1)__;i<n;i++){for(t=e[i],j=i;__(2)__&&t<e[j-g];__(3)__)__(4)__;__(5)__=t;}}while(g!=1);}(1)i=g;(2)j>=g(3)j=j-g(4)e[j]=e[j-g](5)e[j]4.3以下函数rr(inta[],intn)用O(n)的时间复杂性重排数组a[]，将所有取负值的放在a[]的最前面，等于0的留在a[]的中间，大于0的移到a[]的最后面。设重排的数组a[]有n个元素a[0]至a[n-1]，算法自a[0]开始顺序逐一考察a[]中的元素，当前正准备考察元素a[i]。在重排过程中，已发现有neg个元素小于0，已经将它们移至a[0]至a[neg-1]，发现pos个元素大于0，已经将它们移至a[n-pos]至a[n-1]，而a[neg]至a[i-1]是已发现等于0的元素，a[i]至a[n-pos-1]是还未考察的元素。算法根据a[i]小于0、等于0和大于0三种不同情况作不同处理。由于a[]中的元素只被考察一次，所以算法的时间复杂性是O(n)的。

voidrr(inta[],intn){inti,neg,pos,t;neg=0;pos=0;i=0;while(i<n-pos)if(a[i]<0){/*a[i]是负数时*/t=a[i];a[i]=a[neg];a[neg]=t;___(1)___;i++;}elseif(a[i]==0)___(2)___;/*a[i]是0时*/else{/*a[i]是正数时*/t=a[i];a[i]=___(3)___;___(4)___=t;___(5)___;}}neg++i++a[n-pos-1]a[n-pos-1]pos++4.4这里给出的是一个实现插入排序算法的函数，在该函数中，寻找插入位置时，利用被插入的元素段的有序性用二分法寻找插入位置，然后插入处之后的有序段元素后移一个位置，得到一个空位将新的值插入到有序段中。

voidinsertSort(inte[],intn){inti,j,left,right,m;inttemp;for(i=1;i<n;i++){temp=e[i];left=0;right=___(1)___;/*设定初始查找区间*/while(left<=right){/*寻找插入位置*/m=(left+right)/2;if(temp>e[m])___(2)___;else___(3)___;}for(j=i-1;___(4)___;j--)/*插入处之后的元素后移*/____(5)____;___(6)___=temp;}}i-1left=m+1right=m-1j>=lefte[j+1]=e[j]e[left]4.5以下函数

intmerge(intx[],intxn,inty[],intyn,intz[])实现将两个从小到大有序的数组x和y，归并到数组z，并使z也从小到大有序。函数返回z[]的元素个数。intmerge(intx[],intxn,inty[],intyn,intz[]){inti,j,k;i=0;j=0;k=0;while(___(1)___)z[k++]=(x[i]<=y[j])?___(2)___;while(i<xn)___(3)___;while(j<yn)___(4)___;return___(5)___;}i<xn&&j<ynx[i++]:y[j++]z[k++]=x[i++]z[k++]=y[j++]k4.6以下函数intmerge(intx[],intxn,inty[],intyn,intz[])实现将两个从小到大有序的数组x和y，归并到数组z，并使z也从小到大有序，并要求在z中没有相等的元素。函数返回归并后数组z中的元素个数intmerge(intx[],intxn,inty[],intyn,intz[]){inti,j,k;i=0;j=0;k=0;while(___(1)___)if(x[i]<=y[j]){if(k==0||x[i]!=z[k-1])___(2)___;i++;}else{if(k==0||y[j]!=z[k-1])___(3)___;j++}for(;i<xn;i++)if(k==0||x[i]!=z[k-1])___(4)___;for(;j<yn;j++)if(k==0||y[j]!=z[k-1])___(5)___;return___(6)___;}i<xn&&j<ynz[k++]=x[i]z[k++]=y[j]z[k++]=x[i]z[k++]=y[j]k4.7下面的函数是将二叉树t中所有结点的左右子树进行交换。函数用顺序栈存放还未处理完的子树的根结点指针。试完全该函数。typedefstructtnode{intval;structtnode*lchild,*rchild;}binNODE;binNodestack[100];voidexchange(binNODE*t){inttop;binNODE*p;top=0;stack[top++]=t;while(___(1)___){/*栈非空情况下循环*/t=___(2)___;if(___(3)___){/*对于非空的二叉树完成以下处理*/p=t->lchild;t->lchild=t->rchild;t->rchild=p;___(4)___=t->lchild;___(5)___=t->rchild;}}}top>0stack[--top]t!=NULLstack[top++]stack[top++]4.8这里给出的是一个直接插入排序算法。算法假定所给的数组还有一个多余的元素空间，算法采用从后向前方法排序，让排序过程中有序段在数组的后部。算法利用这个多余的元素空间简化了找插入位置的循环条件。voidinsertSort(inte[],intn){intk,j;for(k=____(1)___;k>=0;k--)if(e[k]>e[k+1]){/*若e[k]不大于有序段首元素值的值，则e[k]的位置暂时不动*/e[n]=e[k];j=____(2)___;while(____(3)___>e[j]){____(4)___;j++;}____(5)___=e[n];}}n-2k+1e[n]e[j-1]=e[j]e[j-1]4.9以下函数

voidcountMarkSort(STUTYPEe[],intn)实现已知学生成绩表，为学生计算名次。设学生成绩表中的每个元素是一个记录，对应一个学生，有学生的学号、成绩(<=100)和名次三个成分。函数首先根据成绩统计各成绩的人数，然后计算每个分数的名次，最后，根据学生成绩得到该生的名次。

typedefstructnode{charno[10];/*学号字符串*/intmark;/*成绩*/intorder;/*名次*/}STUTYPE;voidcountMarkSort(STUTYPEe[],intn){int*t,k,u,v;t=(int*)malloc(101*sizeof(int));for(k=0;k<=100;k++)t[k]=0;for(k=0;k<n;k++)/*统计每个分数的人数*/t[_____(1)____]++;for(u=1,k=100;k>=0;k--){/*计算各分数的名次*/v=_____(2)_____;t[k]=_____(3)_____;//当前分数的名次

u=_____(4)_____;//下一个分数的名次

}for(k=0;k<n;k++)e[k].order=t[_____(5)_____];/*填写各学生的名次*/free(t);}e[k].markt[k]uu+ve[k].mark4.10从已知含m个元素的数据序列a中找出部分和为s的最多个数的部分元素。设序列的元素都大于0，序列的全部元素之和不小于s。用递归算法找解，顺序考虑序列的每个元素，对已知序列的每个元素有独立的两种处理方案，如果当前元素被包括在当前解中是允许的(使部分元素和不大于s)，则将它包含在当前解中，并继续递归去考虑其后的元素；如果当前元素不包含在当前解中还是有可能找到更多的和为s的元素(已知序列的元素和小于s)，则考虑不将它包含在解中，并继续递归去考虑其后的元素。设递归函数的模型为：voidfind(int*a,intm,ints,intts,intk)各参数的意义分别为：已知数据序列的首元素指针a，已知数据序列的元素个数m,要求的部分元素和s,已知序列的全部元素和ts,现在欲求部分元素的第k个和数。令函数找解过程中当前正在寻找的数列存于数组p[]，函数将找到的解存于数组q[]，其中q[0]存储解的和数个数。

voidfind(inta[],intm,ints,intts,intk){intj;if(___(1)___)return;/*已知数据序列为空

m==0*/if(s==0&&___(2)___){/*找到解,且元素个数更多k-1>q[0]*/for(j=1;j<k;j++)q[j]=p[j];/*将解保存*/q[0]=___(3)___;/*保存当前解的元素个数,k-1*/return;/*结束递归*/}if(ts<s)return;/*已知序列的元素和小于s，不会有解*/if(*a<=s){/*当前元素不大于和s，对它作选取考虑*/p[k]=*a;/*考虑将当前元素包含在解中*/find(a+1,m-1,___(4)___,ts-*a,k+1);/*继续递归找解,s-*a*/}if(ts-*a>=s&&___(5)___>q[0])//k-1+m/*后继序列的元素和不小于s，且序列元素个数足够多，不取当前元素，去考虑其他可能性*/find(a+1,m-1,s,ts-*a,k);/*递归找解*/}4.11一场激烈的足球赛开始前，售票工作正在紧张进行，每张球票50元。现有2n人排队等待购票，其中有n个人手持50元，另外n个人手持100元。假设开始售票时售票处没有零钱，问这2n个人有多少种排队方式，使售票处不至出现找不开钱的局面。若采用动态规划法，就有以下思考过程：令f(x,y)表示有x个人持50元的钞票，y个人持100元的钞票时共有的方案总数。有以下三种不同情况：(1)y=0：排队购票者都持50元钞票，这x个人排队总数为1，即f(x,0)=1。(2)x<y：因有人不能得到零钱，排队总数为0，即f(x,y)=0。(3)其它情况：有x+y人排队购票，第(x+y)人站在第(x+y-1)人的后面，则第(x+y)人的排队方式可由下列两种情况获得：(3.1)第(x+y)人持100元的钞票，则在他之前的(x+y-1)个人中有x个人持50元钞票，有(y-1)个人持100元钞票，此种情况共有f(x,y-1)。(3.2)第(x+y)人持50元的钞票，则在他之前的(x+y-1)个人中有（x-1）个人持50元钞票，有y个人持100元钞票，此种情况共有f(x-1,y)。x+y个人的排队方案应是上述两种情况之和，即(fx.y)=f(x-1,y)+f(x,y-1)。于是得到f(x,y)的计算公式：

0,x<y;f(x,y)=1,y=0;f(x-1,y)+f(x,y-1)，其它情况。综上所述，得到问题的动态规划求解算法：#defineX40#defineY40intf[X+1][Y+1];intarithmetic(intx,inty){if(y>x)return0;

为数组f的首列各元素赋值1;

赋数组f的上三角元素为0;

按其他情况，计算数组f的其他元素;returnf[x][y];}#defineX40#defineY40intf[X+1][Y+1];intarithmetic(intx,inty){inti,j;if(y>x)return0;for(i=1;i<=x;i++)___(1)___;//f[i][0]=1for(j=0;j<x;j++)f[j][j+1]=0;for(i=1;i<=___(2)___;i++)//xfor(j=1;j<=___(3)___;j++)//y

f[i][j]=___(4)___;//f[i-1][j]+f[i][j-1]return___(5)___;//f[x][y]}4.12、设用有序链表表示集合，以下是完成新元素加入到集合的函数。/*a加入到集合，若集合已有此元素，函数返回0，否则函数返回1*/typedefstructnode{intele;structnode*next;}EleNode;typedefstruct{EleNode*head;//集合链表的首指针}DISJSETS;intinsertEle(inta,DISJSETS*S){EleNode*p=S->head->next,*q=S->head,*s;while(p!=NULL&&____(1)____){//

p->ele<a

q=p;p=p->next;}if(p!=NULL&&____(2)____)//

p->ele==areturn0;s=(EleNode*)malloc(sizeof(EleNode));s->ele=a;s->next=____(3)____;//

p____(4)____;//q->next=sreturn1;}4.13、设用有序链表表示集合，以下是从有序链表表示的集合中删除元素的函数。*从集合删除a。集合不空，元素a在集合中，函数删除a后返回1，否则返回0*/typedefstructnode{intele;structnode*next;}EleNode;typedefstruct{EleNode*head;//集合链表的首指针}DISJSETS;intdeleteEle(inta,DISJSETS*S){EleNode*p=S->head->next,*q=S->head;while(p!=NULL&&____(1)____){//p->ele<aq=p;p=p->next;}if(____(2)____&&____(3)____){//(2)p!=NULL(3)p->ele==aq->next=____(4)____;//

p->nextfree(p);return1;}return0;}4.14、设堆的数据类型BinaryHeap定义如下：typedefintComparable;#defineMAXHEAP100//堆最多元素typedefstruct{intcurrentSize;Comparablee[MAXHEAP];//这里可以加入堆的其它信息｝BinaryHeap;元素X插入到堆中，可先把X放入堆的下一个有效位置，如果X放入后不违背堆的有序性，则插入操作就结束。否则，将它的父结点渗透到该结点位置，而将X上冒到父结点位置。如果这样的渗透和上移以后，还是不能满足堆的有序性，则X的新的父结点继续向下渗透，X继续向根结点方向上移。如此调整，直至满足堆的有序性。堆上插入新结点的算法如下：intbiHeapInsert(ＢinaryHeap*heap,Comparablex){inthole=heap->currentSize,father;if(heap->currentSize>=MAXHEAP)return0;//因堆已满，不能再插入for(;hole>0&&x<heap->e[father=___(1)___];___(2)___)heap->e[hole]=___(3)___;//父结点向下渗透，插入位置上移heap->e[___(4)___]=x;___(5)___；return1;}

(hole-1)/2hole=fatherheap->e[father]holeheap->currentSize++4.15、设堆的数据类型BinaryHeap定义如下：typedefintComparable;#defineMAXHEAP100//堆最多元素typedefstruct{intcurrentSize;Comparablee[MAXHEAP];//这里可以加入堆的其它信息｝BinaryHeap;删除最小堆中最小结点就是删除堆的根结点。删除根结点后，先将堆的最后元素X移到根结点位置，接着将它的两个子结点中较小的结点上移到根结点位置，而将X渗透到这个子结点位置。重复这个过程，直到X放入的某个位置，能使这个变小后的数据集重新变成堆为止。实际上，从根结点开始，沿着含较小的子树根结点的路径向下，到达X放入后能满足堆的有序性的正确位置。以下是堆上删除优先结点的算法：intbinaryHeapDeleteMin(ＢinaryHeap*heap,Comparable*xp){inthole,child;Comparabletmp;if(heap->currentSize==0)return0;//堆空*xp=___(1)___;tmp=heap->e[--heap->currentSize];for(hole=0;hole*2<heap->currentSize;hole=child){child=___(2)___;//左子结点if(child+1<heap->currentSize&&heap->e[child+1]<heap->e[child])child++;//右子结点更小if(___(3)___<tmp)//空位还要下移heap->e[hole]=___(4)___;//上冒elsebreak;}heap->e[___(5)___]=tmp;return1;}

heap->e[0]2*hole+1heap->e[child]heap->e[child]hole4.16、给定一个带权有向图G和源点v0，用Dijkstra算法求从v0到G中其它顶点的最短路径的长度。设图G各边的权值大于0，图用邻接矩阵表示。引入数组S存放已求出最短路径的顶点集合，初始时，S只有源点。以后每求得一条路径，就将路径的终点加入到S中。直至全部顶点都在S中时，算法结束。为了便于找到从源点v0到其他顶点的最短路径，另引入数组dist[]。它的元素dist[i]存储从源点v0到顶点vi的最短路径的长度。初始时，若从源点v0到顶点vi有边，则dist[i]即为该边的权值；若从源点v0到顶点vi没有边，则dist[i]为+

（99999）。#defineMaxInt99999intShortestPath(Mgraph*G,intv0,intdist[]){ints[MaxVerticesNum];inti,j,k,min;for(i=0;i<G->n;i++){dist[i]=G->edges[v0][i];____(1)____;}s[v0]=1;dist[v0]=0;for(j=0;j<G->n-1;j++){//循环n-1次for(min=MaxInt,i=0;i<G->n;i++)if(____(2)____&&dist[i]<min){//寻找下一条最短路径的终点kmin=____(3)____;k=i;}if(min==MaxInt)return-1;//不连通的图s[k]=1;//S←SU{k};for(i=0;i<G->n;i++)//修改dist[i],i

V-S:if(____(4)____&&G->edges[k][i]<MaxInt&&___(5)___)dist[i]=dist[k]+G->edges[k][i];}return0;}(1)s[i]=0(2)s[i]==0(3)dist[i](4)s[i]==0(5)dist[i]>dist[k]+G->edges[k][i];4.17、函数selectSort是采用选择排序法，对数组b[]中的n个元素按递增次序进行排序。voidselectSort(intb[],intn){intk,j,minIndex;temp;for(k=0;k<___(1)____;k++){minIndex=k;for(j=___(2)____;j<____(3)____;j++)if(b[j]<b[minIndex])____(4)____;if(____(5)____){temp=b[k];b[k]=e[minIndex];e[minIndex]=temp;}}}n-1(2)k+1(3)n(4)minindex=j(5)k!=minindex4.18、函数unionSet(DISJSETS*S1,DISJSETS*S2)实现集合S1与S2的并，结果在S1中,集合S1与S2用具有辅助结点的有序(从小到大)链表表示。类型为：typedefstructnode｛intele;structnode*next;｝EleNode;//链表表元类型typedefstruct｛EleNode*head;//集合链表的首指针}DISJSETS;//集合类型voidunionSet(DISJSETS*S1,DISJSETS*S2){EleNode*p,*q,*t;//t指向新的S1*p=S1–>head–>next,*q=S2–>head–>next,*t=S1–>head;while(____(6)____){//p!=NULL&&q!=NULLif(p–>ele==q–>ele)//两集合共有的元素,S1的当前结点接在新的S1上

{t–>next=p;p=p–>next;q=q–>next;}elseif(p–>ele<q–>ele)//S1的当前元素小，将它接在新的S1上

{____(7)____;____(8)____;}//

t->next=p;p=p->next;else{//S2的当前元素小，复制结点接在新的S1上

t–>next=(EleNode*)malloc(sizeof(EleNode));t–>next–>ele=q–>ele;q=q–>