2017年哈尔滨工业大学威海校区854计算机基础(含数据结构、计算机组成原理)之数据结构考研仿真模拟题
● 摘要
一、选择题
1． 某计算机的指令流水线由4个功能段组成，指令流经各功能段的时间（忽略各功能段之间的缓存时间）分别为90ns 、80ns 、70ns 和60ns , 则该计算机的CPU 时钟周期至少是（ ）。
A.90ns
B.80ns
C.70ns
D.60ns
【答案】A
【解析】对于各功能段执行时间不同的指令流水线，计算机的CPU 时钟周期应当以最长的功能段执行时间为准。
2． 某字长为8位的计算机中，y 的机器数分别为已知整型变量x 、
若整型变量
A.11000000
B.00100100
C.10101010
D. 溢出
【答案】A
y 右移一位， 【解析】将x 左移一位，两个数的补码相加的机器数为1 1000000, 故答案选择A 。
3． n 个结点的线索二叉树上含有的线索数为（ ）。
【答案】C
【解析】线索二叉树是利用二叉树的空链域加上线索，n 个结点的二叉树有n+1个空链域。
4． 主机甲与主机乙之间已建立一个TCP 连接，主机甲向主机乙发送了 3个连续的TCP 段，分别包含300字节、400字节和500字节的有效载荷，第3个段的序号为900。若主机乙仅正确接收到第1和第3个段，则主机乙发送给主机甲的确认序号是（ ）。
A.300
B.500
C.1200
D.1400
【答案】B
【解析】本题考查TCP 的确认机制，TCP 首部的序号字段是指本报文所发送的数据的第一个字节的序号。本题中首先根据第3个段的序号为900, 可以得出第2个段的序号为500, 第1个段的
第 2 页，共 55 页 则z 的机器数为（ ）
序号为200, 这里主机乙仅 正确接收了第1段和第3段，这意味着第2段丢失，需要超时重传，因此主机乙发送给主机甲的确认序号，也就是此时接收端期望收到的下一个数据包中第一个字节的序号应该是第二段的第一个字节的序号，也就是500, 因此答案是B 。
5． 栈和队的共同点是（ ）。
A. 都是先进后出
B. 都是后进先出
C. 只允许在端点处插入和删除元素
D. 没有共同点
【答案】C
【解析】栈和队列的区别是栈是先进后出的数据结构，队列是先进先出的数据结构，栈和队列的共同点是都只能在端点处插入和删除元素。
6． 有关二叉树下列说法正确的是（ ）。
A_二叉树的度为2
B. —棵二叉树的度可以小于2
C. 二叉树中至少有一个结点的度为2
D. 二叉树中任何一个结点的度都为2
【答案】B
【解析】树的度=MAX（结点1的度，结点2的度，结点3的度，... ，结点n 的度）。二叉树之所以称为二叉树，是因为二叉树中节点的度最大是2，也可以小于2。
7． 下述文件中适合于磁带存储的是（ ）。
A. 顺序文件
B. 索引文件
C. 哈希文件
D. 多关键字文件
【答案】A
【解析】磁带存储是一种顺序存储，
顺序文件
序文件适合磁带存储。
8． 下列关于图的叙述中，正确的是（ ）。
I. 回路是简单路径
II. 存储稀疏图，用邻接矩阵比邻接表更省空间
III. 若有向图中存在拓扑序列，则该图不存在回路
A. 仅 II
第 3 页，共 55 页 是记录按其在文件中的逻辑顺序依次进入存储介质而建立的，即顺序文件中物理记录的顺序和逻辑记录的顺序是一致的。因此顺
B. 仅 I 、II
C. 仅III
D. 仅 I 、III
【答案】C
【解析】第一个顶点和最后一个顶点相同的路径称为回路；序列中顶点不重复出现的路径称为简单路径；回路显然不是简单路径，所以选项I 错误。稀疏图用邻接表表示比邻接矩阵节省存储空间，稠密图适合用邻接矩阵的存储表示，所以选项II 错误。利用拓扑排序算法可以判断图中是否存在回路，即在拓扑排序输出结束后所余下的顶点都有前驱，则说明了只得到了部分顶点的拓扑有序序列，图中存在回路。所以选项III 正确。
9． 下列序列中，（ ）是执行第一趟快速排序后所得的序列。
【答案】C
【解析】快速排序将数据划分成两部分，其中一部分关键字比另一部分关键字小。
10．主机甲和乙已建立了TCP 连接，甲始终以MSS=1KB大小的段发送数据，并一直有数据发送；乙每收到一个数据段都会发出一个接收窗口为10KB 的确认段。若甲在t 时刻发生超时时拥塞窗
口为8KB , 则从t 时刻起，不再发生超时的情况下，经过10个RTT 后，甲的发送窗口是（ ）。
A.10KB
B.12KB
C.14KB
D.15KB
【答案】A
【解析】发送窗口是接受窗口和拥塞窗口的最小值，这里接收窗口总是10KB 。拥塞窗口到那个时候是大于10KB 的，取最小值。
11．某CPU 主频为1.03GHz , 采用4级指令流水线，每个段的执行需要1个时钟周期。假定CPU
执行了100条指令，在其执行过程中没有发生任何流水线阻塞，此时流水线的吞吐率为（ ）
A.
B.
C.
D.
【答案】C
【解析】采用4级流水线执行100条指令，在执行过程中共用
条指令/秒，故答案为C 。
第 4 页，共 55 页 条指令/秒 条指令/秒 条指令/秒 条指令/秒 个时钟周期。CPU 的主频是1.03GHz , 也就是说每秒钟有1.03G 个时钟周期。流水线的吞吐率
为