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、算法如下：
