内容发布更新时间 : 2024/4/28 6:01:28星期一 下面是文章的全部内容请认真阅读。

《数据结构》模拟试卷B及答案

考试时间 120 分钟 考试方式： 开卷 专业 年级 姓名 学号

一、 单项选择题(本大题共10小题，每小题2分，共20分)

1． 计算机科学中的算法指的是( )。D

A．计算机程序 B．计算数学公式的方法

C．排序算法 D．解决问题的有限运算序列

2． 对长度为n的顺序表，若在任何位置上进行插入操作的概率都相等，则在插入一个元素时，需要移动的元素个数平均是（ ）。A A．n/2 B. (n+1)/2 C. n+1 D. (n-1)/2

3． 设一个栈的输入序列为a，b，c，d，则输出序列不可能的是( )。D A．a，b，c，d B．d，a，b，c C．a，c，d，b D．d，c，b，a

4． 设循环队列中，数组的下标范围是0~n-1，其头尾指针分别为f和r，则队列中的元素个数为（ ）。D

A．r-f B．r-f+1 C．(r-f) mod n+1 D．(r-f+n)mod n

5． 若对二叉树的结点从0开始连续编号，要求每个结点的编号大于其左右孩子的编号，对同一个结点的左右孩子，其左孩子的编号小于其右孩子的编号，则实现编号可采用 ( )。C

A．前序遍历 B．中序遍历 C. 后序遍历 D．层次遍历

6． 任何一个无向连通图的最小生成树( )。B

A. 只有一棵 B．可以有一棵或多棵 C．一定有多棵 D．可能不存在

7． 若带权有向图G存储为代价矩阵A，则顶点i的入度等于A的（ ）。D A．第i行非∞元素之和 B. 第i列非∞元素之和

C．第i行非∞且非0的元素个数 D. 第i 列非∞且非0的元素个数

8． 二分查找算法要求顺序表是( )的。D

A．无序 B．递增有序 C．递减有序 D．递增或递减有序

9． 在最坏情况下，二叉排序树的最大成功查找长度是（ ）。B A． log2n B． n C．n2 D．1

10． ( )可能会出现下面的情况：初始数据有序时，所需要的时间反而最多。C A．简单选择排序 B．冒泡排序 C．快速排序 D．插入排序

二、 填空题(本大题共5小题，每小题3分，共15分)

1． 数据的逻辑结构从逻辑关系上描述数据，独立于计算机，与数据的（ ）无关。 存储结构

2． 线性表采用顺序存储结构时，结点的存储地址（ ）。 一定连续

3． 设一个顺序栈存储在一个长度为n的数组中，变量top指向栈顶位置，栈为满的条件是（ ）。 top= = n一1

4． 已知二叉树有50个叶子结点，则该二叉树的总结点数至少是（ ）。 99

5． 若连通图G的顶点数为n，则G至少有（ ）条边。 n一1

三、 简答题(本大题共4小题，每小题5分，共20分)

1． 研究一个数据结构主要应从哪几个方便进行？ 逻辑结构、物理结构、常用的操作算法、应用。 2． 请简要地描述链表中的表头结点及其作用。 表头结点是链表的附加结点，其中不存储线性表中的数据，其主要作用是方便编写操作算法和提高操作算法的时间效率。

3． 若要对线性表应用二分查找算法,则线性表需要满足什么条件? 线性表必须是有序,且存储为顺序结构

4． 当顺序表的长度固定以后，快速排序在什么情况下所需要的比较次数最多？请举例说明。

有序表的情况。（1，3，6，8，20，30，45）

四、 应用题(本大题共4小题，每小题6分，共24分)

1． 二叉树如下图所示，请写出其前序、中序和后序遍历遍历序列。

ABCEFHJGID 前序：a，b，c，e，d，f，h，g，i，j 中序：e，c，b，h，f，d，j，i，g，a 后序：e，c，h，{，j，i，g，d，b，a

2． 对线性表（18，8，21，7，3）进行选择排序，写出排序过程中每一趟的结果。 18，8，21，7，3

3，8，21，7，18 3，7，21，8，18 3，7，8，21，18 3，7，8，18，21

3． 设有无向图如下图所示，请给出该图的邻接矩阵，写出一个从顶点A出发的广 度优先搜索序列。

BACDFEG

?0 1 1 0 0 0 0??1 0 0 1 0 0 0????1 0 0 1 0 0 0???0 1 1 0 1 1 0?? ?0 0 0 1 0 0 1???0 0 0 1 0 0 1???0 0 0 0 1 1 0???广度优先搜索序列：a，b，c，d，e，f，g

4． 设有一个散列表，散列函数为H(key)=key mod 3，冲突处理方法采用链地址法。现从空的散列表开始，依次存人键值6、7、8、9和11，请画出最终所得到的散列表的示意图，并求出等概率情况下的平均成功查找长度。

t[0] 6 9 ? t[1] 7 10 ? t[2] 8 11 ? 平均成功查找长度ASL＝(3*1+3*2)/6＝3/2

五、 算法设计题(本大题共2小题，共21分)

1． 下面的算法判断一个带表头结点的单链表L是否是递增有序的，请在其中的空白处填上适当的内容，使之成为完整正确的算法。(10分) typedef struct node {char data;

struct node *next; } NODE;

int pdyx(NODE *L) { NODE *pre，*p；

pre=L->next； if (pre!＝NULL) while (①) {p＝②；

if (p->data>③) pre = ④； else

⑤； }

return(1)； }

①pre!＝NULL ②pre->next ④pre->data ④pre->next ⑤return(0)

2． 设计一个算法，求出非空二叉排序树中存储的最大值。(11分) struct node {char data； struct node *lchild;

struct node *rchild;

}

typedef struct node NODE;

int BiSearTreeMax(NODE *t) {

while (t->rchild != NULL)

t=t->rchild; return(t->data); }