下载文档原格式
数据结构期末考试试题及答案一、选择题1. 以下哪种数据结构是线性存储结构？A. 树B. 图C. 栈D. 队列答案：C2. 在链表中，如果一个节点既没有前驱也没有后继，那么这个节点被称作什么？A. 首节点B. 尾节点C. 中间节点D. 孤立节点答案：B3. 树的度是指什么？A. 树中节点的个数B. 树中最大的层次数C. 树的分支数D. 树的节点的度的最大值答案：C4. 在二叉搜索树中，若要查找给定值的节点，当查找失败时应返回的值是？A. -1B. 0C. 1D. 该值本身答案：A5. 快速排序算法的时间复杂度最坏情况下是多少？A. O(n)B. O(nlogn)C. O(n^2)D. O(n!)答案：C二、填空题1. 在顺序表中，元素的物理位置相邻的特点是________，这使得顺序表在________操作上具有较高的效率。
答案：连续性；访问2. 链表相比顺序表的优势在于它能够动态地________存储空间，并且________操作不需要移动大量元素。
答案：分配和释放；插入与删除3. 栈是一种________的数据结构，只允许在________进行插入和删除操作。
答案：后进先出；栈顶4. 图的遍历算法主要有两种，分别是________和________。
答案：深度优先搜索；广度优先搜索5. 哈夫曼树是一种特殊的二叉树，它常用于数据压缩，其构建过程是基于________原则。
答案：最小权值三、简答题1. 请简述数组和链表的优缺点。
答案：数组通过索引直接访问元素，访问速度快，但大小固定，插入和删除操作需要移动大量元素。
链表元素通过指针连接，可以动态分配大小，插入和删除效率高，但访问速度较慢，因为需要从头开始遍历。
2. 什么是二叉树的前序遍历、中序遍历和后序遍历？答案：二叉树的前序遍历是先访问根节点，然后遍历左子树，最后遍历右子树。
中序遍历是先遍历左子树，然后访问根节点，最后遍历右子树。
后序遍历是先遍历左子树，然后遍历右子树，最后访问根节点。
《数据结构》期末考试试卷试题及答案第一部分：选择题（每题2分，共20分）1. 下面哪个数据结构是线性结构？A. 树B. 图C. 队列D. 网络流2. 下面哪个数据结构用于实现广度优先搜索算法？A. 栈B. 队列C. 散列表D. 堆3. 下面哪个数据结构用于实现深度优先搜索算法？A. 栈B. 队列C. 散列表D. 堆4. 下面哪个数据结构用于实现快速排序算法？A. 栈B. 队列C. 散列表D. 堆5. 下面哪个数据结构用于实现优先队列？A. 栈B. 队列C. 散列表D. 堆6. 下面哪个数据结构用于实现哈希表？A. 栈B. 队列C. 散列表D. 堆7. 下面哪个数据结构用于实现最小树算法？A. 栈B. 队列C. 散列表D. 堆8. 下面哪个数据结构用于实现拓扑排序算法？A. 栈B. 队列C. 散列表D. 堆9. 下面哪个数据结构用于实现最短路径算法？A. 栈B. 队列C. 散列表D. 堆10. 下面哪个数据结构用于实现并查集算法？A. 栈B. 队列C. 散列表D. 堆第二部分：填空题（每题2分，共20分）1. 链表是一种______数据结构。
2. 二叉树的节点最多有______个子节点。
3. 堆是一种特殊的______。
4. 散列表的查找效率取决于______。
5. 图的遍历算法包括______和______。
6. 快速排序算法的平均时间复杂度为______。
7. 哈希表中的冲突解决方法有______和______。
8. 最小树算法包括______和______。
9. 最短路径算法包括______和______。
10. 并查集算法用于解决______问题。
第三部分：简答题（每题10分，共50分）1. 请简述栈和队列的区别。
2. 请简述二叉搜索树的特点。
3. 请简述哈希表的原理。
4. 请简述图的深度优先搜索算法。
5. 请简述最小树算法的原理。
第四部分：编程题（每题20分，共50分）1. 编写一个函数，实现链表的插入操作。
（完整版）数据结构复习题（附答案）⼀、算法设计题（每题15分，共60分）答题要求：①⽤⾃然语⾔说明所采⽤算法的思想；②给出每个算法所需的数据结构定义，并做必要说明；③写出对应的算法程序，并做必要的注释。
1、有⼀个带头结点的单链表，每个结点包括两个域，⼀个是整型域info，另⼀个是指向下⼀个结点的指针域next。
假设单链表已建⽴，设计算法删除单链表中所有重复出现的结点，使得info域相等的结点只保留⼀个。
3、约瑟夫环问题（Josephus问题）是指编号为1、2、…，n的n（n>0）个⼈按顺时针⽅向围坐成⼀圈，现从第s个⼈开始按顺时针⽅向报数，数到第m个⼈出列，然后从出列的下⼀个⼈重新开始报数，数到第m的⼈⼜出列，…，如此重复直到所有的⼈全部出列为⽌。
现要求采⽤循环链表结构设计⼀个算法，模拟此过程。
4、编程实现单链表的就地逆置。
23．在数组 A[1..n]中有n个数据，试建⽴⼀个带有头结点的循环链表，头指针为h，要求链中数据从⼩到⼤排列，重复的数据在链中只保存⼀个.5、设计⼀个尽可能的⾼效算法输出单链表的倒数第K个元素。
3、假设以I和O分别表⽰⼊栈和出栈操作。
栈的初态和终态均为空，⼊栈和出栈的操作序列可表⽰为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为⾮法序列。
（15分）（1）下⾯所⽰的序列中哪些是合法的？A. IOIIOIOOB. IOOIOIIOC. IIIOIOIOD. IIIOOIOO（2）通过对（1）的分析，写出⼀个算法，判定所给的操作序列是否合法。
若合法，返回true，否则返回false（假定被判定的操作序列已存⼊⼀维数组中）。
5、设从键盘输⼊⼀整数的序列：a1, a2, a3，…，an,试编写算法实现：⽤栈结构存储输⼊的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。
算法应对异常情况（⼊栈满等）给出相应的信息。
设有⼀个背包可以放⼊的物品重量为S，现有n件物品，重量分别为W1，W2，...，W n。
注意事项：1、下面关于串的叙述中，哪一个是不正确的？（ ）A ．串是字符的有限序列B ．空串是由空格构成的串C ．模式匹配是串的一种重要运算D ．串既可以采用顺序存储，也可以采用链式存储 2、设无向图的顶点个数为n ，则该图最多有（ ）条边。
A ．n-1B ．n(n-1)/2C ． n(n+1)/2D ．0 3、以下数据结构中，（ ）是非线性数据结构。
A ．树B ．字符串C ．队列D ．栈 4、下面关于线性表的叙述中，错误的是哪一个？（ ）A ．线性表采用顺序存储，必须占用一片连续的存储单元。
B ．线性表采用顺序存储，便于进行插入和删除操作。
C ．线性表采用链接存储，不必占用一片连续的存储单元。
D ．线性表采用链接存储，便于插入和删除操作。
5、假设以数组A[m]存放循环队列的元素,其头尾指针分别为front 和rear ，则当前队列中的元素个数为（ ）。
A ．(rear-front+m)%mB ．rear-front+1C ．(front-rear+m)%mD ．(rear-front)%m6、在单链表指针为p 的结点之后插入指针为s 的结点,正确的操作是（ ）。
A ．p->next=s; s->next=p->next;B ．s->next=p->next; p->next=s;C ．p->next=s; p->next=s->next;D ．p->next=s->next; p->next=s; 7、设栈的输入序列是1，2，3，4,则（ ）不可能是其出栈序列。
A ．1，2，4，3B ．2，1，3，4C ．1，4，3，2D ．4，3，1，2， 8、广义表（a,(b,c),d,e ）的表头和表尾分别为（ ）。
A ．a 和(b,c),d,e B ．（a ）和(b,c),d,eC ．a 和 ((b,c)，d,e)D ．(a) 和((b,c)，d,e)9、栈和队都是（ ）A ．顺序存储的线性结构B ．链式存储的非线性结构C ．限制存取点的线性结构D ．限制存取点的非线性结构 10、从逻辑上可以把数据结构分为（ ）两大类。
班 姓 学 考试时 考场（教室装 线《数据结构》期末考试试卷(A)一、判断题：（正确者在括号内打“√”，错误者打“×”。
每小题1分，共10分）1．线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。
（ ） 2．栈和队列是一种非线性数据结构。
（ ） 3．十字链表是无向图的一种存储结构。
（ ） 4．Hash 表的平均查找长度与处理冲突的方法无关。
（ ） 5．数据元素是数据的最小单位。
（ ） 6．就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。
（ ） 7. 对于一棵非空二叉树，它的根结点作为第一层，则它的第i 层上最多能有2i-1个结点。
（ ） 8．有e 条边的无向图，在邻接表中有e 个结点。
（ ） 9．顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
（ ） 中插入一个新结点,总是插入到叶结点下面。
（ ） 二、选择题：（将每小题正确答案的选项填写在题后的横线上，每小题2分，共20分） x 的赋值语句的频度为___________。
FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1;A ． O(2n)B ．O(n)C ．O(n 2) D ．O(log2n) 2．下面关于串的的叙述中，哪一个是不正确的？___________。
A ．串是字符的有限序列B ．空串是由空格构成的串C ．模式匹配是串的一种重要运算D ．串既可以采用顺序存储，也可以采用链式存储 3．栈和队列的共同特点是___________。
A ．只允许在端点处插入和删除元素B ．都是先进后出C ．都是先进先出D ．没有共同点4．一个向量第一个元素的存储地址是50，每个元素的长度为4，则第5个元素的地址是___________。
A. 70 B. 66 C. 50 D. 785．设abcdef 以所给的次序进栈，若在进栈操作时，允许退栈操作,则下面得不到的序列为？___________。
“数据结构”期末考试试题一、单选题(每小题2分，共12分)1．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( )。
A． HL＝ps p一>next＝HLB． p一>next＝HL；HL＝p3C． p一>next＝Hl；p＝HL；D． p一>next＝HL一>next;HL一>next＝p；2．n个顶点的强连通图中至少含有( )。
A.n—l条有向边B.n条有向边C.n(n—1)／2条有向边D.n(n一1)条有向边3.从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为( )。
A.O(1)B.O(n)C.O(1Ogzn)D.O(n2)4．由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。
A．24 B．48C． 72 D． 535．当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为( )参数，以节省参数值的传输时间和存储参数的空间。
A.整形B.引用型C.指针型D.常值引用型·6．向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为( )。
A．O(n) B．O(1)C．O(n2) D．O(10g2n)二、填空题(每空1分，共28分)1．数据的存储结构被分为——、——、——和——四种。
2．在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为——域和——域。
3．——中缀表达式 3十x*(2.4／5—6)所对应的后缀表达式为————。
4．在一棵高度为h的3叉树中，最多含有——结点。
5．假定一棵二叉树的结点数为18，则它的最小深度为——，最大深度为——· 6．在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定——该结点的值，右子树上所有结点的值一定——该结点的值。
7．当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层——调整，直到被调整到——位置为止。
数据结构期末复习题、选择题1. 以下说法中不正确的是（D）。
A. 数据元素是数据的基本单位B. 数据项是不可分割的最小可标识单位C. 数据可由若干个数据元素构成D. 数据项可由若干个数据元素构成2. 计算机所处理的数据一般具备某种内在联系，这是指（B）。
A. 数据和数据之间存在某种关系B. 元素和元素之间存在某种关系C. 元素内部具有某种结构D. 数据项和数据项之间存在某种关系3. 在数据结构中，与所使用的计算机无关的是数据的（A）结构。
A. 逻辑B. 存储C. 逻辑和存储D. 物理4. 数据的逻辑结构可以分为（C）两类。
A. 动态结构和静态结构B. 紧凑结构和非紧凑结构C. 线性结构和非线性结构D. 内部结构和外部结构5. 数据的逻辑结构是指（A）关系的整体。
A. 数据元素之间逻辑B. 数据项之间逻辑C. 数据类型之间D. 存储结构之间6. 以下数据结构中（D）属非线性结构。
A. 栈B. 串C. 队列D. 平衡二叉树7. 以下属于逻辑结构的是（C）。
A. 顺序表B. 哈希表C. 有序表D. 单链表8. 以下不属于存储结构的是（A）。
A. 栈B. 线索二叉树C. 哈希表D. 双链表9. 在计算机中存储数据时，通常不仅要存储个数据元素的值，而且还要存储（C）A. 数据的处理方法B. 数据元素的类型C.数据元素之间的关系D.数据的存储方法10. 数据结构在计算机内存中的表示是指（A）。
A. 数据的存储结构B. 数据结构C. 数据的逻辑结构D. 数据元素之间的关系11. 在数据的存储结构中，一个结点通常存储一个（B）A. 数据项B. 数据元素C. 数据结构D. 数据类型12. 在决定选择何种类型的存储结构时，一般不多考虑（A）A. 各结点的值如何B. 结点个数的多少C. 对数据有哪些运算D. 所用编程语言实现这种结构是否方便13. 计算机中算法指的是解决某一问题的有限运算序列，它必须具备输入、输出、(B)。
一、单选题1. 从物理上可以把数据结构分为（B）两大类。
A. 动态结构、静态结构B. 顺序结构、链式结构C. 线性结构、非线性结构D. 初等结构、构造型结构2. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（C ）(1≤i≤n+1)。
A. O(0)B. O(1)C. O(n)D. O(n2)3. 链表不具有的特点是（B）。
A. 插入、删除不需要移动元素B. 可随机访问任一元素C. 不必事先估计存储空间D. 所需空间与线性长度成正比4. 下列排序算法中(C)排序在一趟结束后不一定能选出一个元素放在其最终位置上。
A. 选择B. 起泡C. 归并D. 堆5. 在下列排序算法中，哪一个算法的时间复杂度与初始排序无关（D ）。
A. 插入排序B. 起泡排序C. 快速排序D. 选择排序6. 一个栈的输入序列为1,2,3,…,n，若输出序列的第一个元素是i，则第j个输出元素是（D）。
A. i-j-1B. i-jC. j-i+1D. 不确定7. 输入序列为ABC，可以变为BCA时，经过的栈操作为（D ）。
A. push,pop,push,pop,push,popB. push,push,push,pop,pop,popC. push,push,pop,pop,push,popD. push,push,pop,push,pop,pop8. 有六个元素6 5 4 3 2 1 的顺序进栈，下列（C ）不是合法的出栈序列。
A. 5 4 3 6 1 2B. 4 5 3 1 2 6C. 3 4 6 5 2 1D. 2 3 4 1 5 69. 串的长度是指（B ）。
A. 串中所含不同字母的个数B. 串中所含字符的个数C. 串中所含不同字符的个数D. 串中所含非空格字符的个数10. 设二维数组A[1.. m,1.. n]（即m行n列）按行存储在数组B[1.. m*n]中，则二维数组元素A[i,j]在一维数组B中的下标为( A)。
数据结构期末考试试卷及答案一、选择题（每题2分，共20分）1. 下列哪一个不是线性结构的特点？A. 有且只有一个根结点B. 每个结点最多有一个前驱和一个后继C. 有多个根结点D. 有且只有一个叶子结点答案：C2. 在单链表中，头结点的作用是（）A. 作为链表的起点B. 作为链表的终点C. 存储链表中的数据元素D. 作为链表中的第一个元素答案：A3. 在顺序表中，插入一个元素的时间复杂度是（）A. O(1)B. O(n)C. O(logn)D. O(n^2)答案：B4. 下列哪种排序算法的平均时间复杂度最高？A. 冒泡排序B. 快速排序C. 直接插入排序D. 希尔排序答案：C5. 在二叉树中，具有3个结点的二叉树有（）种不同的形态。
A. 2B. 3C. 4D. 5答案：C6. 下列哪种情况不适合使用哈希表？A. 查找速度快B. 数据量较大C. 数据量较小D. 数据元素关键字分布均匀答案：C7. 在图的遍历过程中，下列哪种遍历方法属于深度优先遍历？A. 广度优先遍历B. 深度优先遍历C. 混合遍历D. 随机遍历答案：B8. 下列哪种数据结构不适用于实现栈？A. 顺序表B. 链表C. 树D. 图答案：C9. 在双向链表中，删除一个元素的时间复杂度是（）A. O(1)B. O(n)C. O(logn)D. O(n^2)答案：A10. 下列哪种情况不适合使用队列？A. 数据元素先进先出B. 数据元素后进先出C. 数据元素随机进出D. 数据元素按顺序进出答案：B二、填空题（每题2分，共20分）1. 线性表是具有______个数据元素的有限序列。
答案：n2. 在单链表中，每个结点包含两个域：数据域和______域。
答案：指针3. 在顺序表中，插入一个元素的时间复杂度是______。
答案：O(n)4. 快速排序的平均时间复杂度为______。
答案：O(nlogn)5. 哈希表中的冲突指的是______。
答案：不同的关键字对应同一存储位置6. 在图的遍历过程中，深度优先遍历算法使用的数据结构是______。
数据结构期末复习题一、选择题1.以下说法中不正确的是（D）。
A.数据元素是数据的基本单位B.数据项是不可分割的最小可标识单位C.数据可由若干个数据元素构成D.数据项可由若干个数据元素构成2.计算机所处理的数据一般具备某种内在联系，这是指（B）。
A.数据和数据之间存在某种关系B.元素和元素之间存在某种关系C.元素内部具有某种结构D.数据项和数据项之间存在某种关系3.在数据结构中，与所使用的计算机无关的是数据的（A）结构。
A.逻辑B.存储C.逻辑和存储D.物理4.数据的逻辑结构可以分为（C）两类。
A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构5.数据的逻辑结构是指（A）关系的整体。
A.数据元素之间逻辑B.数据项之间逻辑C.数据类型之间D.存储结构之间6.以下数据结构中（D）属非线性结构。
A.栈B.串C.队列D.平衡二叉树7.以下属于逻辑结构的是（C）。
A.顺序表B.哈希表C.有序表D.单链表8.以下不属于存储结构的是（A）。
A.栈B.线索二叉树C.哈希表D.双链表9.在计算机中存储数据时，通常不仅要存储个数据元素的值，而且还要存储（C）。
A.数据的处理方法B.数据元素的类型C.数据元素之间的关系D.数据的存储方法10.数据结构在计算机内存中的表示是指（A）。
A.数据的存储结构B.数据结构C.数据的逻辑结构D.数据元素之间的关系11.在数据的存储结构中，一个结点通常存储一个（B）。
A.数据项B.数据元素C.数据结构D.数据类型12.在决定选择何种类型的存储结构时，一般不多考虑（A）。
A.各结点的值如何B.结点个数的多少C.对数据有哪些运算D.所用编程语言实现这种结构是否方便13.计算机中算法指的是解决某一问题的有限运算序列，它必须具备输入、输出、（B）。
A.可行性、可移植性和可扩充性B.可行性、有穷性和正确性C.正确性、有穷性和稳定性D.易读性、稳定性和正确性14.以下关于算法的说法正确的是（D）。
A.算法最终必须由计算机程序实现B.算法等同于程序C.算法的可行性是指指令不能有二义性D.以上几个都是错误的15.算法的时间复杂度与（A）有关。
A.问题规模B.计算机硬件性能C.编译程序质量D.程序设计语言16.算法的主要任务之一是分析（D）。
A.算法是否具有较好的可读性B.算法中是否存在语法错误C.算法的功能是否符合设计要求D.算法的执行时间和问题规模之间的关系17.某算法的时间复杂度为O（n2），表明该算法的（B）。
A.问题规模是n2B.执行时间等于n2C.执行时间与n2成正比D.问题规模与n2成正比18.算法分析的目的是（C）。
A.找出数据结构的合理性B.研究算法中输入和输出的关系C.分析算法的效率以求改进D.分析算法的易读性和文档性19.以下函数中时间复杂度最小的是（D）。
A.n㏒2n+5000nB.n2-8000nC.n㏒2n-6000nD.20000㏒2n20.以下函数中时间复杂度最小的是（A）。
A.1000㏒2nB.n㏒2n-1000㏒2nC.n2-1000㏒2nD.2n㏒2n-1000㏒2n二、判断题1.线性表中每个元素都有一个前趋元素和一个后继元素。
(X)2.线性表中所有元素的排列顺序必须有小到大或由大到小。
(X)3.静态链表既有顺序存储的优点，又有动态链表的优点，所以，利用它存取表中第i个元素的时间与元素个数n无关。
(X)4.静态链表与动态链表在元素的插入、删除方面类似，不需做元素的移动。
(√)5.线性表的顺序存储结构优于链式存储结构。
(X)6.在循环单链表中，从表中任一结点出发都可以通过前后移动操作遍历整个循环链表。
(X)7.在单链表中，可以从头结点开始查找任何一个结点。
(√)8.在双链表中，可以从任一结点开始沿同一方向查找到任何其他结点。
(X)9.顺序存储结构只能用于存放线性表。
(X)10.线性表的逻辑结构总与其物理顺序一致。
(X)11.顺序表具有随机存取特性。
(√)12.单链表不具有随机存储特性，而双链表具有随机存取特性。
(X)13.顺序栈中元素值的大小是有序的。
(X)14.在n个元素进栈后，它们的出栈顺序和进栈顺序一定正好相反。
(X)15.栈是一种对进栈、出栈操作的次序做了限制的线性表。
(X)16.队列是一种对进栈、出栈操作的次序做了限制的线性表。
(X)17.n个元素进队列的顺序和出队列的顺序总是一致的。
(√)18.顺序队列中有多少元素，可以根据队首指针和队尾指针的值来计算。
(√)19.串长度为串中不同字符的个数。
(X)20.空串就是有空格构成的串。
(X)三、填空题1.线索二叉树中左线索指向其（）结点，右线索指向其（）结点。
前趋；后继2.有n个顶点的无向图最多有（）条边，而有向图最多有（）条弧。
n(n-1)/2 ；n(n-1) 3.图的邻接矩阵和邻接表存储结构中，邻接（）是唯一的，邻接（）是不唯一的。
矩阵；表4.用邻接矩阵存储一个不带权有向图G，其第i行的所有元素之和等于顶点i的（），而第i列的所有元素之和等于顶点i的（）。
出度；入度5.对n个顶点的连通图来说，它的生成树一定有（）条边，它是该图的一个（）连通分量。
n-1；极小6.Prim算法特别适合求（）图的最小生成树，Kruskal特别适合求（）图的最小生成树。
稠密；稀疏7.一个线性表采用折半查找时，该线性表必须具有的特点是顺序存储且（）；而分块查找法要求将待查找表均匀地分成若个块且块中诸记录的顺序可以是任意的，但块与块之间（）。
有序；有序8.高度为8的平衡二叉树的结点数最少有（）个，最多有（）个。
54；255 9.堆排序是一种（）排序方法，堆实质上是一棵（）二叉树。
选择；完全10.对含有n个元素的数据序列进行冒泡排序，其中关键字比较最多的次数是（），关键字比较最少的次数是（）。
n(n-1)/2；n-11.重要知识点：构造二叉树1.前序遍历序列为ABDCEFG，中序遍历序列为DBAFEGC，写出构造二叉树的过程。
答：⑴由前序序列知A为根结点，由中序序列知DB为左子树而FEGC为右子树，如图(a)所示。
⑵其次由前序序列确定左右子树的根结点为B和C,由中序序列知D为B的左孩子，B无右孩子，FEG为C的左子树，C无右子树，如图(b)所示。
⑶由前序序列确定C的左子树的根结点为E，由中序序列知F为E的左孩子而G为E的右孩子，这样就得到最终恢复的二叉树如图(c)所示。
图(a) 图(b) 图(c)2.前序遍历序列为ABDGCEF，中序遍历序列为DGBAECF，写出构造二叉树的过程。
答：⑴由前序序列知A为根结点，由中序序列知DGB为左子树而ECF为右子树，如图(a)所示。
⑵其次由前序序列确定左右子树的根结点为B和C,由中序序列知DG为B的左孩子，B无右孩子，E为C的左孩子，F为C的右孩子，如图(b)所示。
⑶由前序序列确定B的左子树的根结点为D，由中序序列知G为D的右孩子D无左孩子，这样就得到最终恢复的二叉树如图(c)所示。
图(a) 图(b) 图(c)3.中序遍历序列为DGBAECF，后序遍历序列为GDBEFCA，写出构造二叉树的过程。
答：⑴由后序序列知A为根结点，由中序序列知DGB为左子树而ECF为右子树，如图(a)所示。
⑵其次由后序序列确定左右子树的根结点为B和C,由中序序列知DG为B的左孩子，B无右孩子，E为C的左孩子，F为C的右孩子，如图(b)所示。
⑶由后序序列确定B的左子树的根结点为D，由中序序列知G为D的右孩子D无左孩子，这样就得到最终恢复的二叉树如图(c)所示。
图(a) 图(b) 图(c)2.重要知识点：给定树构造与其对应的二叉树1.给定下树，写出与其对应二叉树的转化过程。
GGG图1 图2 解：对于图1：⑶顺时针旋转45度：对于图2:(1)连兄弟：(2)断孩子：(3)顺时针旋转45度：3.1.给定下森林，写出该森林与其对应二叉树的转化过程。
KK图3解：（1）连兄弟：(2) （3）顺时针旋转454.1. 请构造出下面有向图的邻接表和逆邻接表图4解：邻接表：逆邻接表：5. 重要知识点：图的深度优先搜索遍历1. 从顶点v1和v4开始进行深度优先遍历， 写出顶点访问序列和深度优先生成树。
图5解：深度优先搜索遍历序列（分别从V1和V4开始）分别如下：V1—V2—V4—V3—V5—V6—V7—V8V4—V2—V1—V3—V5—V6—V7—V8 相应的深度优先生成树如图所示：6. 重要知识点：Prim 算法1. 从顶点V1开始用普利姆算法得到最小生成树。
图6解：使用Prim算法求得的最小生成树的过程如下图所示：7.重要知识点：二叉检索树1.对于一组记录其关键字序列为（18,5,10,15,12,11,20），要建立一颗平衡的二叉检索树，请给出构造过程。
解：构造平衡二叉检索树的过程如下图所示：8. 重要知识点：哈希检索1. 给定关键字序列（19,14,23,1,68,20,84,27,55,11,10,79），设哈希表长为13，哈希函数为h(k)=k%13。
试画出用线性探查法消解地址冲突时所构造的哈希表。
9. 重要知识点：快速排序1.给定排序码序列为（17,8,21,35,32,15,21,25,12,23），写出快速排序结果的过程。
解：快速排序过程如下：17,8,21,35,32,15,21,25,12,2312,8,21,35,32,15,21,25,17,23 12,8,17,35,32,15,21,25,21,23 12,8,15,35,32,17,21,25,21,23 12,8,15,17,32,35,21,25,21,23第一趟结束，结果为：12,8,15,17,32,35,21,25,21,2310. 重要知识点：堆排序1.给定排序码序列为（17,8,21,35,32,15,21,25,12,23），用堆排序法进行排序，写出构建初始堆的过程。
时不用调整 i=4时将8筛下一层i=3时不用调整 接着再将17筛下一层 接着再将17筛下一层i=2时，将17筛下一层得到初始堆（最大值根堆）第二种：得到初始堆（最小值根堆）。
