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

设顺序表L是一个递增有序表。编写算法，要求利用二分查找法确定插入位置，将元素x插入到L中，使L保持有序。

假设具有n个结点的完全二叉树顺序存储在向量BT[1..n]中，阅读下列算法，并回答问题：

(1)若向量BT为：

     1 2 3 4 5 6 7

画出执行函数f32(BT，7，1)的返回结果;

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

BinTree f32(DataType BT[]，intn，inti)

{

BinTree p;

if(i>n)return NULL;

p=(BinTNode*)malloc(sizeof(BinTNode));

p->data=BT[i];

p->lchild=f32(BT,n，i*2);

p->rchild=f32(BT，n，i*2+1);

return p;

}

已知有向图的邻接表和邻接矩阵定义如下：

#define MaxNum 50 图的最大顶点数

typedef struct node{

int adjvex; ∥邻接点域

struct node半next; ∥链指针域

}EdgeNode; ∥边表结点结构

typedef struct{

char vertex; ∥顶点域

EdgeNode *frrstedge; ∥边表头指针

}VertexNode; ∥顶点表结点结构

typedef struct{

VertexNode adjlist[MaxNum]; ∥邻接表

int n，e; ∥图中当前顶点数和边数

}ALGraph; ∥邻接表描述的图

typedef struct{

char vertex[MaxNum]; ∥顶点表

int adjmatrix[MaxNum][MaxNum]; ∥邻接矩阵

int n，e; ∥图中当前顶点数和边数

}AMGraph; ∥邻接矩阵描述的图

下列算法是将邻接表描述的图Gl改为邻接矩阵描述的图G2趁，在空白处填上适当内容使算法完整：

阅读下列算法，并回答问题：

(1)假设栈S=(3，8，6，2，5)，其中5为栈顶元素，写出执行函数f3l(&S)后的S;

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

void f31(Stack*S)

{Queue Q;InitQueue(&Q);

while(!StackEmpty(S))

EnQueue(&Q，Pop(&S));

while(!QueueEmpty(Q))

Push(&S，DeQueue(&Q));

}

阅读下列算法，并回答问题：

(1)假设p(3，7，7，11，20，20，20，51，51)，写出执行函数=f30(&L)后的L.

(2)简述f30的功能。

对关键字序列(429，653，275，897，170，908，473，256，726)进行基数排序，写出每一趟的排序结果。

对下列关键字序列 (87，25，310，08，27，132，68，96，187，133，70，63，47，135)构造散列表，假设散列函数为h(key)=key%13，用拉链法解决冲突。

(1)画出该散列表;

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

(3)写出删除值为70的关键字时所需进行的关键字比较次数。

已知一个森林的前序遍历序列为CBADHEGF，后序遍历序列为ABCDEFGH。

(1)画出该森林;

(2)画出该森林所对应的二叉树。

多关键字文件的特点是除主文件和主索引外，还建有 。

对于下列稀疏矩阵(注：矩阵元素的行列下标均从1开始)

(1)画出三元组表;

(2)画出三元组表的行表。