数据结构导论2017年10月真题及答案解析（02142）

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

typedef struct btnode

{ DataType data;

  struct btnode *lchild, *rchild;

}*BinTree;

假定vsit(bt)是一个已定义的过程，其功能是访问指针bt所指结点。设计递归算法preorder( BinTree bt)实现在二叉链表上的先序遍历。

给出一组关键字(20，29，11，74，35，3，8，56)，写出冒泡排序前两趟的排序结果，并说明冒泡排序算法的稳定性如何?

设有一n阶方阵A，设计算法实现对该矩阵的转置。

设有向图的邻接表表示如题31图所示，请给出每个顶点的入度和出度。

已知散列表的地址空间为0~10，散列函数为H(key)= key mod11(mod表示求余运算)，采用二次探测法解决冲突，试用键值序列20，38，16，27，5，23，56，29建立散列表，并计算出等概率情况下查找成功的平均查找长度。

直接插入排序的空间复杂度为_________。

已知一个7×6的稀疏矩阵如题29图所示，试写出该稀疏矩阵的三元组表示。

已知一棵二叉树如题30图所示，试求该二叉树的先序遍历序列、后序遍历序列和层次遍历序列。

作为一种数据结构，查找表的逻辑结构是_________。

对于具有n个元素的数据序列，采用二叉排序树查找，平均查找长度介于_________之间。