数据结构答案

一、 单选题1.B 2.A 3.B 4.C 5.D 6.B 7.D 8.A 9.D 10.C 二、 填空题（每空1分，共26分）

1. 联系 图（或图结构）2. 尾 首3. top==0 4. O（1） O（n）5. 128 44 108

6. 3 3

7. 有序 n-1

6 5 5 8. 有序序列 后缀表达式（或逆波兰式） 1 5 1 9. 2n n-1 n+1

10. 2i+1 2i+2 (i-1)/2 3 2 -1 11. 开放定址法 链接法 4 5 -2 12. 快速 归并 5 1 5 三、 运算题（每题6分，共24分） 6 3 7 1. （1） ((1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7)) (3分) 图7 （2） 三元组线性表的顺序存储表示如图7示。 2. 2. 如图8所示。

3. 3. DFS：

BFS：

4. 4. 拓朴排序为： 4 3 6 5 7 2 1 四、 阅读算法（每题7分，共14分） 1. 1. (1) 判断n是否是素数（或质数） （2）O（n）

2. 2. 功能为：从初始点vi出发广度优先搜索由邻接表GL所表示的图。 五、 算法填空（8 分）

(low+high)/2 high=mid-1 low=mid+1 六、 编写算法（8分） ElemType DeleFront(LNode * & HL) {

if (HL==NULL){ cerr<<\"空表\"<exit(1); }

LNode* p=HL; HL=HL->next;

ElemType temp=p->data; delete p; return temp; }

1

图8

模拟题二参考答案

一、 单选题1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A 二、 填空题（每空1分，共26分）

1. 正确性 易读性 强壮性 高效率2. O(n) 3. 9 3 3 4. -1 3 4 X * + 2 Y * 3 / -

5. 2n n-1 n+1 6. e 2e 7. 有向无回路 8. n(n-1)/2 n(n-1)9. （12，40） （ ） （74） （23,55，63） 10. 增加1 11. O(log2n) O(nlog2n) 12. 归并 三、 运算题（每题6分，共24分） 1. 线性表为：（78，50，40，60，34，90）

011101010111011101011. 2. 邻接矩阵：01110 邻接表如图11所示：

图11

2. 3. 用克鲁斯卡尔算法得到的最小生成树为： (1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20

3. 4. 见图12 4 4 2 2 2 2 2 4 4 5 4 5 4 5 图12

8 8 3

2

3 5 8 4 四、 阅读算法（每题7分，共14分） 1. （1）查询链表的尾结点

（2）将第一个结点链接到链表的尾部，作为新的尾结点 （3）返回的线性表为（a2,a3,…,an,a1） 2. 递归地后序遍历链式存储的二叉树。 五、 算法填空（每空2分，共8 分）

2

true BST->left BST->right 六、 编写算法（8分）

int CountX(LNode* HL,ElemType x)

{ int i=0; LNode* p=HL;//i为计数器 while(p!=NULL)

{ if (P->data==x) i++; p=p->next;

}//while, 出循环时i中的值即为x结点个数 return i; }//Count

模拟题三 数据结构试题（答案） 一、单选题（每小题2分，共8分） 题 号 1 2 3 4 答 案 C D A B 二、填空题（每空1分，共32分） 1： 集合、线性、树、图；2： 数据描述、操作声名； 3： （38，56，25，60，42，74）；4： HL→next =NULL； HL=HL→next； 5： 前一个位置； n-1；6： S.stack [S.top]; HS→data;

7： 5 318： 边结点、邻接点域、权域、链域；9： 索引值域、开始位置域； 10： 10、3、3、B、I和J；11： O（log2n）、O(nlog2n);12： m 、 m - 1 三、运算题（每小题6分，共24分） 1

划分次序 划分结果 第一次 [38 24 40] 46 [56 80 95 79] 第二次 24 [38 40] 46 [56 80 95 79] 第三次 24 38 40 46 [56 80 95 79] 第四次 24 38 40 46 56 [80 95 79] 第五次 24 38 40 46 56 79 [80 95] 第六次 24 38 40 46 56 79 80 95 2、

0 1 2 3 4 5 6 7 8 9 10 11 12 78 15 03 57 45 20 31 23 36 12 查找成功的平均查找长度：ASL SUCC=14/10= 1.4 3、此二叉树的后序遍历结果是：EDCBIHJGFA 4、

图 深度优先序列 广度优先序列 邻接矩阵表示0，1，2，8，3，4，5，6，7，0，1，4，2，7，3，8，6，5，时 9 9 邻接表表示时 0，4，3，8，9，5，6，7，1，0，4，1，3，7，2，8，6，9，2 5 四、阅读算法，回答问题（每小题8分，共16分） a) 1、 该算法的输入结果是：34 91 30 45 63 78

3

b) 2、 该算法的功能是：交换二叉树的左右子树的递归算法。 五、算法填空，在画有横线的地方填写合适的内容（10分） 1、1是：（low + high）/2;

2是： Binsch(A,low,mid–1,K); 3是： Binsch(A,mid+1,high,K); 4是： -1；

六、编写算法（10分） 根据编程情况，酌情给分。 {

Lnode *P=HL; HL=NULL; While (p!=null) {

Lnode*q=p; P=p→next; q→next=HL; HL=q; } }

模拟题四数据结构试题参考答案

一、 单项选择题（本大题共15小题，每小题2分，共30分） 1．D２．Ｂ３．Ｃ４．Ｂ５．Ｄ６．Ａ７．Ｃ８，Ｄ９，Ａ10．Ｃ 11．Ｄ12．Ｃ13．Ｄ14．Ｃ15．Ｂ

二、填空题（本大题共10小题，每小题2分，共20分） 16．存储（或存储结构） 17.p－＞next－＞next18．进栈和退栈 19．12 20．a4,8 21．384 22．abefcdg 23．快速排序、堆排序、希尔排序 24．２ 25.多关键字 三、解答题（本大题共4小题，每小题5分，共20分） 26．

图1 图2

27． 28．该图图表 1 的图形

为图表一： 深度优先遍历序列为：abdce广度优先遍历序列为：abedc 29．（１）对关键字35、20、33和48进行查找的比较次数为３、２、１、１；

4

（２）平均查找长度

ASL32112955

四、算法阅读题（本大题共4小题，每小题5分，共20分）

30． ①S1=S1－>next ②s2=s2－>next

③s2(或s2!=NULL或s2&&!s1) ④s1(或s1!=NULL或s1&&!s2) ⑤return 0

31.（1）查询链表的尾结点

（2）将第一个结点链接到链表的尾部，作为新的尾结点 （3）返回的线性表为（a2,a3,…,an,a1） 32. ①(i＋1)%2(或1－i) ②Q－>rear[i]

③(Q－>rear[i]＋)%Maxsize 33.(1)Leafhead F H G D ∧ （2）中序遍历二叉树，按遍历序列中叶子结点数据域的值构建一个以Leafhead为头指针的逆序单链表（或按二叉树中叶子结点数据自右至左链接成一个链表）。

五、算法设计题（本题共10分） 34．（1）该函数的功能是：调整整数数组a[]中的元素并返回分界值i，使所

有＜x的元素均落在a[1..i]上，使所有≥x的元素均落在a[i＋1..h]上。

（2）int f(int b[],int n) 或 int f(int b[],int n) { {

int p,q； int p,q；

p=arrange(b,0,n－1,0)； p=arrange(b,0,n－1,1)； q= arrange(b,p+1,n－1,1)； q= arrange(b,0,p,0)； return q－p； return p－q； } }

数据结构试卷（一）参考答案

一、选择题1.C 2.C 3.D 4.C 5.A 6.C7.C8.B9.B10.B 二、填空题

1. (F+1) % m 2. O(n)，O(n) 3. 2n，n+1 4. s->next=p->next; s->next=s 5. n, 2e 6. m=2e 7. CBA 8. 4，16 9. i-j+1，0 10. n-1 三、应用题

1. 链式存储结构略，前序ABDEC，中序DBEAC，后序DEBCA。

2. 哈夫曼树略，WPL=78 3. (18,5,16,19,21,23)，(5，16，21，19，18，23)

h0h18h2h310h42532h568012345674. 线性探测：81025322768 链地址法：h627

5

5. 深度：125364，广度：123456，最小生成树T的边集为E={(1，4)，(1，3)，(3，5)，(5，6)，(5,6)} 四、算法设计题

1. 1. 设计判断单链表中结点是否关于中心对称算法。

typedef struct {int s[100]; int top;} sqstack; int lklistsymmetry(lklist *head) {

sqstack stack; stack.top= -1; lklist *p;

for(p=head;p!=0;p=p->next) {stack.top++; stack.s[stack.top]=p->data;} for(p=head;p!=0;p=p->next) if (p->data==stack.s[stack.top]) stack.top=stack.top-1; else return(0);

return(1); }

2. 2. 设计在链式存储结构上建立一棵二叉树的算法。

typedef char datatype;

typedef struct node {datatype data; struct node *lchild,*rchild;} bitree; void createbitree(bitree *&bt) {

char ch; scanf(\"%c\ if(ch=='#') {bt=0; return;}

bt=(bitree*)malloc(sizeof(bitree)); bt->data=ch; createbitree(bt->lchild); createbitree(bt->rchild); }

3. 3. 设计判断一棵二叉树是否是二叉排序树的算法。

int minnum=-32768,flag=1;

typedef struct node{int key; struct node *lchild,*rchild;}bitree; void inorder(bitree *bt) {

if (bt!=0)

{inorder(bt->lchild); if(minnum>bt->key)flag=0; minnum=bt->key; inorder(bt->rchild);}

}

数据结构试卷（二）参考答案 一、选择题1.D 2.B 3.C 4.A 5.A 6.C 7.B 8.C 二、填空题

1. 构造一个好的HASH函数，确定解决冲突的方法2. stack.top++，stack.s[stack.top]=x 3. 有序 4. O(n2)，O(nlog2n) 5. N0-1，2N0+N1

6. d/2 7. (31，38，54，56，75，80，55，63)8. (1，3，4，2)，(1，3，2，4) 三、应用题

1. (22，40，45，48，80，78)，(40，45，48，80，22，78) 2. q->llink=p; q->rlink=p->rlink; p->rlink->llink=q; p->rlink=q;

3. 2,ASL=91*1+2*2+3*4+4*2)=25/9 4. 树的链式存储结构略，二叉树略 5. E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)} 6. 略 四、算法设计题

1. 1. 设有一组初始记录关键字序列（K1，K2，…，Kn），要求设计一个算法能

够在O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于Ki，右半部分的每个关键字均大于等于Ki。 void quickpass(int r[], int s, int t)

6

{

int i=s, j=t, x=r[s]; while(iwhile (ix) j=j-1; if (ir[i]=x; }

2. 2. 设有两个集合A和集合B，要求设计生成集合C=A∩B的算法，其中集合

A、B和C用链式存储结构表示。

typedef struct node {int data; struct node *next;}lklist; void intersection(lklist *ha,lklist *hb,lklist *&hc) {

lklist *p,*q,*t;

for(p=ha,hc=0;p!=0;p=p->next)

{ for(q=hb;q!=0;q=q->next) if (q->data==p->data) break;

if(q!=0){ t=(lklist *)malloc(sizeof(lklist)); t->data=p->data;t->next=hc;

hc=t;}

} }

数据结构试卷（三）参考答案

一、选择题1.B 2.B 3.A 4.A 5.A 6.B7.D8.C 9.B10.D

第3小题分析：首先用指针变量q指向结点A的后继结点B，然后将结点B的值复制到结点A中，最后删除结点B。

第9小题分析：9快速排序、归并排序和插入排序必须等到整个排序结束后才能够求出最小的10个数，而堆排序只需要在初始堆的基础上再进行10次筛选即可，每次筛选的时间复杂度为O(log2n)。 二、填空题

1. 顺序存储结构、链式存储结构 2. 9，501 3. 5 4. 出度，入度 5. 0 6. e=d 7. 中序 8. 7 9 . O(1) 10. i/2，2i+1 11. (5，16，71，23，72，94，73) 12. (1，4，3，2) 13. j+1，hashtable[j].key==k 14. return(t)，t=t->rchild

第8小题分析：二分查找的过程可以用一棵二叉树来描述，该二叉树称为二叉判定树。在有序表上进行二分查找时的查找长度不超过二叉判定树的高度1+log2n。

三、算法设计题

1. 1. 设计在单链表中删除值相同的多余结点的算法。

typedef int datatype;

typedef struct node {datatype data; struct node *next;}lklist; void delredundant(lklist *&head) {

lklist *p,*q,*s;

for(p=head;p!=0;p=p->next) {

for(q=p->next,s=q;q!=0; )

if (q->data==p->data) {s->next=q->next; free(q);q=s->next;} else {s=q,q=q->next;} }

7

}

2. 2. 设计一个求结点x在二叉树中的双亲结点算法。

typedef struct node {datatype data; struct node *lchild,*rchild;} bitree; bitree *q[20]; int r=0,f=0,flag=0; void preorder(bitree *bt, char x) {

if (bt!=0 && flag==0)

if (bt->data==x) { flag=1; return;} else {r=(r+1)% 20; q[r]=bt; preorder(bt->lchild,x);

preorder(bt->rchild,x); }

}

void parent(bitree *bt,char x) {

int i;

preorder(bt,x);

for(i=f+1; i<=r; i++) if (q[i]->lchild->data==x || q[i]->rchild->data) break; if (flag==0) printf(\"not found x\\n\");

else if (i<=r) printf(\"%c\}

数据结构试卷（四）参考答案

一、选择题1．C 2．D 3．D 4．B5．C 6．A 7．B 8．A9．C 10．A 二、填空题

1. O(n2)，O(nlog2n) 2. p>llink->rlink=p->rlink; p->rlink->llink=p->rlink 3. 3 4. 2k-1 5. n/2 6. 50，51 7. m-1，(R-F+M)%M 8. n+1-i，n-I 9. (19，18，16，20，30，22) 10. (16，18，19，20，32，22) 11. A[i][j]=1

12. 等于13. BDCA 14. hashtable[i]=0，hashtable[k]=s 三、算法设计题

1. 设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。

typedef char datatype;

typedef struct node {datatype data; struct node *next;}lklist; void split(lklist *head,lklist *&ha,lklist *&hb,lklist *&hc) {

lklist *p; ha=0,hb=0,hc=0; for(p=head;p!=0;p=head) {

head=p->next; p->next=0;

if (p->data>='A' && p->data<='Z') {p->next=ha; ha=p;}

else if (p->data>='0' && p->data<='9') {p->next=hb; hb=p;} else {p->next=hc; hc=p;}

} }

2. 设计在链式存储结构上交换二叉树中所有结点左右子树的算法。

typedef struct node {int data; struct node *lchild,*rchild;} bitree; void swapbitree(bitree *bt) {

bitree *p;

8

if(bt==0) return;

swapbitree(bt->lchild); swapbitree(bt->rchild); p=bt->lchild; bt->lchild=bt->rchild; bt->rchild=p; }

3. 在链式存储结构上建立一棵二叉排序树。

#define n 10

typedef struct node{int key; struct node *lchild,*rchild;}bitree; void bstinsert(bitree *&bt,int key) { if (bt==0){bt=(bitree *)malloc(sizeof(bitree)); bt->key=key;bt->lchild=bt->rchild=0;}

else if (bt->key>key) bstinsert(bt->lchild,key); else bstinsert(bt->rchild,key); }

void createbsttree(bitree *&bt) {

int i;

for(i=1;i<=n;i++) bstinsert(bt,random(100)); }

数据结构试卷（五）参考答案

一、选择题1．A2．B3．A4．A5．D6．B7．B8．B9．C10．C 二、填空题

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] 10. mid=(low+high)/2，r[mid].key>k 三、应用题

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->datadata){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; }

9

数据结构试卷（六）参考答案

一、选择题1D2A3A4A5D 6D7B8A9C10B 11C12A13B14D15B

二、判断题1．错2．对3．对4．对5．错6．错7．对 8．错9．对10．对 三、填空题

1. O(n) 2. s->next=p->next; p->next=s 3. (1，3，2，4，5) 4. n-1 5. 129 6. F==R 7. p->lchild==0&&p->rchild==0 8. O(n2) 9. O(nlog2n)， O(n) 10. 开放定址法，链地址法 四、算法设计题

1. 1. 设计在顺序有序表中实现二分查找的算法。

struct record {int key; int others;}; int bisearch(struct record r[ ], int k) {

int low=0,mid,high=n-1; while(low<=high) {

mid=(low+high)/2;

if(r[mid].key==k) return(mid+1); else if(r[mid].key>k) high=mid-1; else low=mid+1;

}

return(0); }

2. 2. 设计判断二叉树是否为二叉排序树的算法。 int minnum=-32768,flag=1;

typedef struct node{int key; struct node *lchild,*rchild;}bitree; void inorder(bitree *bt) { if (bt!=0) {inorder(bt->lchild); if(minnum>bt->key)flag=0; minnum=bt->key;inorder(bt->rchild);} }

3. 3. 在链式存储结构上设计直接插入排序算法

void straightinsertsort(lklist *&head) {

lklist *s,*p,*q; int t;

if (head==0 || head->next==0) return;

else for(q=head,p=head->next;p!=0;p=q->next) {

for(s=head;s!=q->next;s=s->next) if (s->data>p->data) break; if(s==q->next)q=p;

else{q->next=p->next; p->next=s->next; s->next=p;

t=p->data;p->data=s->data;s->data=t;}

} }

数据结构试卷（七）

一、选择题1．B2．B3．C4．B 5．B6．A7．C8．C9．B 10．D

二、判断题1．对2．对3．对4．对5．对6．对7．对8．错 9错10．错 三、填空题

1. s->left=p，p->right 2. n(n-1)，n(n-1)/2 3. n/2

4. 开放定址法，链地址法 5. 14 6. 2h-1，2h-1

10

7. (12，24，35，27，18，26) 8. (12，18，24，27，35，26) 9. 5 10. i1. 设计在链式结构上实现简单选择排序算法。

void simpleselectsorlklist(lklist *&head) {

lklist *p,*q,*s; int min,t;

if(head==0 ||head->next==0) return; for(q=head; q!=0;q=q->next) {

min=q->data; s=q;

for(p=q->next; p!=0;p=p->next) if(min>p->data){min=p->data; s=p;} if(s!=q){t=s->data; s->data=q->data; q->data=t;} } }

2. 设计在顺序存储结构上实现求子串算法。

void substring(char s[ ], long start, long count, char t[ ]) {

long i,j,length=strlen(s);

if (start<1 || start>length) printf(\"The copy position is wrong\"); else if (start+count-1>length) printf(\"Too characters to be copied\"); else { for(i=start-1,j=0; i3. 设计求结点在二叉排序树中层次的算法。

int lev=0;

typedef struct node{int key; struct node *lchild,*rchild;}bitree; void level(bitree *bt,int x) {

if (bt!=0)

{lev++; if (bt->key==x) return; else if (bt->key>x) level(bt->lchild,x); else level(bt->rchild,x);}

}

数据结构试卷（八）参考答案

一、选择题1．C2．C3．C4．B5．B6．C 7．B8．C9．A 10．A

二、判断题1．对2．错3．对4．错5．错6．对7．对 8．对9．对10．对 三、填空题

1. (49，13，27，50，76，38，65，97)

2. t=(bitree *)malloc(sizeof(bitree))，bstinsert(t->rchild,k)

3. p->next=s 4. head->rlink，p->llink 5. CABD 6. 1，16 7. 0 8. (13，27，38，50，76，49，65，97) 9. n-1 10. 50 四、算法设计题

1. 设计一个在链式存储结构上统计二叉树中结点个数的算法。

void countnode(bitree *bt,int &count) {

if(bt!=0)

{count++; countnode(bt->lchild,count); countnode(bt->rchild,count);} }

2. 设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。

11

typedef struct {int vertex[m]; int edge[m][m];}gadjmatrix;

typedef struct node1{int info;int adjvertex; struct node1 *nextarc;}glinklistnode; typedef struct node2{int vertexinfo;glinklistnode *firstarc;}glinkheadnode; void adjmatrixtoadjlist(gadjmatrix g1[ ],glinkheadnode g2[ ]) {

int i,j; glinklistnode *p;

for(i=0;i<=n-1;i++) g2[i].firstarc=0; for(i=0;i<=n-1;i++) for(j=0;j<=n-1;j++) if (g1.edge[i][j]==1) {

p=(glinklistnode *)malloc(sizeof(glinklistnode));p->adjvertex=j; p->nextarc=g[i].firstarc; g[i].firstarc=p;

p=(glinklistnode *)malloc(sizeof(glinklistnode));p->adjvertex=i; p->nextarc=g[j].firstarc; g[j].firstarc=p; } }

数据结构试卷（九）参考答案

一、选择题1．A 2．A 3．A 4．C 5．D6．D 7．C 8．B 9．C 10．A11．C 12．C 13．D 14．A 15．A 二、填空题

1. p->next，s->data 2. 50 3. m-1 4. 6，8 5. 快速，堆 6. 19/7 7. CBDA 8. 6

9. (24，65，33，80，70，56，48) 10. 8

三、判断题1．错2．对3．对4．对5．错6．错7．对 8．对9．错10．对 四、算法设计题

1． 1． 设计计算二叉树中所有结点值之和的算法。

void sum(bitree *bt,int &s) {

if(bt!=0) {s=s+bt->data; sum(bt->lchild,s); sum(bt->rchild,s);} }

2． 2． 设计将所有奇数移到所有偶数之前的算法。

void quickpass(int r[], int s, int t) {

int i=s,j=t,x=r[s]; while(iwhile (ir[i]=x; }

3． 3． 设计判断单链表中元素是否是递增的算法。

int isriselk(lklist *head) {

if(head==0||head->next==0) return(1);else for(q=head,p=head->next; p!=0; q=p,p=p->next)if(q->data>p->data)

return(0);

return(1); }

12

数据结构试卷（十）参考答案

一、选择题1．A2．D3．B 4．B5．B6．D7．A8．D9．D10．C11．B12．D 二、填空题

1. 4，10 2. O(nlog2n)，O(n2) 3. n 4. 1，2 5. n(m-1)+1

6. q->next 7. 线性结构，树型结构，图型结构 8. O(n2)， O(n+e) 9. 8/3 10. (38，13，27，10，65，76，97)

11. (10，13，27，76，65，97，38) 12. 124653

13. struct node *rchild，bt=0，createbitree(bt->lchild) 14. lklist，q=p 三、算法设计题

1. 设计在链式存储结构上合并排序的算法。

void mergelklist(lklist *ha,lklist *hb,lklist *&hc) {

lklist *s=hc=0;

while(ha!=0 && hb!=0)

if(ha->datadata){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; }

2. 设计在二叉排序树上查找结点X的算法。

bitree *bstsearch1(bitree *t, int key) {

bitree *p=t;

while(p!=0) if (p->key==key) return(p);else if (p->key>key)p=p->lchild; else p=p->rchild;

return(0); }

3. 设关键字序列(k1，k2，…，kn-1)是堆，设计算法将关键字序列(k1，k2，…，kn-1，x)调整为堆。

void adjustheap(int r[ ],int n) {

int j=n,i=j/2,temp=r[j-1];

while (i>=1) if (temp>=r[i-1])break; else{r[j-1]=r[i-1]; j=i; i=i/2;} r[j-1]=temp; }

13