.
第3层有( a )个结点(根结点为第1层)。
A．2 B. 3 C. 4 D. 5 (A) ／ ( B) ／ \\
(C ) (E ) \\ / \\
(D) (F) (H)
\\ (G)
20 先序遍历(DLR)图示二叉树可得到( a )的序列。 (A) ／ ＼ (B) (C) ／ ＼ ＼ (H) (D) (G) ／ ＼ (E) (F) ＼ (I) a) A B H D E F I C G b) H B E D F I A C G c) H E I F D B G C A
21 在有n个结点的二叉树的二叉链表表示中，空指针数 ( b )。 a.不定 b.n+1 c.n d.n-1
2n - (n-1) 2n个指针域 有效指针域
22 若某二叉树有20个叶子结点，有20个结点仅有一个孩子，则该二叉树的总结点数是 ( c )。
A．40 B. 55 C. 59 D. 61 n=n0+n1+n2=20+20+19
23 已知某二叉树的先序遍历次序为abcdefg中序遍历次序为badcgfe， 则该二叉树的后序遍历次序为( c )。层次遍历次序为( a )。 a: abcdefg b: cdebgfa c: bdgfeca d: edcgfba 先序：a b cdefg 谁先访问谁是根 D L R 中序：b a dcgfe L D R
(a)
.
.
／ \\ (b) (c) ／ \\ (d) (e) / \\ (g) (f)
24 图示的三棵二叉树中( c)为最优二叉树。
A) B) C) c a 2 7 a b c d d b 7 5 2 4 4 5 a b c d 7 5 2 4 最优二叉树->哈夫曼树
25 已知某二叉树的后序遍历和中序遍历次序分别为DBFGECA和BDACFEG。 则其先序遍历次序为( b )，层次遍历次序为( a )。
a: abcdefg b: abdcefg c: abcdfeg d: abcdegf 后序：DB FGEC A谁后访问谁是根 L R D 中序：BD A CFEG L D R
(A) ／ \\ (B) (C) \\ \\ (D) (E) / \\ (F) (G)
26 已知某树的先根遍历次序为abcdefg后根遍历次序为cdebgfa。 若将该树转换为二叉树,其后序遍历次序为( d )。
a: abcdefg b: cdebgfa c: cdegbfa d: edcgfba 先根：a bcdefg 后根：cdebgf a
(a) ／ \\ (b) (f) / | \\ \\ (c) (d) (e) (g)
.
.
27 设x和y是二叉树中的任意两个结点，若在先根序列中x在y之前，而在后根序列中x 在y之后，则x和y的关系是( c )。
A. x是y的左兄弟 B. x是y的右兄弟 C. x是y的祖先(不一定是父子) D. x是y的子孙
28 用三叉链表作二叉树的存储结构，当二叉树中有n个结点时，有( d )个空指针。 A. n-1 B. n C. n+1 D. n+2 三叉链表：较二叉链表多一双亲指针域 二叉链表：
2n - (n-1) = n+1 2n个指针域 有效指针域
根节点双亲指针必为空，故n+1+1=n+2
29 对一棵完全二叉树进行层序编号。则编号为n的结点若存在右孩子,其位序是( d )。 编号为n的结点若存在双亲,其位置是( a )。
a: n/2 b: 2n c:2n-1 d:2n+1 e:n f: 2(n+1) 30 设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为m1、m2和m3，则与 森林F对应的二叉树根结点的右子树上的结点个数是( d )。
A. m1 B. m1+m2 C. m3 D. m2+m3
(A) (B) (C) / \\ / \\ / \\ m1 m2 m3
(A) / \\ (左) (右)
m-1 m2+m3
31 下列二叉树中，( a )可用于实现符号不等长高效编码。
a:最优二叉树 b:次优查找树 c:二叉平衡树 d:二叉排序树 哈夫曼树
32 邻接表存储结构下图的深度优先遍历算法类似于二叉树的( a )遍历。 A. 先根 B. 中根 C. 后根 D. 层次 33 设无向图G = (V,E)和G’= (V’,E’)，若G’是G的生成树，则下面不正确的说法是( b )。 A. G’是G的子图 B. G’是G的连通分量
C. G’是G的无环子图 D. G’是G的极小连通子图且V’= V 生成树：极小 连通分量：极大
34 任何一个连通图的最小生成树( b )。
A．只有一棵 B. 有一棵或多棵 C. 一定有多棵 D. 可能不存在
35 深度优先遍历图使用了数据结构(b )，而广度优先遍历图使用了数据结构( c )。 A)数组 B)栈 C)队列 D)线性表
.
.
DFS：栈（递归） BFS：队列（层次）
36 已知某有向图的邻接表存储结构如图所示。
0 E 2 1 ∧
1 D 0 3 4 ∧
2 C 4
3 B 1 2 0 ∧
4 A 2 ∧
根据存储结构依教材中的算法其深度优先遍历次序为( d )。
广度优先遍历此序为( c )。各强连通分量的顶点集为( h )。 a: abcde. b: edcba. c: ecdab. d: ecadb.
e: abc及ed f: bc及aed g: ab及ced h: ac及bed
37 下列查找方法中( a )适用于查找单链表。
A)顺序查找 B)折半查找 C)分块查找 D)hash查找
38 下列算法中(c )适用于求图的最小代价生成树。( b )能对图作广度优先遍历。 A)DFS算法 B)BFS算法 C)Prim算法 D)Dijkstra算法
39 关键路径是指在只有一个源点和一个汇点的有向无环网中源点至汇点( c )的路径。 a:弧的数目最多 b:弧的数目最少 c:权值之和最大 d:权值之和最小 40 哈希表的查找效率取决于( d )。
a: 哈希函数 b:处理冲突的方法。 c:哈希表的装填因子。 d:以上都是 ① 哈希函数是否均匀； ② 处理冲突的方法； ③ 哈希表的装填因子。
41 在Hash函数H(k)=k MOD m中，一般来说，m应取( c )。
A. 奇数 B. 偶数 C. 素数 D. 充分大的数 素数可以有效的减少Hash冲突
42 在顺序表查找中，为避免查找过程中每一步都检测整个表是否查找完毕， 可采用 a 方法。
A.设置监视哨 B.链表存贮 C.二分查找 D.快速查找 43 静态查找表和动态查找表的区别在于( b )。 A. 前者是顺序存储，而后者是链式存储
B. 前者只能进行查找操作，而后者可进行查找、插入和删除操作 C. 前者只能顺序查找，而后者只能折半查找
D. 前者可被排序，而后者不能被排序
动态查找表在查找过程中插入元素或者从查找表中删除元素
.