2016年武汉大学测绘学院数据结构和数据库之数据结构(同等学力加试)复试笔试仿真模拟题
● 摘要
一、选择题
1． 将一棵树t 转换为孩子兄弟链表表示的二叉树h ，则t 的后序遍历是h 的（ ）。
A. 前序遍历 B. 中序遍历 C. 后序遍历 【答案】B
【解析】树的后序遍历恰好对应于二叉树的中序遍历。
2． 已知两个长度分别为m 和n 的升序链表，若将它们合并为一个长度为m+n的降序链表，则最坏情况下的时间复杂度是（ ）
A. B. C. D. 【答案】D
【解析】m 和n 是两个升序链表长度分别为m 和n ，在合并过程中最坏的情况是两个链表中的元素依次进行比较，比较的次数是m 和n 中的最大值。
3． 下列关于管道（Pipe ）通信的叙述中，正确的是（ ）
A. —个管道可实现双向数据传输 B. 管道的容量仅受磁盘容量大小限制
C. 进程对管道进行读操作和写操作都可以被阻塞 D. —个管道只能有一个读写进程或一个写进程对其操作 【答案】C
【解析】只有写进程才能对管道写入数据，读进程对管道进行读取数据，只能半双工通信，即某一时刻只能单向传输。管道为空，则读操作被堵塞，而如果有写操作对管道进行写的话那就要堵塞了。那么C 正确
4． 分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是（ ）。
【答案】C
【解析】二叉排序树：左右子树都是二叉排序树，且保证右子树都比根结点大，左子树都比
根结点小。据以上两点建立二叉排序树。
5． 设有向图G= （V ，E ），顶点集能得到的不同遍历序列个数是（ ）。
A.2 B.3 C.4 D.5
【答案】D
V={V0, VI ，V2, V3}，边
集
若从顶点V0开始对图进行深度优先遍历，则可
【解析】根据题意知有向图的结构如图所示。深度优先遍历的特点是尽可能先对纵深方向进行搜索，所以可
6． 数组通常具有的两种基本操作是（ ）。
A. 查找和修改 B. 查找和索引 C. 索引和修改 D. 建立和删除 【答案】A
【解析】数组中的元素是顺序存放的，通过下标可以很好地查找数组元素，同时通过对应的指针可以修改数组元素的值，因此数组通常具有的两种基本操作是查找和修改。根据数组的性质，数组通常具有的两种基本运算是排序和查找。
7． 系统为某进程分配了4个页框，该进程已访问的页号序列为2, 0, 2, 9, 3, 4, 2, 8, 2, 3, 8, 4, 5, 若进程要访问的下一页的页号为7，依据LRU 算法，应淘汰页的页号是（ ）。
A.2 B.3 C.4 D.8
【答案】B
【解析】LRU 置换算法是选择最近最久未使用的页面予以淘汰。进程有4个页框，题中访问过程中页框的变化如下：
序列：页框：
能得到的不同遍历序列分别是
：
淘汰：3。
8． 元素a , b , c , d , e 依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d 开头的序列个数是（ ）。
A.3 B.4 C.5 D.6
【答案】B
【解析】d 首先出栈后的状态如下图所示。
访问页号为7的页时，内存中存在的页的页号是：3、8、4和5，根据LRU 定义应淘汰的是
此时可有以下4种操作：
（1）e 进找后出栈，出梭序列为decba 。 （2）c 出找，e 进找后出栈，出找序列为dceba 。 （3）cb 出找，e 进找后出栈，出找序列为dcbea 。 （4）cba 出找，e 进找后出找，出找序列为dcbae 。
9． 下列因素中，不会影响信道数据传输速率的是（ ）
A. 信噪比 B. 频率宽带 C. 调制速率 D. 信号传播速度 【答案】D
【解析】信道数据传输速率与信噪比、频率宽度、调制速率都有关。
10．下列不是设计一个“好”的算法应考虑达到的目标是（ ）。
A. 可行的 B. 健壮的 C. 无二义性的 D. 可读性好的 【答案】A