南昌航空工业学院2004-2005学年第二学期期末考试
课程名称：数据结构（C 语言）
A B 卷
（本试卷答卷时间为120分钟；卷面100分，占总分60%，实验及平时占40%） 一、填空题（每空1分，共15分） ⒈对于给定的n 个数据元素，可能构造出 、 、 和 四种逻辑结构。 ⒉任何一个算法的设计取决于选定的 ，而算法的实现依赖于采用的 。 ⒊在一个具有n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是 。 ⒋稀疏矩阵一般的压缩存储方法有两种，即 和 。 ⒌具有n 个顶点的有向图最多有 条边。 ⒍在无向图G 的邻接矩阵中，求第i 个结点的度的方法是 。 ⒎由树转换为二叉树，其根节点的右子树总是 。 ⒏在分块查找方法中，首先查找 ，然后再查找相应的块。 ⒐含12个结点的平衡二叉树的最大深度是 （设根结点的深度为1）。 ⒑树形选择排序通常采用 存储结构。
二、判断题（每小题1分，共10分）若正确，填入“√”，否则填入“╳”。 ⒈ ( )不带头结点的单向循环链表head 为空表的条件是head=NIL 。
⒉ ( )若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下
标互换，就完成了对该矩阵的转置。
⒊ ( )具有n个结点的满二叉树，其叶结点的个数为（n+1）/2。
⒋ ( )若一个广义表的表头为空表，则此广义表亦为空表。
⒌ ( )用一维数组存储二叉树时，总是以前序遍历存储节点。
⒍ ( )前序和中序遍历用线索树方式存储的二叉树，不必使用栈。
⒎ ( )哈夫曼树是带权路径长度最短的树，路径上权值较大的点离根较远。
⒏ ( )若一个有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑有序
序列必定存在。
⒐ ( )折半搜索适用于有序表，包括有序的顺序表和有序的链表。
⒑ ( )快速排序的速度在所有的排序方法中为最快，而且所需附加空间也最少。
三、解答下列各题（每小题6分，共30分）
⒈证明：具有n个结点的完全二叉树的深度为┗log2n┛＋1。
⒉一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来，
试求出空格处的内容，并画出该二叉树。
先序：_ B _ F _ I C E H _ G
中序：D _ K F I A _ E J C _
后序：_ K _ F B H J _ G _ A
⒊用深度优先搜索遍历下图所示的无向图，试给出以1为起点的顶点访问序列
（同一个顶点的多个邻接点，按数字顺序访问），并给出一棵最小生成树。
⒋有关键字集合：{53、17、19、61、98、75、79、63、46、49}，哈希函数：H（key）
=key mod 13，采用开放定址法中的二次探测再散列方法解决冲突。要求：
①将上述关键字填入下表；
②求等概率下查找成功时的平均查找长度；
③求装填因子。
⒌已知序列{503、87、512、61、908、170、897、275、653、462}，写出用下列
算法从小到大排序第一趟结束时的序列。
①希尔排序（第一趟排序时的增量为3）；
②快速排序（选第一个记录为枢轴）；
③堆排序（只写出初始堆）。
四、算法设计题（⒈—⒊，每小题10分，⒋小题15分，共45分）使用类C语
言写出实现算法的函数，并加以适当的注解，不必写出整个程序。
⒈设一个环上有若干个整数，现采用单向循环链表L存储该环，设计算法判断
环上任意两个相邻元素值之差的绝对值是否不超过2。
假设单向循环链表的存储结构描述如下：
struct LNODE {
float coef;
int expn;
struct LNODE *next;
};
typedef struct LNODE * LinkList;
⒉计算二叉树上单分支结点数目。假设二叉树的存储结构描述如下：
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild;*rchild; /*左右孩子指针*/
} BiTNode,*BiTree；
⒊设计算法实现按层次遍历（遍历操作定义为打印结点的data域）二叉树。二
叉树的存储结构描述同上题，在算法中可能要使用一个队列Q，其相关操作:
Iniqueue(Q) 置队列空操作
Empty(Q) 判空函数
Enqueue(Q,x) 入队列操作
Dlqueue(Q) 出队列操作
⒋设计算法在国际象棋棋盘上放置八个皇后，以使其中任意两个不能互相吃掉
对方。
