没有合适的资源?快使用搜索试试~ 我知道了~
1.B 【详解】程序每执行一次,x 就乘以 5,但是 x 又是小于 n 的,所以 5 的 a 次方小于等 2.D 【详解】该算法需要将 n 个元素依次插入到有序
资源详情
资源评论
资源推荐
参考答案
一、单项选择题:1~10 小题,每小题 2 分,共 20 分。
1.B 【详解】程序每执行一次,x 就乘以 5,但是 x 又是小于 n 的,所以 5 的 a 次方小于等
于 n,所以时间复杂度为 O(log
5
(n)), 满足条件是 B。
2.D 【详解】该算法需要将 n 个元素依次插入到有序单链表中,需要两重循环插入每个元
素,所以选 D。
3.C 【详解】根据树的性质,设分支数为 B,结点数为 n ,则 B=n-1,而 B=2*1+3*2+4*3=20,
n=21,所以选 C。
4.A 【详解】根据森林与二叉树的转换规则,二叉树的根是第一株树的根,而第一株树
的其他结点为左子树,所以左子树的结点数为 n1-1,选 A。
5.D【详解】哈夫曼树的构造原理,所有结点度数要么为0,要么为2,而 D 选项的编码
会出现度为 1 的结点,所以选D。
6.B 【详解】根据关键路径定义,所以选 B。
7.C 【详解】简单环路也是简单路径,只是起点和终点重复,所以长度不会超过 n,选 C。
8.C 【详解】看序列数据分布,发现 1 与 15 交换,4 与 7 交换,满足希尔排序思想,所
以选 C。
9.C【详解】比较次数与初态有关的是插入排序,快速排序,所以选 C。
10.D【详解】归并排序和气泡排序是稳定的,所以选 D。
二、填空题:11~15 小题,每小题 2 分,共 10 分。把符合题目要求的答案填写在下划线处。
11. +a*-bcd ; abc–d*+
【详解】中缀表达式转换成前缀表达式需要设置两个栈R、Q,R用于存储运算符,Q用
于存储转换后的表达式。对中缀表达式从右至左依次扫描,当遇到操作数时入栈Q,扫描到
操作符时,将操作符压入栈中,进栈的原则是保持栈顶操作符的优先级要高于栈中其他操作
符的优先级;否则,将栈顶操作符依次出栈并入栈Q,直到满足要求为止;遇到“)”进栈,
当遇到“(”时,退 R 栈入 Q 直到“)”为止。
中缀表达式转换成后缀表达式要对中缀表达式从左至右依次扫描,由于操作数的顺
序保持不变,当遇到操作数时直接输出,设立一个栈用以保存操作符,扫描到操作符时,将
操作符压入栈中,进栈的原则是保持栈顶操作符的优先级要高于栈中其他操作符的优先级;
否则,将栈顶操作符依次退栈并输出,直到满足要求为止;遇到“(”进栈,当遇到“)”时,
退栈输出直到“)”为止。
12. n(n-1) ; n
【详解】图强连通的定义是任意两点之间都有一条路径,最多时每个顶点发出 n-1 条边,n
个顶点共有 n(n-1)条边。最少时每个结点至少要一条出路(单节点除外),至少有 n 条边,正
好可以组成一个环。
13. 63 ; 20
【详解】最多时满二叉树,即 2
6
-1=63,最少时可以利用公式 N
h
=N
h-1
+N
h-2
+1 求得,其中 N
h
代表高度为 h 的 AVL 树最少结点树,N
h-1
代表AVL树的一棵子树,N
h-2
代表另一棵子树,
N
0
=0,N
1
=1,N
2
=2,可以计算出最少为 20。
14. 242 ; 31
【详解】根据 B-树定义,3 阶 B 树最多 3
5
-1=242,第 h 层最少包含结点数为 2
m
/ 2
h
-1,
所以高度为 5 最少关键字数
N
2
3
/ 2
5
-1
-1 =31
15. 4 ; 1
【详解】最多比较是树的高度 log
2
11,取整为 4 。最少比较 1 次。
三、简答题:16~17 小题,每小题 10 分,共 20 分。
伯特兰·罗卜
- 粉丝: 21
- 资源: 309
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0