浙江林学院 2006---2007学年第一学期末考试卷(a)

《浙江林学院 2006---2007学年第一学期末考试卷(a)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、浙江林学院2006---2007学年第一学期末考试卷（A）课程名称：数据结构课程类别：必修考试形式：闭卷注意：本试卷一共五大题,都为必做题目,请认真读题，给出答案。一二三四五得分一、填空题(10×2=20分，每空2分)1、T2006011000080000270设Q[0..N-1]为循环队列，其头、尾指针分别为P和R，则队Q中当前所含元素个数为_______。2、a=“ABCDEFG”,b=“CDEF”.则串a的长度为____，串b在串a中的位置为____。3、设一个线性表的长度为50，P是指向线性链表的第10个元素，且P->next->n

2、ext指向第____元素。4、对于对称矩阵，我们可以为每一对对称元分配一个存储空间，于是，可以把n2个元压缩到_______个元的空间中。5、广义表E=(a,E)的长度为______6、二叉树的第i层最多有______个结点，深度为k的二叉树最多有______个结点。7、在队列中，允许插入的一端为______，允许删除的一端为_______.8、利用MST性质来构造最小生成树的两种常用算法为_________和__________.9、使用折半查找时，静态查找表必须不仅是______，并且______存储.10、快速排序的时间复杂度为___

3、___，空间复杂度为______。二、判断(对的打∨,错误打×,10×1=10分)1、在数据元素的非空有限集中，存在唯一的一个被称为”前驱”的元素，也存在唯一的一个称为”后继”的元素()2、一般情况下，在第i(1<=i<=n)个元素之前插入一个元素，需要将第n个到第i个元素向后移动一个位置，移动元素的个数为n-i+1()3、由于链式存储结构不要求逻辑上相邻的元素在物理位置上也相邻，因此，它具有随机存取的优点()第6页共6页1、队列的基本特征是先进后出()2、非空完全二叉树的一个任意结点的右子树深度与其左子树深度的差值或者为0或者为1。()3

4、、n个结点的二叉链表中必定存在n+1个空链域。4、赫夫曼树是指带权路径长度WPL最小的二叉树。一般而言，在给定条件下构造出的赫夫曼树不是唯一的。()5、路径长度最长的路径为关键路径。()6、先序遍历二叉排序树可得到一个关键字有序的序列。()10、希尔排序中，增量d值的选择应为一个素数，并且在最后一趟排序时必须为1()三、选择题（10×2=20分）1、线性链表不具有的特点().A.随机访问B.不必事先估计所需存储空间大小C.插入与删除时不必移动元素D.所需空间与线性表长度成正比2、向顺序栈中压入新元素时,应当().A.先移动栈顶指针,再存入元

5、素B.先存入元素,再移动栈顶指针C.先后次序无关紧要D.同时进行3、具有65个结点的完全二叉树的高度为().(根的层次号为1)A.8B.7C.6D.54、由权值分别为3，8，10，2，6的叶子结点生成一棵哈夫曼树，则其中非终端结点数为()。A.2B.3C.4D.55、n个顶点的有向完全图中含有向边的数目最多为(  ) A.n-1               B.n          C.n(n-1)/2          D.n(n-1)6、ALV树是一种平衡的二叉排序树，树中任一结点的(  ) A.左、右子树的高度均相同       B.

6、左、右子树高度差的绝对值不超过1 C.左子树的高度均大于右子树的高度 D.左子树的高度均小于右子树的高度7、一个对象序列的排序码为{46,79,56,38,40,84},采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为().第6页共6页A.{38,46,79,56,40,84}B.{38,79,56,46,40,84}C.{40,38,46,56,79,84}D.{38,46,56,79,40,84}8、下列那种排序方法是稳定的().A.快速排序B.堆排序C.希尔排序D.直接插入排序9、长度为11的哈希表中已经填有关键字17，

7、60，29的记录，采用二次探测再散列方法解决冲突，则填入关键字38其地址应该为()（哈希函数为h(key)=keymod11）A.4B.5C.3D.610、在一个无向图中,所有顶点的度数之和等于所有边数的()倍.A.3B.2C.1D.1/2四、程序填空题(共10分)1、已知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。(本题6分=2+2+2)voidMergeList(ListLa，ListLb，List&Lc){InitList(Lc);i=1;j=1

8、;k=0;La_len=ListLength(La);(1)while((i<=La_len)&&(j<=Lb_len)){GetElem(La，i，ai);(2)if(ai<=