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

《郑州大学远程教育学院数据结构试题及答案.pdf》由会员分享，可在线阅读，更多相关《郑州大学远程教育学院数据结构试题及答案.pdf（28页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、个人收集整理 仅供参考学习 郑州大学现代远程教育 数据结构课程（本科）学习指导书 郭纯一 编 个人收集整理 仅供参考学习 课程内容与基本要求“数据结构”在计算机科学中是一门综合性的专业基础课。本课程将主要介绍数据结构的基本概念和术语、非数值计算中常用的数据结构（线性表、栈和队列、串、树和图）和基本技术（查找和排序方法）三大部分。本课程要求学生在掌握线性表、栈和队列、串、树和二叉树、图等基本数据类型的基础上，会分析各种数据结构的特性，会根据应用需求为所涉及的数据合理选择适当的逻辑结构和存储结构，并能据此设计实现问题的算法；还应初步掌握算法的时间和空间效率的分析方法。课程学习进度与指导 章节 课程

2、内容 学时分配 学习指导（均以课件学习为主）第一章 绪论 4 学时 重点掌握基本概念和时间复杂度的计算方法 第二章*线性表 10学时 重点掌握顺序结构和链式结构表示线性表的方法和操作的实现；结合具体例子理解编程实现一个问题的 2 种方法 第三章 栈和队列 8 学时 重点掌握栈和队列的特点以及它们各自的存储表示，尤其是顺序栈和循环队列的实现；结合具体例子理解栈和队列的应用 第四章 串 2 学时 重点掌握串的术语、串操作结果和不同存储结构的特点 第七章*树和二叉树 10 学时 重点掌握二叉树的定义、存储、性质、遍历算法（递归）及应用、线索化；掌握树和森林与二叉树的转换以及 Huffman树和Huf

3、fman编码的构造方法 第八章 图 8 学时 重点掌握图的术语、存储、遍历算法及应用；掌握最小生成树的 2 种构造方法及特点、会求拓扑排序序列和单源最短路径 第九章*查找 8 学时 重点掌握各种动态查找表的构造过程、性能分析、插入/删除方法；掌握静态查找表的顺序、折半和分块查找及ASL求法 第十章*排序 8 学时 掌握关于排序的术语及分类方法；重点掌握插入排序、交换排序、选择排序等内排序方法及其性能分析方法 个人收集整理 仅供参考学习 第一章 绪论 一、章节学习目标与要求 1、理解数据抽象和信息隐蔽原则 2、掌握所有的基本概念和术语、掌握时间复杂度的计算方法、会用C语言描述抽象数据类型和算法；

4、能够熟练使用 C 语言编写程序 二、本章重点、难点 重点：基本概念和术语，C 语言描述算法的方式，简单程序的时间复杂度的求法。难点：时间复杂度的计算方法和原则。三、章节练习（一）选择题：1 具有线性结构的数据结构是_。A.图 B.树 C.集合 D.栈 2 计算机算法是指_。A.计算方法和运算结果 B.调度方法 C.解决某一问题的有限运算系列 D.排序方法 3 线性结构中，最后一个结点有_个后继结点。A.0 B.1 C.任意多 4.算法分析的目的是_。A.找出数据结构的合理性 B.研究算法中输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的可读性和可行性 5.具有非线性结构的数据结构是

5、_。A.图 B.线性表 C.串 D.栈 6 算法具有 5 个特性：_、_、_、输入和输出。A.稳定性、确定性、可行性 B.有穷性、确定性、可行性 C.有穷性、安全性、可行性 D.有穷性、确定性、可移植性 7 设 n 为正整数。则下面程序段的时间复杂度为_。i=1;k=0;while(i=n-1)k+=10*i;个人收集整理 仅供参考学习 i+;A.O(1)B.O(n)C.O(nlogn)D.O(n2)8 设 n 为正整数。则下面程序段的时间复杂度为_。k=0;for(i=1;i=n;i+)for(j=i;jnext=NULL;B.p=NULL;C.p-next=head;D.p=head;4

6、若在线性表的任何位置上插入元素的概率是相等的，那么在长度为n的顺序表中插入一个元素时需平均移动_个元素。A.n B.(n-1)/2 C.n/2 D.(n+1)/2 5 在带头结点的非空单链表中，头结点的位置由_指示，首元结点的存储位置由_指示，除首元结点外，其它任一元素结点的存储位置由_指示。A.头指针 B.头结点的指针域的指针 C.前驱结点的指针域的指针 6.单链表的头指针为 p，若有头结点，则表空的判断条件是_；若不带头结点，则表空的判断条件是_。A.p=NULL B.p-next=NULL C.p-next-next=NULL（二）判断题：1 在单链表中插入或删除元素时是以结点的指针变化

7、来反映逻辑关系的变化，因此不需要移动元素。（）2 顺序表能够以元素在计算机内的物理位置的相邻性来表示线性表中元素之间的逻辑关系。（）3.在不带头结点的非空单链表中，首元结点的存储位置由头指针指示，除首元结点外，其它任一元素结点的存储位置由前驱结点的指针域的指针指示。（）（三）问答题：1 若线性表要求以最快的速度存取而表中元素变动不大，则应采取什么存储结构（顺序或链式结构）？为什么？2 若线性表经常做插入/删除操作，则应采取什么存储结构？为什么？3.在单链表中设置头结点有什么作用？（四）算法题：1.设带头结点的单链表(L 为头指针)中的数据元素递增有序。设计算法，将 x 插入到链表的适当位置上，

8、并仍保持该表的有序性。个人收集整理 仅供参考学习 2.设顺序表 va 中的数据元素递增有序。设计算法，将 x 插入到顺序表的适当位置上，并仍保持该表的有序性。3.设计算法，实现单链表的就地逆置，即利用原表的存储空间将线性表（a1,a2,an）逆置为（an ,an-1,a1）。第三章 栈和队列 一、章节学习目标与要求 1、理解用栈和队列解决实际问题的方法。2、掌握栈和队列的定义以及特性、它们的 2种不同的存储表示方法（特别是顺序栈和循环队列）以及各种常见操作（如入、出操作）在不同表示方式上的实现。二、本章重点、难点 重点：栈和队列的定义、各种表示和实现方法，加深对线性结构的理解 难点：循环队列的

9、表示及为解决循环队列队空、队满判断条件相同而使用的不同实现方式；能在具体问题中灵活运用栈和队列结构。三、章节练习（一）选择题：1 一个栈的入栈序列是 a,b,c,d,e,则栈的不可能的输出序列是_。A.edcba B.decba C.dceab D.abcde 2 栈和队列的共同点是_。A.都是后进先出 B.都是先进先出 C.都是只允许在端点处插入和删除元素 D.无共同点 3 一个队列的入队序列是1,2,3,4,则队列的输出序列是_。A.4321 B.1234 C.1432 D.3241 4 栈的入栈序列是 1，2，n，输出序列为 p1,p2,pn,若 p1=n,则 pi 为_。A.i B.n

10、-i C.n-i+1 D.不确定 5 队列是限定在_进行插入，在_进行删除的线性表。A.队头 B.队尾 C.任意位置 6 循环队列中，设队列元素依次存放在 Q0.m中，f、r分别指示队头元素位置和队尾元素的下一个位置，约定存储 m 个元素时为队满。则队列空的判定方法是_,队列满的判定方法是_。个人收集整理 仅供参考学习 A.f=r B.(f+1)%(m+1)=r C.(r+1)%(m+1)=f D.(r+1)%m=f（二）判断题：1 若用户无法估计所用队列的最大长度，则最好采用链队列。（）2 在链队列上删除队头元素时，只需修改头结点中的指针，不必修改尾指针。（）3.栈是限定仅在栈顶进行插入或删

11、除操作的线性表。（）4.队列是限定在队尾插入元素，在队头删除元素的线性表。（）（三）问答与算法题：1 对于一个栈，若输入序列依次为A,B,C,试给出所有可能的输出序列。2 假设将循环队列定义为：以整型域变量 front和 length分别指示循环队列中队头元素位置和队列中元素个数，指针 elem指示存放队列元素的连续空间的首地址，写出相应的入队列和出队列的算法。第四章 串 一、章节学习目标与要求 1、理解串的抽象数据类型的定义以及相关术语、理解串在文本编辑中的作用。2、掌握字符串的定义及各种基本操作的运算结果以及串的各种存储表示的特点。二、本章重点、难点 重点：串的基本运算、串的各种存储表示和

12、特点。继续加深对线性结构的理解 难点：串的不同存储结构，区分它们和高级语言中串的存储方式的不同。三、章节练习（一）选择题：1 设串 s=I AM A STUDENT,则其串长是_。A.13 B.14 C.15 D.16 2.设 s=HE IS A WORKER,t=WORKER。则 StrIndex(s,t,5)的返回值是_。A.4 B.5 C.6 D.9 E.10 3.串是一种特殊的线性表，其特殊性体现在_。A.可以顺序存储 B.数据元素是一个字符 C.可以链接存储 D.数据元素可以是多个字符 4.已知串 s=ABCDEFGH,则 s 的所有不同子串的个数为_。A.8 B.9 C.36 D.

13、37 个人收集整理 仅供参考学习 5.设串 s=I am a teacher.,则 s 的第 8 个字符起、长度为 7 的子串为_。A.teacher.B.teacher C.a teacher D.teacher 6.设串 s=student.,t=“good ,则执行 StrInsert(s,1,t)后，s 为_。A.good student.B.good student C.goodstudent D.good teacher（二）判断题：1 空串和空格串是相同的。（）2.如果两个串含有相同的字符，则它们是相同的。（）3.串的基本操作和线性表的一样，都是以“单个元素”作为操作对象的。（）

14、4.在串的链式存储结构中，结点大小与存储密度之间没有关系。（）第七章 树和二叉树 一、章节学习目标与要求 1、理解树、二叉树和森林的概念，理解线索化二叉树的特性、创建方法及在线索二叉树上寻找某结点的前驱和后继的方法；理解树与森林的存储方法。2、掌握二叉树的性质及表示；掌握二叉树的各种遍历方法（尤其是递归形式的）以及遍历在实际问题中的应用；掌握树及森林与二叉树的转换及遍历方式的对应；掌握Huffman树的构造方法以及构造Huffman编码的方法。二、本章重点、难点 重点：二叉树的性质（及证明）、存储结构及各种遍历算法，二叉树的线索化过程，树和森林与二叉树的转换关系，Huffman树及 Huffm

15、an编码的构造方法 难点：各种遍历算法的递归实现以及在具体问题中能灵活运用遍历思想解题 三、章节练习（一）选择题：1 下列关于二叉树的说法中，正确的有 _。A.二叉树的度为2 B.二叉树的度可以小于2 C.二叉树中至少有一个结点的度为2 D.二叉树中任一个结点的度都为2 2 任何一棵二叉树的叶子结点在先、中、后序遍历序列中的相对次序_。A.不发生改变 B.发生改变 C.不能确定 D.以上都不对 3 下面几个符号串编码集合中，不是前缀编码的是_。个人收集整理 仅供参考学习 A.0，10，110，1111 B.11，10，001，101，0001 C.00，010，0110，1000 D.b,c,

16、aa,ac,aba,abb,abc 4 二叉树按某种顺序线索化后，任意结点均有指向其前驱和后继的线索，这种说法_。A.正确 B.不正确 C.无法确定（二）判断题：1.哈夫曼树是带权叶子数目固定的二叉树中带权路径长度最小的。（）2.根据二叉树的定义，具有 3 个结点的二叉树有 5 种不同的形态。（）3.深度为 k 的完全二叉树至少有 2k-1个结点，至多有 2k1 个结点。（）4.具有 n 个结点的满二叉树，其叶子结点个数为21n个。（）5.在哈夫曼树中，通常权值较大的结点离根较远。（）（三）问答题：1 下图所示森林转化为相应的二叉树，并在其上标出中序全线索。2 证明：深度为 k 的二叉树上至多

17、有 2k-1 个结点（k 1）。3.证明：任何一棵满二叉树中的分支数 B 满足 B=2(n01)，其中 n0为叶子结点个数。4.以数据集15，3，14，2，6，9，16，17为叶子的权值构造 Huffman树，画出此树并计算其带权路径长度。（四）算法题：1.假设二叉排序树（t为指向根结点的指针）中各元素值均不相同，设计一个递归算法按递增顺序输出树上各元素值。2 编写递归算法,交换二叉链表存储的二叉树中每个结点的左、右子树。个人收集整理 仅供参考学习 3.编写递归算法，求以二叉链表存储的二叉树的深度。4.设计递归算法计算以二叉链表存储的二叉树的叶子结点数目。第八章 图 一、章节学习目标与要求 1

18、、理解图的基本概念和术语。2、掌握图的邻接矩阵和邻接表 2 种表示方法；掌握图的两种遍历算法及其求解连通性问题的方法；掌握用 Prim算法和 Kruskal算法构造最小生成树的过程和性能分析；掌握 AOV网的拓扑排序方法(不要求算法)，掌握用 Dijkstra方法求解单源最短路径问题的方法(不要求算法)。二、本章重点、难点 重点：图的数组表示法和邻接表表示法存储结构以及图的两种遍历方式，求最小生成树的两种方法，AOV网的拓扑排序方法，掌握单源最短路径的求法 难点：图的两种遍历算法的实现以及在图的连通性问题中的应用 三、章节练习（一）选择题：1.4个顶点的无向完全图有_条边。A.6 B.12 C

19、.16 D.20 2 无向图的邻接矩阵是一个_。A.对称矩阵 B.零矩阵 C.对角矩阵 D.上三角矩阵 3 图的广度优先遍历算法类似于二叉树的_，图的深度优先遍历算法类似于二叉树的_。A.先序遍历 B.中序遍历 C.后序遍历 D.层序遍历 4.对_，用 Prim算法求最小生成树较为合适，而 Kruskal算法适于构造_图的最小生成树。A.完全图 B.连通图 C.稀疏图 D.稠密图 5.对于含 n 个顶点、e 条边的无向连通图，利用Prim算法构造最小生成树的时间复杂度_，用 Kruskal算法构造最小生成树的时间复杂度为_。A.O(n)B.O(n2)C.O(e)D.O(eloge)F.O(e2

20、)个人收集整理 仅供参考学习（二）判断题：1.若从无向图的一个顶点出发进行广度优先遍历可访问到图中所有顶点，则该图一定是连通图。（）2.若从无向图的一个顶点出发进行深度优先遍历可访问到图中所有顶点，则该图一定是连通图。（）3.任何有向图的顶点都可以排成拓扑有序序列，而且拓扑序列不唯一。（）4.有 n 个顶点和 n-1条边的无向图一定是生成树。（）5.一棵有 n 个顶点的生成树有且仅有 n-1条边。（）6.连通分量是无向图的极大连通子图，而生成树是无向图的极小连通子图。（）（三）问答及算法题：1.一个图的邻接矩阵G.arcs=110101010，该图有多少个顶点？如果是有向图，该图共有多少条弧？

21、如果是无向图，该图共有多少条边?2.已知如右图所示的有向图，写出该图的:(1)邻接矩阵 (2）一个可能的拓扑有序序列（3）写出从 1 出发的深度优先遍历序列 （4）写出从 5 出发的广度优先遍历序列。3.假设有 5 项活动 C1C5，每项活动要求的前驱活动如下：C1：无；C2：C1，C3；C3：C1；C4：C3，C5 C5：C2；试根据上述关系，画出相应的有向图，再写出一个拓扑排序序列。4.基于图的深度优先遍历策略写一算法，判断以邻接表方式存储的无向图中连通分量的个数。第九章 查找 一、章节学习目标与要求 1、理解各种查找表的定义、各种查找方法的思想以及构造查找表所依据的原则。2、掌握线性表表

22、示的静态查找表的顺序查找和折半查找算法及其性能分析方法；掌握二叉排序树的创建、查找、插入、删除算法及其性能分析方法；掌握 AVL树的平衡化旋转方法及其性能分析；掌握 B-树的插入和删除时结点的分裂和合个人收集整理 仅供参考学习 并方法；掌握 Hash法的查找、构造方法平均查找长度的计算方法。二、本章重点、难点 重点：各种树结构表示的动态查找表和 Hash表的构造方法 难点：二叉排序树的删除、AVL树的旋转处理、B-树的插入和删除、Hash法的构造以及各种查找表的平均查找长度的计算方法 三、章节练习（一）选择题：1._二叉排序树可得到一个关键字的有序序列。A.先序遍历 B.中序遍历 C.后序遍历

23、 D.层序遍历 2 用链地址法处理冲突构造的散列表中，每个地址单元所链接的同义词表中结点的_相同。A.关键字 B.元素值 C.散列地址 D.含义 3 利用折半查找方法在长度为 n 的有序表中查找一个元素的平均查找长度是_。A.O(n2)B.O(nlogn)C.O(n)D.O(logn)4 散列表的装填因子越大，则发生冲突的可能性就_。A.越小 B.越大 C.不确定 5 线性表中共有 256个元素，采用分块查找，若查找每个元素的概率相等，用顺序查找确定结点所在的块，每块有_个元素时查找效率最佳。A.16 B.20 C.25 D.256 6 用折半查找对长度为 7 的有序表进行查找，则等概率下查找

24、成功时的平均查找长度为_。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 D.5（二）判断题：1.折半查找和二叉排序树的查找时间性能一样。（）2.在任意一棵非空的二叉排序树中，删除某结点后又将其插入，则所得的二叉个人收集整理 仅供参考学习 排序树与删除前的二叉排序树形态相同。（）3.根据 B-树的定义，在 9 阶 B-树中，除根以外的任何一个非叶子结点中的关键字数目均在 5 9 之间。（）4.折半查找时，要求线性表必须是

25、有序的且以顺序结构存储。（）（三）问答题：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.关键字序列：1

26、3，28，72，5，16，18，7，11，24，h(key)=key mod 11,表长为 11，用线性探测再散列处理冲突，试填写下表并计算每个关键字的比较次数和等概率情况下查找成功时的平均查找长度。4.在地址空间为 0-16的散列区中，对以下关键字序列(Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec)按链地址法处理冲突构造散列表，设散列函数H(x)=i/2,其中 i 为关键字中第一个字母在字母表中的序号。画出该散列表并求在等概率情况下查找成功时的平均查找长度。第十章 排序 一、章节学习目标与要求 1、理解排序相关的定义以及排序方法的各种分类

27、，理解各种排序方法的基本思想和依据原则。2、掌握内部排序的基本概念和性能分析方法；掌握插入排序、交换排序、选择排序等内排序的方法及其性能分析方法。0 1 2 3 4 5 6 7 8 9 10 哈希表 比较次数 ASL=个人收集整理 仅供参考学习 二、本章重点、难点 重点：各类内部排序方法所依据的原则、特点及典型算法。难点：希尔排序、快速排序、堆排序 三、章节练习（一）选择题：1.下列方法中，_是稳定的排序方法。A 堆排序 B.希尔排序 C.快速排序 D.折半插入排序 2.设有 1000个无序的元素，希望用最快的速度选出其中前20个最大的元素，最好用_排序方法。A.冒泡排序 B.快速排序 C.堆

28、排序 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，

29、则其使用的排序方法为_。A.插入排序 B.选择排序 C.快速排序 D.起泡排序 7.下列方法中，_算法的时间复杂度为 O(n2)。A.堆排序 B.希尔排序 C.快速排序 D.直接插入排序 8.对 n 个记录的序列进行堆排序，最坏情况下的时间复杂度为_。A.O(logn)B.O(nlogn)C.O(n)D.O(n2)（二）判断题：1.快速排序的速度在所有排序方法中是最快的，而且所需的附加空间也最少。（）2.对一个堆按层次遍历，不一定能得到一个有序序列。（）3.由于希尔排序的最后一趟与直接插入排序过程相同，所以前者一定比后者花费个人收集整理 仅供参考学习 的时间多。（）4.快速排序算法在待排序数据

30、有序时最不利于发挥其长处。（）（三）问答题：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)写出用希尔

31、排序方法对序列排序时每一趟结束时的关键字状态。(2)用堆排序方法对其从小到大排序，画出堆排序的初态、建堆和排序过程中重建堆的过程。考试模拟题 客观题部分 一、单项选择题：（每空 2 分，共 20 分）1.单链表是线性表的一种_的存储结构。A.顺序存取 B.随机存取 C.索引存取 2.栈和队列的共同点是_。A.都是后进先出 B.都是先进先出 C.都是只允许在端点处插入和删除元素 D.无共同点 3.设 s=HE IS A WORKER,t=WORKER。则 index(s,t,5)的返回值是_。A.4 B.5 C.6 D.9 E.10 4.串是一种特殊的线性表，其特殊性体现在_。个人收集整理 仅供

32、参考学习 A.可以顺序存储 B.数据元素是一个字符 C.可以链接存储 D.数据元素可以是多个字符 5 树最适合用来表示_。A.有序数据元素 B.无序数据元素 C 元素之间具有分支层次关系的数据 D.元素之间无关联的数据 6 4 个顶点的无向完全图有_条边。A.6 B.12 C.16 D.20 7 散列表的装填因子越大，则发生冲突的可能性就_。A.越小 B.越大 C.不确定 8.在长度为 n 的有序表中折半查找一个元素的平均查找长度是_。A.O(n2)B.O(nlogn)C.O(n)D.O(logn)9.下列方法中，_是不稳定的排序方法。A.折半插入排序 B.直接插入排序 C.冒泡排序 D.堆排

33、序 10_二叉排序树可得到一个关键字的有序序列。A.先序遍历 B.中序遍历 C.后序遍历 D.层序遍历 二、是非题：（每题 1 分，共 10 分）（说明：正确的选“A”,错误选“B”）1 线性表的顺序存储结构优于链式存储结构。（）2 空串和空格串是相同的。（）3 图结构中，每个结点的前驱和后续都可以有任意多个。（）4 快速排序算法在待排序数据有序时最不利于发挥其长处。（）5 连通网的最小生成树是唯一的。（）6 栈是 FIFO的线性表。（）7 由二叉树的先序和后序遍历序列不能唯一确定这棵二叉树。（）8 若从无向图的一个顶点出发进行广度优先遍历可访问到图中的所有顶点，则该图一定是连通图。（）9 折

34、半查找方法要求查找表必须是关键字的有序表，但是对存储结构没有限制。（）10 在一棵非空二叉树的中序遍历序列中，根结点的右边只有其右子树上的所有结点。（）个人收集整理 仅供参考学习 主观题部分 一、简答题：（50 分）1.若线性表要求以最快的速度存取而表中元素变动不大，则应采取什么存储结构（顺序或链式结构）？为什么？（10 分）2.将下图所示森林转化为二叉树并在其上标出中序全线索。（10 分）3.已知如右图所示的有向图，写出该图的:(1)邻接矩阵(2）一个可能的拓扑有序序列。（10 分）4 设散列函数H(key)=key MOD 7,用线性探测再散列法解决冲突。对关键字序列 13，28，72，5

35、，16，8，7，9，11，29 在地址空间为 0-10的散列区中建散列表，画出此表，并求等概率情况下查找成功时的平均查找长度。（10 分）5 对于序列 26，33，35，29，19，12，22，（1）判断它是否是堆，若是，写出其是大顶堆还是小顶堆；若不是，把它调整为堆，写出调整的过程和调整后的序列。（5 分）（2）写出对该序列进行直接插入排序每一趟结束时的关键字状态。（5 分）二、算法设计题：（20 分）1、编写递归算法，计算二叉链表存储的二叉树的结点数目。（10 分）2、基于图的深度优先遍历策略写一算法，判断以邻接表方式存储的无向图中连通分量的个数。（10 分）个人收集整理 仅供参考学习 附

36、：答案或答案要点 第一章章节练习答案（一）选择题：1D 2C 3A 4C 5A 6B 7B 8D（二）判断题：1 2 3.4 第二章章节练习答案（一）选择题：1B,A 2C 3C 4C 5A,B,C 6.B,A（二）判断题：1 2 3（三）问答题：1 应采用顺序结构。因为顺序表是随机存取的存储结构，在顺序表中存取任何元素所花的时间都一样。而链表是顺序存取的存储结构。2应采用链式结构。因为在链表中是以结点的指针变化来反映逻辑关系的变化，因此不需要移动元素，效率高。3头结点在位置上可视为首元结点的前驱，则做插入/输出操作时，i=1（即插入或删除的位置是 1）时不需要做特别处理，否则 i=1时需要修

37、改头指针。（四）算法题：1 status insert_L(LinkList L,ElemType x)/*带头结点*/LinkList p,s;for(p=L;p-next&p-next-datanext);s=(LinkList)malloc(sizeof(LNode);if(!s)return OVERFLOW;s-data=x;s-next=p-next;p-next=s;return OK;2status insert_Sq(SqList*va,ElemType x)int i;if(va-length=va-listsize)exit OVERFLOW;个人收集整理 仅供参考学习

38、for(i=va-length-1;i=0&va-elemix;-i)va-elemi+1=va-elemi;va-elemi+1=x;va-length+;return OK;3void reverse(LinkList L)/*带头结点*/LinkList p;p=L-next;L-next=NULL;for(;p;p=p-next)q=p-next;p-next=L-next;L-next=p;第三章章节练习答案（一）选择题：1.C 2.C 3.B 4.C 5.B,A 6.A，C（二）判断题：1 2 3 4（三）问答与算法题：1所有可能的输出序列有：ABC、ACB、BAC、BCA、CBA

39、 2算法：#define MAXQSIZE 100 typedef struct ElemType*elem;int front;int length;CycQueue;status EnQueue(CycQueue*Q,ElemType e)个人收集整理 仅供参考学习 if(Q-length=MAXQSIZE)return ERROR;Q-elem(Q-front+Q-length)%MAXQSIZE=e;Q-length+;return OK;status DeQueue(CycQueue*Q,ElemType*e)if(Q-length=0)return ERROR;*e=Q-elemQ

40、-front;Q-length-;return OK;第四章章节练习答案（一）选择题：1.B 2.D 3.B 4.D 5.B 6.A（二）判断题：1.2.3.4.第七章章节练习答案（一）选择题：1.B 2.A 3.B 4.B（二）判断题：1.2.3.4.5.（三）问答题：1 个人收集整理 仅供参考学习 2证明：由于深度为 k 的二叉树的最大结点数为二叉树上每一层的最大结点数之和，而二叉树上第 i 层的最大结点数为 2i-1。则 122)i(1k1i1-ikki层的最大结点数第 3.证明：设 n0为叶子结点个数，n2为度为 2 的结点个数，则由二叉树的性质 2 可知：n2=n01 又：满二叉树中

41、只有度为 2 的结点和叶子结点，所以满二叉树中的结点总数 n=n2+n0=2 n01 又：二叉树中的分支数 B=n1 所以：B=2 n011=2(n01)4.wpl=(16+17)*2+(9+14+15)*3+6*4+(2+3)*5=229（四）算法题：1 void output(BiTree t)if(t)output(t-lchild);printf(t-data);output(t-rchild);个人收集整理 仅供参考学习 2.void exchange(BiTree t)BiTree temp;if(t)temp=t-lchild;t-lchild=t-rchild;t-rchild

42、=temp;exchange(t-lchild);exchange(t-rchild);3.int depth(BiTree t)int l,r;if(!t)return 0;l=depth(t-lchild);r=depth(t-rchild);return(l=r?l:r)+1;4.void leaf(BiTree t)if(!t)return 0;if(!t-lchild&!t-rchild)return 1;return leaf(t-lchild)+leaf(t-rchild);第八章章节练习答案（一）选择题：1.A 2.A 3.D,A 4.D,C 5.B,D（二）判断题:1.2.3

43、.4.5.6.（三）问答及算法题：1.图中共有 3 个顶点，如果是有向图，该图共有5 条弧；如果是无向图，该图共有 3 条边。个人收集整理 仅供参考学习 2.（1）邻接矩阵：001000100010000000001000000100000010（2）可能的拓扑序列为：156234（注意 4 一定是最后一个，2 一定在 1 和 5 后）（3）123456（4）562431 3.一个拓扑排序序列：C1 C3 C2 C5 C4 4算法：int count(AlGraph G)for(i=0;iG.vexnum;i+)visitedi=false;sum=0;for(i=0;inextarc)k=p

44、-adjvex;if(!visitedk)dfs(G,k);个人收集整理 仅供参考学习 第九章章节练习答案（一）选择题：1.B 2.C 3.D 4.B 5.A 6.B 7.B（二）判断题：1.2.3.4.（三）问答题：(3)删除 55:删除 84:2 ASL=(1+1+1+2+5+1+1+4)/8=16/8=2 3.1.（1）ASL=(1+2*2+3*3+3*4+2*5)/11=36/11 (2)2_3 树:个人收集整理 仅供参考学习 ASL=（1+1+2+1+1+2+4+3+4）/9=19/9 4.用链地址法处理冲突:（注意链表的有序性）ASL=(7*1+4*2+1*3)/12=18/12

45、第十章章节练习答案（一）选择题：1.D 2.C 3.A 4.A 5.D 6.C 7.D 8.B（二）判断题：1.2.3.4.（三）问答题：1应依据“三者取中”的原则，比较第一个、最后一个和中间位置处记录的关键字，取关键字居中值的记录作为枢轴记录。2第一个序列是堆 第二个序列不是堆。调整为堆后的序列为35，33，26，29，19，12，22 3初始序列：70，83，100，65，10，9，7，32 直接插入排序每一趟结束时的关键字状态：第一趟：（70，83），100，65，10，9，7，32 第二趟：（70，83，100），65，10，9，7，32 第三趟：（65，70，83，100），10，9

46、，7，32 第四趟：（10，65，70，83，100），9，7，32 第五趟：（9，10，65，70，83，100），7，32 3、0 1 2 3 4 5 6 7 8 9 10 哈希表 11 13 24 5 28 72 16 18 7 比较次数 1 1 2 1 1 2 4 3 4 个人收集整理 仅供参考学习 第六趟：（7，9，10，65，70，83，100），32 第七趟：（7，9，10，32，65，70，83，100）快速排序每一趟结束时的关键字状态：初始序列：70，83，100，65，10，9，7，32 第一趟：（32，7，9，65，10），70，（100，83）第二趟：（10，7，9），

47、32，（65）第三趟：83，(100)第四趟：(9，7)，10 第五趟：7，9，10，32，65，70，83，100 输出 14 之后再建堆：13 12 10 8 2 14 输出 13 之后再建堆：12 8 10 2 13 14 输出 12 之后再建堆：10 8 2 12 13 14 输出 10 之后再建堆：8 2 10 12 13 14 输出 8 之后再建堆：2 8 10 12 13 14有序 考试模拟题答案 客观题部分：一、单项选择题：1.A 2.C 3.D 4.B 5.C 6.A 7.B 8.D 9.D 10.B 二、判断题：1.B 2.B 3.A 4.A 5.B 6.B 7.A 8.A

48、 9.B 10.A 主观题部分：一、简答题：4 （1）希尔排序：d1=3:8 2 13 10 12 14 d2=2:8 2 12 10 13 14 d3=1:2 8 10 12 13 14(2)堆排序初态:10，2，14，8，12，13 建堆:14 12 13 8 2 10 个人收集整理 仅供参考学习 1.应采用顺序结构。因为顺序表是随机存取的存储结构，在顺序表中存取任何元素所花的时间都一样。而链表是顺序存取的存储结构。2.3.001000100010000000001000000100000010 可能的拓扑序列为：156234（注意 4 一定是最后一个，2 一定在 1 和 5 之后）4.A

49、SL=(1+1+1+2+5+1+1+4)/8=16/8=2 5.(1)该序列不是堆。原始序列：26，33，35，29，19，12，22 交换 26 和 35，建大顶堆：35，33，26，29，19，12，22 （2）直接插入排序过程：原始序列：（26），33，35，29，19，12，22 i=2：（26，33），35，29，19，12，22 i=3：（26，33，35），29，19，12，22 i=4：（26，29，33，35），19，12，22 个人收集整理 仅供参考学习 i=5：（19，26，29，33，35），12，22 i=6：（12，19，26，29，33，35），22 i=7：（12，19，22，26，29，33，35）二、算法设计题：1.int nodes(BiTree T)if(!T)return 0;return nodes(T-lchild)+nodes(T-rchild)+1;2.int count(AlGraph G)int i,sum;for(i=0;iG.vexnum;i+)visitedi=false;sum=0;for(i=0;inextarc)k=p-adjvex;if(!visitedk)dfs(G,k);