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

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

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

3、1)和G2=(V2,E2),若G2是G1的生成树，则下面的说法中， 错误的是。A. G2是Gi的连通分量 B. G2是Gi的子图C. G2是Gi的极小连通子图，且 Vi=V2D. G2是Gi的一个无环子图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)是采

4、用下列排序方法之一得到的第2趟排序后的结果，则该排序方法只能是。A.泡排序法 B .插入排序法C.选择排序法 D.二路归并排序法210 .根据(大顶)堆积的定义，序列(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、每小题各5分)1 .相对于线性表的顺序存储结构而言，线性表的链式存储结构有什么优点？2 .若度为m且有n个结点的树采用多重链表存储结构，即每个链结点设置m+1个域，其中有1个数据域，m个 指针域，则该链表中空指针的数目是多少？这种有何利弊？3 . 一般情况下，对一个图进行遍历可以得到不同的遍历序列。若图采用邻接表存 储结构，导致遍历序列不惟一的主要因素有哪些？4 .若选择当前参加排序的第1个元素作为分界元素，什么情况下，快速排序法的 时间效率会退化到简单排序法的程度？请说明理由。三、综合题(本题共20分，每小题各5分)1.若已知在长度为n的顺序表(a1,a2, ,an)的第i个位置(1 &am

6、p; i& n+1)插入一个新的数 据元素的概率pi =(1)2( 1) +n n n i,则平均插入一个元素时所需要移动元素次数的期望值(平均次数)是多少？2 .已知有向图采用邻接表存储，邻接表如图3-2所示。请分别写出其所有可能的拓扑 序列。图3-23 .已知对一棵二叉排序树进行前序遍历得到的遍历序列为50,45,35,15,40,46,65,75,70,请画出该二叉排序树。4 .请画出在图3-4所示的3阶B-树中依次插入关键字值55和69以后B-树的状态。图3-40 A1 B2 C3 D4 E5 F1 32 441 2 540 70 85 6020 50 65 68 80 903

7、四、算法设计题（本题20分）已知线性链表第1个结点的指针为list,链结点构造为data link ,请写一算法，该算法用尽可能高的时间效率找到链表的倒数第k个结点。若找到这样的结点，算法给出该结点的地址，否则，算法给出NULL。限制：算法中不得求出链表长度，也不允许使用除指针变量和控制变量以外的其他辅助空间。要求：1 .用文字简要给出算法的基本思想；（5分）2 .根据算法的基本思想写出相应算法。（15分）五、算法设计题（本题20分）已知哈夫曼树采用二叉链表存储结构，链结点构造为lchild data rchild ,其中，叶结点的data域中存放该叶结点对应的权值。请写出计算根结点指针为T的

8、哈夫曼树带权路径长度（WPL）的非递归算法。要求：1 .用文字简要给出算法的基本思想；（5分）2 .根据算法的基本思想写出相应算法。（15分） 一、选择题1. B 2. C 3. C 4. A 5. D6. A 7, C 8. C 9. B 10. D二、简答题1 .答：相对于线性表的顺序存储结构而言，线性表的链式存储结构的优点在于：首先，在表中进行插入和删除操作不需要移动其他元素，当指针指向合适结点后只需修改指针就能达到目的；其次，不需要预先分配存储空间，而是根据实际需要进行空间的动态申请，可使得存储空间得到充分利用；其三，由于表的容量仅受到可用空间的限制，表的容量扩充相对比较容易。2 .答

9、：整个链表一共有n Mm个指针域，由于除根结点外，每一个结点都有一个指针指 向它，故链表中空的指针域数目为nxm-（n-1）= n x（m-1）+1个。采用这种存储结构的优点是结构统一，便于操作，缺点是空的指针域较多，造成存储效 率低。3 .答：（1）开始遍历的顶点的不同；（2）存储结构的不同，即邻接表中边结点链接的次序不同；（3）使用的遍历方法的不同。4.答：在待排序的原始序列中元素已经按值从小到大排好序的情况下，快速排序法的 时间效率会变得很差，因为在排序过程中，每次选取的“分界元素”都是当前序列的最小值 （最前那个元素），经过一趟排序后，将原序列分解成为一个空序列和一个原序列长度仅减1的

10、子序列，这样，对于长度为 n的原始序列，必须经过 n-1趟排序才能把所有元素定位，而 且第i趟排序需要经过n-1次元素之间的比较才能为第i个元素定位，因此，总的排序时间 达到O（n2）。三、综合题1 二-1(1)npi n i =1 1)2+111 1)nn i 2=2 1)3n n 6n(n 1)(2n 1)42n 15 .拓扑序列：(1) ADFBCE(2) ADBCFE(3) ADBFCE3.二叉排序树4. 3阶B-树四、算法设计题(1)算法的基本思想： 设置一个指针变量p (初始时指向链表的第1个结点)，然后让其后移指向链表的第k个结点(不是倒数第k个结点)；再设置另外一个指针变量r,

11、初始时也指向链表的第1个结点； 利用一个循环让p与r同步沿链表向后移动；当 p指向链表最后那个结点时，r指向链表的倒数第k个结点。显然，算法的时间开销主要在第步和第步。若用 n表示链表中链结点的个数，对于任意k (iwkwn),第步要执行k-1、次,第步要执行n-k次，两个部分总计执行 n-1、次, 因此，算法的时间复杂度为0(n)。(2)算法：LinkList SEARCHNODE(LinkList list,int k)(LinkList p,r;int i;if(list!=NULL&& k>0)p=list;for(i=1;i<k;i+)/*循环结束时，p指

12、向链表的第k个结点*/p=p->link;if(p=NULL)printf("链表中不存在倒数第k个结点！")return NULL;r=list;while(p ->link!=NULL)p=p->link;r=r->link;/*循环结束时，p指向链表最后那个结点，r指向倒数第k个结点*/return r; /*给出链表倒数第k个结点(r指向的那个结点)的地址*/5045 6535 46707515 40ABD FEC60 7050 5540 68 8520 65 69 80 905五、算法设计题(1)算法的基本思想：本题宜采用二叉树的后序遍历的

13、非递归算法完成。在遍历过程中，访问一个叶结点时，将该叶结点的数据域值(该叶结点的权值)与该叶结点的路径长度(即当前栈顶指针值加1)相乘，并进行WPL值的累加。遍历结束时便求的该哈夫曼树的WPL。(2)算法：#define MaxNum 50 /* 定义二叉树中结点最大数目*/int POSTORDER_WPL(BTREE T) (/* T为二叉树根结点所在链结点的地址 */BTREE STACK1MaxNum,p=T;int STACK2MaxNum,flag,top= -1;WPL=0;if(T!=NULL)dowhile(p!=NULL)STACK1+top尸p;/*当前p指结点的地址进栈*/STACK2top=0;/* 标志 0 进栈*/ p=p Alchild;/* 将p移到其左孩子结点*/ p=STACK1top;flag=STACK2top -;/* 退栈*/if(flag=0)STACK1+top=p; /*当前p指结