2018年西安工业大学计算机科学与工程学院819数据结构与程序设计之数据结构考研仿真模拟五套题
● 摘要
一、单项选择题
1． 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（ ）排序法。
A. 插入
B. 选择
C. 希尔
D. 二路归并
【答案】A
【解析】解此题需要熟知各种排序方法的基本思想。插入排序的基本思想是:假设待排序的记
录存放在数组中，排序过程的某一中间时刻，R
被划分成两个子区间
插入到有序区中适当的位置上。使和，其中:前一个子区间是已排好序的有序区，后一个子区间则是当前未排序的部分，不妨称其为无序区。将当前无序区的第1个记录变为新的有序区。这种方法通常称为增量法，因为它每次使有序区增加1个记录。
2． 对n 个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是（ ）。
A. 每次分区后，先处理较短的部分
B. 每次分区后，先处理较长的部分
C. 与算法每次分区后的处理顺序无关
D. 以上三者都不对
【答案】A
【解析】令递归函数为f ，第一次进行递归函数认为递归深度为1，以后从深度为n 的递归函数f 中再调用递归函数f ，此时深度为n+1。整个f 的最大深度为递归深度。
3． 某机器字长16位，主存按字节编址，转移指令采用相对寻址，由两个字节组成，第1字节为操作码字段，第2字节为相对位移量字段. 假定取指令时，每取一个字节PC 自动加1. 若某转移指令所在主存地址为2000H ，相对位移量字段的内容为06H ，则该转移指令成功转移后的目标地址是（ ）.
A.2006H
B.2007H
C.2008H
D.2009H
【解析】相对寻址方式的有效地址EA ＝(PC)＋D ，其中PC 为程序计数器，D 为相对偏移量. 主存按字节编址，取指令时，每取一个字节PC 值自动加1. 由于转移指令由两个字节组成，取出这条转移指令之后的PC 值自动加2，为2002H ，故转移的目标地址为2002H ＋06H ＝2008H.
4． 若元素a , b , c , d , e , f 依次进栈, 允许进栈、退栈操作交替进行, 但不允许连续三次进行退栈操作, 则不可能得到的出栈序列是（ ）。
A.d , c , e , b , f , a
B.c , b , d , a , e , f
C.b , c , a , e , f , d
D.a , f , e , d , c , b
【答案】D
【解析】4个选项所给序列的进、出栈操作序列分别为:
选项A.
选项B.
选项C.
选项D.
按照题目要求, 不允许连续三次进行退栈操作, 所以选项D 所给序列为不可能得到的出栈顺序。
5． 某数采用IEEE754单精度浮点数格式表示为C640 0000H, 则该数的值是（ ） A. B. C. D.
【答案】A
【解析】IEEE754单精度浮点数格式为C640 0000H表示为二进制格式为
1100 01 10 0100 0000 0000 0000 0000 0000,
转换为标准的格式为:
因此, 浮点数的值为。
6． 假定有k 个关键字互为同义词，若用线性探测法把这k 个关键字存入哈希表中，至少要进行多少次探测？（ ）
A.k －1次
B.k 次
C.k+1次 D. 次
【解析】至少探测次数
7． 关键路径是AOE 网中（ ）。
A. 从始点到终点的最短路径
B. 从始点到终点的最长路径
C. 从始点到终点的边数最多的路径
D. 从始点到终点的边数最少的路径
【答案】B
【解析】在AOE-网中有些活动可以并行地进行，所以完成工程的最短时间是从开始点到完成点的最长路径的长度(这里所说的路径长度是指路径上各活动持续时间之和，不是路径上弧的数目) 。路径长度最长的路径称作关键路径(critical path)。
8． 已知一棵完全二叉树的第6层(设根为第1层) 有8个叶结点，则该完全二叉树的结点个数最多是（ ）.
A.39
B.52
C.111
D.119
【答案】C
【解析】完全二叉树的一个特点是：叶子结点只能出现在最下层和次下层. 题目中没有说明完全二叉树的高度，首先由完全二叉树的特点确定题目中树的高度. 根据题意，一棵完全二叉树的第6层(设根为第1层) 有8个叶结点，可知此二叉树的高度是6或7. 题目中求二叉树的结点数最多的情况，因此此完全二叉树的高度为7. 由于高度为7的完全二叉树的前6层是一棵满二叉树，根据二叉树的性质2可知，高度为6的满二叉树的结点数是
目中二叉树的第6层结点数是
可达
9． 某计算机有五级中断
的顺序为
A.11110
B.01101
C.00011
D.01010
【答案】D
需要对, 则. 又根据二叉树的性质1可知，题个结点，已知有8个叶子结点，那么其余32﹣8＝24个结点。 均为分支结点，这些结点在第7层上最多有48个子结点(即叶子结点). 所以此二叉树的结点数最多, 中断屏蔽字为表示对级中断进行
屏蔽。若中断响应优先级从高到低的顺序是, 且要求中断处理优先级从高到低的中断处理程序中设置的中断屏蔽字是（ ）。 B
排除掉。【解析】由于L 2的中断处理优先级下降, 屏蔽字中需要3个0, 所以可以将选项A 、
开放, 所以相应位应该为“0”, 即为01010。