数据结构期末考试试题及答案

课程代号：262208

注意事项：请将答案全部写到答题纸上，并注明题号！

一、填空题（每小题2分，共10分）

1. 算法有5个基本特征。其中， 特征，程序可以不必具备。

2. 在一个具有n各结点的有序链表中插入一个新结点并保持单链表依然有序的

渐近时间复杂度是 。

3. 表达式 a+b*(c-d)的后缀表达式为 。

4. 在关键字序列（0，2，4，6，8，10，12，14，16）中，使用折半查找方式查

找键值14和15，需要的比较次数分别为 和 。

5. 有n个元素的顺序型循环队列，其队首和队尾指针分别为f和r，从队列中删

除1个元素，再插入2个元素，其队首和队尾指针分别是 和 。

二、程序填空（每小题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( iwhile( ( 2 ) ) j--; if(i( 5 ) ;

qksort( a, L , j-1 ); qksort( a, j+1, H ); }

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[mm]>key) return ( 7 ) ; if (a[mm]组合：组1，，4，，，，，，，，解答下列问问题：（10分） a. 构造对应的构的Huffmann树 b. 并写出各字并字母的编码。。 5. 使用用Kruskall算法，针针对右图画出出构造最小小生成树的过程程图示（10分） 四、算法设计题（每每小题10分，共分20分）分 5001003010100124360201、给定键键值按升序序排列的带头头结点的单单链表h1和h2，将其其合并成升升序排列的单链表，并返回新链链表的表头头指针。要求求利用原表表的结点数据据空间。 typeddef strucct L{ int d; struuct L *nnext; }LinkkL; LinkLL * mergeeList(LiinkL *h1,,LinkL **h2){ /*补充完整补 **/ } 2、编写算算法，返回回二叉树中序序遍历的第第一个结点；； typedef struct pp{ int d;

struct pp *l,*r; }Btree;

Btree* inFirstNode(Btree *t){

/*补充完整 */ }

江江西师范大学计算算机科学学技术专业 09-10第1学期期《数据据结构》期期末考试试试题A 参考考答案 课程代号号：262208 注意事项项：请将答案案全部写到到答题纸上，，并注明题题号！ 一、填空题（每小题题2分，共10分） 1. 终止止性 2..O(n) 3.abcd--*+n 4. 3和4 5. (r++2)%n和(ff+1)%n 二、程序填空（每小小题10分，共20分） (1). L>>=H (2). ( ii= x ) (3). a[i]=a[j]; (4). i+++; (5). aa[i]=x; (6). (LL+H)/2 (7).BS(a,key,L,,m-1); (8).BS(a,, key, mm+1, H);三、综合解答题（每每小题10分，共计分50分） 1. 给定定关键字序列{12，100，13，233，14，9，22，33}，首先判断断其是否是是堆。若不是是，将其调调整为小根根堆（即根最最小的堆）。（10分） 答：不是是堆。调整后后如右图所所示。 定如下所示的稀疏矩阵阵，写出其其对应2. 给定的三元组组表示。（100分） {(6,7,88),(1,2,12), (1,3,,9), (3,1,-33), (3,6,114), (4,3,244),(5,2,18), (6,1,115), (6,4,-77) } 注意：建议议无论是以以表格格式，还是以元元素对格式，都都可以给满分分。另外，基于从0开始的下标刻画上上述矩阵，也也算做正确确。 3. 已知知某棵二叉树树的前序遍遍历输出序列列为：a、abefgcdb、e、f、c、d、g；中序遍历输出序列为：e、f、b、a、c、g、d； 画出该树的后序二叉穿线树。（10分）

4. 给定如下<字母，频度>组合：，，，，，，，，，，解答下列问题：（10分）

a. 构造对应的Huffman树 b. 并写出各字母的编码。

a（0001）、b（000000）、 c（000001）、d（01）、 e（1000）、f（1001）、 g（00001）、h（101）、 i（001）、j（11）

562112534791338

5. 使用Kruskal算法，针对右图画出构造最小生成树的过程图示（10分）

023初始101003010100150436020201410134110010431100102010431222223010204

343四、算法设计题（每小题10分，共20分）

1、给定键值按升序排列的带头结点的单链表h1和h2，将其合并成升序排列的单链表，并返回新链表的表头指针。要求利用原表的结点数据空间。 typedef struct L{

int d; struct L *next; }LinkL;

LinkL * mergeList(LinkL *h1,LinkL *h2){ LinkL *h,*tail,*q; h=h1; tail=h;

h1=h1->next; h2=h2->next;

while (h1!=NULL && h2!=NULL){ 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; }

江西师范大学计算机科学技术专业 09-10第1学期《数据结构》期末考试试题B

课程代号：262208

注意事项：请将答案全部写到答题纸上，并注明题号！

一、填空题（每小题2分，共10分）

1. 算法有5个基本特征。其中， 特征，程序可以不必具备。 2. 代码段 int n=100; while(n>1) n=n/10; 的渐近时间复杂度

是 。 3. 有n个元素的顺序型循环队列，其队首和队尾指针分别为f和r，则该队列

中的元素个数有 个。 4. 表达式 a+b*(c-d)的前缀表达式为 。

5. 对半带宽为b的带状矩阵（也称2*b+1对角阵），其特点是：对矩阵元素aij，

若它满足 ，则aij=0。

二、程序填空（每小题10分，共20分）

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 ) ; if (a[m]2．下面代码创建前序线索二叉树。（10分）

typedef struct binTreeNode{ char d; int ltag,rtag; struct binTreeNode *l,*r;

}Btree; /* 定义线索树结构 */ Btree *pre=NULL; /* 定义外部变量pre */

void Visit(Btree *p){ /*实现具体线索的创建*/ if (p->l==NULL) {

p->l=pre; ( 4 ) ; }} if (pre!=NULL &&& pre->r==NULL)){ ( 5 ) ; prre->rtag==1; } } voiid creaTThreadTree(Btreee *t){/*创建线索树树*/ Btree *L,*R; if (t==NULL) reeturn; L=t->l; R=t->r;; Visit(t); ( 6 ) ; creaThreadTree((L); creaThreadTree((R); } 三、综合解答题（每每小题10分，共计分50分） 1. 依次输输入键值{12，10，13，23，144，15，17，27，22，33}，画出出其对应的二叉排序序树。（10分）分 2. 给定右图所示的的稀疏矩阵阵，写出其对对应的三元元组表示。（10分） 知某棵二叉叉树的后序遍历输出序序3. 已知列为：f、e、b、g、d、c、a；中序遍历输出序列列为：e、f、b、a、c、g、d；画出该树树的后序二叉叉穿线树。（10分） 4. S={15，10，25，23，45，35，17，27，22，33}依次按散列依列方式存入数组a[]中，其中散散列函数为为 H(key)==key%10，冲突处理的的方法是线线性探测再散列。将将下面数组a存储各元元素的位置示示意图填写写完整。（100分） 数组a 0 1 2 3 4 5 6 4 7 8 9 7 用Prim算法，针对右右图画出构构造最小生成成树的5. 使用过程图示示（10分） 四、算法设计题（每每小题10分，共分20分） 分10030101100150043602201、给定键键值按升序序排列的带头头结点的单单链表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* InLastNode(Btree* bt){ /*补充完整 */ }

江江西师范大学计算算机科学学技术专业 09-10第1学期期《数据据结构》期期末考试试试题B 参考考答案 课程代号号：262208 注意事项项：请将答案案全部写到到答题纸上，，并注明题题号！ 一、填空题（每小题题2分，共10分） 1. 终止止性/或有穷穷性 2. O(loogn) 3. (r+n-f) % n 4. +a*b-cd 55. |i-j||>b 二、程序填空（每小小题10分，共20分） (1). (LL+H)/2 (2).BS(a,key,L,,m-1); (3).BS(a,, key, mm+1, H);(4). p-->ltag=1; (55). pre-->r=p; (66). pre==t; 三、综合解答题（1 - 2题每题题5分，3 -- 5每题100分，共计40分） 1. 依次输输入键值{12，10，13，23，14，15，17，27，22，33}，按照左左子树小于等于根，右子树大于于根的规则则，画出其对应的二二叉排序树。。（10分） 2. 给定稀稀疏矩阵，写出其对应应的三元组组表示。（10分） {(6,7,8), ((1,2,12), (1,,3,9), (3,1,-33), (3,6,14),, (4,3,24), (55,2,18), (66,1,15), (66,4,-7) } 注意：建建议无论是以以表格格式式，还是以元元素对格式式，都可以给给满分。另另外，基于从0开始始的下标刻画画上述矩阵阵，也算做正正确。 a3. 已知知某棵二叉树树的后序遍遍历输出序列列为：f、e、bcb、g、d、c、a；中中序遍历输输出序列为：e、f、b、a、c、g、d；画出该该树的后序序二叉穿线树树。（10分） efgd4. S={15，10，25，23，45，35，17，27，22，33}依次按散列方式存入数组a[]中，其中散列函数为 H(key)=key%10，冲突处理的方法是线性探测再散列。将下面数组a存储各元素的位置示意图填写完整。（10分）

0 1 2 3 4 5 6 7 8 9 数组a 10 27 22 23 33 15 25 45 35 17

100100

3045. 使用Prim算法，针对右图画出构造最小生成树的过1程图示（10分）

1023初始4110501020301020203

600131003010030104122412204124233343四、算法设计题（每小题10分，共20分）

1、给定键值按升序排列的带头结点的单链表h1和h2，将其合并成降序排列的单链表，并返回新链表的表头指针。要求利用原表的结点数据空间。 typedef struct L{

int d; struct L *next; }LinkL;

LinkL * mergeList(LinkL *h1,LinkL *h2){ LinkL *h,*q;

h=h1; h1=h1->next; h2=h2->next; h->next=NULL;

while (h1!=NULL && h2!=NULL){ if (h1->d <= h2->d)

{q=h1; h1=h1->next;} else

{q=h2; h2=h2->next;}

q->next=h->next; h->next=q; }

while(h1!=NULL){

q=h1; h1=h1->next;

q->next=h->next; h->next=q; }

while(h2!=NULL){

q=h2; h2=h2->next;

q->next=h->next; h->next=q; }

return h; }

2、编写算法，返回二叉树中序遍历的最后一个结点； typedef struct pp{ int d;

struct pp *l,*r; }Btree;

Btree* InLastNode(Btree* bt){ Btree* p;

if (bt==NULL) return; p=bt;

while (p->R!=NULL) p=p->R; return p; }