资源描述：
《数据结构试题A》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、2008-2009学年第2学期«数据结构》试题(卷)A课程代码BB002016考试方式闭卷考试时长100分钟姓名学号教学班号专业—级—班得分、选择题：(10分，每题1分)1.算法的时间复杂度取决于A.问题的规模B.待处理数据的初态C・A和B除第一层外，满二叉树中每一层结点个数是上一层结点个数的D.不能确定2.A.2倍B.一半C.相同已知串S二'aabb'，其Next数组值为A.0123B.0113C.0111快速排序在最坏情况下的时间复杂度是A.0(n2log2n)B.0(n2)C.0(nlog2n)能进行折半查找的线性表，必须以A.顺序方式存储，
2、且元素按关键字有序B.链式方式存储，且元素按关键字有序C.顺序方式存储，且元素按关键字分块有序D.链式方式存储，且元素按关键字分块有序6.循环队列sq中，用数组elem[0...25]存放数据元素，sq.front指示队头元素的前一个则当前队列(3.4.5.D.0121D.0(log2n)位置，sq・rear指示队尾元素的当前位置，设当前sq.front为20,sq.rear为12,中的元素个数为A.8B.16C.17D.187.含有10个结点的二叉树中，度为0的结点数为4,则度为2的结点数为A.3B.4C.5D.68.可以惟一地转化成一棵一般树的
3、二叉树的特点是A.根结点无左孩子B.根结点无右孩子C.根结点有两个孩子9•排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是A.选择排序B.快速排序C.冒泡排序D.插入排序10.有n个结点的有向完全图的弧数是A.n2B.2nC.n(n-l)D.2n(n-l)题号—・二三四五七八合计满分1016341624100得分阅卷人得分二、填空题：(16分，每空2分)1.设二叉树中每个结点均用一个字母表示，若一个结点的左子树或右子树为空，用・表示，现前序遍历二叉树，访问的结点的序列为ABD・G.・・CE.H・・F・・，»序遍历二叉树时，访问的结点序
4、列为；后序遍历二叉树时，访问的结点序列为o2.从有序表(12,18,30,43,56,78,82,95)中依次折半搜索元素82时，其搜索长度为・3.一个连通图的生成树是该图的连通子图。若这个连通图有n个顶点，则它的生成树有条边。4.用广义表的取表头head和取表尾ta订的运算，从广义表LS=(b,c,(f),((d)))中分解出原子c的操作为。5.3阶B_树的根结点至少含有个关键字。6.假设以行优先顺序存储三维数组R[6][9][6],其中元素R[0][0][0]的地址为2100,且每个元素占4个存储单元，则存储地址为2836的元素是.得分三、构造
5、题(34分)1.给定一组数据｛8,3,6,11,5,18｝以它构造一棵哈夫曼树，并计算带权路径长度(4分。1.对下边的无向加权图，按Prim算法求其最小生成树（从VI出发），并给出构造最小生成树过程中辅助数组的各分量值（6分）YClosedgeV2v3v4v5UV.-u输出adjVexLowcostadjVexLowcostadjVexLowcostadjVexLowcostadjVexLowcostadjVexLowcost2.对于下面的有向无环图，写出它的四个不同的拓扑有序序列。（4）1.设哈希(Hash)表的地址范围为0〜18,哈希函数为：H
6、(K)=KMOD17,K为关字，用线性探测再散列法处理冲突，输入关键字序列：(10,24,32,17,31,35,46,47,42,63,59)造出哈希表，试回答下列问题：(1)画出哈希表示意图；(5分)(2)若查找关键字63,需要依次与哪些关键字比较？(3分)(3)假定每个关键字的查找概率相等，求查找成功时的平均查找长度。(2分)⑴散列地址0123456789101112131415161718关键字比较次数⑵2.设有一个关键码的输入序列{5,33,18,7,46,73,3,22,44,23},从空树开始构造平衡二叉搜索树，画出每加入一个新结点时
7、二叉树的形态。若发生不平衡，指明需做的平衡旋转的类型及平衡旋转的结果。(5分)得分&(1)给出一组关键字T=(12,2,16,30,&2&4,10,20,6,18),写出用下列算法从小到大排序时第一趟结束时的序列(只写出最终的结果);希尔排序(第一趟排序的增量为5)(2)堆排序(3分)三、算法阅读(16分)(2分)读下面的算法，分析算法所实现的功能。(注：链表是递增有序的、带头节点的、非空的单链表，l是单链表的头指针)(6分)algothm(Linklist&L,inta,intb){P=L；while(p->next&&p->next->data
8、<=a)p=p->next;if(p->next){q=p->next;while(q->datanext
