习题:
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
发布评论