郑州大学远程教育学院数据结构试题及答案

由天下分享时间：2025/1/2 14:24:37 加入收藏我要投稿点赞

一定是连通图。（）

2. 若从无向图的一个顶点出发进行深度优先遍历可访问到图中所有顶点，则该图一定是连通图。（）

3. 任何有向图的顶点都可以排成拓扑有序序列，而且拓扑序列不唯一。（） 4. 有n个顶点和n-1条边的无向图一定是生成树。（） 5. 一棵有n个顶点的生成树有且仅有n-1条边。（） 6.连通分量是无向图的极大连通子图，而生成树是无向图的极小连通子图。（）（三）问答及算法题：

?010??，该图有多少个顶点如果是有向图，该图1011. 一个图的邻接矩阵=?????011??共有多少条弧如果是无向图，该图共有多少条边

2.已知如右图所示的有向图，写出该图的: (1)邻接矩阵 (2）一个可能的拓扑有序序列（3）写出从1出发的深度优先遍历序列（4）写出从5出发的广度优先遍历序列。

3. 假设有5项活动C1～C5，每项活动要求的前驱活动如下：

C1：无； C2：C1，C3； C3：C1； C4：C3，C5 C5：C2；

试根据上述关系，画出相应的有向图，再写出一个拓扑排序序列。 4. 基于图的深度优先遍历策略写一算法，判断以邻接表方式存储的无向图中连通分量的个数。

第九章查找

一、章节学习目标与要求

1、理解各种查找表的定义、各种查找方法的思想以及构造查找表所依据的原则。 2、掌握线性表表示的静态查找表的顺序查找和折半查找算法及其性能分析方法；掌握二叉排序树的创建、查找、插入、删除算法及其性能分析方法；掌握AVL树的平衡化旋转方法及其性能分析；掌握B-树的插入和删除时结点的分裂和合并方法；掌握Hash法的查找、构造方法平均查找长度的计算方法。二、本章重点、难点

重点：各种树结构表示的动态查找表和Hash表的构造方法

难点：二叉排序树的删除、AVL树的旋转处理、B-树的插入和删除、Hash法的构造以及各种查找表的平均查找长度的计算方法三、章节练习（一）选择题：

1. ________二叉排序树可得到一个关键字的有序序列。

A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 层序遍历 2．用链地址法处理冲突构造的散列表中，每个地址单元所链接的同义词表中结点的_____相同。

A. 关键字 B. 元素值 C. 散列地址 D. 含义

3．利用折半查找方法在长度为n的有序表中查找一个元素的平均查找长度是______。

(n2) (nlogn) (n) D. O(logn)

4．散列表的装填因子越大，则发生冲突的可能性就________。 A. 越小 B. 越大 C. 不确定

5．线性表中共有256个元素，采用分块查找，若查找每个元素的概率相等，用顺序查找确定结点所在的块，每块有_____个元素时查找效率最佳。 A. 16 B. 20 C. 25 D. 256

6．用折半查找对长度为7的有序表进行查找，则等概率下查找成功时的平均查找长度为______。

A. 15/7 B. 17/7 C. 18/7 D. 19/7

7．有序表（1，32，41，45，62，75，77，82，95，100），使用折半查找关键字为95的元素时，需要经过____次比较后才能查找成功。 A. 2 B. 3 C. 4 （二）判断题：

1. 折半查找和二叉排序树的查找时间性能一样。（） 2. 在任意一棵非空的二叉排序树中，删除某结点后又将其插入，则所得的二叉排序树与删除前的二叉排序树形态相同。（） 3. 根据B-树的定义，在9阶B-树中，除根以外的任何一个非叶子结点中的关键字

数目均在5～9之间。（） 4.折半查找时，要求线性表必须是有序的且以顺序结构存储。（）（三）问答题：

1. 设有一组关键字序列{19，1，23，14，55，20，84，27，68，11，40}，（1）按表中元素顺序构造一棵二叉排序树，画出这棵树，并求其在等概率情况下查找成功时的平均查找长度。

（2）从空树开始，按表中元素顺序构造一棵2_3树(3阶B_树)，若此后再删除55，84，画出每一步执行后2_3树的状态。

2. 设散列函数H(key)=key MOD 7,用线性探测再散列法解决冲突。对关键字序列{ 13，28，72，5，16，8，7，11 }在地址空间为0-10的散列区中建散列表，画出此表，并求等概率情况下查找成功时的平均查找长度。

3. 关键字序列：13，28，72，5，16，18，7，11，24，h (key) = key mod 11,表长

为11，用线性探测再散列处理冲突，试填写下表并计算每个关键字的比较次数和等概率情况下查找成功时的平均查找长度。

哈希表

0 1 2 3 4 5 6 7 8 9 10 比较次数 ASL=

4. 在地址空间为0-16的散列区中，对以下关键字序列(Jan,Feb,Mar,Apr,May, June,July,Aug,Sep,Oct,Nov,Dec)按链地址法处理冲突构造散列表，设散列函数H(x)=i/2,其中i为关键字中第一个字母在字母表中的序号。画出该散列表并求在等概率情况下查找成功时的平均查找长度。

第十章排序

一、章节学习目标与要求

1、理解排序相关的定义以及排序方法的各种分类，理解各种排序方法的基本思想和依据原则。

2、掌握内部排序的基本概念和性能分析方法；掌握插入排序、交换排序、选择排序等内排序的方法及其性能分析方法。二、本章重点、难点

重点：各类内部排序方法所依据的原则、特点及典型算法。

难点：希尔排序、快速排序、堆排序三、章节练习（一）选择题：

1. 下列方法中，________是稳定的排序方法。

A．堆排序 B. 希尔排序 C. 快速排序 D. 折半插入排序

2. 设有1000个无序的元素，希望用最快的速度选出其中前20个最大的元素，最好用________排序方法。

A. 冒泡排序 B. 快速排序 C. 堆排序 D. 希尔排序 3．下列序列中，______是堆。

A. {12，35，20，60，40，30} B. {100，85，120，38，10，9，36} C. {1，5，6，24，7，3，4 } D. {38，24，15，20，30，46} 4．在待排序的元素序列基本有序时，效率最高的排序方法是__ ____。 A.插入排序 B.选择排序 C.快速排序 D. 归并排序

5．在下列排序方法中，某一趟结束后未必能选出一个元素放在其最终位置上的是_______。

A. 堆排序 B. 起泡排序 C. 快速排序 D. 直接插入排序 6．对序列{22,86,19,49,12,30,65,35,18}进行一趟排序后得到的结果为{18,12,19,22,49,30,65,35,86}，则其使用的排序方法为_______。 A. 插入排序 B. 选择排序 C. 快速排序 D. 起泡排序 7. 下列方法中，________算法的时间复杂度为O(n2)。

A. 堆排序 B. 希尔排序 C. 快速排序 D. 直接插入排序 8. 对n个记录的序列进行堆排序，最坏情况下的时间复杂度为______。 A. O(logn) B. O(nlogn) C. O(n) (n2) （二）判断题：

1.快速排序的速度在所有排序方法中是最快的，而且所需的附加空间也最少。（） 2.对一个堆按层次遍历，不一定能得到一个有序序列。（） 3.由于希尔排序的最后一趟与直接插入排序过程相同，所以前者一定比后者花费的时间多。（） 4.快速排序算法在待排序数据有序时最不利于发挥其长处。（）

（三）问答题：

1.在快速排序过程中，通常取序列中的第1个记录作为枢轴，以它为“分界线”重排其余记录。但当初始记录序列按关键字有序或基本有序时，快速排序将蜕化为起泡排序，为改进之，应如何选取枢轴记录

2.判断以下序列是否是堆，若不是，把它调整为堆（要求记录交换次数最少），写出调整后的序列。

1）{ 5，26，20，60，80，35，53，70 } 2）{ 26，33，35，29，19，12，22 }

3.已知关键字序列{70，83，100，65，10，9，7，32}，写出直接插入排序和快速排序每一趟结束时的关键字状态。

4.设关键字集合为{10，2，14，8，12，13}，

(1)写出用希尔排序方法对序列排序时每一趟结束时的关键字状态。

(2)用堆排序方法对其从小到大排序，画出堆排序的初态、建堆和排序过程中重建堆的过程。

考试模拟题客观题部分

一、单项选择题：（每空2分，共20分） 1. 单链表是线性表的一种________的存储结构。 A. 顺序存取 B. 随机存取 C. 索引存取 2. 栈和队列的共同点是________。