[其它课程]算法复习题新

算法基础复习题算法基础复习题 试题结构试题结构一、单项选择题一、单项选择题二、简答题二、简答题三、算法应用题三、算法应用题四、完成算法题四、完成算法题试题集试题集一、单项选择题一、单项选择题1.1、对整数序列、对整数序列 5， 3， 15， 1， 10， 4作从小到大排序，经排序算法一次处理后，该序列作从小到大排序，经排序算法一次处理后，该序列变成变成 4， 3， 1， 5， 10， 15则在以下四种供选择的排序方法中，能实现这个要则在以下四种供选择的排序方法中，能实现这个要求的排序方法是求的排序方法是A. 插入排序插入排序 B. 快速排序快速排序 C. 选择排序选择排序 D. 归并排序归并排序1.2、对图作广图优先遍历，要采用的数据结构是对图作广图优先遍历，要采用的数据结构是A、栈、栈B、优先队列、优先队列C、堆、堆D、队列、队列1.3、对于长度为对于长度为n 的线性表，采用顺序检索法的线性表，采用顺序检索法查找，每个元素的平均查找时间为查找，每个元素的平均查找时间为 A . n/2 B. n C. (n-1)/2 D. (n+1)/2 1.4、在回溯法中，为了确保算法能够终止，、在回溯法中，为了确保算法能够终止，调整时，要确保调整时，要确保 A. 所有可能的候选解都应被检验所有可能的候选解都应被检验 B. 只有哪些最终成为解的候选解才被检验只有哪些最终成为解的候选解才被检验C. 可能的候选解能被重复检验可能的候选解能被重复检验 D. 曾被放弃的候选解不会被再次检验曾被放弃的候选解不会被再次检验1.5、索引表中每个索引项对应数据表中一个、索引表中每个索引项对应数据表中一个记录的索引结构是记录的索引结构是 A. 稀疏索引稀疏索引 B. 动态索引动态索引 C. 稠密索引稠密索引 D. 线性索引线性索引1.6、购物找零钱时，为使找出的零钱硬币数、购物找零钱时，为使找出的零钱硬币数最少，售货员从最大面值的币种开始，按递减最少，售货员从最大面值的币种开始，按递减的顺序考虑各种硬币，先尽量用大面值的硬币，的顺序考虑各种硬币，先尽量用大面值的硬币，当不够大面值硬币的金额时才去考虑下一种较当不够大面值硬币的金额时才去考虑下一种较小面值的硬币。售货员采用的算法是小面值的硬币。售货员采用的算法是 A. 贪婪法贪婪法 B. 递推法递推法 C. 试探法试探法 D. 动态规划法动态规划法1.7、m路搜索树的高度为路搜索树的高度为h，有最多结点数的，有最多结点数的搜索树是除叶结点之外，每个结点都有搜索树是除叶结点之外，每个结点都有m个子个子树，高度为树，高度为h的一棵的一棵m路搜索树中，最多关键路搜索树中，最多关键码数为码数为 A.mh+1-1 B.mh-1+1 C.mh+1 D.mh-11.8、若希望尽可能快地对整数数组进行稳定的排序，、若希望尽可能快地对整数数组进行稳定的排序，则在以下四种供选择的排序方法中，能实现这个要求则在以下四种供选择的排序方法中，能实现这个要求的排序方法是的排序方法是 A. 插入排序插入排序 B. 快速排序快速排序 C. 堆排序堆排序D. 选择排序选择排序1.9、迭代算法求方程的根时，如方程有解，但迭代算法还是、迭代算法求方程的根时，如方程有解，但迭代算法还是找不到解，在下列供选择的原因中，是可能原因之一的是找不到解，在下列供选择的原因中，是可能原因之一的是 A在程序中没有对迭代次数给予检测在程序中没有对迭代次数给予检测 B. 近似根的初始值选择不合理近似根的初始值选择不合理C. 计算机速度不够快计算机速度不够快 D. 方程根的精度要求太低。方程根的精度要求太低。1.10、对可能是解的许许多多候选解，按某一种顺序进行逐、对可能是解的许许多多候选解，按某一种顺序进行逐一枚举和检验，从中找出那些符合要求的候选解作为问题的一枚举和检验，从中找出那些符合要求的候选解作为问题的解。这类算法统称为解。这类算法统称为 A. 穷举搜索法穷举搜索法 B. 试探法试探法 C. 贪婪法贪婪法 D. 分治法分治法 1.11、将问题的求解过程分成若干个步骤，在每一步直接根将问题的求解过程分成若干个步骤，在每一步直接根据当前状态，确定下一步骤，而不顾及未来的整体情况。这据当前状态，确定下一步骤，而不顾及未来的整体情况。这类算法统称为类算法统称为 A. 试探法试探法 B. 动态规划法动态规划法 C. 贪婪法贪婪法 D. 分治法分治法 1.12、对数据量很大的文件，数据增删动态变化也大，频繁对数据量很大的文件，数据增删动态变化也大，频繁作随机查找和顺序查找，宜采用的索引结构为作随机查找和顺序查找，宜采用的索引结构为 A、AVL树树 B、多路动态索引结构、多路动态索引结构 C、B+树树 D、B树树1.13、当数据表中的记录按记录的加入顺序存放，而不是按、当数据表中的记录按记录的加入顺序存放，而不是按关键码有序存放时，这种数据表的索引表必须采用关键码有序存放时，这种数据表的索引表必须采用 A. 稀疏索引结构稀疏索引结构 B. 非线性索引结构非线性索引结构 C. 线性索引结构线性索引结构 D. 稠密索引结构稠密索引结构1.14、通常，在支持递归算法执行的环境中，采用的数据结、通常，在支持递归算法执行的环境中，采用的数据结构是构是 A. 队列队列 B. 二叉树二叉树 C. 链表链表 D. 栈栈1.15、对整数序列、对整数序列 5， 4， 9， 3， 8， 2作从小到大排序，经排序算法一次处理后，该序列变成作从小到大排序，经排序算法一次处理后，该序列变成 2， 4， 9， 3， 8， 5则在以下四种供选择的排序方法中，能实现这个要求的排序方则在以下四种供选择的排序方法中，能实现这个要求的排序方法是法是 A. 插入排序插入排序 B. 快速排序快速排序 C. 选择排序选择排序 D. 归并排序归并排序1.16、在执行操作过程中，将路径上所遇到的结点都直接挂到在执行操作过程中，将路径上所遇到的结点都直接挂到根结点之下，称作路径压缩，该操作是根结点之下，称作路径压缩，该操作是 A. Union B. Find C. Insert D. Delete1.17、迭代算法求方程的根时，为了防止方程、迭代算法求方程的根时，为了防止方程无解，宜采用的措施是无解，宜采用的措施是 A. 在程序中增加对迭代次数给予检测和限制在程序中增加对迭代次数给予检测和限制的代码的代码 B. 自动选择新的初始根自动选择新的初始根C. 选择速度更快的计算机选择速度更快的计算机 D. 降低方程根的精度要求降低方程根的精度要求1.18、把大问题分解成一些较小的问题，然后，、把大问题分解成一些较小的问题，然后，由小问题的解答构造出大问题的解答，这类算由小问题的解答构造出大问题的解答，这类算法统称为法统称为 A. 试探法试探法 B. 迭代法迭代法 C. 贪婪法贪婪法 D. 分治法分治法1.19、对整数序列、对整数序列 10， 8， 20， 6， 18作从小到大排序，经排序算法一次处理后，该序列变作从小到大排序，经排序算法一次处理后，该序列变成成 8， 10， 20， 6， 18则在以下四种供选择的排序方法中，能实现这个要求则在以下四种供选择的排序方法中，能实现这个要求的排序方法是的排序方法是 A、快速排序、快速排序B、插入排序、插入排序C、选择排序、选择排序 D、归并排序、归并排序1.20、下列排序算法中，哪一个排序算法在每趟排序、下列排序算法中，哪一个排序算法在每趟排序后不一定能选出一个元素放到其排序好的序列的正确后不一定能选出一个元素放到其排序好的序列的正确位置上。位置上。A冒泡排序冒泡排序 B 堆排序堆排序 C 直接插入排序直接插入排序 D 选择排序选择排序1.21、在下列内排序方法中，平均比较次数最、在下列内排序方法中，平均比较次数最少的是少的是A.插入排序插入排序B.选择排序选择排序 C.冒泡排序冒泡排序D.快速排序快速排序1.22、在内排序方法中，从未排序序列中依次、在内排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将取出元素与已排序序列中的元素进行比较，将其放入已排序序列中的方法称为其放入已排序序列中的方法称为A.希尔排序希尔排序B.冒泡排序冒泡排序C.插入排序插入排序 D.选择排序选择排序1. 23、非空的、非空的m路路B树的根结点的子结点至少树的根结点的子结点至少有（设根结点不是叶子结点）有（设根结点不是叶子结点）A、1个个 B、2个个 C、 m/2 个个 D、 m/2 个个1.24、对整数序列、对整数序列26， 43， 38， 18， 19， 41，17，31作从小到大的排序，经排序算法一作从小到大的排序，经排序算法一趟处理后，序列变成趟处理后，序列变成41，31， 43，26，17，38，18，19。试问这是采用何种排序方法。试问这是采用何种排序方法A、堆排序、堆排序B、选择排序、选择排序C、shell排序排序D、基数排序、基数排序 1.25、一棵查找二叉树，其结点、一棵查找二叉树，其结点A、B、C、D、E、F。如果该查找二叉树的根结点为。如果该查找二叉树的根结点为D，则它的一种可能，则它的一种可能的前序遍历为的前序遍历为 A、DABCFEB、DAFCEBC、DAFCBED、DACEBF一棵二叉检索树，其结点一棵二叉检索树，其结点A，B，C，D，E，F。如果。如果该二叉检索树的根结点为该二叉检索树的根结点为C，则在以下供选择的，则在以下供选择的4个序个序列中，可能是它的层次遍历序列的是列中，可能是它的层次遍历序列的是 A、CABDFEB、CAFBEDC、CADEBFD、CAFDBE 1.26、把复杂问题分解出一系列子问题，为不重复求、把复杂问题分解出一系列子问题，为不重复求相同子问题，把新的子问题的解答暂存于一个数组中相同子问题，把新的子问题的解答暂存于一个数组中，待再次解同样子问题时，就从数组中取出该子问题，待再次解同样子问题时，就从数组中取出该子问题的解答。这类算法通称的解答。这类算法通称A、试探法、试探法B、迭代法、迭代法C、动态规划法、动态规划法D、贪婪法、贪婪法 1.27、如下程序段的时间复杂性为、如下程序段的时间复杂性为 for (p0 = 5, i = 1; i n; i+) pi = pi-1+4;for (s = 0, i = 0; i n; i+) s += pi; A、O(n+(n-1) B、O(2*n) C、O(n) D、O(n2)1.28、对图作遍历的算法引入数组、对图作遍历的算法引入数组visited，其作用是，其作用是A、提高算法的速度、提高算法的速度B、顺序存储被访问的顶点号、顺序存储被访问的顶点号C、广度优先的遍历算法，该数组可以不要、广度优先的遍历算法，该数组可以不要D、对被访问过的顶点置标记，避免被重复访问、对被访问过的顶点置标记，避免被重复访问 1.29、在、在Kruskal算法求网络的最小生成树中，采用的算法求网络的最小生成树中，采用的两种数据结构是两种数据结构是A、堆和集合、堆和集合B、堆和队列、堆和队列C、栈和集合、栈和集合D、堆和栈、堆和栈1.30、若一棵完全二叉树的第、若一棵完全二叉树的第3层有层有5个叶子结点（设个叶子结点（设根结点是第根结点是第0层），则这棵二叉树的最多结点个数是层），则这棵二叉树的最多结点个数是A、23B、16C、22D、21 1.31、BM算法，用模式算法，用模式“KBVUPBD”对正文作匹配，先要求各对正文作匹配，先要求各字符的字符的d函数值。其中，函数值。其中，dA、dD和和dB的值依次是的值依次是 A、7， 6，1B、7， 7，1 C、7， 7，2D、6， 6，2 现有模式现有模式“ZQVUPQY”，其中，其中，dX、dY和和dP的值依次是的值依次是 A、7， 7，2B、0， 7，1 C、7， 7，1D、6， 6，21.32、若将元素、若将元素A，B，C，D，E依次进入栈依次进入栈S，如果从栈，如果从栈S出栈出栈的第一个元素是的第一个元素是E，则下一个出栈的元素是，则下一个出栈的元素是 A、CB、DC、BD、不能确定、不能确定 1.33、若对整数序列、若对整数序列1、2、3、4、5、6、7、8，采用二分法检，采用二分法检索索6，则从开始比较到最后找到，算法比较的整数依次是，则从开始比较到最后找到，算法比较的整数依次是A 、3、5、6 B、5、6C、3、5、7、6 D、4、6 二、简答题二、简答题2.1、对关键字序列、对关键字序列（55、57、35、56、31、27、68、22）进行快速排序，并设在快速排序过程中作分划进行快速排序，并设在快速排序过程中作分划的基准数为分划序列的第一个数。这样，进行的基准数为分划序列的第一个数。这样，进行一次分划后，得到的关键字序列为一次分划后，得到的关键字序列为22 ，27 ，35 ，31 ，55 ，56 ，68 ，572.2、在插入排序、选择排序、归并排序和基数、在插入排序、选择排序、归并排序和基数排序这四种排序方法中，最好和最坏情况下的排序这四种排序方法中，最好和最坏情况下的时间复杂度均为时间复杂度均为O(n lb n)，且稳定的排序方法，且稳定的排序方法是是归并排序归并排序2.3、用代码、用代码writeN1(12345)调用以下递归函调用以下递归函数，递归函数的输出结果是数，递归函数的输出结果是 void writeN1(int n) if(n10) printf(“%d”, n); else writeN1(n/10); printf(“%d”, n%10); 123452.4、用代码、用代码writeN2(12345)调用以下递归函数，调用以下递归函数，递归函数的输出结果是递归函数的输出结果是 void writeN2(int n) if(n= 0 & pj = tk) j-; k-; if (j 0) return t + i - m + 1; i = i+dti; while (i B, A-C-B, A-C-D-BC 25 A-CD - ,30 -, A-C-DE 40, 35 A-E, A-C-D-E 3.8、对关键字序列（、对关键字序列（48、30、63、54、58、27、37）进行）进行SHELL排序，设第一次取间隔排序，设第一次取间隔g为为3，则，则进行第一趟处理之后得到的结果为进行第一趟处理之后得到的结果为3.9、设输入记录的关键码依次为、设输入记录的关键码依次为:8，14，3，7，16，5，6，构造一棵，构造一棵3阶阶B树。试画出按所给出的树。试画出按所给出的关键码顺序输入记录，从空的关键码顺序输入记录，从空的B树开始，构造一棵树开始，构造一棵3阶阶B树的构造过程。树的构造过程。3.10、某系统在通信联系中将出现、某系统在通信联系中将出现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.11、下图是一棵、下图是一棵4阶阶B+树树，叶子结点的，叶子结点的m1 = 5,画出对该树加入关键码画出对该树加入关键码28后的后的B+树。树。3.12、下图是一棵、下图是一棵4阶阶B+树树，叶子结点的，叶子结点的m1 = 5,画画出对该树删除关键码出对该树删除关键码33以后的以后的B+树。树。3.13、Floyd算法是从图的邻接矩阵（记为算法是从图的邻接矩阵（记为A(-1)）出发，递）出发，递推地产生矩阵序列推地产生矩阵序列A(0)，A(n-1)，求得各顶点之间的最，求得各顶点之间的最短路径。试对右图，按短路径。试对右图，按Floyd算法，求出算法，求出A(0)。A(-1) A(0)0 50 27 - 24 0 50 27 - 24 - 0 - - 35 - 0 - - 35 - 37 0 25 - - 37 0 25 - 23 - - 0 - 23 73 50 0 47 - - - 30 0 - - - 30 0 四完成算法题四完成算法题4.1、这里给出的是一个实现插入排序算法的函数，在该函、这里给出的是一个实现插入排序算法的函数，在该函数中，寻找插入位置时，利用被插入的元素段的有序性用二数中，寻找插入位置时，利用被插入的元素段的有序性用二分法寻找插入位置，然后插入处之后的有序段元素后移一个分法寻找插入位置，然后插入处之后的有序段元素后移一个位置，得到一个空位将新的值插入到有序段中。位置，得到一个空位将新的值插入到有序段中。 void insertSort(int e, int n) int i, j, left, right, m; int temp; for(i = 1; i n; i+) temp = ei; left = 0 ; right = _(1)_ ; /* 设定初始查找区间设定初始查找区间 */ while(left em) _(2)_; else _(3)_; for(j = i-1; _(4)_; j-) /* 插入处之后的元素后移插入处之后的元素后移 */ _(5)_; _(6)_ = temp; i-1left = m+1right = m-1j = leftej+1 = ejeleft 4.2、利用栈实现的二叉树非递归中序遍历函数。、利用栈实现的二叉树非递归中序遍历函数。#define MAX 100 typedef struct node int data; struct node *lChild, *rChild; Bnode; typedef struct snode Bnode *elemMAX; int top;STACK; void InOrderTraverse (Bnode *bT ) STACK s; Bnode * p; s.top = 0; p = bT; /*初始化初始化*/ do while (p != NULL) /* 当前结点指针进栈和向左子树前进，当前结点指针进栈和向左子树前进， /*/ s.elems.top+ = p; p = p-lChild; if ( s.top 0 ) /*栈非空栈非空*/ p = s.elem-s.top ; /* 退栈退栈*/ printf (“%d “, p-data); /* 访问根结点访问根结点*/ p = p-rChild; /* 向右链走向右链走 */ while ( p | s.top 0); 4.3、设用有序链表表示集合，以下是完成新元素加入到集合的函数。、设用有序链表表示集合，以下是完成新元素加入到集合的函数。/* a加入到集合，若集合已有此元素，函数返回加入到集合，若集合已有此元素，函数返回0，否则函数返回，否则函数返回1*/typedef struct node int ele; struct node *next;EleNode;typedef struct EleNode *head; /集合链表的首指针集合链表的首指针DISJSETS;int insertEle(int a, DISJSETS *S) EleNode *p=S-head-next, *q=S-head, *s; while(p != NULL & _(1)_ ) / p-ele ele next; if(p != NULL & _(2)_)/ p-ele = ap-ele = a return 0; s = (EleNode *)malloc(sizeof(EleNode); s-ele = a; s-next = _(3)_; / p p _(4)_; / /q-next = sq-next = s return 1;4.4 、设用有序链表表示集合，以下是从有序链表表示的集合中删除元素、设用有序链表表示集合，以下是从有序链表表示的集合中删除元素的函数。的函数。*从集合删除从集合删除a。集合不空，元素。集合不空，元素a在集合中，函数删除在集合中，函数删除a后返回后返回1，否则返回，否则返回0*/typedef struct node int ele; struct node *next;EleNode;typedef struct EleNode *head; /集合链表的首指针集合链表的首指针DISJSETS;int deleteEle(int a, DISJSETS *S) EleNode *p = S- head -next, *q = S- head; while(p != NULL & _(1)_) / p-ele ele next; if(_(2)_ & _(3)_) / ( (2)p != NULL 2)p != NULL (3) (3) p-ele = ap-ele = a q-next = _(4)_; / p-nextp-next free(p); return 1; return 0;4.5、设堆的数据类型、设堆的数据类型BinaryHeap定义如下：定义如下：typedef int Comparable;#define MAXHEAP 100 /堆最多元素堆最多元素typedef struct int currentSize; Comparable eMAXHEAP; / 这里可以加入堆的其它信息这里可以加入堆的其它信息BinaryHeap;元素元素X插入到堆中插入到堆中，可先把，可先把X放入堆的下一个有效位置，如果放入堆的下一个有效位置，如果X放入后不违背堆的有序性，则插入操作就结束。否则，将它的放入后不违背堆的有序性，则插入操作就结束。否则，将它的父结点渗透到该结点位置，而将父结点渗透到该结点位置，而将X上冒到父结点位置。如果这样上冒到父结点位置。如果这样的渗透和上移以后，还是不能满足堆的有序性，则的渗透和上移以后，还是不能满足堆的有序性，则X的新的父结的新的父结点继续向下渗透，点继续向下渗透，X继续向根结点方向上移。如此调整，直至满继续向根结点方向上移。如此调整，直至满足堆的有序性。足堆的有序性。堆上插入新结点的算法如下：堆上插入新结点的算法如下：int biHeapInsert(inaryHeap*heap,Comparable x) int hole = heap-currentSize, father; if(heap-currentSize = MAXHEAP) return 0;/因堆已满，不能再插入因堆已满，不能再插入 for(; hole 0 & xefather =_(1)_; _(2)_) heap-ehole = _(3)_; / 父结点向下渗透，插入位置上移父结点向下渗透，插入位置上移 heap-e_(4)_ = x; _(5)_； return 1; (hole-1)/2(hole-1)/2hole=fatherhole=fatherheap-efatherheap-efatherholeholeheap-currentSize+heap-currentSize+4.6、设堆的数据类型、设堆的数据类型BinaryHeap定义如下：定义如下：typedef int Comparable;#define MAXHEAP 100 /堆最多元素堆最多元素typedef struct int currentSize; Comparable eMAXHEAP; / 这里可以加入堆的其它信息这里可以加入堆的其它信息BinaryHeap;删除最小堆中最小结点删除最小堆中最小结点就是删除堆的根结点。删除根结点后，就是删除堆的根结点。删除根结点后，先将堆的最后元素先将堆的最后元素X移到根结点位置，接着将它的两个子结点移到根结点位置，接着将它的两个子结点中较小的结点上移到根结点位置，而将中较小的结点上移到根结点位置，而将X渗透到这个子结点位渗透到这个子结点位置。重复这个过程，直到置。重复这个过程，直到X放入的某个位置，能使这个变小后放入的某个位置，能使这个变小后的数据集重新变成堆为止。实际上，从根结点开始，沿着含较的数据集重新变成堆为止。实际上，从根结点开始，沿着含较小的子树根结点的路径向下，到达小的子树根结点的路径向下，到达X放入后能满足堆的有序性放入后能满足堆的有序性的正确位置。以下是堆上删除优先结点的算法：的正确位置。以下是堆上删除优先结点的算法：int binaryHeapDeleteMin(inaryHeap*heap, Comparable*xp) int hole, child; Comparable tmp; if(heap-currentSize = 0) return 0; /堆空堆空 *xp = _(1)_; tmp = heap-e-heap-currentSize; for(hole = 0; hole*2 currentSize; hole = child) child = _(2)_; /左子结点左子结点 if(child+1 currentSize & heap-echild+1 echild) child+; /右子结点更小右子结点更小 if(_(3)_ ehole =_(4)_;/上冒上冒 else break; heap-e_(5)_ = tmp; return 1; heap-e0 heap-e0 2 2* *hole + 1hole + 1heap-echild heap-echild heap-echildheap-echildholehole4.7、本题的函数、本题的函数intNode * inserteInt(intNode * h, int key)实现在从小到大有序整数链表中插入一个整数，使插入后的新链表依旧保实现在从小到大有序整数链表中插入一个整数，使插入后的新链表依旧保持有序。持有序。typedef struct node int data ; struct node *next ; /* 存放后继表元的指针存放后继表元的指针 */intNode;intNode * inserteInt(intNode * h, int key) intNode *u, *v, *p; u = NULL, v = h; for(; v != NULL &_（1）_; u = v, v= v-next); p = (intNode *)malloc(sizeof(intNode); p-data = key; p-next = _（2）_; if (_（3）_) h = p; /* 因插入在首表元之前，修改链表头指针因插入在首表元之前，修改链表头指针 */ else u-next = p; return h;（1 1）key v-data (2) v (3)u = NULL key v-data (2) v (3)u = NULL 4.8、函数函数unionSet ( DISJSETS *S1, DISJSETS *S2 ) 实现集合实现集合S1与与S2的并，结的并，结果在果在S1中中, 集合集合S1与与S2用具有辅助结点的有序用具有辅助结点的有序(从小到大从小到大)链表表示。类型为：链表表示。类型为：typedef struct node int ele ; struct node *next ; EleNode ; / 链表表元类型链表表元类型typedef structEleNode *head ; /集合链表的首指针集合链表的首指针 DISJSETS ; / 集合类型集合类型void unionSet ( DISJSETS *S1 , DISJSETS *S2 ) EleNode *p , *q , *t ; / t指向新的指向新的S1*p = S1 head next , *q = S2 head next , *t = S1 head ; while ( _(1)_ ) /p != NULL & q != NULLp != NULL & q != NULL if ( p ele = q ele ) / 两集合共有的元素两集合共有的元素,S1的当前结点接在新的的当前结点接在新的S1上上 t next = p ; p = p next ; q = q next ; else if ( p ele ele ) / S1的当前元素小，将它接在新的的当前元素小，将它接在新的S1上上 _(2)_ ; _(3)_ ; / t-next = p; p = p-next;t-next = p; p = p-next; else /S2的当前元素小，复制结点接在新的的当前元素小，复制结点接在新的S1上上 t next = ( EleNode * ) malloc ( sizeof ( EleNode ) ) ; t next ele = q ele ; q = q next ; t = t next; if ( p != NULL ) t next = p ; / S1未扫视完，链接在新的未扫视完，链接在新的S1上上 else /S2集合未扫视完，逐一复制到新的集合未扫视完，逐一复制到新的S1上上 while ( _(4)_ ) /q != NULLq != NULL t next = ( EleNode * ) malloc ( sizeof ( EleNode ) ) ; t next ele = q ele ; t = t next ; q = q next ; _(5)_ ; / 链表收尾链表收尾 t-next = NULLt-next = NULL 4.9、函数函数intersection ( DISJSETS *S1, DISJSETS *S2 ) 实现集合实现集合S1与与S2的的交，结果在交，结果在S1中中, 集合集合S1与与S2用具有辅助结点的有序用具有辅助结点的有序(从小到大从小到大)链表表示。类型链表表示。类型为：为：typedef struct node int ele ; struct node *next ; EleNode ; / 链表表元类型链表表元类型typedef structEleNode *head ; /集合链表的首指针集合链表的首指针 DISJSETS ; / 集合类型集合类型void intersection(DISJSETS *S1, DISJSETS *S2) EleNode *p , *q , *t ; / t指向新的指向新的S1*p = S1 head next , *q = S2 head next , *t = S1 head; while ( _(1 )_ ) /p != NULL & q != NULLp != NULL & q != NULL if ( p ele = q ele ) /两集合共有的元素，两集合共有的元素，S1的当前元素保留的当前元素保留 t = t next; p = p next ; q = q next ; else if ( p ele ele) / S1的当前元素小，删除该元素的当前元素小，删除该元素 t next = _(2 )_ ; / p-nextp-next free(p); p = t next ; else /S2的当前元素小的当前元素小 _(3 )_; / q = q-nextq = q-next while (_(4 )_ ) /S1集合未扫视完集合未扫视完 , 删除删除S1中元素中元素 t next = p next ; free ( p ); p = _(5 )_; / t-next t-next 4.10、函数函数maxCountNum(int a, int n)是在数组中寻找出现次数最多的元素。当有是在数组中寻找出现次数最多的元素。当有多个不同元素有相同的最多出现次数时，选择值更小的元素。多个不同元素有相同的最多出现次数时，选择值更小的元素。int maxCountNum(int a, int n) int i, j, ind, tempC, c; for(c = i = 0; i n; i+) for(tempC= 1, j = i+1; j c | tempC = c & _(2)_ ) /当当ai是更好的解时，保存是更好的解时，保存 _(3)_ ; ind = i; return aind;(1)tempC+(2) ai head next , *q = S2 head next , *t = S1 head; while ( _(1)_ ) /p != NULL & q != NULLp != NULL & q != NULL if ( p ele = q ele ) /两集合共有的元素，该元素从两集合共有的元素，该元素从S1中删除中删除 t next = _(2)_ ; / p-nextp-next free(p); p = p = _(3)_ ; ; / t-next t-next q = q-next; q = q-next; else if ( p ele ele q-ele S1的当前元素小，保留该元素的当前元素小，保留该元素 t = t next ; p = p next ; else _(5)_ / q = q-nextq = q-next S2的当前元素小，的当前元素小， S2继续向前继续向前 4 .11 、在冒泡排序过程中，若某次遍历在某个位置、在冒泡排序过程中，若某次遍历在某个位置j发生最后一次交换，发生最后一次交换，j以后的以后的位置都未发生交换，则实际上位置都未发生交换，则实际上j以后位置的全部元素都是已排好序的。利用这个性以后位置的全部元素都是已排好序的。利用这个性质，后一次遍历范围的下界可立即缩短至上一次遍历的最后交换处。以下是利用质，后一次遍历范围的下界可立即缩短至上一次遍历的最后交换处。以下是利用这个性质编写的冒泡排序算法。这个性质编写的冒泡排序算法。void bubbleSort(int e, int n) int i, j, k, low; int temp; low = 0;/* low用于记录本次遍历范围的下界用于记录本次遍历范围的下界 */ while( _(1)_ ) /* 扫视范围非空时循环扫视范围非空时循环 */ for(_(2)_ , j=n-1; _(3)_; j-) /*比较至比较至low */ if(ej-1ej)/* ej-1与与ej交换交换 */ temp = ej-1; ej-1 = ej; ej = temp; k = _(4)_; low =_(5)_; (1) low low(4) j(5) k4 .12、本题的函数本题的函数intNode * inserteInt(intNode * h, int key)实现在从小到大有序整数链表中插入一个整数，使插入后的新实现在从小到大有序整数链表中插入一个整数，使插入后的新链表依旧保持有序。链表依旧保持有序。typedef struct node int data ; struct node *next ; intNode;intNode * inserteInt(intNode * h, int key) intNode *u, *v, *p; u = NULL, v = h; for(; v != NULL &_（1）_; u = v, _（2）_); p = (intNode *)malloc(sizeof(intNode); p-data = key; p-next = _（3）_; if (_（4）_) h = p; /* 因插入在首表元之前，修改链表因插入在首表元之前，修改链表头指针头指针 */ else u-next = _（5）_; return h;(1) v-datakey(2) v = v-next(3) V(4) u=NULL(5) p4 .13、本题的函数、本题的函数intNode * inserteInt(intNode * h, int key)实现在从小到大有序整数链表中插入一个整数，使插入后的新链表依旧保持有序实现在从小到大有序整数链表中插入一个整数，使插入后的新链表依旧保持有序。typedef struct node int data ; struct node *next ; /* 存放后继表元的指针存放后继表元的指针 */intNode;intNode * inserteInt(intNode * h, int key) intNode *u, *v, *p; u = NULL, v = h; for(; v != NULL &_（1）_; u = v, _（2）_); p = (intNode *)malloc(sizeof(intNode); p-data = key; p-next = _（3）_; if (_（4）_) h = p; /* 因插入在首表元之前，修改链表头指针因插入在首表元之前，修改链表头指针 */ else u-next = _（5）_; return h;(1) v-data next(3) v(4) u= NULL(5) u-next = p4 .14、寻找一个最小整数，要求满足以下条件：寻找一个最小整数，要求满足以下条件： 被被5除余除余4，被，被7除余除余3，被，被9除余除余2。采用分阶段的办法，先让变量在保证满足条件被采用分阶段的办法，先让变量在保证满足条件被5除余除余4情况下，寻找被情况下，寻找被7除余除余3的解；接着在保证被的解；接着在保证被5除余除余4和被和被7除余除余3的条件下，寻找被的条件下，寻找被9除余除余2的解的解#include void main() int i =4; /* 初值初值i被被5除余除余4 */ do_(1)_; /* 使使i继续满足被继续满足被5除余除余4 ，寻找被，寻找被7除余除余3*/ while (i % 7 != 3); while (_(2)_ != 2) i = _(3)_; /* 使使i继续满足被继续满足被5除余除余4 ，被，被7除余除余3 */ printf(被被5除余除余4，被，被7除余除余3，被，被9除余除余2的最小的数是的最小的数是: %dn, i);(1) i = i+5(2) i%9(3) i+354 .15、设二叉树采用标准存储结构存储，即结点类型有三个成分：整型、设二叉树采用标准存储结构存储，即结点类型有三个成分：整型值域值域data、左子树指针、左子树指针lchild和右子树指针和右子树指针rchild。以下算法，已知二叉。以下算法，已知二叉树的根结点指针，求该二叉树最大值的结点指针的函数。树的根结点指针，求该二叉树最大值的结点指针的函数。typedef struct node int data; struct node *lChild, *rChild;BINNODE;BINNODE *maxInPree(BINNODE *t) BINNODE *maxPt, *lmaxPt, *rmaxPt; if(_(1)_) return NULL; lmaxPt = _(2)_;/求左子树的最大值结点指针求左子树的最大值结点指针 if(lmaxPt & lmaxPt-data t-data) /与根结点的比较，确定临时与根结点的比较，确定临时最大值结点指针最大值结点指针 maxPt = lmaxPt; else maxPt = t; rmaxPt = _(3)_;/求右子树的最大值结点指针求右子树的最大值结点指针 if(rmaxPt & rmaxPt-data maxPt-data) return _(4)_; return _(5)_;(1) t = NULL(2) maxInPree(t-lChild)(3) maxInPree(t-rChild)(4) rmaxPt(5) maxPt4 .16、试编写函数，将数组、试编写函数，将数组int An中的所有奇数移到所有偶数之前，要中的所有奇数移到所有偶数之前，要求时间复杂度为求时间复杂度为O(n)。解：设当前已发现的奇数个数存于变量解：设当前已发现的奇数个数存于变量odd中，它的初值为中，它的初值为0。顺序考察。顺序考察数组的元素，当发现是奇数时，将它与前面第一个偶数交换。数组的元素，当发现是奇数时，将它与前面第一个偶数交换。Void oddNumbefor(int x, int n) int k, odd = 0; for(k = 0; k _(1)_; k+) if(_(2)_) int t = xk; xk = xodd; xodd = t; _(3)_; (1) kn(2) xk%2 = 1(3) odd+偶数移到所有奇数偶数移到所有奇数4 .17、以下函数将数组以下函数将数组int xn中所有负数移到所有非负数之中所有负数移到所有非负数之前，要求算法的时间复杂度为前，要求算法的时间复杂度为O(n)。设当前已发现的负数个。设当前已发现的负数个数存于变量数存于变量neg中，它的初值为中，它的初值为0。顺序考察数组的元素，当。顺序考察数组的元素，当发现是负数时，将它与前面第一个非负数交换。发现是负数时，将它与前面第一个非负数交换。Void negNumbefor(int x, int n) int k, neg = 0; for(k = 0; k _(1)_; k+) if(_(2)_) int t = xk; xk = xneg; xneg = t; _(3)_; (1) kn(2) xk0(3) neg+