《数据结构》3套模拟试题综合测试题带答案5.doc
《《数据结构》3套模拟试题综合测试题带答案5.doc》由会员分享,可在线阅读,更多相关《《数据结构》3套模拟试题综合测试题带答案5.doc(32页珍藏版)》请在咨信网上搜索。
1、数据结构模拟试题13一、填空题(每小题2分,共18分)1、 数据的逻辑结构包括 , 和 三种结构。2、 队列是操作受限的线性结构,只能在 插入元素,而在 删除元素。3、 串是一种特殊的线性表,其特殊性体现在 。4、 有一个10阶对称矩阵A,采用压缩存储方式采用压缩存储方式,以行为主存储下三角形到一个一维数组中,A00的地址是100(每个元素占2个基本存储单元),则A59的地址是 。5、 在高度为h的二叉树的中只有度为0和度为2的结点,则该类二叉树中所包含的结点数至少为 。6、 对于一个有n个顶点和e条边的无向图,若采用邻接链表存储,则表头向量的大小为,邻接表中的结点总数为 。7、 对线性表进行
2、二分查找时,要求线性表必须是 ,且要求 。8、 对于文件,按物理结构划分,可分为顺序文件、 文件、 文件和多关键字文件。9、 外部排序的最基本方法是 ,其主要时间花费在 方面。二、单项选择题(请将答案写在题目后的括号中。每题2分,共18分)1、如下函数是求1!+2!+n!,其时间复杂度是( )。Long int Sum (int n) long int sum=0 , t=1 ; int p ;for (p=1; p=n ;p+) t=t*p ; sum+=t ; return(sum) ;(A) O(n) (B) O(n2) (C) O(2n) (D) O(n2n)2、 设有一个栈顶指针为t
3、op的顺序栈S,则弹出S的栈定元素的操作是( )。(A) p=Stop+; (B) p=S+top;(C) p=Stop-; (D) p=S-top; 3、 广义表(a),(b),c),(d)的表头是 ,表尾是 。( )(A) (a) (b),c),(d) (B) (a) (b),c),(d)(C) (a),(b),c),(d) (D) (a) (d)4、一棵二叉树,其先序遍历序列是abdgehicf,中序遍历序列是gdbheiafc,则其后序遍历序列是( )。(A) abdgehicf (B) gdbheiafc(C) gdhiebfca (D) gdheibfca5、 具有五层结点的平衡二
4、叉树至少有 。( )(A) 10 (B) 12 (C) 17 (D) 156、 在无权图G的邻接矩阵中,若(Vi,Vj)或属于G的边集,则对应元素Aij等于 ,否则等于 。( )(A) 1,1 (B) 1,0 (C) 0,1 (D) 0,07、 判断一个有向图是否存在回路除了可以利用拓扑排序方法外,还可以利用( )。(A) 广度优先遍历算法 (B) 求关键路径的方法(C) 深度优先遍历算法 (D) 求最短路径的Dijkstra算法8、设有一个长度为n的线性表,当采用顺序查找方法时,每个元素的平均查找长度是 ;而采用二分查找方法时,其平均查找长度是 。( )(A) n/2 ,O(n) (B) n
5、/2,O(2n) (C) (n+1)/2, O(n2n) (D) (n+1)/2, O(2n)9、 设有一组记录的关键字是(37,28,56,80,60,14,25,50),用快速排序法以第一个记录为基准得到的一次划分结果是( )。(A) 25,28,14,37,60,80,56,50 (B) 25,28,37,14,60,80,56,50 (C) 25,28,14,37,60,56,80,50 (D) 25,28,37,14,56,80,60,50三、分析题(每题6分,共30分)1、 设有一份电文中工使用了7个字符:a,b,c,d,s,m,n,它们出现的频率依次为3,6,4,2,8,9,7,
6、请画出对应的Huffman树(按左子树根结点的权小于等于右子树根结点的权的次序构造),并求其带权路径长度WPL。2、 对于下图中的网,写出该网的邻接链表;然后写出其深度优先搜索生成树(假设从顶点V3出发);最后给出按Kruskal算法得到的最小生成树。1243812561173、 将关键字序列(14,19,16,7,4,13,25,9,18,12)依此插入到初态为空的二叉排序树中,请画出所得到的树T;然后画出删除13之后的二叉排序树T1;最后再后画出插入13之后的二叉排序树T2。4、 线性表的关键字集合31,25,18,29,42,67,15,33,17,36,46,共有11个元素,已知散列函
7、数为:H(k) = k MOD 11,采用线性探测法处理冲突,请给出对应的散列表结构,并计算该表成功查找的平均查找长度。5、 已知序列35,29,22,16,17,9,38,27,13,45,请给出采用希尔排序法对该序列做非递减排序时的每一趟结果,增量序列为5,3,1。四、算法填空(每空2分,共20分)请在下面各个算法的空白处填上相应的语句,以实现算法功能。每个空白处只能填一个语句。1、 循环队列Q的入队操作算法。#define Max_Queue_Size 100Void Insert_CirQueue(SqQueue Q , ElemType e) if ( ) printf(“The C
8、ircular Queue is Overflow!”) ;else ; Q.Queue_arrayQ.rear=e ; 2、 二叉树先序遍历的非递归算法。#define Max_Node_Num 50Void PreorderTraverse( BTNode *T) BTNode *StackMax_Node_Num ,*p=T, *q ; int top=0 ; if (T=NULL) printf(“The Binary Tree is Empty!n”) ; else do visit( p- data ) ; q=p-Rchild ; if ( q!=NULL ) stack+top
9、=q ; ; if (p=NULL) ; while ( ) ; 3、 用正邻接链表保存有向图,各结点的结构形式如下,所有的顶点结点放在数组adjlist中,统计图中顶点的入度。链表结点adjvexinfonextarc顶点结点indegreedatafirstarcVoid count_indegree(ALGraph *G) int k ; LinkNode *p ;for (k=0; kvexnum; k+)G-adjlistk.indegree=0 ;for (k=0; kvexnum; k+) ;while (p!=NULL) G-adjlistp-adjvex.indegree+
10、; ; 4、 冒泡排序算法。#define FALSE 0#define TRUE 1Void Bubble_Sort(Sqlist *L) int j ,k ,flag ;for (j=0; jlength; j+) ;for (k=1; klength-j; k+) /* 一趟排序 */if ( ) flag=FALSE ; L-R0=L-Rk ; L-Rk=L-Rk+1 ; ; if (flag=TRUE) break ; 五、编写算法(要求给出相应的数据结构说明,14分)设以L为头结点的单链表中的所有结点的值均互不相同。对该单链表进行动态查找,查找值为k的结点:若链表中有该值的结点,则
11、删除;若链表中没有该值的结点,则插入为第一个结点;并对算法进行分析。5数据结构模拟试题13参考答案一、填空题(每小题2分,共18分)1、 线性结构 树形结构 图(或网)状结构2、 表的一端 表的另一端3、 数据元素是一个字符4、 2005、 2h-16、 n 2e7、 以顺序方式存储 结点按关键字有序8、 索引 散列9、 归并 内、外存之间的数据交换二、单项选择题(请将答案写在题目后的括号中。每题2分,共18分)题号123456789答案ACBCDBCDA三、分析题(每题6分,共30分)1、 解:依题意对应的Huffman树如下图所示。39891772354691322WPL=(2+3)4+(
12、4+6+7)3+(8+9)2=1052、 解:该网的邻接链表如下图所示: 012312342123748112364112617451821135从顶点V3出发的深度优先搜索的顶点序列是3214,相应的生成树如下:最小生成树1243567从顶点V3出发深度优先搜索生成树124381263、 解:将关键字序列(14,19,16,7,4,13,25,9,18,12)依此插入到初态为空的二叉排序树中所得到的二叉排序树T如图(a)所示;删除13之后的二叉排序树T1如图(b)所示;最后再插入13之后的二叉排序树T2。图(a) 生成的二叉排序树14719913416251218图(b) 删除13的二叉排序
13、树147199124162518图(c) 插入13的二叉排序树147199124162518134、 解:根据所给定的散列函数和处理冲突方法,其地址计算过程如下:H(31)=31 MOD 11=9 H(25)=25 MOD 11=3 H(18)=18 MOD 11=7H(19)=19 MOD 11=8 H(42)=42 MOD 11=9 冲突 H(42)=(9+1) MOD 11=10H(67)=67 MOD 11=1 H(15)=15 MOD 11=4 H(33)=33 MOD 11=0H(17)=17 MOD 11=6 H(36)=36 MOD 11=3 冲突 H(36)=(3+1) MO
14、D 11=4 冲突H(36)=(4+1) MOD 11=5 H(46)=46 MOD 11=2得到的散列表结构如下:散列地址关键字0 1 2 3 4 5 6 7 8 9 1033 67 46 25 15 36 17 18 19 31 42成功查找的平均查找长度:ASL=(19+12+13)/11=14/115、 解:做非递减排序时的每一趟结果如下:初始关键字:35,29,22,16,17,9,38,27,13,45第一趟: 9,29,22,13,17,35,38,27,16,45第二趟: 9,17,16,13,27,22,38,29,35,45第三趟: 9, 13,16,17,22,27,29
15、,35,38,45第三趟归并完毕,排序结束。四、算法填空(每空2分,共20分)请在下面各个算法的空白处填上相应的语句,以实现算法功能。每个空白处只能填一个语句。1、 循环队列Q的入队操作算法。(Q.rear+1)%Max_Queue_Size=Q.frontQ.rear=(Q.rear+1)%Max_Queue_Size ;2、 二叉树先序遍历的非递归算法。P=p-Lchildp=stacktop-p!=NULL 3、统计图中顶点的入度。P=G-adjlistk.firstarcP=p-nextarc4、冒泡排序算法。flag=TRUEL-Rk.keyL-Rk+1.keyL-Rk+1=L-R0
16、五、编写算法(要求给出相应的数据结构说明,14分)解:结点类型定义及算法如下:#define int ElemType typedef struct Lnode ElemType data; /* 数据域,保存结点的值 */struct LNode *next; /* 指针域 */LNode; /* 结点的类型 */void Dynomic_search(LNode *L , ElemType k) LNode *ptr , *p=L, *q=L-next ;while ( q!=NULL&q-data!=k) p=q ; q=q-next ; if (q-data=k) p-next=q-n
- 配套讲稿:
如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。