数据结构自考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)画出三元组表的行表。

设有一组记录的关键字为{19，14，23，1，68，12，10，78，25}，用链地址法构造散列表，散列函数为h(key)=key%11，散列地址为1的链中有 个记录。

在排序过程中，如果 ，则称其为外部排序。

对于稀疏图，采用 表示法较为节省存储空间。

在一棵具有n个结点的严格二叉树中，度为1的结点个数为 。

假设一个10阶的上三角矩阵A按z…--…-顺序压缩存储在一维数组B中，若矩阵中的第一个元素a1，1在B中的存储位置k=O，则元素a5，5在B中的存储位置k=

栈的修改是按 的原则进行。

字符串中任意个连续的字符组成的予序列称为该串的 。

散列文件是一种(　　)

若一个算法中的语句频度之和为，则该算法的渐近时间复杂度为 。

在单链表中，除了第1个元素结点外，任一结点的存储位置均由 指示。

对有序表进行二分查找成功时，元素比较的次数(　　)

若希望在1000个无序元素中尽快求得前10个最大元素，应借用(　　)

具有n个顶点，e条边的无向图的邻接矩阵中，零元素的个数为(　　)

要以O(n log n)时间复杂度进行稳定的排序，可用的排序方法是(　　)

在一棵二叉树中，度为2的结点数为15，度为1的结点数为3，则叶子结点数为(　　)

已知10x12的二维数组A，按“行优先顺序”存储，每个元素占1个存储单元，已知A[1] [1]的存储地址为420，则A[5][5]的存储地址为(　　)

在带权图的最短路径问题中，路径长度是指(　　)

广义表A=(a，B，(a，B，(a，B，……)))的长度为(　　)

一个链串的结点类型定义为 (　　)

#define NodeSize 6

typedef struct node{

char data[NodeSize];

struct node*next;

}LinkStrNode;

如果每个字符占1个字节，指针占2个字节，该链串的存储密度为(　　)

队列的特点是(　　)

设栈的初始状态为空，入栈序列为1,2,3,4,5,6，若出栈序列为2,4,3,6,5,1，则操作过程中栈中元素个数最多时为(　　)

指针p1和p2分别指向两个无头结点的非空单循环链表中的尾结点，要将两个链表链接成一个新的单循环链表，应执行的操作为(　　)

在一个长度为n的顺序表中插入一个元素的算法的时间复杂度为(　　)

在数据的逻辑结构中，树结构和图结构都是(　　)