16
4、将关键码DEC, FEB, NOV, OCT, JUL, SEP, AUG, APR, MAR, MAY, JUN, JAN 依次插入到一棵初始为空的AVL树中，画出每插入一个关键码后的AVL树。（6分）
套题6
一、选择题（共10题，每题2分，共20分）
1、对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( ) 。 A、（N+1）/2 B、N/2 C、N D、[（1+N）*N ]/2
2、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）(1<=i<=n+1)。
A、O(0) B、O(1) C、O(n) D、O(n2) 3、循环队列存储在数组A[0..m]中，则入队时的操作为（）。
A、rear=rear+1 B、rear=(rear+1) mod (m-1) C、rear=(rear+1) mod m D、rear=(rear+1)mod(m+1) 4、从逻辑上可以把数据结构分为（）两大类。 A、动态结构、静态结构 C、线性结构、非线性结构
B、顺序结构、链式结构 D、初等结构、构造型结构
5、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（） A、9 B、11 C、15 D、不确定 6、以下说法正确的是（）。 A、数据元素是数据的最小单位
B、数据项是数据的最大单位
D、数据结构是带有结构的数据元素的集合
C、数据结构是带有结构的各数据项的集合
7、具有12个关键字的有序表，折半查找的平均查找长度（）。
A、3.1 B、4 C、2.5 D、5 8、设无向图的顶点个数为n，则该图最多有（）条边。 A、 n-1
B、n(n-1)/2
C、n(n+1)/2
D、0
9、有关二叉树下列说法正确的是（） A、二叉树的度为2
B、一棵二叉树的度可以小于2 C、 二叉树中至少有一个结点的度为2 D、二叉树中任何一个结点的度都为2
10、下面给出的四种排序法中( )排序法是不稳定性排序法。 A、插入
B、冒泡
C、二路归并
D、堆
17
二、判断题（共10题，每题1分，共10分）
1、当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省。（） 2、完全二叉树一定存在度为1的结点。（）
3、栈和队列都是线性表，只是在插入和删除时受到了一些限制。（） 4、数据的逻辑结构是指数据的各数据项之间的逻辑关系。（） 5、二叉树是一般树的特殊情形。( )
6、用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。（） 7、线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。( )
8、链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。（） 9、若输入序列为1，2，3，4，5，6，则通过一个栈可以输出序列3，2，5，6，4，1。（） 10、对于有n个结点的二叉树，其高度为log2n。( )
三、填空题（共10空，每空2分，共20分）
1、设Q[0..N-1]为循环队列，其头、尾指针分别为P和R，则队Q中当前所含元素个数为_______。 2、在单链表L中，指针p所指结点有后继结点的条件是：__ 。
3、对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为________，在给定值为x的结点后插入一个新结点的时间复杂度为________。
4、在单链表p结点之后插入s结点的操作是：___ ___ 、。 5、二叉树的第i层上最多含有结点数为 。
6、在一个无向图中，所有顶点的度数之和等于所有边数倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的倍。
7、具有N个结点的二叉树，采用二叉链表存储，共有______个空链域。
四、程序填空题和算法设计题（共4题，每题5分，共20分）
1、以下程序的功能是在一个带有头结点的单链表L中，删除第i个元素，并由e返回其值的算法,请在画线部分填上代码。（5分）
StatusListDelete_L(LinkList&L,int i,ElemType &e)
//在带头结点的单链表L中，删除第i个元素，并由e返回其值 {p=L;
j=0;
while(p->next&&j （1） ; 18 ++j; } （2） ; p->next = q->next; e=q->data; free(q); return OK; } 2、以下程序的功能是在一有序表ST中折半查找其关键字等于key的数据元素。若找到，则函数值为该元素中的位置，否则为0,请在画线部分填上代码。（5分） int Search_Bin(SSTable ST,KeyType key) { /* 在有序表ST中折半查找其关键字等于key的数据元素。若找到，则函数值为 */ /* 该元素在表中的位置，否则为0。*/ int low,high,mid; low=1; /* 置区间初值 */ high=ST.length; while(low<=high) { (1) ; if EQ(key,ST.elem[mid].key) /* 找到待查元素 */ return mid; else if LT(key,ST.elem[mid].key) (2) ; /* 继续在前半区间进行查找 */ else low=mid+1; /* 继续在后半区间进行查找 */ } return 0; /* 顺序表中不存在待查元素 */ } 3、请用递归算法写出二叉树的先序遍历算法。（5分） 4、写一算法，求带有头结点的单链表的表长。（5分） 五、操作题 if(!(p->next) ||j>i-1) return ERROR; 19 1、设一棵二叉树的前序序列为ABDGECFH，中序序列为：DGBEAFHC 。 （1）试画出该二叉树。（2）写出该二叉树的后序遍历序列。 （3）说明由二叉树的中序遍历序列和后序遍历序列是否可唯一地确定出该二叉树？ （4）说明由二叉树的前序遍历和后序遍历结果能否唯一确定一棵二叉树？（10分） 2、依次输入表(30，15，28，20，24，10，12，68，35，50，46，55)中的元素，生成一棵二叉排序树。 (1) 试画出生成之后的二叉排序树； (2) 对该二叉排序树作中序遍历，试写出遍历序列； (3) 假定每个元素的查找概率相等，试计算该二叉排序树的平均查找长度。（10分） 3、 写出对数据（49，38，65，97，76，13，27，49）进行快速排序中第一趟的序列。（5分） 4、无向图G=(V，E)，其中：V={a，b，c，d，e，f}，E={(a，b)，(a，e)，(a，c)，(b，e)，(c，f)，(f，d)，(e，d)}，写出对该图进行广度优先遍历的序列。（5分） 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 e a f d g c j h i b 5、二叉树结点数值采用顺序存储结构，如下图所示： 1) 画出上述顺序存储结构所对应的二叉树表示形式； 2) 写出前序遍历、中序遍历和后序遍历的结果； 3) 写出结点C的双亲结点、其左、右孩子分别是什么； 若此树是由森林转换而成的二叉树，请将此二叉树还原成森林。 6、关键字序列{a,b,c,d,e,f,g,h}在某段文字中出现的频率分别是0.03，0.20，0.01，0.05，0.34，0.04，0.23，0.10。 要求： (1)画出赫夫曼树；（3分） (2)依据你所做的赫夫曼树，约定左分支表示字符 ‘1’，右分支表示字符‘0’，写出它的赫夫曼编码。（3分）