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

一、填空题

1． 关键码序列(Q，H ，C ，Y ，Q ，A ，M ，S ，R ，D ，F ，X) ，要按照关键码值递增的次序进行排序，若采用初始步长为4的希尔排序法，则一趟扫描的结果是_____; 若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是_____。

【答案】(Q，A ，C ，S ，Q ，D ，F ，X ，R ，H ，M ，Y) ; (F，H ，C ，D ，a ，A ，M ，Q ，R ，S ，Y ，X)

【解析】希尔排序的基本思想是:先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

快速排序(quick sort) 的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

2． 设T 是一棵结点值为整数的二叉排序树，A 是一个任意给定的整数。在下面的算法中，free_tree(T)在对二叉排序树丁进行后序遍历时释放二又排序树T 的所有结点

；

，首先在二叉排序树T 中查找值为A 的结点，根据查找情况分别进行如下

处理:(1)若找不到值为A 的结点，则返回根结点的地址(2)若找到值为A 的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A 的结点是查找树的根结点，删除后变成空的二叉树，则返NULL ; 否则返回根结点的地址。

【答案】

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

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

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

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

(2)indegree是有n 个分量的一维数组，放顶点的入度， (3)函数crein 用于记算顶点入度； (4)有三个函数回1，否则0) 。

("图有回路") ;

【答案】

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

【解析】有向图用邻接矩阵表示时，顶点i 的入度等于第i 列的所有元素之和。拓扑排序过程:首先将入度为0的顶点全部进栈。然后弹出栈顶结点，并将与弹出的顶点相连的其它顶点的入度 减一，然后判断这些顶点的入度是否为零，如果为零，继续进栈，重复这些操作，完成拓扑排序。

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

(_____)

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

6． 在顺序存储的二叉树中，编号为i 和j 的两个结点处在同一层的条件是_____。

【答案】

【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，

要加“虚结点”。

设编号为i 和j 的结点在顺序存储中的下标为s 和t , 则结点i 和j 在同一层上的条件是

。

7． 检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按_____检索。也可以按_____检索；按_____检索又可以有

检索和_____检索。

【答案】关键字；记录号；记录号；顺序；直接

8． 阅读下列程序，指出其功能，并写出空格处应填上的语句。

【答案】

【解析】本题是在哈希表中插入值为item 的元素，如该元素已在哈希表中，报告出错。

9． 起始地址为480，大小为8的块，其伙伴块的起始地址是_____；若块大小为32, 则其伙伴块的起始地址为_____; 。

【答案】480+8=488，480－32=448

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

根据上述公式起始地址就为488。

10．如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为_____。

【答案】

【解析】如果关键码是排好序的，构建二叉排序树就会形成一个单支树，它的查找效率和顺序查找效率一样为。

11．二叉树的前序序列和中序序列相同的条件是_____。

【答案】空树或任何结点至多只有右子树的二叉树