2017年四川大学874计算机科学专业基础综合之数据结构考研导师圈点必考题汇编(1)
● 摘要
一、选择题
1． 主机甲与主机乙之间使用后退N 帧协议（GBN ）传输数据，甲的发送窗口尺寸为1000, 数据帧长为1000字节，信道宽带为100Mbps ，乙每收到一个数据帧立即利用一个短帧（忽略其传输延迟）进行确认，若甲乙之间 的单向传播延迟是50ms ，则甲可以达到的最大平均数据传输速率约为（ ）
A .10 Mbps
B. 20 Mbps
C.80 Mbps
D.100 Mbps
【答案】C 【解析】
2． 设n 是描述问题规模的非负整数，下面程序片段的时间复杂度是（ ）。
【答案】A
【解析】其中，以基本的原操作重复执行的次数作为算法的时间度量。题目中的基本运算是语句，则有设其执行时间为T （n ）
3． 假设磁头当前位于第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。
4． 采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是（ ）。
A. 递归次数与初始数据的排列次序无关
B. 每次划分后，先处理较长的分区可以减少递归次数
C. 每次划分后，先处理较短的分区可以减少递归次数
D. 递归次数与每次划分后得到的分区的处理顺序无关
【答案】D
【解析】快速排序是递归的，递归过程可用一棵二叉树给出，递归调用层次数与二叉树的深
，采用快速排序方法，其对应递归调用度一致。例如：待排序列{48, 62，35, 77, 55, 14, 35, 98）
过程的二叉树如下图所示。
在最坏情况下，若初始序列按关键码有序或基本有序时，快速排序反而蜕化为冒泡排序。即其对应递归调用过程的二叉树是一棵单支树。因此快速排序的递归次数与初始数据的排列次序有关。但快速排序的递归次数与每次划分后得到的分区处理顺序无关，即先处理较长的分区或先处理较短的分区都不影响递归次数。
5． 若一棵二叉树的前序遍历序列为a ，e ，b ，d ，c ，后序遍历序列为b , c, d, e, a, 则根结点的孩子结点（ ）。
A. 只有e
B. 有 e 、b
C. 有 e 、c
D. 无法确定
【答案】A 。
b , d, c, 后序遍历序列为b ，c , d, 【解析】由题目可知，若一棵二叉树的前序遍历序列为a , e，
e , a , 其中a 为这棵二叉树的根结点，接下来，在前序遍历的第二个结点为e , 而后序遍历的倒数第二个结点为e , 说 明a 的孩子结点只有e 。
6． 从堆中删除一个元素的时间复杂度为（ ）。
【答案】B
【解析】堆中删除一个元素，需要重新调整堆，其时间复杂度为
7． 若用户进程访问内存时产生缺页，则下列选项中，操作系统可能执行的是（ ）
I. 处理越界错 II. 置换页 III. 分配内存
A. 仅I 、II
B .仅II 、III
C. 仅I 、III
D.I 、II 、和III
【答案】B
【解析】用户进程访问内存时缺页会发生缺页中断。发生缺页中断，系统地执行的操作可能是置换页面或分配内存。系统内没有越界的错误，不会进行越界出错处理。
8． 若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是（ ）。
A.257
B.258
C.384
D.385
【答案】C
【解析】由
：
_
则和
__可知
，
即显然
384, 所以二叉树的叶结点个数是384。还可以根据完全二叉树的另一个性质：最后一个分支结点的序号为[768/2], 故非叶子结点数为384, 而叶子结点的个数为768-384=384。（[x]表示不大于x 的最大整数，比如[3.14] =3）。
9． 下列序列中，（ ）是执行第一趟快速排序后所得的序列。
【答案】C
【解析】快速排序将数据划分成两部分，其中一部分关键字比另一部分关键字小。
10． 为支持中视频文件的快速随机播放，播放性能最好的文件数据块组织方式是（ ）
A. 连续结构
B. 链式结构
C. 直接索引结构
D. 多级索引结钩
【答案】A
【解析】为了实现快速随机播放，要保证最短的查询时间，即不能选取链表和索引结构，因此连续结构最优。
11．4个圆盘的Hanoi 塔，总的移动次数为（ ）。
A.7
B.-8
C.15