09--13年全国自考数据结构历年试题及部分答案 - 图文

22．已知有向图如下所示，其中顶点A到顶点C的最短路径长度是___35______。

23．对序列{55，46，13，05，94，17，42}进行基数排序，第一趟排序后的结果是_10,42,12,94,55,01,46,17。 24．高度为3的3阶B-树最少的关键字总数是__13_______。

25．VSAM通常作为大型索引顺序文件的标准组织，其动态索引结构采用的是___B+______。

三、解答题(本大题共4小题，每小题5分，共20分) 26．假设二叉树的RNL遍历算法定义如下： 若二叉树非空，则依次执行如下操作： (1)遍历右子树； (2)访问根节点； (3)遍历左子树。

已知一棵二叉树如图所示，请给出其RNL遍历的结果序列。GCFABDC

27．已知一个无向图G=(V，E)，其中V={A，B，C，D，E，F}，邻接矩阵表示如下所示。

请回答下列问题：

(1)请画出对应的图G。

(2)画出图G的邻接表存储结构。

28．已知一组待排记录的关键字序列为(16，12，18，60，15，36，14，18，25，85)，用堆排序方法建小根堆，请

给出初始建堆后的序列。

29．已知一棵二叉排序树如图所示。 请回答下列问题：

(1)画出插入元素23后的树结构；

(2)请画出在原图中删除元素57后的树结构。

四、算法阅读题(本大题共4小题，每小题5分，共20分) 30．已知下列程序，Ls指向带头结点的单链表。 Typedefstruct node { DataType data;

- 本套试题共分64页，当前页是第25页-

struct node * next; } * LinkList;

void f30( LinkList Ls ) { LinkList p, q; q = Ls->next;

if ( q && q->next ) { Ls->next = q->next; p=q

while ( p->next ) p = p->next; p->next = q; q->next = NULL; } }

请回答下列问题：

(1)当Ls指向的链表如下图所示，请画出执行本函数之后的链表的结果。

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

31．已知字符串处理函数f31程序如下。 int f31(char*strl，char*str2)

{ while(*strl==*str2&&(*strl!=’＼0’)){

strl++； str2++； }

return(*strl-*str2 ? l∶0)； }

请回答下列问题：

(1)若调用语句是f31(”abcde”，”abcdf’)，则函数的返回值是什么?若调用语句是

f31(”abcde”，”abcde”)，则函数的返回值是什么?

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

32．数组A[]中存储有n个整数，请阅读下列程序。 void f32(intA[]，int n) { inti，j，k，x；

k=n-l； while(k>0){

i=k； k=0；

for(j=O；jA[j+1]){ x=A[j]；

A[j]=A[j+l]； A[j+1]=x； k=j；

}／／end of if }／／end of while return； }

- 本套试题共分64页，当前页是第26页-

请回答下列问题：

(1)当A[]={10，8，2，4，6，7}时，执行f32(A，6)后，数组A中存储的结果是什么? (2)说明该算法的功能。

33．下面程序实现二分查找算法。 Typedef struct{

KeyType key；

InfoType otherinfo； }SeqList[N+1]；

int BinSearch(SeqList R, int n，KeyType K) { int low=1，high=n； while( (1) ){

mid=(1ow+high)／2； if( (2) )

return mid； if(R[mid]．key>K)

high=mid-1； else

(3) ；

}

return O； } ／／BinSearch

请在空白处填写适当内容，使该程序功能完整。 (1) (2) (3)

五、算法设计题(本题10分)

34．已知二叉树采用二叉链表存储，其结点结构定义如下： typedef struct Node{

ElmType data；

struct Node *lchild，*rchild； }*BiTree；

请编写递归函数SumNodes(BiTree T)，返回二叉树T的结点总数。

- 本套试题共分64页，当前页是第27页-

- 本套试题共分64页，当前页是第28页-