第3部分 模拟试题及参考答案(5)

第3部分 模拟试题及参考答案 ·21·

if(T){

leaf_link(T->lchild);

if(!T->lchild && !T->rchild){

if(head==NULL){head=T;tail=T;} else {tail->rchild=T;tail=T;} }

leaf_link(T->rchild); } }

2．算法代码：

int delete(ALGraph graph,int i,int j){ ArcPtr q, p;

/*删除顶点vi的邻接点链表中的表结点j*/ p=graph.vertices[i].firstarc;

while(p!=NULL&&p->adjvex!=j) {q=p; p=p->nextarc;} if(p->adjvex==j)

q->netarc=p->nextarc;

/*删除顶点vj的邻接点链表中的表结点i*/ p=graph.vertices[j].firstarc;

while(p!=NULL&&p->adjvex!=i) {q=p; p=p->nextarc;} if(p->adjvex==i)

q->netarc=p->nextarc; }

3．算法代码：

void binsert_sort(SSTable st , int x){/*对有序表st进行折半查找*/ int i,j,low,high,mid;

if(x== st.elem[1].key||x== st.elem[st.length].key) return; else{

st.elem[0].key=x; low=1;

high= st.length;

while(low<=high) {/*折半查找插入位置low*/

mid=(low+high)/2; if(st.elem[0].key==st.elem[mid].key) return; else if(st.elem[0].key

for(j= st.length;j>=low;j--) st.elem[j+1] =st.elem[j];/*后移元素*/ st.elem[low]=st.elem[0]; st.length++; } }

模拟试题4参考答案

一、选择题(20分) 1~5 6~10

A B

C B

A C

B A

D D

·22· 数据结构简明教程（C语言描述）

二、填空题(20分)

1．n

2．只由空格字符组成的字符串 空格字符的个数 3．5 4．k(k+1)/2 5．3 6．7 7．12

8．二叉树无左子树 三、应用题(30分) 1．参考答案：

2．参考答案： (1)

(2) 参考答案： 9 4 3 6 4 3 6 4 3 3．参考答案：

HT的初态 HT3 0 0 0 12 0 0 0

7 0 0 0 4 0 0 0 2 0 0 0 8 0 0 0

3

52 30 68 20 50 60 70 3 4 6 5 10 7 9 8 8 10 7 6 5 8 9 5 10 7 8 5 7

9

10

的终态 3 8 0 0 12 12 0 0 7 10 0 0 4 9 0 0 2 8 0 0 8 10 0 0 第3部分 模拟试题及参考答案 ·23·

11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

11 5 9 15 20 27 47 11 0 9 5 11 4 12 3 13 9 13 2 0 0 1 8 6 7 10 11 12

4．参考答案： (1)

(2)

始点 C C C C C 终点 A B D E F

最短路径 无 无 C,D C,D,F,E C,D,F 长度 ∞ ∞ 3 11 8

5．参考答案：

(1) 哈希表a及其生成过程：

19：5 24：3 10：3，4

17：3，4，5，6 15：1

38：3，4，5，6，7 18：4，5，6，7，8 40：5，6，7，8，9

ASL=(1+1+2+4+1+5+5+5)/8=24/8=3

0 1 2 3 4 5 6 7 8 9 15 24 10 19 17 38 18 40

(2) 哈希表b及其生成过程：

19：5 24：3 10：3，4 17：3，4，2

·24· 数据结构简明教程（C语言描述）

15：1

38：3，4，2，7 18：4，5，3，8 40：5，6，4，9

ASL=(1+1+2+3+1+4+4+4)/8=20/8=2.5

0 1 2 3 4 5 6 7 8 9 15 17 24 10 19 38 18 40

6．参考答案：

A B D G

E C F

四．算法设计题(30分) 1．算法代码：

void delete(LinkList h){ LinkList q, p; p=h->next;

while(p!=NULL){ q=p;

p=p->next;

while(p->data==q->data) { q->next=p->next; free(p); p=q->next; } } }

2．算法代码：

void huffmancode(HTNode *ht, int m, char *hc[], int n){ int i,start,c,p; char cd[m]; cd[m-1]='\\0';

for(i=0;i

if(ht[p].lchild==c) cd[--start]='0'; else cd[--start]='1'; c=p;

p=ht[p].parent; }

strcpy(hc[i],&cd[start]);

第3部分 模拟试题及参考答案 ·25·

} }

3．算法代码：

int idk(ALGraph graph, int k){ ArcPtr p;

int count=0, i;

/*求邻接表中顶点k的入度*/ for (i=1;i<=graph.vexnum;++i){ p=graph.vertices[i].firstarc; while(p!=NULL) {

if(p->adjvex==k) count++; p=p->nextarc; } } }

模拟试题5参考答案

一、选择题(20分) 1~5 6~10

C D

C B

D C

A B

A B

二、填空题(20分) 1．结点*p的左右链域为空 2．深度优先 3．N﹣1 4．A[N/2]

5．sq.front=(sq.fron+1)%M 6．4，9，14，17，20 7．0 入度减1 三、应用题(30分) 1．参考答案： (1) 二叉树

A (sq.rear+1)%M = = sq.front

环

B C D E F G H I (2) 对应的森林