2017《数据结构》期末考试试题及答案.pdf
《2017《数据结构》期末考试试题及答案.pdf》由会员分享,可在线阅读,更多相关《2017《数据结构》期末考试试题及答案.pdf(20页珍藏版)》请在咨信网上搜索。
1、第 1 页 共 23 页2017数据结构期末考试试题及答案数据结构期末考试试题及答案1.2试题 1 答案.7数据结构期末考试试题及答案2.9试题 2 答案.14 数据结构期末考试试题及答案3.16 试题 3 答案.21 第 2 页 共 23 页数据结构期末考试试题及答案1 一、单选题(每题2 分,共 20 分)1.栈和队列的共同特点是()。A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.用链接方式存储的队列,在进行插入运算时().A.仅修改头指针B.头、尾指针都要修改C.仅修改尾指针D.头、尾指针可能都要修改3.以下数据结构中哪一个是非线性结构?()A.队列B
2、.栈C.线性表D.二叉树4.设有一个二维数组Amn,假设A00 存放位置在644(10),A22 存放位置在676(10),每个元素占一个空间,问A33(10)存放在什么位置?脚注(10)表示用 10 进制表示。A688 B678 C692 D696 5.树最适合用来表示()。A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第 k 层的结点数最多为().A2k-1 B.2K+1 C.2K-1 D.2k-1 7.若有 18 个元素的有序表存放在一维数组A19 中,第一个元素放 A1 中,现进行二分查找,则查找A3的比较序列的下标依次为()A.
3、1,2,3 B.9,5,2,3 C.9,5,3 D.9,4,2,3 8.对 n 个记录的文件进行快速排序,所需要的辅助存储空间大致为A.O(1)B.O(n)C.O(1og2n)D.O(n2)9.对于线性表(7,34,55,25,64,46,20,10)进行散列存储第 3 页 共 23 页时,若选用 H(K)=K%9 作为散列函数,则散列地址为1 的元素有()个,A1 B2 C3 D4 10.设有 6 个结点的无向图,该图至少应有()条边才能确保是一个连通图。A.5 B.6 C.7 D.8 二、填空题(每空 1 分,共 26分)1.通常从四个方面评价算法的质量:_ _、_ _、_和_。2.一个算
4、法的时间复杂度为(n3+n2log2n+14n)/n2,其数量级表示为_。3.假定一棵树的广义表表示为A(C,D(E,F,G),H(I,J),则树中所含的结点数为_个,树的深度为_,树的度为_。4.后缀算式 9 2 3+-10 2/-的值为 _。中缀算式(3+4X)-2Y/3对应的后缀算式为 _。5.若用链表存储一棵二叉树时,每个结点除数据域外,还有指向左孩子和右孩子的两个指针。在这种存储结构中,n 个结点的二叉树共有_个指针域,其中有 _个指针域是存放了地址,有_ 个指针是空指针。6.对于一个具有 n 个顶点和 e条边的有向图和无向图,在其对应的邻接表中,所含边结点分别有_n_个和_个。7.
5、AOV 网是一种 _ 的图。8.在一个具有n 个顶点的无向完全图中,包含有_条边,在一个具有 n 个顶点的有向完全图中,包含有_条边。9.假定一个线性表为(12,23,74,55,63,40),若按 Key%4 条件进行划分,使得同一余数的元素成为一个子表,则得到的四个子表分别为 _、_、_ 和_。10.向一棵 B_树插入元素的过程中,若最终引起树根结点的分裂,则新树比原树的高度 _。11.在堆排序的过程中,对任一分支结点进行筛运算的时间复杂度为_,整个堆排序过程的时间复杂度为_。第 4 页 共 23 页12.在快速排序、堆排序、归并排序中,_排序是稳定的。三、运算题(每题6 分,共 24 分
6、)1.在如下数组 A 中链接存储了一个线性表,表头指针为A 0.next,试写出该线性表。A 0 1 2 3 4 5 6 7 data 60 50 78 90 34 40 next 3 5 7 2 0 4 1 2.请画出图 10 的邻接矩阵和邻接表。3.已知一个图的顶点集V 和边集 E 分别为:(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)20 V=1,2,3,4,5,6,7;E=(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25;
7、用克鲁斯卡尔算法得到最小生成树,试写出在最小生成树中依次得到的各条边。4.画出向小根堆中加入数据4,2,5,8,3 时,每加入一个数据后堆的变化。四、阅读算法(每题7 分,共 14分)1.LinkList mynote(LinkList L)/L 是不带头结点的单链表的头指针if(L&L-next)q=L;L=Lnext;p=L;S1:while(pnext)p=pnext;S2:pnext=q;qnext=NULL;return L;图 10 第 5 页 共 23 页 请回答下列问题:1.(1)查询链表的尾结点(2)将第一个结点链接到链表的尾部,作为新的尾结点(3)返回的线性表为(a2,a3
8、,an,a1)(1)说明语句 S1的功能;(2)说明语句组 S2的功能;(3)设链表表示的线性表为(a1,a2,an),写出算法执行后的返回值所表示的线性表。2.void ABC(BTNode*BT)if BT ABC(BT-left);ABC(BT-right);coutdatadata)item=BST-data;/查找成功return _;else if(itemdata)return Find(_,item);else return Find(_,item);第 6 页 共 23 页/if 六、编写算法(共 8 分)统计出单链表 HL 中结点的值等于给定值X 的结点数。int Coun
9、tX(LNode*HL,ElemType x)第 7 页 共 23 页试题 1 答案一、单选题(每题 2 分,共 20 分)1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A 二、填空题(每空 1 分,共 26 分)1.正确性易读性强壮性高效率2.O(n)3.9 3 3 4.-1 3 4 X*+2 Y*3/-5.2n n-1 n+1 6.e 2e 7.有向无回路8.n(n-1)/2 n(n-1)9.(12,40)()(74)(23,55,63)10.增加 1 11.O(log2n)O(nlog2n)12.归并三、运算题(每题 6 分,共 24 分)1.线性表为:(
10、78,50,40,60,34,90)2.邻接矩阵:0111010101110111010101110邻接表如图 11 所示:图 11 3.用克鲁斯卡尔算法得到的最小生成树为:(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)20 4.见图 12 第 8 页 共 23 页5.4.画出向小根堆中加入数据4,2,5,8,3 时,每加入一个数据后堆的变化。6.图 12 四、阅读算法(每题 7 分,共 14 分)3.(1)查询链表的尾结点(2)将第一个结点链接到链表的尾部,作为新的尾结点(3)返回的线性表为(a2,a3,an,a1)4.递归地后序遍历链式存储的二叉树。五、
11、算法填空(每空 2 分,共 8 分)true BST-left BST-right 六、编写算法(8 分)int CountX(LNode*HL,ElemType x)int i=0;LNode*p=HL;/i为计数器while(p!=NULL)if(P-data=x)i+;p=p-next;/while,出循环时 i 中的值即为 x 结点个数return i;/CountX 4 4 4 4 4 2 2 2 5 5 5 2 2 8 8 4 3 5 2 8 3 4 第 9 页 共 23 页数据结构期末考试试题及答案2 一、单选题(每小题 2 分,共 8 分)1、在一个长度为 n 的顺序线性表中顺
12、序查找值为x 的元素时,查找成功时的平均查找长度(即x 与元素的平均比较次数,假定查找每个元素的概率都相等)为()。A n B n/2 C(n+1)/2 D(n-1)/2 2、在一个单链表中,若 q 所指结点是 p所指结点的前驱结点,若在 q与 p 之间插入一个 s所指的结点,则执行()。A slink=plink;plink=s;B plink=s;slink=q;C plink=slink;slink=p;D q link=s;slink=p;3、栈的插入和删除操作在()进行。A 栈顶B 栈底C 任意位置D 指定位置4、由权值分别为 11,8,6,2,5 的叶子结点生成一棵哈夫曼树,它的带
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 2017 期末考试 试题 答案
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【二***】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【二***】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。