《数据结构与算法》模拟试卷三

《数据结构与算法》模拟试卷三

ID:17616504

大小:722.50 KB

页数:3页

时间:2018-09-03

《数据结构与算法》模拟试卷三_第1页
《数据结构与算法》模拟试卷三_第2页
《数据结构与算法》模拟试卷三_第3页
资源描述:

《《数据结构与算法》模拟试卷三》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、江西财经大学09-10第二学期期末考试试卷试卷代码:18335C授课课时:96考试用时:150分钟课程名称:数据结构与算法(软件)适用对象:软件工程选课班试卷命题人邓庆山试卷审核人一、填空题(每空2分,共20分)1.栈与队列和一般线性表的区别体现在_____________。2.向一个长度为n的顺序线性表删除第i个元素(1<=i<=n),需向前移动______个元素。3.在双向链表中,每个结点有两个指针域,一个指向_________,一个指向_________。4.在一棵二叉树中,度为0的结点的个数是10,则度为2的结点个数是_________5.一个有n个结点的二

2、叉树的深度最大为___________,最小为__________6.n个定点的连通图至少有_______条边。7.在无向图G的邻接矩阵A中,若(vi,vj)属于图G的边的集合,则对应元素A[i][j]等于_______,否则等于_________.二、选择题(从下列各题四个备选答案中选出一个正确答案,并将其代号写在答题纸相应位置处。每小题2分,共10分。)1.组成数据的基本单位是()A.数据项B.数据类型C.数据元素D.数据变量2.链表不具备的特点是()A.可随机访问任何一个元素B.插入、删除操作不需要移动元素C.无需事先估计存储空间大小D.所需存储空间与线性表长

3、度成正比3.head为指向单链表的头结点中的指针,判断该链表的非空条件是()。A.head==NULLB.head->link==NULLC.head!=NULLD.head->link!=NULL4.一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是()。A.edcbaB.decbaC.dceabD.abcde5.请选出下列说法中唯一正确的一个:()。A.判断队列是否为空只能通过头结点的count信息来判断。B.除了头结点,队列中的每一个元素都只有一个唯一的前驱。C.队列在实现递归算法、表达式求值等方面有较多的应用。D.队列是一种典型的后进先出(LIF

4、O)的数据结构。6.【第3页共3页】如果一棵二叉树结点的前序序列是A、B、C,后序序列是C、B、A,则该二叉树结点的中序序列()。A.必为A、B、CB.必为A、C、BC.必为B、C、AD.不能确定7.含有15个结点的二叉树的最小高度是()A.3B.4C.5D.68.具有n(n>0)个顶点的无向图最多含有()条边。A.n(n-1)B.n(n+1)C.n(n-1)/2D.n(n+1)/29.在线形表中采用折半查找法查找一个数据,线性表应满足()A.以数组方式存储。B.以链接方式存储C.以数组方式存储且结点按关键码有序排列。D.以链接方式存储且结点按关键码有序排列10.快

5、速排序在下列()情况下最易发挥其长处。A.被排序的数据中含有多个相同排序码B.被排序的数据已基本有序C.被排序的数据完全无序D.被排序的数据中的最大值和最小值相差悬殊三、简答题(要求写出主要操作步骤及结果。每小题5分,共35分)1.试写出下列程序段的输出结果(栈的元素类型是char)voidmain(){stackS;charx=’c’,y=’k’;InitStack(S);Push(S,x);Push(S,’a’);Push(S,y);Pop(S,x);Push(S,’t’);Push(S,x);Pop(S,x);Push(S,’s’);While(!StackE

6、mpty(S)){Pop(S,y);printf(“%c”,y);}printf(“%c”,x);}2.已知如下的一棵二叉树,写出其先序,中序,后序和层序序列。ABCDEFGHI3.假定用于通讯的电文仅有8个字母C1,C2,…,C8组成,各个字母在电文中出现的频率分别为5,25,3,6,10,11,36,4,试为这8个字母设计哈夫曼编码树。【第3页共3页】4.已知一无向图的邻接表如下所示,写出从顶点V1出发的深度和广度优先搜索序列。5.求出下图的一棵最小生成树。3674185263475588546366.设待排序的排序码序列为{12,2,16,30,28,10,1

7、6*,20,6,18},试用希尔排序(增量为5,2,1)排序,写出每趟排序后的结果。7.设散列表为T[0..12],哈希函数为H(key)=key%13,给定键值序列是{52,41,95,21,14,28,82,30},请画出用线性探测再散列方法处理冲突时所构成的散列表,并求出在等概率情况下,查找成功的平均查找长度。四、证明题(要求写出证明过程。共8分)证明:在有N个叶子的哈夫曼树上,其结点总数为2N-1。五、算法设计题(共17分,第1题8分,第2题9分)1.试写一个算法,实现在顺序线性表L中第i个位置之前插入新的元素e。2.给出二叉树的二叉链表存储结构,计算二

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。