数据结构模拟试题.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分）