52. 二叉树中第5层上的结点个数最多为( C ) A.8 B.15 C.16 D.32
53. 下列编码中属前缀码的是( A )
A.{1,01,000,001} B.{1,01,011,010} C.{0,10,110,11} D.{0,1,00,11}
54. 如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用（ B ） A．深度优先搜索算法 B．广度优先搜索算法 C．求最小生成树的prim算法 D．拓扑排序算法
55. 对n个关键字的序列进行快速排序，平均情况下的空间复杂度为( B ) A.O(1) B.O(logn) C.O(n) D.O(n logn)
56. 对表长为n的顺序表进行顺序查找，在查找概率相等的情况下，查找成功的平均查找长度为( C )
A. (n-1)/2 B. n/2 C. (n+1)/2 D. n
57. 对于哈希函数H(key)=key,被称为同义词的关键字是( D ) A.35和41 B.23和39 C.15和44 D.25和51
58. 关于线性表的说法,下面选项正确的是（ B ）
A 线性表的特点是每个元素都有一个前驱和一个后继 B 线性表是具有n(n>=0)个元素的一个有限序列 C 线性表就是顺序存储的表
D 线性表只能用顺序存储结构实现
59. 表长为n的顺序存储的线性表，当在任何一个位置上插入或者删除一个元素的概率相等时，删除一个元素需要移动元素的平均个数为（ A ） A (n-1)/2 B n/2 C n D n-1
60. 设双向循环链表中节点的结构为(data,LLink,RLink)，且不带头节点。若想在指针p所指节点之后插入指针s所指节点，则应执行下列哪一个操作？（ D ） A p->RLink=s; s->LLink=p;
p->RLink->LLink=s; s->RLink=p->RLink; B p->RLink=s; p->RLink->LLink=s;
s->LLink=p; s->RLink=p->RLink; C s->LLink=p; s->RLink=p->RLink;
p->RLink=s; p->RLink->LLink=s; D s->LLink=p; s->RLink=p->RLink;
p->RLink->LLink=s; p->RLink=s;
61. 栈和队列都是（ A ） A 限制存取位置的线性结构 B 链式存储的非线性结构 C 顺序存储的线性结构
D 限制存取位置的非线性结构
62. 单循环链表表示的队列长度为n，若只设头指针，则入队的时间复杂度为（ A ） A O(n) B O(1) C O(n*n) D O(n*logn)
63. 一棵含有n个节点的k叉树，可能达到的最小深度为多少？（ C ） A n-k B n-k+1 C |logkn|+1 D |logkn| 其中|k|表示下取整
64. 下列序列中( 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
65. 在下列内排序方法中，( C )的平均时间复杂性是O(nlogn)。
A. 直接插入排序 B. 简单选择排序 C. 快速排序 D. 希尔排序
66. 设顺序栈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;
67. 已知L是带头结点的单链表，p指向表中某结点，则要删除p结点的后继结点应执行操作( A )；要在p结点后插入s结点应执行操作( D )。
A. p?next:=p?next?next; B. p?next?next:= ?.next;
C. p?next:=s; s?next:=p?next; D. s?next:=p?next; p?next:=s;
68. 下述二叉树中,哪一种满足性质:从任一结点出发到根的路径上所经过的结点序列按其关键字有序（ D ）。
A．二叉排序树 B．哈夫曼树 C．AVL树 D．堆
69. 下面给出的四种排序法中( D )排序法是不稳定性排序法。
A. 插入 B. 冒泡 C. 二路归并 D. 快速排序
70. 若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ C ）。
A. 快速排序 B. 堆排序 C. 归并排序 D. 直接插入排序
二 填空题
1、在单链表L中，指针p所指结点有后继结点的条件是： p->next!=null
2、表达式23+((12*3-2)/4+34*5/7)+108/9的后缀表达式是： (请在表达式中用点(.)将数隔开) 23.12.3*2-4/34.5*7/++108.9/+
3、有一个100*90的稀疏矩阵，非0元素有9个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是 60
4、深度为9的完全二叉树至少具有的 个结点
256
5、已知二叉树后序为DGEBFCA，中序为DBGEACF，则前序一定是 ABDEGCF
6、先根遍历树林正好等同于按__ _遍历对应的二叉树. 先序
7、构造n个结点的强连通图，至少有_______条弧。 n
8、在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比较的元素下标依次为 6,9,11,12
9、在单链表指针为p的结点之后插入指针为s的结点的操作是： s->next=p->next;p->next=s;
10、有N个顶点的有向图，至少需要量_______条弧才能保证是连通的。 N-1
11、在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值12，需做的关键码比较次数为 4
13、下面是一个无向图的邻接矩阵，试将有关数据填入本题的空白处（顶点号由1开始） 0 1 0 1 1 1 0 1 0 0 0 1 0 1 0 1 0 1 0 1 1 0 0 1 0
该图的顶点数为 该图的边数为 顶点3的度为 。 5 6 2
14、后根遍历树林正好等同于按__(6) _遍历对应的二叉树。 中序
15、n个结点的完全有向图含有边的数目__(7) n*（n－l）
16、当问题的规模n趋向无穷大时，算法执行时间T(n)的数量级被称为算法的________。 时间复杂度
17、假设S和X分别表示进栈和出栈操作，由输入序列“ABC”得到输出序列“BCA”的操作序列为SSXSXX，则由“a*b+c/d”得到“ab*cd/+”的操作序列为___________。 SXSSXXSSXSSXXX
18、在一棵度为3的树中，度为2的结点个数是1，度为0的结点个数是6，则度为3的结
点个数是________。 （注：没有包含度为1的结点） 2
19、如图所示的有向无环图可以排出________种不同的拓扑序列。 12
20、利用筛选法将关键字序列(37，66，48，29，31，75)建成的大根堆为(____ ____)。
75, 66, 48, 29, 31, 37
21、对长度为20的有序表进行二分查找的判定树的高度为________。 5
22、n个顶点的连通无向图，其边的条数至少为________________________。 n-1
23、排序(sorting)有哪几种方法_______________，_____________，____________，_____________，____________。
直接插入排序，冒泡排序，快速排序，希尔排序，归并排序，基数排序，堆排序等 24、下面程序段的时间复杂度为______________。（用O估计） FOR i:=1 TO n DO FOR j:=i TO n DO s=s+j; O（n*n）
25、非线性结构包括______________和_________________。 树，图
26、在线性表的___________存储结构上进行插入或删除操作要移动元素。 顺序存储结构
27、用一维数组r[0. .m-1]表示顺序存储的循环队列，设队头和队尾指针分别是front 和rear，且队头指针所指的单元闲置，则队满的条件是______________________________，队空的条件是_____________________________。 Front=rear, rear+1=front
28、下面表达式树所对应的表达式的前缀表达式是_____________________________，后缀表达式是____________________________。
+*a-bc/de , abc-*de/+
29、在AOE-网中，设e(i)和l(i)分别表示活动ai的最早开始时间和最晚开始时间，则当且仅当_________________时，ai为关键活动。
e(i)==l(i)
30．对有向图进行拓扑排序，若拓扑排序不成功，则说明该图_________________。下面有向图的一个拓扑有序序列是______________________________。
存在回路，123456798
31、二叉排序树的特点是其 序列是有序的。 中序遍历
三 简答题
1、名词解释：（1）抽象数据类型；（2）算法的时间复杂性； （3）散列法(hashing)；（4）索引文件。 （1）抽象数据类型：（课本P7）是指一个数学模型以及定义在该模型上的一组操作。 （2）算法的时间复杂性；（课本P15）一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f（n），算法的时间量度记作T(n)=O(f(n))，它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称做算法的渐近时间复杂度，简称时间复杂度。 （3）散列法(hashing)：（课本P253） 散列法（Hashing）或哈希法是一种将字符组成的字符串转换为固定长度（一般是更短长度）的数值或索引值的方法。
根据设定的哈希函数和处理冲突的方法将一组关键字映像到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表便称为哈希表，这一映像过程称为哈希造表或散列。
（4）索引文件： （课本P311） 除了文件本身（称作数据区）之外，另建立一张指示逻辑记录和物理记录之间一一对应关系的表---索引表。这类包括文件数据区和索引表两大部分的文件称作索引文件。
索引表中的每一项称作索引项，一般索引项都是由主关键字和该关键字所在记录的物理 地址组成的。显然，索引表必须按主关键字有序，而主文件本身则可以按主关键字有序或无 序，前者称为索引顺序文件（Indexed Sequential File），后者称为索引非顺序文件（Indexed NonSequential File）。
2、堆与二元查找树的区别?
（课本P280）堆的定义如下： n个元素的序列{Kl，K2，…，Kn}当且仅当满足如下关系时，称之为堆：
(1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤??n/2??)