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

一、填空题

1． 以下是用类C 语言写出的算法，该算法将以二叉链表存储的二叉树中的叶结点按从左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild 域作为前链域，指向结点的直接前驱，结点的Rchild 域作为后链域，指向结点的直接后继。算法中，使用一个顺序栈stack , 栈顶指针为top ，P ，t 为辅助指针，head 为双向循环链表的头指针。试填充算法中的空格，使算法完整。

【答案】

2． 设m 、n 均为自然数，m 可表示为一些不超过n 的自然数之和，f(m，n) 为这种表示方式的数目。例f(5，3) ＝5, 有5种表示方式:3＋2, 3＋1＋1，2＋2＋1，2＋1＋1＋1，1＋1＋1＋1＋1。

①以下是该函数的程序段，请将未完成的部分填入，使之完整。

_____

_____；

}

_____；

}

，_____)

②执行程序，f(6，4) ＝_____。

【答案】①1; 1; f(m, n ﹣1) ; n ②9

3． 在一个无向图的的邻接表中，若表结点的个数是m ，则图中边的条数是_____条。 【答案】

【解析】对于无向图，在邻接表中，如果存在n 条边，则会有2n 个表结点。

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

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

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

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

成_____，若

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

5． 对单链表中元素按插入方法排序的C 语言描述算法如下，其中L 为链表头结点指针。请填充算法中标出的空白处，完成其功能。

:_____:

{_____)

(_____、

:_____；_____；p ＝u ；

【答案】(1)L﹣＞next ＝NULL //置空链表，然后将原链表结点逐个插入到有序表中

(2)p!＝NULL //当链表尚未到尾，p 为工作指针

(3)q!＝NULL //查P 结点在链表中的插入位置，这时q 是工作指针

(4)p﹣＞next ＝r ﹣＞next //将P 结点链入链表中

(5)r﹣＞next ＝p //r是q 的前驱，u 是下个待插入结点的指针

6． 顺序栈用存储数据，栈顶指针是top ，则值为x 的元素入栈的操作是_____。

【答案】if(top!＝n)data[++top]＝x ；

【解析】先判断栈是否满，如果不满，元素入栈。否则返回溢出信息。

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

【答案】1196

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

8． 二叉树由_____，_____，_____三个基本单元组成。

【答案】根结点；左子树；右子树

9． 已知t) ，LEN(t)＋1))

:

【答案】 ；；ASSIGN(S，U) ；ASSIGN(V，SUBSTR(S，INDEX(S，，求REPLACE(S，V ，m) ＝_____。

10．对于给定的元素，可以构造出的逻辑结构有_____，_____，_____，_____四种。

【答案】集合；线性结构；树形结构；图状结构(网状结构)

11．外排序的基本操作过程是_____和_____。

【答案】生成有序归并段(顺串) ；归并

12．空格串是指_____，其长度等于_____。

【答案】由空格字符(ASCII值32) 所组成的字符串；空格个数

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

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

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

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

【答案】26

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

15．索引顺序文件既可以顺序存取，也可以 _____存取。

【答案】随机

二、判断题