《2010年算法与数据结构(I)期末试题与参考答案.doc》由会员分享，可在线阅读，更多相关《2010年算法与数据结构(I)期末试题与参考答案.doc（6页珍藏版）》请在金锄头文库上搜索。
1、蜗牛在线更多免费学习资料等待您的光临！20092010学年“算法与数据结构(I)”期末试题与参考答案一、单项选择题（本题共20分，每小题各2分）1一个完整算法应该具备的特性之一是有穷性，这里的有穷性是指。A算法必须写得简明扼要 B算法必须在有限的时间内能够结束C算法的每一步必须有清晰明确的含义 D算法的每一步必须具有可执行性2设非空单链表的结点构造为data link 。若已知q指结点是p指结点的的直接前驱，则在q和p之间插入s所指结点的过程是依次执行As-link=p-link; p-link=s; Bp-link=s-link; s-link=p;Cq-link=s; s-link=p;
2、Dp-link=s; s-link=q;3下列4种操作中，不是堆栈的基本操作的是。A判断堆栈是否为空 B删除栈顶元素C删除栈底元素 D将堆栈置为空栈4若完全二叉树的第6层有10个叶结点，则该完全二叉树结点总数最多是。A107 B108 C234 D2355若具有n 个顶点e 条边且不带权的无向图采用邻接矩阵存储，则邻接矩阵中零元素的数目是。An+e B2(n+e) Cn2+2e Dn2-2e6对于无向图G1=(V1,E1)和G2=(V2,E2)，若G2是G1的生成树，则下面的说法中，错误的是。AG2是G1的连通分量 BG2是G1的子图CG2是G1的极小连通子图，且V1=V2 DG2是G1的一个
3、无环子图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根据(大顶)堆积的定义，序列(shi,deng,an,wang,tang,bai,fang,l
4、iu)对应的堆积是。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个域，其中有1个数据域，m个_指针域，则该链表中空指针的数目是多少？这种存储结构有何利弊？3一般情况下，
5、对一个图进行遍历可以得到不同的遍历序列。若图采用邻接表存储结构，导致遍历序列不惟一的主要因素有哪些？4若选择当前参加排序的第1 个元素作为分界元素，什么情况下，快速排序法的时间效率会退化到简单排序法的程度？请说明理由。三、综合题（本题共20分，每小题各5分）1若已知在长度为n的顺序表(a1,a2,an)的第i个位置(1in+1)插入一个新的数据元素的概率pi=( 1)2( 1)+- +n nn i，则平均插入一个元素时所需要移动元素次数的期望值(平均次数)是多少？2已知有向图采用邻接表存储，邻接表如图3-2所示。请分别写出其所有可能的拓扑序列。图3-23已知对一棵二叉排序树进行前序遍历得到的遍
6、历序列为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 5440 70 856020 50 65 68 80 903四、算法设计题（本题20分）已知线性链表第1个结点的指针为list，链结点构造为data link ，请写一算法，该算法用尽可能高的时间效率找到链表的倒数第k个结点。若找到这样的结点，算法给出该结点的地址，否则，算法给出NULL。限制：算法中不得求出链表长度，也不允许使用除指针变量和控制变量以外的其他辅助空间。
7、要求：1用文字简要给出算法的基本思想；（5 分）2根据算法的基本思想写出相应算法。（15分）五、算法设计题（本题20分）已知哈夫曼树采用二叉链表存储结构，链结点构造为lchild data rchild ，其中，叶结点的data 域中存放该叶结点对应的权值。请写出计算根结点指针为T 的哈夫曼树带权路径长度(WPL)的非递归算法。要求：1用文字简要给出算法的基本思想；（5 分）2根据算法的基本思想写出相应算法。（15分）参考答案一、选择题1B 2C 3C 4A 5D6A 7C 8C 9B 10D二、简答题1答：相对于线性表的顺序存储结构而言，线性表的链式存储结构的优点在于：首先，在表中进行插入和
8、删除操作不需要移动其他元素，当指针指向合适结点后只需修改指针就能达到目的；其次，不需要预先分配存储空间，而是根据实际需要进行空间的动态申请，可使得存储空间得到充分利用；其三，由于表的容量仅受到可用空间的限制，表的容量扩充相对比较容易。2答：整个链表一共有nm个指针域，由于除根结点外，每一个结点都有一个指针指向它，故链表中空的指针域数目为nm-(n-1)= n(m-1)+1 个。采用这种存储结构的优点是结构统一，便于操作，缺点是空的指针域较多，造成存储效率低。3答：（1）开始遍历的顶点的不同；（2）存储结构的不同，即邻接表中边结点链接的次序不同；（3）使用的遍历方法的不同。4答：在待排序的原始序
9、列中元素已经按值从小到大排好序的情况下，快速排序法的时间效率会变得很差，因为在排序过程中，每次选取的“分界元素”都是当前序列的最小值(最前那个元素)，经过一趟排序后，将原序列分解成为一个空序列和一个原序列长度仅减1的子序列，这样，对于长度为n的原始序列，必须经过n-1 趟排序才能把所有元素定位，而且第i趟排序需要经过n-1 次元素之间的比较才能为第i个元素定位，因此，总的排序时间达到O(n2)。4三、综合题1 +=- +11( 1)nipi n i =( 1)2n n + +=- +11( 1)nin i 2=( 1)2n n + 6n(n +1)(2n +1)=32n +12拓扑序列：(1)
10、 ADFBCE(2) ADBCFE(3) ADBFCE3二叉排序树43阶B-树四、算法设计题（1）算法的基本思想： 设置一个指针变量p（初始时指向链表的第1 个结点），然后让其后移指向链表的第k个结点（不是倒数第k个结点）； 再设置另外一个指针变量 r，初始时也指向链表的第1 个结点； 利用一个循环让p 与r 同步沿链表向后移动；当p 指向链表最后那个结点时，r 指向链表的倒数第k个结点。显然，算法的时间开销主要在第步和第步。若用n 表示链表中链结点的个数，对于任意k（1kn），第步要执行k-1 次，第步要执行n-k次，两个部分总计执行n-1 次，因此，算法的时间复杂度为O(n)。（2）算法：
11、LinkList SEARCHNODE(LinkList list,int k)LinkList p,r;int i;if(list!=NULL& k0)p=list;for(i=1;ilink;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
12、68 8520 65 69 80 905五、算法设计题（1）算法的基本思想：本题宜采用二叉树的后序遍历的非递归算法完成。在遍历过程中，访问一个叶结点时，将该叶结点的数据域值(该叶结点的权值)与该叶结点的路径长度(即当前栈顶指针值加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!
13、=NULL)dowhile(p!=NULL)STACK1+top=p; /* 当前p指结点的地址进栈*/STACK2top=0; /* 标志0 进栈*/p=p-lchild; /* 将p移到其左孩子结点*/p=STACK1top;flag=STACK2top-; /* 退栈*/if(flag=0)STACK1+top=p; /* 当前p指结点的地址再次进栈*/STACK2top=1; /* 标志1 进栈*/p=p-rchild; /* 将p移到其右孩子结点*/elseif(p-lchild=NULL& p-rchild=NULL) /* p指结点为叶结点*/WPL=WPL+p-data*(top+1);p=NULL;while(!(p=NULL& top=-1)；returnWPL;
