2018年河北经贸大学计算机软件与理论807数据结构考研强化五套模拟题
● 摘要
一、单项选择题
1． 在系统总线的数据线上, 不可能传输的是（ ）。
A. 指令
B. 操作数
C. 握手(应答) 信号
D. 中断类型号型号
【答案】C
【解析】握手(应答) 信号属于通信联络控制信号应该在通信总线上传输, 不可能在数据总线上传输。而指令、操作数和中断类型码都可以在数据线上传输。
2． 下述二叉树中，哪一种满足性质:从任一结点出发到根的路径上所经过的结点序列按其关键字有序（ ）。
A. 二叉排序树
B. 哈夫曼树
C.A VL 树
D. 堆
【答案】D
【解析】堆的定义:
n 个关键字序列K 1，K 2，... ，K n 称为堆，当且仅当该序列满足如下性质(简称为堆性质) :
(1)
(2)
且且或
满足第(1)种情况的堆，称为小顶堆；满足第(2)种情况的堆，称为大顶堆。
由堆的定义可知堆可以满足上述性质。
3． 假定有k 个关键字互为同义词，若用线性探测法把这k 个关键字存入哈希表中，至少要进行多少次探测？（ ）
A.k －1次
B.k 次
C.k+1次 D.
【答案】D
第 2 页，共 70 页 次
【解析】至少探测次数
4． 某计算机有五级中断
的顺序为
A.11110
B.01101
C.00011
D.01010
【答案】D , 则。 , 中断屏蔽字为表示对级中断进行
屏蔽。若中断响应优先级从高到低的顺序是, 且要求中断处理优先级从高到低的中断处理程序中设置的中断屏蔽字是（ ）。
B
排除掉。【解析】由于L 2的中断处理优先级下降, 屏蔽字中需要3个0, 所以可以将选项A 、
需要对开放, 所以相应位应该为“0”, 即为01010。
5． 设图的邻接矩阵A 如下所示, 各顶点的度依次是（ ）
A.1, 2, 1, 2
B.2, 2, 1, 1
C.3, 4, 2, 3
D.4, 4, 2, 2
【答案】C
【解析】当图用邻接矩阵存储时, 各顶点的度是矩阵中此结点对应的横行和纵列非零元素之和。
6． 假定编译器规定int 和short 类型长度分别为32位和16位, 执行下列C 语言语句:
;
A.00007FFAH
B.0000FFFAH
C.FFFF7FFAH
D.FFFFFFFAH
【答案】B 。
X 和y 均为无符号数, 其中X 为16位, y 为32位, 将16位无符号数转化成32位无符【解析】
号数, 前面要补零。因为X=65530=FFFAH, 所以y=0000FFFAH。
7． 设有一个10阶的对称矩阵A ，采用压缩存储方式，以行序为主存储，a 11为第一元素，其存储地址为1，每个元素占一个地址空间，则a 85的地址为（ ）。
A.13
B.33
C.18
第 3 页，共 70 页 :得到y 的机器数为（ ）。
D.40
【答案】B
【解析】对于对称矩阵，为了节省存储空间，为多个相同的元素只分配一个存储空间。对于对称矩阵，元素下表之间的对应关系为:当i ＞＝j 时，k ＝i(i﹣l)/2＋j ﹣l ；当i ＜＝j 时，k ＝j(j﹣l)/2＋i ﹣l 。其中k 相当于地址空间的标号，i 为行号，j 为列号。因为第一个元素存储地址为1，所以最后计算的k 需要加1。所以a 85的存储位置为8*(8﹣1)/2＋5＝33。
8． 已知有向图G=(V，E) , 其中
,
G 的拓扑序列是（ ）。 A.
B.
C. D.
【答案】A
拓扑序列的条件:若
在顶
点 能被称为必须排【解析】设G=(V，E) 是一个具有n 个顶点的有向图，V 中顶点序列是图中的边(即从顶点。
9． 某字长为8位的计算机中, 已知整型变量x 、y 的机器数分别为
, A.11000000
B.00100100
C.10101010
D. 溢出
【答案】A 。若整型变量到有一条路径) ，则在序列中顶点之前。根据上面拓扑序列的定义，就可以得出G 的拓扑序列
是, 则z 的机器数为（ ）
【解析】将x 左移一位, y 右移一位, 两个数的补码相加的机器数为11000000, 故答案选择A 。
10．循环队列A[0..m﹣1]存放其元素值，用front 和rear 分别表示队头和队尾，则当前队列中的元素数是（ ）。
A.(rear﹣front ＋m)%m
B.rear ﹣front ＋1
C.rear ﹣front ﹣1
D.rear ﹣front
【答案】A
【解析】对于循环队列，需要深刻理解队头(font)和队尾(rear)的概念，在队头进行出队操作，在队尾进行进队操作。rear-front 可能为正也可能为负，为正时元素个数＝(rear-front)；如果为负则
第 4 页，共 70 页