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

一、填空题

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

2． 当广义表中的每个元素都是原子时，广义表便成了_____。

【答案】线性表

【解析】如果每个元素都是原子，则元素不可分。此时的元素是只有一对一的关系，所以广义表变成了线性表。

3． N 个顶点的连通图用邻接矩阵表示时，该矩阵至少有_____个非零元素。 【答案】

【解析】所谓连通图一定指的是无向图，有向图会称作强连通图。连接N 个顶点，至少需要N －1条边就可以了。由于无向图的每一条边同时关联了两个顶点。因此用邻接矩阵表示时，该矩阵至少有2(N－1) 个非零元素。

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

【答案】2(n－1)

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

5． 试利用下列栈和串的基本操作完成下述填空题。

initstack(S)置S 为空栈；

push(S，X) 元素X 入栈；

pop(S)出栈操作；

gettop(S)返回栈顶元素；

sempty(S)判栈空函数；

setnull(St)置串St 为空串；

length(st)返回串st 的长度；

equal(S1，S 2) 判串S 1并S 2是否相等的函数；

concat(S1，S 2) 返回联接S 1和S 2之后的串；

sub(S，i ，1) 返回S 中第i 个字符；

empty(st)判串空函数

FUNCinvert(pre:string ；V ARexp :string) :boolean ；

{若给定的表达式的前缀式pre 正确，本过程求得和它相应的表达式exp 并返回true ，否则exp 为空串，并返回false 。已知原表达式中不包含括弧，opset 为运算符的集合。

)

_____；_____；

_____THEN_____

IF_____THEN_____

(_____，_____)；

(_____，_____)；

_____

_____THEN

注意:每个空格只填一个语句。

【答案】(1)initstack(S)//栈s 初始化为空栈

(2)setnull(exp)//串exp 初始化为空串

(3)chinopset//判取出字符是否是操作符

(4)push(s，ch)//如ch 是运算符，则入操作符栈s

(5)sempty(s)//判栈s 是否为空

(6)succ:＝false//若读出ch 是操作数且栈为空，则按出错处理

(7)exp

(8)ch//若ch 是操作数且栈非空，则形成部分中缀表达式

(9)exp

(10)gettop(s)//取栈顶操作符

(11)pop(s)//操作符取出后，出栈

(12)sempty(s)//将pre 的最后一个字符(操作数) 加入到中缀式exp 的最后

6． 下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n 个顶点

用相邻矩阵A 表示，边的权全是正数。请在下列划线处填上正确叙述。

(1)若是边，则的值等于_____，若不是边，则A(i, j) 的值是一个比任何

置边的权_____，矩阵的对角线元素全为0。 (2)构造最小生成树过程中，若顶点已包括进生成树，就把相邻矩阵的对角线元素

成_____，若

【答案】(1)已包括进生成树，就把矩阵元素置成_____。 (3)算法结束时，相邻矩阵中_____的元素指出最小生成树的_____。 边上的权值；都大的数；(2)1; 负值；(3)为负；边

7． 分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是_____算法。

【答案】起泡；快速

【解析】当初态为有序表时，冒泡排序只需要进行一趟比较即可，此时时间复杂度为O(n)，

2而快速排序算 法需要比较的次数达到最大，时间复杂度为O (n) 。

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

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

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

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

【答案】S ＝(LinkedList*)malloc(sizeof (LNode))；s ﹣＞data ＝x ；s ﹣＞next ＝r ﹣＞next ；r ﹣＞next ＝s ；r ＝s ；

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

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

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

二、单项选择题

11．当系统发生抖动(thrashing)时, 可以采取的有效措施是（ ）。

Ⅰ. 撤销部分进程

Ⅱ. 增加磁盘交换区的容量

Ⅲ. 提高用户进程的优先级

A. 仅Ⅰ

B. 仅Ⅱ

C. 仅Ⅲ

D. 仅Ⅰ、Ⅱ

【答案】A

【解析】“抖动”现象是指刚刚被换出的页很快又要被访问, 为此, 又要换出其他页, 而该页又很快被访问, 必须换入, 如此频繁地置换页面, 以致操作系统的大部分时间都花在页面置换上, 引起