数据结构导论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个元素的数据序列，采用二叉排序树查找，平均查找长度介于_________之间。

Dijkstra算法的思想是按照最短路径长度_________的方法产生从一点到其他顶点的最短路径。

遍历图的基本方法有深度优先搜索和_________优先搜索两种。

在树形结构中，每一层结点只能和上一层中的至多一个结点相关，而在_________中，任意两个结点之间都可能相关。

若对一棵有n(n>0)个结点的完全二叉树从1开始进行结点的编号，并按此编号把它顺序存储到一维数组A中，即编号为1的结点存储到A[1]中，其余类推。若i>2，则A[i]的双亲结点为_________。

用于描述分类过程的二叉树称为_________。

设顺序表A长度为100，若下标从1开始计数，则删除元素A[10]需要移动_________个元素。

循环队列的队头指针为front，队尾指针为rear，当_________时表明队列为空。

对于一棵包含n个结点的二叉树，用二叉链表存储时，其指针总数为_________个。

对于按位置查找运算，顺序表是随机存取，其时间复杂度为_________。

在估算算法空间复杂度时，一般只需要分析_________所占用的空间。

假设顺序表为(b1，b2，b3)，查找b1，b2，b3的概率分别为0.2，0.2，0.6，则顺序查找法的平均查找长度为(　　)

已知一个有序表为(13，18，24，35，47，50，62，83，90，115，134)，当用二分查找方法查找值为90的元素时，查找成功时，键值比较的次数为(　　)

在插入排序方法中，类似图书馆中整理图书的过程的是(　　)

一个具有n个顶点的无向完全图的边数为(　　)

邻接表的存储方法结合了(　　)

关于满二叉树和完全二叉树，下面叙述正确的是(　　)

与二叉链表结构形式完全相同的是(　　)

关于树的概念，下面叙述正确的是(　　)

设两个数据元素类型一致的栈共享一维数组空间data[max]成为双栈，两个栈的栈底分别设在数组两端，这两个栈的栈顶变量分别为top1和top2，且top2≥top1，则下列会发生“上溢”情况的是(　　)

设有一循环队列SQ，现将数据x进行入队操作，语句为(　　)

关于栈和队列，下面叙述正确的是(　　)

在双向循环链表中，设p指向待删结点，删除*p的正确语句为(　　)

假设顺序表的长度为n，则在第i(1≤i≤n+1)个元素之前插入一个新元素x所需移动元素的个数为(　　)

与数据元素本身的形式、内容、相对位置、个数无关的是数据的(　　)

时间复杂度的阶数中，O(n)表示(　　)