云南专升本-数据结构历年试题及答案.doc
《云南专升本-数据结构历年试题及答案.doc》由会员分享,可在线阅读,更多相关《云南专升本-数据结构历年试题及答案.doc(14页珍藏版)》请在咨信网上搜索。
1、一、 单项选择题1算法指的是( D ) D解决问题的有限运算序列2线性表采用链式存储时,结点的存储地址( B )B连续与否均可3将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为( C )AO(1) BO(n) CO(m) DO(m+n)4由两个栈共享一个向量空间的好处是:( B ) B节省存储空间,降低上溢发生的机率5设数组datam作为循环队列SQ的存储空间,front为队头指针,rear为队尾指针,则执行出队操作后其头指针front值为( D) Dfront=(front+1)%m6如下陈述中正确的是( A ) A串是一种特殊的线性表 7若目标串的长度为n,模式串的长度为n
2、/3,则执行模式匹配算法时,在最坏情况下的时间复杂度是( C ) CO(n2) 8一个非空广义表的表头( D ) D可以是子表或原子9假设以带行表的三元组表表示稀疏矩阵,则和下列行表02335对应的稀疏矩阵是( A ) 10在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个数为( C ) C6 11在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( D ) Dn22e12假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有弧的时间复杂度是( C ) CO(n+e) 13用某种排序方法对关键字序列(25,84,21,47,15,2
3、7,68,35,20)进行排序时,序列的变化情况如下: 20,15,21,25,47,27,68,35,84 15,20,21,25,35,27,47,68,84 15,20,21,25,27,35,47,68,84 则所采用的排序方法是( D ) D快速排序14适于对动态查找表进行高效率查找的组织结构是( C ) C三叉排序树 15不定长文件是指(B ) B记录的长度不固定二、填空题16数据的逻辑结构是从逻辑关系上描述数据,它与数据的 存储(存储结构) 无关,是独立于计算机的.17在一个带头结点的单循环链表中,p指向尾结点的直接前驱,则指向头结点的指针head可用p表示为head= p-ne
4、xtnext 。18栈顶的位置是随着 进栈和退栈 操作而变化的。19在串S=“structure”中,以t为首字符的子串有 12 个.20假设一个9阶的上三角矩阵A按列优先顺序压缩存储在一维数组B中,其中B0存储矩阵中第1个元素a1,1,则B31中存放的元素是 a4,8 .21已知一棵完全二叉树中共有768结点,则该树中共有 384 个叶子结点。 22已知一个图的广度优先生成树如右图所示,则与此相 应的广度优先遍历序列为 abefcdg 。 23在单链表上难以实现的排序方法有 快速排序 和 堆排序 . 24在有序表(12,24,36,48,60,72,84)中二分查找关键字72时所需进行的关键
5、字比较次数为 2 。 25多重表文件和倒排文件都归属于 多关键字 文件。 三、解答题(本大题共4小题,每小题5分,共20分)26画出下列广义表的共享结构图形表示 P=((z),(x,y)),((x,y),x),(z))27请画出与下列二叉树对应的森林。28已知一个无向图的顶点集为a, b, c, d, e ,其邻接矩阵如下所示ab cde(1)画出该图的图形;(2)根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历,写出相应的遍历序列.深度优先遍历序列为:abdce 广度优先遍历序列为:abedc29已知一个散列表如下图所示:3520334859 0 1 2 3 4 5 6 7 8 9 1
6、0 11 12 其散列函数为h(key)=key%13, 处理冲突的方法为双重散列法,探查序列为:hi=(h(key)+*h1(key)m =0,1,m1其中h1(key)=key11+1回答下列问题:(1)对表中关键字35,20,33和48进行查找时,所需进行的比较次数各为多少?(2)该散列表在等概率查找时查找成功的平均查找长度为多少?解:()对关键字35、20、33和48进行查找的比较次数为、; ()平均查找长度一、单项选择 1。下面程序段的时间复杂度是( D ) for(i=0;i<n;i+) for(j=1;j<m;j+) Aij=0; D。O(mn) 2。在单链表中,指针
7、p指向元素为x的结点,实现“删除x的后继的语句是( B ) B。p>;next=p->nextgt;next 3。在头指针为head且表长大于1的单循环链表中,指针p指向表中某个结点,若pgt;nextgt;next= head,则( D ) D.*P的直接后继是尾结点4。判定“带头结点的链队列为空”的条件是( C ) C。Q.front=Q。rear 5.设有两个串T和P,求P在T中首次出现的位置的串运算称作( D ) D。子串定位6.广义表A=(a,(b),(),(c,d,e)的长度为( D ) D.7 7。一棵含18个结点的二叉树的高度至少为( C )序列为ABDECF,中序序
8、列为DBEAFC,则后序序列为( D ) D。DEBFCA 9.无向图中一个顶点的度是指图中( B ) B。与该顶点相邻接的顶点数 10。已知一个图如下所示,从顶点a出发进行广度优先遍历可能得到的序列为( C ) C。a c b d e f 11.在下列排序方法中,平均时间性能为O(nlogn)且空间性能最好的是( B ) B。堆排序 12。已知一组关键字为25,48,36,72,79,82,23,40,16,35,其中每相邻两个为有序子序列。对这些子序列进行一趟两两归并的结果是( A ) A。25,36,48,72,23,40,79,82,16,35 13.设顺序存储的线性表共有123个元素
9、,按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块,并在确定的块中进行顺序查找,则在查找概率相等的情况下,分块查找成功时的平均查找长度为( B ) B。23 14。索引非顺序文件的特点是( A ) A。主文件无序,索引表有序 15。倒排文件的主要优点是( C ) C。便于进行多关键字查询 二、填空题(本大题共10小题,每小题2分,若有两个空格,每个空格1分,共20分) 16。抽象数据类型的特点是将_数据_和_运算_封装在一起,从而现实信息隐藏。 17。从顺序表中删除一个元素时,表中所有在被删元素之后的元素均需_前移_一个位置。 18.在队列中,允许进行插入操作的一端称为_队尾_,允许
10、进行删除操作的一端称为_队头_。 19.如图两个栈共享一个向量空间,top1和top2分别为指向两个栈顶元素的指针,则“栈满” 的判定条件是_top1=top21_。 20。设S1=quot;goodquot;,S2=quot; quot;,S3="bookquot;,则S1,S2和S3依次联接后的结果是_ good book_. 21.假设三维数组A1098按行优先顺序存储,若每个元素占3个存储单元,且首地址为100,则元素A987的存储地址是_2257_. 22.已知在一棵含有n个结点的树中,只有度为k的分支结点和度为0的叶子结点,则该树中含有的叶子结点的数目为_(n1)/k)(
11、k-1)+1_或 n (n-1)/k_。 23。能够成功完全拓扑排序的图一定是一个_有向无环图_. 24.如果在排序前,关键字序列已接近正序或逆序,则在堆排序和快速排序两者之中,选用_堆排序_较为适当。 25.假设哈希表的表长为m,哈希函数为H(key),若用线性探查法解决冲突,则探查地址序列的形式表达为_hi=(H(key)+I)/m_。 三、解答题(本大题共4小题,每小题5分,共20分) 26.假设通信电文使用的字符集为a,b,c,d,e,f,名字符在电文中出现的频度分别为:34,5,12,23,8,18,试为这6个字符设计哈夫曼编码。请先画出你所构造的哈夫曼树(要求树中左孩子结点的权值小
12、于右孩子结点的权值),然后分别写出每个字符对应的编码。27。已知一个图如下所示,其顶点按a、b、c、d、e、f顺序存放在邻接表的顶点表中,请画出该图的邻接表,使得按此邻接表进行深度优先遍历时得到的顶点序列为acbefd,进行广度优先遍历时得到的顶点序列为acbdfe.28。已知两个45的稀疏矩阵的三元组表分别如下: 0 1 4 16 0 1 1 32 1 2 2 18 1 2 2 22 2 3 4 25 2 2 5 69 3 4 2 28 3 3 4 25 4 4 2 51 请画出这两个稀疏矩阵之和的三元组表。 解: 29。从空树起,依次插入关键字40,8,90,15,62,95,12,23,
13、56,32,构造一棵二叉排序树. (1)画出该二叉排序树 (2)画出删去该树中元素值为90的结点之后的二叉排序树。1。计算机识别、存储和加工处理的对象被统称为(BB.数据元素2。在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是(B)B.O(n)3。队和栈的主要区别是(D) D.限定插入和删除的位置不同4.链栈与顺序栈相比,比较明显的优点是(D)D。不会出现上溢的情况5.采用两类不同存储结构的字符串可分别简称为(B)B.顺序串和链串6.在目标串T0。n1=xwxxyxy中,对模式串P0.。m-1=xy进行子串定位操作的结果是(C)C。37.已知广义表的表头为a,表尾为(b
14、,c),则此广义表为(B) B。(a,b,c)8。二维数组A按行优先顺序存储,其中每个元素占1个存储单元.若A11的存储地址为420,A33的存储地址为446,则A55的存储地址为(C) C.4729。二叉树中第5层上的结点个数最多为(D)D.3210.下列编码中属前缀码的是(A) A。1,01,000,00111。如果某图的邻接矩阵是对角线元素均为零的上三角矩阵,则此图是(D)D。有向无环图12。对n个关键字的序列进行快速排序,平均情况下的空间复杂度为(D)D.O(nlogn)13.对表长为n的顺序表进行顺序查找,在查找概率相等的情况下,查找成功的平均查找长度为(n/2)A.B。C.D.n1
15、4。对于哈希函数H(key)=key13,被称为同义词的关键字是(D)D。25和5115。稠密索引是在索引表中()A。为每个记录建立一个索引项B。为每个页块建立一个索引项C.为每组记录建立一个索引项D。为每个字段建立一个索引项二、填空题(每小题2分,若有两个空格,每个空格1分,共20分)16.当问题的规模n趋向无穷大时,算法执行时间T(n)的数量级被称为算法的_时间复杂度_17。在链表的结点中,数据元素所占的存储量和整个结点所占的存储量之比称作_存储密度_18.已知链栈的结点结构为栈顶指针为top,则实现将指针p所指结点插入栈顶的语句依次为_date_和_next_。19.空串的长度是_0_;
16、空格串的长度是_空格的数目_。20.假设一个6阶的下三角矩阵B按列优先顺序压缩存储在一维数组A中,其中A0存储矩阵的第一个元素b11,则A14存储的元素是_b63_。21。在一棵度为3的树中,度为2的结点个数是1,度为0的结点个数是6,则度为3的结点个数是_2_。22.如图所示的有向无环图可以排出_种不同的拓扑序列。 23。利用筛选法将关键字序列(37,66,48,29,31,75)建成的大根堆为(_75,66,48,29,31,37)。24.对长度为20的有序表进行二分查找的判定树的高度为_5_.25.在多重表文件中,次关键字索引的组织方式是将_次关键字相同_的记录链接成一个链表.三、解答题
17、(本大题共4小题,每小题5分,共20分)26.对于单链表、单循环链表和双向链表,如果仅仅知道一个指向链表中某结点的指针p,能否将p所指结点的数据元素与其确实存在的直接前驱交换?请对每一种链表作出判断,若可以,写出程序段;否则说明理由。datenext单链表和单循环链表的结点结构为priordatenext双向链表的结点结构为(1)单链表:(不可以,无法找到前驱接点)(2)单循环链表(可以:q=pnext;while(qnext!=p)q=q-next;qdata-pdata;(3)双向链表(可以:ppriordatapdata;)27。假设通信电文使用的字符集为a,b,c,d,e,f,g,字符
18、的哈夫曼编码依次为:0110,10,110,111,00,0111和010。(1)请根据哈夫曼编码画出此哈夫曼树,并在叶子结点中标注相应字符;(2)若这些字符在电文中出现的频度分别为:3,35,13,15,20,5和9,求该哈夫曼树的带权路径长度。28.当采用邻接表作为图的存储结构时,也可将邻接表中的顶点表由顺序结构改为链表结构。(1)请分别画出这种邻接表的顶点链表结点和边表结点,并说明结点中各个域的作用;(2)对如图所示的有向图画出这种邻接表。29。已知4阶B树如图所96示。(1)分别画出将关键字23和89相继插入之后的B树.(2)画出从插入之前的B-树中删除关键字51之后的B树.一、单项选
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 云南 数据结构 历年试题 答案
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【人****来】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【人****来】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。