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

蜗牛在线更多免费学习资料等待您的光临！ 2009—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-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．235 5．若具有n 个顶点e 条边且不带权的无向图采用邻接矩阵存储，则邻接矩阵中零 元素的数目是。 A．n+e B．2(n+e) C．n2+2e D．n2-2e 6．对于无向图G1=(V1,E1)和G2=(V2,E2)，若G2是G1的生成树，则下面的说法中， 错误的是。 A．G2是G1的连通分量 B．G2是G1的子图 C．G2是G1的极小连通子图，且V1=V2 D．G2是G1的一个无环子图 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．二路归并排序法 2 10．根据(大顶)堆积的定义，序列(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个 域，其中有1个数据域，m个__________指 有何利弊？ 3．一般情况下，对一个图进行遍历可以得到不同的遍历序列。若图采用邻接表存 储结构，导致遍历序列不惟一的主要因素有哪些？ 4．若选择当前参加排序的第1 个元素作为分界元素，什么情况下，快速排序法的 时间效率会退化到简单排序法的程度？请说明理由。 三、综合题（本题共20分，每小题各5分） 1．若已知在长度为n的顺序表(a1,a2,…,an)的第i个位置(1≤i≤n+1)插入一个新的数 据元素的概率pi= ( 1) 2( 1) ? ??? n n n i ，则平均插入一个元素时所需要移动元素次数的期望值(平 均次数)是多少？ 2．已知有向图采用邻接表存储，邻接表 如图3-2所示。请分别写出其所有可能的拓扑 序列。 图3-2 3．已知对一棵二叉排序树进行前序遍历得到的遍历序列为50,45,35,15,40,46,65,75,70， 请画出该二叉排序树。 4．请画出在图3-4所示的3阶B-树中依次插入关键字值55和69以后B-树的状态。 图3-4 0 A 1 B 2 C 3 D 4 E 5 F 1 3 2 4 4 1 2 5 4 ^ ^ ^ ^ ^ ^ 40 70 85 60 20 50 65 68 80 90 3 四、算法设计题（本题20分） 已知线性链表第1个结点的指针为list，链结点构造为data link ，请写一算法， 该算法用尽可能高的时间效率找到链表的倒数第k个结点。若找到这样的结点，算法给 出该结点的地址，否则，算法给出NULL。 限制：算法中不得求出链表长度，也不允许使用除指针变量和控制变量以外的其他 辅助空间。 要求： 1．用文字简要给出算法的基本思想；（5 分） 2．根据算法的基本思想写出相应算法。（15分） 五