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

设单链表及链栈S的结构定义如下：

typedef struct node

{ Data Type data;

  struct node *next;

｝linkstack;

编写一个算法void ReverseList(1inkstack *head)，借助于栈S将带头结点单链表head中序号为奇数的结点逆置，序号为偶数的结点保持不变。(例如：单链表的逻辑结构为(a₁，a₂，a₃，a₄，a₅，a₆)，逆置后变为(a₅，a₂，a₃，a₄，a₁，a₆))。

说明：栈的初始化运算用InitStack(S);进栈运算用Push(S, x);判栈空运算用EmptyStack(S);出栈运算用Pop(S);取栈顶元素运算用Gettop(S)。

以二叉链表作为存储结构，试编写递归算法实现求二叉树中叶子结点个数。

将一组键值(80，50，65，13，86，35，96，57，39，79，59，15)应用二路归并排序算法从小到大排序，试写出各趟的结果。

已知散列表的地址空间为0至13，散列函数H(k)=k mod 11，(mod为求余运算)，待散列序列为(26，61，38，84，49)，用二次探测法解决冲突，构造该序列的散列表，要求写出处理冲突的过程。

写出题31图所示无向图的邻接矩阵，并写出每个顶点的度。

                     题31图

稀疏矩阵A如题29图所示，写出该稀疏矩阵A的三元组表示法。

设二叉树的中序遍历序列为BDCEAFHG，后序遍历序列为DECBHGFA，试画出该二叉树。

归并排序算法的时间复杂度是_________。

在长度为n的带有岗哨的顺序表中进行顺序查找，查找不成功时，与关键字的比较次数为_________。

要完全避免散列所产生的“堆积”现象，通常采用_________解决冲突。

已知完全二叉树的第5层有5个结点，则整个完全二叉树有_________个结点。

n个顶点的有向图G用邻接矩阵A[1..n，1..n]存储，其第i列的所有元素之和等于顶点V_i的_________。

具有10个顶点的有向完全图的弧数为_________。

稀疏矩阵一般采用的压缩存储方法是_________。

100个结点的二叉树采用二叉链表存储时，用来指向左、右孩子结点的指针域有_________个。

在带有头结点的循环链表中，尾指针为rear，判断指针P所指结点为首结点的条件是_________。

若线性表中最常用的操作是求表长和读表元素，则顺序表和链表这两种存储方式中，较节省时间的是_________。

不含任何数据元素的栈称为_________。

下述算法中，不稳定的排序算法是(　　)

• A.直接插入排序
• B.冒泡排序
• C.堆排序
• D.归并排序

数据的基本单位是_________。

双向循环链表中，在p所指结点的后面插入一个新结点*t，需要修改四个指针，分别为t->prior=P; t->next=p->next; _________; p->next=t; 。

构造散列函数的方法很多，常用的构造方法有(　　)

• A.数字分析法、除留余数法、平方取中法
• B.线性探测法、二次探测法、除留余数法
• C.线性探测法、除留余数法、链地址法
• D.线性探测法、二次探测法、链地址法

就平均时间性能而言，快速排序方法最佳，其时间复杂度为(　　)

• A.O(n)
• B.O(nlog₂n)
• C.O(n2)
• D.O(1og₂n)

在具有101个元素的顺序表中查找值为x的元素结点时，平均比较元素的次数为(　　)

• A.50
• B.51
• C.100
• D.101

无向图的邻接矩阵是(　　)

• A.对角矩阵
• B.稀疏矩阵
• C.上三角矩阵
• D.对称矩阵

n为图的顶点个数，e为图中弧的数目，则图的拓扑排序算法的时间复杂度为(　　)

• A.O(n)
• B.O(e)
• C.O(n-e)
• D.O(n+e)

如果结点A有2个兄弟结点，结点B为A的双亲，则B的度为(　　)

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

将题9图所示的一棵树转换为二叉树，结点C是(　　)

• A.A的左孩子
• B.A的右孩子
• C.B的右孩子
• D.E的右孩子

元素的进栈次序为A，B，C，D，E，出栈的第一个元素为E，则第四个出栈的元素为(　　)

• A.D
• B.C
• C.B
• D.A

深度为5的二叉树，结点个数最多为(　　)

• A.31个
• B.32个
• C.63个
• D.64个

带头结点的链队列中，队列头和队列尾指针分别为front和rear，则判断队列空的条件为(　　)

• A.front==rear
• B.front!=NULL
• C.rear!==NULL
• D.front==NULL

顺序表中定位算法(查找值为x的结点序号最小值)的平均时间复杂度为(　　)

• A.O(1)
• B.O(log₂n)
• C.O(n)
• D.O(n²)

表长为n的顺序表中做删除运算的平均时间复杂度为(　　)

• A.O(1)
• B.O(log₂n)
• C.O(n)
• D.O(n²)

数据的存储方式中除了顺序存储方式和链式存储方式之外，还有(　　)

• A.索引存储方式和树形存储方式
• B.线性存储方式和散列存储方式
• C.线性存储方式和索引存储方式
• D.索引存储方式和散列存储方式

下列几种算法时间复杂度中，最小的是(　　)

• A.O(log₂n)
• B.O(n)
• C.O(n²)
• D.O(1)