《2022年数据结构模拟试卷和答案.docx》由会员分享，可在线阅读，更多相关《2022年数据结构模拟试卷和答案.docx（29页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆北京语言高校网络训练学院数据结构模拟试卷一留意：1. 试卷保密,考生不得将试卷带出考场或撕页,否就成果作废；请监考老师负责监督；2. 请各位考生留意考试纪律,考试作弊全部成果以零分运算；3. 本试卷满分100 分,答题时间为90 分钟；4. 本试卷分为试题卷和答题卷,全部答案必需答在答题卷上,答在试题卷上不给分；一、【单项挑选题】 本大题共 10 小题,每道题 2 分,共 20 分 在每道题列出的四个选项中只有一个选项是符合题目要求的,请将正确选项前的字母填在 答题卷相应题号处；1、如某线性表最常用的操作是存取任一指定
2、序号的元素和在最终进行插入和删除运算,就采纳（）储备方式最节约时间；（）的二叉树； A 次序表 B 双链表 C 带头结点的双循环链表 D 单循环链表2、队列操作的原就是（）； A 只能进行删除 B 后进先出 C 只能进行插入 D 先进先出3、某二叉树的先序序列和后序序列正好相反,就该二叉树肯定是 A 空或只有一个结点 C 任一结点无左孩子 B 高度等于其结点数 D 任一结点无右孩子4、在以下排序方法中, （）方法平均时间复杂度为 0nlogn ,最坏情形下时间复杂度为 0n 2； A 插入排序 B 希尔排序 C 快速排序 D 堆排序5、对二叉树从 1 开头进行连续编号,要求每个结点的编号大于其
3、左、右孩子的编号,同一个结点的左、右孩子中,其左孩子编号小于右孩子编号；就可采纳（）次序的遍历实现编号； A 先序 B 中序 C 后序 D 从根开头的层次遍历6、如用数组 Sn 作为两个栈 S1 和 S2 的共用储备结构,对任何一个栈,只有当 Sn 全满时才不能作入栈操作；为这两个栈安排空间的正确方案是（）； A S1 的栈底位置为 0,S2 的栈底位置为 n B S1 的栈底位置为1,S2 的栈底位置为 n/2 C S1 的栈底位置为 0,S2 的栈底位置为 n1 D S1 的栈底位置为 0,S2 的栈底位置为 n/27、对一棵二叉排序树进行（）遍历,可以得到该二叉树的全部结点按值从小到名师
4、归纳总结 - - - - - - -第 1 页,共 18 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆大排列的序列； A 前序 B 后序 C 中序 D 按层次8、在以下排序算法中, （）算法可能会显现下面情形：在最终一趟开头之前,所有元素都不在其最终的位置上； A 堆排序 B 冒泡排序 C 快速排序 D 插入排序9、采纳邻接表储备的图的广度优先算法类似于二叉树的（）； A 先序遍历 B 中序遍历 C 后序遍历 D 层次遍历10、具有 6 个顶点的无向图至少应有（）条边才能保证图的连通性； A 4 B 5 C 6 D 7F,填二、【判定题】 本大题共 10 小题
5、,每道题2 分,共 20 分 正确的填 T,错误的填在 答题卷相应题号处；11 、线性表如采纳链式储备表示时全部结点之间的储备单元地址可连续可不连续；（）12、任何二叉树都唯独对应一个森林,反之亦然；（）13、有向图的邻接矩阵肯定是对称的；（）14、线性表的链式储备结构优于次序储备结构；（）15、关键路径可能不只一条,但缩短某一关键路径肯定能够缩短工期；（）16、直接挑选排序是一种不稳固的排序方法；（）17、次序表用一维数组作为储备结构,因此次序表是一维数组；（）18、栈和队列都是次序存取的的线性表,但它们对存取位置的限制不同；（）19、闭散列法通常比开散列法时间效率更高；（）20、一棵 m阶
6、 B 树中每个结点最多有 m个关键码, 最少有 2 个关键码；（）三、【填空题】（本大题共 10 小空,每小空 2 分,共 20 分）请将答案填写在 答题卷相应题号处 ；名师归纳总结 21、数据结构课程争论的主要内容是数据的规律结构、储备结构和（）；第 2 页,共 18 页22、如要在单链表结点*P 后插入一结点 *S,执行的语句（）；23、折半搜寻只适合用于（）；24、栈结构答应进行删除操作的一端为（）；25、设一行优先次序储备的数组A56,A00的地址为 1100,且每个元素占2 个储备单元,就A23的地址为（）；26、如某二叉树有20 个叶子结点, 有 30 个结点仅有一个孩子,就该二叉
7、树的总结点个数为（）；27、一棵具有5 层满二叉树中节点总数为（）；28、从树中一个结点到另一个结点之间的分支构成这两个结点之间的（）；- - - - - - -精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆29、在无向图中,如从顶点 A 到顶点 B 存在（）,就称 A 与 B 之间是连通的；30、如图的邻接矩阵是对称矩阵,就该图肯定是（）；四、【应用题】（本大题共 5 小题,每道题 8 分,共 40 分）请将答案填写在 答题卷相应题号处 ；31、已知序列（ 12,4, 17,10,7,30）,用直接挑选排序法对其进行递增排序,写出每一趟的排序结果；32、单链表结
8、点的类型定义如下：typedef struct LNode int data; struct LNode *next; LNode, *Linklist; 写一算法,将带头结点的有序单链表A 和 B 合并成一新的有序表C；（注：不破坏 A 和 B 的原有结构）33、已知一棵非空二叉树,其按中序和后序遍历的结果分别为：中序： CGBAHEDJFI 后序： GBCHEJIFDA 请画出这棵二叉树,并写出其前序遍历的结果；34、已知字符： C1,C2,C3,C4,C5,C6的权分别为： 17,5,16,4,8,11,请构造相应的赫夫曼树,并给出相应字符的赫夫曼编码；35、已知如下图所示二叉树,分别写
9、出其前序、中序和后序序列； A B C D E F 名师归纳总结 - - - - - - -第 3 页,共 18 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆数据结构模拟试卷一 答案一、【单项挑选题 】本大题共 10 小题,每道题2 分,共 20 分 8 9 10 题号1 2 3 4 5 6 7 答案C D B C C C C D D B 二、【判定题 】 本大题共 10 小题,每道题2 分,共 20 分 18 19 20 题号11 12 13 14 15 16 17 答案T T F F F T F T F F 三、【填空题】（本大题共10 小空,每小空2 分
10、,共 20 分）21、 运算 ；22、 s-next=p-next;p-next=s ；23、 有序表 ；24、 栈顶 ；25、 1130 ；26、 69 ；27、 31 ；28、 路径 ；29、 路径 ；30、 无向图 ；四、【应用题】（本大题共5 小题,每道题8 分,共 40 分）31、标准答案：第 1 趟： 4 12 17 10 7 30 第 2 趟： 4 7 17 10 12 30 第 3 趟： 4 7 10 17 12 30 第 4 趟： 4 7 10 12 17 30 第 5 趟： 4 7 10 12 17 30 复习范畴或考核目标：课件第十章其次节；32、标准答案：名师归纳总结
11、- - - - - - -第 4 页,共 18 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆MergeLinklist A, Linklist B, Linklist &C void MergeLinklist A, Linklist B, Linklist &C C=LinklistmallocsizeofLNode; pa=A-next; pb=B-next; pc=C; whilepa&pb pc-next=LinklistmallocsizeofLNode; pc=pc-next; ifpa-datadata pc-data=pa-data; pa=p
12、a-next; else pc-data=pb-data; pb=pb-next; if.pa pa=pb; whilepa pc-next=LinklistmallocsizeofLNode; pc=pc-next; pc-data=pa-data; pa=pa-next; pc-next=NULL; 复习范畴或考核目标：课件其次章第三节；33、标准答案：前序遍历结果 :ACBGDEHFJI复习范畴或考核目标：课件第六章第四节；34、标准答案：名师归纳总结 - - - - - - -第 5 页,共 18 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆c1:10
13、 c2:1111 c3:01 c4:1110 c5:110 c6:00 复习范畴或考核目标：课件第六章第八节；35、标准答案：前序： ABDECF 中序： DBEACF 后序： DEBFCA 复习范畴或考核目标：课件第六章第四节；名师归纳总结 - - - - - - -第 6 页,共 18 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆北京语言高校网络训练学院数据结构模拟试卷二留意：1. 试卷保密,考生不得将试卷带出考场或撕页,否就成果作废；请监考老师负责监督；2. 请各位考生留意考试纪律,考试作弊全部成果以零分运算；3. 本试卷满分100 分,答题时间为90
14、分钟；4. 本试卷分为试题卷和答题卷,全部答案必需答在答题卷上,答在试题卷上不给分；一、【单项挑选题】 本大题共 10 小题,每道题 2 分,共 20 分 在每道题列出的四个选项中只有一个选项是符合题目要求的,请将正确选项前的字母填在 答题卷相应题号处；1、程序段： sum=0; for i=1;in*n;i+ Sum+; 的平均情形下时间代价的 表达式是（）； A 1 B n C n 2 D nlogn 2、数据结构通常是争论数据的（）及它们之间的联系；名师归纳总结 A 储备和规律结构 B 储备和抽象第 7 页,共 18 页 C 抱负和抽象 D 抱负与规律3、将一棵有100 个结点的完全二叉
15、树从上到下,从左到右依次对结点进行编号,根结点的编号为1,就编号为49 的结点的左孩子的编号为（）； A 98 B 99 C 50 D 48 4、在有 n 个叶结点的Huffman 树中 , 其结点总数为（）； A 2n-1 B 2n+1 C 2n D 不确定5、设有 100 个元素,用折半查找法进行查找时,最大比较次数是（）； A 25 B 50 C 10 D 7 6、如需要利用形参直接拜访实参,就应把形参变量说明为（）参数；A 指针B 引用C 传值D 常值7、已知单链表A 长度为 m,单链表 B 长度为 n,如将 B 联接在 A 的末尾,其时间复杂度应为（）；A O1 B Om C On
16、D Om+n 8、在一棵高度为h假定树根结点的层号为0的完全二叉树中,所含结点个数不小于（h-1）；B 2h+1C 2h-1 D 2hA 29、假定一个链式队列的队头和队尾指针分别为front 和 rear,就判定队空的条件为（）；A front = rear B front .= NULL C rear .= NULL D front = NULL 10、在一棵树中, （）没有前驱结点；A 分支结点B 叶结点C 树根结点D 空结点- - - - - - -精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆二、【判定题】 本大题共 10 小题,每道题2 分,共 20
17、分 正确的填 T,错误的填F,填在 答题卷相应题号处；（）11、线性表的规律次序与物理次序总是一样的；12、在链式储备的栈的头部必需要设头结点；（）13、在二叉树中插入结点,就该项二叉树便不再是二叉树；（）14、由二叉树结点的先序序列和后序序列可以唯独确定一棵二叉树；（）15、栈和队列也是线性表；假如需要,可对它们中的任一元素进行操作；（）16、用树的前序遍历序列和中序遍历序列可以导出树的后序遍历序列；（）17、即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作,所得到的序列也肯定相同；（）18、哈夫曼 Huffman 树是带权路径长度最短的树；路径上权值较大的结点离根较
18、近；（）19、对于任一个图, 从某顶点动身进行一次深度或广度优先搜寻,可以拜访图中每一个顶点；（）20、带权的无向连通图的最小生成树是唯独的；（）三、【填空题】（本大题共 10 小空,每小空 2 分,共 20 分）请将答案填写在 答题卷相应题号处 ；21、假如 n 个顶点的图是一个环,就它有（）棵生成树；22、设在等概率情形下 , 对有 n 个元素的次序表进行插入（插入位置 i 取 0 到 n 范畴内的整数） , 平均需要移动（）个元素；23、具有 96 个结点的完全二叉树的高度为（）；24、假如一棵树有 n1 个度为 1 的结点 , 有 n2 个度为 2 的结点 , , nm个度为 m的结点
19、 , 就度为 0 的结点有（）个；25、如二叉树的中序序列与后序序列相同,就该二叉树是空树或（）；26、如一棵完全二叉树有 500 个结点,就该二叉树的深度为（）；27、用邻接矩阵表示无向图时,如图中有 有（）矩阵元素；1000 个顶点, 1000 条边,就形成的邻接矩阵28、给定序列 100 ,86,48,73,35,39,42, 57,66,21 ,按堆结构的定义,就它名师归纳总结 肯定是（）堆；且很少进行插入和删除操作,但要求以最快的速度第 8 页,共 18 页29、当线性表的元素总数基本稳固,存取线性表的元素是,应采纳（）储备结构；30、向一个长度为n 的次序表的第i 个元素 1 i
20、n+1 之前插入一个元素时,需向后移动（）个元素；- - - - - - -精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆四、【应用题】（本大题共5 小题,每道题8 分,共 40 分）请将答案填写在答题卷相应题号处 ；31、已知某二叉树中序遍历的结果是ABC,试画出其可能的二叉树五种外形；32、一个一维整数数组 Am 中有 n n m个非空整数,它们相继存放于数组的前端并已按非递减次序排列,在数组 Am 中插入一个新的整数 x,并使得插入后仍保持非递减有序；要求 x 插在值相等的整数后面；编写相应的函数实现；33、假设字符 A,B,C,D,E,F 的使用频率分别是
21、 0.07,0.09,0.12,0.22,0.23,0.27,写出A,B,C,D,E,F 的 Huffman （哈夫曼）编码；34、一颗二叉树的中序序列和后序序列分别是 给出先序序列；DCBAEFG和 DCBGFEA, 请画出该二叉树并35、设有一个输入数据的序列是 46, 25, 78, 62, 12, 37, 70, 29 , 试画出从空树起,逐个输入各个数据而生成的二叉搜寻树；名师归纳总结 - - - - - - -第 9 页,共 18 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆数据结构模拟试卷二 答案一、【单项挑选题 】本大题共 10 小题,每道题2
22、 分,共 20 分 8 9 10 题号1 2 3 4 5 6 7 答案C A A A D B C D D C 二、【判定题 】 本大题共 10 小题,每道题2 分,共 20 分 18 19 20 题号11 12 13 14 15 16 17 答案F F F F F T F T F F 三、【填空题】（本大题共10 小空,每小空2 分,共 20 分）21、 n ；22、 n/2 ；23、 7 ；24、 n2+2n3+ .+m-1nm+1 ；25、 只有根节点的二叉树 ；26、 9 ；27、 1000000 ；28、 大顶 ；29、 次序 ；30、 ni 1 ；四、【应用题】（本大题共5 小题,每
23、道题8 分,共 40 分）31、标准答案：二叉树图形如下图 1：图 1 二叉树的不同外形名师归纳总结 - - - - - - -第 10 页,共 18 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆复习范畴或考核目标：课件第六章第四节；32、标准答案：插入函数如下：void InsertSort int A , int m , int & n , int x if nm int I,j ; for i=0 ; in&Ai=I ; j- Aj+1 = A j ; A I =x ; n+; elsecerr数组已满,不能插入！”=2 B K=3 C K=4 D K=
24、5 二、【判定题】 本大题共 10 小题,每道题 2 分,共 20 分 正确的填 T,错误的填 F,填在 答题卷相应题号处；11、树的父链表示就是用数组表示树的储备结构；（）12、栈和队列规律上都是线性表；（）13、单链表从任何一个结点动身,都能拜访到全部结点；（）14、AOE网中,只有一个入度为 0 的顶点（起始点） ,只有一个出度为 0 的顶点（终止点）；（）15、关键路径可能不只一条,但缩短某一关键路径肯定能够缩短工期；（）16、有向图的邻接矩阵肯定不是对称的；（）17、在 AOE网中,关键路径是唯独的；（）18、如将一株树转换成二叉树,就该二叉树的根结点肯定没有右子树；（）19、索引次
25、序存取方法 ISAM 是一种特地为磁盘存取设计的索引次序文件的组织方法；（）20 、基数分类只适用于以数字为关键字的情形,不适用以字符串为关键字的情形；三、【填空题】（本大题共10 小空,每小空2 分,共 20 分）请将答案填写在（）答题卷相应题号处 ；21、数据结构算法中,通常用时间复杂度和（）两种方法衡量其效率；22、如频繁地对线性表进行插入与删除操作,该线性表应采纳（）储备结构；23、（）链表从任何一个结点动身,都能拜访到全部结点；24、某带头结点的单链表的头指针 head,判定该单链表非空的条件（）；25、已知指针 p 指向单链表中某个结点,就语句 p-next=p-next-next
26、 的作用是（）；26、在栈的次序实现中,栈顶指针 top ,栈为空条件（）；27、在长度为 n 的循环队列中,删除其节点为 x 的时间复杂度为（）；28、有三个结点的二叉树,最多有（）种外形；29、深度为 90 的满二叉树,第 11 层有（）个结点；30、设有 10 个值,构成哈夫曼树,就该哈夫曼树共有（）个结点；四、【应用题】（本大题共 5 小题,每道题 8 分,共 40 分）请将答案填写在 答题卷相应题号处 ；名师归纳总结 - - - - - - -第 14 页,共 18 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆31、已知一棵二叉树的先序序列是ABCD
27、EFG ,中序序列为CBEDAFG ,请构造出该二叉树；32、有一组关键码序列（38,19,65,13,49,41,1,73）,采纳冒泡排序方法由小到 大进行排序,请写出每趟排序的结果；33、设图 G,V1 ,2,3,4,5,6 ,E=, , ；画出该图,并写出全部的拓扑序列；34、一个一维整数数组 Am 中有 n n m个非空整数, 它们相继存放于数组的前端并已 按非递减次序排列,要求删除数组中余外的值相等的整数（只保留第一次显现的那个整 数）；编写相应的函数实现；35、试编写一个函数,在一个次序表A 中查找出具有最大值和最小值的整数；函数的原型如下所示, 原型的参数表中给出次序表对象为 A
28、 ,通过算法执行, 从参数表中的引用参数 Max 中得到表中的最大整数,Min 中得到表中的最小整数；留意,函数中可使用次序表的如下两个公有函数：int Length ; 求表的长度；int getDataint k; 提取第 k 个元素的值；#include “SeqList.h”template void FindMaxMinSeqList& A, int& Max, int& Min; 名师归纳总结 - - - - - - -第 15 页,共 18 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆数据结构模拟试卷三 答案一、【单项挑选题 】本大题共 10 小
29、题,每道题2 分,共 20 分 8 9 10 题号1 2 3 4 5 6 7 答案C C A A A C C B C C 二、【判定题 】 本大题共 10 小题,每道题2 分,共 20 分 18 19 20 题号11 12 13 14 15 16 17 答案T T F T F F F T T F 三、【填空题】（本大题共10 小空,每小空2 分,共 20 分）21、 空间复杂度 ；22、 链表 ；23、 循环 ；24、 head-next.=Null ；25、 删除 p 的后继结点 ；26、 top=-1 ；27、 On ；28、 5 ；29、 1024 ；30、 19 ；四、【应用题】（本大
30、题共5 小题,每道题8 分,共 40 分）31、标准答案：名师归纳总结 - - - - - - -第 16 页,共 18 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆ACBDFGE 复习范畴或考核目标：课件第六章第四节；32、标准答案：1 38 19 65 13 49 41 73 1 13 38 19 65 41 49 73 1 13 19 38 41 65 49 73 1 13 19 38 41 49 65 73 1 13 19 38 41 49 65 73 1 13 19 38 41 49 65 73 1 13 19 38 41 49 65 73 复习范畴
31、或考核目标：课件第十章第三节；33、标准答案：125436拓扑序列：123654 132654 136254 复习范畴或考核目标：课件第七章其次节第三节；34、标准答案：删除函数如下：Void delDuplicate int A , int & n 名师归纳总结 - - - - - - -第 17 页,共 18 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆Int i=0 , j , k ; While in-1 J = I + 1 ; While jn If Ai= =Aj For k=j+1 ; kn ; k+ Ak-1=Ak ; n- ; else j+; i+; 复习范畴或考核目标：课件第五章第一节；35、标准答案：void FindMaxMinSeqList& A, int& Max, int& Min Max=Min=A.getData0; forint i=1; iMax Max=A.getDatai; else ifA.getDataiMin Min=A.geyDatai; 复习范畴或考核目标：课件第九章第一节；名师归纳总结 - - - - - - -第 18 页,共 18 页