广西工学院《数据结构与算法》考试试题2010(A)-答案解析最新

4、下列程序段中，语句（1），（2），（3）执行的次数为多少？ for (i=1; i≤m; i++) {

x ? x + 2; ............................. .(1) for (j=1; j≤n; j++) {

y ? y + 2; ........................(2) for (k=1; k≤j; j++)

z ? x + y; ...................(3) } }

5、请画出下面的无向带权图的最小生成树：

6、下面是简单选择排序算法，效率不高，请给出优化后的算法。

void SelectSort(int r[], int n) {

for ( i ? 1； i ≤ n-1； i++ )

for ( j ? i+1； j ≤ n； j++ ) if ( r[j] < r[k] )

r[i] ?? r[k]；

}

四、算法设计题（每小题15分，共30分，任选其中两题） 1、试写出计算二叉树节点数目的算法。

2、编写一个算法，从一给定的数组A[]中删除元素值在x到 y（x≤y）之间的所有

元素（假定数组中有n个元素）。算法头部约定如下：

void Delete( A[], n, x, y )

3、对于任意给定的一个线性表：L=(a1,a2,……,an),写出构造一个链表的算法。节点

类型及其算法头部约定如下：

struct node

{

ElemType data； struct node *next； }；

typedef struct node NODE；

NODE *CreateLinkList(int n)

4、设有两个有序关键字表S1，S2。S1和S2存储在数组r[low,high]中，Sl放在r［low，

mid］中，S2放在r［mid+1，high］中，如下图所示。现在要把S1，S2归并，请写出归并排序算法。算法头部约定为：void Merge(r[], low, mid, high)

low mid mid+1 high

广西工学院 2010 — 2011 学年第 1 学期考试试题 考核课程 数据结构与算法 （ A 卷）考核班级 计y091~096 学生数 215 印数 230 考核方式 闭卷 考核时间 120 分钟

参考答案

一、选择题（每小题2分，共30分）

BADAC AAADD CCCCC 二、判断题：（每小题1分，共10分） √√√√√ ××××× 三、简答题（每小题5分，共30分） 1、 带权路径长度WPL=299

100

42 58

19 23 25 33

9 10 12 13 15 18

4 5 6 7

2、 先序： A B D F K I C E H J G 或者：A D K J

中序： D B K F I A H E J C G 或者：B H G

后序： D K I F B H J E G C A 或者：D I E C

A

B C

D F E G

K I H J

3、 11，29，5，4，13，17，30，37，6，23，33 4，13，5，11，29，6，23，33，17，30，37 4，5，6， 11，17，13，23，30，29，33，37 4、（1）m （2）m*n （3）m*n*n*（n+1）/2 5、答：该图的最小生成树为：

6、答：该算法经优化后的形式如下：

void SelectSort(int r[], int n)

{

for ( i ? 1； i ≤ n-1； i++ ) {

k ? i；

for ( j ? i+1； j ≤ n； j++ ) if ( r[j] < r[k] ) k ? j； if ( k ≠ i )

r[i] ?? r[k]；

} }

四、算法设计题（每小题15分，共30分）

1、算法如下：