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

一、填空题

1． 完善算法:求KMP 算法.next 数组。

k :＝_____；next[1]:＝0；

k :＝_____；

END ；

【答案】0；next[k]

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

【答案】

；边稀疏

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

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

4． 应用prim 算法求解连通网络的最小生成树问题。

(1)针对如图所示的连通网络，试按如下格式给出在构造最小生成树过程中顺序选出的各条边。(始顶点号，终顶点号，权值

)

(2)下面是Prim 算法的实现，中间有5个地方缺失，请阅读程序后将它们补上。

的值在

第 2 页，共 56 页

中

图的顶点数，应由用户定义

用二维数组作为邻接矩阵表示

生成树的边结点

边的起点与终点

边上的权值

最小生成树定义

从顶点rt 出发构造图G 的最小生成树T , rt 成为树的根结点

初始化最小生成树

T

依次求MST 的候选边

遍历当前候选边集合

选具有最小权值的候选边

图不连通，出错处理

修改候选边集合

【答案】(1)

(2)

【解析】Prim 算法的执行类似于寻找图的最短路径的Dijkstra 算法。假设是N 上最小生成树边的集合。算法从属于 5． 已知t) ，LEN(t)＋1))

:

【答案】

的边为止。

；

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

，

属于E 中找一条代价最小的边

加入集合

是连通图

，

，v ，

直到

开始，重复执行下述操作:在所有u 属于

，同时将并入

6． 文件可按其记录的类型不同而分成两类，即 _____和_____文件。

【答案】操作系统文件；数据库

第 3 页，共 56 页

7． 数据结构是研讨数据的_____和_____以及它们之间的相互关系，并对与这种结构定义相应的_____, 设计出相应的_____。

【答案】逻辑结构；物理结构；操作(运算) ；算法

8． 对单链表中元素按插入方法排序的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 是下个待插入结点的指针

9． 实现字符串拷贝的函数strcpv 为:

(_____)

【答案】s++＝*t++或(*s++＝*t++)!＝'\0‟

10．_____；串是一种特殊的线性表，其特殊性表现在_____；串的两种最基本的存储方式是_____、两个串相等的充分必要条件是_____。

【答案】其数据元素都是字符；顺序存储；链式存储；串的长度相等且两串中对应位置的字符也相等

二、单项选择题

第 4 页，共 56 页