2016年宁夏医科大学公共卫生与管理学院数据结构复试笔试最后押题五套卷
● 摘要
一、选择题
1． 下面关于B 和B+树的叙述中，不正确的是（ ）
A.B 树和B+树都是平衡的多叉树
B.B 树和B+树都可用于文件的索引结构
C.B 树和B+树都能有效地支持顺序检索
D.B 树和B+树都能有效地支持随机检索
答:C
【解析】B 树是一种平衡的多分树，通常我们说m 阶的B 树，它必须满足如下条件：①每个结点至多有m 个子结点；②除根结点和叶结点外，其它每个结点至少有个子结点；③若根结点不是叶子结点，则至少有两个子结点；④所有的叶结点在同一层；⑤有k 个子结点的非根结点恰好包含k-1个关键码。B+树是B 树的一种变形树，它与B 树的差异在于：有k 个子结点的结点必然有k 个关键码；非叶结点仅具有索引作用，跟记录有关的信息均存放在叶结点中。其中B 树适合与随即检索，不适合于顺序检索，所以C 项错误。
2． 采用指令Cache 与数据Cache 分离的主要目的是（ ）
A. 减低Cache 的缺失损失
B. 提高Cache 的命中率
C. 减低CPU 平均访问时间
D. 减少指令流水线资源冲突
答:D
【解析】指令流水线不会断流，预取过来的都是指令
3． 在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个。
A.4
B.5
C.6
D.7
答:C
【解析】设度为0的结点数为x 则度为3的树总结点数n=度为0的结点数+度为1的结点数+度为2的结点数+度为3的结点数
为3
的树总结点数
从每个结点所指向的结点数的和的角度来计算度两种方法所计算出来的n 相等，所以
4． 若将关键字1，2, 3, 4, 5, 6, 7依次插入到初始为空的平衡二叉树T 中，则T 中平衡因子为0的分支结点的个数是（ ）
A.0
B.1
C.2
D.3
答:D
【解析】将图中给定的关键字序列依次插入到平衡树中，构成的平衡树如下图所示，由图可知平衡因子为0的分支结点为3个叶子结点，故答案为D 。
5． 有
A. B.
C.
D.
答:C 个分支结点的满二叉树的深度是（ ）。
【解析】满二叉树的结点总数=分支的结点总数+非分支的结点总数。由于此树为满二叉树，
所以非分支的结点总数为1，所以满二叉树共有个结点，所以满二叉树的深度为
6． 下列选项给出的是从根分别到达两个叶节点路径上的权值序列，能属于同一棵哈夫曼树的是（ ）。
A.24，10，5 和24，10，7
B.24，10，5 和24，12，7
C.24，10，10和24，14，11
D.24，10，10和 24，14，6
答:D
【解析】哈夫曼树是带权路径长度最短的二叉树。由根节点出发到两个叶子节路径中，第二个被访问的两个结点的权值要么相等，要么和为根节点的权值，故B 项错误。同理，通过第三个被访问的节点排除A 项。C 项，由两条路径可推出三个叶子节点的权值分别是：3、10和11，而根据哈夫曼树的定义可知，权值为3的节点应该和权值为10的结点结合，故C 项错误。D 项，反推出有四个叶子节点，权值分别为：5、5、6和8，满足哈夫曼树的条件。
7． 下列进程调度算法中，综合考虑进程等待时间和执行时间的是（ ）。
A. 时间片轮转调度算法
B. 短进程优先调度算法
C. 先来先服务调度算法
D. 尚响应比优先调度算法
答:D
【解析】时间片轮转法和先来先服务算法都是公平的方法，并未考虑进程等待时间和执行时间，而短进程优先考虑的是进程执行时间。最高响应比优先调度算法是最先执行响应比最尚的进程（响应比=1＋等待时间/估计运行时间）。该算法综合了先来先服务（FCFS ）和短作业优先（SJF ）算法，FCFS 只考虑每个作业的等待时间，而未考虑执行时间的长短。SJF 只考虑执行时间的长短，而未考虑等待时间的长短，HRRN 算法则同时考虑执行时间和等待时间。
8． 对于100Mbps 的以太网交换机，当输出端口无排队直通（cut-throughswitching ）方式转发一个以太网帧（不包括前导码）时，引入的转发延迟至少是（ ） A. B. C. D.
答:B
【解析】直通交换方式是指以太网交换机可以在各端口间交换数据。它在输入端口检测到一个数据包时，检查该包的包头，获取包的目的地址，启动内部的动态查找表转换成相应的输出端口，在输入与输出交叉处接通，把数据包直通到相应的端口，实现交换功能。通常情况下，直通交换方式只检查数据包的包头即前14个字节，由于不需要考虑前导码，只需要检测目的地址的6B ，
所以最短的传输延迟是
9． 线性表是具有n 个（ ）的有限序列（n ＞0）。
A. 表元素
B. 字符
C. 数据元素
D. 数据项E. 信息项
答:C
【解析】一个线性表是n 个数据元素的有限序列。至于每个数据元素的具体含义，在不同的情况下各不相同。
10．对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是（ ）。
A.95, 22, 91, 24, 94, 71
B.92, 20, 91, 34, 88, 35
C.21, 89, 77, 29, 36, 38
D.12, 25, 71, 68, 33, 34
答:A
【解析】各选项对应的查找过程如下图所示，从中看到选项B 、C 、D 对应的查找树都是二叉
相关内容
相关标签