第8小题分析：二分查找的过程可以用一棵二叉树来描述，该二叉树称为二叉判定树。在有序表上进行二分查找时的查找长度不超过二叉判定树的高度1+log2n。 三、算法设计题
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;} } }
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(\
else if (i<=r) printf(\}
数据结构试卷（四）参考答案
一、选择题
1．C 2．D 3．D 4．B 6．A 7．B 8．A 9．C 二、填空题
2
1. O(n)，O(nlog2n)
2. p>llink->rlink=p->rlink; p->rlink->llink=p->rlink 3. 3
k-1
4. 2 5. n/2 6. 50，51
21
5．C 10．A
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;
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)); }
数据结构试卷（五）参考答案
22
一、选择题 1．A 2．B 3．A 4．A 5．D 6．B 7．B 8．B 9．C 10．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 11. 三、应用题 12. 13.
2. DEBCA
3. E={(1,5),(5,2),(5,3),(3,4)},W=10 4. ASL=(1*1+2*2+3*4)/7=17/7 5. 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
数据结构试卷（六）参考答案
一、选择题
1．D 2．A 6．D 7．B 11．C 12．A 13．B 二、判断题
1．错 2．对 3．对
3．A 4．A 8．A 9．C 14．D 15．B 4．对 5．错
23
5．D 10．B
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. 设计在顺序有序表中实现二分查找的算法。
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. 设计判断二叉树是否为二叉排序树的算法。 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. 在链式存储结构上设计直接插入排序算法
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;} } }
数据结构试卷（七）
一、选择题
24
1．B 2．B 3．C 4．B 5．B 6．A 7．C 8．C 9．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
7. (12，24，35，27，18，26) 8. (12，18，24，27，35，26) 9. 5
10. i 四、算法设计题 1. 设计在链式结构上实现简单选择排序算法。 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(\ else if (start+count-1>length) printf(\else { for(i=start-1,j=0; i 3. 设计求结点在二叉排序树中层次的算法。 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);} } 25