数据结构自考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}，一趟二路归并排序的结果为_______。