郑州大学远程教育学院大数据结构精彩试题及问题详解

1、大学现代远程教育数据结构课程（本科）学习指导书郭纯一编 课程容与基本要求“数揭结构”在计算机科学中足一门综合性的专业基础课。本课程将主要介 绍数据结构的基本概念和术语、非数值计算中常用的数JS结构（线性表、栈和队 列、串、树和图）和基本技术（查找和排序方法）三大部分。本课程要求学生在学握线性表、栈和队列、串、树和二叉树、图等基本数揭 类型的基础上，会分析各种数据结构的特性.会根拯应用需求为所涉及的数拯合 理选择适当的逻辑结构和存储结构，并能据此设计实现问題的算法；还应初步学 握算法的时间和空间效率的分析方法。 课程学习进度与扌旨导拿节课程容学时分配学习扌旨导（均以课件学习为主）笫一拿绪论4学时

2、重点掌握基本概念和时间复杂皮的计算方法笫二拿*线性表10学时重点学握顺序结构和谜式结构表示线性 表的方法和操作的实现；结合具体例子理 解编程实现一个问題的2种方法第三拿栈和队列8学时重点学握栈和队列的特点以及它们各自 的存储表示. 尤其足顺序栈利循环队列的 实现；结合具体例子理解栈利队列的应用笫四拿串2学时董点学握串的术J吾、串操作结果和不同存 储结构的特点笫七拿*树和二叉树10学时董点学握二叉树的定义、存储.性质、遍 历算法（递归）及应用、线索化；学握树 和孤林与二叉树的转换以及Huffman树利 Huffman编码的构造方法第八拿图8学时董点学握图的术语、存储、遍历算法及应 用：学握最小生

3、成树的2种构造方法及特 点.会求拓扑排序序列和单源最短路径笫九拿*查找8学时董点学握各种动态査找表的构适过程、性 能分析、插入/删除方法；学握静态查找表 的顺序、折半和分块査找及 ASL求法笫十拿*排序8学时学握关于排序的术语及分类方法；至点学 握插入排序、交换排序、选择排序等排序 方法及其性能分析方法一、拿节学习目标与要求1 V理解数摇抽象和信息隐蔽原则2、学握所有的基本概念和术语、学握时间复杂度的计算方法、会用C语言描述抽象数揭类盘和算法；能够熟练使用 C语言编写程序二、本拿重点、难点車点：基本概念和术语，C语言描述算法的方式.简单程序的时间复杂度的求法。难点：时间复杂度的计算方法和原则。

4、三、拿节练习（一）选择题：1 具有线性结构的数揭结构是oA.图B.树 C.桨合 D.栈2. 计算机算法是扌旨oA 计算方法和运算结果B.调度方法C.解决某一问題的有限运算系列D.排序方法3. 线性结构中. 最后一个结点有个后继结点°A. O B. 1 C.任愆多4. 算法分析的目的足。A. 找出数揭结构的合理性C.分析算法的效率以求改进5. 具有非线性结构的数揭结构足A.图B.线性表 C.串6. 葬法具有5个特性：、A. 稳定性、确定性、可行性C.有穷性、安全性、可行性7. 设n为正隹数B. 研究算法中输入和输出的关系D.分析算法的可诔性和可行性D.栈、输入和输出B. 有穷性、确定性

5、、可行性D.有穷性、确定性、可移植性则下面程序段的时间复杂皮为i=l; k=0;while(i<=n-l)k+=10*i;i+；爸减沖I扁朋霭蠶)A.O(l) B. O(n) C. O(nlogn) D. O(n2)8.设n为正進数。则下面程序段的时间复杂度为。k=0;for(i=l;i<=n;i+)for(j=i;j<=n;j+)k+;)A.O(l) B. O(n) C. O(nlogn) D. O(n2)(二) 判断题：1. 在数JS结构中.从逻辑上可以把数结构分为动态结构利静态结构两大类。()2. 任何一个算法的设计取决于数摇的逻辑结构.而算法的实现则依赖于所采用的存储

6、结构。()3. 数揭元素是数摇的不可分割的最小单位。()4. 算法分析的两个主要方面是时间复杂度利空间复杂度。()第二章址性表一、拿节学习目标与要求1、理解线性表的逻楫结构特性、顺序表和傩表表示线性表的优缺点、循环链表 和双向ta表的特点。2、学握线性表的两种存储方式及其实现：熟练学握顺序表和链表的创理、插入元素、删除元素以及定位等常用操作的实现算法并会求相应算法的时间复杂度。二、本拿重点、施点至点：线性表的特点、两种表示方式及它们的运算实现，会求算法的时间复杂皮。难点：单链表结构、特点及其实现三、拿节练习(一) 选择题：1. 顺序表足一种的存储结构，单谜表是的存储结构。A顺序存取B.随机存取

7、C.索引存取2. 顺序表中第一个元素的起始存储地址为100,每个元素的长度为4,则笫五个元素的起始地址是。A. 105B. 110C. 116D. 1203. 非空循环单谜表（head为头指针）的屋结点（由扌旨针p所扌旨示）应满足oA. p->next=NULL; B. p二二NULL; C. p->next=head; D. p=head;4. 若在线性表的任何位宜上插入元索的概率足相等的，那么在长度为n的顺序表中插入一个元素时需平均移动个元素。A. nB. （n-1 ）/2C.n/2D. （n+l）/25. 在带头结点的非空单链表中. 头结点的位狙由扌&示. 首元结点的

8、存储位S.由折示，除首元结点外. 其它任一元素结点的存储位迢由描示。A.头扌旨针 B.头结点的扌旨针域的扌旨针C.前驱结点的指针域的指针6. 单链表的头扌旨针为p,若有头结点，则表空的判断条件是;若不带头结点.则表空的判断条件足oA. p=NULL B. p->next=NULL C. p->next->next=NULL（二）判断题：1. 在单K表中插入或删除元素时足以结点的描针变化来反映逻辑关系的变化.因此不需要移动元素°（）2. 顺序表能够以元素在计算机的物理位狙的相邻性来表示线性表中元素之间的逻辑关系°（）3在不带头结点的非空单谜表中.首元结点的存

9、储位迢由头指针指示，除首元结 点外. 其它任一元素结点的存储位迢由前驱结点的扌旨针域的扌旨针扌旨示。（）（三）问答题：1. 若线性表要求以最快的速皮存取而表中元素变动不大.则应采取什么存储结构（顺序或链式结构）？为什么？2. 若线性表经常做插入/删除操作，则应采取什么存储结构？为什么？3. 在单憊表中设宜头结点有什么作用？（四）算法题：1 设带头结点的单链表（L为头扌&针）中的数揭元素递增有序。设计算法，将 x插 入到怯表的适当位宜上. 并仍保持该表的有序性。2设顺序表va中的数揭元素递&有序。设计算法，将x插入到顺序表的适当位狙 上，并仍保持该表的有序性。營减同I朋朋霭蠶3设

10、计算法，实现单谜表的就地逆宜.即利用原表的存储空间将线性表(“142,an)逆置为(an,ani/*%ai)0第三章栈和队列一、拿节学习目标与要求1、理解用栈和队列解决实际问题的方法。2、学握栈和队列的定义以及特性、它们的2种不同的存储表示方法(特别是顺 序栈和循环队列)以及各种席见操作(如入、出操作)在不同表示方式上的实现。二、本拿至点、晅点重点：栈和队列的定义、各种表示和实现方法，加深对线性结构的理解难点：循环队列的表示及为解决循环队列队空、队满判断条件相同而使用的不同 实现方式；能在具体问题中灵活运用栈和队列结构。三、拿节练习(一) 选择题：1. 一个栈的入栈序列足abc,d©

11、则栈的不可能的输出序列足oA.edeba B.decba C.dceabD.abcde2. 栈和队列的共同点是oA.祁是后进先出B.都是先进先出C. 祁足只允许在端点处插入利删除元素 D.无共同点3. 个队列的入队序列足 123,4.则队列的输出序列是oA. 4321 B. 1234 C. 1432 D. 32414. 栈的入栈序列足1, 2,，nf输出序列为pl,p2,pn.若pl二n,贝！J pi为。A. i B. n-i C. n-i+1 D.不确定5. 队列足限定在进行插入，在进行删除的线性表。A.队头 B.队尾 C.任意位迟6. 循环队列中，设队列元素依次存放在 QOm中，f、I分别

12、扌旨示队头元索位鱼和队尾元素的下一个位狙.约定存储 m 个元素时为队满。则队列空的判定方法 是，队列满的判定方法是oA.f=r B. (f+l)%(m+l)=r C. (i+l)%(m+l)=f D. (r+1)% m=f(二) 判断题：F轴I朋朋霭蠶1. 若用户无法估计所用队列的瑕大长度.则最好采用ta队列。()2. 在谜队列上删除队头元素时，只船修改头结点中的扌&针，不必修改屋指针。()3. 栈足限定仅在栈顶进行插入或删除操作的线性表。()4. 队列是限定在队尾插入元素.在队头删除元素的线性表。()(三) 问答与葬法题：1. 对于一个栈. 若输入序列依次为A,B,C,试给出所有可能

13、的输出序列。2. 假设将循环队列定义为：以生型域变front和length分别扌&示循环队列中队 头元素位迢和队列中元素个数，扌旨针 elem扌旨示存放队列元索的连续空间的首地 址，写出相应的入队列和出队列的算法。第四章审一、拿节学习目标与要求1、理解串的抽象数拯类魁的定义以及相关术语、理解串在文本编碌中的作用。2、学握字符串的定义及各种基本操作的运算结果以及串的各种存储表示的特点。二、本拿重点、难点重点：串的基本运算、串的各种存储表示和特点。继续加深对线性结构的理解 难点：串的不同存储结构， 区分它们和髙级语言中串的存储方式的不同。三、拿节练习(一) 选择题：1. 设串s=HI AM

14、 A STUDENT",则其串长足oA. 13 B. 14 C. 15 D. 162. 设 s ="HE IS A WORKER"，匸”WORKER"。贝！J Strlndex(s,t,5)的返回值是。A. 4B.5 C. 6 D. 9 E. 103. 串是一种特殊的线性表. 其特殊性体现在oA.可以顺序存储 B.数揭元素是一个字符C. 可以存储 D.数揭元素可以是多个字苻4已知串sM'ABCDEFGH 则s的所有不同子串的个数为。A. 8B.9 C. 36 D. 375设串s=MI am a teacher/，则s的笫8个字符起、长度为7的子串

15、为oA. Mteacher. H B. HteacherH C. Ha teacher11 D. M teacher*1營减同I朋朋霭蠶6设串 s=Hstudent/t= “good -则执行 Strlnsert(sj,t)后.s 为。A"good student.nB. ''good studentnC. HgoodstudentHD. H good teacher11(二) 判断题：1. 空串和空格串足相同的。()2. 如果两个串含有相同的字符，则它们是相同的。()3. 串的基本操作和线性表的一样.都是以“单个元素”作为操作对象的。 ()4. 在串的链式存储结构中

16、. 结点大小与存储密度之间没有关系。()第七章材和二又材一、拿节学习目标与要求1、理解树、二叉树和探林的槪念. 理解线索化二叉树的特性、创理方法及在线 索二叉树上寻找某结点的前驱和后继的方法；理解树与孤林的存储方法。2、掌握二叉树的性质及表示；学握二叉树的各种迪历方法(尤其足递归形式的) 以及遍历在实际问题中的应用；掌握树及孤林与二叉树的转换及遍历方式的对 应；掌握Huffman树的构造方法以及构造 Huffman编码的方法。二、本拿重点、施点至点：二叉树的性质(及证明)、存储结构及各种遍历算法，二叉树的线索化过 程. 树和探林与二叉树的转换关系.Huffman树及 Huffman编码的构造方

17、法 难点：各种遍历算法的递归实现以及在具体问題中能灵活运用迪历思葱解題三、拿节练习(一) 选择題：1. 下列关于二叉树的说法中，正确的有oA.二叉树的度为2 B.二叉树的度可以小于2C二叉树中至少有一个结点的度为2D.二叉树中任一个结点的懐都为22. 任何一棵二叉树的叶子结点在先、中、后序適历序列中的相对次序oA. 不发生改变B.发生改变 C. 不能确定 D.以上都不对3. 下面几个符号串编码槊合中，不足前缀编码的足oA. 0, 10f 110, 1111 B. llt 10, 001, 101, 0001)C. 00. 010. 0110, 1000 D. b,c5aa,ac,aba,abb

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

19、 ）o3. 证明：任何一棵满二叉树中的分支数 B满足 B=2（n0- 1）, 其中n（）为叶子结点 个数。4以数揭柔15, 3, 14, 2, 6, 9, 16, 17为叶子的权值构造 Huffman树，画 出此树并计算其带权路径长度。（四）算法题：1 假设二叉排序树（t为指向根结点的指针）中各元素值均不相同，设计一个递 归算法按递增顺序输出树上各元素值。2. 编写递归葬法，交换二叉谜表存储的二叉树中毎个结点的左、右子树°3. 编写递归算法. 求以二叉链表存储的二叉树的深度。4. 设计递归算法计算以二叉链表存储的二叉树的叶子结点数目。一、拿节学习目标与要求1、理解图的基本概念和术语。

20、2、学握图的邻接矩阵和邻接表2种表示方法；学握图的两科遍历算法及其求解 连通性问题的方法；掌握用Prim 葬法和 Kniskal算法构造最小生成树的过程和性 能分析；学握 AOV网的拓扑排序方法（不要求算法），学握用 Dijkstra方法求解 单源瑕短路径问题的方法（不要求葬法）。二、本拿至点、晅点車点：图的数组表示法和邻接表表示法存储结构以及图的两种適历方式. 求最小 生成树的两种方法，AOV网的拓扑排序方法，学握单源最短路径的求法 难点：图的两种迪历算法的实现以及在图的连通性问题中的应用 三、拿节练习（一）选择题：1. 4个顶点的无向完全图有条边。D. 20D.上三甬矩阵A. 6B. 12

21、C. 162. 无向图的邻接矩阵是一个oA.对称矩阵B.零矩阵 C.对甬矩阵3. 图的广度优先遍历算法类似于二叉树的,图的深度优先遍历算法类似于二叉树的oA.先序適历B.中序適历 C.后序遍历 D.层序遍历4.对.用 Prim 算法求最小生成树较为合适.而 Kruskal葬法适于构造图的最小生成树。A.完全图 B.连通图 C.稀疏图D.稠密图5. 对于含n个顶点、e条边的无向连通图.利用Prim 算法构造最小生成树的时间复杂ZK,用Kruskal算法构造垠小生成树的时间复杂度为A. O(n) B. O(n2) C. O(e) D. O(eloge) F. O(e2)（二）判断题：1. 若从无向

22、图的一个顶点出发进行广度优先適历可访问到图中所有顶点，则该图贝!J该图2. 若从无向 图的一个顶点出发进行深度优先適历可访问到图中所有顶点.3. 任何有向图的顶点祁可以排成拓扑有序序列，而且拓扑序列不唯一。4. 有n个顶点和n-1条边的无向图一定足生成树。5. 一棵有n个顶点的生成树有且仅有n-1条边°6 连通分好足无向图的极通子图.而生成树足无向图的极小连通子图。（三）问答及算法题：1. 一个图的邻接矩阵G.arcs=, 该图有多少个顶点？如果足有向图. 该图共有多少条弧？如果是无向图. 该图共有多少条边？2已知如右图所示的有向图.写出该图的：（1）邻接矩阵（2） 个可能的拓扑有序

23、序列（3）写出从1出发的深度优先遍历序列 （4）写出从5出发的广度优先遍历序列。3假设有5项活动ClC5,毎项活动要求的前驱活动如下：C1:无；C2: Cl, C3;C3: Cl; C4: C3, C5 C5: C2;试根据上述关系，画出相应的有向图，再写出一个拓扑排序序列。4. 基于图的深度优先適历策略写一算法，判断以邻接表方式存储的无向图中连通第九章 左找一、拿节学习目标与要求1、理解各种査找表的定义、各种查找方法的思越以及构造查找表所依揺的原则。2、学握线性表表示的静态査找表的顺序査找和折半查找算法及其性能分析方法; 学握二叉排序树的创理、查找、插入、删除算法及其性能分析方法；掌握 AV

24、L 树的平衡化施转方法及其性能分析；掌握 B树的插入和删除时结点的分裂和合 并方法；学握 Hash法的查找、构造方法平均查找长皮的计算方法。二、本拿重点、婕点 裁細I朋霜打蠶' _ .車点：各种树结构表示的动态査找表和Hash表的构造方法难点：二叉排序树的删除、AVL树的旋转处理、B树的插入和删除、Hush法的构 造以及各种査找表的平均査找长度的计算方法三、拿节练习(一) 选择题：1. 二叉排序树可得到一个关键字的有序序列。A.先序迪历 B.中序遍历C.后序迪历D.层序遍历2. 用谜地址法处理冲突构造的散列表中，毎个地址单元所的同义词表中结点的相同oA.关键字 B.元素值 C.散列地址

25、D.含义3. 利用折半查找方法在长度为n的有序表中查找一个元素的平均查找长皮是OA.O(n2) B.O(nlogn) C.O(n) D. O(logn)4. 散列表的装填因子越大.则发生冲突的可能性就oA.越小B.越大C.不确定5. 线性表中共有256个元素，采用分块查找，若查找毎个元素的概率相等.用顺序査找确定结点所在的块，毎块有个元索时査找效率最佳oA. 16 B. 20 C. 25 D. 2566. 用折半查找对长度为7的有序表进行査找.则等概率下查找成功时的平均査找长度为oA. 15/7 B. 17/7 C. 18/7 D. 19/77. 有序表(1. 32, 41, 45, 62,

26、75. 77, 82, 95, 100),使用折半查找关键字为95的元素时，需要经过次比较后才能查找成功。A. 2 B. 3C.4D.5(二) 判断题：1. 折半査找和二叉排序树的査找时间性能一样。()2. 在任意一棵非空的二叉排序树中.删除某结点后又将其插入，则所得的二叉排序树与删除前的二叉排序树形态相同。()3. 根揺 B树的定义，在9阶 B-树中，除根以外的任何一个非叶子结点中的关键字数目均在5一9之间。()4折半査找时.要求线性表必须是有序的且以顺序结构存储°()(三) 问答题：1 设有一组关键字序列19, 1, 23, 14, 55, 20, 84, 27, 6&

27、11, 40,(1) 按表中元素顺序构造一棵二叉排序树. 画出这棵树. 并求其在等概率情况下査找成功时的平均査找长度。(2) 从空树开始. 按表中元索顺序构造一棵2_3树(3阶 B_树). 若此后再删除55, 84,画出毎一步执行后2_3树的状态。2.设散列函数 H(key)二key MOD 7.用线性探测再散列法解决冲突。对关键字序列 13, 2& 72. 5, 16, & 7, 11 在地址空间为010的散列区中理散列表， 画出此表. 并求等概率T卉况下査找成功时的平均査找长度°3关键字序列：13, 2& 72, 5, 16, 18, 7. 11, 24.

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

29、理解各种排序方法的基本思 惣和依揭原则。2、学握部排序的基本概念和性能分析方法；学握插入排序、交换排序、选择排 序等排序的方法及其性能分析方法。二、本拿重点、滩点 車点：各类部排序方法所依揭的原则、特点及典空算法。难点：希尔排序、快速排序、堆排序三、拿节练习(一)选择題：1. 下列方法中.足稳定的排序方法。A.堆排序 B.希尔排序 C.快逑排序 D.折半插入排序2. 设有1000个无序的元素.希坠用最快的速皮选出其中前20个最大的元素.最好用排序方法。A.百泡排序B.快速排序C.堆排序D.希尔排序3. 下列序列中，足堆。A.12, 35, 20, 60, 40, 30) B. 100, 85,

30、 120, 38, 10, 9, 36)C. 1, 5, 6, 24, 7, 3, 4 ) D.3& 24, 15, 20, 30, 46)4. 在待排序的元素序列基本有序时. 效率最髙的排序方法足oA.插入排序B.选择排序C.快速排序D.归并排序5. 在下列排序方法中，某一趟结束后朱必能选出一个元索放在其最终位宜上的是OA.堆排序 B.起泡排序C.快速排序D.直接插入排序6 对序列22,86,19,49,12,30,65,35,18进 行一趟 排序后 得到的 结果为18,12,19,22,49,30,65,35,86,则其使用的排序方法为oA.插入排序 B.选择排序 C.快速排序 D

31、.起泡排序7下列方法中. 算法的时间复杂度为 O(n2)oA.堆排序 B.希尔排序 C.快速排序 D.克接插入排序8. 对n个记录的序列进行堆排序. 最坏情况下的时间复杂皮为oA. O(logn) B. O(nlogn) C. O(n) D.O(n2)(二)判断题：1. 快逑排序的逑度在所有排序方法中是最快的，而且所希的附加空间也最少。()2对一个堆按层次適历，不一定能得到一个有序序列。()3由于希尔排序的最后一粗与直接插入排序过程相同，所以前者一定比后者花费 的时间多°()4 快逑排序算法在待排序数甥有序时最不利于发挥其长处。(三) 问答题：1在快速排序过程中，通常取序列中的第1个

32、记录作为枢轴，以它为“分界线” 重排其余记录。但当初始记录序列按关键字有序或基本有序时，快速排序将蜕化 为起泡排序，为改进之. 应如何选取枢轴记录？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, & 12, 13.(1 )写出用希尔排序方法对序列排序时毎

33、一趟结束时的关键字状态。(2)用堆排序方法对其从小到大排序，画出堆排序的初态、理堆利排序过程中重 理堆的过程。冷试棋拟题客观题部分、草项选择题：(毎空2分,共20分)1. 单饯表是线性表的一种的存储结构。A顺序存取B.随机存取C.索弓I存取2. 栈和队列的共同点是oA.祁是后进先出 B.都是先进先出C.都是只允许在端点处插入和删除元素 D.无共同点3. s="HE IS A WORKER",t="WORKER,o 贝!Jindex(s,t,5)的返回值是。A. 4 B. 5 C. 6 D. 9 E. 104. 串足一种特殊的线性表. 其特殊性体现在oA.可以顺序存

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

35、 B.中序遍历C.后序遍历D.层序遍历二、是非趣：(毎题1分，共10分)(说明：正硝的选“A",績谖选)1. 线性表的顺序存储结构优于憊式存储结构。()2. 空串和空格串足相同的。()3. 图结构中，毎个结点的前驱和后续都可以有任意多个。()4. 快速排序葬法在待排序数揭有序时最不利于发挥其长处。()5. 连通网的最小生成树足唯一的。()6. 栈足FIFO的线性表。()7. 由二叉树的先序和后序遍历序列不能唯一确定这棵二叉树。()8. 若从无向图的一个顶点出发进行广度优先遍历可访问到图中的所有顶点，则该图一定是连通图。()9. 折半查找方法要求查找表必须足关键字的有序表，但足对存储结

36、构没有限制。()10 在一棵非空二叉树的中序適历序列中，根结点的右边只有其右子树上的所有结点。主观题部分一、简答理：（50分）1. 若线性表要求以垠快的速度存取而表中元素变动不大.则应采取什么存储结构（顺序或俵式结构）？为什么？（10分）2将下图所示孤林转化为二叉树并在其上标出中序全线索。（10分）3已知如右图所示的有向图.写出该图的:（1）邻接矩阵（2） 一个可能的拓扑有序序列。（10分）4. 设散列函数 H（key）二key MOD 7、用线性探测再散列法解决冲突。对关键字序 列 13, 2& 72, 5. 16. & 7. 9. llt 29 在地址空间0-10的散列区中

37、理 散列表，画出此表. 并求等概率情况下查找成功时的平均查找长度。（10分）5. 对于序列 26, 33, 35, 29, 19, 12, 22 ,（1）判断它是否是堆，若足，写出其是大顶堆还是小顶堆；若不是，把它调進 为堆，写出调進的过程利调進后的序列。（5分）（2）写出对该序列进行克接插入排序毎一趟结束时的关键字状态。（5分）二.算法设计题：（20分）1、编写递归算法. 计算二叉傩表存储的二叉树的结点数目。（10分）2、基于图的深度优先遍历束略写一算法，判断以邻接表方式存储的无向图中连通分讶的个数。（10分）附：答5ft戒答案要点弟一章章爷嫁习答案(一)选择趣：1. D 2. C 3. A

38、（二）判断題：1. X4. C 5 A 6. B 7. B8D2. /3. x4. J第二章章节嫁习答案(一)选择题：1. B,A 2. C 3. C4. C 5.A, B, C 6B,A(二)判靳题：1. J2. x/3. v/(三) 问答题：1. 应采用顺序结构。因为顺序表是随机存取的存储结构. 在顺序表中存取任何 元素所花的时间都一样。而谜表足顺序存职的存储结构。2. 应采用K式结构。因为在低表中是以结点的指针变化来反映逻辑关系的变化， 因此不船要移动元索.效率髙。3. 头结点在位宜上可视为首元结点的前驱，则做插入/输出操作时，i=l (即插 入或删除的位宜是I)时不需要做特别处理，否则

39、i=l时需要修改头指针。(四) 算法题：1. status insert_L (LinkList L, ElemType x)/*带头结点*/LinkList p,s;for (p=L; p->next && p->next->data<x ; p=p->next);s=(LinkList )malloc(sizeof(LNode);if(!s) return OVERFLOW;s->data=x; s->next=p->next; p->next=s;return OK;)2. status insert_Sq(SqLis

40、t *va,ElemType x)int i;if( va->length=va->listsize) exit OVERFLOW;学吹网络管理中2for( i=va->length-1 ;i>=0 && va->elemi>x;i)va->elemi+l= va->elemi;va->elemi+l=x; va->length+;return OK;)3. void reverse(LinkList L)/*带头结点勺LinkList p;p=L->next; L->next=NULL;for(; p;

41、p=p->next)q=p->next; p->next=L > next; L->next=p;)第三章章节练习答条(一) 选择题：l.C 2.C3. B 4.C5. B, A 6. A, C(二) 判断题：1. v/ 2x 3h 4v/(三) 问答与葬法题：1. 所有可能的输出序列有：ABC、ACB、BAC、BCA、CBA)2. 葬法：#define MAXQSIZE 100typedef struct ElemType *elem;int front;int length;(CycQueue;status EnQueue(CycQueue ElemType

42、e)辔細I朋般打蠶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=O) return ERROR;*e= Q->elem Q->front ;Q->length -return OK;（一）选择题：l.B 2. D 3. B4. D 5. B 6. A（二）判断题：1.x2.x3.x4.

43、x（一）选择题：1. B2. A3. B4. B（二）判断题：1.丿2. J3. J（三）问答题：1.NULL2.证明：由于深皮为k的二叉树的最大结点数为二叉树上毎一层的最大结点数 之和. 而二叉树上笫i层的最大结点数为2口。则£(第i层的最大结点数)=£2" =2k-J-1i-13证明：设no为叶子结点个数.血 为度为2的结点个数，则由二叉树的性质2可知：n2二no - 1又：满二叉树中只有度为2的结点和叶子结点，所以满二叉树中的结点总数n二n?4- no=2 no - 1又：二叉树中的分支数B=n- 1所以：B=2 n0-1 - l=2(n0-1)wpl=(

44、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=temp;exchange (t-> lchild);exchange (t->rchild);3. int dept

45、h(BiTree t)int l,r;if (!t) return 0;1= depth (t->lchild);r= depth (t->rchild);return (l>=r?l:r)+l;4. void leaf(BiTree t) if (!t) return 0;if (!t->lchild && !t->rchild) return 1;return leaf(t->lchild)+leaf(t->rchild);（一）选择题：l.A2.A3.D, A4D, C 5B D（二）判断题：1. J2. J 3. x（三）问答及

46、算法题：1. 图中共有3个顶点,如果足有向图,该图共有5条弧；如果是无向图.010000_0010002. (1)邻接矩阵：000100000000010001000100(2)可能的拓扑序列为156234(注愆4一定足最后一个.2定在1和5后)(3) 123456(4) 562431for (i=0; i<G.vexnum; i+) visitedi=false;sum=0;for (i=0; i< G.vexnum; i+)if (!visitedi) (sum+; dfs (G, i);Jreturn sum;void dfs (AlGraph G int i)visited

47、i=true;for (p=G. vert ices i . f irstarc; p; p=p->nextarc) k=p->adjvex;if(!visitedk)dfs(Q k);(I)-製雜叵(M) 、寸 XE Xe XI -製占黑(M) HZcq.9 V, H寸 GE Qe H一 -最欢的(I)8、寻 + -+-+e+1+1+1HJS v寸二 g z 二 t0T6OOA:寸coZTO012345678910哈希表1113245287216187比较次，釵1121124344.用链地址法处理冲突：（注意储表的有序性）01234567891011 1213141516ASL=

48、 (1+1+2+1 + 1+2+4+3+4) /9=19/9第十章章节练习答秦（一）选择题：l.D 2.C3.A4.A5.D6.C7.D &B（二）判断题：1.x2丿3.x4v/（三）问答题：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第三趙：(