河海大学《算法与数据结构》期末试题A卷

专业课复习资料（最新版）封面数据结构期末试卷(A)2008-2009____________姓名____________学号___________成绩_____________一、选择题：（10分，每题1分）1．算法的时间复杂度取决于（）A．问题的规模B.待处理数据的初态C.A和B2.除第一层外，满二叉树中每一层结点个数是上一层结点个数的（）A．2倍B．一半C．相同D．不能确定3．已知串S=‘aabb’,其Next数组值为（）A．0123B．0113C．0111D．01214.快速排序在最坏情况下的时间复杂度是（）A.O(n2log2n)B.O(n2)C.O(nlog2n)D.O(log2n)5．能进行折半查找的线性,必须以（）A．顺序方式存储,且元素按关键字有序B．链式方式存储,且元素按关键字有序C．顺序方式存储,且元素按关键字分块有序D.链式方式存储,且元素按关键字分块有序6.循环队列sq中，用数组elem［0...25］存放数据元素，sq.front指示队头元素的前一个位置，sq.rear指示队尾元素的当前位置，设当前sq.front为20，sq.rear为12，则当前队列中的元素个数为（）A.8B.16C.17D.187．含有10个结点的二叉树中，度为0的结点数为4，则度为2的结点数为（）A.3B.4C.5D.68．可以惟一地转化成一棵一般树的二叉树的特点是（）A.根结点无左孩子B.根结点无右孩子C.根结点有两个孩子9.排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是（）A.选择排序B.快速排序C.冒泡排序D.插入排序10.有n个结点的有向完全图的弧数是（）A.n2B.2nC.n(n-1)D.2n(n-1)二、填空题：（16分，每空2分）1.设二叉树中每个结点均用一个字母表示，若一个结点的左子树或右子树为空，用．表示，现前序遍历二叉树，访问的结点的序列为ABD.G...CE.H..F．．，则中序遍历二叉树时，访问的结点序列为___;后序遍历二叉树时，访问的结点序列为___。2.从有序表（12，18，30，43，56，78，82，95）中依次折半搜索元素82时，其搜索长度为_________.3.一个连通图的生成树是该图的连通子图。若这个连通图有n个顶点，则它的生成树有条边。4.用广义表的取表头head和取表尾tail的运算，从广义表LS=(b,c,(f),((d)))中分解出原子c的操作为_________。5.3阶B_树的根结点至少含有_________个关键字。6.假设以行优先顺序存储三维数组R[6][9][6]，其中元素R[0][0][0]的地址为2100，且每个元素占4个存储单元，则存储地址为2836的元素是_________.三、构造题（34分）1.给定一组数据{8，3，6，11，5，18}以它构造一棵哈夫曼树，并计算带权路径长度（4分）。2.对下边的无向加权图，按Prim算法求其最小生成树（从V1出发），并给出构造最小生成树过程中辅助数组的各分量值（6分）第2题图YClosedgeV2v3v4v5UV.-U输出adjVexLowcostadjVexLowcostadjVexLowcostadjVexLowcostadjVexLowcostadjVexLowcost3.对于下面的有向无环图，写出它的四个不同的拓扑有序序列。（4）4.设哈希(Hash)表的地址范围为0～18，哈希函数为：H(K)=KMOD17,K为关键字，用线性探测再散列法处理冲突，输入关键字序列:(10,24,32,17,31,35,46,47,42,63,59)造出哈希表，试回答下列问题：21743658v1v2v3v4v56153655(1)画出哈希表示意图；（5分）(2)若查找关键字63，需要依次与哪些关键字比较?（3分）(3)假定每个关键字的查找概率相等，求查找成功时的平均查找长度。（2分）(1)散列地址0123456789101112131415161718关键字比较次数(2)(3)5.设有一个关键码的输入序列{5，33，18，7，46，73，3，22，44，23}，从空树开始构造平衡二叉搜索树，画出每加入一个新结点时二叉树的形态。若发生不平衡，指明需做的平衡旋转的类型及平衡旋转的结果。(5分)6.给出一组关键字T=(12,2,16,30,8,28,4,10,20,6,18),写出用下列算法从小到大排序时第一趟结束时的序列（只写出最终的结果）；（1）希尔排序（第一趟排序的增量为5）（2分）（2）堆排序（3分）三、算法阅读（16分）1．读下面的算法，算法所实现的功能。（注：链表是递增有序的、带头节点的、非空的单链表，L是单链表的头指针）（6分）algothm(Linklist&L,inta,intb){p=L;while(p->next&&p->next->data<=a)p=p->next;if(p->next){q=p->next;while(q->data<b)q=q->next;p->next=q;}}2.算法填空：将二叉树bt中每一个结点的左右子树互换的算法如下，其中ADDQ(Q,bt),DELQ(Q),EMPTY(Q)分别为进队，出队和判别队列是否为空的函数，请填写算法中得空白处，完成其功能。（每空2分）typedefstructnode{intdata;structnode*lchild,*rchild;}btnode;voidEXCHANGE(btnode*bt){btnode*p,*q;if(bt){ADDQ(Q,bt);while(!EMPTY(Q)){p=DELQ(Q);q=___;p->rchild=___;___=q;if(p->lchild)___;if(p->rchild)__;}}}四、算法设计（24分）（一）定义一个单链表类，链表中结点的数据类型为整型，该类的基本操作包括：1.创建一个带头节点的递增有序的单链表2.把元素递增排列的链表A和B合并为C,且C中元素递减排列,使用原空间。（二）在一棵以二叉链表表示的二叉树上，试写出用按层次顺序遍历二叉树的方法，统计树中具有度为1的结点数目的算法。二叉链表中节点的类型定义为：typedefstructnode{intdata;structnode*lchild,*rchild;}btnode;