吉林大学数据结构考题

所需积分/C币:48 2019-08-25 14:46:59 1.63MB PDF
57
收藏 收藏
举报

吉林大学数据结构课程的历年期末试题,含有详细的讲解和答案,以供各位参考。如果你的积分不足,可以私聊我发给你,祝好!
前言 在几个月前,只剩下三周时间去复习数据结构。全班非常紧张,害怕考试不 能得到高分,于是全班一起去复印社团购了《数据结构》历年真题。我们买来后 却大跌眼镜—一这质量简直差的不能再差!卖给同学简直坑钱!可是我们也只能 将就用了,毕竟时间已绎非常紧迫了。最后考完这门课的时候我心想是不是需要 花点时间做份《数据结构》复习试题给大家用,让大家享受高质量的试卷?在 系列的事情后我决定开始做这件事(其中包含着我一些承诺和某些“典故”)。我 联系了身边各位大神并得到一些人的支持,在此真的很感谢他们,没有他们真的 这份试题不能完成。然后经历一两个月后这个计划完成了。又想到在做之初别人 告诉我没必要多管闲事,复印社印刷的瓷料还是可以将就用的。作为一个追求完 美的人我是不能容忍这现象的,我还是硬着头皮做了,希望真的可以让读者获得 考试buf,人人上90拿满绩点! 本资料收纳了五套试题和一套复习题,供计算机学院、软件学院的同学复习 参考。本着以最少的题目得最高分数的原则,我尽量做到把考试90%以上的知识 点融入这份资料里面。资料的每个题目望读者用心研究,学明白了何尝不能达到 88分,甚至99分呢( Richard的分数就是99分)?在这份资料中尤其需要关注 09级试题(当年大约45%人不及格)以及计算机唐敖庆班考试真题(也同吋是 软件卓越T程师班的考题,考查的知识范围很广)当然有几个试题不是真题(试 题出现了重复,换成其他一些类型的题目了),希望读者明白 值得一提的是一一本资料在制作后期有点仓促,答案没有经过三人校对,所 以会出现某些试题答案不对和没给一些算法题代码。实属抱歉,编者也是学生, 也需要学习其他科目,真的做出这份资料费了很多吋间。Jose& Austin制作这份 资料完全出自那份初心,所以请读者谅解此事。 在这里真诚感谢 Austin&Aex& Richard&Chen四人。他们完成了大部分答 案、凭着对考题的印象打岀了2017级讣算机唐敖庆班数据结构试题(为他点100 个赞)、给出了唐敖庆班考题的答案,以及一些算法题解题思路。感谢你们付出, 没有你们就没有这份资料! 最后我希望大家用上这份资料能够为你的数据结构期末考试保驾启航 编者 使用比资料注意: 1.不保证做的答案全部是正确的,该资料不适合只相信答案的人使用; 2.部分题目修改过,可能不会与原题一模一样 3.如果发现错误请加Q0群:783124749并告诉管理员;也欢迎大家入这个群 交流学习; 4.Jose& Austin拥有资料所有版权。未经许可翻版必追查责任! 5.该资料是免费共享的,严禁拿该资料获利! 2015年数据结构考试试题A 、选择题(5*2分) 1.设栈的输入队列是(a,b,c,d),则不可能是其出栈序列 A abcd B bacd C adcb D. dcab 2.若一棵二叉树有10个度为2的结点,则该二叉树的叶结太的个数是。 A.9B.11 C.10 D.12 3.在图形结构中,每个结点的前驱结点数和后继结点数可以有个。 A.1 B.2C.任意多D.0 4.下面的排序算法中不稳定的是。 A.合并排序B.希尔排序C.直接插入排序D.冒泡排序 5.中缀表达式{A+B*C-[D+E/F米(G+H)]}对应的后级表达式是 A+ABC*-DEF /*+GH B.ABC*+一DEF/GH+* C.ABC+DEF/米+GH D.ABC*+DEF/GH+*十一 、简答题(55分) 1.简述数据结构包含哪三个方面的内容?数据的储存方法有几种,并对每一种 存储方法的特点进行简单的描述。(5分) By Jose Austin 2.给出如下稀疏矩阵的三元组表示(行列从0开始编号):(5分) 50000 A二 100200 0000 3.构造权值为{5,13,21,7,18,30,41}的哈夫曼树,并给出哈夫曼编码 (6分) 4.数组A中,每个元素A[i][j的长度均为2个字节,行下标从1到5,列下 标从1到10,从首地址S开始连续存放于主存储器中。(8分)求 (1)存放该数组共需要多少字节? (2)存放数组第四列所有元素至少需要多少个单元? (3)数据按照行存放时,元素A[2][4]的起始地址是多少? 4)数据按照列存放时,元素A[4][刁]的起始地址是多少? 5.已知一棵二叉树的后根和中根遍历序列如下(6分) 后根遍历序列 CEFDBHGA 中根遍历序列 CBEDFAGH 1>画出这棵二叉树的逻辑结构 <2>给出这棵二叉树的先根遍历序列 6.设散列表长度为11,散列函数h(x)=x%11,给定的关键字序列为:1,13,12, 34,38,33,27,22。试画出用线性探查解决冲突时所构建的散列表。(8分) 7.待排序的文件为(6,25,7,11,51,17,39,85,8,9),请给出堆排序过 程。(10分) 8.给定顺序表(5,12,17,19,23,25,30,36),请画出此顺序表对半查找 时对应的二叉判定树。当采用对半查找算法查找关键字30时,进行多少次比较 后査找成功?算出该顺序表成功査找和失败査找的平均比较次数(各个关键字等 概率)。(7分) 三、算法题(35分) 注意:可选择适用C艹+或ADL语言,建议使用ADL语言;算法开始处必须通过注 释说明算法主要思想,关键操作步骤须冇注释:书写算法吋要有必要的缩进。 1.设计一个算法,给定整数K,重排大小为n的整型数组A[1:n],将A中所有 小于K的关键字排在所有大于K的关键学之前。5t 1>给出算法的基本设计的思想(4分) <2>用算法描述语言描述算法,并要求对算法中的关键步骤给出注释(6分)。 2.假定以单链表保存学生成绩信息,data域值为考试成绩。设计一算法,计算 单链表中所有学生成绩的平时分。 1>给出算法的基本设计思想(4分); 2>用算法描述语言描述算法,并要求对算法中的关键步骤给岀注释(6分) 3.一棵二叉树以链表形式存储,结点结构为(Left,Data, Right),设计一算 法,求二叉树中从根结点到叶结点的条路径长度等于树的高度的路径,石 这样的路径存在多条,则输出路径终点(叶结点)“最左“的一条 1>给出算法的基木设计思想(5分); 2>用算法描述语言描述算法,并要求对算法中的关键步骤给出注释(10分) By jose Austin 2014级数据结构考试试题A卷 判断题(10*1分) 环状队列是一种物理结构 2.若完全二叉树的某结点无左孩了,则它必是叶结点。 3.N个顶点的无向连通图至少有N+1条边。 4.任何AOV网的拓扑序列都是唯一的 5.无向图的邻接矩阵是对称的,有向图的邻接矩阵一定不对称 6.关键路径是AOE网中从源点到汇点的最短路径。 7.如果序列已经有序,直接插入排序的时间复杂性为o(n)。 8.对两棵具有相同关键字集合而形状不同的二叉查找树,按中序遍历它们得到 的序列是一样的。 9.AⅥL树是棵二叉树,该树上任结点的平衡因子(平衡系数)的绝对值不大 于 10.散列法存储的基木思想是由关键词的值决定数据的存储地址。 选择题(10*2分) 1.设栈的输入序列是(1、2、3、4),则不可能是其出栈序列 A.1234 B.2134 C.1432 D.4312 2求字符串T在字符串S中首次出现的位置的操作称为 A串的模式匹配B求字串C求串的长度D串的连接 3.下面关于哈夫曼树的说法,不正确的是。 A.哈夫曼树没有度为1的结点 B哈夫曼树具有最小的带权路径长度 C对应一组权值构造出的哈夫曼树一般不是唯一的 D哈夫曼树除了度为1的结点外,还有度为2的结点和叶结点 4.任何一棵非空弌叉树的叶结点在先根遍历、中根遍历和后根遍历中相对位置 A.都公发生改变 B不会发生改变 C.有可能发生改变 D部分会发生改变 5.具有2000个结点的非空二叉树的最小深度为。 A.9 B.10 C.11 D.12 6若一棵满二叉树有1024个叶结点,则该二叉树结点的个数为。 A.2045 C.2046 D.2047 D.2048 7.下面关于图的存储的叙述中,是正确的。 A用邻接矩阼存储图,占用的存储空问的大小只与图中顶点个数有关,而与边数 无关 B.用邻接矩阵存储图,占用的存储空间的大小只与图中边数有关,而与顶点个 数无关 C.用邻接表存储图,占用的存储空间的大小只与图中顶点个数有关,而与边数 无关 D.用邻接表存储图,占用的存储空间的大小只与图中边数有关,而与顶点个数 无关 8.下面的叙述中,不止确的是。 A.任何关键活动不按期完成就会影响整个工程完成的时间 B.仁何一个关键活动提前完成,将使整个工程提前完成 C.所有关键活动都提前完成,将使整个工程提前完成、 D.所有关键活动不按期完成就会影响整个工程的完成时间 9.下面的排序算法中,具有稳定性的是排序 A.直接选择B.希尔 堆 10.一组记录的关键字为(25,50,15,3580,85,20,40,3670),其中含有5个长度为2 的有序表,用归并排序方法对该序列进行一趟归并后的结果为 A.15,25,3550,20,408085,36,70 B.15,25,355080,20,85,40,70,36 C.15,25,50,3580,85,20364070 D.15,25,35,50,80,20,36,40,70,85 三、简答题(35分) 1将表达式(a+b)-c*(d+e)f*(g+h)改写成后缀表达式(2分)。 2.给出如下稀疏矩阵的三元组表示。(4分) 0060 4000 0008 By Jose Austin 3.已知一棵二叉树中序和前序序列如下,画出该二叉树,并求该二叉树后序序 列。(4分) 中序序列: cbdeagihjf 前序序列: a bcedfg hij 4.已知序列17,31,13,1120,3525,8,4,1124,40,27,请画出该序列的二叉合找树。 (7分) 5.一组记录的关键字为(5256,26,12,69,8533,48,70),给出堆排序的过程,即画出 每次堆调整后堆的状态。(8分) 6.对于如下的有向图,请利用 Dijkstra算法求出从源点1到其他各顶点的最短 路径,并写出执行该算法过程中扩充点集的每次状态。(10分) 10 三、算法趣(共35分) 1.编写一个算法,在带表头结点head的单链表中单链表中寻找第i(i>=1)个 结点:若找到,则函数返回指向第i个结点的指针;若找不到,则函数返回 NULL。(7分) 2.编写算法计算并输出以root为根的二义树中叶结点个数。(8分 3.编写算法求任意二叉树中第一条最长的路径,并输出此路径上各结点的值。 (10分) By Jose Austin 4.设讣一个算法,判断无向图G是否是一棵树。若是,则返回1:否则返回0。 (10分) By Jose austin 2009级《数据结构》期末试题A卷 判断题(5*2分 算法的优劣与所用的计算机无关。但是与算法描述的语言有关 2.根据算法的吋间复杂性,人们常常把算法分成两类:多项式阶算法、指数阶 算法。当n很大时,可以讦明有如下关系 o(1<o loglog n)O(log n)o(n*log n <o(n<o(n 2)<o(2An 3.分析排序算法的最好和最坏时间复杂性时,当排序文件已经是排好序时,则 算法对此文件执行排序具有最好时间复杂性;当排序文件是逆排列时,算法 对此文件执行排序具有最坏时间复杂性 4.N个结点的有向图,若它有N(N1)条边,则它一定是强连通的。在n个结点 的无向图中,若边数大于N-1,则该图必是连通图。 5.中序遍历一棵二叉查找树可以得到一个排好序的结点序列 、单选题(7*2分) 1.一棵左右子树均不空的二叉树在后序线索化后,其空指针域的个数为 A.0 B. 1 C.2 D.3 2.下列排序算法中,某一趟排序后木必能选出一个元素放在最终位置上的是。 A.堆排序B直接插入排序C分划交换排序D冒泡排序 3.一棵具有N个顶点,K条边的无向图是个森林(N*,则该森林必有_棵树 A K CN-K D.1 4若一组记录关键字为(34,605530,32,85),则利用堆排序的方法建立的初始堆为 A.{603455303285} B.{85605530,32,34} C.185605534,32,30 D{85,556032,34,30} 5在下述结论中正确的有个 1)只有一个结点的二叉树的度为0 2)二叉树的度为2 3)二叉树的左右字数可任意交换 4深度为K的完全二叉树的结点个数小于或等于深度相同的二叉树 5)有4个不同关键字的结点可以构成14种不同的二叉树 A.1 B.2 C.3 D.4 6在一个有向图中,所有顶点的入度之和等于所有顶点出度之和的倍 A.1 B.2 C.1.5 D.不能确定 7设有数组A[j,数组的每一个元素长度为三个字节,i的值为1到8,j的值为 1到10,数组从内存首地址S开始顺序存放,当按列优先存放时,元素A5,8]的 存储首地址为 A.S+141 B.S+180 C.S+222 D.S+225 、简答题(46分) 1.说明顺序存储和链式存储的区别及各自的优缺点。(4分) 2.将表达式(a+b)*C+d/(e*g)h改写成前缀和后缀表达式。(6分) 3.已知一棵二叉树T的诸结点在先根次序下的排列为: ABCEDEGH,在中根次 序下的排序为: ECBDFAHIG,画出此树形,并给出其后根序列。(6分) 4.组记录的关键字为(4875:8503342,86,26,70),给出快速排序的过程(只需 给出每次分划后的结果)。(6分) 5.一个AOV网如下图所示:(8分) 1)计算出所有活动的最早开始时间e(a)和最迟开始时间l(a); 2)基于以上计算结果,给出该网络中的所有关键路径。 6.设有序顺序表为10,20,30,40,50,6070,80}画出折半查找算法对应的叉判定 树,并计算采用折半查找方法查找以上顺序表时,查找成功和查找失败情况 下的平均查找次数。(6分) 7.设散列表长度为11,散列函数h(x)=x%11,给定的关键字序列是1,13,12 34,38,33,27,22试画出用线性探査法解决冲突时所构造的散列表。(6分) 8.填充如下排序算法中的方框,并讨论该算法的稳定性。(4分) 算法C(R,n) /比较计数,本算法按关键词K1,K2,…,Kn排序记录R1,R2,…,Rn.一维数 组 COUNT[1:n]用来记录各个记录的排序位置* [C1 FOR i=1 TO n DO LC2 FOR i=n To 2 2 DO FOR j=i-1 TO 1 STEP-1 DO HF③THEN COUNT[]<COUNT[]+1 ELSE 四、算法题(30分) 1.设计一个算法,将链表的链接完全颠倒。(10分) 2.对以左儿了一右兄弟链接表示的树,编写计算树的深度的算法。(10分) 3.图采用邻接表存储结构,编写一个算法,判别无向图中任意给定的两个顶点 之间是否存在一条长度为k的简单路径。(10分)

...展开详情
试读 41P 吉林大学数据结构考题
立即下载 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
  • 签到新秀

  • 分享王者

关注 私信
上传资源赚钱or赚积分
最新推荐
吉林大学数据结构考题 48积分/C币 立即下载
1/41
吉林大学数据结构考题第1页
吉林大学数据结构考题第2页
吉林大学数据结构考题第3页
吉林大学数据结构考题第4页
吉林大学数据结构考题第5页
吉林大学数据结构考题第6页
吉林大学数据结构考题第7页
吉林大学数据结构考题第8页
吉林大学数据结构考题第9页

试读结束, 可继续读4页

48积分/C币 立即下载