2022年电大数据结构期末复习指导 .docx

精选学习资料 - - - - - - - - - 一、单项选择题（每道题 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, 6,7,8,就队列的输出序列是（）；A. 5 6 7 8 B. 8 7 6 5 C. 7 8 6 5 D.可能有多种情形q 所指结点是p 所指结点6. 串函数 StrCmp（“d” ,“D” ）的值为（）；A0 B 1 C -1 D3 7在一个单链表中,p、q 分别指向表中两个相邻的结点,且的直接后继,现要删除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 所示二叉树进行中序遍历,结果是（）；A. dfebagc B. defbagc C. defbacg D.dbaefcg a d b g c c f e 图 1 10 . 任何一个无向连通图的最小生成树（）；A. 至少有一棵 B. 只有一棵 C.肯定有多棵 D.可能不存在11设有一个 10 阶的对称矩阵 A ,采纳压缩储备的方式,将其下三角部分以行序为主序储备到一维数组 B 中（数组下标从 1 开头）,就矩阵中元素 A 8,5在一维数组 B 中的下标是（）；A 33 B32 C85 D 41 12 . 一组记录的关键字序列为（37, 70,47,29,31,85）,利用快速排序,以第一个关键字为分割元素,经过一次划分后结果为（）； A 31,29,37, 85,47,70 B29,31,37,47,70, 85 C 31,29,37,70,47,85 D 31,29,37,47,70,85 13 . 对 n 个元素进行冒泡排序,要求按升序排列,程序中设定某一趟冒泡没有显现元素交换,就终止排序过程；对某 n 个元素的排序共进行了 3n-6 次元素间的比较就完成了排1 / 21 名师归纳总结 - - - - - - -第 1 页,共 21 页精选学习资料 - - - - - - - - - 序,就（）；A. 原序列是升序排列B. 原序列是降序排列C. 对序列只进行了 2 趟冒泡D. 对序列只进行了 3 趟冒泡14在一个栈顶指针为 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 分）s 所指的新结点,应执行s->next=p-1在一个单向链表中p 所指结点之后插入一个>next ；和 _操作；2依据数据元素间关系的不同特性,通常可分为_、四类基本结构；3在一个链队中,设 f 和 r 分别为队头和队尾指针,就删除一个结点的操作为_ ；结点的指针域为 next 4._ 遍历二叉排序树可得到一个有序序列；5. 一棵有 2n-1 个结点的二叉树,其每一个非叶结点的度数都为 个叶结点；2,就该树共有 _6. 如图 1 所示的二叉树,其中序遍历序列为 _ _；a b c d g e h f i 图 1 7. 对稀疏矩阵进行压缩储备,矩阵中每个非零元素所对应的三元组包括该元素的_ 、_和_三项信息；8 . 有一个有序表 2,3,9,13,33,42,45,63,74,77,82,95,110,用折半查找法查找值为82 的结点,经 _次比较后查找胜利；9 . 图的深度优先搜寻和广度优先搜寻序列不是唯独的；此断言是 _的； 回答正确或不正确 10哈希法既是一种储备方法,又是一种；1144.在对一组记录 55,39,97,22,16,73,65,47,88 进行直接插入排序时,当把第 7 个记录 65 插入到有序表时,为查找插入位置需比较 _次；2 / 21 名师归纳总结 - - - - - - -第 2 页,共 21 页精选学习资料 - - - - - - - - - 12栈和队列的操作特点分别是 _和 _；三、综合题（每道题 10 分,共 30 分）1已知序列 11 ,19,5,4, 7,13,2,10 ,（1）试给出用归并排序法对该序列作升序排序时的每一趟的结果；（ 2）对上述序列用堆排序的方法建立初始堆（要求小根堆,以二叉树描述建堆过程）；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 分,共 16 分）1以下冒泡法程序对存放在a1 ,a2 , , an 中的序列进行冒泡排序,完成程序中的空格部分,其中 n 是元素个数,程序按升序排列；Void bsort NODE a , int NODE temp ； int i,j,flag；j+ ； forj=1；（ 1） flag=0； fori=1；（ 2）； i+ ifai.key>ai+1.key flag=1； temp=ai；（3）；（ 4）； ifflag= =0break； 程序中 flag 的功能是（ 5）7以下程序是后序遍历二叉树的递归算法的程序,完成程序中空格部分（树结构中左、右指针域分别为left 和 right ,数据域为data,其数据类型为字符型,BT 指向根结点）；Void Postorder struct BTree Node *BT ifBT.=NULL 3 / 21 名师归纳总结 - - - - - - -第 3 页,共 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. f=f->next ；4. 中序 5.n 6. dgbaechhif 7. 行号、列号、元素值 8.4 次 9. 正确 10查找方法 113 次 12先进后出 先进先出三、综合题（每道题 10 分,共 30 分）11 初始 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 10 4 19 7 11 5 2 10 4 19 7 2 11 2 5 13 13 11 4 / 21 名师归纳总结 4 2 4 5 第 4 页,共 21 页- - - - - - -精选学习资料 - - - - - - - - - 2 113,36,63,135 2 1 2 3 4 6 7 9 10 11 12 5 8 33 次31 2 5 14 4 6 18 3 7 16 2 中序遍历 中序 2,3, 4,5,6,7,14,16,18 四、程序填空题（每空 2 分,共 16 分）1（1）j<=n-1 5 / 21 名师归纳总结 - - - - - - -第 5 页,共 21 页精选学习资料 - - - - - - - - - （2）i<=n-j （3）ai=ai+1 （4）ai+1=temp （5）当某趟冒泡中没有显现交换就已排好序,终止循环 2（1）PostorderBT left （2）PostorderBT right （3）printf“ %c” ,BT data 其次部分 期末综合练习题一、 单项选择题（每道题 2 分）1针对线性表,在储备后假如最常用的操作是取第 i 个结点及其前驱,就采纳（）存储方式最节约时间；A单链表 B双链表 C 次序表 D单循环链表2带头结点的单向链表为空的判定条件是（）（设头指针为 head）；Ahead = =NULL B head.=NULL Chead->next= =head Dhead->next= =NULL 3链表所具备的特点是（）；A可以随机拜访任一结点 B占用连续的储备空间C插入删除元素的操作不需要移动元素结点 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-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=s next Bp next=s next ；Cs next=p next ； p next=s ； Dp next= s ； s next= p next 11从一个栈顶指针为 top 的链栈中删除一个结点时,用变量 x 储存被删结点的植,就执行（）；Ax=top->data； top=top next ； B x=top->data；Ctop=top->next； x=top->data； Dtop=top->next； x=data ；6 / 21 名师归纳总结 - - - - - - -第 6 页,共 21 页精选学习资料 - - - - - - - - - 12在一个链队中,假设f和 r分别为队头和队尾指针,就删除一个结点的运算为（）； Ar=f next ； Br=r next ； C f=f next ； Df=r next ；13在一个链队中,假设 f 和 r 分别为队头和队尾指针,就插入 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,5D1,3,5,7 15设有一个 18 阶的对称矩阵 A,采纳压缩储备的方式,将其下三角部分以行序为主序存储到一维数组 B 中（数组下标从 1 开头）,就矩阵中元素 a10,8 在一维数组 B 中的下标是（）；A18 B45 C 53D58 16在 C语言中,次序储备长度为 3 的字符串,需要占用（）个字节； 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 C n-1 D n+1 20一棵具有 35 个结点的完全二叉树,最终一层有（）个结点； A 4 B6 C16 D8 21一棵完全二叉树共有 5 层,且第 5 层上有六个结点,该树共有（）个结点； A30 B20 C 21 D23 22在一个无向图中,全部顶点的度数之和等于边数的（）倍； A3 B2 C2.5 D 1.5 23已知如图 1 所示的一个图,如从顶点 a 动身,按深度优先搜寻法进行遍历,就可能得到的一种顶点序列为（）； Aabecdf Bacfebd Caedfcb D aebcfd a b e c d f 图 1 24已知如图3 所示的一个图,如从顶点V1 动身,按广度优先法进行遍历,就可能得到的7 / 21 名师归纳总结 - - - - - - -第 7 页,共 21 页精选学习资料 - - - - - - - - - 一种顶点序列为（）；AV1V2V4V8V5V3V6V7 BV1V2V4V5V8V3V6V7CV1V2V4V8V3V5V6V7 DV1V3V6V7V2V4V5V8 V 1V 4V 2V 5V 6V 3V 7V 8图 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个元素排序到位,该方法是（）；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 D 二填空题39,80, 46,47,41,57 1把数据储备到运算机中,并详细表达数据之间的规律结构称为_结构；2算法的 5 个特点为 _；3结构中的数据元素存在的关系称为树形结构；4要求在 n 个数据元素中找其中值最大的元素,设基本操作为元素间的比较；就比较的次 数和算法的时间复杂度分别为 _和 _ ；5求两个 n 阶矩阵的乘积,算法的基本操作和时间复杂度分别为_和_；6在一个单向链表中p 所指结点之后插入一个s 所指向的结点时,应执行s->next=p-8 / 21 名师归纳总结 - - - - - - -第 8 页,共 21 页精选学习资料 - - - - - - - - - >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 ；结点的指针域为 next ；12在一个链队中,设 f 和 r 分别为队头和队尾指针,就插入 s 所指结点的操作为 r->next=s；和 结点的指针域为 next ；13在一个链队中,设 f 和 r 分别为队头和队尾指针,就删除一个结点的操作为 _；结点的指针域为 next 14.两个串相等的充分必要条件是 _；15对稀疏矩阵进行压缩储备,矩阵中每个非零元素对应的三元组包括该元素的 _、_和_ 三项信息；16在二叉树的链式储备结构中,通常每个结点中设置三个域,它们是 _、；17一棵有2n-1 个结点的二叉树,其每一个非叶结点的度数都为2,就该树共有 _个叶结点；18一棵二叉树中有2n-2 条边（结点间的连线）,其中每一个非叶结点的度数都为2,就该树共有 _个非叶结点；19中序遍历二叉排序树可得到一个；20如图 1 所示的二叉树,其中序遍历序列为_；b a c a b c d e f _；d e g g h i f 图 2 图 1 21如图 1 所示的二叉树,其先序遍历序列为22如图 1 所示的二叉树,其后序遍历序列为_；23如图 2 所示的二叉树,其前序遍历序列为_；24哈希函数是记录关键字值与该记录储备地址之间所构造的对应关系；9 / 21 名师归纳总结 - - - - - - -第 9 页,共 21 页精选学习资料 - - - - - - - - - 25图的深度优先搜寻和广度优先搜寻序列不肯定是唯独的；此断言是 _的； 回答正确或不正确 26 n 个元素进行冒泡法排序,通常需要进行_趟冒泡,第j 趟冒泡要进行 _次元素间的比较；三、综合题1设一组记录的关键字序列为（49,83, 59,41,43,47）,采纳堆排序算法完成以下操作：（要求小根堆,并画出中间过程）（1）以二叉树描述 6 个元素的初始堆（2）以二叉树描述逐次取走堆顶元素后,经调整得到的 2已知序列 11 ,19,5,4,7,13,2,10 5 个元素、 4 个元素的堆（1）试给出用归并排序法对该序列作升序排序时的每一趟的结果；（2）对上述序列用堆排序的方法建立初始堆（要求小根堆,以二叉树描述建堆过程）；3一组记录的关键字序列为（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 用冒泡法对该表进行排序（要求升序排列）,要求写出每一趟的排序过程,通常对 n个元素进行冒泡排序要进行多少趟冒泡？第j 趟要进行多少次元素间的比较？ 2 在排序后的有序表的基础上,画出对其进行折半查找所对应的判定树 .要求以数据元素作为树结点 3 求在等概率条件下,对上述有序表胜利查找的平均查找长度. 6（1）假如二叉树中任一结点的值均大于其左孩子的值、小于其右孩子的值,就该树为二叉排序树,这种说法是否正确？如认为正确,就回答正确,如认为不正确,就举例说明；（ 2）设有数据集合 40 ,29, 7, 73,101,4, 55,2,81, 92,39 ,依次取集合中各数据,构造一棵二叉排序树 . 7 1 设有查找表 5,14,2,6,18,7,4,16,3, 依次取表中数据,构造一棵二叉排序树 . （2）说明如何由序列的二叉排序树得到相应序列的排序结果,对上述二叉排序给出中序遍历的结果 . 81 “ 一棵二叉树如它的根结点的值大于左子树全部结点的值,小于右子树全部结点的值,就该树肯定是二叉排序树” ；该说法是否正确,如认为正确,就回答正确,如认为不正确就说明理由？2设有查找表 7 ,16,4,8,20, 9,6,18,5 ,依次取表中数据构造一棵二叉排序树 . 对上述二叉树给出后序遍历的结果 . 9 1 以 2,3,4,7, 8,9 作为叶结点的权,构造一棵哈夫曼树,给出相应权重值叶结点的10 / 21 名师归纳总结 - - - - - - -第 10 页,共 21 页精选学习资料 - - - - - - - - - 哈夫曼编码；2 一棵哈夫曼树有 n 个叶结点,它一共有多少个结点？简述理由？10（ 1）对给定权值 2,1,3, 3,4,5,构造哈夫曼树；（2）同样用上述权值构造另一棵哈夫曼树,使两棵哈夫曼树有不同的高度,并分别 求两棵树的带权路径长度；11如下列图的二叉树（1）给出中序遍历序列 a （2）给出先序遍历序列（3）给出后序遍历序列d g b e c h f i 四、程序填空题1以下冒泡法程序对存放在a1,a2, , an中的序列进行冒泡排序完成程序中的空格部分,其中 n 是元素个数,要求按升序排列；void bsort NODE a , int n NODE temp ； int i,j,flag ； forj=1 ； j+ ； flag=0 ； fori=1 ； i+ ifai.key>ai+1.key flag=1 ； temp=ai ； ifflag= =0break ； 程序中 flag 的功能是2以下是用尾插法建立带头结点且有n 个结点的单向链表的程序,结点中的数据域从前向后依次为 1,2,3, ,n,完成程序中空格部分；NODE *createn NODE *head , *p, *q； int i ； p=NODE*mallocsizeofNODE；head=；p next=NULL ； /* 建立头结点 */ 11 / 21 名师归纳总结 - - - - - - -第 11 页,共 21 页精选学习资料 - - - - - - - - - fori=1 ； i<=n ； i+ p=； p->data=i ； p->next=NULL ； q->next= ； returnhead； 3以下是用头插法建立带头结点且有n 个结点的单向链表的程序,要求结点中的数据域从前向后依次为 n,n-1, ,1,完成程序中空格部分；NODE *create2n NODE *head , *p, *q； int i ； p=NODE*mallocsizeofNODE；p->next=NULL ；head=；fori=1 ； i<=n ； i+ p=； p->data=i ； ifi= =1 p->next=NULL ； else p->next= ；q->next= returnhead； 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 ； /* 以上终止建表过程 */ p=head； /*p 为工作指针,预备输出链表 */ 12 / 21 名师归纳总结 - - - - - - -第 12 页,共 21 页精选学习资料 - - - - - - - - - do printf “ %dn”, ； while ； 5以下程序是先序遍历二叉树的递归算法的程序,完成程序中空格部分（树结构中左、右指针域分别为left 和 right,数据域data为字符型, BT 指向根结点）；void Preorder struct BTreeNode *BT ifBT.=NULL ； 6以下程序是中序遍历二叉树的递归算法的程序,完成程序中空格部分（树结构中左、右指针域分别为left 和 right,数据域data为字符型, BT 指向根结点）；void Inorder struct BTreeNode *BT ifBT.=NULL ； 7以下程序是后序遍历二叉树的递归算法的程序,完成程序中空格部分（树结构中,左、右指针域分别为 left 和 right,数据域 data 为字符型, BT 指向根结点）；void Postorder struct BTreeNode *BT ifBT.=NULL ； 8以下程序是中序遍历二叉树的递归算法的程序,完成程序中空格部分（树结构中左、右指针域分别为left 和 right,数据域data为字符型, BT 指向根结点）；void Inorder struct BTreeNode *BT b a c ifBT.=NULL （1）；（2）；InorderBT->right ； 利用上述程序对右图进行遍历,结果是；d e f 13 / 21 名师归纳总结 - - - - - - -第 13 页,共 21 页精选学习资料 - - - - - - - - - 综合练习题答案一、单项选择题1C 2 D 3 C 4 D 5 B6C 7 A 8 B 9D 10 C 11 A 12 C 13 C 14 B15C 16 A 17B 18 A 19C 20A 21 C 22 B 23 C 24 A 25 B 26 C27A28D 29 C30 B 二、填空题 物理（储备）有穷性、确定性、可行性、零个或多个输入、一个或多个输入3树形 4n-1,On 5乘法, On 3 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值