版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、2009-2010年计算机考试试题及答案数据结构,数据结构分析,2009年统考试题,2010年统考试题,2009年统考试题,1。单项选择题(2分,每个小问题10个问题)1。为了解决计算机和打印机速度不匹配的问题,通常设置一个打印数据缓冲区,数据由主机输出。缓冲区的逻辑结构应该是:(a)堆栈b .队列c .树d .图,b.2 .让堆栈s和队列q的初始状态为空,元素a、b、c、d、e、f和g依次进入堆栈s。如果每个元素在离开堆栈后立即进入队列Q,并且离开队列的七个元素的顺序是bdcfeag,那么堆栈S的容量至少是(A1)b . 2 c . 3d . 4 3。右图显示了给定的二叉树。假设生成表二叉树
2、的根,L代表根节点的左子树,R代表根节点的右子树。如果遍历后的节点序列是3,1,7,5,6,2,4,那么遍历模式是()ALRN NRL RLN RNL。在下面的二进制排序树中,符合平衡二叉树定义的是()5。完整二叉树的第六层是已知的(让根成为第一层)。完整二叉树的最大节点数是(A39B.52C.111D.119,B、C、6)。将林转换成相应的二叉树。如果节点u是二叉树中节点v的父节点,那么在原始林中,u和v之间的关系可能是(1)父子关系(2)。兄弟姐妹关系IIi。u的父节点和v的父节点是兄弟关系a。只有IIB。一和二C .一和三D .一、二和三7。在下面关于无向连通图的特征的描述中,I的所有顶
3、点的度数之和为偶数是正确的。边的数量大于顶点的数量减1。至少有一个顶点的度数是1。只有1。只有2。C。1和2。D。1和3,B,A,8。在下面的描述中,不满足M阶B树定义要求的是()根节点最多有M个子树。所有叶节点都在同一层。每个节点中的关键字按升序或降序排列。叶节点由指针连接。9.众所周知,关键序列5、8、12、19、28、20、15、22是小根桩(最小桩)。插入关键字3,调整后得到小的关键字。20,15,22,19b.3,5,12,19,20,15,22,8,28c.3,8,12,5,20,15,22,28,19d.3,12,5,8,28那么排序算法只能是()A .冒泡排序b .插入排序c
4、.选择排序d .双向合并排序,A,2 .综合应用问题(10分和15分),41。(10点)加权图的最短路径问题(权重不是负的,表示由边连接的两个顶点之间的距离)是寻找从初始顶点到目标顶点的最短路径。假设从初始顶点到目标顶点有一条路径,有一种方法可以解决这个问题:让最短路径最初只包含初始顶点,并让当前顶点u为初始顶点;选择离u最近但尚未在最短路径中的顶点v,将其添加到最短路径中,并修改当前顶点u=v;重复上述步骤,直到u成为目标顶点。用上述方法可以得到最短路径吗?如果这个方法有效,请证明它;否则,请举例说明。41,通过该方法获得的路径不一定是最短路径。例如,对于下图所示的加权图,如果根据标题中的原
5、理,从A到C的最短路径是ABC,那么实际上,最短路径是ADC。42.(15分)带有标题节点的单个链表是已知的,节点结构是。假设链表中只给出了头指针列表。在不改变链表的前提下,请尽可能设计一个高效的算法来寻找链表中第k个位置的节点(k是正整数)。如果搜索成功,算法输出节点的数据值并返回1;否则,只返回0。要求:(1)描述算法的基本设计思想;(2)描述算法的详细实现步骤;(3)根据设计思想和实现步骤,用编程语言描述算法(用C或C或JAVA语言)。请对要点进行简要评论。问题42的答案分析(1)算法的基本设计思想:定义两个指针变量P和Q,它们最初指向头节点的下一个节点。指针沿着链表移动;当p指针移动到
6、第k个节点时,q指针开始与p指针同步移动。当p指针移动到链表的最后一个节点时,q指针指向的元素是从底部开始的第k个节点。上述过程只扫描链表一次。(2)算法的详细实现步骤:计数=0,p和Q指向链表头节点的下一个节点;如果p是空的,转动;如果计数等于k,q指向下一个节点;否则,计数=计数1;p指向下一个节点,转到步骤;如果计数等于k,则搜索成功,输出该节点的数据字段的值并返回1;返回,搜索失败,返回0;算法结束。(3)算法实现:typedef struct LNode int数据;结构LNode *链接;*链接列表;链接列表p,q;int count=0;/*将初始值分配给计数器*/p=q=lis
7、t-link;/*p和q指向链表头节点中的下一个节点*/while(p!=空)如果(countlink/*q移动到下一个节点*/p=p-link;/* p移动到下一个节点*/if(count data);/*搜索成功*/返回(1);2010年,计算机研究生入学考试统一举行。1.单项选择题(每个小问题有2分和11个问题)1。如果元素A、B、C、D、E和F依次堆叠,堆叠和堆叠操作可以交替进行。但是,不允许连续三次堆叠,因此无法获得的堆叠顺序为:(a : DCB fab 3360 CBD AEFC 3360 BCA ef d : AFE DCB 2)。允许队列在两端排队,但只能在一端出列。那么不可能
8、的顺序是()a: bacde b: dbacec: dbcaed: ecbad,d,c,3。在下面的线索二叉树中(线索用虚线表示),符合下面线索树定义的是()、D、4。将关键字48插入下图所示的平衡二叉树中,得到一个新的平衡二叉树。在新的平衡二叉树中,存储在关键字37所在节点的左、右子节点中的关键字是:(A):13,48b: 24,48c: 24,53 D:24,90 5。在4度树中,如果有20个4度节点,10个3度节点,1个2度节点和10个1度节点。那么树t的叶节点数是(a):41b:82c:113d:122,c,b,6。霍夫曼树由n(n2)个不同权重的字符组成。在这个哈弗曼树的描述中,错误
9、是:(a)树必须是一个完整的二叉树;(b)树中不能有1度的节点;树中具有最小权重的两个节点必须是兄弟节点d:树中任何非叶节点的权重必须不小于下一个节点7的权重。如果无向图G=(V.E)包含7个顶点,则保证图G在任何情况下都是连通的。那么所需的边数至少是()6:15:16:21,8。不同延伸序列的数目可以获得为:(甲:4乙:3丙:2丁:1 9。长度为16的序列表L是已知的,它的元素根据关键字排序。如果采用,最大比较次数为(a):4b:5c:6d:7,b,b,10。递归用于快速排序顺序表。以下关于递归的陈述是正确的:(1)递归与初始数据的排列顺序无关(2)在每个分区之后,处理较长的分区可以减少递归
10、(3)在每个分区之后,先处理较短的分区可以减少递归次数(4)递归次数与每个分区之后获得的分区处理顺序无关(5)。11.对一组数据(2,12,16,88,5,10)进行排序,如果前三遍的排序结果如下:(第一遍:2,12,16,5,10,88第二遍:2,12,88采用的排序方法可以是:A:冒泡排序b:希尔排序c:合并排序D:基数排序D,A,2。综合应用问题(10分和13分),41。(10分)将关键字序列(7,8,30,11,18,9,14)散列到散列列表(1)请绘制构造的散列表;(2)计算同等概率下成功搜索和失败搜索的平均搜索长度。(1)构造的哈希表如下(2)成功搜索的平均长度为:ASL成功=12/7。不成功搜索的平均长度为:不成功=18/7。42。(13点)让我们将n(n,1)个整数放入一维数组R中,尝试设计一种在时间和空间上尽可能有效的算法,并将存储在R中的序列向左循环移位P(0Pn)个位置,即,将R中的数据从(X0 X1 Xn-1)更改为(xpx 1x n-1Xxp-1)。(2)根据设计思想,用C或C或JAVA语言表达算法,并标注关键点。(3)解释你设计的算法的时间复杂度和空间复杂度,并分析42个问题的答案。(1)给出算法的基本设计思想:首
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2026年N1叉车司机理论考试模拟题题库(含答案)
- 2026高中生物教资面试往期考题题库及解析
- 近年真题 初中语文教资面试高频题题库及参考答案
- 2026年母婴护理证题库(含答案)
- 2026年新版金融笔试题库(含答案)
- 2026年大专中药考试题库带答案
- 2026年公卫执业医师题库及参考答案
- 2026年广西现代职业技术学院单招综合素质考试题库及答案
- 2026年产科专科护理学考试题库带答案
- 2026年新员工入职培训考核模拟题及答案
- 猝死科普教学课件
- YB-T5034-2024《履带用热轧型钢》
- 气象公园施工方案(3篇)
- 按摩技师合作合同协议书
- 安省g1驾照考试题库及答案
- 华润万家顾客服务培训
- 2025公基题库(附答案解析)
- 消化内镜检查中的事故应对与处理措施
- DBJ50-052-2020公共建筑节能(绿色建筑)设计标准
- 农村土地承包合同(2篇)
- 《银行承兑汇票培训》课件
评论
0/150
提交评论