(D) 不能确定
10 设一组初始记录关键字序列为(45，80，55，40，42，85)，则以第一个记录关键字45为基准而得到一趟快速排序的结果是（ ）。 (A) 40，42，45，55，80，83 (B) 42，40，45，80，85，88 (C) 42，40，45，55，80，85 (D) 42，40，45，85，55，80
二、填空题(共30分)
1. 设有一个顺序共享栈S[0：n-1]，其中第一个栈项指针top1的初值为-1，第二个栈顶指针top2的初值为n，则判断共享栈满的条件是____________________。
2. 在图的邻接表中用顺序存储结构存储表头结点的优点是____________________。
3. 设有一个n阶的下三角矩阵A，如果按照行的顺序将下三角矩阵中的元素（包括对角线上元素）存放在n(n+1)个连续的存储单元中，则A[i][j]与A[0][0]之间有_______个数据元素。
4. 栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为__________表；队列的插入和删除运算分别在队列的两端进行，先进队列的元素必定先出队列，所以又把队列称为_________表。
5. 设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF，则该二叉树的前序遍历序列为___________，中序遍历序列为___________，后序遍历序列为___________。
6. 设一棵完全二叉树有128个结点，则该完全二叉树的深度为________，有__________个叶子结点。 7. 设有向图G的存储结构用邻接矩阵A来表示，则A中第i行中所有非零元素个数之和等于顶点i的________，第i列中所有非零元素个数之和等于顶点i的__________。
8. 设一组初始记录关键字序列(k1，k2， ，kn)是堆，则对i=1，2， ，n/2而言满足的条件为_______________________________。
9. 下面程序段的功能是实现冒泡排序算法，请在下划线处填上正确的语句。 void bubble(int r[n]) {
for(i=1;i<=n-1; i++)
{
for(exchange=0,j=0; j<_____________;j++)
if (exchange==0) return； }
}
10. 下面程序段的功能是实现二分查找算法，请在下划线处填上正确的语句。 struct record{int key; int others;}; int bisearch(struct record r[ ], int k) {
int low=0,mid,high=n-1; while(low<=high) {
________________________________;
if(r[mid].key==k) return(mid+1); else if(____________) high=mid-1;else low=mid+1; }
return(0); }
三、应用题(24分)
1. 设某棵二叉树的中序遍历序列为DBEAC，前序遍历序列为ABDEC，要求给出该二叉树的的后序遍历序列。
2. 设无向图G（如右图所示），给出该图的最小生成树上边的集合并计算最小生成树各边上的权值之和。
3. 设一组初始记录关键字序列为(15，17，18，22，35，51，60)，要求计算出成功查找时的平均查找长度。
4. 设散列表的长度为8，散列函数H(k)=k mod 7，初始记录关键字序列为(25，31，8，27，13，68)，要求分别计算出用线性探测法和链地址法作为解决冲突方法的平均查找长度。
四、算法设计题(16分)
1． 设计判断两个二叉树是否相同的算法。 2． 设计两个有序单链表的合并排序算法。
数据结构试卷（五）参考答案
一、选择题 1．A 2．B 6．B 7．B
二、填空题
1. top1+1=top2
2. 可以随机访问到任一个顶点的简单链表 3. i(i+1)/2+j-1 4. FILO，FIFO
5. ABDECF，DBEAFC，DEBFCA 6. 8，64
7. 出度，入度
8. ki<=k2i && ki<=k2i+1 9. n-i，r[j+1]=r[j]
3．A 8．B 4．A 9．C 5．D 10．C
三、应用题
1. DEBCA
2. E={(1,5),(5,2),(5,3),(3,4)},W=10 3. ASL=(1*1+2*2+3*4)/7=17/7 4. ASL1=7/6，ASL2=4/3 四、算法设计题
1. 设计判断两个二叉树是否相同的算法。
typedef struct node {datatype data; struct node *lchild,*rchild;} bitree; int judgebitree(bitree *bt1,bitree *bt2)
{
if (bt1==0 && bt2==0) return(1);
else if (bt1==0 || bt2==0 ||bt1->data!=bt2->data) return(0);
else return(judgebitree(bt1->lchild,bt2->lchild)*judgebitree(bt1->rchild,bt2->rchild)); }
2. 设计两个有序单链表的合并排序算法。 void mergelklist(lklist *ha,lklist *hb,lklist *&hc) {
lklist *s=hc=0; while(ha!=0 && hb!=0)
if(ha->data<hb->data){if(s==0) hc=s=ha; else {s->next=ha; s=ha;};ha=ha->next;} else {if(s==0) hc=s=hb; else {s->next=hb; s=hb;};hb=hb->next;} if(ha==0) s->next=hb; else s->next=ha; }
数据结构试卷（六）
一、选择题(30分) 1． 设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为（ (A) 20 (B) 30 (C) 40 (D) 45
2．执行一趟快速排序能够得到的序列是（ ）。 (A) [41，12，34，45，27] 55 [72，63] (B) [45，34，12，41] 55 [72，63，27] (C) [63，12，34，45，27] 55 [41，72]
(D) [12，27，45，41] 55 [34，63，72]
3．设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（ ）。 (A) head==0 (B) head->next==0 (C) head->next==head (D) head!=0
4．时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是（ ）。
(A) 堆排序 (B) 冒泡排序 (C) 希尔排序 (D) 快速排序
5．设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（ ）。 (A) 空或只有一个结点 (B) 高度等于其结点数 (C) 任一结点无左孩子 (D) 任一结点无右孩子
6．一趟排序结束后不一定能够选出一个元素放在其最终位置上的是（ ）。 (A) 堆排序 (B) 冒泡排序 (C) 快速排序 (D) 希尔排序
7．设某棵三叉树中有40个结点，则该三叉树的最小高度为（ ）。 。 ）
8．顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（ ）。 (A) O(n) (B) O(n2)(C) O(n1/2) (D) O(1og2n) 9．二路归并排序的时间复杂度为（ ）。 (A) O(n) (B) O(n2)(C) O(nlog2n) (D) O(1og2n) 10. 深度为k的完全二叉树中最少有（ ）个结点。