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

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

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

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

3、个元素B.插入、删除操作不需要移动元素C.无需事先估计存储空间大小D.所需存储空间与线性表长度成正比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.除了

4、头结点，队列中的每一个元素都只有一个唯一的前驱。C.队列在实现递归算法、表达式求值等方面有较多的应用。D.队列是一种典型的后进先出（LIFO）的数据结构。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

5、.在线形表中采用折半查找法查找一个数据，线性表应满足（）A.以数组方式存储。B.以链接方式存储C.以数组方式存储且结点按关键码有序排列。D.以链接方式存储且结点按关键码有序排列10.快速排序在下列（）情况下最易发挥其长处。A.被排序的数据中含有多个相同排序码B.被排序的数据已基本有序C.被排序的数据完全无序D.被排序的数据中的最大值和最小值相差悬殊三、简答题（要求写出主要操作步骤及结果。每小题5分,共35分）1．试写出下列程序段的输出结果（栈的元素类型是char）voidmain(){stackS;charx=’c’,y

6、=’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(!StackEmpty(S)){Pop(S,y);printf(“%c”,y);}printf(“%c”,x);}2.已知如下的一棵二叉树，写出其先序，中序，后序和层序序列。ABCDEFGHI3.假定用于通讯的电文仅有8个字母C1，C2，…，C8组成，各个字母在电文中出现的频率分别为5，25，3，6，10，1

7、1，36，4，试为这8个字母设计哈夫曼编码树。【第3页共3页】4．已知一无向图的邻接表如下所示，写出从顶点V1出发的深度和广度优先搜索序列。5.求出下图的一棵最小生成树。3674185263475588546366.设待排序的排序码序列为{12,2,16,30,28,10,16*,20,6,18},试用希尔排序(增量为5,2,1)排序，写出每趟排序后的结果。7.设散列表为T[0..12]，哈希函数为H(key)=key%13,给定键值序列是{52,41,95,21,14,28,82,30}，请画出用线性探测再散列方法处理

8、冲突时所构成的散列表，并求出在等概率情况下，查找成功的平均查找长度。四、证明题（要求写出证明过程。共8分）证明：在有N个叶子的哈夫曼树上，其结点总数为2N-1。五、算法设计题（共17分，第1题8分，第2题9分）1.试写一个算法，实现在顺序线性表L中第i个位置之前插入新的元素e。2.给出二叉树的二叉链表存储结构，计算二