《2022年电大数据结构期末复习指导.docx》由会员分享，可在线阅读，更多相关《2022年电大数据结构期末复习指导.docx（22页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精品学习资源一、单项选择题（每道题2 分，共 30 分）1. 数据结构中，与所使用的运算机无关的是数据的（）结构；A. 规律B.物理C.储备D.规律与物理2. 下述各类表中可以随机拜访的是（）；A. 单向链表B.双向链表C.单向循环链表D.次序表3. 在一个长度为n 的次序表中为了删除第5 个元素，从前到后依次移动了15 个元素；就原次序表的长度为（）；A. 21B. 20C. 19D. 254. 元素 2，4， 6 按次序依次进栈，就该栈的不行能的输出序列是（）；A. 6 4 2B. 6 2 4C. 4 2 6D. 2 6 45. 一个队列的入队序列是5， 6， 7， 8，就队列的输出序列是
2、（）；A. 5 6 7 8B. 8 7 6 5C. 7 8 6 5D.可能有多种情形6. 串函数 StrCmp（“ d”，“ D”）的值为（）；A 0B 1 C -1D 37. 在一个单链表中， p、q 分别指向表中两个相邻的结点，且q 所指结点是 p 所指结点的直接后继，现要删除q 所指结点，可用语句（）；A p=q-nextB p-next=qC p-next=q-next D q-next=NULL8. 设一棵哈夫曼树共有n 个非叶结点，就该树一共有（）个结点；A. 2*n-1B. 2*n +1C. 2*nD. 2*n-19. 对如图 1 所示二叉树进行中序遍历，结果是（）；A. dfe
3、bagcB. defbagcC. defbacgD.dbaefcgabccdgef图 110 .任何一个无向连通图的最小生成树（）；A. 至少有一棵 B. 只有一棵 C. 肯定有多棵 D. 可能不存在11设有一个 10 阶的对称矩阵 A ，采纳压缩储备的方式，将其下三角部分以行序为主序储备到一维数组B 中（数组下标从1 开头），就矩阵中元素A 8,5 在一维数组B 中的下标是（）；A 33B32C 85D 4112 .一组记录的关键字序列为（37， 70， 47， 29， 31， 85），利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（）；A 31， 29，37， 85，47，
4、70B 29， 31， 37， 47，70， 85C 31， 29， 37， 70， 47，85D 31，29， 37， 47， 70， 8513 .对 n 个元素进行冒泡排序，要求按升序排列，程序中设定某一趟冒泡没有显现元素交换，就终止排序过程；对某n 个元素的排序共进行了3n-6 次元素间的比较就完成了排欢迎下载精品学习资源序，就（）；A. 原序列是升序排列B. 原序列是降序排列C. 对序列只进行了 2 趟冒泡D. 对序列只进行了 3 趟冒泡14. 在一个栈顶指针为top的链栈中删除一个结点时，用x 储存被删除的结点，应执行（）；A.x=top-data；top=top-next；B.to
5、p=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 分别为队头和队尾指针，就删除一个结点的操作为 ；结点的指针域为next4. 遍历二叉排序树可得到一个有序序列；5. 一棵有 2n-1 个结点的二叉树，其每一个
6、非叶结点的度数都为2，就该树共有 个叶结点；6. 如图 1 所示的二叉树，其中序遍历序列为 ；abcdefghi图 17. 对稀疏矩阵进行压缩储备，矩阵中每个非零元素所对应的三元组包括该元素的 、和三项信息；8 .有一个有序表 2,3,9,13,33,42,45,63,74,77,82,95,110,用折半查找法查找值为82 的结点，经次比较后查找胜利；欢迎下载精品学习资源9 . 图的深度优先搜寻和广度优先搜寻序列不是唯独的；此断言是确或不正确 10哈希法既是一种储备方法，又是一种； 的； 回答正欢迎下载精品学习资源11 44.在对一组记录 55,39,97,22,16,73,65,47,88
7、 进行直接插入排序时，当把第7 个记录 65 插入到有序表时，为查找插入位置需比较 次；欢迎下载精品学习资源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 次元素间的比较才
8、能胜利查到（ 2）画出对上述有序表进行折半查找所对应的判定树（树结点用下标表示）（ 3）设查找元素5，需要进行多少次元素间的比较才能确定不能查到.31 设有查找表 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,f
9、lag；forj=1；（ 1）；j+ ；flag=0；fori=1；（ 2）； i+ ifai.keyai+1.keyflag=1；temp=ai；（ 3）；（ 4）；ifflag= =0break；程序中 flag的功能是（ 5）7以下程序是后序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为left 和 right ，数据域为data，其数据类型为字符型，BT 指向根结点）；Void Postorder struct BTree Node *BTifBT.=NULL欢迎下载精品学习资源（ 1）；（ 2）；（ 3）；试卷答案；一、单项选择题（每道题2 分，共 30
10、分）1 A2 D3 B4 B5 A6 C7 C8 B9 A10 A11 A 12 D 13 D 14 A15 D二、填空题（每道题2 分，共 24 分）1.p-next=s；2. 集合、线性、树形、图状3. f=f-next ；4. 中序5.n6. dgbaechhif7. 行号、列号、元素值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
11、， 10，11， 13， 19 21111欢迎下载精品学习资源195192欢迎下载精品学习资源欢迎下载精品学习资源4713247135欢迎下载精品学习资源10101124 / 214245欢迎下载精品学习资源2 113,36,63,135639147112581012521446183716233 次3 12 中序遍历中序 2，3， 4， 5，6， 7，14， 16， 18四、程序填空题（每空2 分，共 16 分） 1（ 1）j=n-1欢迎下载精品学习资源（ 2）inext= =headD head-next= =NULL3链表所具备的特点是（A可以随机拜访任一结点）；B占用连续的储备空间C插
12、入删除元素的操作不需要移动元素结点D可以通过下标对链表进行直接拜访4 非空的单向循环链表的尾结点满意（）（设头指针为head，指针 p 指向尾结点）；A p-next = =NULLB p= =NULLC p= =head D p-next= =head 5数据结构中，与所使用的运算机无关的是数据的（）结构；A物理B规律C储备 D规律与物理6. 算法的时间复杂度与（）有关；A所使用的运算机B运算机的操作系统C算法本身 D数据结构7. 设有一个长度为n 的次序表，要在第i 个元素之前插入一个元素（也就是插入元素作为新表的第 i 个元素），就移动元素个数为（）；A n-i+1B n-iCn-i-1
13、D i8. 设有一个长度为n 的次序表，要删除第i 个元素需移动元素的个数为（）；A n-i+1B n-iC n-i-1Di9. 在一个单链表中， p、q 分别指向表中两个相邻的结点，且q 所指结点是 p 所指结点的直接后继，现要删除q 所指结点，可用的语句是（）；A p=q-nextB p-next=qC q-next=NULL D p-next=q-next10在一个单链表中p 所指结点之后插入一个s 所指的结点时，可执行（）；A p=snext B pnext=snext ；C snext=pnext ； pnext=s ；Dpnext= s ； snext= pnext 11从一个栈顶
14、指针为top的链栈中删除一个结点时，用变量x 储存被删结点的植，就执行（）；A. x=top-data； top=topnext ； Bx=top-data；C top=top-next； x=top-data； D top=top-next； x=data ；欢迎下载精品学习资源12. 在一个链队中，假设f和 r分别为队头和队尾指针，就删除一个结点的运算为（）；A r=fnext ； B r=rnext ； C f=fnext ； D f=rnext ；13. 在一个链队中，假设f和 r分别为队头和队尾指针，就插入s 所指结点的运算为（）；A f-next=s； f=s ；B s-next=
15、r； r=s ；C r-next=s； r=s ；D s-next=f ；f=s ；14. 元素 1， 3，5， 7 按次序依次进栈，就该栈的不行能输出序列是（）（进栈出栈可以交替进行）；A 7，5， 3， 1B 7， 5，1， 3C 3，1， 7， 5D 1， 3，5， 715. 设有一个 18 阶的对称矩阵 A，采纳压缩储备的方式，将其下三角部分以行序为主序存储到一维数组 B 中（数组下标从1 开头），就矩阵中元素a10,8 在一维数组B 中的下标是（）；A 18 B 45C 53D5816. 在 C 语言中，次序储备长度为3 的字符串，需要占用（）个字节； A 4B3C 6D12 17一
16、棵有 n 个结点采纳链式储备的二叉树中，共有（）个指针域为空；A nB n+1C n-1D n-2 18在一棵二叉树中，如编号为i 的结点存在左孩子，就左孩子的次序编号为（）；A 2iB 2i-1C 2i+1D 2i+2 19设一棵哈夫曼树共有n 个叶结点，就该树有（）个非叶结点；A nB 2n C n-1 D n+120一棵具有 35 个结点的完全二叉树，最终一层有（）个结点；A 4B 6C16D 821一棵完全二叉树共有5 层，且第5 层上有六个结点，该树共有（）个结点；A 30B 20 C 21D2322. 在一个无向图中，全部顶点的度数之和等于边数的（）倍；A 3B 2C 2.5D 1
17、.523. 已知如图 1 所示的一个图，如从顶点a 动身，按深度优先搜寻法进行遍历，就可能得到的一种顶点序列为（）；A abecdfB acfebdCaedfcb D aebcfdabecdf图 124. 已知如图 3 所示的一个图，如从顶点V1 动身，按广度优先法进行遍历，就可能得到的欢迎下载精品学习资源一种顶点序列为（）；A V1V2V4V8V5V3V6V7B V1V2V4V5V8V3V6V7C V1V2V4V8V3V5V6V7DV 1 V1V3V6V7V2V4V5V8V 2V 3V 4V 5V 6V 7V 8图 325在有序表 1 ， 3， 8， 13， 33， 42， 46， 63，7
18、6，78， 86， 97， 100 中，用折半查找值86 时，经（）次比较后查找胜利；A 3 B 4 C 6D826. 对二叉排序树进行（）遍历，可以使遍历所得到的序列是有序序列；A按层次B后序C中序D前序27. 有一个长度为12 的有序表，按折半查找对该表进行查找，在等概率情形下查找胜利的平均比较次数为（）；A 37/12B39/12C41/12D 35/1228. 设已有 m 个元素有序，在未排好序的序列中选择第m+1 个元素，并且只经过一次元素的交换就使第m+1个元素排序到位，该方法是（）；A折半排序B冒泡排序C归并排序D简洁选择排序29. 一组记录的关键字序列为（46， 79， 56，
19、 38， 40， 84），利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（）；A 40， 38， 46， 79， 56，84B40， 38，46， 84，56， 79 C 40， 38， 46， 56， 79， 84D 38， 40， 46， 56， 79， 8430. 一组记录的关键字序列为（47， 80， 57， 39， 41， 46），利用堆排序（堆顶元素是最小元素）的方法建立的初始堆为（）；A 39， 47， 46， 80， 41，57B 39， 41， 46， 80， 47，57 C 41，39， 46，47， 57，80D 39， 80， 46， 47， 41， 57
20、二填空题1. 把数据储备到运算机中,并详细表达数据之间的规律结构称为 结构；2. 算法的 5 个特点为；3. 结构中的数据元素存在的关系称为树形结构；4. 要求在 n 个数据元素中找其中值最大的元素，设基本操作为元素间的比较；就比较的次数和算法的时间复杂度分别为 和；5. 求两个 n 阶矩阵的乘积，算法的基本操作和时间复杂度分别为 和；6. 在一个单向链表中p 所指结点之后插入一个s 所指向的结点时，应执行s-next=p-欢迎下载精品学习资源next ；和的操作；7. 设有一个头指针为head 的单向循环链表，p 指向链表中的结点，如p-next=head，就p 所指结点为；8. 在一个单向
21、链表中，要删除p 所指结点，已知 q 指向 p 所指结点的前驱结点；就可以用操作；9. 设有一个头指针为head 的单向链表， p 指向表中某一个结点，且有p-next= =NULL, 通过操作,就可使该单向链表构造成单向循环链表；10. 向一个栈顶指针为h 的链栈中插入一个s 所指结点时，可执行s-next=h； 和操作； 结点的指针域为 next11. 从一个栈顶指针为h 的链栈中删除一个结点时，用x 储存被删结点的值，可执行和 h=h-next ；结点的指针域为 next ；12. 在一个链队中，设f 和 r 分别为队头和队尾指针，就插入s 所指结点的操作为r-next=s；和 结点的指
22、针域为 next ；13. 在一个链队中，设f 和 r 分别为队头和队尾指针，就删除一个结点的操作为 ； 结点的指针域为 next14. 两个串相等的充分必要条件是 ；15. 对稀疏矩阵进行压缩储备，矩阵中每个非零元素对应的三元组包括该元素的 、 和三项信息；16. 在二叉树的链式储备结构中，通常每个结点中设置三个域，它们是 、；17. 一棵有 2n-1 个结点的二叉树，其每一个非叶结点的度数都为2，就该树共有个叶结点；18. 一棵二叉树中有2n-2 条边（结点间的连线），其中每一个非叶结点的度数都为2，就该树共有个非叶结点；19. 中序遍历二叉排序树可得到一个；aabcbcdefdgeghi
23、f20. 如图 1 所示的二叉树，其中序遍历序列为 ；图 1图 221如图1 所示的二叉树，其先序遍历序列为 ；22如图1 所示的二叉树，其后序遍历序列为 ；23如图2 所示的二叉树，其前序遍历序列为 ；24. 哈希函数是记录关键字值与该记录储备地址之间所构造的对应关系；欢迎下载精品学习资源25. 图的深度优先搜寻和广度优先搜寻序列不肯定是唯独的；此断言是确或不正确 的； 回答正欢迎下载精品学习资源26. n 个元素进行冒泡法排序，通常需要进行 趟冒泡，第 j 趟冒泡要进行次元素间的比较；三、综合题1. 设一组记录的关键字序列为（49， 83， 59， 41， 43， 47），采纳堆排序算法完
24、成以下操作：（要求小根堆，并画出中间过程）（ 1）以二叉树描述 6 个元素的初始堆（ 2）以二叉树描述逐次取走堆顶元素后，经调整得到的5 个元素、 4 个元素的堆2已知序列 11 ， 19， 5， 4， 7， 13，2， 10（ 1）试给出用归并排序法对该序列作升序排序时的每一趟的结果；（ 2）对上述序列用堆排序的方法建立初始堆（要求小根堆，以二叉树描述建堆过程）；3一组记录的关键字序列为（46， 79， 56， 38， 40， 84）（ 1）利用快速排序的方法，给出以第一个记录为基准得到的一次划分结果（给出逐次交换元素的过程，要求以升序排列）（ 2）对上述序列用堆排序的方法建立大根堆，要求以
25、二叉树逐次描述建堆过程；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) 在排序后的有序表的基础上，画出对其进行折半查找所对应的判定树. 要求以
26、数据元素作为树结点 (3) 求在等概率条件下,对上述有序表胜利查找的平均查找长度. 6（ 1）假如二叉树中任一结点的值均大于其左孩子的值、小于其右孩子的值，就该树为二叉排序树，这种说法是否正确？如认为正确，就回答正确，如认为不正确，就举例说明；（ 2）设有数据集合 40 ， 29， 7， 73， 101， 4， 55， 2， 81， 92， 39 ，依次取集合中各数据，构造一棵二叉排序树.71 设有查找表 5,14,2,6,18,7,4,16,3, 依次取表中数据，构造一棵二叉排序树.（ 2）说明如何由序列的二叉排序树得到相应序列的排序结果，对上述二叉排序给出中序遍历的结果 .81 “一棵二叉
27、树如它的根结点的值大于左子树全部结点的值，小于右子树全部结点的值，就该树肯定是二叉排序树”；该说法是否正确，如认为正确，就回答正确，如认为不正确就说明理由？2 设有查找表 7 ， 16， 4， 8， 20， 9， 6， 18， 5 ，依次取表中数据构造一棵二叉排序树.对上述二叉树给出后序遍历的结果. 9(1) 以 2，3， 4， 7， 8， 9 作为叶结点的权，构造一棵哈夫曼树，给出相应权重值叶结点的欢迎下载精品学习资源哈夫曼编码；(2) 一棵哈夫曼树有 n 个叶结点，它一共有多少个结点？简述理由？ 10（ 1）对给定权值2， 1， 3， 3， 4， 5，构造哈夫曼树；（ 2）同样用上述权值构
28、造另一棵哈夫曼树，使两棵哈夫曼树有不同的高度，并分别求两棵树的带权路径长度；11. 如下列图的二叉树（ 1）给出中序遍历序列a（ 2）给出先序遍历序列（ 3）给出后序遍历序列bcdefghi四、程序填空题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.keyai+1.keyflag=1 ；temp=ai ；ifflag= =0bre
29、ak ；程序中 flag 的功能是2. 以下是用尾插法建立带头结点且有n 个结点的单向链表的程序，结点中的数据域从前向后依次为 1,2,3, ,n，完成程序中空格部分；NODE *createnNODE *head , *p, *q；int i ；p=NODE*mallocsizeofNODE；head=； ；pnext=NULL ； /* 建立头结点 */欢迎下载精品学习资源fori=1 ； idata=i ；p- next=NULL ；q- next=；returnhead；3. 以下是用头插法建立带头结点且有n 个结点的单向链表的程序，要求结点中的数据域从前向后依次为n,n-1, ,1，
30、完成程序中空格部分；NODE *create2nNODE *head , *p, *q；int i ；p=NODE*mallocsizeofNODE；p-next=NULL ；head=；fori=1 ； idata=i ；ifi= =1p-next=NULL ；elsep-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.
31、data=4； /*d 是尾结点 */ head=；a.next=&b ；b.next=&c ；c.next=&d ； /* 以上终止建表过程*/p=head； /*p 为工作指针，预备输出链表*/欢迎下载精品学习资源doprintf “%dn”,；while；5. 以下程序是先序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为 left 和 right ，数据域 data 为字符型， BT 指向根结点）；void Preorder struct BTreeNode *BTifBT.=NULL；6. 以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构
32、中左、右指针域分别为 left 和 right ，数据域 data 为字符型， BT 指向根结点）；void Inorder struct BTreeNode *BTifBT.=NULL；7. 以下程序是后序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中，左、右指针域分别为left 和 right ，数据域 data 为字符型， BT 指向根结点）；void Postorder struct BTreeNode *BTifBT.=NULL；8. 以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为 left 和 right ，数据域 data 为字
33、符型， BT 指向根结点）；void Inorder struct BTreeNode *BT欢迎下载精品学习资源ifBT.=NULL（ 1） ；（ 2）；InorderBT-right ；利用上述程序对右图进行遍历，结果是；abcdef欢迎下载精品学习资源综合练习题答案一、单项选择题1 C 2 D3 C4 D5 B6 C 7 A 8 B9 D 10 C 11 A 12 C 13 C14 B15C 16 A 17 B 18 A19 C 20 A 21 C 22 B 23 C 24 A25 B26 C27A28 D 29 C30 B二、填空题 物理（储备）有穷性、确定性、可行性、零个或多个输入、
34、一个或多个输入3树形4 n-1,On 5乘法， On 36. s-next=p-next ；7. head8. q-next=p-next ；9. p-next=head ；10. s-next=h；11. h=h-next ；12. r-next=s ；13. f=f-next ；14串长度相等且对应位置的字符相等15行下标、列下标、非零元素值16值域、左指针、右指针17 n18 n-1 19中序20. dgbaechif21. abdgcefhi22. gdbeihfca23. abdefcg 24储备地址25正确26 n-1,n-j三、综合题1 1欢迎下载精品学习资源494949欢迎下载
35、精品学习资源835941434783474143594147834359欢迎下载精品学习资源4141欢迎下载精品学习资源49478343594347834959欢迎下载精品学习资源2594343434759474947欢迎下载精品学习资源834941834941835941欢迎下载精品学习资源475949495947欢迎下载精品学习资源834341834341欢迎下载精品学习资源2欢迎下载精品学习资源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
36、， 11， 10，11， 1321111195192471324713510101124245欢迎下载精品学习资源1971351071311欢迎下载精品学习资源10193(1) 初始序列46， 79， 56， 38， 40， 8440， 79， 56， 38， 40， 8440， 79， 56，38， 79， 8440， 38， 56， 38， 79， 8440， 38， 56，56， 79， 8440， 38， 46， 56， 79， 8424646欢迎下载精品学习资源795638408416 / 217984384056欢迎下载精品学习资源8484欢迎下载精品学习资源79463840567956384046欢迎下载精品学习资源4 16391471025811(2) 4 次3ASL=1+2*2+3*4+4*4/11=351 原序列 16 1520 53 64 715 1620 53 764n-1 趟15 1620 75364n-j 次151672053641571620536471516205364216753152064欢迎下载精品学习资源3平均查找长度 =（ 1*1+2*2+3*3 ） /6=14/66(1) 不正确，例2145(2) 2402973欢迎下载精品学习资源73955101欢迎下载精品学习资源481292715214