一、选择题 1．D 6．D 11．C
2．A 7．B
3．A 8．A 14．D
4．A 9．C
5．D 10．B
12．A 13．B 15．B
二、判断题 1．错 2．对 6．错 7．对
三、填空题 1. O(n) 2. 3. 4. 5. 7. 8. 9. 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;
3．对 8．错
4．对 9．对
5．错 10．对
s->next=p->next; p->next=s (1，3，2，4，5) n-1 129
p->lchild==0&&p->rchild==0 O(n2)
O(nlog2n)， O(n)
开放定址法，链地址法
6. F==R
minnum=bt->key;inorder(bt->rchild);}
}
3. 在链式存储结构上设计直接插入排序算法
void straightinsertsort(lklist *&head) {
35
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;
t=p->data;p->data=s->data;s->data=t;}
} }
p->next=s->next;
s->next=p;
36
数据结构试卷（七）
一、选择题 1．B 2．B 6．A 7．C
二、判断题 1．对 6．对
2．对 7．对
3．C 8．C
4．B 9．B
5．B 10．D
3．对 8．错 4．对 9．错 5．对 10．错
三、填空题
1. s->left=p，p->right 2. n(n-1)，n(n-1)/2
3. n/2
4. 开放定址法，链地址法 5. 14
h-1h
6. 2，2-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(\ 37 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); level(bt->rchild,x);} } 数据结构试卷（八）参考答案 一、选择题 1．C 2．C 3．C 4．B 5．B 6．C 7．B 8．C 9．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) { 38 else if(bt!=0) {count++; countnode(bt->lchild,count); countnode(bt->rchild,count);} } 2. 设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。 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 6．D 11．C 2．A 7．C 12．C 3．A 8．B 13．D 4．C 9．C 14．A 5．D 10．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 39