2016年昆明理工大学知识产权发展研究院J006数据结构(同等学力加试)复试笔试仿真模拟题
● 摘要
一、选择题
1．
协议对
A.011111000011111010
B.011111000111110101111110
C.01111100011111010
D.011111000111111001111101
【答案】A
HDLC 协议对比特串进行组帧时，HDLC 数据帧以位模式0111 1110标识每一个帧的【解析】
开始和结束，因此在帧数据中凡是出现了 5个连续的位“1”的时候，就会在输出的位流中填充一个“0”。所以答案为A 。
2． 若X 是二叉中序线索树中一个有左孩子的结点，且X 不为根，则X 的前驱为（ ）。
A.X 的双亲
B.X 的右子树中最左的结点
C.X 的左子树中最右的结点
D.X 的左子树中最右的叶结点
【答案】C
【解析】中序线索，只有把其左子树最右结点遍历完后，才会遍历自己，所以X 的前驱为X 的左子树中最右的结点。
3． 下列二叉排序树中，满足平衡二叉树定义的是（ ）。
组帧后对应的比特串为（ ）
【答案】B
【解析】平衡二叉树是指左右子树高度差（平衡因子）的绝对值不超过1的二叉树。A 项中根结点的平衡因子是2; B 项中每个结点的平衡因子的绝对值均不超过1; C 项中根结点的平衡因子是-2; D 项中根结点的平衡因子是3。
4．
用户程序发出磁盘
是（ ）
A. 用户程序
B. 系统调用处理程序
C. 设备驱动程序
D. 中断处理程序
【答案】C 请求后，系统的处理系统的处理流程是：用户程序一系统调用处理程序一设备骆动程序一中断处理程序。其中，计算数据所在磁盘的柱面号、磁头号、扇区号的程序
【解析】计算磁盘号、磁头号和扇区号的工作是由设备驱动程序完成的，所以答案选C 。
5． 有向带权图如题图所示，若采用迪杰斯特拉（Dijkstra ）算法求从源点a 到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是b ，第二条最短路径的目标顶点是c ，后续得到的其余各最短路径的目标顶点依次是（ ）。
题图有向带权图
A.d , e , f
B.e , d , f
C.f , d , e
D.f , e , d
【答案】C 。
【解析】本题主要考查Dijkstra 算法的思想和解题步骤。题目执行算法过程中各步的状态如下表所示。
执行Dijkstra 算法过程中各步的状态表，故后续目标顶点依次为f ，d , e 。
6． 某磁盘的转速为10, 000转/分，平均寻道时间是为磁盘传输速率是磁盘控制器延迟
读取一个4KB 的扇区所需平均时间约为（ ）
A.9ms
B.9.4ms
C.12ms
D.12.4ms
【答案】B
【解析】磁盘转速是10 000转/分钟，平均转一转的时间是6ms ，因此平均查询扇区的时间是3ms ，平均寻道时间是6ms ，读取4KB 扇区信息的时间为0.2ms ，信息延迟的时间为0.2ms ，总时 间为
7． 下列关于银行家算法的叙述中，正确的是（ ）
A. 银行家算法可以预防死锁
B. 当系统处于安全状态时，系统中一定无死锁进程
C. 当系统处于不安全状态时，系统中一定会出现死锁进程
D. 银行家算法破坏了死锁必要条件中的“请求和保持”条件
【答案】B
【解析】银行家算法是避免死锁的方法。利用银行家算法，系统处于安全状态时没有死锁进程，故答案选B 。
8． 某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，元素a , b , c , d , e 依次入此队列后再进行出队操作，则不可能得到的出队序列是（ ）。
A.b ，a , c , d ，e
B.d ，b , a , c ，e
C.d ，b , c , a ，e
D.e ，c ，b , a ，d
【答案】C
【解析】根据题意，队列两端都可以输入数据元素，但是只能在一端输出数据元素，这种队列为输出受限的双端队列。本题解题方法分别判断每个选项如何入队和出队，从而得出不可能的情况。
假设L 代表从左端入队，R 代表从右端入队，出队都是从左端L 出。四个选项所给序列的进队操作序列分别为：
选项 A. aL （或 aR ）, bL, cR, dR, eR 选项 B. aL （或 aR ）, bL, cR，dL , eR 选项C. 不可能出现 选项 D. aL （或 aR ）, bL, cL, dR, eL
9． 数据序列只能是下列排序算法中的（ ）的两趟排序后的结果。
A. 选择排序
B. 起泡排序
C. 插入排序
D. 堆排序
相关内容
相关标签