4. S={15，10，25，23，45，35，17，27，22，33}依次按散列方式存入 数组 a[]中，其中散列函数为 H(key)=key%10，冲突处理的方法是线性探测再 散列。将下面数组 a 存储各元素的位置示意图填写完整。（10 分）
0123456789
数组 a
5. 使用 Prim 算法，针对右图画出构造最小生成树的 过程图示（10 分）
while( ( 2 ) ) j--;
if(i<j) {
(3) ;
( 4 ) ;}
while( ( i<j ) && ( a[i] <=x ) ) i++;
if( i<j ) { a[j]=a[i]; j--; }
}
(5) ;
qksort( a, L , j-1 );
qksort( a, j+1, H );
是
。
3. 有 n 个元素的顺序型循环队列，其队首和队尾指针分别为 f 和 r，则该队列
中的元素个数有
个。
4. 表达式 a+b*(c-d)的前缀表达式为
。
5. 对半带宽为 b 的带状矩阵（也称 2*b+1 对角阵），其特点是：对矩阵元素 aij，
若它满足
，则 aij=0。
二、程序填空（每小题 10 分，共 20 分）
江西师范大学计算机科学技术专业
09-10 第 1 学期《数据结构》期末考试试题 B
参考答案
课程代号：262208 注意事项：请将答案全部写到答题纸上，并注明题号！
一、填空题（每小题 2 分，共 10 分）
1. 终止性/或有穷性
2. O(logn) 3. (r+n-f) % n
4. +a*b-cd 5. |i-j|>b
gb、e、f、c、Fra bibliotek、g；中序遍历输出序列为：e、f、b、a、c、g、d； 画出该树的后序二叉穿线树。（10 分）
4. 给定如下<字母，频度>组合：<a，12>，<b，3>，<c，4>，<d，56>，<e，
7>，<f，9>，<g，5>，<h，13>，<i，21>，<j，28>，解答下列问题：（10
和
。
二、程序填空（每小题 10 分，共 20 分）
1、下面代码实现对数组 a[]的快速排序,L 和 H 是数组 a 的边界（10 分）
void qksort(int a[],int L,int H){
int i, j, x;
if( ( 1 ) ) return;
i=L; j=H; x=a[i];
while( i<j ) {
渐近时间复杂度是
。
3. 表达式 a+b*(c-d)的后缀表达式为
。
4. 在关键字序列（0，2，4，6，8，10，12，14，16）中，使用折半查找方式查
找键值 14 和 15，需要的比较次数分别为
和
。
5. 有 n 个元素的顺序型循环队列，其队首和队尾指针分别为 f 和 r，从队列中删
除 1 个元素，再插入 2 个元素，其队首和队尾指针分别是
(2) ;
if (a[m]<key) return
(3) ;
}
2．下面代码创建前序线索二叉树。（10 分）
typedef struct binTreeNode{
char d; int ltag,rtag;
struct binTreeNode *l,*r;
}Btree;
/* 定义线索树结构 */
Btree *pre=NULL; /* 定义外部变量 pre */
(7) ; (8) ;
三、综合解答题（每小题 10 分，共计 50 分） 1. 给定关键字序列{12，10，13，23，14，9，22，33}，首先判断其是否是 堆。若不是，将其调整为小根堆（即根 最小的堆）。（10 分）
2. 给定如下所示的稀疏矩阵，写出其 对应的三元组表示。（10 分）
3. 已知某棵二叉树的前序遍历输出序列为：a、b、e、f、c、d、g；中序遍历 输出序列为：e、f、b、a、c、g、d；画出该树的后序二叉穿线树。（10 分）
(1,3,9),
(3,1,-3),
(3,6,14),
(4,3,24),(5,2,18),
(6,1,15),
(6,4,-7) }
注意：建议无论是以表格格式，还是以元素对
格式，都可以给满分。另外，基于从 0 开始的下 标刻画上述矩阵，也算做正确。
3. 已知某棵二叉树的前序遍历输出序列为：a、
a
b
c
e
d
f
4. 3 和 4
二、程序填空（每小题 10 分，共 20 分）
(1). L>=H (3). a[i]=a[j];
(2). ( i<j ) && ( a[j] >= x )
(4). i++;
(5). a[i]=x;
(6). (L+H)/2 (7).BS(a,key,L,m-1); (8).BS(a, key, m+1, H);
1 30
50 10
2 20
4
60
3
四、算法设计题（每小题 10 分，共 20 分）
1、给定键值按升序排列的带头结点的单链表 h1 和 h2，将其合并成升序排列的 单链表，并返回新链表的表头指针。要求利用原表的结点数据空间。
typedef struct L{ int d; struct L *next;
}LinkL; LinkL * mergeList(LinkL *h1,LinkL *h2){
/*补充完整 */
}
2、编写算法，返回二叉树中序遍历的第一个结点；
typedef struct pp{ int d; struct pp *l,*r;
}Btree; Btree* inFirstNode(Btree *t){
四、算法设计题（每小题 10 分，共 20 分）
10 0
1 30
50 10
2 20
100
4
60
3
1、给定键值按升序排列的带头结点的单链表 h1 和 h2，将其合并成降序排列的 单链表，并返回新链表的表头指针。要求利用原表的结点数据空间。
typedef struct L{ int d; struct L *next;
}
三、综合解答题（每小题 10 分，共计 50 分） 1. 依次输入键值{12，10，13，23，14，15，17，27，22，33}，画出其对应的 二叉排序树。（10 分）
2. 给定右图所示的稀疏矩阵，写出其对 应的三元组表示。（10 分）
3. 已知某棵二叉树的后序遍历输出序 列为：f、e、b、g、d、c、a；中序遍历输出序列为：e、f、b、a、c、g、d； 画出该树的后序二叉穿线树。（10 分）
1、以下代码实现折半检索，L、H 刻画在数组 a 中检索的范围。(10 分)
BS(int[] a, int key, int L, int H){
int m;
if (L>H) return -1；
m= ( 1 ) ;
if (a[m]==key) return m;
if (a[m]>key) return
}
2、以下代码实现通用的折半检索，L、H 刻画在数组 a 中检索的范围。(10 分) BS(int[] a, int key, int L, int H){ int m; if (L>H) return -1； m= ( 6 ) ; if (a[m]==key) return m;
if (a[m]>key) return if (a[m]<key) return }
4. 给定如下<字母，频度>组合：<a，12>，<b，3>，<c，4>，<d，56>，<e，
7>，<f，9>，<g，5>，<h，13>，<i，21>，<j，28>，解答下列问题：（10
分）
a. 构造对应的 Huffman 树 b. 并写出各字母的编码。
10 0 100
5. 使用 Kruskal 算法，针对右图画出构造最小生成 树的过程图示（10 分）
分）
a. 构造对应的 Huffman 树 b. 并写出各字母的编码。
a（0001）、b（000000）、 c（000001）、d（01）、 e（1000）、f（1001）、 g（00001）、h（101）、 i（001）、j（11）
56
21
12 5
38 13
34
79
5. 使用 Kruskal 算法，针对右图画出构造最小生 成树的过程图示（10 分）
if (h1->d <= h2->d) {q=h1; h1=h1->next;}
else {q=h2; h2=h2->next;}
tail->next=q; tail=q; } if (h1==NULL)
tail->next=h2; else
tail->next=h1; return h; }
2、编写算法，返回二叉树中序遍历的第一个结点； typedef struct pp{ int d; struct pp *l,*r; }Btree; Btree* inFirstNode(Btree *t){ if (bt==NULL) return; p=bt; while (p->L!=NULL) p=p->L; return p; }