2022年电大数据结构期末综合练习 .docx

《2022年电大数据结构期末综合练习 .docx》由会员分享，可在线阅读，更多相关《2022年电大数据结构期末综合练习 .docx（57页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选学习资料 - - - - - - - - - 数据结构（本）期末综合练习2022 年 6 月本课程期末考试卷型及试卷结构为：单项选择题（每道题2 分,共30 分）、填空题2（每道题2 分,共24 分）、综合题（每道题10 分,共30 分）、程序填空题（每空分,共 16 分）；以下各套期末综合练习,请同学们仔细完成；期末综合练习一一、单项选择题1（）是性质相同的数据元素的集合,是数据的子集；A、数据元素 B数据对象 C数据结构 D数据项2数据的物理结构（）；A与数据的规律结构无关 B仅仅包括数据元素的表示C只包括数据元素间关系的表示 D包括数据元素的表示和关系的表示3设链表中的结点是 NOD

2、E 类型的结构体变量,且有 NODE *p ；为了申请一个新结点,并由 p 指向该结点,可用以下语句（）；Ap=NODE *mallocsizeofNODE；Bp=*NODEmallocsizeofNODE；Cp=NODE mallocsizeofp；Dp=NODE *mallocsizeofp ；4从 n 个数中选取最大元素（）； B算法的时间复杂度是On 2 A基本操作是数据元素间的交换C算法的时间复杂度是On D需要进行 n+1次数据元素间的比较5设次序储备的线性长度为 n,要在第 i 个元素之前插入一个新元素,按课本的算法当 i=（）时,移动元素次数为 2 An/2 Bn C1 Dn-

3、1 6线性表的次序结构中,（）；A规律上相邻的元素在物理位置上不肯定相邻B数据元素是不能随机拜访的C规律上相邻的元素在物理位置上也相邻D进行数据元素的插入、删除效率较高7一个栈的进栈序列是1,2,3,4,就栈的不行能的出栈序列是（）（进出栈操作可以交替进行）A3,2,4, 1 B1,4,2,3 C4,3,2,1 D3, 2,1,4 8带头结点的单向链表为空的判定条件是（）（设头指针为head）；Ahead = =NULL Bhead-next= =NULL Chead-next= =head Dhead.=NULL 9设有一个带头结点的链队列,队列中每个结点由一个数据域 data 和指针域 n

4、ext 组成, front 和 rear 分别为链队列的头指针和尾指针；设 p 指向要入队的新结点 该结点已被赋值 ,就入队操作为（）；1 / 33 名师归纳总结 - - - - - - -第 1 页,共 33 页精选学习资料 - - - - - - - - - Arear-next=p； rear=p； Brear-next=p；p =rear；Cp =rear-next ；rear=p； Drear=p；rear-next=p ；10线性结构中数据元素的位置之间存在（）的关系；A一对一 B一对多 C多对多 D每一个元素都有一个直接前驱和一个直接后继 11以下说法不正确选项（）； A次序栈中

5、,栈满时再进行进栈操作称为“ 上溢”B次序栈中,栈空时再作出栈栈操作称为“ 下溢”C次序队列中,当尾指针已经超越队列储备空间的上界,就肯定是队列已满 D次序队列中,队列的头指针和尾指针均超越队列储备空间的上界,就队列已空12设次序储备的线性表长度为n,要删除第i 个元素,按课本的算法,当i=（）时,移动元素的次数为3 A3 Bn/2 C n-3 D4 13设有一个 20 阶的对称矩阵 A,采纳压缩储备方式,将其下三角部分以行序为主 序储备到一维数组中（矩阵 A 的第一个元素为 a11,数组 b 的下标从 1 开头）,就 矩阵元素 a8,5 在一维数组 b 中的下标是（）；A30 B28 C 4

6、0 D33 14. 以下说法不正确选项（）；A栈的特点是后进先出 B队列的特点是先进先出 C栈的删除操作在栈底进行,插入操作在栈顶进行 D队列的插入操作在队尾进行,删除操作在队头进行15深度为 5 的完全二叉树第5 层上有 4 个结点,该树一共有（）个结点；A28 B30 C31 D19 16一个栈的进栈序列是a,b,c,d,就栈的不行能的出栈序列是（）；Aadbc BbcadCcbad D dcba 17已知一个图的全部顶点的度数之和为m,就 m 肯定不行能是（）；A4 B8 C12 D9 18设 top 是一个链栈的栈顶指针,栈中每个结点由一个数据域 data 和指针域 next 组 成,

7、设用 x 接收栈顶元素,就出栈操作为（）；Ax=top-data ；top=top-next ； Btop=top-next ；x=top-data ；Cx=top-next ；top=top-data ； Dtop-next =top ；x=top-data ；19以下说法正确选项（）； A连通图 G 的生成树中可以包含回路 B连通图 G 的生成树可以是不连通的 C连通图 G 的生成树肯定是唯独的 D连通图 G 的生成树肯定是连通而不包含回路的 20设有一个带头结点的链队列,队列中每个结点由一个数据域 data 和指针域 next 组成, front 和 rear 分别为链队列的头指针和尾指

8、针,要执行出队操作,用 x 储存出队元素 的值, p 为指向结点类型的指针,可执行如下操作：p=front-next ；x=p-data；然后执行（）；Afront=p-next ； Bfront-next=p-next ；Cfront=p ； Dfront-next =p ；21 对 n 个元素进行冒泡排序,通常要进行n-1 趟冒泡,在第j 趟冒泡中共要进行2 / 33 名师归纳总结 - - - - - - -第 2 页,共 33 页精选学习资料 - - - - - - - - - （）次元素间的比较；Aj Bj-1 Cn-j Dn-j-1 22在排序过程中,可以有效地削减一趟排序过程中元素

9、间的比较次数的算法是（）；A冒泡 B选择 C直接插入 D折半插入23空串的长度为（）；A0 B1 C2 D3 24如图 1 所示,如从顶点 列为（）；a 动身按深度优先搜寻法进行遍历,就可能得到的顶点序Aaebcfd Babedcf a Cacebdf Dacfbdeb d e c f 图 1 25串函数 StrCmp“abA”,”aba”的值为（）；A1 B0 C“abAaba” D-1 26一棵哈夫曼树有 n 个叶子结点（终端结点）,该树总共有（）个结点；A2n-2 B2n-1 C2n D2n+2 27设有一个 10 阶的对称矩阵 A,采纳压缩储备方式将其下三角部分以行序为主序存储到一维数

10、组 b 中；（矩阵 A 的第一个元素为 a1,1,数组 b 的下标从 1 开头）,就矩阵元素 a5,3 对应一维数组 b 的数组元素是（）；A b18 Bb8 Cb13 Db10 28数据的（）结构与所使用的运算机无关；A规律 B物理 C储备 D规律与储备29已知如图 2 所示的一个图,如从顶点 a 动身,按深度优先搜寻法进行遍历,就可能得到的一种顶点序列为（）； Aabecdf B acfebd Caebcfd Daedfcb a b e c d f 图 2 二、填空题1通常可以把一本含有不同章节的书的目录结构抽象成 _结构；3 / 33 名师归纳总结 - - - - - - -第 3 页,

11、共 33 页精选学习资料 - - - - - - - - - 2通常数据的规律结构包括集合、线性、_、_四种类型；3要在一个单向链表中 p 所指向的结点之后插入一个 s 所指向的新结点,如链表中结点的指针域为 next ,可执行 _和 p-next=s；的操作；4通常可以把某城市中各公交站点间的线路图抽象成 _结构；5设有一个非空的链栈,栈顶指针为 hs,要进行出栈操作,用 x 储存出栈结点的值,栈结点的指针域为 next,就可执行 x=hs-data；_；6设有一个单向链表,结点的指针域为 next,头指针为 head,p 指向尾结点,为了使该单向链表改为单向循环链表,可用语句 _；7在一个

12、不带头结点的非空链队中,f 和 r 分别为队头和队尾指针,队结点的数据域为 data,指针域为next,如要进行出队操作,并用变量x 存放出队元素的数据值,就相关操作为 x=f-data； _；8循环队列的队头指针为f,队尾指针为r,当 _时说明队列已空；9循环队列的最大储备空间为MaxSize=8,采纳少用一个元素空间以有效的判定栈空或栈满,如队头指针 front=4 ,就当队尾指针 rear= _ 时,队列为空,当 rear= _时,队列有 6 个元素；10设有一个链栈,栈顶指针为 hs,现有一个 s 所指向的结点要入栈,就可执行操作_和 hs=s；11稀疏矩阵储备时,采纳一个由 定矩阵中

13、的一个非零元素；_ 、_、 _3 部分信息组成的三元组唯独确12在一个链队中,f 和 r 分别为队头和队尾指针,队结点的指针域为 next,就插入一个 s 所指结点的操作为 _；r=s；13一棵二叉树次序编号为6 的结点（树中各结点的编号与等深度的完全二叉中对应位置上结点的编号相同）,如它存在右孩子,就右孩子的编号为 _；14串的两种最基本的储备方式分别是_和 _ _；15结构中的数据元素存在多对多的关系称为 _结构；16一棵二叉树中次序编号为 别为 _ _、_ _；i 的结点,如它存在左、右孩子,就左、右孩子编号分17结构中的数据元素存在一对多的关系称为 _结构；18,两个串相等的充分必要条

14、件是；19如图 3 所示的二叉树,其前序遍历序列为 _ _；a b c d g e f 图 3 4 / 33 名师归纳总结 - - - - - - -第 4 页,共 33 页精选学习资料 - - - - - - - - - 20一棵二叉树叶结点（终端结点）数为5,单分支结点数为2,该树共有 _个结点；21在队列的次序储备结构中,当插入一个新的队列元素时,指针的值增 1,当删除一个元素队列时,指针的值增 1；22依据搜寻方法的不同,图的遍历有_、 _两种方法；23循环队列的引入,目的是为了克服；24一个有序表 3,4, 10,14,34, 43,46,64, 75,78,90,96,130用折半

15、查找法查找值为 90 的结点,经 _次比较后查找胜利；三、综合题 1（ 1）设 head1和 p1分别是不带头结点的单向链表 A 的头指针和尾指针,head2 和p2分别是不带头结点的单向链表 B 的头指针和尾指针,如要把 B 链表接到 A 链表之后,得到一个以 head1 为头指针的单向循环链表,写出其中两个关键的赋值语句（不用完整程序,结点的链域为 next）；（2）单向链表的链域为 next,设指针 p 指向单向链表中的某个结点,指针 s 指向一个要插入链表的新结点,现要把 s 所指结点插入 p 所指结点之后,某同学采纳以下语句： p-next=s； s-next=p-next ；这样做

16、正确吗？如正确就回答正确,如不正确就说明应如何改写；2（ 1）已知某二叉树的后序遍历序列是debca,中序遍历序列是dbeac,试画出该二叉树（ 2）如上述二叉树的各个结点的字符分别代表不同的整数（其中没有相等的）,并恰好使该树成为一棵二叉排序树,试给出（3）给出该树的前序遍历序列a、b、c、d、e 的大小关系；3（ 1）画出对长度为10 的有序表进行折半查找的判定树（以序号1,2, 10 表示树结点）（2）对上述序列进行折半查找,求等概率条件下,胜利查找的平均查找长度4（ 1）一组记录的关键字序列为45,40,65,43,35, 95,写出利用快速排序的方法,以第一个记录为基准得到的一趟划分

17、的结果（要求给出一趟划分中每次扫描和交换 的结果）（2）对序列 45,40,65,43,35,95利用直接插入排序,写出逐次插入过程（从第 一个元素始终到第六个元素）；5（ 1）利用选择法,把序列37, 77, 62 , 97, 11 , 27, 52, 47建成堆（小根堆）,画出相应的完全二叉树（2）写出对上述堆所对应的二叉树进行前序遍历得到的序列5 / 33 名师归纳总结 - - - - - - -第 5 页,共 33 页精选学习资料 - - - - - - - - - 6 1设有查找表 5,14,2,6,18,7,4,16,3, 依次取表中数据,构造一棵二叉排序树 . （2）说明如何通过

18、序列的二叉排序树得到相应序列的排序结果；四、程序填空题1以下函数为直接选择排序算法,对 成程序中的空格typedef struct int key； NODE；void selsortNODE a,int n int i,j,k ；NODE temp；a1,a2, an 中的记录进行直接选择排序,完fori=1；i= _1_；i+ k=i；forj=i+1 ；j= _2_；j+ ifaj.keydata=x；_2_；_3_； 期末综合练习一答案一、单项选择题1B 2 D 3 A4C5 D 6 C7 B 8 B 9 A 10 A11C 12 C13 D 14 C15 D 16 A17 D 18

19、A19 D 20 B21 C 22 D 23 A 24 B 25 D26B 27 C28A29 D 7 / 33 名师归纳总结 - - - - - - -第 7 页,共 33 页精选学习资料 - - - - - - - - - 二、填空题1树形 2树形；图状 3s-next= p-next；4图状 5hs=hs-next；6p-next=head ；7f=f-next ；8r=f 94；2 10s-next=hs；11行号；列号；非零元 12r-next=s 1313 14次序储备 链式储备15图状 162i 和 2i+1 17树形18串长度相等且对应位置的字符相等 19abdefcg 201

20、1 21尾 头22深度优先搜寻遍历 广度优先搜寻遍历 23假上溢 244 三、综合应用题1（1）p1-next= head 2；p2-next= head 1；（2）不对, s-next=p-next；p-next=s；2（ 1）a d b e c （2）dbeac （3）abdec 8 / 33 名师归纳总结 - - - - - - -第 8 页,共 33 页精选学习资料 - - - - - - - - - 3（ 1）5 1 2 3 4 6 8 9 10 7 （2） ASL=（1x1+2x2+3x4+4x3）/10=29/10 4（1） 45 40 65 43 35 95 35 40 65

21、43 35 95 35 40 65 43 65 95 35 40 43 43 65 95 35 40 43 45 65 95 （2） 40 45 65 43 35 95 40 43 45 65 35 95 35 40 43 45 65 95 5（ 1）77 37 62 37 11 27 47 97 11 27 52 堆9747 762 52 初始树（2）11, 37,47,97,77,27,62,52 9 / 33 名师归纳总结 - - - - - - -第 9 页,共 33 页精选学习资料 - - - - - - - - - 6（ 1）5 2 4 6 113 7 12 中序遍历四、程序填空题

22、1（ 1）n-1 （2）n （3）k=j （4）ai=ak （5）ak=temp 2（ 1）low=high （2）mid （3）amid.keyleft （2）printf“ %c”,BT-data （3） InorderBT-right 4（ 1）sizeof struct node （2）p-next=top （3）top=p 10 / 33 名师归纳总结 - - - - - - -第 10 页,共 33 页精选学习资料 - - - - - - - - - 期末综合练习二一、单项选择题1深度为 5 的完全二叉树共有20 个结点,就第5 层上有（）个结点 根所在结点为第一层 ；A3 B8

23、C5 D6 2同一种规律结构（）； A只能有唯独的储备结构 B可以有不同的储备结构 C只能表示某一种数据元素之间的关系 D以上三种说法均不正确3已知一个图的边数为m,就该图的全部顶点的度数之和为（）；A2mBm C2m+1 Dm/2 4链表所具备的特点是（）；A可以随机拜访任一结点 B占用连续的储备空间 C插入删除元素的操作不需要移动元素结点 D可以通过下标对链表进行直接拜访）结构；5数据结构中,与所使用的运算机无关的是数据的（ A物理 B储备 C规律与物理 D 规律 6数据的物理结构（）；A与数据的规律结构无关 B 仅仅包括数据元素的表示C只包括数据元素间关系的表示 D 包括数据元素的表示和

24、关系的表示7线性结构中数据元素的位置之间存在（）的关系；A一对一 B一对多C多对多 D每一个元素都有一个直接前驱和一个直接后继8线性表只要以（）方式储备就能进行折半查找；A链接 B次序 C关键字有序的次序 D二叉树9以下表中可以随机拜访的是（）；A单向链表 B 双向链表C单向循环链表 D次序表10散列查找的原理是（）；A在待查记录的关键字值与该记录的储备位置之间建立确定的对应关系B按待查记录的关键字有序的次序方式储备C按关键字值的比较进行查找D基于二分查找的方法11算法的时间复杂度与（）有关；A所使用的运算机 B与运算机的操作系统C与算法本身 D与数据结构12对 n 个元素进行冒泡排序如某趟冒

25、泡中只进行了（序列已经排好序；A1 B2 C0 Dn-1 ）次元素间的交换,就说明13设有一个长度为n 的次序表,要删除第i 个元素需移动元素的个数为（）；An-i+1 Bn-i Cn-i-1 Di 11 / 33 名师归纳总结 - - - - - - -第 11 页,共 33 页精选学习资料 - - - - - - - - - 14排序过程中,每一趟从无序子表中将一个待排序的记录按其关键字的大小放置到已经排好序的子序列的适当位置,直到全部排好序为止,该排序算法是 ；A直接插入排序 B快速排序C冒泡排序 D选择排序15在一个单链表中,p、q 分别指向表中两个相邻的结点,且 q 所指结点是 p

26、所指结点的直接后继,现要删除 q 所指结点,可用的语句是（）； A p=q-next Bp-next=q Cp-next=q next D q-next=NULL 16在对一组元素（64,48,106,33,25,82,70,55,93）进行直接插入排序时,当进行到要把第 7 个元素 70 插入到已经排好序的子表时,为找到插入位置,需进行（）次元素间的比较（指由小到大排序）；A6 B2 C3 D4 17从一个栈顶指针为 top 的链栈中删除一个结点时,用变量 x 储存被删结点的值,就执行（）；Ax=top-data； top=top-next； Bx=top-data ；C top=top-n

27、ext； x=top-data； Dtop=top-next； x=data ；18采纳次序查找法对长度为n 的线性表进行查找（不采纳表尾设监视哨的方法）,最坏的情形下要进行（）次元素间的比较；An+2 Bn Cn-1 Dn/2 19在一个链队中,假设 f 和 r 分别为队头和队尾指针,就删除一个结点的运算为（）； A r=f-next； B r=r-next； C f=f-next； D f=r-next；20如图 1,如从顶点 a 动身按广度优先搜寻法进行遍历,就可能得到的顶点序列为（）；Aacebdgf B abecdgf b d a g c f C acfedgb e Dabecfdg

28、图 1 21一个栈的进栈序列是a,b,c,d,e,就栈的不行能输出序列是（）（进栈出栈可以交替进行）；Adceab Bedcba Cdecba D abcde 22元素 2,4,6,8 按次序依次进栈,就该栈的不行能输出序列是（）（进栈出栈可以交替进行）； A8, 6,4,2 B2,4,6,8 C4,2,8, 6 D 8,6,2,4 23有一个长度为 10 的有序表,按折半查找对该表进行查找,在等概率情形下查找成功的平均比较次数为（）；A 26/10 B29/10 C29/9 D 31/10 24排序方法中,从未排序序列中选择元素,并将其依次放入已排序序列（初始为空）的一端的方法,称为（）排序

29、；12 / 33 名师归纳总结 - - - - - - -第 12 页,共 33 页精选学习资料 - - - - - - - - - A归并 B插入 C选择 D快速25排序算法中,从未排序序列中依次取出元素与已排序序列（初始为空）中的元素进行比较（要求比较次数尽量少）,然后将其放入已排序序列的正确位置的方法是（）；A冒泡 B直接插入 C折半插入 D选择排序26一棵哈夫曼树总共有23 个结点,该树共有（）个叶结点（终端结点）A10 B13 C11 D12 27设有一个 10 阶的对称矩阵 A,采纳压缩储备的方式,将其下三角部分以行序为主储备到一维数组 B 中（数组下标从 1 开头）,就矩阵中元素

30、 A8,5在一维数组 B 中的下标是（）；A33 B 32 C 85 D 41 28队列的插入操作在（）进行；A队头 B队尾 C队头或队尾 D在任意指定位置29在一个无向图中,全部顶点的度数之和等于边数的（）倍；A3 B2.5 C 1.5 D2 二、填空题1一棵二叉树没有单分支结点,有6 个叶结点,就该树总共有_个结点；2栈和队列的操作特点分别是_ _和 _ _；3设一棵完全二叉树,其最高层上最右边的叶结点的编号为奇数,该叶节点的双亲结点的编号为 10,该完全二叉树一共有 _个结点；4结构中的数据元素存在多对多的关系称为 _ _结构；5依据二叉树的递归定义,对二叉树遍历的常用算法有_、_、 _

31、三种；6依据数据元素间关系的不同特性,通常可分为集合、线性、四类基本结构；7数据结构中的数据元素存在一对多的关系称为 _结构；8要求在 n 个数据元素中找其中值最大的元素,设基本操作为元素间的比较；就比较的次数和算法的时间复杂度分别为 _和 _ ；9把数据储备到运算机中 ,并详细表达数据之间的规律结构称为 _结构；10在一个单向链表中 p 所指结点之后插入一个 s 所指向的结点时,应执行 _ _和 p-next=s；的操作；11结构中的数据元素存在一对一的关系称为 _结构；12在二叉树的链式储备结构中,通常每个结点中设置三个域,它们是值域、；13如图 2 所示的二叉树,其后序遍历序列为；13

32、/ 33 名师归纳总结 - - - - - - -第 13 页,共 33 页精选学习资料 - - - - - - - - - a b c d g e h f i 图 2 14一棵二叉树中次序编号为 别为 _、_；i 的结点,如它存在左、右孩子,就左、右孩子编号分15n 个元素进行冒泡法排序,通常需要进行_趟冒泡；s-next=h；和16向一个栈顶指针为h 的链栈中插入一个s 所指结点时,可执行_；17二叉树为二叉排序的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值；这种说法是 _的； 回答正确或不正确 18在一个链队中,设 f 和 r 分别为队头和队尾指针,就插入 s 所指结

33、点的操作为_和 r=s；结点的指针域为 next 19图的深度优先搜寻和广度优先搜寻序列不肯定是唯独的；此断言是 _的； 回答正确或不正确 20设有一棵深度为 4 的完全二叉树,第四层上有 5 个结点,该树共有 _个结点；（根所在结点为第 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建成堆（小根堆）,画出该堆（不要求中间过程）；（2）写出对上述堆对应的完全二叉树进行中序遍历得到的序列；2 1以 2,3, 4,7,8,9 作为叶结点的权,构造一棵哈夫曼树 14 /