当前位置：问答库＞考研试题

一、填空题

1． 对n 个记录的表r[l..n]进行简单选择排序，所需进行的关键字间的比较次数为_____。

【答案】n （n-1）/2

【解析】第一次需要n-1次比较，第i 此需要n-i 此比较，所以共需要、n-l+n-2+...+l=n（n-l ）/2。

2． 设数组储，则元素为_____。

【答案】9174；8788

【解析】设一个元素的行标为i ，列标为j 。若以行序为主存储顺序，

则它的存储地址为

若以列序为主存储顺序，则它的存储地址为

3． 数组的存储结构采用_____存储方式。

【答案】顺序存储结构

【解析】数组本身的存储结构是线性的，也就是说它是连续存储的。

4． 模式串的next 函数值序列为_____。

【答案】01122312

5． 在单链表L 中，指针P 所指结点有后继结点的条件是_____

【答案】

【解析】指针所指节点的指针域所指向的元素非空，说明该指针所指节点有后继结点。

6． 设二维数组A 的行和列的下标范围分别为和每个元素占2个单元，按行优先顺序存储，第一个元素的存储起始位置为b ，则存储位置为

【答案】

当其值为

处的元素为_____。

的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存

的存储地址为_____；若以列序为主序顺序存储，则元素

的存储地址

【解析】令这个元素的行标为i ，列标为j 。则它的存储位置是

时，则i=2，j=3。

7． 下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空：

【答案】

【解析】通过递归算法，首先找到最高位的值，将其放到str 对应的数组中，依次反向获取从高位到地位的值，将其放到数组中，完成了将整数逆序放到一个字符数组中。

8． 已知链队列的头尾指针分别是f 和r , 则将值x 入队的操作序列是_____。

【答案】

【解析】队列采用链式存储结构，先分配一个节点的内存，然后在队尾添加该节点。

9． 在双向循环链表中，向P 所指的结点之后插入指针f 所指的结点，其操作是_____、_____、_____、_____。

【答案】

10．在哈希函数

中，P 值最好取_____。

【答案】小于等于表长的最大素数或不包含小于20的质因子的合数

【解析】在使用除留余数法时，对除数P 的选择很重要。若P 选的不好，容易产生同义词。一般情况下，可以选P 为质数或不包含小于20的质因素的合数。

11．在有n 个顶点的有向图中，每个顶点的度最大可达。

【答案】2（n-l ）

【解析】当有向图为完全连通图时每个顶点的度达到最大，出度入度均为n-1。

12．高度为4的3阶B-树中，最多有_____个关键字。

【答案】26

【解析】第4层是叶结点，1层至3层每个结点两个关键字，每个节点的关键字达到最大时，关键字最多。

二、选择题

13．对下图进行拓扑排序，可以得到不同的拓扑序列的个数是（ ）。

A.4

B.3 C.2 D.1

【答案】B

【解析】拓扑排序的步骤为：

（1）在有向图中选一个没有前驱的顶点并且输出它；

（2）从图中删除该顶点和以它为尾的弧。重复上述两步，直至全部顶点均已输出。由于没有前驱的顶点可能不唯一，所以拓扑排序的结果也不唯一。题中所给图有三个不同的拓扑棑序序列，分别为abced ，abecd ，aebcd 。

14．下列命中组合情况中，一次访存过程中不可能发生的是（ ）。

A.TLB 未命中，Cache 未命中，Page 未命中 B.TLB 未命中，Cache 命中，Page 命中 C.TLB 命中，Cache 未命中，Page 命中 D.TLB 命中，Cache 命中，Page 未命中 【答案】D

【解析】TLB （快表）和慢表（页表，Page ）构成二级存储系统，若TLB 命中，则Page 必命中。因此不可能发生的是D 选项。

15．下列选项中，不会引起指令流水线阻塞的是（ ）。

A. 数据旁路（转发） B. 数据相关 C. 条件转移 D. 资源冲突 【答案】A

【解析】由于采用流水线方式，相邻或相近的两条指令可能会因为存在某种关联，后一条指令不能按照原指定的时钟周期运行，从而使流水线断流。有三种相关可能引起指令流水线阻塞：

①结构相关，又称资源相关； ②数据相关；

③控制相关，又称指令相关，主要由转移指令引起。