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

二叉树的存储结构类型定义如下

typedef struct node{

int data;

struct node *lchild， *rchild;

} BinNode;

typedef BinNode *BinTree;

编写递归算法，求只有一个孩子结点的结点总数，并计算这些结点的数据值的和。函数的原型为：void f34(BinTree T, int *count, int *sum)*count和*sum的初值为0。

顺序表类型定义如下：

(1)给出该算法的功能;

(2)给出该算法的时间复杂度。

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

(1)这是哪一种插入排序算法?该算法是否稳定?

(2)设置r[0]的作用是什么?

有向图的邻接矩阵类型定义如下：

#define MVN 100 ∥ 最大顶点数

typedef int EType; ∥ 边上权值类型

typedef struct{

EType edges[MVN][MVN]; ∥ 邻接矩阵，即边表

int n; ∥ 图的顶点数

｝MGraph; ∥ 图类型

例如，一个有向图的邻接矩阵如下所示：

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

(1)step1到step2之间的二重循环语句的功能是什么?

(2)step2之后的二重循环语句的功能是什么?

一组记录关键字(55,76,44,32,64,82,20,16,43)，用散列函数H(key)=key%11将记录 散列到散列表HT[0..12]中去，用线性探测法解决冲突。(1)画出存入所有记录后的散列表。(2)求在等概率情况下，查找成功的平均查找长度。

顺序表类型定义如下：

# define ListSize 100

typedef struct {

int data[ListSize];

int length;}SeqList;

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

(1)若L->data 中的数据为(22,4,63,0,15,29,34,42,3),则执行上述算法后L->data中的数据以及L->length的值各是什么?

(2)该算法的功能是什么?

假设Q是一个具有11个元素存储空间的循环队列(队尾指针指向队尾元素的下一个位置，队头指针指向队头元素)，初始状态Q.front=Q.rear=0;写出依次执行下列操作后头、尾指针的当前值。

a,b,c,d,e,f入队，a,b,c,d出队; (1) Q.front=______;Q.rear=______。

g,h,i,j,k,l入队，e,f,g,h出队; (2) Q.front=______;Q.rear=______。

M,n,o,P入队，i,j,k,l,m出队; (3) Q.front=______;Q.rear=______。

已知一个无向图如题27图所示，以①为起点，用普里姆(Prim)算法求其最小生成树，画出最小生成树的构造过程。

用归并排序法对序列 (98,36,-9,0,47,23,1,8)进行排序，问：

(1)一共需要几趟归并可完成排序。

(2)写出第一趟归并后数据的排列次序。

对于长度为81的表，若采用分块查找，每块的最佳长度为______。

用二叉链表保存有n个结点的二叉树，则结点中有______个空指针域。

直接选择排序算法的时间复杂度是______。

一组字符(a,b,c,d)在文中出现的次数分别为(7，6，3，5)，字符'd'的哈夫曼编码的长度为______。

在一个具有n个顶点的无向图中，要连通全部顶点至少需要______条边。

在二叉树中，带权路径长度最短的树称为______。

已知广义表G，head(G)与tail(G)的深度分别为4和6，则G的深度是______。

数据元素之间的逻辑关系称为数据的______结构。

在线性表中，表的长度定义为______。

用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1、2、3、4，为了得到1、3、4、2的出栈顺序，相应的S和X的操作序列为______。

下列关于m阶B树的叙述中，错误的是(　　)

分别用以下序列生成二叉排序树，其中三个序列生成的二叉排序树是相同的，不同的序列是(　　)

下列序列不为堆的是(　　)

对线性表进行二分查找时，要求线性表必须是(　　)

可进行拓扑排序的图只能是(　　)

下列排序方法中稳定的是(　　)

设无向图的顶点个数为n，则该图边的数目最多为(　　)

树的后序遍历等价于该树对应二叉树的(　　)

使用二叉线索树的目的是便于(　　)

下列关于顺序栈的叙述中，正确的是(　　)

A是一个10×10的对称矩阵，若采用行优先的下三角压缩存储，第一个元素,0的存储地址为1，每个元素占一个存储单元，则的地址为(　　)

设以数组A[0..m-1]存放循环队列，front指向队头元素，rear指向队尾元素的下一个位置，则当前队列中的元素个数为(　　)

顺序表便于(　　)

设带头结点的单循环链表的头指针为head，指针变量P指向尾结点的条件是(　　)

一个算法的时间耗费的数量级称为该算法的(　　)