习题：
A．r- f B．r- f +1 C．（r- f ） MOD n+1 D．（r- f + n） MOD n
2．线性表若采用链表存贮结构，要求内存中可用存贮单元地址（D）．
A．必须连续 B．部分地址必须连续 C．一定不连续 D．连续不连续均可
3．下列叙述中，正确的是（ D ）．
A.线性表的线性存贮结构优于链表存贮结构 B.队列的操作方式是先进后出
C.栈的操作方式是先进先出
D．二维数组是指它的每个数据元素为一个线性表的线性表
4.在顺序表(2，5，7，10，14，15，18，23，35，41，52)中，用二分法查12，所需的关键码比较的次数为( C )
A.2 B.3 C.4 D.5
A.i B.n-1 C.n-i+1 D.不确定
6.如果一个栈初始时为空，且当前栈中的元素从栈底到栈顶依次为a,b,c（如图所示），另有元素d已经出栈，则可能的入栈顺序是（ D ）。
A. a d c b B. b a c d C. a c b d D. d a b c
7.( B )是一种先进先出的线性表
A. ABC B. CBA C. ACB D. BAC
9．元素R1、R2、R3、R4、R5入栈的顺序为R1、R2、R3、R4、R5。如果第1个出栈的是R3，那么第5个出栈的不可能是( B )。
A. R1 B.R2 C.R4 D.R5
10. 设栈S的初始状态为空，元素a, b, c, d, e 依次入栈，以下出栈序列不可能出现的有（C）。
A. a, b, c, e, d B. b, c, a, e, d C. a, e, c, b, d D. d, c, e, b, a
11．一个高度为h的二叉树最小元素数目是( B )。
A.2h+l B.h C.2h-1 D.2h E.2h-l
12．已知队列(13，2，11，34，41，77，5，7，18，26，15)，第一个进入队列的元素是13，则第五个出队列的元素是( B )。
A.5 B.41 C.77 D.13 E.18
13．无向图G有16条边，有3个4度顶点、4个3度顶点，其余顶点的度均小于3，则G至少有 个顶点。 答： 11
14.由3个a，1个b和2个c构成的所有字符串中，包含子串“abc”的共有（ D ）个
A.20 B.8 C.16 D.12 E.24
15. 设栈S的初始状态为空，元素a, b, c, d, e, f, g依次入栈，以下出栈序列不可能出现的是（ E ）。
A. a, b, c, e, d, f, g B. b, c, a, f, e, g, d C. a, e, d, c, b, f, g
D. d, c, f, e, b, a, g E. g, e, f, d, c, b, a
16.设栈S的初始状态为空，元素A,B,C,D,E,f依次入栈S，出栈的序列为B,D,f,E,C,A,则栈S的容量至少应该是（C）
A.6 B.5 C.4 D.3
17．某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为空，从这一时刻开始的出入记录为："进，出，进，进，进，出，出，进，进，进，出,出"。假设车辆入站的顺序为1，2，3，……，则车辆出站的顺序为（ C ）。
A. 1, 2, 3, 4, 5 B. 1, 2, 4, 5, 7 C. 1, 4, 3, 7, 6 D. 1, 4, 3, 7, 2
18.某车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时该车站站台为空，从这一时刻开始出入记录为：“进出进进出进进进出出进出”。假设车辆入站的顺序为1,2,3……，则车辆出站的顺序为（E）
A.1，2，3，4，5 B.1，2，4，5，7 C.1，3，5，4，6
D.1，3，5，6，7 E.1，3，6，5，7
19.地面上有标号为A.B.C的三根柱，在A柱上放有10个直径相同中间有孔的圆盘，从上到下依次编号为1，2，3……，将A柱上的部分盘子经过B柱移入C柱，也可以在B柱上暂存。如果B柱上的操作记录为“进、进、出、进、进、出、出、进、进、出、进、出、出”。那么，在C柱上，从下到上的编号为（ C ）。
A．2 4 3 6 5 7 B．2 4 1 2 5 7 C．2 4 3 1 7 6 D．2 4 3 6 7 5
20.有六个元素FEDCBA 从左至右依次顺序进栈，在进栈过程中会有元素被弹出栈。问下列哪一个不可能是合法的出栈序列？ D
A. EDCFAB B. DECABF C. CDFEBA D. BCDAEF
21.在下图，从端点（E ）出发存在一条路径可以遍历图中的每条边一次，而且仅遍历一次
A. 4 B.3 C.5 D. 2 E. 6
23. 二叉树T的宽度优先遍历序列为A B C D E F G H I，已知A是C的父结点，D 是G 的父结点，F 是I 的父结点，树中所有结点的最大深度为3（根结点深度设为0），可知F的父结点是（ C ）。
A. 无法确定 B. B C. C D. D E. E
排序题24．一棵二叉树的前序遍历序列是ABCDEFG，后序遍历序列是CBFEGDA，则根结点的左子树的结点个数可能是（ A ）。
A．2 B. 3 C. 4 D. 5
25．高度为n的均衡的二叉树是指：如果去掉叶结点及相应的树枝，它应该是高度为n-1的满二叉树。在这里，树高等于叶结点的最大深度，根结点的深度为0，如果某个均衡的二叉树共有2381个结点，则该树的树高为（ B ）。
A. 10 B. 11 C. 12 D. 13
26．如果根结点的深度记为1，则一棵恰有2011个叶结点的二叉树的深度最少是( C )。
A．10 B．11 C．12 D．13
27.完全二叉树的顺序存储方案，是指将完全二叉树的结点从上到下、从左到右依次存放到一个顺序结构的数组中。假定根结点存放在数组的1号位置上，则第k号结点的父结点如果存在的话，应当存放在数组中的（ C ）号位置。
A. 2k B. 2k+1 C. k/2下取整 D. (k+1)/2
28. 满二叉树的叶节点为N，则它的节点总数为（ C ）
A.N B.2N C.2N-1 D.2N+1 E.2^N-1
29. 完全二叉树共有2N-1个节点，则它的叶节点数为（B）
A. N-1 B.N C. 2*N D.2^N-1
30．二叉树T，已知其前序遍历序列为1 2 4 3 5 7 6，中序遍历序列为4 2 1 5 7 3 6，其后序遍历序列为( B )
A.4 2 5 7 6 3 1 B.4 2 7 5 6 3 1 C.4 2 7 5 3 6 1 D.4 7 2 3 5 6 1
E.4 5 2 6 3 7 1
31．已知7个节点的二叉树的先根遍历是1 2 4 5 6 3 7（数字为节点的编号，以下同），中根遍历是4 2 6 5 1 7 3，则该二叉树的后根遍历是（ A ）。
A．4 6 5 2 7 3 1 B．4 6 5 2 1 3 7 C．4 2 3 1 5 4 7 D．4 6 5 3 1 7 2
32. 已知6个结点的二叉树的先根遍历是1 2 3 4 5 6（数字为结点的编号，以下同），后根遍历是3 2 5 6 4 1，则该二叉树的可能的中根遍历是（ B ）
A. 3 2 1 4 6 5 B. 3 2 1 5 4 6 C. 2 1 3 5 4 6 D. 2 3 1 4 6 5
33.二叉树T，已知其先根遍历为1 2 4 3 5 7 6，中根遍历为2 4 1 5 7 3 6，后跟遍历是（ B ）
A. 4 2 5 7 6 3 1 B. 4 2 7 5 6 3 1 C.7 4 2 5 6 3 1 D. 4 2 7 6 5 3 1
34.设T是一棵有n个顶（定错）点的树，以下说法不正确的是（ A ）。
A.T有n条边 B.T是联通的 C.T是无环的 D.T有n-1条边。
35. 一个包含n个分支结点（非叶结点）的非空二叉树，它的叶结点数目最多为（D)
A. 2n + 1 B. 2n-1 C. n-1 D. n+1
36.如果树根算第1层，那么一颗n层的二叉树最多有（ A ）个结点。
A. 2n-1 B. 2n C. 2n+1 D. 2n+1
37. 平面上有五个点A(5, 3), B(3, 5), C(2, 1), D(3, 3), E(5, 1)。以这五点作为完全图G 的顶点，每两点之间的直线距离是图G 中对应边的权值。以下哪条边不是图G 的最小生成树中的边（ D ）。
A. AD B. BD C. CD D. DE E. EA
38．无向完全图是图中每对顶点之间都恰有一条边的简单图。己知无向完全图G有7个顶点，则它共有( B )条边。
A．7 B．21 C．42 D．49
发布评论