数据结构,期末考试试卷,复旦大学计算机科学技术学院-2012

第1页（装订线内不要答题）复旦大学计算机科学技术学院《数据结构》期末考试试卷（参考答案与评分标准）A卷共8页课程代码：COMP130004.01-03考试形式：□开卷■闭卷2012年1月（本试卷答卷时间为120分钟，答案必须写在试卷上，做在草稿纸上无效）专业学号姓名成绩题号一二三四总分得分一、填空题（25%,1~8题每题2分）1、设W为一个二维数组，其每个数据元素占用4个字节，行下标i从0到7，列下标j从0到3，则二维数组W的数据元素共占用个字节。若按行顺序存放二维数组W，其起始地址为100(10进制)，则二维数组元素W[6，3]的起始地址为（10进制表示）。答：128,208。2、后缀算式923+-102/-的值为__________。中缀算式（3+4X）-2Y/3对应的后缀算式为_______________________________。答：-1,34X*+2Y*3/-。3、由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为_________。答：714、在有序表（12，24，36，48，60，72，84）中二分查找关键字72时所需进行的关键字比较次数为。答：25、在含n个顶点和e条边的无向图（无自环、重边）的邻接矩阵中,零元素的个数为。答：n2-2e6、已知一棵完全二叉树中共有768结点，则该树中共有个叶子结点。答：3847、有向图的边集为{(a,c),(a,e),(e,b),(e,d),(b,d),(d,c),(c,f)}，该图的一个拓扑排序为：答：aebdcf8、当输入序列局部有序或元素个数较小时，在快速排序、选择排序、插入排序、归并排序、堆第2页排序中，最佳的排序方法是。答：插入排序9、假设两个队列共享一个循环向量空间（参见右图），其类型Queue2定义如下：typedefstruct{DateTypedata[MaxSize]；intfront[2],rear[2]；}Queue2；对于i=0或1，front[i]和rear[i]分别为第i个队列的头指针和尾指针。请对以下算法填空，实现第i个队列的入队操作。intEnQueue(Queue2*Q,inti,DateTypex){//若第i个队列不满，则元素x入队列，并返回1；否则返回0if(i0||i1)return0；if(Q－rear[i]==Q－front[])return0；Q－data[]=x；Q－rear[i]=[];return1；}答：(i＋1)%2(或1－i)；Q－rear[i]；(Q－rear[i]＋1)%Maxsize;（每空1分）10、以下是一个判断二叉树是否平衡的程序，对于平衡的二叉树，depth将会返回其高度（对于非平衡二叉树不要求返回）。请在空白处填上代码完成程序。（6分）boolisBalanced(BiTreeNode*pRoot,int&depth){if(pRoot==NULL){;return;}intleftDepth,rightDepth;if(){intdif=leftDepth–rightDepth;if(){depth=(1+leftDepth)(1+rightDepth)?1+leftDepth:1+rightDepth;return;}}returnfalse;第3页（装订线内不要答题）}答：depth=0（1分）true(1分)isBalanced(pRoot-left,leftDepth)&&isBalanced(pRoot-right,rightDepth)（2分）dif=-1&&dif=1（1分）true（1分）二、选择题（10%）1、对于双向循环链表，每个结点有两个指针域next和prior，分别指向前驱和后继。在p指针所指向的结点之后插入s指针所指结点的操作应为（）A.p-next=s;s-prior=p;p-next-prior=s;s-next=p-next;B.p-next=s;p-next-prior=s;s-prior=p;s-next=p-next;C.s-prior=p;s-next=p-next;p-next=s;p-next-prior=s;D.s-prior=p;s-next=p-next;p-next-prior=s;p-next=s;答：D。2、一个栈的输入序列为123，则下列序列中不可能是栈的输出序列的是()A.231B.321C.312D.123答：C。3、采用开放定址法处理散列表的冲突时，其平均查找长度（）。A．低于链接法处理冲突B.高于链接法处理冲突C．与链接法处理冲突相同D．高于二分查找答：B。4、假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有弧的时间复杂度是()A．O(n)B．O(e)C．O(n+e)D．O(n*e)答：C。5、设有6个结点的无向图，该图至少应有()条边才能确保是一个连通图。A.5B.6C.7D.8答：A三、问答题（40%）1、设一棵m叉树中有N1个度数为1的结点，N2个度数为2的结点，……，Nm个度数为m的结点，则该树中共有多少个叶子结点？（请写出求解过程）（5分）第4页答：度数为i的结点的孩子个数为iiN×。除了根结点，其他结点都是某结点的孩子，且父亲结点唯一。因此该树共有total=11miiiN=+×∑个结点。度数大于0的结点都是非叶子结点，因此内部结点个数inner=1miiN=∑。叶子结点个数leaf=total–inner=121(1)1(1)mmiiiiiNiN==+−×=+−×∑∑评分标准：总分5分，分析过程正确或者部分正确为1-5分，否则为0分。2、一个线性表为B=（12，23，45，57，20，03，78，31，15，36），设散列表为HT[0..12]，散列函数为H（key）=key%13并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。（5分）答：78150357452031233612查找成功的平均查找长度：ASLSUCC=14/10=1.4（散列表4分，查找成功的平均查找长度1分）3、已知二叉树的存储结构为二叉链表，阅读下面算法。typedefstructnode{DateTypedata；Structnode*next；}ListNode；typedefListNode*LinkList；LinkListLeafhead=NULL；VoidInorder(BinTreeT){LinkLists；If(T){Inorder(T－lchild)；If((!T－lchild)&&(!T－rchild)){0123456789101112第5页（装订线内不要答题）s=(ListNode*)malloc(sizeof(ListNode))；s－data=T－data；s－next=Leafhead；Leafhead=s；}Inorder(T－rchild);}}对于如下所示的二叉树（1）画出执行上述算法后所建立的结构；（4分）（2）说明该算法的功能。（2分）答：(1)LeafheadFHGD∧（2）中序遍历二叉树，按遍历序列中叶子结点数据域的值构建一个以Leafhead为头指针的逆序单链表（或按二叉树中叶子结点数据自右至左链接成一个链表）。4、一棵二叉树的先序序列为ABCDGEF，中序序列为CBDGAFE。请画出该二叉树并将其中序线索化，后将二叉树转换为相应的森林。（5分）答：(二叉树：1分)：(中序线索：2分)：ABECDFGNULLNULL(森林：2分)：第6页5、对于以下AVL树，依次插入关键码35、28、5。请画出每插入一个关键码之后AVL树的形状。（6分）805011020601040307090120100答：插入35（2分）：插入28（2分）：805011020601035307090120100408050110306020352870901201004010插入5（2分）：80301102050102835609012010040570第7页（装订线内不要答题）评分标准：总分6分，每次插入后的形状2分。6、已知一个连通图如下图所示，试给出图的邻接矩阵和邻接表存储示意图，若从顶点v1出发对该图进行遍历，分别给出一个按深度优先遍历和广度优先遍历的顶点序列.(8分)(1)图的邻接矩阵(1分)(2)邻接表存储示意图（1分）(3)从v1开始的深度优先遍历的顶点序列（2分）(4)分析在深度遍历过程中，分别使用邻接矩阵和邻接表存储的算法复杂度(2分)（6）讨论在图遍历问题中，这两种存储方式的优劣。（2分）答:(1)图的邻接矩阵(1分)001001001110110011010010011101101010(2)邻接表存储示意图（1分）（3）深度优先遍历的顶点序列:v1,v2,v3,v5,v4,v6(2分)(有多个答案)(4)深度优先邻接矩阵复杂度：O(n2)，n为顶点数；邻接表复杂度：O(n+e)，n为顶点数,e为边的条数。(2分)(5)在图的遍历算法中，遍历一个顶点的邻居，对于邻接矩阵，时间复杂度为O(n),而邻接表只需要该顶点的邻居数量复杂度；因此对于整个图的遍历，如深度优先、广度优先等，邻接矩阵需要O(n2)，而邻接表时间复杂度为O(n+e)，当图为稀疏图时，邻接表的时间复杂度优于邻接矩阵，而且存储开销也优于邻接矩阵；当图为密集图时，两者性能差不多；总的来说，邻接表的时间复杂度和空间存储开销都优于邻接矩阵。（2分）7、分析对比AVL树和Hash的时空特性，并讨论它们的适合场合。(6分)答：第8页时空特性：AVL树是高度平衡的二叉查找树，查找时间复杂度为O(logn)，Hash的查找时间复杂度为O(1)。存储开销Hash往往比AVL树小。适合场合：Hash必须处理冲突，而AVL树不存在这种问题。对于删除操作，AVL树的时间开销很稳定，为O(logn)，而Hash，如果采用拉链法处理冲突，则删除操作易于实现，如果采用开放定址法，则删除操作很难实现，因此开放定址法的Hash不适合更新频繁的数据存储。另外，AVL树对数据的存储是有序的，而Hash对数据的存储并不能反映数据之间的大小关系。因此，AVL树适用于有序的数据存储，而Hash适用于数据量比较大且分布比较均匀，对数据排序无要求的数据存储。四、算法题（25%，第一题要求写代码；后两题要求写伪代码或步骤清晰的解题思路）1、堆是一种很常用的数据结构，其中的一个重要用途是优先队列。以整数最小堆为例，写出优先队列（最小优先）的两个基本操作的代码：(10分)（1）入队，即插入一个元素到存放堆的数组的末尾，然后调整堆。（2）出队，即删除堆顶节点，然后调整堆。voidinsert(intk,inta[],intn){//假设新的元素k先被放在堆末尾位置a[n]单元中答：n++;intj=n-1;inti=(j-1)/2;while(j0){if(a[i]=k)break;a[j]=a[i];j=i;i=(i-1)/2;}a[j]=k;}intdeleteMin(inta[],intn){//假设在堆顶元素被删除之前，堆中共有n个元素答：a[0]=a[n-1];n--;inti=0;inttemp=a[i];while((j=2*i+1)n){if(jn-1&&a[j+1]a[j])j++;if(a[j]=temp)break;a[i]=a[j];i=j;第9页（装订线内不要答题）}a[i]=temp;}2、堆的另外一个常用场合是求topk问题。假设我们已经有一个n个元素的最小堆，如果用最直观的方法求最小的k个元素，其计算复杂度为O(klogn)。试问：如何在更小的复杂度内求topk问题？用伪代码描述你的方法，并给出复杂度证明。(7分)答：假设原最小堆为H，新建一个最小堆H’，H’初始化为空。将最小堆H的堆顶元素a插入H’；然后以下步骤执行