2017年延安大学数学与计算机科学学院812数据结构与程序设计考研冲刺密押题
● 摘要
一、选择题
1． 下列选项中，能缩短程序执行时间的措施是（ ）。
I. 提高CPU 时钟频率 II. 优化数据通路结构 III. 对程序进行编译优化 A. 仅I 和II B. 仅I 和III C. 仅II 和III D.I 、II 和III 【答案】D
【解析】一般说来，CPU 时钟频率（主频）越高，CPU 的速度就越快；优化数据通路结构，可以有效提高计算机系统的吞吐量；编译优化可得到更优的指令序列。所以I 、II 、III 都是有效措施。
2． 若用一个大小为6的数组来实现循环队列，且当前rear 和front 的值分别为0和3, 当从队列中删除一个元素，再加入两个元素后，rear ，front 的值分别为多少？（ ）
A.1和5 B.2和4 C.4和2 D.5和1 【答案】B
【解析】入队操作的主要步骤
：个后
，
加入一个后，
再加入一
删除一个后
，
出队操作的主要步骤
：
3． n 个顶点的无向图的邻接表最多有（ ）个表结点。
A.IT B.n （n-l ） C.n （n+l） D.n （n-l ）/2 【答案】B
【解析】当n 个顶点构成的无向图是无向完全图时，则每一个结点都会和其余的n-1个结点连接，从而会产生n （n-l ）个表结点。
4． 某计算机主存容量为64KB , 其中ROM 区为4KB , 其余为RAM 区，按字节编址。现要用2Kx8位的ROM 芯片和4Kx4位的RAM 芯片来设计该存储器，则需要上述规格的ROM 芯片数和RAM 芯片数分别是（ ）。
A.1、15 B.2、15 C.1、30 D.2、30 【答案】D
【解析】主存储器包括RAM 和ROM 两部分，由于ROM 区为4KB ，则RAM 区为60KB 。存储容量的扩展方法有字扩展、位扩展、字和位同时扩展三种。选用2Kx8位的ROM 芯片，只需/4*2采用2片芯片进行字扩展便可得到4KB 的ROM 区；选用4Kx4位的RAM 芯片，需采用（60）片芯片进行字和位同时扩展便可得60KB 的RAM 区。
5． 在下面的程序段中，对x 的赋值语句的时间复杂度为（ ）
【答案】C 【解析】两个循环嵌套，那么语句x :=x＋l :
则被执行了次。
6． 下列关于AOE 网的叙述中，不正确的是（ ）。
A. 关键活动不按期完成就会影响整个工程的完成时间 B. 任何一个关键活动提前完成，那么整个工程将会提前完成 C. 所有的关键活动提前完成，那么整个工程将会提前完成 D. 某些关键活动若提前完成，那么整个工程将会提前完成 【答案】B
【解析】关键路径是指从有向图的源点到汇点的最长路径。某些关键活动提前完成，那么整个工程将会提前完成，但不是任何一个关键活动提前完成，就能保证整个工程将会提前完成。
7． 对如下所示的有向图进行拓扑排序，得到的拓扑序列可能是（ ）
A.
B.
C.
D.
【答案】D
【解析】拓扑排序方法如下：
（1）从有向图中选择一个没有前驱（即入度为0）的顶点并且输出它； （2）从图中删去该顶点，并且删去从该顶点发出的全部有向边； （3）重复上述两步，直到剩余的网中不再存在没有前趋的顶点为止。 对于此有向图进行拓扑排序所有序列为：
8． 以太网的MAC 协议提供的是（ ）。
A. 无连接不可靠服务 B. 无连接可靠服务 C. 有连接不可靠服务 D. 有连接可靠服务 【答案】A 。
【解析】考查以太网MAC 协议，考虑到局域网信道质量好，以太网采取了两项重要的措施以使通信更简洁：①采用无连接的工作方式；②不对发送的数据帧进行编号，也不要求对方发回确认。因此，以太网提供的服务是不可靠的服务，即尽最大努力交付，差错的纠正由高层完成。
9． 设哈希表
长哈希函
数表中已有4个结点
：
其余地址为空，如用二次探测
再哈希法解决冲突，关键字为49的结点的地址是（ ）。
【答案】D
【解析】15，38，61，84用哈希函数为5，发生冲突，用二次探测再散列法解决冲突：
仍然发生冲突。
仍然发生冲突。
不再发生冲突。
10．若X 是二叉中序线索树中一个有左孩子的结点，且X 不为根，则X 的前驱为（ ）。
A.X 的双亲
B.X 的右子树中最左的结点 C.X 的左子树中最右的结点
和所以选D
计算后得地址：4，5，6，7。49计算后
相关内容
相关标签