2017年大连理工大学电子信息与电气工程学部810数据结构和计算机组成原理之数据结构考研题库
● 摘要
一、选择题
1． 下列指令中，不能在用户态执行的是（ ）
A.trap 指令 B. 跳转指令 C. 后栈指令 D. 关中断指令 【答案】D
【解析】关中断指令必须在和心态才能执行，trap 指令可以在用户态下执行，执行了就转到和心态，跳转与退栈指令都是可以在用户态下执行的指令。
2． 对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是（ ）。
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 对应的查找树都是二叉排序树，只有选项A 对应的查找树不是一棵二叉排序树，因为在以91为根的左子树中出现了比91大的结点94。
3． 链表不具有的特点是（ ）。
A. 插入、删除不需要移动元素 B. 可随机访问任一元素
C. 不必事先估计存储空间 D. 所需空间与线性长度成正比 【答案】B
【解析】B 项是顺序表的特点。只要确定了顺序线性表的起始位置，线性表中的任一数据元素都可随机存取。
4． 主机甲和乙已建立了TCP 连接，甲始终以MSS=1KB大小的段发送数据，并一直有数据发送；乙每收到一个数据段都会发出一个接收窗口为10KB 的确认段。若甲在t 时刻发生超时时拥塞窗 口为8KB , 则从t 时刻起，不再发生超时的情况下，经过10个RTT 后，甲的发送窗口是（ ）。
A.10KB B.12KB C.14KB D.15KB 【答案】A
【解析】发送窗口是接受窗口和拥塞窗口的最小值，这里接收窗口总是10KB 。拥塞窗口到那个时候是大于10KB 的，取最小值。
5． 假设栈初始为空，将中缀表达式
当扫描到f 时，栈中的元素依次是（ ）
A.
B. C. D. 【答案】B
【解析】中缀表达式转后缀表达式遵循以下原则： （1）遇到操作数，直接输出； （2）栈为空时，遇到运算符，入栈； （3）遇到左括号，将其入栈；
（4）遇到右括号，执行出栈操作，并将出桟的元素输出，直到弹出栈的是左括号， 左括号不输出； （5）遇到其他运算符运算符入栈；
（6）最终将栈中的元素依次出栈，输出。 所以扫描到优先级比优先级比
入栈‘描到
由于
优先级比
低，所以将
弹出，
入栈；扫描到
，
高，入栈；扫描到
入栈; 扫描到
将栈中优先级更高的
弹出，入栈; 扫描到
时，弹出所有优先级大于或等于该运算符的栈顶元素，然后将该
转换为等价后缀表达式的过程中，
高，入栈。所以扫描到f 的时候，栈中元素为
6． 下列选项中，满足短任务优先且不会发生饥饿现象的调度算法是（ ）。
A. 先来先服务 B. 高响应比优先 C. 时间片轮转
D. 非抢占式短任务优先 【答案】B
【解析】分析该题目可以看到，本题所提到的问题是涉及短任务调度也就是属于作业调度，因此首先排除时 间片轮转算法；因为作业调度算法中没有时间片轮转的算法。其次，因为问题提到短任务，则先来先服务的算法也可以排除了，它与短任务无关。剩余高响应比优先算法和非抢占式短任务优先是哪一个? 我们可以通过分析得到，非抢占式短任务优先算法不能解决饥饿问题，因为当一个系统短任务源源不断到达是，长任务必然会得不到 调度，产生饥饿。而解决此方法的最好方式就是采用计算响应比的方法，并以高响应比值优先调度。这样，无论短任务或长任务，均可以得到调度，而且，较短任务会得到优先的调度。故满足短任务优先且不会发生饥饿现象的调度算法只有尚响应比优先算法。
7． 下列选项中，对正确接收到的数据帧进行确认的MAC 协议是（ ）。
A.CSMA B.CDMA C.CSMA/CD D.CSMA/CA 【答案】D
【解析】可采用排除法。CDMA 是码分多址复用，是物理层的内容；CSMA/CD即带冲突检测的载波监听多 路访问，接收方并不需要确认；CSMA/CD是CSMA 的加强版，故CSMA 也无确定；CSMA/CD是802.11中的 协议，其利用ACK 信号来避免冲突的发生，也就是说，只有当 客户端收到网络上返回的ACK 信号后才确认送 出的数据已经正确到达目的地址，因此答案是D 。
8． 下列选项中会导致进程从执行态变为就绪态的事件是（ ）。
A. 执行P （wait ）操作 B. 申请内存失败 C. 启动I/O设备 D. 被尚优先级进程抢占 【答案】D
【解析】D 项，被高优先级进程抢占，进程会由执行态变为就绪态。ABC 三项，程序由于缺少资源而由执行态转为阻塞态。
9． 排序算法的稳定性是指（ ）。
A. 经过排序之后，能使值相同的数据保持原顺序中的相对位置不变 B. 经过排序之后，能使值相同的数据保持原顺序中的绝对位置不变
相关内容
相关标签