自考数据结构02331历年试题及答案（2009--2015个人整理版） - 图文

}

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

for (j=0； j

for (j=1; 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的功能。 五、算法设计题（本题10分）

34.假设用带头结点的单循环链表表示线性表，单链表的类型定义如下： typedef struct node { int data; struct node*next; }LinkNode，*LinkList;

编写程序，求头指针为head的单循环链表中data域值为正整数的结点个数占结点总数的比例，若为空表输出0，并给出所写算法的时间复杂度。函数原型为：

float f34(LinkList head):