郑州大学远程教育学院数据结构试题(卷)与答案解析

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

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

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

4、和原则。三、章节练习(一)选择题：1 .具有线性结构的数据结构是 A.图 B.树 C.集合 D.栈2 .计算机算法是指 A.计算方法和运算结果B.调度方法C.解决某一问题的有限运算系列D.排序方法3 .线性结构中，最后一个结点有个后名Bi结点。A. 0 B. 1 C.任意多4 .算法分析的目的是 A.找出数据结构的合理性B.研究算法中输入和输出的关系C.分析算法的效率以求改进D.分析算法的可读性和可行性5 .具有非线性结构的数据结构是。A.图 B.线性表 C.申 D.栈6 .算法具有5个特性：。、输入和输出。A.稳定性、确定性、可行性 B.有穷性、确定性、可行性C.有穷性、安全性、可行性 D.

5、有穷性、确定性、可移植性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;j<=n;j+) k+;A.O(1) B. O(n) C. O(nlogn)D. O(n2)(二)判断题：1 .在数据结构中，从逻辑上可以把数据结构分为动态结构和静态结构两大类。()2 .任何一个算法的设计取决于数据的逻辑结构，而算法的实现则依赖于所采用的存储结构。 (

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

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

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

9、它任一元素结点的存储位置由前驱结点的指针域的指针指示。（）（三）问答题：1 .若线性表要求以最快的速度存取而表中元素变动不大，则应采取什么存储结构（顺序或链式结构）？为什么？2 .若线性表经常做插入/删除操作，则应采取什么存储结构？为什么？3 .在单链表中设置头结点有什么作用？（四）算法题：1设带头结点的单链表（L为头指针）中的数据元素递增有序。设计算法，将 x插 入到链表的适当位置上，并仍保持该表的有序性。2 .设顺序表va中的数据元素递增有序。设计算法，将 x插入到顺序表的适当位 置上，并仍保持该表的有序性。3 .设计算法，实现单链表的就地逆置，即利用原表的存储空间将线性表 （日,电,an

10、） 逆置为（an ,an-i,a）。第三章栈和队列一、章节学习目标与要求1、理解用栈和队列解决实际问题的方法。2、掌握栈和队列的定义以及特性、它们的 2种不同的存储表示方法（特别是顺序栈和循环队列）以及各种常见操作（如入、出操作）在不同表示方式上的实现。二、本章重点、难点重点：栈和队列的定义、各种表示和实现方法，加深对线性结构的理解难点：循环队列的表示及为解决循环队列队空、队涉判断条件相同而使用的不同实现方式；能在具体问题中灵活运用栈和队列结构。三、章节练习（一）选择题：1 . 一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是 A. edcba B.decba C.dceabD.

11、abcde2 .栈和队列的共同点是 A.都是后进先出B.都是先进先出C.都是只允许在端点处插入和删除元素D.无共同点3 . 一个队列的入队序列是1,2,3,4则队列的输出序列是_A. 4321 B. 1234 C. 1432 D. 32414 .栈的入栈序列是1, 2,，n,输出序列为p1,p2, pn,若p1=n,则pi为 A. i B. n-i C. n-i+1 D.不确定5 .队列是限定在进行插入、在进行删除的线性表。A.队头 B.队尾 C.任意位置6 .循环队列中，设队列元素依次存放在 Q0.m中，f、r分别指示队头元素位置 和队尾元素的下一个位置，约定存储m个元素时为队满。则队列空的

12、判定方法A.f=r是队列满的判定方法是。B. (f+1)%(m+1)=r C. (r+1)%(m+1)=f D. (r+1)% m=f（二）判断题：1 .若用户无法估计所用队列的最大长度，则最好采用链队列。（）2 .在链队列上删除队头元素时，只需修改头结点中的指针，不必修改尾指针。（）3 .栈是限定仅在栈顶进行插入或删除操作的线性表。（）4 .队列是限定在队尾插入元素，在队头删除元素的线性表。（）（三）问答与算法题：1 .对于一个栈，若输入序列依次为A,B,C,试给出所有可能的输出序列。2 .假设将循环队列定义为：以整型域变量 front和length分别指示循环队列中 队头元素位置和队列中元

13、素个数，指针 elem指示存放队列元素的连续空间的首 地址，写出相应的入队列和出队列的算法。第四章 申一、章节学习目标与要求1、理解用的抽象数据类型的定义以及相关术语、理解用在文本编辑中的作用。2、掌握字符串的定义及各种基本操作的运算结果以及用的各种存储表示的特点。二、本章重点、难点重点：用的基本运算、用的各种存储表示和特点。继续加深对线性结构的理解 难点：用的不同存储结构，区分它们和高级语言中用的存储方式的不同。三、章节练习（一）选择题：1 .设用s="I AM A STUDENT", 则其串长是 A. 13 B. 14 C. 15D. 162 .设 s ="H

14、E IS A WORKER",t="WORKER"。则 StrIndex（s,t,5）的返回值是 A. 4 B. 5 C. 6 D. 9 E. 103 .申是一种特殊的线性表，其特殊性体现在 。A.可以顺序存储B.数据元素是一个字符C.可以链接存储D.数据元素可以是多个字符4 .已知用s="ABCDEFGH '，则s的所有不同子用的个数为。A. 8 B. 9 C. 36 D. 375 .设用s="I am a teacher.',则s的第8个字符起、长度为7的子用为。A. "teacher. " B. &qu

15、ot;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

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

17、过程，树和森林与二叉树的转换关系，Huffman树及Huffman编码的构造方法难点：各种遍历算法的递归实现以及在具体问题中能灵活运用遍历思想解题三、章节练习（一）选择题：1 .下列关于二叉树的说法中，正确的有 A.二叉树白度为2 B.二叉树的度可以小于2C.二叉树中至少有一个结点的度为 2 D.二叉树中任一个结点的度都为 22 .任何一棵二叉树的叶子结点在先、中、后序遍历序列中的相对次序 A.不发生改变B.发生改变C.不能确定D.以上都不对3 .下面几个符号用编码集合中，不是前缀编码的是 A. 0, 10, 110 1111 B. 11 10, 001, 101, 0001C. 00, 01

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

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

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

21、.无向图的邻接矩阵是一个_二A.对称矩阵B.零矩阵 C.对角矩阵D.上三角矩阵3 .图的广度优先遍历算法类似于二叉树的 ffl的深度优先遍历算法类似于二叉树的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）（二）判断题：1 .若从无向图的一

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

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

24、分析方法；掌握二叉排序树的创建、查找、插入、删除算法及其性能分析方法；掌握 AVL树的平衡化旋转方法及其性能分析；掌握 B-树的插入和删除时结点的分裂和合并方法；掌握Hash法的查找、构造方法平均查找长度的计算方法。二、本章重点、难点重点：各种树结构表示的动态查找表和 Hash表的构造方法难点：二叉排序树的删除、AVL树的旋转处理、B-树的插入和删除、Hash法的构造以及各种查找表的平均查找长度的计算方法三、章节练习（一）选择题：1 .二叉排序树可得到一个关键字的有序序列。A.先序遍历 B.中序遍历C.后序遍历D.层序遍历2 .用链地址法处理冲突构造的散列表中，每个地址单元所链接的同义词表中结

25、点的 相同。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. 2566 .用折半查找对长度为7的有序表进行查找，则等概率下查找成功时的平 均查找长度为A. 15/7 B. 17/7 C. 18/7 D. 19/77 .有

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

27、84, 27, 68, 11, 40,(1)按表中元素顺序构造一棵二叉排序树，画出这棵树，并求其在等概率情 况下查找成功时的平均查找长度。(2)从空树开始，按表中元素顺序构造一棵2_3树(3阶BJt),若此后再删除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

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

29、掌握内部排序的基本概念和性能分析方法；掌握插入排序、交换排序、选择排序等内排序的方法及其性能分析方法。二、本章重点、难点重点：各类内部排序方法所依据的原则、特点及典型算法。难点：希尔排序、快速排序、堆排序三、章节练习（一）选择题：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,

30、 36C. 1 5, 6, 24, 7, 3, 4 D. 38, 24, 15, 20, 30, 464 .在待排序的元素序列基本有序时，效率最高的排序方法是堆A.插入排序B.选择排序C.快速排序D.归并排序5 .在下列排序方法中，某一趟结束后未必能选出一个元素放在其最终位置上的A.堆排序 B.起泡排序 C.快速排序D.直接插入排序6 .对序列22,86,19,49,12,30,65,35,181行一趟排序后得到的结果为18,12,19,22,49,30,65,35,86则其使用的排序方法为。A.插入排序 B.选择排序C.快速排序D.起泡排序7 .下列方法中，算法的时间复杂度为O（n2）。A.

31、堆排序 B.希尔排序 C.快速排序D.直接插入排序8 .对n个记录的序列进行堆排序，最坏情况下的时间复杂度为 A. 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, 8, 12, 13（1”出用希尔排序方法对序列排序时每一趟结束时的关键字状态。(2)用堆排序方法对其从小到大排序，画

33、出堆排序的初态、建堆和排序过程中重建堆的过程考试模拟题客观题部分一、单项选择题：(每空2分，共20分)1 .单链表是线性表的一种的存储结构。A.顺序存取 B.随机存取C.索引存取2 .栈和队列的共同点是。A.都是后进先出B.都是先进先出C.都是只允许在端点处才S入和删除元素D.无共同点3 .设$=3£ IS A WORKER",t="WORKER"。则index(s,t,5)的返回值是。A. 4 B. 5 C. 6 D. 9 E. 104 .用是一种特殊的线性表，其特殊性体现在。A.可以顺序存储B.数据元素是一个字符C.可以链接存储D.数据元素可以是多个

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

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

36、序列中，根结点的右边只有其右子树上的所有结点主观题部分一、简答题：（50分）1 .若线性表要求以最快的速度存取而表中元素变动不大,结构（顺序或链式结构）？为什么？ （10分）则应采取什么存储2 .将下图所示森林转化为二叉树并在其上标出中序全线索。（10分）3 .已知如右图所示的有向图，写出该图的（1郑接货!阵（2） 一个可能的拓扑有序序列（10分）4 .设散列函数H（key尸key MOD 7,用线性探测再散列法解决冲突。对关键字序列 13, 28, 72, 5, 16, 8, 7, 9, 11, 29 在地址空间为0-10的散列区中建散列表，画出此表，并求等概率情况下查找成功时的平均查找长度

37、。（10分）5 .对于序列 26, 33, 35, 29, 19, 12, 22 ,（1）判断它是否是堆，若是，写出其是大顶堆还是小顶堆；若不是，把它调整为堆，写出调整的过程和调整后的序列（5分）（2）写出对该序列进行直接插入排序每一趟结束时的关键字状态。（5分）二、算法设计题：（20分）1、编写递归算法，计算二叉链表存储的二叉树的结点数目。（10分）2、基于图的深度优先遍历策略写一算法， 判断以邻接表方式存储的无向图中连通分量的个数。（10分）附：答案或答案要点第一章章节练习答案（一）选择题：1. D 2. C 3. A4. C 5. A 6. B 7. B 8. D（二）判断题： 1. x

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

39、s 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(SqList *va,ElemType x)int i;if( v

40、a->length=va->listsize) exit OVERFLOW;for( i=va->length-1;i>=0 && va->elemi>x;-i)va->elemi+1= va->elemi;va->elemi+1=x; va->length+;return OK;3. void reverse(LinkList L)/*带头结点*/LinkList p;p=L->next; L->next=NULL;for(; p; p=p->next)q=p->next;p->next

41、=L->next;L->next=p;第三章章节练习答案(一)选择题：1.C 2.C3. B 4.C5. B, A 6. A, C(二)判断题：1. V 2. X 3. V4. V(三)问答与算法题：1 .所有可能的输出序列有：ABC卜ACBbBAC、BCAbCBA2 .算法：#define MAXQSIZE 100typedef struct ElemType *elem;int front;int length;CycQueue;status EnQueue(CycQueue *Q, ElemType e)if (Q->length=MAXQSIZE) return ER

42、ROR;Q->elem(Q->front+Q->length) % MAXQSIZE=e;Q->length+;return OK;status DeQueue(CycQueue *Q, ElemType *e)第四章章节练（一）选择题:（二）判断题:第七章章节练（一）选择题:（二）判断题:（三）问答题:1.KULL*e= Q->elemQ->front;Q->length -;return OK;习答案1.B 2. D 3. B 4. D 5. B 6. A1 .X 2.X 3.x 4.X习答案1. B2. A3. B4. B1. V 2. V3.

43、V4. V5.义r击if (Q->length=0) return ERROR;2 .证明：由于深度为k的二叉树的最大结点数为二叉树上每一层的最大结点数 之和，而二叉树上第i层的最大结点数为2i-1。则Z （第i层的最大结点数）=Z 2i-1 =2k-13 .证明：设n°为叶子结点个数，n2为度为2的结点个数,则由二叉树的性质2可知：n2= no-1又：满二叉树中只有度为2的结点和叶子结点, 所以满二叉树中的结点总数n= n2+ no=2 n°1又：二叉树中的分支数B=n14.所以：B=2 n o 11=2(no1)wpl=(16+17)*2+(9+14+15)*3+

44、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-> Ichild);exchange (t->rchild);3. int depth(BiTree t)int l,r

45、;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.A2.A3.D, A 4.D, C 5.B, D（二）判断题：1. V 2. V 3.X 4. X 5. V

46、 6. V（三）问答及算法题：1.图中共有3个顶点，如果是有向图，该图共有 5条弧；如果是无向图,该图共有3条边2. （1）邻接矩阵:010001000000010000000000100000001100（2）可能的拓扑序列为:156234 （注意4 一定是最后一个，2一定在1和5后）(3) 123456(4) 5624313. 一个拓扑排序序歹U:C1 C3 C2 C5 C4for (i=0; i<G.vexnum; i+) visitedi=false;sum=0;for (i=0; i< G.vexnum; i+)if (!visitedi) sum+; dfs (G, i

47、);return sum;void dfs (AlGraph G, int i)visitedi=true;for (p=G.verticesi.firstarc; p; p=p->nextarc) k=p->adjvex;if (!visitedk) dfs(G, k);第九章章节练习答案(一)选择题：1.B 2,C 3.D 4.B 5.A6. B 7. B（二）判断题：1.X 2. X 3.1. (D=16/8=2ASL=(1+2*2+3*3+3*4+2*5)/11=36/11(2) 2_邻t:(3)删除55:删除84:0 1/ 3 4 5 6 7 2 9 102.1112 5

48、 114ASL=(1+1+1+2+5+1+1+4)/83.3、0123456789101113245287216187比较次数1121124344.用链地址法处理冲突：（注意链表的有序性）01 234 5678 910 11 12 13 14 15 16W I W I *ASL= (1+1+2+1+1+2+4+3+4 ) /9=19/9July |Ntay|OctAug八June "7TASL=(7*1+4*2+1*3)/12=18/12第十章章节练习答案（一）选择题：1.D2.C3.A4.A5.D6.C7.D 8.B（二）判断题：1.x 2.V 3.X 4.V（三）问答题：1 .应依据“三者取中”的原则，比较第一个、最后一个和中间位置处记录的关键字，取关键字居中值的记录作为枢轴记录。2 .第一个序列是堆第二个序列不是堆。调整为堆后的序列为35, 33, 26, 29, 19, 12, 223 .初始序列：70, 83, 100, 65, 10, 9, 7, 32直接插入排序每一趟结束时的关键字状态：第一趟：(70,83), 100 65,10,9,7