数据结构模拟试题.docx

PAGE

PAGE1

数据结构模拟试题

一．选择题 (10分)

在下列各题的备选答案中选出一个正确的，将其编号写在答卷上。

设一个栈的输入序列为ABCD，则借助该栈所得到的输出序列不可能是 。

?ABCD ?DCBA ?ACDB ?DABC

在有n个叶子结点的赫夫曼树中，其结点总数为 。

?不确定 ?2n ?2n-1 ?2n+1

折半查找法要求查找表中各记录的关键字必须是 排列。

?无序 ?递增 ?递减 ?递增或递减

4. 对于关键字序列（12,13,11,18,60,15,7,18,25,100），用筛选法建堆，必须从关键字为 的结点开始。

?12 ?60 ?15 ?100

下列排序方法中，平均移动次数最少的排序方法是 。

?简单选择排序 ?直接插入排序 ?折半插入排序 ?起泡排序

二．判断题 (10分)

对下列叙述作出判断，用?或?表示正确或错误，将答案些在答卷上。

在顺序表中取出第i个元素所花费的时间与i成正比。

因为线性结构经排序后仍然是线性结构，所以排序是一种引用型运算。

将线性表的存储结构由单链表改为双链表，可以提高LOCATE运算的速度。

链表的特点之一，是可以随机访问任一数据元素。

串长度是指串中不同字符的个数。

在栈满情况下不能作进栈运算，否则产生“上溢”。

存在着这样的二叉树，对它采用任何次序遍历，其结点访问序列均相同。

具有奇数个结点的完全二叉树必是严格二叉树。

二路归并排序的核心操作是将两个有序序列归并为一个有序序列。

一个有向图的邻接表和逆邻接表中的结点个数一定相等。

三．填空题 (10分)

在带有头结点的线性链表L中，指向第一个元素结点的指针是 。

已知二维数组A

1010

中每个元素占4个单元，若按行优先方式将其存储到起始地址为1000

的连续的存储区域，则A

49

的地址是 。

具有100个结点的完全二叉树的深度为 。

已知二叉树中叶子数为50，仅有一个孩子的结点数为30，则总结点数为 。

高度为5的3阶B-树中至少有 个结点。

四．解答下列各题 (40分)

《数据结构》课程中算法的输入输出概念与《程序设计》课程中程序的输入输出概念有何区别？请简要回答。 （6分）

设线性表A和B的长度分别为m和n，若在下列存储结构上分别实现将表B联接在表A末尾的操作，其时间复杂度各是多少？ （6分）

线性链表

带头指针的循环链表

带尾指针的循环链表

设哈希表地址空间为0~7，哈希函数为H(key)=keyMOD7，处理冲突采用线性探测法。请画出依次插入关键字(23,14,9,6,12,18)后的哈希表，并对该哈希表计算在等概率情况下查找成功时的平均查找长度。（8分）

已知二叉树结点的后序和中序序列如下，构造出该二叉树。 （5分）后序序列：ABCDEFG

中序序列：ACBGEDF

对下列数据表，采用快速排序算法从小到大进行排序，请写出每趟的结果。 （5分）

（60，20，31，55，66，80，87，29）

6. 设有向图G=(V,A)，V={1,2,3,4,5,6}，A={1,2,1,3,2,5,3,6,6,5,5,4,6,4}，

试给出G的邻接矩阵、邻接表、逆邻接表及其从V1出发分别按深度优先和广度优先搜索遍历所得到的顶点序列。 （10分）

五．算法设计题 (30分)

设一棵二叉树以二叉链表为存储结构，其中每个结点有三个字段，分别是 lchild，data和

rchild，试设计算法，统计该二叉树上度为1的结点个数。 （10分）

已知循环队列的类型定义如下：

#define MAXSIZE 100 //队列容量

typedefstruct{

QElemType base[MAXSIZE]; //队列存储空间

int

rear;

//尾指针,若队列不空,指向队尾元素

int

length;

//队列长度,即队列中的元素个数

}SqQueue;

试编写入队列算法和出队列（删除并返回队首元素）算法。 （20分）