资源描述：
《浙江林学院 2004---2005学年第一学期末考试卷(b)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、浙江林学院2004---2005学年第一学期末考试卷（B）课程名称：数据结构课程类别：必修考试形式：闭卷注意：本试卷一共五大题,都为必做题目,请认真读题，给出答案。一二三四五得分一、填空题(18分，每空1分)1、常见的存储结构有________、_________。2、a=“ABCDEFG”,b=“CDEF”.则串a的长度为____，串b在串a中的位置为____。3、向一个长度为n的有序单链表中插入一个元素时，为寻找插入位置需要平均比较____个元素。4、对于对称矩阵，我们可以为每一对对称元分配一个存储空间，于是，可以把n2个元压缩到_______个元
2、的空间中。5、广义表E=(a,E)的长度为______6、对于一棵具有30个结点二叉树，若一个结点的编号为8，则它的左孩子结点的编号为______，右孩子结点的编号为______，双亲的编号为______。7、在队列中，允许删除的一端为______，允许插入的一端为_______.8、利用MST性质来构造最小生成树的两种常用算法为_________和__________.9、使用折半查找时，时间复杂度为______。顺序查找时，时间复杂度为______。10、堆排序的时间复杂度为______，空间复杂度为______。二、判断(对的打∨,错误打×,10
3、×1分=10分)1、在数据元素的非空有限集中，存在唯一的一个被称为”前驱”的元素，但是不一定存在唯一的一个称为”后继”的元素()2、一般情况下，在第i(1<=i<=n)个元素之前插入一个元素，需要将第n个到第i个元素向后移动一个位置，移动元素的个数为n-i()3、由于链式存储结构要求逻辑上相邻的元素在物理位置上也相邻，因此，它不具有随机存取的优点()第6页共6页1、队列的基本特征是先进先出()2、带权的无向连通图的最小生成树是不唯一的。()3、n个结点的二叉链表中必定存在2n个空链域。()4、赫夫曼树是指带权路径长度WPL最小的二叉树。一般而言，在给定
4、条件下构造出的赫夫曼树是唯一的。()8、装载因子是散列表的一个重要参数，它反映了散列表的查找长度。（） 9、中序遍历二叉排序树不可能得到一个关键字有序的序列。()10、希尔排序中，增量d值的选择必须为一个素数，在最后一趟排序时应为1()二、选择题（10×2分=20分）1、线性链表不具有的特点().A.随机访问B.不必事先估计所需存储空间大小C.插入与删除时不必移动元素D.所需空间与线性表长度成正比2、向顺序栈中压入新元素时,应当().A.先移动栈顶指针,再存入元素B.先存入元素,再移动栈顶指针C.先后次序无关紧要D.同时进行3、具有63个结点的完全二叉
5、树的高度为().(根的层次号为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.左、右子树高度差的绝对值不超过1 C.左子树的高度均大于右子树的高度 D.左子树的高度均小于右子树的高度7
6、、一个对象序列的排序码为{46,79,56,38,40,84},采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为().A.{38,79,56,46,40,84}B.{38,46,79,56,40,84}C.{38,46,56,79,40,84}D.{40,38,46,56,79,84}第6页共6页8、对有14个数据元素的有序表R[14]进行折半搜索，搜索到R[3]的关键码等于给定值，此时元素比较顺序依次为（）。A．R[0]，R[13]，R[2]，R[3]B．R[0]，R[1]，R[2]，R[3]C．R[6]，R[4]，R[2]，R[3]D
7、．R[6]，R[2]，R[4]，R[3]9、长度为7的哈希表中已经填有关键字17，60，29的记录，采用二次探测再散列方法解决冲突，则填入关键字38其地址应该为()（哈希函数为h(key)=keymod7）A.4B.5C.3D.610、在一个无向图中,所有边数之和等于顶点的所有度数之和的()倍.A.3B.2C.1D.1/2四、程序填空题(共10分，每空2分)1、在带头结点的单链表L中的第i个位置前插入一个元素e,算法如下：(本题4分)StatusListInsert_L(Linklist&L，inti,ElemType){p=L;j=0;while(p
8、&&jnext;++j;}if(!p
9、
10、j>i-1)returnERRO
