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

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

typedef struct btnode

{ DataType data;

  struct btnode *lchild, *rchild;

}*BinTree;

利用二叉树遍历的递归算法，设计求二叉树的高度的算法Height(BinTree bt)。

设计一个算法实现以下功能：在整型数组A[n]中查找值为k的元素，若找到，贝!1输出其位置i(0≤i≤n-1)，否则输出-1作为标志。

将一组键值 {83，69，41，22，15，33，8，76} 应用二路归并排序算法从小到大排序，试写出各趟排序的结果。

画出题31图所示森林经转换后所对应的二叉树。

已知如题 32 图所示的无向带权图，请从结点 A 出发，用普里姆(Prim)算法求其最小生成树，并画出过程示意图。

已知一棵二叉树的先序遍历结果为ABDCEF，中序遍历结果为DBAECF，试画出这棵二叉树，并写出这棵二叉树的后序遍历序列。

设A、B、C、D、E五个元素依次进栈(进栈后可立即出栈)，问能否得到下列序列：

(1)A，B，C，D，E; (2)A，C，E，B，D

若能得到，刚给出该序列的操作过程(用push(A)表示A进栈，pop(A)表示A出栈);若不能，则说明理由。

从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为_________排序法。

如果包含n个顶点的连通图G的一个子图G’的边数大于n-1，则G’中一定有_________。

在含有9个元素的有序表(2，4，12，18，23，37，49，51，68)中二分查找关键字(关键字即为数据元素的值)为37的元素时，所需进行的比较次数为_________次。

树的双亲表示法由一个一维数组构成，数组的每个分量包含_________和双亲域两个域。

设栈S的初始状态为空，若元素a，b，C，d依次进栈，得到的出栈序列是c，d，b，a，则栈的容量至少是_________。

若一棵完全二叉树有14个结点，则它的深度为_________。

在栈中，允许进行插入和删除操作的一端称为_________。

即使输入非法数据，算法也能适当地做出反应或进行处理，不会产生预料不到的运行结果， 这种评价算法好坏的因素称为_________。

假设一个8阶的上三角矩阵A按照列优先顺序压缩存储在一维数组8中，则B数组的大小应为_________。

为了便于运算的实现，在单链表的第一个结点之前增设一个类型相同的结点，称之为_________。

一个算法的时空性是指该算法的时间性能和_________。

线性表、栈和队列中的元素具有相同的逻辑结构，即_________。

下列排序方法中不稳定的是(　　)

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

从宏观上看，数据、数据元素和_________反映了数据组织的三个层次。

静态查找表指对查找表只进行两项操作，即(　　)

• A.插入和删除一个数据元素
• B.查找表中某一元素和插入一个数据元素
• C.读取表中“特定”数据元素和删除一个数据元素
• D.查找表中某一元素和读取表中“特定”数据元素

图的深度优先搜索遍历类似于树的(　　)

• A.先序遍历
• B.中序遍历
• C.后序遍历
• D.层次遍历

若在线性表中采用二分查找法查找元素，该线性表应该(　　)

• A.元素按值有序，且采用链式存储结构
• B.元素按值无序，且采用链式存储结构
• C.元素按值有序，且采用顺序存储结构
• D.元素按值无序，且采用顺序存储结构

含有100个结点的二叉树采用二叉链表存储时，空指针域NULL的个数是(　　)

• A.99个
• B.100个
• C.101个
• D.200个

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

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

树中叶子的度是(　　)

• A.0
• B.1
• C.2
• D.3

将一棵有n个结点的完全二叉树按层编号，若编号i所对应的结点为A，且i>1，则A的双亲的编号为(　　)

• A.i
• B.i/2
• C.
• D.

栈的修改原则是(　　)

• A.先进先出
• B.后进先出
• C.栈空则进
• D.栈满则出

设有一顺序队列SQ，已知尾指针rear<队列的最大长度-1，则数据x进行入队列操作的语句为(　　)

• A.SQ.front=SQ.front+1;
• B.SQ.front=SQ.rear+1;
• C.SQ.front=SQ.front+1; SQ.dataF[Sq.front]=x;
• D.SQ.rear=SQ.rear+1; SQ.datar[SQ.rear]=x;

一个数组的第一个元素的存储地址是100，每个元素占2存储单元，则第5个元素的存储地址是(　　)

• A.105
• B.108
• C.115
• D.118

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

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

双向循环链表中，在指针P所指结点的后面插入一个新结点*t，正确的语句为(　　)

• A.t->prior-P;    t->next=p->next;    p->next->prior=t;    p->next=t;
• B.t->prior=p;    t->next=p->next;    p->next=t;
• C.t->prior-P;    p->next->prior=t;    t->next=p->next;    P->next=t;
• D.p->next-->prior=t;    p->next=t;

表示数据元素之间的关联方式通常采用的存储方式是(　　)

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

任意两个结点之间都没有邻接关系，组织形式松散，这种组织形式称为(　　)

• A.集合
• B.线性结构
• C.树形结构
• D.图结构