2017年山东省培养单位烟台海岸带研究所864程序设计之数据结构考研导师圈点必考题汇编
● 摘要
一、选择题
1． 5个字符有如下4种编码方案，不是前缀编码的是（ ）
A.
B.
C.
D.
【答案】D
【解析】在一个字符集中，任何一个字符的编码都不是另一个字符编码的前缀。约定左分支
表示字符
右分支表示字符则可以用从根结点到叶子结点的路径上的分支字符串作为该叶子结点字符的编码。如此得到的编码必是前缀编码。D 选项中，编码110是编码1100的前缀，故不符合前缀编码的定义。
2． 某计算机处理器主频为50MHz ，采用定时查询方式控制设备A 的I/0, 查询程序运行一次所用的时钟 周期数至少为500。在设备A 工作期间，为保证数据不丢失，每秒需对其查询至少200次，则CPU 用于设备A 的I/0的时间占整个CPU 时间的百分比至少是（ ）。
A.0.02%
B.0.05%
C.0.20%
D.0.50%
【答案】C
【解析】对于设备A ，每秒中查询至少200次，每次查询至少500个时钟周期，总的时钟周期数为100000, 又因为处理器主频为50MHz 。所以CPU 用于设备A 的I/0的时间占整个CPU 时间的百分比至少为100000/50=0.20%。
3． 下列因素中，不会影响信道数据传输速率的是（ ）
A. 信噪比
B. 频率宽带
C. 调制速率
D. 信号传播速度
【答案】D
【解析】信道数据传输速率与信噪比、频率宽度、调制速率都有关。
4． 将两个各有N 个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。
A.N
B.2N-1
C.2N
D.N-1
【答案】A
【解析】归并排序基本思想：归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表。归并排序最好情况下的复杂度为
5． 若对如下的二叉树进行中序线索化，则结点x 的左、右线索指向的结点分别是（ ）
A.
B.
C.
D.
【答案】D
【解析】此二叉树的中序遍历序列为：debxac ，由于节点x 左右孩子都为空，所有进行中序线索化时，它的左右孩子指针分别指向它的中序遍历序列的直接前驱结点b 和直接后继结点a , 所以选D
6． 下列选项中，导致创建新进程的操作是（ ）。
用户登录成功
设备分配
启动程序执行
A.
仅
和
B.
仅
和
C.
仅
和
D. 和
【答案】C
【解析】进程创建是需要填写PCB 表的，其中唯一不需要的是II 。考察一个进程创建的过程是这样的：当进程被创建，可以是用户创建，例如双击相关图标；也可以由父进程创建，例如lock
（ ）时，操作系统首先到PCB 表区搜索空闲的表格，若无则直接拒绝创建进程，若有则填
，许多操写PCB 表创建进程。通常填写PCB 表的过程有一段时间（主要涉及资源分配需要协调）
，也有的操作系统不设这个中间状态。此时操作系作系统为此设立了一个中间状态称为“初始化”
统填写进程ID 号、处理机参数、进程参数（状态、特权、优先级）、分配内存（若是虚拟存储就分配虚拟地址）、映射文件等，一切就绪，将控制权交给系统进行下一步调度。设备分配可能引起进程状态的改变，但不会创建新进程，用户登录成功和启动程序执行都会创建新的进程，所以本题答案为C 。
7． 主机甲与主机乙之间已建立一个TCP 连接，主机甲向主机乙发送了 3个连续的TCP 段，分别包含300字节、400字节和500字节的有效载荷，第3个段的序号为900。若主机乙仅正确接收到第1和第3个段，则主机乙发送给主机甲的确认序号是（ ）。
A.300
B.500
C.1200
D.1400
【答案】B
【解析】本题考查TCP 的确认机制，TCP 首部的序号字段是指本报文所发送的数据的第一个字节的序号。本题中首先根据第3个段的序号为900, 可以得出第2个段的序号为500, 第1个段的序号为200, 这里主机乙仅 正确接收了第1段和第3段，这意味着第2段丢失，需要超时重传，因此主机乙发送给主机甲的确认序号，也就是此时接收端期望收到的下一个数据包中第一个字节的序号应该是第二段的第一个字节的序号，也就是500, 因此答案是B 。
8． 希尔排序的组内排序采用的是（ ）。
A. 直接插入排序
B. 折半插入排序
C. 快速排序
D. 归并排序
【答案】A
【解析】希尔排序基本思想是：先将整个待排元素序列按某个增量分割成若干个子序列，在子序列内进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。
9． —个多道批处理系统中仅有P1和P2两个作业，P2比P1晚5ms 到达。它们的计算和
P1:计算60ms ，作顺序如下：计算
计算计算
虑调度和切换时间，则完成两个作业需要的时间最少是（ ）。
A.240ms
B.260ms
C.340ms
D.360ms
操若不考
相关内容
相关标签