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

已知二叉树的二叉链表类型定义如下：

为完成指定功能，请在空白处填写适当内容，使其功能完整。

函数f33的参数t指向题33图所示的二叉排序树的根，阅读程序，回答下列问题。

(1)若连续3次调用函数f33，参数K的值依次取10、25、10，写出每次调用后函数的输出结果;

(2)说明函数f33的功能。

已知顺序表SeqList定义如下：

typedef struct{

   KeyType key;

   InfoType otherinf0;

 }RecType：

typedef RecType SeqList[MAXSIZE+1];

编写函数，用冒泡排序法将n个元素的待排序列R按关键字降序排序。函数原型为：

int f34(SeqList R，int n)。

请写出下列程序段的输出结果。

己知存储稀疏矩阵三元组表的类型定义如下：

#define MAX 100

typedef struct{

           int i, j;               //非零元素的行号、列号(下标)

           int v;                //非零元素值

} TriTupleNode;

typedef struct{

     TriTupleNode data[ MAX];          //存储三元组的数组

      int m, n, t;                  //矩阵的行数、列数和非零元素个数

     }TSMatrix;              //稀疏矩阵类型

函数f31的功能是将a所表示的矩阵转置后保存在*b中。请在空白处填写适当内容，使其完成指定功能。

己知二又树T如题27图所示。

请问答下列问题：

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

(2)写出对森林进行前序遍历的遍历序列i

题28图所示为一棵含2个关键字的3阶B树T。现将关键字序列{40，60，70，20，10}依次插入到T中，画出每插入一个关键字后得到的树型。

给定无向带权连通图G如题29图所示，从顶点v0开始，使用普里姆(Prim)算法，求G的最小生成树T。

请回答下列问题。

(1)画出最小生成树T。

(2)计算T中各边权值之和。

已知n阶对称矩阵A的元素为(0≤i，j≤n-1)，采用“按行优先”将下三角部分的元素(含主对角线)保存在一维数组sa中，且约定元素,0保存在sa[0]中，元素(≤i，j≤n-1)保存在sa[k]中，请给出由下标i，j计算下标k的计算公式。

已知关键字序列为{66，82，25，51，98，108}，一趟二路归并排序的结果为_______。

借助于一个栈来实现的图的遍历算法是_______。

若有向图中存在拓扑排序序列，则该图一定不存在_______。

在有n个顶点的无向图中，任一顶点的度不大于_______。

由一棵二叉树的后序遍历序列和_______遍历序列可以唯一确定该二叉树。

设树T的度为3，其中度为1、2和3的结点个数分别为3、2和1，则T中叶子结点的个数为_______。

广义表L=(a，(b，e，(e，f，g，h)))，head(L)= _______。

设Push，、Pop分别表示人栈和出栈操作，x=10，y=20，z=30。依次进行下列操作：Push(y)、Push(z)、Push(z)、X=Pop()、Y=Pop()，x,y的值分别是_______。

线性表(a1，a2，…，an)中，除_______外，每个元素都有唯一的直接前趋。

指针P指向单链表中某个结点，在P所指结点后插入指针s所指的结点，正确的操作序列是_______。

下列选项中，其平均查找性能与基于二叉排序树的查找相当的是(　　)

已知关键字序列为{66，82，25，51，98，108}，利用快速排序方法，以第一个元素为基准得到的一趟排序结果为(　　)

下列选项中，能构成题10图中一条路径的是(　　)

下列选项中，符合堆定义的是(　　)

有向图采用邻接矩阵存储，某一行中非零元素的个数等于(　　)

6个顶点的强连通图中，含有的边数至少是(　　)

对题10图进行深度优先搜索遍历，下列选项中，正确的遍历序列是(　　)

一棵左子树为空的二叉树在前序线索化后，其空指针域个数为(　　)

广义表A=(x，((y)，((a))，A))的深度是(　　)

下列关于哈夫曼树的叙述中，错误的是(　　)

若一个栈以数组V[0..n-1]存储，初始栈顶指针top为n，则x入栈的正确操作是(　　)

在二维数组a[9][10]中：每个数组元素占用3个存储空间，从首地址SA开始按行优先连续存放，则元素a[8][5]的起始地址是(　　)

栈采用不同的存储方式时，下列关于出栈过程的叙述中，正确的是(　　)

长度为n的顺序表，删除位置i上的元素(0≤i≤n-1)，需要移动的元素个数为(　　)

下列选项中，不属于线性结构的是(　　)