2017年烟台大学计算机与控制工程学院846数据结构考研导师圈点必考题汇编
● 摘要
一、选择题
1． 有
A.
B.
C.
D. 个分支结点的满二叉树的深度是（ ）。
【答案】C
【解析】满二叉树的结点总数=分支的结点总数+非分支的结点总数。由于此树为满二叉树，所以非分支的结点总数为1，所以满二叉树共有个结点，所以满二叉树的深度为
2． 使用浏览器访问某大学Web 网站主页时，不可能使用的协议是（ ）
A.PPP
B.ARP
C.UDP
D.SMTP
【答案】D
【解析】SMTP 是简单邮件传输协议，访问主页时并不涉及邮件相关协议。
3． 为支持 中视频文件的快速随机播放，播放性能最好的文件数据块组织方式是（ ）
A. 连续结构
B. 链式结构
C. 直接索引结构
D. 多级索引结钩
【答案】A
【解析】为了实现快速随机播放，要保证最短的查询时间，即不能选取链表和索引结构，因此连续结构最优。
4． 下列寄存器中，汇编语言程序员可见的是（ ）。
A. 存储器地址寄存器（MAR ）
B. 程序计数器（PC ）
C. 存储器数据寄存器（MDR ）
D. 指令寄存器（IR ）
【答案】B
【解析】CPU 有5个专用寄存器，它们是程序计数器（PC ）、指令寄存器OR ）、存储器地址
，这些寄存器中有些寄存器（MAR ）、 存储器数据寄存器（MBR ）和状态标志寄存器（PSWR ）
是CPU 的内部工作寄存器，对汇编语言程序员来说是透明的，在汇编语言程序设计中不会出现。但汇编语言程序员可以通过制定待执行指令的地址来设置PC 的值，所以程序计数器（PC ）对于汇编语言程序员可见的。
5． 假设磁头当前位于第105道，正在向磁道序号増加的方向移动。现有一个磁道访问请求，序列为35, 45, 12, 68, 110, 180, 170, 195，采用SCAN 调度（电梯调度）算法得到的磁道访问序列是（ ）。
A.110, 170, 180, 195，68, 45, 35，12
B.110，68，45，35，12，170，180，195
C.110，170，180，195，12，35, 45, 68
D.12, 31, 45, 68, 110, 170, 180, 195
【答案】A
【解析】SCAN 算法类似电梯工作原理，即朝一个固定方向前进，经过的磁道有访问请求则马上服务，直至到达一端顶点，再掉头往回移动以服务经过的磁道，并这样在两端之间往返。因此，当磁头从105道向序号増加的方向移动时，便会服务所有大于105的磁道号（从小到大的顺序）；往回返时又会按照从大到小的顺序进行服务。注意与循环扫描算法的区别，所以SCAN 算法的访问序列是：110, 170，180，195, 68, 45, 35, 12。
6． 在任意一棵非空二叉排序树T1中，删除某结点v 之后形成二叉排序树T2, 再将v 插入T2形成二叉排序树T3。下列关于T1与T3的叙述中，正确的是（ ）
I. 若v 是T1的叶结点，则T1与T3不同
II. 若v 是T1的叶结点，则T1与T3相同
III. 若v 不是T1的叶结点，则T1与T3不同
IV . 若v 不是T1的叶结点，则T1与T3相同
A. 仅 I 、III
B .仅 I 、IV
C. 仅 II 、III
D. 仅 II 、IV
【答案】C
【解析】在一棵二叉排序树中删除一个结点后再将此结点插入到二叉排序树中，如果删除的结点是叶子结点那么在插入结点后，后来的二叉排序树与删除结点之前相同。如果删除的结点不是叶子结点，那么再插入这个结点后，后来的二叉树可能发生变化，不完全相同。
7． 已知串其Next 数组值为（ ）。
A.0123
B.1123
C.1231
D.1211
【答案】A
【解析】KMP 算法的next 数组建立的原则
8． 某同步总线采用数据线和地址线复用方式。其中地址数据线有8根，总线时钟频率为66MHZ , 每个时钟同期传送两次数据。（上升沿和下降沿各传送一次数据）该总线的最大数据传输率是（总线带宽）（ ）
：
A.
B.
C.
D.
【答案】C
【解析】总线带宽=总线工作频率X （总线宽度/8）, 由于地址线与数据线复用，所以在两次数据传输过程中总线上数据一共传输了8次，那么总线带宽为
9． 下列关于最小生成树的叙述中，正确的是（ ）。 所以选C
I . 最小生成树的代价唯一 II. 所有权值最小的边一定会出现在所有的最小生成树中III. 使用普里姆（Prim ）算法从不同顶点开始得到的最小生成树一定相同IV . 使用普里姆算法和克鲁斯卡尔（Kruskal ）算法得到的最小生成树总不相同
A. 仅I
B. 仅II
C. 仅 I 、III
D. 仅 II 、IV
【答案】A 。
【解析】当图中存在相同权值的边时，其最小生成树可能是不唯一的，但最小生成树的代价
所以说法I 正确。一定是相同的，从n 个顶点的连通图中选取n-1条权值最小的边可能构成回路，
所以说法II 错误。当某个顶点有权值相同的边，使用普里姆（Prim ）算法从不同顶点开始得到的最小生成树并不一定相同，所以说法III 错误。当最小生成树不唯一时，使用普里姆算法和克鲁斯卡尔（Krnskal ）算法得到的最小生成树可能相同，也可能不同，所以说法IV 错误。由此可得出正确答案。
10．给定二叉树如下图所示。设N 代表二叉树的根，L 代表根结点的左子树，R 代表根结点的右子树，若遍历后的节点序列为3，1，7，5，6，2，4，则其遍历方式是（ ）
A.LRN
B.NRL
C.RLN
D.RNL
相关内容
相关标签