《2022年电大数据结构期末复习指导》由会员分享,可在线阅读,更多相关《2022年电大数据结构期末复习指导(21页珍藏版)》请在金锄头文库上搜索。
1、1 / 21 一、单项选择题(每小题2 分,共 30 分)1. 数据结构中,与所使用的计算机无关的是数据的()结构。A. 逻辑 B. 物理 C. 存储 D. 逻辑与物理2. 下述各类表中可以随机访问的是()。A. 单向链表 B. 双向链表 C.单向循环链表 D.顺序表3. 在一个长度为n 的顺序表中为了删除第5 个元素,从前到后依次移动了15 个元素。则原顺序表的长度为()。A. 21 B. 20 C. 19 D. 25 4. 元素 2,4,6 按顺序依次进栈,则该栈的不可能的输出序列是()。A. 6 4 2 B. 6 2 4 C. 4 2 6 D. 2 6 4 5. 一个队列的入队序列是5,
2、 6,7,8,则队列的输出序列是()。A. 5 6 7 8 B. 8 7 6 5 C. 7 8 6 5 D.可能有多种情况6. 串函数 StrCmp(“ d”,“ D”)的值为()。A0 B 1 C -1 D3 7在一个单链表中,p、q 分别指向表中两个相邻的结点,且q 所指结点是p 所指结点的直接后继,现要删除q 所指结点,可用语句()。A p=q-next B p-next=q C p-next=q-next D q-next=NULL8. 设一棵哈夫曼树共有n 个非叶结点,则该树一共有()个结点。A. 2*n-1 B. 2*n +1 C. 2*n D. 2*(n-1) 9. 对如图 1
3、所示二叉树进行中序遍历,结果是()。A. dfebagc B. defbagc C. defbacg D.dbaefcg 10 . 任何一个无向连通图的最小生成树()。A.至少有一棵 B. 只有一棵C.一定有多棵D.可能不存在11设有一个10 阶的对称矩阵A,采用压缩存储的方式,将其下三角部分以行序为主序存储到一维数组B 中(数组下标从1 开始),则矩阵中元素A8,5在一维数组B 中的下标是()。A 33 B32 C85 D 41 12 . 一组记录的关键字序列为(37, 70,47,29,31,85),利用快速排序,以第一个关键字为分割元素,经过一次划分后结果为()。 A 31,29,37,
4、 85,47,70 B29,31,37,47,70, 85 C 31,29,37,70,47,85 D31,29,37,47,70,85 13 . 对 n 个元素进行冒泡排序,要求按升序排列,程序中设定某一趟冒泡没有出现元素交换,就结束排序过程。对某n 个元素的排序共进行了3n-6 次元素间的比较就完成了排图 1 c b c d e f g a 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页,共 21 页2 / 21 序,则()。A. 原序列是升序排列B. 原序列是降序排列C. 对序列只进行了2 趟冒泡D. 对序列只进行了3 趟冒泡14在一
5、个栈顶指针为top的链栈中删除一个结点时,用x 保存被删除的结点,应执行()。A.x=top-data。top=top-next。 B.top=top-next 。 x=top 。C.x=top 。top=top-next 。 D.x=top-data。15串函数StrCat(a,b)的功能是进行串()。 A 比较 B复制 C赋值 D连接二、填空题(每小题2 分,共 24 分)1在一个单向链表中p 所指结点之后插入一个s 所指的新结点,应执行s-next=p-next ;和 _操作。2根据数据元素间关系的不同特性,通常可分为_、四类基本结构。3在一个链队中,设f 和r 分别为队头和队尾指针,则
6、删除一个结点的操作为_。(结点的指针域为next) 4._ 遍历二叉排序树可得到一个有序序列。5. 一棵有 2n-1 个结点的二叉树,其每一个非叶结点的度数都为2,则该树共有 _个叶结点。6. 如图 1 所示的二叉树,其中序遍历序列为_ _。图 1 7. 对稀疏矩阵进行压缩存储,矩阵中每个非零元素所对应的三元组包括该元素的_、_和_三项信息。8 . 有一个有序表2,3,9,13,33,42,45,63,74,77,82,95,110,用折半查找法查找值为82 的结点,经 _次比较后查找成功。9 . 图的深度优先搜索和广度优先搜索序列不是唯一的。此断言是_的。 (回答正确或不正确 ) 10哈希法
7、既是一种存储方法,又是一种。1144.在对一组记录(55,39,97,22,16,73,65,47,88) 进行直接插入排序时,当把第7 个记录 65 插入到有序表时,为寻找插入位置需比较_次。e f g i b a c h d 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页,共 21 页3 / 21 12栈和队列的操作特点分别是_和 _。三、综合题(每小题10 分,共 30 分)1已知序列 11 ,19,5,4, 7,13,2,10 ,(1)试给出用归并排序法对该序列作升序排序时的每一趟的结果。( 2)对上述序列用堆排序的方法建立初始堆(
8、要求小根堆,以二叉树描述建堆过程)。2设有序表为(13, 19, 25, 36, 48, 51,63,84,91,116,135,200),元素的下标依次为1,2, ,12. (1)说出有哪几个元素需要经过3次元素间的比较才能成功查到(2)画出对上述有序表进行折半查找所对应的判定树(树结点用下标表示)(3)设查找元素5,需要进行多少次元素间的比较才能确定不能查到. 3 (1) 设有查找表 5,14,2,6,18,7,4,16,3, 依次取表中数据,构造一棵二叉排序树. (2)说明如何通过序列的二叉排序树得到相应序列的排序结果,对上述二叉排序给出中序遍历的结果. 四、程序填空题(每空2 分,共
9、16 分)1以下冒泡法程序对存放在a1 ,a2 , an 中的序列进行冒泡排序,完成程序中的空格部分,其中n 是元素个数,程序按升序排列。Void bsort (NODE a , int) NODE temp 。 int i,j,flag。 for(j=1。( 1)。j+) 。 flag=0。 for(i=1。( 2)。 i+) if(ai.keyai+1.key) flag=1。 temp=ai。(3)。( 4)。 if(flag= =0)break。 程序中 flag的功能是( 5)7以下程序是后序遍历二叉树的递归算法的程序,完成程序中空格部分(树结构中左、右指针域分别为left 和 ri
10、ght ,数据域为data,其数据类型为字符型,BT 指向根结点)。Void Postorder (struct BTree Node *BT) if(BT!=NULL) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页,共 21 页4 / 21 (1)。(2)。(3)。 试卷答案;一、单项选择题(每小题2 分,共 30 分)1A 2 D 3 B 4 B5A 6 C 7 C 8 B 9 A 10 A 11A 12 D 13 D 14 A 15 D 二、填空题(每小题2 分,共 24 分)1.p-next=s。2. 集合、线性、树形、图状3.
11、f=f-next 。4. 中序5.n 6. dgbaechhif 7. 行号、列号、元素值8.4 次9. 正确10查找方法113 次12先进后出先进先出三、综合题(每小题10 分,共 30 分)1(1) 初始 11,19,5,4, 7,13, 2,10 第一趟 11,194 ,57 ,132 ,10 第二趟 4,5,11,192 ,7,10, 13 第三趟 2,4,5,7, 10,11,13,19 (2) 2 10 11 5 19 7 4 13 13 5 10 11 19 7 2 4 11 2 4 2 4 5 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - -
12、- -第 4 页,共 21 页5 / 21 2 (1)13,36,63,135 (2) (3)3 次3(1) (2)中序遍历中序 2,3, 4,5,6,7,14,16,18 四、程序填空题(每空2 分,共 16 分)1(1)j=n-1 4 7 12 8 5 2 11 1 10 6 3 9 2 4 6 16 7 3 18 5 14 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页,共 21 页6 / 21 (2)inext= =head Dhead-next= =NULL 3链表所具备的特点是()。A可以随机访问任一结点 B占用连续的存储空间C
13、插入删除元素的操作不需要移动元素结点 D 可以通过下标对链表进行直接访问4非空的单向循环链表的尾结点满足()(设头指针为head,指针p 指向尾结点)。 Ap-next = =NULL Bp= =NULLCp= =head D p-next= =head 5数据结构中,与所使用的计算机无关的是数据的()结构。 A物理 B逻辑 C存储 D 逻辑与物理6算法的时间复杂度与()有关。 A所使用的计算机 B计算机的操作系统C算法本身 D数据结构7设有一个长度为n 的顺序表,要在第i 个元素之前插入一个元素(也就是插入元素作为新表的第i 个元素),则移动元素个数为()。 A n-i+1 Bn-i Cn-
14、i-1 Di 8设有一个长度为n 的顺序表,要删除第i 个元素需移动元素的个数为()。 An-i+1 Bn-i Cn-i-1 Di 9在一个单链表中,p、q 分别指向表中两个相邻的结点,且q 所指结点是p 所指结点的直接后继,现要删除q 所指结点,可用的语句是()。 Ap=q-next Bp-next=q C q-next=NULL D p-next=q-next 10在一个单链表中p 所指结点之后插入一个s 所指的结点时,可执行()。Ap=snext Bpnext=snext 。Csnext=pnext 。 pnext=s 。 Dpnext= s 。 snext= pnext 11从一个栈顶
15、指针为top 的链栈中删除一个结点时,用变量x 保存被删结点的植,则执行()。Ax=top-data。 top=topnext 。 B x=top-data。Ctop=top-next。 x=top-data。 Dtop=top-next。 x=data 。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页,共 21 页7 / 21 12在一个链队中,假设f和 r分别为队头和队尾指针,则删除一个结点的运算为()。 Ar=fnext 。 Br=rnext 。 C f=fnext 。 Df=rnext 。13在一个链队中,假设f和 r分别为队头和队
16、尾指针,则插入s 所指结点的运算为()。 A f-next=s。f=s 。B s-next=r。 r=s 。C r-next=s。 r=s 。D s-next=f 。f=s 。14元素 1,3,5,7 按顺序依次进栈,则该栈的不可能输出序列是()(进栈出栈可以交替进行)。 A7,5,3,1 B7, 5,1,3 C3,1,7,5D 1,3,5,7 15设有一个18 阶的对称矩阵A,采用压缩存储的方式,将其下三角部分以行序为主序存储到一维数组B 中(数组下标从1 开始),则矩阵中元素a10,8在一维数组B 中的下标是()。A18 B45 C 53D58 16在 C语言中,顺序存储长度为3 的字符串
17、,需要占用()个字节。 A 4 B3 C6 D12 17一棵有n 个结点采用链式存储的二叉树中,共有()个指针域为空。 An B n+1 Cn-1 D n-2 18在一棵二叉树中,若编号为i 的结点存在左孩子,则左孩子的顺序编号为()。A2i B2i-1 C2i+1 D2i+2 19设一棵哈夫曼树共有n 个叶结点,则该树有()个非叶结点。An B2n Cn-1 D n+1 20一棵具有35 个结点的完全二叉树,最后一层有()个结点。 A 4 B6 C16 D8 21一棵完全二叉树共有5 层,且第5 层上有六个结点,该树共有()个结点。 A30 B20 C 21 D23 22在一个无向图中,所有
18、顶点的度数之和等于边数的()倍。 A3 B2 C2.5 D 1.5 23已知如图1 所示的一个图,若从顶点a 出发,按深度优先搜索法进行遍历,则可能得到的一种顶点序列为()。 Aabecdf Bacfebd Caedfcb D aebcfd 图 1 24已知如图3 所示的一个图,若从顶点V1出发,按广度优先法进行遍历,则可能得到的b d f e c a 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页,共 21 页8 / 21 一种顶点序列为()。AV1V2V4V8V5V3V6V7 BV1V2V4V5V8V3V6V7CV1V2V4V8V3V5
19、V6V7 DV1V3V6V7V2V4V5V8 图 3 25在有序表 1 , 3,8,13,33, 42,46,63,76,78,86,97,100 中,用折半查找值86 时,经()次比较后查找成功。A3 B 4 C 6 D8 26对二叉排序树进行()遍历,可以使遍历所得到的序列是有序序列。 A按层次 B后序 C中序 D前序27有一个长度为12 的有序表,按折半查找对该表进行查找,在等概率情况下查找成功的平均比较次数为()。A37/12 B39/12 C41/12 D35/1228设已有m 个元素有序,在未排好序的序列中挑选第m+1个元素,并且只经过一次元素的交换就使第m+1个元素排序到位,该方
20、法是()。A折半排序 B冒泡排序 C归并排序 D简单选择排序29一组记录的关键字序列为(46,79,56, 38,40,84),利用快速排序,以第一个关键字为分割元素,经过一次划分后结果为()。A40, 38,46,79,56,84 B40,38,46,84,56,79 C40,38,46, 56,79,84D38,40,46,56,79, 84 30一组记录的关键字序列为(47,80,57, 39,41,46),利用堆排序(堆顶元素是最小元素)的方法建立的初始堆为()。A39,47, 46,80,41,57B39,41,46,80, 47,57 C41,39,46,47,57,80 D39,
21、80, 46,47,41,57 二填空题1把数据存储到计算机中,并具体体现数据之间的逻辑结构称为_结构。2算法的5 个特征为 _。3结构中的数据元素存在的关系称为树形结构。4要求在n 个数据元素中找其中值最大的元素,设基本操作为元素间的比较。则比较的次数和算法的时间复杂度分别为_和 _ 。5求两个n 阶矩阵的乘积,算法的基本操作和时间复杂度分别为_和_。6在一个单向链表中p 所指结点之后插入一个s 所指向的结点时,应执行s-next=p-V6V7V1V2V3V8V4V5精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页,共 21 页9 / 21
22、 next。和的操作。7设有一个头指针为head的单向循环链表,p 指向链表中的结点,若p-next= =head,则p 所指结点为。8在一个单向链表中,要删除p 所指结点,已知q 指向 p 所指结点的前驱结点。则可以用操作 _。9设有一个头指针为head的单向链表, p 指向表中某一个结点,且有p-next= =NULL, 通过操作 _,就可使该单向链表构造成单向循环链表。10向一个栈顶指针为h 的链栈中插入一个s 所指结点时,可执行s-next=h。 和操作。(结点的指针域为next) 11从一个栈顶指针为h 的链栈中删除一个结点时,用x 保存被删结点的值,可执行和 h=h-next 。(
23、结点的指针域为next)。12在一个链队中,设f 和r 分别为队头和队尾指针,则插入s 所指结点的操作为r-next=s。和 (结点的指针域为next)。13在一个链队中,设f 和 r 分别为队头和队尾指针,则删除一个结点的操作为_。(结点的指针域为next) 14.两个串相等的充分必要条件是_。15对稀疏矩阵进行压缩存储,矩阵中每个非零元素对应的三元组包括该元素的_、_和_三项信息。16在二叉树的链式存储结构中,通常每个结点中设置三个域,它们是_、。17一棵有2n-1 个结点的二叉树,其每一个非叶结点的度数都为2,则该树共有_个叶结点。18一棵二叉树中有2n-2 条边(结点间的连线),其中每
24、一个非叶结点的度数都为2,则该树共有 _个非叶结点。19中序遍历二叉排序树可得到一个。20如图 1 所示的二叉树,其中序遍历序列为_。21如图 1 所示的二叉树,其先序遍历序列为_。22如图 1 所示的二叉树,其后序遍历序列为_。23如图 2 所示的二叉树,其前序遍历序列为_。24哈希函数是记录关键字值与该记录存储地址之间所构造的对应关系。图 1 图 2 e f g i b a c h d g f a b d e c 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页,共 21 页10 / 21 25图的深度优先搜索和广度优先搜索序列不一定是唯
25、一的。此断言是_的。 (回答正确或不正确 ) 26 n 个元素进行冒泡法排序,通常需要进行_趟冒泡,第j 趟冒泡要进行_次元素间的比较。三、综合题1设一组记录的关键字序列为(49,83, 59,41,43,47),采用堆排序算法完成以下操作:(要求小根堆,并画出中间过程)(1)以二叉树描述6 个元素的初始堆(2)以二叉树描述逐次取走堆顶元素后,经调整得到的5个元素、 4 个元素的堆2已知序列 11,19,5,4,7,13,2,10 (1)试给出用归并排序法对该序列作升序排序时的每一趟的结果。(2)对上述序列用堆排序的方法建立初始堆(要求小根堆,以二叉树描述建堆过程)。3一组记录的关键字序列为(
26、46,79,56,38,40,84)(1)利用快速排序的方法,给出以第一个记录为基准得到的一次划分结果(给出逐次交换元素的过程,要求以升序排列)(2)对上述序列用堆排序的方法建立大根堆,要求以二叉树逐次描述建堆过程。4设查找表为(7,15,21,22,40,58,68,80,88,89,120) , 元素的下标依次为1,2,3,, 11. (1)画出对上述查找表进行折半查找所对应的判定树(树中结点用下标表示)(2)说明成功查找到元素40 需要经过多少次比较?(3)求在等概率条件下,成功查找的平均比较次数?5设查找表为(16,15,20,53,64,7), (1)用冒泡法对该表进行排序(要求升序
27、排列),要求写出每一趟的排序过程,通常对n个元素进行冒泡排序要进行多少趟冒泡?第j 趟要进行多少次元素间的比较? (2)在排序后的有序表的基础上,画出对其进行折半查找所对应的判定树.(要求以数据元素作为树结点 ) (3)求在等概率条件下,对上述有序表成功查找的平均查找长度. 6(1)如果二叉树中任一结点的值均大于其左孩子的值、小于其右孩子的值,则该树为二叉排序树,这种说法是否正确?若认为正确,则回答正确,若认为不正确,则举例说明。( 2)设有数据集合40,29, 7, 73,101,4, 55,2,81, 92,39 ,依次取集合中各数据,构造一棵二叉排序树. 7 (1) 设有查找表 5,14
28、,2,6,18,7,4,16,3, 依次取表中数据,构造一棵二叉排序树. (2)说明如何由序列的二叉排序树得到相应序列的排序结果,对上述二叉排序给出中序遍历的结果 . 8(1)“一棵二叉树若它的根结点的值大于左子树所有结点的值,小于右子树所有结点的值,则该树一定是二叉排序树”。该说法是否正确,若认为正确,则回答正确,若认为不正确则说明理由?(2)设有查找表 7 ,16,4,8,20, 9,6,18,5 ,依次取表中数据构造一棵二叉排序树. 对上述二叉树给出后序遍历的结果. 9 (1)以 2,3,4,7, 8,9 作为叶结点的权,构造一棵哈夫曼树,给出相应权重值叶结点的精选学习资料 - - -
29、- - - - - - 名师归纳总结 - - - - - - -第 10 页,共 21 页11 / 21 哈夫曼编码。(2) 一棵哈夫曼树有n 个叶结点,它一共有多少个结点?简述理由?10( 1)对给定权值2,1,3, 3,4,5,构造哈夫曼树。(2)同样用上述权值构造另一棵哈夫曼树,使两棵哈夫曼树有不同的高度,并分别求两棵树的带权路径长度。11如图所示的二叉树(1)给出中序遍历序列(2)给出先序遍历序列(3)给出后序遍历序列四、程序填空题1以下冒泡法程序对存放在a1,a2, , an中的序列进行冒泡排序完成程序中的空格部分,其中n是元素个数,要求按升序排列。void bsort (NODE
30、a , int n) NODE temp 。 int i,j,flag 。 for(j=1 。 j+) 。 flag=0 。 for(i=1 。 i+) if(ai.keyai+1.key) flag=1 。 temp=ai 。 if(flag= =0)break 。 程序中 flag 的功能是2以下是用尾插法建立带头结点且有n 个结点的单向链表的程序,结点中的数据域从前向后依次为1,2,3, ,n,完成程序中空格部分。NODE *create(n) NODE *head , *p, *q。 int i 。 p=(NODE*)malloc(sizeof(NODE)。head=。pnext=NU
31、LL 。 /*建立头结点 */ g i a b c e h f d 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页,共 21 页12 / 21 for(i=1 。 idata=i 。 p-next=NULL 。 q-next= 。 return(head)。 3以下是用头插法建立带头结点且有n 个结点的单向链表的程序,要求结点中的数据域从前向后依次为n,n-1, ,1,完成程序中空格部分。NODE *create2(n) NODE *head , *p, *q。 int i 。 p=(NODE*)malloc(sizeof(NODE)。p
32、-next=NULL 。head=。for(i=1 。 idata=i 。 if(i= =1) p-next=NULL 。 else p-next= 。q-next= 。 return(head)。 4设线性表为(6,10,16,4),以下程序用说明结构变量的方法建立单向链表,并输出链表中各结点中的数据。 #define NULL 0 void main( ) NODE a,b,c,d,*head,*p 。a.data=6。b.data=10。c.data=16。d.data=4。 /*d 是尾结点 */ head=。a.next=&b 。b.next=&c 。c.next=&d 。 /* 以
33、上结束建表过程*/ p=head。 /*p 为工作指针,准备输出链表*/ 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页,共 21 页13 / 21 do printf( “ %dn” ,)。 while()。 5以下程序是先序遍历二叉树的递归算法的程序,完成程序中空格部分(树结构中左、右指针域分别为left 和 right,数据域data为字符型, BT 指向根结点)。void Preorder (struct BTreeNode *BT) if(BT!=NULL) 。 6以下程序是中序遍历二叉树的递归算法的程序,完成程序中空格部分(树
34、结构中左、右指针域分别为left 和 right,数据域data为字符型, BT 指向根结点)。void Inorder (struct BTreeNode *BT) if(BT!=NULL) 。 7以下程序是后序遍历二叉树的递归算法的程序,完成程序中空格部分(树结构中,左、右指针域分别为left 和 right,数据域data为字符型, BT 指向根结点)。void Postorder (struct BTreeNode *BT) if(BT!=NULL) 。 8以下程序是中序遍历二叉树的递归算法的程序,完成程序中空格部分(树结构中左、右指针域分别为left 和 right,数据域data为
35、字符型, BT 指向根结点)。void Inorder (struct BTreeNode *BT) if(BT!=NULL) (1)。(2)。Inorder(BT-right) 。 利用上述程序对右图进行遍历,结果是。e f a b c d 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页,共 21 页14 / 21 综合练习题答案一、单项选择题1C 2 D 3 C 4 D 5 B6C 7A 8 B 9D 10C 11 A 12 C 13C 14 B15C 16 A 17B 18 A 19C 20A 21 C 22 B 23 C 24 A
36、 25 B 26 C27A28D 29C30 B 二、填空题物理(存储)有穷性、确定性、可行性、零个或多个输入、一个或多个输入3树形4n-1,O(n) 5乘法, O(n3) 6s-next=p-next 。7head 8q-next=p-next 。9p-next=head。10 s-next=h。11h=h-next。12 r-next=s。13 f=f-next 。14串长度相等且对应位置的字符相等15行下标、列下标、非零元素值16值域、左指针、右指针17 n 18 n-1 19中序20 dgbaechif 21 abdgcefhi 22 gdbeihfca 23 abdefcg 24存储
37、地址25正确26 n-1,n-j 三、综合题1(1) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页,共 21 页15 / 21 (2) 249 59 83 41 43 47 83 47 41 43 59 49 49 83 41 43 47 83 43 59 49 41 43 47 83 49 59 41 47 59 59 47 41 49 83 43 43 47 41 59 83 49 59 47 41 43 83 49 4741 83 59 43 49 47 41 43 83 49 59 精选学习资料 - - - - - - - -
38、- 名师归纳总结 - - - - - - -第 15 页,共 21 页16 / 21 (1) 初始 11,19,5,4,7, 13,2, 10 第一趟 11,194 ,57 ,132 ,10 第二趟 4,5,11,192 ,7,10, 13 第三趟 2,4,5,7, 11,10,11,13 (2) 3(1)初始序列46, 79,56,38, 40,84 40, 79,56,38, 40,84 40, 79,56,38, 79,84 40, 38,56, 38, 79,84 40, 38,56,56, 79,84 40, 38,46,56, 79,84 (2) 5679 38 40 84 46
39、8479 38 40 46 562 10 11 5 19 7 4 13 13 5 10 11 19 7 2 4 7 13 10 13 19 11 2 5 4 19 2 4 7 10 5 11 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 16 页,共 21 页17 / 21 4(1) (2)4 次(3)ASL=(1+2*2+3*4+4*4)/11=3 5(1)原序列 16 15 20 53 64 7 15 16 20 53 7 64 n-1 趟 15 16 20 7 53 64 n-j 次 15 16 7 20 53 64 15 7 16 20
40、53 64 7 15 16 20 53 64 (2) 4 7 11 8 5 2 10 1 3 9 6 7 15 20 64 16 535679 38 40 4679 38 40 84 84 56 46 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 17 页,共 21 页18 / 21 (3)平均查找长度=(1*1+2*2+3*3 ) /6=14/6 6 (1)不正确,例(2) 7(1) (2)中序遍历中序 2,3,4,5,6, 7,14, 16,18 1 5 4 2 39 55 92 81 4 101 7 2 40 7329 2 4 6 16 7
41、 3 18 5 14 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 18 页,共 21 页19 / 21 8(1)不正确,二叉排序树要求其子树也是二叉排序树。(2) 后续遍历 5,6, 4,9,8,18,20,16, 7 9 (1) 20000 30001 4001 710 811 901 (2)2n-1 个,因为非叶结点数比叶结点数少一个。10( 1)9 7 5 8 9 2 4 3 33 1518 5 3 4 1811 7 6 3 3 1 2 4 6 8 9 5 20 7 16 18 精选学习资料 - - - - - - - - - 名师归纳总
42、结 - - - - - - -第 19 页,共 21 页20 / 21 wpl1=45 (2) wpl2=45 11( 1)dgbaechif (2)abdgcefhi (3)gdbeihfca 四、程序填空题1j=n-1 inext p 4&a 187 11 3 1 2 3 3 4 6 5 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 20 页,共 21 页21 / 21 dnext= =NULL pdata p=pnext p!=NULL 5printf( “ %c” ,BT-data)。Preorder(BT-left) 。Preorder(BT-right) 。6Inorder(BT-left) 。printf( “ %c” ,BT-data)。Inorder(BT-right) 。7Postorder(BT-left) 。Postorder(BT-right) 。printf( “ %c” ,BT-data)。8Inorder(BT-left) 。printf( “ %c” ,BT-data)。dbeafc 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 21 页,共 21 页