版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、05 年招收硕士研究生入学考试试题科目名称:数据结构试题编号:429共3 页一判断题(每小题1 分,共10 分)若一个算法中的语句频度之和为 T(n)=1024n+4nlogn,则算法的时间复杂度0(nlogn)串是一种特殊的线性表。两个栈共享一个向量空间的优点是其中一个栈可用该空间一半或一半以上。广义表是非线性数据结构,因为表中的元素可以是子表。二叉树的中序序列中,结点A 在结点B 之前的条件是A B 的祖先。若一个有向图的拓扑排序没有包括全部顶点,则说明该图存在有向回路。具有几个顶点 e 条边的无向图,若用邻接矩阵作为存储结构,则求任一顶点的0(e).哈希法既是一种查找方法,又是一种存储方
2、法。希尔排序是属于插入排序的改进方法。在单链表上可以实现简单选择排序,但难以实现堆(选择)排序。二填空题(每小题2分,共20分)在字符串S=“structure”中,以t 为首字符的子串有个。N 阶的下三角阵按行序为主序存储,每个元素占 L 个单元,若已知首地址为loc(A00 ),则元素Aij(0jin-1)的存储地址loc(Aij)为1,2,3,nP1,P2,P3,Pn。若P1=n,则Pi为已知广义表LSa(b,c,)运用head和tail函数取出LS中的原子b的运算是在一棵具有h 层的满三叉树中,结点总数为n 3 0 0的结点数为T 41,2,3,4 4,2,1,1,则听众叶子数为20
3、4 阶B-树中进行查找,至多访问个结点。将 m 个互为冲突(具有相同的哈希地址)的记录存入哈希表,处理冲突采用伪随机探测法。最多需要探测次。30 5 块,进行分块查找,平均查找长度是。三,单选题(2 30分)算法是指可执行程序。 B。问题求解的计算方法。C。系统软件。D。解决问题的有限运算序列。从逻辑上可以把数据结构分成结构。动态和静态紧凑和非紧凑线性和非线性内部和外部将长度为n 的单链表链接在长度为m 的单链表之后的算法的时间复杂度为A0(1)B0(n) C0(m) D0(m+n)长度为()front 和rear 条件为rear%n=front Bfront%n+1=rearCrear%n-
4、1=front Drear%n+1=front2n 个结点,则对于m0 个结点的二叉树的先序序列正好相反,则该二叉树一定不是的二叉树。A任一结点无左孩子B任一结点无右孩子C深度为nD存在度为 2 的结点 7二叉树用二叉链表表示,若要将其所有结点的左,右子树相互交换位置,则采用下列遍历的方法较为合适。先序C后序对于二叉树的两个结点X和Y,应该选择两个序列来判断X是否Y 的祖先。A先序和后序 B先序和中序 C中序和后序 D任意两个序列都行最小生成树指的是连通图中 A边数最少的生成树 B顶点相对较少的生成树 C极小连通子图 D所有生成树中权值之和最小的生成树具有n 个顶点的强连通图至少有条弧。An-
5、1Bn C2nDn(n-1)20 个有序记录进行折半查找,查找成功的平均查找长度为A5B37/10C39/10D41/10哈希表长度为m,哈希函数H(K)=K%P,一般来说P 应取小于m 的最大A奇数偶数C素数D合数对动态查找有高效率的查找表组织结构是A有序表B分块有序表C循环链表 DB-树当初始数据有序时,不应采用A堆排序B快速排序C基数排序D希尔排序在n 个元素中找出两个最小的元素,当n 很大时,采用方法比较次数较少。A树型选择排序B简单选择排序C归并排序 D快速排序四综合题(每小题 10 分,共 40 分) 1一棵二叉树的先序,中序,后序序列分别如下(其中有部分结点未显示出来先序序列:_
6、B_F_ICEH_G 中序序列:D_KFIA_EJC_ 后序序列:_K_FBHJ_G_A。将先序,中序,后序序列完整写出来。画出该二叉树。2对关键字序列Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec (1).构造一棵平衡二叉(排序)树(2。求其查找成功的平均查找长度AS。3 对无向加权图:用普里姆算法从顶点出发求其最小生成树,并写出选点顺序。用克鲁斯卡尔算法求其最小生成树,并写出选边顺序43 阶B-树:B-29,25,84,6 后的B-树。B-11,49,52,36 后的B-树。五算法题(1,2,3 12 4 14 50 分)对用二叉链表表示
7、的二叉树,设计一个算法,求其后序序列的第一个结点。完全二叉树顺序存储在数组An中,请写一算法:求下标为i 和j 有公共祖先结点,并按下标从大到小的顺序将它们的值打印出来。长度为n 1 的单链表中。试写一算法,判断字符串是否中心对称(abccb是中心对称。已知一棵满二叉树顺序存储在数组Bn中,设计一个算法,产生二叉树的二叉链表。2003 年数据结构考研试题判断题(每小题一分,共十分)数据结构,数据元素,数据项在计算机中的映象(表示)分别称为存储结构,结点,数据域。对线性表的逻辑顺序与存储顺序总是一致的。错广义表的表头或是元素或是一个广义表,而表尾总是一个广义表。对拓扑排序是一种内部排序的算法。错
8、字符串是一种特殊的线性表,其特殊性体现在数据元素是一个字符。对若线索二叉树有n 个结点,则必有n+1 条不空的指向树中结点的线索。 错稀疏矩阵的压缩存储方法一般有三元组和十字链表两种。对在AOE 网中,一定有不止一条关键路径。错二维数组是其数据元素为线性表的线性表。对一个栈的输入序列是12345,则输出序列43512 是可能的。错二 单项选择(2 20 分)数据结构从逻辑上可以分成 线性和非线性 两种结构。哈希(Hash)法查找的基本思想是根据 关键字值 来决定记录的存储位置。利用栈求表达式(A-)-)-(D-(E-F)操作数栈须有4项。图的广度优先搜索算法类似于二叉树的 按层 遍历操作。在所
9、有排序方法中关键字比较次数与记录初始排列次序有关的是 插入排序。A 1 81 103 个单元,则该数组按“以列序为主序”存放时,A58的起始位置是 180表达式a*(b+c)-d 的后缀表示(逆波兰式)是 abc+*d在一个具有n 个结点的单链表中查找,查找成功时需要平均计较 (n+1)/2 结点。设 Q0n-1为循环队列,front,rear 分别为队列的头,尾,则队列中的元素个数为(rear-front+n) MOD n在各种查找方法中,平均查找长度与结点个数无关的查找方法是 二叉树查找三 计算题(6 30 分)一颗树有N1 1 的结点,N2 2 的结点,Nm 个度为m 的结点,求:该树中
10、终端(叶)结点的个数N0对长度为 12 的有序表进行折半查找,求查找成功与不成功时各平均比较次数。3 B25 个关键字,求该B树的最小高度和最大高度(不包含叶子层)已知一棵平衡二叉树的深度为 6,求树中最少可能的结点数和最多可能的结点数。n 个结点的平衡二叉树,请分别求出当二叉树具有最小深度K 和最大深度K K层上的结点数。四 综合题 (8 40 分)1 广义表 A(a),(b,(c,d,e),(),请写出其链式存储结构。设链表中有两类结点,表结点形式为tag=1 hptp,其中指针hp和tp分别指向表头和表尾,元素(原子)结点形式为 tag0元素值2 对关键字序列(49,38,65,97,7
11、5,13,27,51,55,10)进行希尔排序。若排序三趟,各趟的增量分别为 d1=5 ,d2=3 ,d3=1 ,则请写出每趟的结果及元素移动次数。电文中使用字符a,b,c,d,e,f,他们出现的频率为(4,7,5,2,9,8),请画出对应的编码哈夫曼树, 并求出传送电文的总长度。已知一棵二叉树的中序序列为 DAJFBGICEHK,后序序列为 DAFBJCIKHEG,请画出该二叉树,并使其成为先序线索树。对于加权图1268151341610920105用克鲁斯卡尔(Kruskal)方法构造最小生成树,并写出选边的次序。五 算法题 (1,2 13 分,3,4 12 50 分)设用二叉链表表示的二
12、叉树不空,其根指针为root,结点形式为: lchilddatarchild请写出将二叉树中所有结点的左,右子树相互交换的非递归算法。利用两个栈 S1 和 S2 来模拟一个队列。若不存在栈溢出问题,则请写出用栈的操作来实现队列的插入和删除的算法。设计一个算法,在长度为n 的(小顶)堆Rn中删除一个元素Rs(s=)一个长度为n1 的(小顶)堆,并将Rs存放于Rn中。p 个算法,将p 所指节点的前驱结点变为p 所指结点的后继结点。2001 年数据结构考研试题填空(14 分)数据元素是数据结构的基本单位,数据项是数据的不可分割的最小单位。深度是k 2(k1)2k-1 个结点。哈希表的查找效率主要取决
13、于造表时选取的哈希函数和处理冲突的方法。100 个记录进行折半查找,最多比较7 1 次。n 0 条边,最多有n(n-1)/2 条边。AOE 对于堆排序,常用的建堆算法是筛选法,堆的形状是一棵完全二叉树。1 线性表的链式存储结构优于顺序存储结构。错2 链表的每个节点中都帢包含一个指针。错例如双向链表31 线性表的链式存储结构优于顺序存储结构。错2 链表的每个节点中都帢包含一个指针。错例如双向链表3 栈和队列都是顺序存储结构的线性结构。错链栈4 2 时,则该树为二叉树。错5 若广义表中的每个元素都是原子,则广义表为线性表。对三 问答题(每小题4 分,共16 分)3 4 层(根为第一层,叶子为第四层
14、)的B树,至少有多少个关键字,至多有多少个关键字?答:7 个26个利用栈秋表达式A-(D-(E-F)的值,运算符栈和操作数栈各必须具有多少项?答:5 项4 项以行序为主序存储 10 阶对称矩阵 A,采用下三角的压缩存储方式,若起始地址是d,则A85的存储地址是多少?答:32d(如图一所示H(K)=K MOD 11,用二次探测再94 的记录的存储地址是多少?012345678910图一答:存储地址是 24516396276四 综合题(5 35 分)给定一组权值9,6,14,17,2,15,3,16,请构造哈夫曼树,并计算其带权路径长度。186已知二叉树的先序遍历的结果为ABCDEFGHIJ,中序遍历的结果为CBEDAHGIJF,请画出这颗二叉树。对图二所示的无向图1)请用邻接表表示,且顶点链接按序号从小到大链接。(2)请写出从V0 出发的深度优先遍历和广度优先遍历的结果。图二:0O1234567将图三所示的树转换为二叉树,并使其成为后序线索树。图三:ABCDEFGHIJKLMN5 对关键字序列44,12,53,13,37,88,24,61构造一棵平衡二叉树。6 已知一个OE 网,如图四所示,求其关键路径,并给出时间4 5 最早发生时间?图四:1441252691151009181463535778
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2026年棒球专业模拟考试卷带答案
- 2026年维修电工安全模拟试题及答案
- 2026年建筑安全务实模拟试题及参考答案
- 2026年国际志愿者日志愿服务条例模拟试题(含答案)
- 2026年房地产经纪人考试房地产法规备考试题(含答案)
- 2026年食品质量监督员专业能力考核模拟试题及答案
- 2026年新媒体实务模拟试题及答案
- 2026年昌江黎族自治县乡村振兴投资发展有限公司招聘模拟考试题带答案
- 吉大2026年课程考试电子政务概论离线作业考核模拟试题带答案
- 2026年执业医师考试仿真模拟试题及答案
- 企业融资申请书范本及填写指南
- 藏羌碉楼营造技艺传承-洞察及研究
- DB35∕T 1036-2023 10kV及以下电力用户业扩工程技术规范
- 河北食品经营许可现场核查表及核查意见(食品销售)
- 数字智慧方案5445丨企业碳资产管理案例分享北京环境交
- 《奶牛的饲养管理》课件
- 中国文化概论教学课件
- 冷库储存生姜合同范例
- 气管切开套管的选择与更换
- GB/T 9799-2024金属及其他无机覆盖层钢铁上经过处理的锌电镀层
- 半球电压力锅说明书
评论
0/150
提交评论