|
|
大工16秋《数据结构》在线作业2
一、单选题：
1.若一棵二叉树的先序遍历序列为abdgcefh，中序遍历的序列为dgbaechf，则后序遍历的结果为( )。 (满分:5)
A. gdbehfca
B. bdgaechf
C. gdbecfha
D. gcefhabd
2.具有3个结点的二叉树可能有( )种不同的形态。 (满分:5)
A. 3
B. 4
C. 5
D. 6
3.若一棵二叉树的后序遍历序列为dabec，中序遍历序列为debac，则先序遍历序列为( )。 (满分:5)
A. cbeda
B. decab
C. deabc
D. cedba
4.( )方法可以判断出一个有向图中是否有环（回路）。 (满分:5)
A. 深度优先遍历
B. 拓扑排序
C. 求最短路径
D. 求关键路径
5.深度为k的完全二叉树，其叶子结点必在第( )层上。 (满分:5)
A. k-1
B. 1
C. k
D. k-1或k
6.Huffman树的带权路径长度WPL等于( )。 (满分:5)
A. 除根结点之外的所有结点权值之和
B. 所有结点权值之和
C. 根结点的值
D. 各叶子结点的带权路径长度之和
7.具有N个结点的完全二叉树的深度是( )。 (满分:5)
A. log2N
B. log2N +1
C. log2(2N)
D. log2N -1
8.设有8个结点的无向图，该图至少应有( )条边才能确保是一个连通图。 (满分:5)
A. 5
B. 6
C. 7
D. 8
9.任何一棵二叉树的叶结点在先序、中序、后序遍历序列中的相对次序( )。 (满分:5)
A. 发生改变
B. 不发生改变
C. 不能确定
D. 以上都不对
10.一棵完全二叉树上有1001个结点，其中叶子结点的个数是( )。 (满分:5)
A. 250
B. 254
C. 501
D. 505
三、判断题：
1.在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。 (满分:5)
A. 错误
B. 正确
2.中缀表达式A+(B-C/D)*E的后缀形式是ABCD/-E*+。 (满分:5)
A. 错误
B. 正确
3.度为2的有序树是二叉树。 (满分:5)
A. 错误
B. 正确
4.若已知一棵二叉树的前序遍历序列和后序遍历序列，可以恢复该二叉树。 (满分:5)
A. 错误
B. 正确
5.出栈操作的时间复杂度为O(n)。 (满分:5)
A. 错误
B. 正确
6.设树根为第1层，在一棵二叉树上第6层的结点数最多为32。 (满分:5)
A. 错误
B. 正确
7.在用顺序表表示的循环队列中，可用标志位来区分队空或队满的条件。 (满分:5)
A. 错误
B. 正确
8.哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。 (满分:5)
A. 错误
B. 正确
9.二叉树的左右子树次序是严格的，不能够任意改变。 (满分:5)
A. 错误
B. 正确
10.具有m个结点的二叉排序树有多种，其中树高最小的二叉排序树是最佳的。 (满分:5)
A. 错误
B. 正确
|
|
