四、算法阅读题（本大题共4小题，每小题5分，共20分）
30.阅读下列程序。
void f30(int A[]， int n)
{
int i,j,m;
for (i=1；i<n；i++)
for (j=0；j<i；j++)
{
m=A[i*n+j]；
A[i*n+j]=A[j*n+i]；
A[j*n+i]=m；
}
}
回答下列问题：
(1)已知矩阵B= ，将其按行优先存于一维数组A中，给出执行函数调
用f30(A，3)后矩阵B的值；
(2)简述函数f30的功能。
31.假设以二叉链表表示二叉树，其类型定义如下：
typedef struct node {
char data;
struct node*Ichild, *rchild; ∥左右孩子指针
} *BinTree；
阅读下列程序。
void f31(BinTree T)
{
InitStack(S); ∥ 初始化一个堆栈S
while (T || !StackEmpty(S)
{
while (T)
{
Push(S,T); T=T->lchild;
}
if (!StackEmpty(S))
{
T=Pop(S); printf(“%c”,T->data); T=T->rchild;
}
}
}
回答下列问题：
(1)已知以T为根指针的二叉树如图所示，
请写出执行f31(T)的输出结果：
(2)简述算法f31的功能。
32.阅读下列程序。
void f32(int A[],int n)
{
int i,j,m=l,t；
for (i=0; i<n-l&&m; i++)
{
for (j=0； j<n； j++)
printf(“%d ”,A[j])；
printf(“＼n”);
m=0：
for (j=1; j<n-i; j++)
if (A[j-1]>A[j])
{
t=A[j-l];
A[j-1]=A[j]；
A[j]=t；
m=1；
}
}
}
回答问题：
已知整型数组A[ ]={34,26,15,89,42}，写出执行函数调用f32(A,5)后的输出结果。
33.已知顺序表的表结构定义如下：
#define MAXLEN 100
typedef int KeyType;
typedef struct {
KeyType key;
InfoType otherinfo;
} NodeType；
typedef NodeType SqList[MAXLEN];
阅读下列程序。
Int f33(SqList R，NodeType X, int p, int q)
{ int m;
if (p>q) return -1;
m=(p+q)／2；
if (R[m].key==X.key) return m;
if (R[m].key>X.key) return f33(R,X,p,m-l);
else return f33(R,X,m+l,q);
}
请回答下列问题：
(1)若有序的顺序表R的关键字序列为(2,5，13,26,55,80,105)，分别写出X.key=18和X.key=26时，执行函数调用f33(R,X,0,6)的函数返回值。
(2)简述算法f33的功能。
