《2022年数据结构期末综合练习4.docx》由会员分享，可在线阅读，更多相关《2022年数据结构期末综合练习4.docx（40页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选学习资料 - - - - - - - - - 数据结构（本）期末综合练习2022 年 6 月期末综合练习一一、单项选择题1深度为 5 的完全二叉树共有20 个结点,就第5 层上有（）个结点 根所在结点为第一层 ；A 3 B8 C 5 D6 2同一种规律结构（）； A只能有唯独的储备结构 B可以有不同的储备结构 C只能表示某一种数据元素之间的关系 D以上三种说法均不正确3已知一个图的边数为m,就该图的全部顶点的度数之和为（）；A 2mBm C2m+1 D m/2 4链表所具备的特点是（）；A可以随机拜访任一结点 B占用连续的储备空间 C插入删除元素的操作不需要移动元素结点 D可以通过下标对链
2、表进行直接拜访）结构；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以下表
3、中可以随机拜访的是（）； A 单向链表 B 双向链表C单向循环链表 D次序表11散列查找的原理是（）；A在待查记录的关键字值与该记录的储备位置之间建立确定的对应关系B按待查记录的关键字有序的次序方式储备1 / 23 名师归纳总结 - - - - - - -第 1 页,共 23 页精选学习资料 - - - - - - - - - C按关键字值的比较进行查找D基于二分查找的方法12算法的时间复杂度与（）有关；A所使用的运算机 B与运算机的操作系统C与算法本身 D与数据结构13对 n 个元素进行冒泡排序如某趟冒泡中只进行了（序列已经排好序；A 1 B2 C 0 D n-1 ）次元素间的交换,就说明1
4、4设有一个长度为n 的次序表,要删除第i 个元素需移动元素的个数为（）；A n-i+1 Bn-i Cn-i-1 Di 15排序过程中,每一趟从无序子表中将一个待排序的记录按其关键字的大小放置到已经排好序的子序列的适当位置,直到全部排好序为止,该排序算法是 ；A直接插入排序 B 快速排序C冒泡排序 D选择排序16在一个单链表中,p、q 分别指向表中两个相邻的结点,且 q 所指结点是 p 所指结点的直接后继,现要删除 q 所指结点,可用的语句是（）； Ap=q-next Bp-next=q Cp-next=q next D q-next=NULL 17在对一组元素（64,48,106,33, 25
5、,82,70,55,93）进行直接插入排序时,当进行到要把第 7 个元素 70 插入到已经排好序的子表时,为找到插入位置,需进行（）次元素间的比较（指由小到大排序）；A6 B2 C3 D 4 18从一个栈顶指针为top的链栈中删除一个结点时,用变量；x 储存被删结点的值,就执行（）； x=data ； A x=top-data； top=top-next； Bx=top-dataCtop=top-next； x=top-data； Dtop=top-next19采纳次序查找法对长度为n 的线性表进行查找（不采纳表尾设监视哨的方法）,最坏的情形下要进行（）次元素间的比较；A n+2 B n Cn
6、-1 D n/2 20在一个链队中,假设 f 和 r 分别为队头和队尾指针,就删除一个结点的运算为（）； A r=f-next； Br=r-next； C f=f-next； D f=r-next；21如图 1,如从顶点 a 动身按广度优先搜寻法进行遍历,就可能得到的顶点序列为（）；A acebdgf Babecdgf a Cacfedgb D abecfdgb d e g c f 图 1 22一个栈的进栈序列是a,b,c,d,e,就栈的不行能输出序列是（）（进栈出2 / 23 名师归纳总结 - - - - - - -第 2 页,共 23 页精选学习资料 - - - - - - - - - 栈
7、可以交替进行）；Adceab Bedcba C decba D abcde 23元素 2, 4,6,8 按次序依次进栈,就该栈的不行能输出序列是（）（进栈出栈可以交替进行）； A 8,6,4,2 B 2,4,6,8 C4, 2,8,6 D 8,6,2,4 24有一个长度为 10 的有序表,按折半查找对该表进行查找,在等概率情形下查找成功的平均比较次数为（）；A26/10 B 29/10 C29/9 D 31/10 25排序方法中,从未排序序列中选择元素,并将其依次放入已排序序列（初始为空）的一端的方法,称为（）排序； A归并 B插入 C选择 D快速26排序算法中,从未排序序列中依次取出元素与已
8、排序序列（初始为空）中的元素进行比较（要求比较次数尽量少）,然后将其放入已排序序列的正确位置的方法是（）； A冒泡 B直接插入 C折半插入 D选择排序27一棵哈夫曼树总共有23 个结点,该树共有（）个叶结点（终端结点）A10 B 13 C11 D12 28设有一个 10 阶的对称矩阵 A,采纳压缩储备的方式,将其下三角部分以行序为主储备到一维数组 B 中（数组下标从 1 开头）,就矩阵中元素 A8,5在一维数组 B 中的下标是（）；A33 B32 C 85 D 41 29队列的插入操作在（）进行；A队头 B队尾 C 队头或队尾 D在任意指定位置30在一个无向图中,全部顶点的度数之和等于边数的（
9、）倍；A3 B2.5 C 1.5 D2 二、填空题1一棵二叉树没有单分支结点,有6 个叶结点,就该树总共有_个结点；2栈和队列的操作特点分别是_ _和 _ _；3设一棵完全二叉树,其最高层上最右边的叶结点的编号为奇数,该叶节点的双亲结点的编号为 10,该完全二叉树一共有 _个结点；4结构中的数据元素存在多对多的关系称为 _ _结构；5依据二叉树的递归定义,对二叉树遍历的常用算法有_、_、 _三种；6依据数据元素间关系的不同特性,通常可分为集合、线性、四类基本结构；7数据结构中的数据元素存在一对多的关系称为 _结构；8要求在 n 个数据元素中找其中值最大的元素,设基本操作为元素间的比较；就比较的
10、次数和算法的时间复杂度分别为 _和 _ ；9把数据储备到运算机中 ,并详细表达数据之间的规律结构称为 _结构；10在一个单向链表中 p 所指结点之后插入一个 s 所指向的结点时,应执行 _ _和 p-next=s；的操作；11结构中的数据元素存在一对一的关系称为 _结构；3 / 23 名师归纳总结 - - - - - - -第 3 页,共 23 页精选学习资料 - - - - - - - - - 12在二叉树的链式储备结构中,通常每个结点中设置三个域,它们是值域、；13如图 2 所示的二叉树,其后序遍历序列为；a b c d g e h f i 图 2 14一棵二叉树中次序编号为 为_、 _；
11、i 的结点,如它存在左、右孩子,就左、右孩子编号分别15n 个元素进行冒泡法排序,通常需要进行_趟冒泡；s-next=h ；和16向一个栈顶指针为h 的链栈中插入一个s 所指结点时,可执行_；17二叉树为二叉排序的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值；这种说法是 _的； 回答正确或不正确 18在一个链队中,设 f 和 r 分别为队头和队尾指针,就插入 s 所指结点的操作为_和 r=s；结点的指针域为 next 19图的深度优先搜寻和广度优先搜寻序列不肯定是唯独的；此断言是 _的； 回答正确或不正确 20设有一棵深度为 4 的完全二叉树,第四层上有 5 个结点,该树共
12、有 _个结点；（根所在结点为第 1 层）21依据搜寻方法的不同,图的遍历有 _、 _两种方法22对稀疏矩阵进行压缩储备,矩阵中每个非零元素对应的三元组包括该元素的_、_ _和_ _三项信息；23按某关键字对记录序列排序,如关键字的记录在排序前和排序后仍保持它们的前后关系,就排序算法是稳固的,否就是不稳固的；24在对一组记录55,39,97,22,16,73,65,47,88 进行直接插入排序时,当把第7 个记录65插入到有序表时,为查找插入位置需比较_次；三、综合题1（ 1）利用选择过程把序列42 , 82 , 67, 102, 16, 32, 57, 52 建成堆（小根堆）,画出该堆（不要求
13、中间过程）；4 / 23 名师归纳总结 - - - - - - -第 4 页,共 23 页精选学习资料 - - - - - - - - - （2）写出对上述堆对应的完全二叉树进行中序遍历得到的序列；2 1以 2,3,4, 7,8,9 作为叶结点的权,构造一棵哈夫曼树 要求每个结点的左子树根结点的权小于等于右子树根结点的权 ,给出相应权重值叶结点的哈夫曼编码；2 一棵哈夫曼树有 n 个叶结点,它一共有多少个结点？简述理由？3设查找表为 16,15,20,53,64,7, 1 用冒泡法对该表进行排序（要求升序排列）,要求写出每一趟的排序过程；2 在排序后的有序表的基础上,画出对其进行折半查找所对应
14、的判定树 .要求以数据元素作为树结点 3求在等概率条件下,对上述有序表胜利查找的平均查找长度. 4一组记录的关键字序列为（46,79,56,38, 40,84）（ 1）利用快速排序的方法,给出以第一个记录为基准得到的一次划分结果（给出逐次交 换元素的过程,要求以升序排列）（ 2）对上述序列用堆排序的方法建立大根堆,要求以二叉树逐次描述建堆过程；5（ 1）设有一个整数序列50 ,38,16,82,110,13,64 ,依次取出序列中的数,构造一棵二叉排序树（2）利用上述二叉排序树,为了查找110,经多少次元素间的比较能胜利查到,为了查找 15,经多少次元素间的比较可知道查找失败5 / 23 名师
15、归纳总结 - - - - - - -第 5 页,共 23 页精选学习资料 - - - - - - - - - 6设查找表为 50,60,75,85,96,98,105,110,120,130 1 说出进行折半查找胜利查找到元素120 需要进行多少次元素间的比较？2为了折半查找元素 95,经过多少次元素间的比较才能确定不能查到？（ 3）画出对上述有序表进行折半查找所对应的判定树 要求以数据元素作为树结点 四、程序填空题1以下函数为链队列的入队操作,x 为要入队的结点的数据域的值,front 、rear 分别是链队列的队头、队尾指针struct node ElemType data ；struct
16、 node *next ；struct node *front , *rear；void InQueueElemType x struct node *p；_1_ ； p= struct node* p-data=xp-next=NULL ；_2_ ； rear= _3_ ； 2以下是用尾插法建立带头结点且有n 个结点的单向链表的程序,结点中的数据域从前向后依次为 1,2,3, ,n,完成程序中空格部分；NODE *createn NODE *head , *p, *q； int i ； p=NODE*mallocsizeofNODE；head= （1）； （2）；p next=NULL ；
17、/* 建立头结点 */ 6 / 23 名师归纳总结 - - - - - - -第 6 页,共 23 页精选学习资料 - - - - - - - - - fori=1 ； inext ； free_5_ ； return1 ； 4以下程序是中序遍历二叉树的递归算法的程序,完成程序中空格部分（树结构中 左、右指针域分别为 left 和 right ,数据域 data 为字符型, BT 指向根结点）；void Inorder struct BTreeNode *BT ifBT.=NULL （1）；（2）；（3）；7 / 23 名师归纳总结 - - - - - - -第 7 页,共 23 页精选学习资
18、料 - - - - - - - - - 期末综合练习一答案 一、单项选择题 1 C 2 B 3 A4 C5 D6 D7 C 8 A9 C10 D 11 A 12 C13 C 14 B 15 A 16 C 17 C 18 A19 B 20 C21 B 22 A 23 D 24 B25 C 26C27D28A29 B 30 D 二、填空题111 2后进先出、先进先出321 4图状（网状）5先序；中序；后序 6树形 图状7树形 8n-1,On 9物理（储备）10s-next=p-next；11线性 12左指针 右指针 13gdbeihfca 14 2i 2i+1 15n-1 16h=s；17不正确
19、18r-next=s；19正确 2012 21深度优先搜寻遍历 广度优先搜寻遍历22行下标、列下标、非零元素值 23相等 243 三、综合应用题1（ 1）16 42 32 102 52 82 67 57 8 / 23 名师归纳总结 - - - - - - -第 8 页,共 23 页精选学习资料 - - - - - - - - - （2）102,52,42,82,16,67,32, 57 2 1 33 7 15 8 9 18 4 9 5 2 3 2：1110 3: 1111 4：110 7：00 8：01 9：10 （2） 2n-1 个,由于非叶结点数比叶结点数少一个；31 原序列 16 15
20、20 53 64 7 15 16 20 53 7 64 15 16 20 7 53 64 15 16 7 20 53 64 15 7 16 20 53 64 7 15 16 20 53 64 2 16 7 53名师归纳总结 15 20 64 9 / 23 第 9 页,共 23 页- - - - - - -精选学习资料 - - - - - - - - - 3平均查找长度 =（1*1+2*2+3*3 ）/6=14/6 41初始序列 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,
21、 38,56,56, 79,84 40, 38,46,56, 79,84 2 46 46 38 79 40 84 56 38 79 40 84 84 5684 38 79 40 46 38 79 40 56 56 46 5（ 1）50 38 82 16 64 110 10 / 23 13 名师归纳总结 - - - - - - -第 10 页,共 23 页精选学习资料 - - - - - - - - - （ 2）三次；四次6 13 次 24 次 3 96 60 11050 75 85 98 105 120 130 四、程序填空题1（ 1） mallocsizeof struct node （2）
22、rear-next=p （3）p 2（1）p （2）q=p （3）NODE*mallocsizeofNODE （4）p （5）q=p 3（ 1） jnext （3）q-next （4）q-next （5）p 11 / 23 名师归纳总结 - - - - - - -第 11 页,共 23 页精选学习资料 - - - - - - - - - 4（1）InorderBT-left （2）printf“ %c” ,BT-data （3） InorderBT-right 期末综合练习二一、单项选择题1在 C语言中,次序储备长度为3 的字符串,需要占用（）个字节；A4 B3 C 6 D 12 2数据的物理
23、结构（）；A与数据的规律结构无关 B仅仅包括数据元素的表示C只包括数据元素间关系的表示 D包括数据元素的表示和关系的表示3串函数 StrCat （a,b ）的功能是进行串（）；A比较 B 复制 C 赋值 D 连接4从 n 个数中选取最大元素（）； B算法的时间复杂度是On2 A基本操作是数据元素间的交换C算法的时间复杂度是On D 需要进行 n+1 次数据元素间的比较5一棵有 n 个结点采纳链式储备的二叉树中,共有（）个指针域为空； An+1 Bn Cn-1 Dn-2 6线性表的次序结构中,（）；A 规律上相邻的元素在物理位置上不肯定相邻B数据元素是不能随机拜访的C规律上相邻的元素在物理位置上
24、也相邻D进行数据元素的插入、删除效率较高7设一棵哈夫曼树共有 n 个非叶结点,就该树有（）个叶结点；A n Bn+1 C n-1 D2n 8带头结点的单向链表为空的判定条件是（）（设头指针为 head）；A head = =NULL B head-next= =NULL C head-next= =head D head.=NULL 9从一个栈顶指针为 top 的链栈中删除一个结点时,用变量 x 储存被删结点的值,就执行（）； Ax=top-data； top=top next ； Bx=top-data；Ctop=top-next； x=top-data； Dtop=top-next； x=
25、data ；10线性结构中数据元素的位置之间存在（）的关系；A 一对一 B一对多 C多对多 D每一个元素都有一个直接前驱和一个直接后继11一棵完全二叉树共有5 层,且第 5 层上有六个结点,该树共有（）个结点；）时, A30 B20 C 21 D 23 i=（12设次序储备的线性表长度为n,要删除第i 个元素,按课本的算法,当移动元素的次数为3 12 / 23 名师归纳总结 - - - - - - -第 12 页,共 23 页精选学习资料 - - - - - - - - - A 3 Bn/2 Cn-3 D4 13在一个无向图中,全部顶点的度数之和等于边数的（）倍； A 3 B 2.5 C 1.
26、5 D2 14. 以下说法不正确选项（）；A 栈的特点是后进先出 B队列的特点是先进先出C栈的删除操作在栈底进行,插入操作在栈顶进行D队列的插入操作在队尾进行,删除操作在队头进行15已知如图 1 所示的一个图,如从顶点 V1 动身,按深度优先搜寻法进行遍历,就可能得到的一种顶点序列为（）；A V1V2V4V8V5V3V6V7 BV1V2V4V5V8V3V6V7CV1V2V4V8V3V5V6V7 DV1V3V6V7V2V4V5V8 V 1V 4V2V 5V 6V 3V 7V 8图 1 16一个栈的进栈序列是a,b, c,d,就栈的不行能的出栈序列是（）；A adbc B bcad Ccbad D
27、 dcba 17已知如图 2 所示的一个图,如从顶点 a 动身,按广度优先搜寻法进行遍历,就可能得到的一种顶点序列为（）； Aabcedf Babcefd Caebcfd Dacfdeb a b e c d f 图 2 18设top 是一个链栈的栈顶指针,栈中每个结点由一个数据域data 和指针域next 组成,设用 x 接收栈顶元素,就出栈操作为（）；13 / 23 名师归纳总结 - - - - - - -第 13 页,共 23 页精选学习资料 - - - - - - - - - A x=top-data； top=top-next ； Btop=top-next ；x=top-data；C
28、x=top-next ； top=top-data ； Dtop-next =top ；x=top-data；19对二叉排序树进行（按层次 B 后序 C中序 D 前序）遍历,可以使遍历所得到的序列是有序序列；20设有一个带头结点的链队列,队列中每个结点由一个数据域 data 和指针域 next 组成, front 和 rear 分别为链队列的头指针和尾指针,要执行出队操作,用 x 储存出队元素的值, p 为指向结点类型的指针,可执行如下操作：p=front-next ；x=p-data；然后执行（）；A front=p-next ； B front-next=p-next ；C front=p
29、 ； D front-next =p ；21在有序表 2 ,4, 7,14,34,43,47, 64,75,80, 90,97,120 中,用折半查找法查找值 80 时,经（）次比较后查找胜利；A4 B2C 3 D522以下说法正确选项（）；A 队列是后进先出 B栈的特点是后进后出C栈的删除和插入操作都只能在栈顶进行D队列的删除和插入操作都只能在队头进行23有一个长度为 9 的有序表,按折半查找对该表进行查找,在等概率情形下查找成功的平均比较次数为（）；A25/10 B25/9 C 20/9 D17/9 24空串的长度为（）；A0 B1 C 2 D 3 25排序算法中,从未排序序列中依次取出元
30、素与已排序序列（初始为空）中的元素进行比较（要求比较次数尽量少）,然后将其放入已排序序列的正确位置的方法是（）；A冒泡 B直接插入 C折半插入 D 选择排序26串函数 StrCmp“ abA”,”aba”的值为（）；A 1 B 0 C“abAaba” D-1 27一组记录的关键字序列为（46,79,56 ,38,40,84）,利用快速排序,以第一个关键字为分割元素,经过一次划分后结果为（）； A 40,38,46,79,56,84 B40, 38,46,56,79,84 C40,38,46, 84,56,79 D 38,40,46, 56,79,84 28设有一个 10 阶的对称矩阵 A,采纳
31、压缩储备方式将其下三角部分以行序为主序储备到一维数组 b 中；（矩阵 A 的第一个元素为 a1,1,数组 b 的下标从 1 开头）,就矩阵元素 a5,3对应一维数组 b 的数组元素是（）；Ab18 B b8 C b13 D b10 29排序方法中,从尚未排序序列中选择元素,并将其依次放入已排序序列（初始为空）的一端的方法,称为（）排序； A 归并 B 插入 C 快速 D 选择30已知如图 3 所示的一个图,如从顶点 a 动身,按深度优先搜寻法进行遍历,就可能得到的一种顶点序列为（）； Aabecdf Bacfebd Caebcfd D aedfcb 14 / 23 名师归纳总结 - - - -
32、 - - -第 14 页,共 23 页精选学习资料 - - - - - - - - - a b e c d f 图 3 二、填空题1在二叉树的链式储备结构中,通常每个结点中设置三个域,它们是 _、右指针；2通常数据的规律结构包括集合、线性、_、 _四种类型；3一棵二叉树中次序编号为 i 的结点,如它存在左、右孩子,就左、右孩子编号分别为_ _、_ _；4通常可以把某城市中各公交站点间的线路图抽象成 _结构；5串的两种最基本的储备方式是_ _和 _ _；6设有一个单向链表,结点的指针域为next,头指针为head,p 指向尾结点,为了使该单向链表改为单向循环链表,可用语句_；7一棵有 2n-1
33、个结点的二叉树,其每一个非叶结点的度数都为 个叶结点；2,就该树共有 _8循环队列的队头指针为 f ,队尾指针为 r,当 _时说明队列已空；9对于一棵具有 n 个结点的二叉树,其相应的链式储备结构中共有 _个指针域为空；10设有一个链栈,栈顶指针为hs,现有一个s 所指向的结点要入栈,就可执行操作_和 hs=s；11_遍历二叉排序树可得到一个有序序列；12在一个链队中,f 和 r 分别为队头和队尾指针,队结点的指针域为 next,就插入一个 s 所指结点的操作为 _；r=s；13如图 4 所示的二叉树,其后序遍历序列为；a b c d g e h f i 图 4 15 / 23 名师归纳总结
34、- - - - - - -第 15 页,共 23 页精选学习资料 - - - - - - - - - 14串的两种最基本的储备方式分别是_和 _ _；15如图 5 所示的二叉树,其先序遍历序列为 _ _；a b c d g e f 图 5 16一棵二叉树中次序编号为i 的结点,如它存在左、右孩子,就左、右孩子编号分别为_ _、 _ _；17图的深度优先搜寻和广度优先搜寻序列不肯定是唯独的；此断言是 _的； 回答正确或不正确 18两个串相等的充分必要条件是；19二叉树为二叉排序的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值；这种说法是 _的； 回答正确或不正确 20一棵二叉树叶结点（终端结点）数为 5,单分支结点数为 2,该树共有 _个结点；21对记录序列排序是指按记录的某个关键字排序,记录序列按 唯独的；22依据搜寻方法的不同,图的遍历有 _、 _两种方法；_排序结果是23按某关键字对记录序列排序,如在排序前和排序后仍保持它们的前后关系,就排 序算法是稳固的,否就是不稳固的；24一个有序表 3 ,4, 10,14,34, 43,46,64,75,78,90,96,130 用折半查找 法查找值为 90 的结点,经 _次比较后查找胜利；三、综合题1设查找表为 16,15,20,53,64,7, 1用冒