数据结构导论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，则顺序查找法的平均查找长度为(　　)

• A.1
• B.1.2
• C.1.4
• D.1.6

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

• A.2
• B.3
• C.4
• D.5

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

• A.希尔排序
• B.表插入排序
• C.折半插入排序
• D.直接插入排序

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

• A.n²/2
• B.n²
• C.n(n-1)/2
• D.n(n-1)

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

• A.顺序存储与散列存储
• B.顺序存储与链式存储
• C.链式存储与索引存储
• D.链式存储与散列存储

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

• A.完全二叉树结点个数>满二叉树结点个数
• B.满二叉树一定是完全二叉树
• C.完全二叉树一定是满二叉树
• D.含有n个结点的完全二叉树的深度为log₂n

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

• A.孩子链表
• B.孩子兄弟链表
• C.带双亲的孩子链表
• D.双亲链表

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

• A.树可以没有根结点
• B.树中结点个数不为0
• C.树中可以存在多个根节点
• D.若树中存在多个子树，则子树之间可以相交

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

• A.top1+1=top2
• B.top1=top2
• C.top2+1-=top1
• D.top1+top2=max

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

• A.SQ. front=(SQ. front+1)%maxsize;
• B.SQ. rear=(SQ. rear+1)%maxsize;
• C.SQ. front=(SQ. front +1)%maxsize; SQ. data[SQ. front]=x;
• D.SQ. rear=(SQ. rear+1)%maxsize; SQ. data[SQ.rear]=x;

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

• A.函数的嵌套调用用队列来实现
• B.操作系统中进程调用用栈来实现
• C.程序递归的处理用队列来实现
• D.栈和队列是运算受限的线性表

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

• A.p->prior->next=p->next; p->next->prior=p->prior; free(p);
• B.p->next= p->prior->next; p->prior= p->next->prior; free(p);
• C.p->prior->next=p->next; p->next->prior=-p->prior;
• D.p->next=p->prior->next; p->prior= p->next->prior;

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

• A.i
• B.n-i
• C.n-i+1
• D.n

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

• A.存储结构
• B.逻辑结构
• C.类型
• D.运算实现

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

• A.常数阶
• B.线性阶
• C.多项式阶
• D.指数阶