资源描述：
《2010年算法与数据结构(i)期末试题与参考答案new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、蜗牛在线更多免费学习资料等待您的光临！2009—2010学年“算法与数据结构(I)”期末试题与参考答案一、单项选择题（本题共20分，每小题各2分）1．一个完整算法应该具备的特性之一是有穷性，这里的有穷性是指。A．算法必须写得简明扼要B．算法必须在有限的时间内能够结束C．算法的每一步必须有清晰明确的含义D．算法的每一步必须具有可执行性2．设非空单链表的结点构造为datalink。若已知q指结点是p指结点的的直接前驱，则在q和p之间插入s所指结点的过程是依次执行A．s->link=p->link;p->link=s;B．p->link
2、=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．107B．108C．234D．2355．若具有n个顶点e条边且不带权的无向图采用邻接矩阵存储，则邻接矩阵中零元素的数目是。A．n+eB．2(n+e)C．n2+2eD．n2-2e6．对于无向图G1=(V1,E1)和G2=(V
3、2,E2)，若G2是G1的生成树，则下面的说法中，错误的是。A．G2是G1的连通分量B．G2是G1的子图C．G2是G1的极小连通子图，且V1=V2D．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
4、,23,4,5)是采用下列排序方法之一得到的第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,
5、shi,bai,an,deng)二、简答题（本题共20分，每小题各5分）1．相对于线性表的顺序存储结构而言，线性表的链式存储结构有什么优点？2．若度为m且有n个结点的树采用多重链表存储结构，即每个链结点设置m+1个域，其中有1个数据域，m个__________指针域，则该链表中空指针的数目是多少？这种存储结构有何利弊？3．一般情况下，对一个图进行遍历可以得到不同的遍历序列。若图采用邻接表存储结构，导致遍历序列不惟一的主要因素有哪些？4．若选择当前参加排序的第1个元素作为分界元素，什么情况下，快速排序法的时间效率会退化到简单排序法的
6、程度？请说明理由。三、综合题（本题共20分，每小题各5分）1．若已知在长度为n的顺序表(a1,a2,…,an)的第i个位置(1≤i≤n+1)插入一个新的数据元素的概率pi=(1)2(1)+-+nnni，则平均插入一个元素时所需要移动元素次数的期望值(平均次数)是多少？2．已知有向图采用邻接表存储，邻接表如图3-2所示。请分别写出其所有可能的拓扑序列。图3-23．已知对一棵二叉排序树进行前序遍历得到的遍历序列为50,45,35,15,40,46,65,75,70，请画出该二叉排序树。4．请画出在图3-4所示的3阶B-树中依次插入关键
7、字值55和69以后B-树的状态。图3-40A1B2C3D4E5F132441254^^^^^^407085602050656880903四、算法设计题（本题20分）已知线性链表第1个结点的指针为list，链结点构造为datalink，请写一算法，该算法用尽可能高的时间效率找到链表的倒数第k个结点。若找到这样的结点，算法给出该结点的地址，否则，算法给出NULL。限制：算法中不得求出链表长度，也不允许使用除指针变量和控制变量以外的其他辅助空间。要求：1．用文字简要给出算法的基本思想；（5分）2．根据算法的基本思想写出相应算法。（15分
8、）五、算法设计题（本题20分）已知哈夫曼树采用二叉链表存储结构，链结点构造为lchilddatarchild，其中，叶结点的data域中存放该叶结点对应的权值。请写出计算根结点指针为T的哈夫曼树带权路径长度(WPL)的非递归算法。要求：1．用文字简
