48. 链栈与顺序栈相比，比较明显的优点是( D )
A)插入操作更加方便 B)删除操作更加方便 C)不会出现下溢的情况 D)不会出现上溢的情况
49. 下面关于二分查找的叙述正确的是 ( D )
A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 C. 表必须有序，而且只能从小到大排列
B. 表必须有序且表中数据必须是整型，实型或字符型 D. 表必须有序，且表只能以顺序方式存储
50. 二叉查找树的查找效率与二叉树的( （1）)有关, 在 (（2）)时其查找效率最低 (1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置 (2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。
CC
51. 如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用（ B ）
A)深度优先搜索算法 B)广度优先搜索算法
C)求最小生成树的prim算法
D)拓扑排序算法
52. 既希望较快的查找又便于线性表动态变化的查找方法是 ( C ) A．顺序查找 B. 折半查找 C. 索引顺序查找 D. 哈希法查找
53. 对表长为n的顺序表进行顺序查找，在查找概率相等的情况下，查找成功的平均查找长度为( C )
A) (n-1)/2 B) n/2
C) (n+1)/2 D) n
54. 对于哈希函数H(key)=key,被称为同义词的关键字是( D )
A)35和41 B)23和39
C)15和44 D)25和51
55. 某内排序方法的稳定性是指( D)。
A．该排序算法不允许有相同的关键字记录 B．该排序算法允许有相同的关键字记录 C．平均时间为0（n log n）的排序方法 D．以上都不对
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) 2K+1-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) 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 r^.Lchild:=tempA^.Lchild ELSE r^.Rchild:=tempA^.Lchild 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);*/