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

一、填空题

1． 假设一个15阶的上三角矩阵A 按行优先顺序压缩存储在一维数组B 中，则非零元素中的存储位置k ＝_____。(注:矩阵元素下标从1开始)

【答案】93

【解析】对于上三角矩阵，k ＝(i﹣l)(2n﹣i ＋2)/2＋(j﹣i) ＋l 。将i ＝j ＝9，n ＝15代入得93。

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

【答案】顺序存储结构

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

3． 高度为h 的堆中，最多有_____元素，最少有_____个元素。 【答案】

。当最后一层只有【解析】当这个堆构成的是满二叉树时，元素的个数最多，元素个数为在B

一个元素时，此时堆的元素个数最少，元素个数为。

4． 已知一循环队列的存储空间为，其中n ＞m ，队头和队尾指针分别为front 和rear ，则此循环队列判满的条件是_____ 【答案】

5． 遍历图的过程实质上是_____，广度优先遍历图的时间复杂度____；深度优先遍历图的时间复杂度_____，两者不同之处在于_____，反映在数据结构上的差别是_____。

【答案】查找顶点的邻接点的过程；0(n+e)；0(n+e)；访问顶点的顺序不同；队列和栈

【解析】广度优先遍历图使用队列这种数据结构，深度优先遍历图使用栈这种数据结构。

6． 设单链表的结点结构为(data，next) ，next 为指针域，已知指针px 指向单链表中data 为x 的结点，指针py 指向data 为y 的新结点，若将结点y 插入结点x 之后，则需要执行以下语句: _____；_____；

【答案】py ﹣＞next ＝px ﹣＞next ；px ﹣＞next ＝py

7． 克鲁斯卡尔算法的时间复杂度为_____，它对_____图较为适合。 【答案】

；边稀疏

8． 对于一个具有n 个结点的二叉树，当它为一棵_____二叉树时具有最小高度, 当它为一棵_____时，具有最大高度。

【答案】完全；只有一个叶结点的二叉树

9． 顺序查找n 个元素的顺序表，若查找成功，则比较关键字的次数最多为_____次；当使用监视哨时，若查找失败，则比较关键字的次数为_____。

【答案】n ; n+1

【解析】最多的情况就是把整个表遍历了一遍。使用监视哨时，需要多一个存储空间来存监视哨。

10．已知二维数组

【答案】1196

【解析】设元素的行标为i ，列标为j 。则它的存储位置为:l000＋[(i﹣l)*l0＋(j﹣0)]*4

中每个元素占4个单元，在按行优先方式将其存储到起始地址为1000的连续存储区域时，A[5，9]的地址是: _____。

二、单项选择题

11．设桟S 和队列Q 的初始状态为空，元素el ，e2，e3，e4，e5和e6依次通过栈S ，一个元素出栈后即进队列Q ，若6个元素出队的序列是e2，e4，e3，e6，e5，el ，则栈S 的容量至少应该是（ ）。

A.6

B.4

C.3

D.2

【答案】C

12．用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（ ）。

A. 仅修改队头指针

B. 仅修改队尾指针

C. 队头、队尾指针都可能要修改

D. 队头、队尾指针都要修改

【答案】C

【解析】用不带头结点的单链表存储队列，一般删除操作仅修改队头指针，但当队列中只有一个结点时，进行删除操作要将队头、队尾指针都修改成NULL 。

13．有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（ ）。

A.543612

B.453126

C.346521

D.234156

【答案】C

【解析】根据栈的后进先出的特点，对于C 选项中前两个元素得出栈顺序可以看出，4在5和6前先出栈，又根据入栈顺序，4在5和6后入栈，因此4出栈时，5和6必定在栈内，且5在6之上，所以出栈时5要比6先出枝。

14．在缺页处理过程中, 操作系统执行的操作可能是（ ）。

Ⅰ. 修改页表

Ⅱ. 磁盘

Ⅲ. 分配页框

A. 仅Ⅰ、Ⅱ

B. 仅Ⅱ

C. 仅Ⅲ

D. Ⅰ、Ⅱ和Ⅲ

【答案】D

【解析】首先我们要考虑的是, 为什么会发生缺页中断? 当然, 在一个采用虚拟存储管理技术的系统中, 程序是部分装入的, 还有部分是处于外存上的, 因此, 当需要访问那部分位于外存上的代码或数据时, 系统会产生缺页中断。产生缺页中断的目的是要将位于外存上的代码或数据装入内存, 据此, 缺页中断接下去所做的工作就是首先要在内存中找到空闲页框并分配给需要访问的页(若没有空闲的页面则要调用页面置换程序找到一处页面, 将该页面的内容处理掉, 或回写磁盘, 或覆盖掉, 然后将此页分配给需要访问的页) , 分配妥当以后,

缺页中断处理程序调用设备驱动程序做磁盘

, 将位于外存(一般是磁盘) 上的页面调入内存, 调入后转身去修改页表, 将页表中代表该页是否在内存的标志位(一般称为存在位或有效位、在位位) 修改为“真”, 将物理页框号填入相应位置, 若必要还需修改其它相关表项等。完成上述任务后, 缺页中断处理程序返回, 继续程序的执行。从上述过程可以看出, 涉及的相关处理非常多, 因此, 答案就显而易见了。

15．假设某计算机的存储系统由Cache 和主存组成. 某程序执行过程中访存1000次，其中访问Cache 缺失(未命中)50次，则Cache 的命中率是（ ）.

A.5% B.

C.50%

D.95%

【答案】D

【解析】Cache 的命中率H ＝N 1(N1＋N 2) ，其中N 1为访问Cache 的次数，N 2为访存主存的次数，程序总访存次数为N 1＋N 2，程序访存次数减去失效次数就是访问Cache 的次数队. 所以根据公式可得：H ＝(1000﹣50) /100＝95%.