2010年算法与数据结构(I)期末试题与参考答案

1、蜗牛在线更多免费学习资料等待您的光临！20092010学年“算法与数据结构(I)”期末试题与参考答案一、单项选择题(本题共20分，每小题各2分)1一个完整算法应该具备的特性之一是有穷性，这里的有穷性是指。A.算法必须写得简明扼要B.算法必须在有限的时间内能够结束C.算法的每一步必须有清晰明确的含义D.算法的每一步必须具有可执行性2设非空单链表的结点构造为datalink。若已知q指结点是p指结点的的直接前驱，则在q和p之间插入s所指结点的过程是依次执行As->link=p->link;p->link=s;Bp->link=s->link;s->link=p;

2、C.q->link=s;s->link=p;D.p->link=s;s->link=q;3下列4种操作中，不是堆栈的基本操作的是。A.判断堆栈是否为空B.删除栈顶元素C.删除栈底元素D.将堆栈置为空栈4.若完全二叉树的第6层有10个叶结点，则该完全二叉树结点总数最多是。A.107B.108C.234D.2355若具有n个顶点e条边且不带权的无向图采用邻接矩阵存储，则邻接矩阵中零元素的数目是。A.n+eB.2(n+e)C.n2+2eD.n2-2e6. 对于无向图G=(V,E)和G2=(V2,E2),若G2是G的生成树，贝I下面的说法中，错误的是。A.G2是G1的连通分量B

3、.G2是G1的子图C.G2是G1的极小连通子图，且V=V2D.G2是G的一个无环子图7. 在表长为9的有序表中进行折半查找，经过3次元素之间的比较以后查找成功的元素分别是。A.第2,4,7,9个元素B.第2,4,7,8个元素C.第1,3,6,8个元素D.第1,4,6,9个元素8. 评价一个“好”的散列函数的主要指标是。A.函数是否是一个解析式子B.函数的形式是否简单C.函数的取值是否均匀D.函数的计算是否快9. 若序列(11,12,13,7,8,9,23,4,5)是采用下列排序方法之一得到的第2趟排序后的结果，则该排序方法只能是。A.泡排序法B.插入排序法C.选择排序法D.二路归并排序法210

4、. 根据(大顶)堆积的定义，序列(shi,deng,an,wang,tang,bai,fang,liu)对应的堆积是。A.(tang,wang,fang,shi,deng,bai,an,liu)B.(tang,shi,fang,wang,deng,bai,an,liu)C.(wang,tang,fang,deng,shi,bai,an,liu)D.(wang,tang,fang,liu,shi,bai,an,deng)二、简答题(本题共20分，每小题各5分)1相对于线性表的顺序存储结构而言，线性表的链式存储结构有什么优点？2若度为m且有n个结点的树采用多重链表存储结构，即每个链结点设置m+1个

5、域，其中有1个数据域，m个指针域，则该链表中空指针的数目是多少？这种存储结构有何利弊？3一般情况下，对一个图进行遍历可以得到不同的遍历序列。若图采用邻接表存储结构，导致遍历序列不惟一的主要因素有哪些？4若选择当前参加排序的第1个元素作为分界元素，什么情况下，快速排序法的时间效率会退化到简单排序法的程度？请说明理由。三、综合题(本题共20分，每小题各5分)1若已知在长度为n的顺序表(a,a2,an)的第i个位置(1WiWn+1)插入一个新的数据元素的概率pi=(1)2(1)，nnni，则平均插入一个元素时所需要移动元素次数的期望值(平均次数)是多少？2已知有向图采用邻接表存储，邻接表如图3-2所

6、示。请分别写出其所有可能的拓扑序列。图3-23已知对一棵二叉排序树进行前序遍历得到的遍历序列为50,45,35,15,40,46,65,75,70,请画出该二叉排序树。4请画出在图3-4所示的3阶B-树中依次插入关键字值55和69以后B-树的状态。图3-40A1 B2 C3 D4 E5 F1 32 441254A407085602050656880903四、算法设计题（本题20分）已知线性链表第1个结点的指针为1ist，链结点构造为datalink，请写一算法，该算法用尽可能高的时间效率找到链表的倒数第k个结点。若找到这样的结点，算法给出该结点的地址，否则，算法给出NULL。限制：算法中不得求

7、出链表长度，也不允许使用除指针变量和控制变量以外的其他辅助空间。要求：1用文字简要给出算法的基本思想；（5分）2根据算法的基本思想写出相应算法。（15分）五、算法设计题（本题20分）已知哈夫曼树采用二叉链表存储结构，链结点构造为1childdatarchild，其中，叶结点的data域中存放该叶结点对应的权值。请写出计算根结点指针为T的哈夫曼树带权路径长度（WPL）的非递归算法。要求：1用文字简要给出算法的基本思想；（5分）2根据算法的基本思想写出相应算法。（15分）参考答案一、选择题1B2C3C4A5D6A7C8C9B10D二、简答题1答：相对于线性表的顺序存储结构而言，线性表的链式存储结构

8、的优点在于：首先，在表中进行插入和删除操作不需要移动其他元素，当指针指向合适结点后只需修改指针就能达到目的；其次，不需要预先分配存储空间，而是根据实际需要进行空间的动态申请，可使得存储空间得到充分利用；其三，由于表的容量仅受到可用空间的限制，表的容量扩充相对比较容易。2. 答：整个链表一共有nm个指针域，由于除根结点外，每一个结点都有一个指针指向它，故链表中空的指针域数目为nxm-（n-1）=nx（m-1）+1个。采用这种存储结构的优点是结构统一，便于操作，缺点是空的指针域较多，造成存储效率低。3. 答：（1）开始遍历的顶点的不同；（2）存储结构的不同，即邻接表中边结点链接的次序不同；（3）使

9、用的遍历方法的不同。4. 答：在待排序的原始序列中元素已经按值从小到大排好序的情况下，快速排序法的时间效率会变得很差，因为在排序过程中，每次选取的“分界元素”都是当前序列的最小值（最前那个元素），经过一趟排序后，将原序列分解成为一个空序列和一个原序列长度仅减1的子序列，这样，对于长度为n的原始序列，必须经过n-1趟排序才能把所有元素定位，而且第i趟排序需要经过n-1次元素之间的比较才能为第i个元素定位，因此，总的排序时间达到O（n2）。三、综合题1+11(1)nipini=(1)2nn+厶+11(1)nini2=(1)2nn+6n(n+l)(2n+1)32n+12拓扑序列：(1) ADFBCE

10、(2) ADBCFE(3) ADBFCE3.二叉排序树4.3阶B-树四、算法设计题(1)算法的基本思想： 设置一个指针变量p(初始时指向链表的第1个结点)，然后让其后移指向链表的第k个结点(不是倒数第k个结点)； 再设置另外一个指针变量r,初始时也指向链表的第1个结点； 利用一个循环让p与r同步沿链表向后移动；当p指向链表最后那个结点时，r指向链表的倒数第k个结点。显然，算法的时间开销主要在第步和第步。若用n表示链表中链结点的个数，对于任意k(lWkWn)，第步要执行k-1次，第步要执行n-k次，两个部分总计执行n-1次,因此，算法的时间复杂度为O(n)。(2)算法：LinkListSEARC

11、HNODE(LinkListlist,intk)LinkListp,r;inti;if(list!=NULL&&k>0)p=list;for(i=1;ivk;i+)/*循环结束时，p指向链表的第k个结点*/p=p->link;if(p=NULL)printf("链表中不存在倒数第k个结点！”)returnNULL;r=list;while(p->link!=NULL)p=p->link;r=r->link;/*循环结束时，p指向链表最后那个结点，r指向倒数第k个结点*/returnr;/*给出链表倒数第k个结点(r指向的那个结点)的地址*

12、/504565354670751540ABDFEC6070505540688520656980905五、算法设计题(1)算法的基本思想：本题宜采用二叉树的后序遍历的非递归算法完成。在遍历过程中，访问一个叶结点时，将该叶结点的数据域值(该叶结点的权值)与该叶结点的路径长度(即当前栈顶指针值加1)相乘，并进行WPL值的累加。遍历结束时便求的该哈夫曼树的WPL。(2)算法：#defineMaxNum50/*定义二叉树中结点最大数目*/intPOSTORDER_WPL(BTREET)/*T为二叉树根结点所在链结点的地址*/BTREESTACK1MaxNum,p=T;intSTACK2MaxNum,flag,top=1;WPL=0;if(T!=NULL)dowhile(p!=NULL)STACKl+top=p;/*当前p指结点的地址进栈*/STACK2top=0;/*标志0进栈*/p=p->lchild;/*将p移到其左孩子结点*/p=STACKltop;flag=STACK2top;/*退栈*/if(flag=0)STACK1+top=p;/*当前p指结