56. 下列内部排序算法中：
A．快速排序 B.直接插入排序 C. 二路归并排序 D. 简单选择排序 E. 起泡排序 F. 堆排序 （1） 其比较次数与序列初态无关的算法是（ ） （2）不稳定的排序算法是（ ）
（3）在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，k< （4）排序的平均时间复杂度为O(n?logn)的算法是（ ）为O(n?n)的算法是（ ） 1 DC 2 ADF 3 B 4 ACF BDE 57. 下列排序算法中(C )排序在一趟结束后不一定能选出一个元素放在其最终位置上。 A. 选择 B. 冒泡 C. 归并 D. 堆 58. 栈和队列都是（ A ） A)限制存取位置的线性结构 C)顺序存储的线性结构 B)链式存储的非线性结构 D)限制存取位置的非线性结构 59. 对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（ B ）。 A. (2,5,12,16)26(60,32,72) B. (5,16,2,12)28(60,32,72) C. (2,16,12,5)28(60,32,72) D. (5,16,2,12)28(32,60,72) 60. 一棵含有n个节点的k叉树，可能达到的最小深度为多少？（ C ） A) n-k B) n-k+1 C) |logkn|+1 D) |logkn| 其中|k|表示下取整 61. 下列序列中( B )不是堆。 A) 12 36 53 68 48 60 75 B) 12 48 53 68 36 60 75 C) 12 48 36 60 75 68 53 D) 12 36 60 53 48 68 75 62. 在下列内排序方法中，( C )的平均时间复杂性是O(nlogn)。 A) 直接插入排序 B) 简单选择排序 C) 快速排序 D) 希尔排序 63. 设顺序栈s非空，则语句段( C )可实现栈s的出栈操作，其中s.top为栈顶指针，s.elem为栈空间，出栈的元素存放在x中。 A) s.top:=s.top+1; B) x:=s.elem[s.top]; x:=s.elem[s.top]; s.top:=s.top+1; C) s.top:=s.top-1; D) x:=s.elem[s.top]; x:=s.elem[s.top]; s.top:=s.top-1; 64. 有一组数据（15，9，7，8，20，-1，7，4），用堆排序的筛选方法建立的初始堆为 （ C ） A．-1，4，8，9，20，7，15，7 B．-1，7，15，7，4，8，20，9 C．-1，4，7，8，20，15，7，9 D．A，B，C均不对。 65. 下述二叉树中,哪一种满足性质:从任一结点出发到根的路径上所经过的结点序列按其关键字有序（ D ）。 A)二叉排序树 B)哈夫曼树 C)AVL树 D)堆 66. 下面给出的四种排序法中( D )排序法是不稳定性排序法。 A) 插入 B) 冒泡 C) 二路归并 D) 快速排序 67. 算法的时间复杂度取决于（ A ） A．问题的规模 B. 待处理数据的初态 C. A和B D. 计算机cpu 68. 有关静态链表的叙述：(1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。(2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。(3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。以上错误的是（ B ） A．（1），（2） B．（1） C．（1），（2）,(3) D.（2） 69．一个栈的输入序列为123?n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ B ）。 A. 不确定 B. n-i+1 C. i D. n-i 70．下面关于串的的叙述中，哪一个是不正确的？（ B ） A．串是字符的有限序列 B．空串是由空格构成的串 C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储 71. 关于二叉树的叙述：①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。正确的是（ D ） A．①②③ B．②③④ C．②④ D．①④ 72．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是( A )。 A．逆拓扑有序 B．拓扑有序 C．无序的 73. 对n个关键字的序列进行快速排序，平均情况下的空间复杂度为( B ) A.O(1) B.O(logn) C.O(n) D.O(n logn) 二 填空题 1、在单链表L中，指针p所指结点有后继结点的条件是： p->next!=null 2、n（n大于1）个结点的各棵树中，其深度最小的那棵树的深度是_(1)__。它共有_(2)__个叶子结点和_(3)__个非叶子结点，其中深度最大的那棵树的深度是_(4)__，它共有_(5)__个叶子结点和_(6)__个非叶子结点。 (1)2 (2) n-1 (3) 1 (4) n (5) 1 (6) n-1 3、深度为9的完全二叉树最多有 个结点 256 4、二叉树由_(1)__，__(2)_，_(3)__三个基本单元组成。 .(1)根结点(2)左子树(3)右子树 5、先根遍历树林正好等同于按__ _遍历对应的二叉树. 先序 6、设只含根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数为______,最小结点数为______。 (1) 2-1 (2) k+1 7、在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比较的元素下标依次为 6,9,11,12 8、设y指向二叉线索树的一叶子，x指向一待插入结点，现x作为y的左孩子插入，树中标志域为ltag和rtag，并规定标志为1是线索，则下面的一段算法将x插入并修改相应的线索，试补充完整：(lchild,rchild分别代表左，右孩子) x^.ltag:= (1)___; x^.lchild:= (2)___; y^.ltag:= (3)___; y^.lchild:= (4)___; x^.rtag:= (5)___; x^.rchild:= (6)___; IF (x^.lchild<>NIL) AND (x^lchild^.rtag=1) THEN x^.lchild^.rchild:= (7)___; (1)1 (2)y^.lchild (3)0 (4)x (5)1 (6) y (7)x(本题按中序线索化) 9、有N个顶点的有向图，至少需要量_______条弧才能保证是连通的。 N-1 10、在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值11，需做的关 键码比较次数为 4 11、①二叉树用来表示表达式，因为需要保存各子树的值，修改二叉树的结点结构为(Lchild,Data,Val,Rchild)。其中Lchild,Rchild的意义同前，Val用来存放以该结点为根的子树的值，值的类型依具体情况而定。为了简便起见，算法假定所考虑的表达式只有+，-，*，/ 四种二目运算，且已表示成相应的二叉树。算法所计算的表达式值放在根结点的Val域中。 PROC Postorder-eval(t:ptrType) BEGIN IF (t!=NULL) K+1 BEGIN (1)_______; (2)_______; CASE t^.data: ‘+’: t^.Val:=t^. Lchild^. Val + t^. Rchild ^. Val; BREAK; ‘-’: t^.Val:=t^. Lchild^. Val - t^. Rchild ^. Val; BREAK; ‘*’: t^.Val:=t^. Lchild^. Val * t^. Rchild ^. Val; BREAK; ‘/’: t^.Val:=t^. Lchild^. Val / t^. Rchild ^. Val; BREAK; otherwise: (3)___; BREAK; ENDCASE END END; ②PROC Delete(x:datatype,A:tree) BEGIN tempA:= (4)___; WHILE (tempA^.Item!=x) AND (tempA!=NULL) DO IF (x ELSE BEGIN r:=tempA;tempA:=tempA^.Rchild;END;//tempA为要删结点，r为tempA的父亲 IF (6)___ return(x); IF (tempA^.Lchild!=NULL) AND (tempA^.rchild!=NULL) BEGIN t:=tempA; q:=tempA^.Rchild; WHILE (q^.Lchild!=NULL) DO BEGIN t:=q; q:=q^.Lchild; END; t^.Lchild:= (7)___; //删去q q^.Lchild :=tempA^.Lchild; q^.Rchild:=tempA^.Rchild; IF (tempA^.item< r^.item) r^.Lchild := (8)_ ELSE r^.Rchild:=q //用q代替 tempA END; ELSE IF(tempA^.Lchild!=NULL) IF(tempA^.item ELSE IF(tempA^.Rchild!=NULL) IF(tempA^.item ELSE r^.Lchild:=tempA^.Rchild ELSE //tempA为树叶 IF(10)_ r^.Lchild:=NULL ELSE r^.Rchild:=NULL END; 本题①是表达式求值，②是在二叉排序树中删除值为x的结点。首先查找x，若没有x，则结束。否则分成四种情况讨论：x结点有左右子树；只有左子树；只有右子树和本身是叶子。 (1)Postoder_eval(t^.Lchild) (2) Postorder_eval(t^.Rchild) (3)ERROR(无此运算符)(4)A (5)tempA^.Lchild (6)tempA=NULL (7)q^.Rchild (8)q (9)tempA^.Rchild (10)tempA^.Item 12、利用树的孩子兄弟表示法存储，可以将一棵树转换为______。 二叉树 13、n个结点的完全有向图含有边的数目__(7) n*（n－l） 14、当问题的规模n趋向无穷大时，算法执行时间T(n)的数量级被称为算法的________。 时间复杂度 15、假设S和X分别表示进栈和出栈操作，由输入序列“ABC”得到输出序列“BCA”的操作序列为SSXSXX，则由“a*b+c/d”得到“ab*cd/+”的操作序列为___________。 SXSSXXSSXSSXXX 16、在一棵度为3的树中，度为2的结点个数是1，度为0的结点个数是6，则度为3的结点个数是________。 2 17、设t是给定的一棵二叉树，下面的递归程序count(t)用于求得:二叉树t中具有非空的左,右两个儿子 的结点个数N2;只有非空左儿子的个数NL;只有非空右儿子的结点个数NR和叶子结点个数N0。N2、NL、NR、N0都是全局量，且在调用count(t)之前都置为0. typedef struct node {int data; struct node *lchild,*rchild;}node; int N2,NL,NR,N0; void count(node *t) {if (t->lchild!=NULL) if (1)___ N2++; else NL++; else if (2)___ NR++; else (3)__ ; if(t->lchild!=NULL)(4)____; if (t->rchild!=NULL) (5)____; } /*call form :if(t!=NULL) count(t);*/ (1)t->rchild!=null (2)t->rchild!=null (3)N0++ (4)count(t->lchild) (5)count(t->rchild) 18、利用筛选法将关键字序列(37，66，48，29，31，75)建成的大根堆为(____ ____)。 75, 66, 48, 29, 31, 37 19、对长度为20的有序表进行二分查找的判定树的高度为________。 5 20、阅读下列程序说明和程序，填充程序中的______ 【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示（编者略）。 本程序采用非递归的方法，设立一个堆栈stack存放还没有转换过的结点，它的栈顶指针为tp。交换左、右子树的算法为： （1）把根结点放入堆栈。 （2）当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。 （3）重复（2）直到堆栈为空时为止。 typedef struct node *tree; struct node{int data; tree lchild,rchild;} exchange(tree t) {tree r,p; tree stack [500]; int tp=0; (1)_______ while (tp>=0) {(2)_______ if((3)_______) {r=p->lchild; p->lchild=p->rchild; p->rchild=r stack[(4)_______]=p->lchild; stack[++tp]=p->rchild; } }} (1)stack[tp]=t (2) p=stack[tp--] (3)p (4)++tp 21、排序(sorting)有哪几种方法_______________，_____________，____________，_____________，____________。 直接插入排序，冒泡排序，快速排序，希尔排序，归并排序，基数排序，堆排序等 22、下面程序段的时间复杂度为______________。（用O估计） FOR i:=1 TO n DO FOR j:=i TO n DO s=s+j; O（n*n） 23、非线性结构包括______________和_________________。 树，图 24、判断带头结点的双向循环链表L是否对称相等的算法如下所示，请在划线处填上正确的语句