《2022年c语言数据结构试题模拟试卷.docx》由会员分享，可在线阅读，更多相关《2022年c语言数据结构试题模拟试卷.docx（35页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -模拟试卷一一、一、单项题（每题2 分,共 20 分）q 指向的1.1.以下数据结构中哪一个是线性结构？ 2 2.A. 有向图B. 队列C. 线索二叉树D. B 树2.在一个单链表HL 中,如要在当前由指针p 指向的结点后面插入一个由结点,就执行如下 4 语句序列； A. p=q; p-next=q; B. p-next=q; q-next=p; C. p-next=q-next; p=q; D. q-next=p-next; p-next=q; 3.3.以下哪一个不是队列的基本运算？（1 ）A. 在队列第 i
2、 个元素之后插入一个元素B. 从队头删除一个元素C. 判定一个队列是否为空 D.读取队头元素的值4. 4. 字符 A、B、C 依次进入一个栈,按出栈的先后次序组成不同的字符串,至多可以组成 b 个不同的字符串？ A.14 B.5 C.6 D.8 5. 5. 由权值分别为 3,8,6,2 的叶子生成一棵哈夫曼树,它的带权路径长度为 b ；A 11 B.35 C. 19 D. 53 A E G F 6.6.以下 6-8 题基于图1； 3 ；该二叉树结点的前序遍历的序列为C 7.7.A.A.E、G、 F、A、C、D、 B 1 ；B.B.E、A、 G、C、F、B、 D C.C.E、A、 C、B、D、G
3、、 F D.D.E、G、 A、C、D、F、 B 该二叉树结点的中序遍历的序列为A. A 、B、C、D、 E、G、F 8.8.B D B. E 、A、G、C、 F、B、D C. E 、A、C、B、 D、G、F 图 1E.E.B、D、 C、A、F、G、 E 该二叉树的按层遍历的序列为 3 ；9. AE、G、F、A、C、D、 B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、 D D. E 、G、A、C、D、F、B 9.下面关于图的储备的表达中正确选项2 ； A 用邻接表法储备图,占用的储备空间大小只与图中边数有关,而与结点个数无关B用邻接表法储备图,占用的储备空间大小与图中边数和
4、结点个数都有关C. 用邻接矩阵法储备图,占用的储备空间大小与图中结点个数和边数都有关D用邻接矩阵法储备图,占用的储备空间大小只与图中边数有关,而与结点个数无关10.10.设有关键码序列q,g,m,z,a,n,p,x, h,下面哪一个序列是从上述序列出 第 1 页,共 21 页 - - - - - - - - - 发建堆的结果 . 2 A. a,g,h,m, n,p,q,x,z B. a,g,m,h,q,n,p, x,z C. g,m,q,a, n,p,x,h,z D. h,g,m,p,a,n,q, x,z二、二、填空题（每空1 分,共 26 分）1.1.数据的物理结构被分为_次序、链表 _、_
5、索引 _和_散列四种；细心整理归纳 精选学习资料 - - - - - - - - - - - - - - -名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -2.2.对于一个长度为n 的次序储备的线性表,在表头插入元素的时间复杂度为_on_ ,在表尾插入元素的时间复杂度为_O1_ ；3.3.向 一 个 由HS指 向 的 链 栈 中 插 入 一 个 结 点 时p 时 , 需 要 执 行 的 操 作 是p-next=HS,HS =p;删除一个结点时,需要执行的操作是 且无需回收被删除结点）；HS=HS-next （假设栈不空而4. 4. 对于一棵具有 n 个结点
6、的二叉树,一个结点的编号为 i1in,如它有左孩子就左孩子结点的编号为 _2i_ ,如它有右孩子, 就右孩子结点的编号为 _2i+1_ ,如它有双亲,就双亲结点的编号为 _2/i_ ；5. 5. 当向一个大根堆插入一个具有最大值的元素时,需要逐层 _向上 _调整,直到被调整到根 _位置为止；6.6.以二分查找方法从长度为10 的有序表中查找一个元素时,平均查找长度为_2.9_；7. 7. 表示图的三种常用的储备结构为 邻接矩阵 _、邻接表 _和 _边集数组 _；8. 8. 对于线性表（70, 34,55,23, 65,41,20）进行散列储备时,如选用 H（K）=K %7 作为散列函数, 就散
7、列地址为 0 的元素有 _个,散列地址为 6 的有 _个；9. 9. 在归并排序中,进行每趟归并的时间复杂度为 _,整个排序过程的时间复杂度为 _,空间复杂度为 _；10. 10. 在一棵 m 阶 B_ 树上,每个非树根结点的关键字数目最少为 _个,最多为_个,其子树数目最少为_,最多为 _；三、三、运算题（每题6 分,共 24 分）图 2 1.1.写出以下中缀表达式的后缀形式：（1）（1）3X/Y-2+1 （2）（2）2+X*Y+3 2.2.试对图 2 中的二叉树画出其：1 1次序储备表示的示意图；2 2二叉链表储备表示的示意图；3.3.判定以下序列是否是小根堆. 假如不是 , 将它调整为小
8、根堆；（1） 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 （2） 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 4.4.已知一个图的顶点集V 和边集 E 分别为： V=1,2,3,4,5,6,7; E=1,23,1,35,1,48,2,510,2,36,3,415,3,512,3,69,4,64, 4,720,5,618,6,725; 条边；依据普里姆算法从顶点 1 动身得到最小生成树, 试写出在最小生成树中依次得到的各四、1.四、阅读算法（每题7 分,共 14 分）1.void AEStack& S Init
9、StackS; PushS,3; PushS,4; int x=PopS+2*PopS; PushS,x; 细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 2 页,共 21 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - - int i,a5=1,5,8,12,15; fori=0;i5;i+ PushS,2*ai; while.StackEmptyS coutPopSleft,c1,c2; c1+; if BT-left=NULL&BT-right=NULL c2+; AB
10、CBT-right,c1,c2; /if 该函数执行的功能是什么？统计结点总数和叶子总数 ; 五、五、算法填空（共 8 分）向单链表的末尾添加一个元素的算法；Void InsertRearLNode*& HL,const ElemType& item LNode* newptr; newptr=new LNode; If _newptr=NULL_ cerrMemory allocation failare.data_=item; newptr-next=NULL; if HL=NULL HL=_newptr_; else LNode* P=HL; While P-next.=NULL p=p
11、-next_; p-next=newptr; newptr=NULL newptr-=data newptr p=p-next i 的值进行六、六、编写算法（共8 分）编写从类型为List的线性表 L 中将第 i 个元素删除的算法, （假定不需要对有效性检查 , 也不用判别L 是否为空表；）void DeleteList& L, int iforj=i-1;jnext=HS;HS=p HS=HS-next4.4.2i 2i+1 i/2（或 i/2 ）5. 5.向上根6. 6.2.9 7. 7.邻接矩阵邻接表边集数组8. 8.1 49. 9.On Onlog2n On10. 10.m/2 -1
12、m-1 m/2 m 三、三、运算题（每题6 分,共 24 分）图 31.1.1 3 X * Y 2 - / 1 + 222 X Y 3 + * + 2.2.（1）0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 2 3 4 5 6 7 8 9 （2）见图 3 所示：3.3.1不是小根堆；调整为：12,65,33,70,24,56,48,92,86,33 2是小根堆；4.4.普里姆算法从顶点1 动身得到最小生成树为：1,23, 1,35, 1,48, 4,64, 2,510, 4,720 四、1.四、阅读算法（每题7 分,共 14 分）1.30 24 16 10 2 10
13、 2.2.该函数的功能是：统计出BT 所指向的二叉树的结点总数和叶子总数五、五、算法填空（共8 分,每一空2 分）六、newptr=NULL newptr-=data newptr p=p-next 六、编写算法（ 8 分） void DeleteList& L, int i forint j=i-1;jnext=HL; B. p-next=HL-next; HL-next=p; C. p-next=HL; p=HL; D. p-next=HL; HL=p; 2.如次序储备的循环队列的QueueMaxSize=n,就该队列最多可储备（素. A. n B.n-1 C. n+1 D. 不确定3.
14、3. 下述哪一条是次序储备方式的优点？（） A储备密度大 B. 插入和删除运算便利 C. 猎取符合某种条件的元素便利 D. 查找运算速度快4. 4. 设有一个二维数组 Amn ,假设 A00 存放位置在 60010,A33 存放位置在67810,每个元素占一个空间,问 A23 10存放在什么位置？脚注 10表示用 10 进制表示 ,m3 5.5.A 658 B648 C 633 ；D653 以下关于二叉树遍历的表达中,正确选项 A. 如一个树叶是某二叉树的中序遍历的最终一个结点,就它必是该二叉树的前序遍历最终一个结点B如一个点是某二叉树的前序遍历最终一个结点,就它必是该二叉树的中序遍历的最后一
15、个结点 C如一个结点是某二叉树的中序遍历的最终一个结点,一个结点就它必是该二叉树的前序最终 D如一个树叶是某二叉树的前序最终一个结点,就它必是该二叉树的中序遍历最终一 个结点 A6.6.k 层二叉树的结点总数最多为 . D. 2k-12 k-1 B.2K+1 C.2K-1 7.7.对线性表进行二分法查找,其前提条件是 . A.A. 线性表以链接方式储备,并且按关键码值排好序 B.B. 线性表以次序方式储备,并且按关键码值的检索频率排好序 C.C. 线性表以次序方式储备,并且按关键码值排好序 D.D.线性表以链接方式储备,并且按关键码值的检索频率排好序细心整理归纳 精选学习资料 8.8.对 n
16、个记录进行堆排序,所需要的帮助储备空间为H（ K） 第 5 页,共 21 页 A. O（1og2n）B. O （ n） C. O（1） D. O（n2）9.9.对于线性表（ 7,34,77,25,64,49,20,14）进行散列储备时,如选用=K %7作为散列函数,就散列地址为0 的元素有（）个, A 1 B2 C3 D4 10.10. 以下关于数据结构的表达中,正确选项 . A. A.数组是不同类型值的集合B. B.递归算法的程序结构比迭代算法的程序结构更为精炼 - - - - - - - - - - - - - - - - - - - - - - - - 名师归纳总结 精品学习资料 - -
17、 - - - - - - - - - - - - -C. C. 树是一种线性结构二、1. 2. 3.4.D. D.用一维数组储备一棵完全二叉树是有效的储备方法二、填空题（每空1 分,共 26 分）1.数据的规律结构被分为_、_、_和_四种；2.一个算法的时间复杂度为3n 3+2000nlog 2n+90/n2,其数量级表示为_；3.对于一个长度为n 的单链储备的队列,在表头插入元素的时间复杂度为_,在表尾插入元素的时间复杂度为_；4.假定一棵树的广义表表示为A（ D（ E,G）,H（I,J）,就树中所含的结点数为_个,树的深度为_,树的度为 _；5.5.后缀算式 79 2 30 + - 4 2
18、 / * 的值为 _；中缀算式（3+X*Y ）-2Y/36.对应的后缀算式为_ ；6.在一棵高度为5 的抱负平稳树中,最少含有_个结点,最多含有_个结点；7. 7. 在树中,一个结点的直接后继结点称为该结点的 _；一个结点的直接前趋结点称为该结点的 _；8. 8. 在一个具有 10 个顶点的无向完全图中,包含有 _条边, 在一个具有 n 个顶点的有向完全图中,包含有 _条边；9. 9. 假定一个线性表为 12,17,74,5,63,49,82,36 ,如按 Key % 4 条件进行划分,使得同一 余 数 的 元 素 成 为 一 个 子 表 , 就 得 到 的 四 个 子 表 分 别 为_ 、
19、_ 、 _和_ ；10. 10. 对一棵 B_树进行删除元素的过程中,如最终引起树根结点的合并时,会使新树的高度比原树的高度 _；11. 11. 在堆排序的过程中,对任一分支结点进行筛运算的时间复杂度为 _,整个堆排序过程的时间复杂度为 _；12. 12. 在线性表的散列储备中,装填因子 又称为装填系数,如用 m 表示散列表的长度,n 表示待散列储备的元素的个数,就 等于 _；三、三、运算题（每题 6 分,共 24 分）1 1在如下数组 A 中链接储备了一个线性表,表头指针存放在 A 0.next ,试写出该线性表； A 0 1 2 3 4 5 6 7 data 60 50 78 90 34
20、40 next 4 0 5 2 7 1 3 2 2已 知 一 棵 二 叉 树 的 前 序 遍 历 的 结 果 是 ABKCDFGHIJ, 中 序 遍 历 的 结 果 是KBCDAFHIGJ, 试画出这棵二叉树；3 3已知一个图的顶点集 V 为：V=1,2,3,4,5,6,7; 其共有 10 条边；该图用如下边集数组储备：起点1 2 2 5 5 2 2 6 1 3 第 6 页,共 21 页 - - - - - - - - - 终点6 4 5 4 7 6 7 7 7 5 权1 1 2 2 2 3 3 4 5 7 试用克鲁斯卡尔算法依次 求出该图的最小生成树中所得到的各条边及权值；4 4画出向小根堆
21、中加入数据4, 2, 5, 8, 3, 6, 10, 1 时,每加入一个数据后堆的变化；四、四、阅读算法（每题7 分,共 14 分）1.1.在下面的每个程序段中,假定线性表La 的类型为 List ,元素类型ElemType 为细心整理归纳 精选学习资料 - - - - - - - - - - - - - - -名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -int ,并假定每个程序段是连续执行的；试写出每个程序段执行后所得到的线性表 La；（1）（ 1）InitListLa; Int a=100,26,57,34,79; For i=0;i5;i+ In
22、sertLa,ai; TraverseListLa; （2）（ 2）DeleteFrontLa; InsertRearLa, DeleteFrontLa; TraverseListLa; （3）（ 3）ClearListLa; For i=0;i5;i+ InsertFrontLa,ai; TraverseListLa; 2.2.现面算法的功能是什么？void ABCBTNode * BT if BT coutdataleft; ABCBT-right; 五、五、算法填空（共8 分）二分查找的递归算法； Int BinschElemType A,int low,int high,KeyType
23、 K if _ int mid=low+high/2; if _ return mid; / else if KAmid.key return BinschA,low,mid-1,K; /查找胜利,返回元素的下标在左子表上连续查找 else return_； /在右子表上连续查找 else _； /查找失败,返回-1 六、六、编写算法（共 8 分）HL 为单链表的表头指针,试写出在该单链表中查找具有给定的元素 item 的算法；bool FindLNode* HL, ElemType &item模拟试卷二参考答案一、2.B 一、4.C 5.D 单项题（每题2 分,共 20 分） 第 7 页,共
24、 21 页 1.B 3.A 6.A 7.C 8.C 9.D 10.D 二、二、填空题（每空1 分,共 26 分）细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -1.1.集合结构线性结构树结构图结构2.2.On 时,逐步形成二叉树的A 3.3.O1 O1 4.4.7 2 2 5.5.94 3 X Y * + 2 Y * 3 / - 6.6.16 31 7.7.孩子（或子）结点双亲（或父）结点8.8.45 nn-1 9.9.（12,36）
25、（17,5,49 ）（ 74,82）（63）10.10.削减 1（或削减）11.11.Olog 2n Onlog2n 12.12.n/m 三、三、运算题（每题6 分,共 24 分）1.1.线性表为：（ 90,40,78, 50,34,60）2.2.当前序序列为ABKCDFGHIJ ,中序序列为KBCDAFHIGJ过程如下图4 所示：A A A KBCD FHIGJ B F B F B F K CD HIGJ K C G K C G D HI J D HJ I 2 图 4 3.3.用克鲁斯卡尔算法得到的最小生成树为：1,61, 2,41, 2,52, 5,72, 2,63, 3,57 4.4.见
26、图 5；4 4 2 2 2 2 4 4 5 4 5 4 5 8 8 3 2 2 2 1 5 3 5 3 5 3 5 2 8 4 8 4 6 8 4 6 10 3 4 6 10 8 图 5 四、1.四、阅读算法（每题7 分,共 14 分）1.1 La=26,34,57,79,100 2La=57,79,100,34 3La=79,34,57,26,100 2.2.前序遍历链式储备的二叉树； 第 8 页,共 21 页 - - - - - - - - - 五、五、算法填空（每空2 分,共 8 分）lowdata=item return true; else p=p-next; return fals
27、e; 模拟试卷三一、1.1.一、单项题（每题2 分,共 20 分）D时空复杂度对一个算法的评判,不包括如下（）方面的内容；A 健壮性和可读性B并行性C正确性2.2.在带有头结点的单链表HL 中,要向表头插入一个由指针p 指向的结点, 就执行 ； A. p-next=HL-next; HL-next=p; B. p-next=HL; HL=p; C. p-next=HL; p=HL; D. HL=p; p-next=HL; 3. 3. 对线性表,在以下哪种情形下应当采纳链表表示？ A. 常常需要随机地存取元素 B. 常常需要进行插入和删除操作 C. 表中元素需要占据一片连续的储备空间 D. 表中
28、元素的个数不变4. 4. 一个栈的输入序列为 1 2 3,就以下序列中不行能是栈的输出序列的是 A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. 5. AOV 网是一种（）；A有向图 B无向图 C无向无环图 D有向无环图6. 6. 采纳开放定址法处理散列表的冲突时,其平均查找长度（）；A低于链接法处理冲突 B. 高于链接法处理冲突C与链接法处理冲突相同 D高于二分查找7. 7. 如需要利用形参直接拜访实参时,应将形参变量说明为（）参数；A值 B函数 C指针 D引用8. 8. 在稀疏矩阵的带行指针向量的链接储备中,每个单链表中的结点都具有相同的（）；A行号 B列号 C
29、元素值 D非零元素个数9. 9. 快速排序在最坏情形下的时间复杂度为（）；AOlog2n BOnlog2n C0n D0n 2 10.10. 从二叉搜寻树中查找一个元素时,其时间复杂度大致为 ； A. On B. O1 C. Olog 2n D. On 2二、二、运算题（每题 6 分,共 24 分）1. 1. 数据结构是指数据及其相互之间的 _；当结点之间存在 M 对 N（M ：N）的联系时,称这种结构为_；2.2.队列的插入操作是在队列的_进行,删除操作是在队列的_进 第 9 页,共 21 页 细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - - - -
30、 - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -行；3.3.当用长度为N 的数组次序储备一个栈时,假定用top=N 表示栈空,就表示栈满的条件是 _；4. 4. 对于一个长度为 n 的单链储备的线性表,在表头插入元素的时间复杂度为_,在表尾插入元素的时间复杂度为 _；5. 5. 设 W 为一个二维数组,其每个数据元素占用 4 个字节,行下标 i 从 0 到 7 ,列下标 j 从 0 到 3 ,就二维数组 W 的数据元素共占用_个字节； W 中第 6 行的元素和第 4 列的元素共占用_个字节； 如按行次序存放二维数组 W,其起始地址
31、为 100,就二维数组元素 W6 ,3的起始地址为_；6. 6. 广 义 表 A= a,a,b,a,b,c, 就 它 的 深 度 为 _ , 它 的 长 度 为_；7.7.二叉树是指度为2 的_树；一棵结点数为N 的二叉树,其所8.有结点的度的总和是_；_；对8.对一棵二叉搜寻树进行中序遍历时,得到的结点序列是一个一棵由算术表达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的_；9.9.对 于 一 棵 具 有n 个 结 点 的 二 叉 树 , 用 二 叉 链 表 存 储 时 , 其 指 针 总 数 为_个,其中 _个用于指向孩子,是闲暇的；_个指针10. 10. 如对一棵完全二叉树从 0 开头进行结点的编号,并按此编号把它次序储备到一维数组 A 中,即编号为 0 的结点储备到 A0 中；其余类推,就 A i 元素的左孩子元素为_,右孩子元素为 _,双亲元素为 _；11.11.在线性表的散列储备中,处理冲突的常用方法有_ 和_ 两种；12.12.当 待 排 序 的 记 录 数 较 大 , 排 序 码 较 随 机 且 对 稳 定 性 不 作 要 求 时 , 宜 采 用_