下载文档原格式
数据结构填空题天涯古巷 出品1. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动 n-i+1 个元素。
2. 向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动 n-i 个元素。
3. 在顺序表中访问任意一结点的时间复杂度均为 O(1) ，因此，顺序表也称为 随机存取 的数据结构。
4. 在单链表中，除了首元结点外，任一结点的存储位置由 其直接前驱结点的链域的值 指示。
5．对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为 O(1) ，在给定值为x的结点后插入一个新结点的时间复杂度为 O(n) 。
第三章1. 向量、栈和队列都是 线性 结构，可以在向量的 任何 位置插入和删除元素；对于栈只能在 栈顶 插入和删除元素；对于队列只能在 队尾 插入和 队首 删除元素。
2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶 。
不允许插入和删除运算的一端称为 栈底 。
3. 队列 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。
4. 在具有n个单元的循环队列中，队满时共有 n-1 个元素。
第四章1. 不包含任何字符（长度为0）的串 称为空串。
2. 由一个或多个空格（仅由空格符）组成的串 称为空白串。
3. 设S=“A;/document/Mary.doc”，则strlen(s)= 20 , “/”的字符定位的位置为 3 。
4. 子串的定位运算称为串的模式匹配； 被匹配的主串 称为目标串， 子串 称为模式。
5. 设目标T=”abccdcdccbaa”，模式P=“cdcc”，则第 6 次匹配成功。
6. 若n为主串长，m为子串长，则串的古典（朴素）匹配算法最坏的情况下需要比较字符的总次数为 (n-m+1)*m 。
7.设数组a[1…60, 1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为 8950 。
一、单选题1、逻辑上通常可以将数据结构分为( )A.初等结构和组合结构B.顺序结构和链式结构C.线性结构和非线性结构D.动态结构和静态结构正确答案：C2、如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是()。
A.栈B. 队列C.图D.树正确答案：D3、在长度为n的顺序表的第i个位置上插入一个元素(1<=i<=n+1)，元素的移动次数为：（）A.n-iB.i-1C.n-i+1D.i正确答案：C4、在非空线性链表中由p所指结点的后面插入一个由q所指的结点，应依次执行（）A.q->next=p；p->next=q；B.p->next=q；q->next=p；C.q->next=p->next；p->next=q；D.q->next=p->next；p=q；正确答案：C5、已知栈的最大容量为4。
若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为（）A.2，3，5，6，1，4B.1，4，6，5，2，3C.5，4，3，2，1，6D.3，2，5，4，1，6正确答案：D6、设栈S和队列Q初始均为空，若6个元素入栈的顺序为1、2、3、4、5、6，一个元素出栈以后立即入队列Q，若6个元素出队的顺序为2、4、3、6、5、1，则栈S的容量至少为（）A.3B.5C.4D.2正确答案：A7、在计算机内实现递归算法时所需的辅助数据结构是（）A.队列B.栈C.图D.树正确答案：B8、循环队列存储在数组A[0..m-1],则出队时的操作为（）A.front=(front mod m)+1B.ront=(front+1)mod mC.front=front+1D.front=(front+1)mod (m-1)正确答案：B9、若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列合法的是（)A.SXXSXSSXB.SSSXXSXXC.SXSSXXXXD.SXSXXSSX正确答案：B10、在具有m个单元的循环队列中，队头指针为front，队尾指针为rear，则队满的条件是（）A.(front+1)%m==rearB.(rear+1)%m==frontC.front==rearD.rear+1==front正确答案：B11、在表长为n的顺序表上做插入运算，平均要移动的结点数为（）A.n/4B.nC.n/3D.n/2正确答案：D12、元素的进栈次序为A，B，C，D，E，则退栈中不可能的序列是（）A.E，D，C，B，AB.A，B，C，D，EC.E，A，B，C，DD.B，C，D，E，A正确答案：C13、下述二叉树中，（）满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序。
数据结构期末考试试题一、选择题（每题2分，共20分）1. 在数据结构中，以下哪个不是线性数据结构？A. 数组B. 链表C. 树D. 图2. 一个栈的初始状态为空，元素a、b、c依次入栈，然后依次出栈，以下哪个序列不是可能的出栈序列？A. a, b, cB. b, a, cC. c, b, aD. b, c, a3. 哈希表的冲突可以通过哪种方式解决？A. 排序B. 链地址法C. 折半查找D. 二分查找4. 在二叉树中，以下哪个操作的时间复杂度是O(n)？A. 查找B. 插入C. 先序遍历D. 删除5. 以下哪个排序算法是稳定的？A. 快速排序B. 归并排序C. 堆排序D. 选择排序二、简答题（每题10分，共20分）1. 请简述什么是平衡二叉树，并说明其在数据结构中的重要性。
2. 解释什么是哈夫曼编码，并说明它在数据压缩中的应用。
三、算法题（每题15分，共30分）1. 编写一个函数，实现对链表的反转。
链表中的每个节点包含一个数据域和一个指向下一个节点的指针。
2. 给定一个未排序的整数数组，请编写一个函数，使用快速排序算法对其进行排序。
四、应用题（每题15分，共15分）1. 假设你正在设计一个在线购物平台的推荐系统，你需要使用数据结构来存储用户的行为数据。
请描述你将如何使用数据结构来优化推荐算法的性能。
五、编程题（每题15分，共15分）1. 编写一个程序，实现一个简单的文本编辑器，该编辑器支持插入、删除、查找和替换文本的功能。
请使用适当的数据结构来实现这些功能，并解释你的选择。
《数据结构》期末考试试卷试题及答案第一部分：选择题（每题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. 编写一个函数，实现链表的插入操作。
数据结构判断题天涯古巷 出品( × ) 1. 数据元素是数据的最小单位。
( × ) 2. 记录是数据处理的最小单位。
( × ) 3. 数据的逻辑结构是指数据的各数据项之间的逻辑关系。
( × ) 4．算法的优劣与算法描述语言无关，但与所用计算机有关。
( √ ) 5．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。
( √ ) 6．数据的物理结构是指数据在计算机内的实际存储形式。
( × ) 7. 数据结构的抽象操作的定义与具体实现有关。
第二章( × ) 1. 链表的每个结点中都恰好包含一个指针。
答：错，链表中的结点可含多个指针域，分别存放多个指针。
例如，双向链表中的结点可以含有两个指针域，分别存放指向其直接前趋和直接后继结点的指针。
( × ) 2. 链表的物理存储结构具有同链表一样的顺序。
答：错，链表的存储结构特点是无序，而链表的示意图有序。
( × ) 3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。
答：错，链表的结点不会移动，只是指针内容改变。
( × ) 4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。
答：错，混淆了逻辑结构与物理结构，链表也是线性表！且即使是顺序表，也能存放记录型数据。
( × ) 5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。
答：错，正好说反了。
顺序表才适合随机存取，链表恰恰适于“顺藤摸瓜”( × ) 6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
答：错，前一半正确，但后一半说法错误，那是链式存储的优点。
顺序存储方式插入、删除运算效率较低，在表长为n的顺序表中，插入和删除一个数据元素，平均需移动表长一半个数的数据元素。
( × ) 7. 线性表在物理存储空间中也一定是连续的。
《数据结构》期末考试试卷试题及答案一、选择题（每题5分，共20分）1. 下列哪个不是线性结构？A. 栈B. 队列C. 图D. 数组2. 下列哪个不是栈的基本操作？A. 入栈B. 出栈C. 查找D. 判断栈空3. 下列哪个不是队列的基本操作？A. 入队B. 出队C. 查找D. 判断队列空4. 下列哪个不是图的基本概念？A. 顶点B. 边C. 路径D. 环二、填空题（每题5分，共20分）5. 栈是一种______结构的线性表，队列是一种______结构的线性表。
6. 图的顶点集记为V(G)，边集记为E(G)，则无向图G=(V(G),E(G))，有向图G=(______，______)。
7. 树的根结点的度为______，度为0的结点称为______。
8. 在二叉树中，一个结点的左子结点是指______的结点，右子结点是指______的结点。
三、简答题（每题10分，共30分）9. 简述线性表、栈、队列、图、树、二叉树的基本概念。
10. 简述二叉树的遍历方法。
11. 简述图的存储结构及其特点。
四、算法题（每题15分，共30分）12. 编写一个算法，实现栈的入栈操作。
13. 编写一个算法，实现队列的出队操作。
五、综合题（每题20分，共40分）14. 已知一个无向图G=(V,E)，其中V={1,2,3,4,5}，E={<1,2>,<1,3>,<2,4>,<3,4>,<4,5>}，画出图G，并给出图G的邻接矩阵。
15. 已知一个二叉树，其前序遍历序列为ABDCE，中序遍历序列为DBACE，请画出该二叉树，并给出其后序遍历序列。
答案部分一、选择题答案1. C2. C3. C4. D二、填空题答案5. 后进先出先进先出6. V(G),E(G)7. 0 叶结点8. 左孩子右孩子三、简答题答案9. （1）线性表：一个线性结构，其特点是数据元素之间存在一对一的线性关系。
数据结构应用题天涯古巷 出品题型一：表达式求值按照四则运算加（+）、减（-）、乘（*）、除（/）和幂运算(^)优先关系的惯例，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：A-B×C/D+E^F解：BC=G G/D=H A-H=I E^F=J I+J=K步骤 OPTR栈 OPND栈 输入字符 主要操作1 # A-B*C/D+E^F# PUSH(OPND,A)2 # A -B*C/D+E^F# PUSH(OPTR,-)3 #- A B*C/D+E^F# PUSH(OPND,B)4 #- A B *C/D+E^F# PUSH(OPTR,*)5 #-* A B C/D+E^F# PUSH(OPND,C)6 #-* A B C /D+E^F# Operate(B,*,C)7 #- A G /D+E^F# PUSH(OPTR,/)8 #-/ A G D+E^F# PUSH(OPND,D)9 #-/ A G D +E^F# Operate(G,/,D)10 #- A H +E^F# Operate(A,-,H)11 # I +E^F# PUSH(OPTR,+)12 #+ I E^F# PUSH(OPND,E)13 #+ I E ^F# PUSH(OPTR,^)14 #+^ I E F# PUSH(OPND,F)15 #+^ I E F # Operate(E,^,F)16 #+ I J # Operate(I,+,J)17 # K # RETURN题型二：汉诺塔时间复杂度的分析及证明汉诺塔问题的递归算法的时间复杂度是什么？请给出答案并且给予证明。
解：时间复杂度T(n)=O(2n)，证明如下已知：f(1)=1，f(n)=2f(n-1)+1 所以：f(n)+1=2(f(n-1)+1)f(n)= 2n-1 （2n-1为至少执行移动操作的次数）T(n)=O(2n)故：得证题型一：数组地址的计算设有二维数组A(6×8)，每个元素占6字节存储，顺序存放，A的起地址为1000，计算：（1）数组A的体积（即存储量）；（2）数组的最后一个元素A57的起始地址；（3）按行优先存放时，元素A14的起始地址；（4）按列优先存放时，元素A47的起始地址。
数据结构试题（考试时间120分钟）——————————————————————————————————————一、单项选择题：（总分10分，每小题1分）1、在顺序存储的线性表(a1,a2,-----,a n)中，删除任意结点时所需移动结点的平均次数为（ c ）。
A．n B n/2 C2A B.C3、某二叉树的前序遍历结点顺序为：ABCDEFG，中序遍历结点顺序为：CBDAFGE，则后续遍历结点的顺序为：（ a ）。
A．CDBGFEA B.CDGFEAB C.CDBAGFE D.CDBFAGE4、6．在一棵高度为H的满三叉树中，结点总数为（b ）。
A．3H - 1 B．（3H – 1）/2 C．（3H - 1 ）/3 D．3H5、设N阶方阵A是一对对称矩阵，为节省存储空间，将其下三角（包括对角线）以行序为主序存储在一维数组B[1----N（N+1）/2]中，则对任一上三角元素，在一维数组B中的下标位置K是（）A I(I-1)/2+jB j(j-1)/2+iC I(j-1)2+1D j(I-1)/2+16、用孩子兄弟链表表示一棵树，若要找到结点X的第5个孩子，只要先找到X的第一个孩子，然后（ d ）A 从孩子域指针连续扫描5个结点即可B从孩子域指针连续扫描4个结点即可C从兄弟域指针连续扫描5个结点即可D从兄弟域指针连续扫描4个结点即可7、设输入序列为a，b，c，d，借助一个栈得到的输出序列不可能是（d ）。
A．a，b，c，d B．d，c，b，a C．a，c，d，b D．d，a，b，c8、一个无向连通图的生成树是含有该连通图的全部顶点的（ a ）“A 极小连通子图B 极小子图C 极大连通子图D 极大子图9、有12个节点的平衡二叉树的最大深度是（ b ）。
A ．4B ．5C ．6D ．310、对于静态表顺序查找算法，若在表头设置岗哨，则正确的查找方式（ c ）A 从第0个元素往后查找该数据元素B 从第1个元素往后查找该数据元素C 从第N 个元素开始往前查找该数据元素D 与查找顺序无关二、填空题（每题2分，共20分）1．一般树的遍历结果和它所对应的二叉树的遍历结果之间有一定的对应关系：一般树的前序遍历序列和它所对应二叉树的 先序 遍历序列一致，一般树的后2、设某双链表的结点形式为Q 所指结点（中间结点）的后面插入一个新结点，则需执行下述语句段：s->prior=q; s->next=q->next ; ____________ ;q->next=s:3、对50个记录进行折半查找，最多比较次数和最少比较次数分别是 6 1 。
《数据结构》期末考试试题及答案一、选择题（每题2分，共20分）1. 下列哪一个不是线性结构的基本特征？A. 有且只有一个根结点B. 每个结点最多有一个前驱和一个后继C. 有且只有一个叶子结点D. 有序对中第一个元素是根结点答案：C2. 在单链表中，存储元素的数据域称为元素的哪个部分？A. 指针域B. 数据域C. 结点域D. 头结点答案：B3. 在顺序存储结构中，数据元素之间的逻辑关系由哪个因素决定？A. 数据元素的存储顺序B. 数据元素的存储位置C. 数据元素的类型D. 数据元素的大小答案：A4. 下列哪种排序算法的时间复杂度不是O(nlogn)？A. 快速排序B. 归并排序C. 堆排序D. 冒泡排序答案：D5. 在二叉树中，具有度为2的结点的个数是n0，度为0的结点个数是n2，则有（）。
A. n0 = n2 - 1B. n0 = n2 + 1C. n0 = n2D. n0 = n2 + 2答案：B6. 在线索二叉树中，哪个结点被称为线索结点？A. 有左子树的结点B. 有右子树的结点C. 既没有左子树也没有右子树的结点D. 具有左右子树的结点答案：C7. 在双向链表中，查找结点的时间复杂度是（）。
A. O(1)B. O(n)C. O(nlogn)D. O(n^2)答案：B8. 在栈的操作中，下列哪个操作是非法的？A. 先进先出B. 后进先出C. 可以插入任意元素D. 可以删除任意元素答案：D9. 在顺序表中进行插入操作时，平均移动次数为（）。
A. 0B. n/2C. nD. n-1答案：C10. 在下列排序算法中，哪个算法是不稳定的？A. 冒泡排序B. 快速排序C. 插入排序D. 归并排序答案：B二、填空题（每题2分，共20分）1. 线性表的顺序存储结构称为顺序表，其基本特点是（）。
答案：元素顺序存储2. 在单链表中，每个结点包括两个域：数据域和（）。
答案：指针域3. 在二叉树中，度为0的结点称为（），度为2的结点称为（）。
数据结构期末考试试卷及答案一、选择题（每题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. 在图的遍历过程中，深度优先遍历算法使用的数据结构是______。
数据结构应用题天涯古巷 出品题型一：表达式求值按照四则运算加（+）、减（-）、乘（*）、除（/）和幂运算(^)优先关系的惯例，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：A-B×C/D+E^F解：BC=G G/D=H A-H=I E^F=J I+J=K步骤 OPTR栈 OPND栈 输入字符 主要操作1 # A-B*C/D+E^F# PUSH(OPND,A)2 # A -B*C/D+E^F# PUSH(OPTR,-)3 #- A B*C/D+E^F# PUSH(OPND,B)4 #- A B *C/D+E^F# PUSH(OPTR,*)5 #-* A B C/D+E^F# PUSH(OPND,C)6 #-* A B C /D+E^F# Operate(B,*,C)7 #- A G /D+E^F# PUSH(OPTR,/)8 #-/ A G D+E^F# PUSH(OPND,D)9 #-/ A G D +E^F# Operate(G,/,D)10 #- A H +E^F# Operate(A,-,H)11 # I +E^F# PUSH(OPTR,+)12 #+ I E^F# PUSH(OPND,E)13 #+ I E ^F# PUSH(OPTR,^)14 #+^ I E F# PUSH(OPND,F)15 #+^ I E F # Operate(E,^,F)16 #+ I J # Operate(I,+,J)17 # K # RETURN题型二：汉诺塔时间复杂度的分析及证明汉诺塔问题的递归算法的时间复杂度是什么？请给出答案并且给予证明。
解：时间复杂度T(n)=O(2n)，证明如下已知：f(1)=1，f(n)=2f(n-1)+1 所以：f(n)+1=2(f(n-1)+1)f(n)= 2n-1 （2n-1为至少执行移动操作的次数）T(n)=O(2n)故：得证题型一：数组地址的计算设有二维数组A(6×8)，每个元素占6字节存储，顺序存放，A的起地址为1000，计算：（1）数组A的体积（即存储量）；（2）数组的最后一个元素A57的起始地址；（3）按行优先存放时，元素A14的起始地址；（4）按列优先存放时，元素A47的起始地址。
第五章题型一：由二叉树的中序遍历和前（后）序遍历，画出该二叉树1、给定二叉树的两种遍历序列，分别是：前序遍历序列：A B D F C E G H； 中序遍历序列：B F D A G E H C试画出二叉树B，并简述由任意二叉树B的前序遍历序列和中序遍历序列求二叉树B的思想方法。
结点序列。
题型二：哈夫曼树的构造（画树、计算WPL、初态和终态表），设计哈夫曼编码1、假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。
① 试为这8个字母设计赫夫曼编码。
② 试设计另一种由二进制表示的等长编码方案。
③ 对于上述实例，比较两种方案的优缺点。
答案：方案1；哈夫曼编码先将概率放大100倍，以方便构造哈夫曼树。
w={7,19,2,6,32,3,21,10}，按哈夫曼规则：【[（2,3），6], (7,10)】, ……19, 21, 32（100）（40） （60）（17） （11）7 10 6 （5） 2 3方案比较： 方案1WPL=2*(0.19+0.32+0.21)+4*(0.07+0.06+0.10)+5*(0.02+0.03)=1.44+0.92+0.25=2.61 方案2WPL＝3*(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3 结论：哈夫曼编码优于等长二进制编码字母编号 对应编码出现频率1 000 0.072 001 0.193 010 0.024 011 0.065 100 0.326 101 0.037 110 0.21 81110.10字母编号对应编码出现频率 1 1100 0.07 2 00 0.19 3 11110 0.02 4 1110 0.06 5 10 0.32 6 111110.03 7 01 0.21 811010.102、已知下列字符A、B、C、D、E、F、G 的权值分别为3、12、7、4、2、8，11，试填写出其对应哈夫曼树HT 的存储结构的初态和终态。
答案：初态:终态:weightparentlchild rchild1 3 8 0 02 12 12 0 03 7 10 0 04 4 9 0 05 2 8 0 06 8 10 0 07 11 11 0 08 59 5 1 9 9 11 4 8 10 15 12 3 6 11 20 13 9 7 12 27 13 2 10 13 471112weight parent lchild rchild 1 3 0 0 0 2 12 0 0 0 3 7 0 0 0 4 4 0 0 0 5 2 0 0 0 6 8 0 0 0 7 11 0 0 0 8 0 0 0 9 0 0 0 10 0 0 0 11 0 0 0 12 0 0 0 13题型三：利用二叉树的性质对某些问题进行证明 对于那些所有非叶子结点均含有左右子数的二叉树： (1) 试问：有n 个叶子结点的树中共有多少个结点？(2) 试证明：()1211=∑=−−ni l i ，其中n 为叶子结点的个数，i l 表示第i 个叶子结点所在的层次（设根节点所在层次为1）。
解：（1）总结点数为121n +，其中1n 为非叶子结点数，则叶子结点数为11+=n n ，所以总结点数为12−n 。
（2）用归纳法证明。
i=1，说明二叉树只有一个叶子结点，则整棵树只有一个根结点，11=l ,12)1(1=−−l ，结论成立。
设有n 个叶子结点时也成立，即12 (2)...22)1()1()1()1(21=++++++−−−−−−−n p l l l l ，现假设增加一个叶子结点，这意味着在某叶子结点p 上新生两个叶子结点，而结点p 则成为非叶子结点，可见，总结点数增2，叶子结点数增1。
此时，所有叶子结点是原结点除去p，然后加上两个深度为1+p l 的新叶子结点，由此，)11()11()1()1()1()1()1(222 (2)2...221121−+−−+−+−−−−−−−−−+++++++++−p p n p p l l l l l l l12 (2)...22)1()1()1()1(21=+++++=+−−−−−−−n p l l l l则当i=n+1时，也成立，由此即得到证明。
第六章题型一：给定图的逻辑结构，画出邻接矩阵和邻接表（或反过来考） 1、已知图所示的有向图，请给出： ① 每个顶点的入度和出度； ② 邻接矩阵； ③ 邻接表；④ 逆邻接表。
答案：2、已知如图6.33所示的无向网，请给出： ① 邻接矩阵； ② 邻接表； ③ 最小生成树 答案： ①③⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞6456252363794567555553955434②a →b 4 →c 3b → a 4 →c 5 →d 5 →e 9c → a 3 → b 5 →d 5 → h 5d → b 5 → c 5 →e 7 →f 6 →g 5 →h 4e → b 9 → d 7 →f 3f → d 6 → e 3 →g 2g → d 5 → f 2 → h 6题型二：根据图的逻辑结构或存储结构，写出深度、广度优先搜索遍历结果（根据逻辑结构写是唯一的，根据存储结构写不唯一）已知图的邻接矩阵如图所示。
试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。
答案：题型三：根据图的逻辑结构填写最短路径求解过程表，画出最小生成树（计算权值和），写出拓扑排序结果有向网如图所示，试用迪杰斯特拉算法求出从顶点a 到其他各顶点间的最短路径，完成下表答案：第七章题型一：折半查找过程，画判定树，计算ASL假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：① 画出描述折半查找过程的判定树；② 若查找元素54，需依次与哪些元素比较？③ 若查找元素90，需依次与哪些元素比较？④ 假定每个元素的查找概率相等，求查找成功时的平均查找长度。
答案：①先画出判定树如下（注：mid=⎣(1+12)/2⎦=6）：305 633 7 42 874 24 54 72 95②查找元素54，需依次与30, 63, 42, 54 元素比较；③查找元素90，需依次与30, 63,87, 95元素比较；④求ASL之前，需要统计每个元素的查找次数。
判定树的前3层共查找1＋2×2＋4×3=17次；但最后一层未满，不能用8×4，只能用5×4=20次，所以ASL＝1/12（17＋20）＝37/12≈3.08题型二：二叉排序树的创建，查找，计算ASL已知如下所示长度为12的表：（Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec）① 试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。
② 若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。
答案：题型三：已知哈希表长度和哈希函数，利用线性探测法和链地址法解决冲突，构造哈希表，计算ASL1、（线性探测）设哈希表的地址范围为0～17，哈希函数为：H（key）=key%16。
用线性探测法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49），构造哈希表，试回答下列问题：① 画出哈希表的示意图；② 若查找关键字63，需要依次与哪些关键字进行比较？③ 若查找关键字60，需要依次与哪些关键字比较？④ 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。
答案：①画表如下：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 32 17 63 49 24 40 10 30 31 46 47②查找63,首先要与H(63)=63%16=15号单元内容比较，即63与31比较 ,不匹配;然后顺移，与46,47,32,17,63相比，一共比较了6次！③查找60,首先要与H(60)=60%16=12号单元内容比较，但因为12号单元为空（应当有空标记），所以应当只比较这一次即可。
