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

一、填空题

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

【答案】2(n－1)

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

2． 文件由_____组成；记录由_____组成。

【答案】记录；数据项

3． 对n 个记录的表

【答案】n (n－1) /2

【解析】第一次需要n －1次比较，第i 此需要n －i 此比较，所以共需要

4． 求最短路径的Dijkstra 算法的时间复杂度为_____。 【答案】

5． 无用单元是指_____，例_____

【答案】用户不再使用而系统没有回收的结构和变量；

6． 组成串的数据元素只能是_____。

【答案】字符

7． 在单链表中设置头结点的作用是_____。

【答案】方便运算

8． 顺序存储结构是通过_____表示元素之间的关系的；链式存储结构是通过_____表示元素之间的关系的。

【答案】物理上相邻；指针

【解析】顺序存储结构是通过物理位置表示元素之间的关系的，链式存储结构通过指针表示元素之间的关系。

9． n 个顶点的有向图用邻接矩阵array 表示，下面是其拓扑排序算法，试补充完整。

注:(1)图的顶点号从0开始计；

进行简单选择排序，所需进行的关键字间的比较次数为_____。 。

(2)indegree是有n 个分量的一维数组，放顶点的入度，

(3)函数crein 用于记算顶点入度；

(4)有三个函数

回1，否则0) 。

("图有回路") ;

【答案】

其含义为数据data 入栈，出栈和测试栈是否空(不空返

【解析】有向图用邻接矩阵表示时，顶点i 的入度等于第i 列的所有元素之和。拓扑排序过程:首先将入度为0的顶点全部进栈。然后弹出栈顶结点，并将与弹出的顶点相连的其它顶点的入度

减一，然后判断这些顶点的入度是否为零，如果为零，继续进栈，重复这些操作，完成拓扑排序。

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

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

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

11．有向图G=(V, E) ，其中，用三元组表示弧及弧上的权d 。E(G)为

，则从源点0到顶点3的最短路径长度是_____，经过的中间顶点是_____。

【答案】50；4

12．设正文串长度为n ，模式串长度为m ，则串匹配的KMP 算法的时间复杂度为_____。

【答案】O(m＋n)

二、判断题

13．中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。（ ）

【答案】 √

【解析】二叉排序树是的父结点和左右子树的值的大小是确定的。

14．算法的优劣与算法描述语言无关，但与所用计算机有关。（ ）

【答案】 ×

【解析】算法的优劣和它的时间复杂度和空间复杂度有关，与算法描述语言和所用计算机都无关。

15．对长度为无穷大的广义表，由于存储空间的限制，不能在计算机中实现。（ ）

【答案】 √

【解析】可以有长度无穷大的广义表，只是在计算机中不能实现。

16．拓扑排序的有向图中，最多存在一条环路。（ ）

【答案】×

【解析】要进行拓扑排序，需要满足一个条件为:若顶点A 在序列中排在顶点B 的前面，则在图中不存在顶点B 到顶点A 的路径。如果是一个有环图，则不能满足这个条件，所以拓扑排序的有向图中不能存在环路。

17．在伙伴系统中的伙伴是指任意两块大小相同、位置相邻的内存块。（ ）

【答案】×

【解析】伙伴系统的伙伴不一定是位置相邻的内存块。

起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下:

只要符合公式的内存块都是伙伴。

18．排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（ ）

【答案】×

【解析】排序的稳定性指:假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri 在rj 之前，而在排序后的序列中，ri 仍在ij 之前，则称这种排序算法是稳定的；否则称为不稳定的。

19．无环有向图才能进行拓扑排序。（ ）

【答案】√

【解析】在图论中，由一个有向无环图的顶点组成的序列，才能进行拓扑排序。