2018年太原科技大学计算机科学与技术学院828数据结构考研仿真模拟五套题
● 摘要
一、单项选择题
1． 设计一个判别表达式中左、右括号是否配对出现的算法，采用（ ）数据结构最佳。
A. 线性表的顺序存储结构
B. 队列
C. 线性表的链式存储结构
D. 栈
【答案】D
【解析】用栈更合适，如果是左括号，进栈；如果是右括号，看栈顶是不是左括号，如果是，则左括号出栈；否则不配对(可以直接结束算法) 。处理完所有符号号，如果栈为空则配对成功。
2． 若数据元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是（ ）.
A.. 起泡排序
B. 插入排序
C. 选择排序
D. 二路归并排序
【答案】B
【解析】经过两趟排序后，A 项起泡排序的结果是两个最小或最大的元素放到了序列的最终位置；B 项插入排序的结果是前三个数有序即可；C 项选择排序结果是两个最小的元素在最前面按顺序排好；D 项二路归并排序的结果是长度为4的子序列有序，即前4个数排好序，接下来的4个数排好序. 显然题目中的元素序列只能是插入排序第二趟排序后的结果，因此，B 项正确.
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． 使用浏览器访问某大学Web 网站主页时, 不可能使用的协议是（ ）
A.PPP
B.ARP
C.UDP
D.SMTP
【答案】D
【解析】SMTP 是简单邮件传输协议, 访问主页时并不涉及邮件相关协议。
5． 下列二叉排序树中，满足平衡二叉树定义的是（ ）. A. B. C. D.
【答案】B
【解析】平衡二叉树是指左右子树高度差(平衡因子) 的绝对值不超过1的二叉树.A 项中根结
B 项中每个结点的平衡因子的绝对值均不超过1；C 项中根结点的平衡因子是；点的平衡因子是2；
D 项中根结点的平衡
因子是3.
6． 在下列表述中，正确的是（ ）
A. 含有一个或多个空格字符的串称为空格串
B. 对n(n＞0) 个顶点的网，求出权最小的n ﹣1条边便可构成其最小生成树
C. 选择排序算法是不稳定的
D. 平衡二叉树的左右子树的结点数之差的绝对值不超过1
【答案】C
【解析】平衡二叉树的左右子树的深度之差的绝对值不超过1。求最小生成树时，每次挑最小权值边，是要求该边的两点都在不同的连通分量上的。
7． 执行（ ）操作时，需要使用队列做辅助存储空间。
A. 查找哈希(Hash)表
B. 广度优先搜索网
C. 前序(根) 遍历二叉树
D. 深度优先搜索网
【答案】B
【解析】查找哈希表不需要辅助存储空间，前序遍历二叉树和深度优先搜索网需要使用栈做辅助存储空间，广度优先搜索树需要队列做辅助存储空间。
8． 某设备中断请求的相应和处理时间为100ns , 每400ns 发出一次中断请求, 中断相应所容许的最长延迟时间为50ns , 则在该设备持续工作过程中CPU 用于该设备的
分比至少是（ ） A. B. C. D.
【答案】B
【解析】每400ns 响应一次中断并且用100ns 进行处理, 所以该设备的时间占用CPU 时间百分比为100/400=25%, 中断响应容许的延迟时间对此没有影响, 属于干扰条件。
9． 若X 是后序线索二叉树中的叶结点, 且X 存在左兄弟结点Y , 则X 的右线索指向的是 （ ）
A.X 的父结点
B. 以Y 为根的子树的最左下结点
C.X 的左兄弟结点Y
D. 以Y 为根的子树的最右下结点
【答案】A
【解析】根据后续线索二叉树的定义, X 结点为叶子结点且有左兄弟, 那么这个结点为右孩子结点, 利用后续遍历的方式可知X 结点的后继是其父结点, 即其右线索指向的是父结点。
时间占整个CPU 时间百