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

《[其它课程]算法复习题新.ppt》由会员分享，可在线阅读，更多相关《[其它课程]算法复习题新.ppt（75页珍藏版）》请在三一办公上搜索。

1、算法基础复习题,试题结构,一、单项选择题二、简答题三、算法应用题四、完成算法题,试题集,一、单项选择题,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、在回溯法中，为了确保算法能够终止，调

2、整时，要确保 A.所有可能的候选解都应被检验 B.只有哪些最终成为解的候选解才被检验C.可能的候选解能被重复检验 D.曾被放弃的候选解不会被再次检验1.5、索引表中每个索引项对应数据表中一个记录的索引结构是 A.稀疏索引 B.动态索引 C.稠密索引 D.线性索引,1.6、购物找零钱时，为使找出的零钱硬币数最少，售货员从最大面值的币种开始，按递减的顺序考虑各种硬币，先尽量用大面值的硬币，当不够大面值硬币的金额时才去考虑下一种较小面值的硬币。售货员采用的算法是 A.贪婪法 B.递推法 C.试探法 D.动态规划法1.7、m路搜索树的高度为h，有最多结点数的搜索树是除叶结点之外，每个结点都有m个子树，

3、高度为h的一棵m路搜索树中，最多关键码数为 A.mh+1-1 B.mh-1+1 C.mh+1 D.mh-1,1.8、若希望尽可能快地对整数数组进行稳定的排序，则在以下四种供选择的排序方法中，能实现这个要求的排序方法是 A.插入排序 B.快速排序 C.堆排序D.选择排序,1.9、迭代算法求方程的根时，如方程有解，但迭代算法还是找不到解，在下列供选择的原因中，是可能原因之一的是 A在程序中没有对迭代次数给予检测 B.近似根的初始值选择不合理C.计算机速度不够快 D.方程根的精度要求太低。1.10、对可能是解的许许多多候选解，按某一种顺序进行逐一枚举和检验，从中找出那些符合要求的候选解作为问题的解。

4、这类算法统称为 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、通常，在支持递归算法

5、执行的环境中，采用的数据结构是 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.Delete,1.17、迭代算法求方程的根时，为了防止方程无解，宜采用的措施是 A.在程序中增加对迭代次数给予检测和限制的代码 B.自动选择新的初始根C

6、.选择速度更快的计算机 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、在下列内

7、排序方法中，平均比较次数最少的是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、基数排序

8、,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、如下

9、程序段的时间复杂性为 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、

10、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

11、、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 wri

12、teN1(n/10);printf(“%d”,n%10);12345,2.4、用代码writeN2(12345)调用以下递归函数，递归函数的输出结果是 void writeN2(int n)if(n10)printf(“%d”,n);else printf(“%d”,n%10);writeN2(n/10);54321,2.5、对关键字序列：47、20、52、11、59、15、18、50、54、15进行快速排序，并设在快速排序过程中一次分划按以下步骤进行：1、确定基准数，分划序列的第一个数、中间数和末位置数，这三个数中的中间大小的哪一个数作为分划的基准数，并在确定基准数的同时，将这3个数中的最小

13、的数放于数列的最前端，最大的数放在数列的最后端，中间数暂留在中间。2、将基准数与数列最后第二个位置的数交换。3、对包括从第2个数至最后第3个数的部分数列作分划，让小于基准数的数移至前端，而大于基准数的数移到后端。4、将数列最后第2个数（基准数）与分划结束处的数交换。这样，进行一次分划后，得到的关键字序列为。15，20，18，11，15，47，52，50，54，59,2.6、写出使用归并排序法对下列数据进行从小到大排序的中间过程和最后结果。83，40，63，13，84，35，96，57，39，79，61，1540，83，13，63，35，84，57，96，39，79，15，61 13，40，63

14、，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.7、对目标串yxyxzyxyxac模式串yxyxa进行匹配，先求出模式串各字符的失效函数，然后描述KMP算法进行匹配的过程。各字符的失效函数值：-1,0,0,1,2。yxyxzyxyxacyxyxa,char*kmpMatch(char*t,char*p)int i,j;faillink(p,next);i=j=0;while(ti!=0)if(pj=ti)j+;i+;if(

15、pj=0)return t+i-j;else if(j=0)i+;else j=nextj;return NULL;,首先，从目标位置0和模式位置0开始比较，至yxyxz和yxyxa，不等时目标位置为4，模式位置也为4。因4位置失效函数的值（next 4）为2，从目标位置4和模式位置2开始新一轮比较。再次不等，因2位置失效函数的值（next 2）为0，从目标位置4和模式位置0开始新一轮比较。再次不等，这时因模式位置为0，让目标位置增1，目标位置5和模式位置0开始新一轮比较，直到模式位置比较至4，模式位置增1后，模式串结束，匹配成功。,2.8、采用BM算法，对目标串yxyxzyxyxac模式串y

16、xyxa进行匹配，先求出da、dx、dy、dz的值，然后描述BM算法进行匹配的过程。,char*bmMatch(char*t,char*p)int k,j,i,m=strlen(p),n=strlen(t),d256;calculateD(d,p,m);i=m-1;do j=m-1;k=i;while(j=0,da=5、dx=1、dy=2、dz=5,首先，从目标位置4和模式位置4开始比较，z和a不等，dz=5，i+dt4，目标位置改为9，从目标位置9和模式位置4开始新一轮比较，直到模式位置小于0，匹配成功。,2.9、用树表示离散集合0、1、2、3、4、5，并用数组存储，又设初始时，每个元素均独

17、立是一个集合，给出连续执行并操作union(3,2);union(3,5);union(1,3)后，数组各元素的值。约定，union(s1,s2)是s2所在集合合并至s1所在集合。,2.10、已知关键字序列（58、32、40、27、18、28、25、19、26）是一个最大堆，从堆删除最大元，并使删除最大元后的序列重新调整成最大堆，给出调整后的最大堆的序列。,40、32、28、27、18、26、25、19,2.11、已知关键字序列（50、37、31、32、26、20、28、29）是一个最大堆，向堆插入关键字39，并使插入后的序列重新调整成最大堆，给出调整后的最大堆的序列。,50、39、31、37

18、、26、20、28、29、32,2.12、对关键字序列（215、328、457、123、149、265）进行基数排序，需作多遍计数排序处理。分别给出第一遍和第二遍处理之后得到的关键字序列。2.13、以下是一棵3阶B树，对这棵B树删除关键码85，试画出删除后的B树。,删除后,2.14、对于给定的一组关键字序列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,2

19、6,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,45,选择排序,插入排序等,2.15、设散列表长度为11，散列函数h(x)=x%7，用开地址法，并用二次探查法解决冲突。依次插入关键字序列（24、12、17、13、6、20、16），给出这些关键字插入后所构造的散列表。,二次探查法,线性探查法,2.16、某图的邻接矩阵如下，依据该邻接矩阵，求从顶点A出发的广度优先遍历顶点序列。,ABFCDE,三.算法

20、理解题,3.1、输入一组记录构造一棵二叉检索 树，设输入记录的关键字依次为10，18，3，9，7，6，8，25，2，8，20试画出按所给出的顺序输入记录，所构造的一棵二叉检索树。,3.2、对下图所示二叉检索 树，画出执 行删除关键字78结点后的二叉检索 树。,删除后的二叉检索树,3.3、输入一组记录构造一棵AVL树，设输入记录的关键字依次为50，30，20，40，55，46，42，48，45试画出按所给出的顺序输入记录，所构造的一棵AVL树。,3.4、对于下列图，分别写出按深度优先搜索（从顶点A出发）和按广度优先搜索（从顶点F出发）的顶点访问序列。设顶点按字母顺序编号，要求按该图的邻接矩阵进行

21、遍历。,3.5、对于下列2图,分别采用Kruskal算法构造最小生成树，画出构造各步骤的全过程。,(1),(2),3.6、采用Prim算法构造下图的最小生成树，画出构造各步骤全过程(以A为起始顶点)。A 27 F 20 32 25 D 28 B E 26 35 24 C,3.7、试按Dijkstra算法，给出下列3图从顶点（A）出发到其它各顶点最短路经的求解过程。Dist PathB 70,50,45 A-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排

22、序，设第一次取间隔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:00,3.11、下图是一棵4阶B+树，叶子结点的m1=5,画出对该树加入关键码28后的B+树。,3.12、下图

23、是一棵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、这里给出的是一个实现插入排序算法的函数，在该函数中，寻找插入位置时，利用被插入的元素段的有序性用二分法寻找插入位置，然后插入处之后的有序段元素后移一个位

24、置，得到一个空位将新的值插入到有序段中。void insertSort(int e,int n)int i,j,left,right,m;int temp;for(i=1;i 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;t

25、ypedef 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、设用有序链表表示集合，以下

26、是完成新元素加入到集合的函数。/*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,4.4、设用有序链表表示集合，以下是从有序链表表示的集合中删除元素的函数。*从集合删除a。集合不空，元素a在集合中，函数删除a后返回1，否则返回0

27、*/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,4.5、设堆的数据类型BinaryHeap定义如下：typedef int Comparable;#define MAXHEAP 100/堆最多元素typedef struct int currentSize;Comparable eMAXHE

28、AP;/这里可以加入堆的其它信息BinaryHeap;元素X插入到堆中，可先把X放入堆的下一个有效位置，如果X放入后不违背堆的有序性，则插入操作就结束。否则，将它的父结点渗透到该结点位置，而将X上冒到父结点位置。如果这样的渗透和上移以后，还是不能满足堆的有序性，则X的新的父结点继续向下渗透，X继续向根结点方向上移。如此调整，直至满足堆的有序性。,堆上插入新结点的算法如下：int biHeapInsert(inaryHeap*heap,Comparable x)int hole=heap-currentSize,father;if(heap-currentSize=MAXHEAP)return

29、0;/因堆已满，不能再插入 for(;hole 0,(hole-1)/2hole=fatherheap-efatherholeheap-currentSize+,4.6、设堆的数据类型BinaryHeap定义如下：typedef int Comparable;#define MAXHEAP 100/堆最多元素typedef struct int currentSize;Comparable eMAXHEAP;/这里可以加入堆的其它信息BinaryHeap;删除最小堆中最小结点就是删除堆的根结点。删除根结点后，先将堆的最后元素X移到根结点位置，接着将它的两个子结点中较小的结点上移到根结点位置，而

30、将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;h

31、ole=child)child=_(2)_;/左子结点 if(child+1 currentSize,heap-e0 2*hole+1heap-echild heap-echildhole,4.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=N

32、ULL,v=h;for(;v!=NULL,（1）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,

33、*t;/t指向新的S1,*p=S1 head next,*q=S2 head next,*t=S1 head;while(_(1)_)/p!=NULL/链表收尾 t-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;/集合类型vo

34、id 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/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 c|tempC=c,(1)tempC+(2)ai ai

35、nd(3)c=tmpC,void difference(DISJSETS*S1,DISJSETS*S2)EleNode EleNode*p,*q,*t;/t指向新的S1*p=S1 head next,*q=S2 head next,*t=S1 head;while(_(1)_)/p!=NULL else _(5)_/q=q-next S2的当前元素小，S2继续向前,4.11、在冒泡排序过程中，若某次遍历在某个位置j发生最后一次交换，j以后的位置都未发生交换，则实际上j以后位置的全部元素都是已排好序的。利用这个性质，后一次遍历范围的下界可立即缩短至上一次遍历的最后交换处。以下是利用这个性质编写的

36、冒泡排序算法。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)k,4.12、本题的函数intNode*inserteInt(intNode*h,int key)实现在从小到大有序整数链表中插入一个整数，使

37、插入后的新链表依旧保持有序。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,v-datakeyv=v-nextVu=NULLp,4.13、本题的函数intNode*inserteInt(intNode*h,int key)实现在从小到大有序整数链表中插入一个整数，使插入后的新链表依旧保持有序。typedef struct node int data;struct node*next;

38、/*存放后继表元的指针*/intNode;intNode*inserteInt(intNode*h,int key)intNode*u,*v,*p;u=NULL,v=h;for(;v!=NULL,v-data nextvu=NULLu-next=p,4.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，寻找被

39、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);,i=i+5i%9i+35,4.15、设二叉树采用标准存储结构存储，即结点类型有三个成分：整型值域data、左子树指针lchild和右子树指针rchild。以下算法，已知二叉树的根结点指针，求该二叉树最大值的结点指针的函数。typedef struct node int data;struct node*lChild,*rChild;BINNODE;BINNODE*maxInPree(BINN

40、ODE*t)BINNODE*maxPt,*lmaxPt,*rmaxPt;if(_(1)_)return NULL;lmaxPt=_(2)_;/求左子树的最大值结点指针 if(lmaxPt,t=NULLmaxInPree(t-lChild)maxInPree(t-rChild)rmaxPtmaxPt,4.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)_;,knxk%2=1odd+,偶数移到所有奇数,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)_;,knxk0neg+,