数据结构自考2011年1月真题及答案解析

假设用带头结点的单循环链表表示线性表，单链表的类型定义如下：

typedef struct node {

int data;

struct node*next;

}LinkNode，*LinkList;

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

阅读下列程序。

回答问题：已知整型数组A[ ]={34,26,15,89,42}，写出执行函数调用f32(A,5)后的输出结果。

已知顺序表的表结构定义如下：

#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的功能。

假设以二叉链表表示二叉树，其类型定义如下：

回答下列问题：

(1)已知以T为根指针的二叉树如图所示，请写出执行f31(T)的输出结果：

(2)简述算法f31的功能。

阅读下列程序。

回答下列问题：

(1)已知矩阵B=，将其按行优先存于一维数组A中，给出执行函数调用f30(A，3)后矩阵B的值;

(2)简述函数f30的功能。

已知待排记录的关键字序列为{25，96，11，63，57，78，44}，请回答下列问题：

(1)画出堆排序的初始堆(大根堆);

(2)画出第二次重建堆之后的堆。

已知关键字序列为(56，23，41，79，38，62，18)，用散列函数H(key)=key%11将其散列到散列表HT[0..10]中，采用线性探测法处理冲突。请回答下列问题：

(1)画出散列存储后的散列表：

(2)求在等概率情况下查找成功的平均查找长度。

已知有向图的邻接表如图所示，请回答下面问题：

(1)给出该图的邻接矩阵;

(2)从结点A出发，写出该图的深度优先遍历序列。

不定长文件指的是文件的____________大小不固定。

已知一棵二叉排序树(结点值大小按字母顺序)的前序遍历序列为EBACDFHG，请回答下列问题：

(1)画出此二叉排序树;

(2)若将此二叉排序树看作森林的二叉链表存储，请画出对应的森林。