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

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

模拟试题2参考答案

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

D C

C D

B B

C C

A A

二、填空题(20分)

1． 顺序存储结构 链式存储结构 2． n(n﹣1)/2 n(n﹣1) 3． 前驱结点的指针值 4． A[i/2] A[2i]

5． 在查找不成功时，静态查找只宣布查找失败，而动态查找还需要将所查找的元素插入到查找表中 6．2k﹣1 2k﹣1 三、判断题(10分) 1．√ 6．√

2．√ 7．×

3．×

8．√

4．× 9．×

5．×

10．√

四、应用题(20分) 1．参考答案：

0 1 2 3 4 5 6 7 8 9 10

22 01 46 13 67 41 53 30

2．参考答案：

森林的先序序列：1,2,3,4,5,6,7,8,9,10 森林的中序序列：2,3,4,1,6,5,8,10,9,7

1 2 6 5 3 7 4 8 9 10

3．参考答案：

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

4．参考答案：

66 27 30 27 30 27 12 27 12 27 12 27

5．参考答案：

6．参考答案： (1) 邻接矩阵：

70 12 100 30 92 35 85 66 92 35 70 12 85 50 35 12 50 66 92 70 85 30 92 50 70 35 66 85 35 30 50 66 92 70 85 30 35 50 66 70 85 92

19 14 23 01 21 66 27 83 56 0 2 3 0 0 0 0 0 3 0 0 1 0 0 0 0 0 2 1 0 2 4 0 0 0 0 0 2 0 1 2 0 0 0 0 4 1 0 0 4 0 0 0 0 2 0 0 3 0 0 0 0 0 4 3 0

50

100 100 100

100 100

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

(2) 最小生成树：

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

int search_bin(SSTable ST,int low,int high,int key){ /*对有序表ST折半查找的递归算法*/ int mid;

if (low<=high){

mid=(low+high)/2;

if(key==ST.elem[mid].key) return(mid);

else if(key

return (search_bin(ST,low,mid-1,key)); else

return (search_bin(ST,mid+1,high,key));} else return -1; /*查找失败*/ }

2．算法代码：

void inorder_thr(BiThrTree T){ BiThrTree p; while(p){

while(p->ltag==0) p=p->lchild;

printf(\访问其左子树为空的结点*/ while(p->rtag==1&&p->rchild!=NULL){ p=p->rchild;

printf(\ }

p= p->rchild; } }

3．算法代码：

int count=0;

void is_connected(ALGraph G){ int i;

for (i=1;i<=G.vexnum;i++) /*标识数组置0*/ visited[i]=0;

for (i=1;i<=G.vexnum;i++) if(!visited[i]){

DFS(G,i); /*从顶点vi出发深度优先遍历vi所在的连通分量*/ count++; } }

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

模拟试题3参考答案

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

A B

C A

B C

D B

C D

二、填空题(20分) l．15 2．6 261 3．3n﹣2 2i+j﹣3 4．24 13 5．对数阶(O(log2N)) 6．广度优先遍历 三、判断题(10分) 1．√ 6．√

2．× 7．√

3．√ 8． ×

4．×

9．×

5．×

10．√

53

四、应用题(20分)

1．参考答案：

先序遍历序列：HDACBGFE 中序遍历序列：ADCBFEGH 后序遍历序列：ABCDEFGH

2．参考答案：

a4=6

a2=7

a6=4 a9=2 a10=5

a11=5 a13=2

3．参考答案： (1) ABCDEF (2) ABCEDF (3) ABEFCD

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

(4) ACDBEF

4．参考答案：

0 1 2 3 4 5 6 7 8 9 10 11 12

11 ^ 10 23 ^ 29 55 68 ^ 01 14 27 ^ 5．参考答案：

45 70 24 30 53 90 3 12 26 37 50 61 85 100

6．参考答案：

初始序列：28,07,39,10,65,14,61,17,50,21 21前移 ： 21,07,39,10,65,14,61,17,50,[ ] 39后移 ： 21,07,[ ],10,65,14,61,17,50,39 17前移 ： 21,07,17,10,65,14,61,[ ],50,39 65后移 ： 21,07,17,10,[ ],14,61,65,50,39 14前移 ： 21,07,17,10,14,[ ],61,65,50,39

排序结果：{21,07,17,10,14} 28 {61,65,50,39} 五．算法设计题(30分) 1．算法代码：

BiTree head,tail;

void leaf_link(BiTree T ){/*编写函数将二叉树的所有叶子结点从左到右链成一个单链表head*/