数据结构07～08第二学期A卷-答案

广州大学2007-2008学年第二学期考试卷课程《数据结构》考试A卷答案

一、判断题（对打√，错打×。每题1分，共15分） × √ √ √ × × × √ √ × √ × √ √ ×

二、选择题（每题2分，共20分）

B H C D B B D C A B

三、问答题（共30分） 1、（5分，每个位置发生改变的关键字1分） 6、37、15、19、26、74、50、[75]、82、81 2、（5分，每个答案1分，说明原因2分） 答：7个顶点的无向图，最多有（7×（7-1））/2 = 21条边，即无向完全图。显然有26条边的无向连通图至少有8个顶点。至多有27个顶点，这些顶点依次连成一串。有26条边的无向非连通图，至少有9个顶点，即其中8个顶点构成连通分量，外加1个孤立顶点。

3、（6分，画出二叉树4分，先序序列2分）前序序列：ABDEGCFH A / \\ B C / \\ \\ D E F / / G H

4、（7分）

100

/ \\

57 43 / \\ / \\ 28 29(E) 20(H) 23 / \\ / \\

13(B) 15 11(F) 12(A) / \\ 6 9(G) / \\

1(C) 5(D) A：111 B：000 C：00100 D：00101 E：01 F：110 G：0011 H：10 编码可能不同。

WPL＝0.01×5＋0.05×5＋0.09×4＋0.11×3＋0.12×3＋0.13×3＋0.20×2＋0.29×2 ＝2.72

5、（7分，画出图3分，最小生成树4分）

1 5 1

6 2 1 5 4 2 1 5 3 5 3 3 4 4

6 2 3 5 6 6 5

四、算法题（第1题15分，第2题20分）

1、

Connect ( LinkList *ha , LinkList *hb , LinkList *hc , int m , int n){ //根据给定的两个链表的长度选择较短的链表并找到其尾结点。 LinkList p , q; if (mnext) p=p->next; p->next=q->next; free(q); //释放头结点 *ha=*hb=NULL; }

时间复杂度T(n)=O(min(m,n)) 2、

typedef struct Node{ ElemType data; struct Node *lchild,* rchild; }BinNode, *BinTree ;

方法一：

int NodeNum = 0 ;

void CountNode ( BinTree root ){

4 2 6 /* preorder visit bintree and count the number of leaf node */ if ( root ! = NULL ){ leafNum ++ ; CountNode ( root->lchild ) ; CountNode ( root->rchild ); } }

方法二：

int CountNode (BinTree root ){ if ( root = = NULL ) return 0 ; else return (CountNode ( root->lchild ) + CountNode ( root->rchild ) + 1) ; }