2018年大连理工大学管理与经济学部810数据结构和计算机组成原理之数据结构考研仿真模拟五套题
● 摘要
一、单项选择题
1． 对一组数据(2, 12, 16, 88, 5, 10) 进行排序, 若前三趟排序结果如下:
第一趟:2, 12, 16, 5, 10, 88
第二趟:2, 12, 5, 10, 16, 88
第三趟:2, 5, 10, 12, 16, 88
则采用的排序方法可能是（ ）。
A. 起泡排序
B. 希尔排序
C. 归并排序
D. 基数排序
【答案】A
【解析】题目中所给的三趟排序过程, 显然是使用起泡排序方法, 每趟排序时从前往后依次比较, 使大值“沉底”。希尔排序的基本思想是:先对序列进行“宏观调整”, 待序列中的记录“基本有序”时再进行直接插入排序。宏观调整的方法是:通过某种规则将大的待排序序列分割为若干小的待排序序列, 再依次对这些小的序列直接插入排序。宏观调整可以多次, 每次分割的序列数逐渐增多, 而每个序列中所包含的元素数逐渐减少。归并排序的基本操作是将多个小的有序序列合并为一个大的有序序列, 然后“逐趙归并”, 直至整个序列为有序为止。基数排序是分配排序的一种, 这类排序不是通过关键字比较, 而是通过“分配”和“收集”过程来实现排序的。本题中, 很容易看出大值逐渐“沉底”, 显然使用的是起泡排序法。
2． 在体系结构中, 直接为ICMP 提供服务的协议是（ ）。
A.PPP
B.IP
C.UDP
D.TCP
【答案】B 。
【解析】首先明确ICMP 是网络层的协议, 由于服务必须是下一层向上一层提供服务的, 因此选项C 项中的UDP 和选项D 项中的TCP 属于传输层, 在网络层上面, 所以显然错误, 而PPP 协议是广域网数据链路层协议, 直接为网络层, 也就是IP 层提供服务, ICMP 协议是封装在网络层, 因此PPP 不能直接为ICMP 提供服务, ICMP 报文直接封装在IP 分组中, 故答案是B 。
3． 设n 是描述问题规模的非负整数, 下面程序片段的时间复杂度是（ ）。
A.
B.
C.
D.
【答案】A
【解析】其中, 以基本的原操作重复执行的次数作为算法的时间度量。题目中的基本运算是语
句, 设其执行时间为, 则有即。
4． 若x=103, y=-25测下列表达式采用8位定点补码运算实现时, 会发生溢出的是（ ）
A.x+y
B.-x+y
C.x-y
D.-x-y
【答案】C
答:8位定点补码能表示的数的范围为:-128~127
A 结果为78, B 结果为-128, D结果为-78都在此范围内, 只有C 结果128超过了8位定点补码能表示的数的范围, 会发生溢出
5． 引入二叉线索树的目的是（ ）。
A. 加快查找结点的前驱或后继的速度
B. 为了能在二叉树中方便地进行插入与删除
C. 为了能方便地找到双亲
D. 使二叉树的遍历结果唯一
【答案】A
【解析】二叉线索树有指向前驱和后继的指针，因此加快了查找前驱和后继结点的速度。
6． 采用指令Cache 与数据Cache 分离的主要目的是（ ）
A. 减低Cache 的缺失损失
B. 提高Cache 的命中率
C. 减低CPU 平均访问时间
D. 减少指令流水线资源冲突
【答案】D
【解析】指令流水线不会断流, 预取过来的都是指令
7． 连续存储设计时，存储单元的地址（ ）。
A. 一定连续
B. 一定不连续
C. 不一定连续
D. 部分连续，部分不连续
【答案】A
【解析】连续存储是指数据的物理存储相连，即存储单元的地址是连续的。
8． 下列线索二叉树中(用虚线表示线索) , 符合后序线索树定义的是（ ）。
【答案】D
【解析】线索二叉树利用二叉链表的空链域来存放结点的前驱和后继信息, 解题思路较简单。题中所给二叉树的后序序列为dbca 。结点d 无前驱和左子树, 左链域空, 无右子树, 右链域指向其后继结点b ; 结点b 无左子树, 左链域指向其前驱结点d ; 结点c 无左子树, 左链域指向其前驱结点b , 无右子树, 右链域指向其后继结点a 。所以正确选项为D 。
9． 对任意一棵树，设它有n 个结点，这n 个结点的度数之和为（ ）。
A.n
B.n ﹣2
C.n ﹣1
D.n ＋1
【答案】c
【解析】每个结点(除根节点外) 都是一个分支，即所有结点的度数之和等于分支个数等于总的结点数减一，即n ﹣1。
10．冯•诺依曼计算机中指令和数据均以二进制形式存放在存储器中，CPU 区分它们的依据是（ ）.
A. 指令操作码的译码结果
B. 指令和数据的寻址方式
C. 指令周期的不同阶段