2017年哈尔滨工业大学生命科学与技术学院854计算机基础考研导师圈点必考题汇编
● 摘要
一、选择题
1． 有关二叉树下列说法正确的是（ ）。
A_二叉树的度为2
B. —棵二叉树的度可以小于2
C. 二叉树中至少有一个结点的度为2
D. 二叉树中任何一个结点的度都为2
【答案】B
【解析】树的度=MAX（结点1的度，结点2的度，结点3的度，... ，结点n 的度）。二叉树之所以称为二叉树，是因为二叉树中节点的度最大是2，也可以小于2。
2． 下列命中组合情况中，一次访存过程中不可能发生的是（ ）。
A.TLB 未命中，Cache 未命中，Page 未命中
B.TLB 未命中，Cache 命中，Page 命中
C.TLB 命中，Cache 未命中，Page 命中
D.TLB 命中，Cache 命中，Page 未命中
【答案】D
【解析】TLB （快表）和慢表（页表，Page ）构成二级存储系统，若TLB 命中，则Page 必命中。因此不可能发生的是D 选项。
3． 程序P 在机器M 上的执行时间是20秒，编译优化后，P 执行的指令数减少到原来的CPI 増加到原来的1.2倍，则P 在M 上的执行时间是（ ）
A.8.4 秒
B.11.7 秒
C.14 秒
D.16.8 秒
【答案】D 【解析】
4． 组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为（ ）。
A.
B.
第 2 页，共 56 页 而
C.
D.
【答案】B
个组分别排序即可，基于比较的排序方法每组的时
【解析】因组与组之间已有序，故将间下界为
0全部时间下界为
5． 引入二叉线索树的目的是（ ）。
A. 加快查找结点的前驱或后继的速度
B. 为了能在二叉树中方便地进行插入与删除
C. 为了能方便地找到双亲
D. 使二叉树的遍历结果唯一
【答案】A
【解析】二叉线索树有指向前驱和后继的指针，因此加快了查找前驱和后继结点的速度。
6． 在有向图G 的拓扑序列中，若顶点V i 在顶点V j 之前，则下列情形不可能出现的是（ ） 。
A.G 中有弧
C.G 中没有弧 【答案】D 【解析】若想实现图的一个拓扑排序，需要满足的一个条件为：若顶点A 在序列中排在顶点B 的前面，则在图中不存在从顶点B 到顶点A 的路径。又因为若G 中有一条从V j 到V i 的路径，则在拓扑序列中V i 不可能在V j 前。 7． 为提高散列（Hash ）表的查找效率，可以采用的正确措施是（ ）。 I .增大装填（载）因子 II. 设计冲突（碰撞）少的散列函数 III. 处理冲突（碰撞）时避免产生聚集（堆积）现象 A. 仅I B. 仅 II C. 仅 I 、II D. 仅 II 、III 【答案】D 【解析】散列表的查找效率（比较次数）取决于：散列函数、处理冲突的方法和散列表的装填因子a 。CX 标 志着散列表的装满程度，通常情况下，（X 越小，发生冲突的可能性越小；反之，a 越大，表示已填入的记录越多， 再填入记录时，发生冲突的可能性越大。因此选项I 错误，越是增大装填因子，发生冲突的可能性就越大，查找 效率也越低。选项II 正确。选项III 正确。采用合适的处理冲突的方法避免产生聚集现象，也将提高查找效率。例如，用拉链法解决冲突时不存在聚集现象，用线性探测法解决冲突时易引起聚集现象。 8． 图G 是n 个顶点的无向完全图，则下列说法不正确的是（ ） A.G 的邻接多重表需要n （n-l ）个边结点和n 个顶点结点 第 3 页，共 56 页 B.G 的连通分量个数最少 C.G 为连通图 D.G 所有顶点的度的总和为n （n-1） 【答案】A 【解析】A 项中G 的邻接多重表中需要n （n-l ）/2个边结点和n 个顶点结点。此时连通分量最少为1。无向完全图中任意两个顶点之间都存在路径，则G 必为连通图。每个顶点的度为n-1，则n 个结点的度的总和为n （n-l ）。 9． 用有向无环图描述表达式（A+B）*（，至少需要顶点的数目为（ ）（A+B）/A）。 A.5 B.6 C.8 D.9 【答案】A 【解析】一共5个结点 6条边 10．主机甲与乙之间已建立一个TCP 连接，双方持续有数据传输，且无差错与丢失。若甲收到1个来自乙的TCP 段，该段的序号为1913、确认序号为2046、有效载荷为100字节，则甲立即发送给乙的TCP 段的序号和确认分别是（ ） A.2046、 2012 B.2046、 2013 C.2047、 2012 D.2047、 2012 【答案】B 【解析】若甲收到1个来自乙的TCP 段，该段的序号seq=1913、确认序号ack=2046、有效载荷为100字节，则甲立即发送给乙的TCP 段的序号seql=ack=2046和确认序号ackl =seq+100=2013, 答案为B 。 11．若平衡二叉树的高度为6, 且所有非叶结点的平衡因子均为1，则该平衡二叉树的结点总数为（ ）。 A.12 B.20 C.32 D.33 【答案】B 。 【解析】本题题目的实际问题是，具有6层结点的平衡二叉树含有最少的结点数是多少。表示深度为h 的平衡二叉树中含有的最少结点数，有 由此可得对应的平衡二叉树如下图所示。 第 4 页，共 56 页