2017年广州大学数学与信息科学学院623数据结构考研题库
● 摘要
一、选择题
1． 对序
列
A.1
B.4
C.3
D.2
【答案】B
【解析】由所给的序列知，本序列要进行递增排序，经过一趟后15的位置没有变化，而给的序列中只有20比15大，20的位置和15的位置相差4。所以该次采用的増量是4。
2． 在参考摸型中，下列功能需由应用层的相邻层实现的是（ ）
A. 对话管理
B. 数据格式转换
C. 路由选择
D. 可靠数据传输
【答案】B
【解析】应用层的相邻层即为表示层，表示层负责管理数据的压缩、加密与解密、格式装换等，故答案为B 。
3． 下列选项中，满足短任务优先且不会发生饥饿现象的调度算法是（ ）。
A. 先来先服务
B. 高响应比优先
C. 时间片轮转
D. 非抢占式短任务优先
【答案】B
【解析】分析该题目可以看到，本题所提到的问题是涉及短任务调度也就是属于作业调度，因此首先排除时 间片轮转算法；因为作业调度算法中没有时间片轮转的算法。其次，因为问题提到短任务，则先来先服务的算法也可以排除了，它与短任务无关。剩余高响应比优先算法和非抢占式短任务优先是哪一个? 我们可以通过分析得到，非抢占式短任务优先算法不能解决饥饿问题，因为当一个系统短任务源源不断到达是，长任务必然会得不到 调度，产生饥饿。而解决此方法的最好方式就是采用计算响应比的方法，并以高响应比值优先调度。这样，无论短任务或长任务，均可以得到调度，而且，较短任务会得到优先的调度。故满足短任务优先且不会发生饥饿现象的调度算法只有尚响应比优先算法。
第 2 页，共 58 页 用希尔排序方法排序，经一趟后序列变
为则该次采用的增量是（ ）。
4． 假设栈初始为空，将中缀表达式
当扫描到f 时，栈中的元素依次是（ ）
A.
B.
C.
D.
【答案】B
【解析】中缀表达式转后缀表达式遵循以下原则：
（1）遇到操作数，直接输出；
（2）栈为空时，遇到运算符，入栈；
（3）遇到左括号，将其入栈；
（4）遇到右括号，执行出栈操作，并将出桟的元素输出，直到弹出栈的是左括号，
左括号不输出；
（5）遇到其他运算符
运算符入栈；
（6）最终将栈中的元素依次出栈，输出。 所以扫描到
优先级比入栈‘描到
由于优先级比低，所以将弹出，
入栈；扫描到，高，入栈；扫描到入栈; 扫描到将栈中优先级更高的弹出，入栈; 扫描到时，弹出所有优先级大于或等于该运算符的栈顶元素，然后将该
转换为等价后缀表达式的过程中，优先级比高，入栈。所以扫描到f 的时候，栈中元素为
5． ARP 协议的功能是（ ）。
A. 根据IP 地址查询MAC 地址
B. 根据MAC 地址查询IP 地址
C. 根据域名查询IP ±也址
D. 根据IP 地址查询域名
【答案】A 。
【解析】ARP 协议是网络层协议，因此只能和传输层和数据链路层有关系，从这一点出发，域名是应用层的范畴，选项C 和D 是不正确的，根据MAC 地址查询IP 地址是RARP 协议的功能，因此进而得出正确答案是A 。
6． 图的BFS 生成树的树高比DFS 生成树的树高（ ）。
A. 小或相等 B. 小 C. 大或相等 D. 大
【答案】A
【解析】BFS 称作广度优先搜索，DFS 称作深度优先搜索。广度优先搜索类似与二叉树的层序遍历算法，深度优先搜索类似于树的先序遍历。因为深度优先搜索算法遵循的策略是尽可能的
第 3 页，共 58 页
“深”地搜索一个图。所以图的BFS 生成树的树高比DFS 生成树的树高小或者相等。
7． 采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是（ ）。
A. 递归次数与初始数据的排列次序无关
B. 每次划分后，先处理较长的分区可以减少递归次数
C. 每次划分后，先处理较短的分区可以减少递归次数
D. 递归次数与每次划分后得到的分区的处理顺序无关
【答案】D
【解析】快速排序是递归的，递归过程可用一棵二叉树给出，递归调用层次数与二叉树的深
，采用快速排序方法，其对应递归调用度一致。例如：待排序列{48, 62，35, 77, 55, 14, 35, 98）
过程的二叉树如下图所示。
在最坏情况下，若初始序列按关键码有序或基本有序时，快速排序反而蜕化为冒泡排序。即其对应递归调用过程的二叉树是一棵单支树。因此快速排序的递归次数与初始数据的排列次序有关。但快速排序的递归次数与每次划分后得到的分区处理顺序无关，即先处理较长的分区或先处理较短的分区都不影响递归次数。
8． 下列选项中会导致进程从执行态变为就绪态的事件是（ ）。
A. 执行P （wait ）操作
B. 申请内存失败
C. 启动I/O设备
D. 被尚优先级进程抢占
【答案】D
【解析】D 项，被高优先级进程抢占，进程会由执行态变为就绪态。ABC 三项，程序由于缺少资源而由执行态转为阻塞态。
9． 假定有4个整数用8位补码分别表示为
存放在一个8位寄存器中，则下列运算会发生溢出的是（ ）。
A.r1×r2
B.r2×r3
C.r1×r4
D.r2×r4
【答案】B
第 4 页，共 58 页 若将运算结果