2018年中国农业科学院天津环保所808数据结构考研强化五套模拟题
● 摘要
一、单项选择题
1． n 个结点的完全有向图含有边的数目（ ）。
A.n*n
B.n(n+1)
C.n/2
D.n*(n－1)
【答案】D
【解析】在有向图中，如果任意两个顶点之间都存在边，则称为有向完全图。顶点个数为n 的无向图，最多有条边。如是有向图，需要在无向图的最多边的基础上乘以2，则为n(n－1) 。
2． 对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（ ）。
A.(2，5，12，16)26(60，32，72)
B.(5，16，2，12)28(60，32，72)
C.(2，16，12，5)28(60，32，72)
D.(5，16，2，12)28(32，60，72)
【答案】B
【解析】快速排序是将待排记录分割成独立的两部分，其中一部分的关键字均比另一部分记录的关键字小。
第一次比较:28比72小，不交换;
第二次比较:28比5大，交换，此时为(5，16，32，12，60，2，28，72) ;
第三次比较:16比28小，不交换；
第四次比较:32比28大，交换，此时为(5，16，28，12，60，2，32，72) ;
第五次比较:28比2大，交换，此时为(5，16，2，12，60，28，32，72) ;
第六次比较:28比12大，不交换；
第七次比较:28比60小，交换，此时为(5，16，2，12，28，60，32，72) ;
一次划分结束。
3． ARP 协议的功能是（ ）。
A. 根据IP 地址查询MAC 地址
B. 根据MAC 地址查询IP 地址
C. 根据域名查询IP 地址
D. 根据IP 地址查询域名
【答案】A 。
【解析】ARP 协议是网络层协议, 因此只能和传输层和数据链路层有关系, 从这一点出发, 域名是应用层的范畴, 选项C 和D 是不正确的, 根据MAC 地址查询IP 地址是RARP 协议的功能, 因此进而得出正确答案是A 。
4． 下列介质访问控制方法中, 可能发生冲突的是（ ）
A.CDMA
B.CSMA
C.TDMAC
D.FDMA
【答案】B
【解析】介质访向控制协议中能够发生冲突的是CSMA 协议, 答案为B 。
5． 若一棵二叉树的前序遍历序列和后序遍历序列分别为1, 2, 3, 4和4, 3, 2, 1, 则该二叉树的中序遍历序列不会是（ ）。
A.1, 2, 3, 4
B.2, 3, 4, 1
C.3, 2, 4, 1
D.4, 3, 2, 1
【答案】C
【解析】题目中的二叉树的先序序列和后序序列正好相反, 这样的二叉树每层只有一个结点。该二叉树的形态如下图所示。
从左至右, 这8棵二叉树的中序序列分别为:
(1)4, 3, 2, 1,
(2)3, 4, 2, 1
(3)2, 4, 3, 1
(4)2, 3, 4, 1
(5)1, 4, 3, 2
(6)1, 3, 4, 2
(7)1, 2, 4, 3
(8)1, 2, 3, 4
显然选项C 的中序序列不会出现。
6． 若数据元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是（ ）.
A.. 起泡排序
B. 插入排序
C. 选择排序
D. 二路归并排序
【答案】B
【解析】经过两趟排序后，A 项起泡排序的结果是两个最小或最大的元素放到了序列的最终位置；B 项插入排序的结果是前三个数有序即可；C 项选择排序结果是两个最小的元素在最前面按顺序排好；D 项二路归并排序的结果是长度为4的子序列有序，即前4个数排好序，接下来的4个数排好序. 显然题目中的元素序列只能是插入排序第二趟排序后的结果，因此，B 项正确.
7． 某字长为8位的计算机中, 已知整型变量x 、y 的机器数分别为
, A.11000000
B.00100100
C.10101010
D. 溢出
【答案】A
【解析】将x 左移一位, y 右移一位, 两个数的补码相加的机器数为11000000, 故答案选择A 。
8． 设计一个判别表达式中左、右括号是否配对出现的算法，采用（ ）数据结构最佳。
A. 线性表的顺序存储结构
B. 队列
C. 线性表的链式存储结构
D. 栈
【答案】D
【解析】用栈更合适，如果是左括号，进栈；如果是右括号，看栈顶是不是左括号，如果是，则左括号出栈；否则不配对(可以直接结束算法) 。处理完所有符号号，如果栈为空则配对成功。
9． 采用指令Cache 与数据Cache 分离的主要目的是（ ）
A. 减低Cache 的缺失损失
B. 提高Cache 的命中率
C. 减低CPU 平均访问时间
D. 减少指令流水线资源冲突
【答案】D
【解析】指令流水线不会断流, 预取过来的都是指令
。若整型变量, 则z 的机器数为（ ）