资源描述：
《数据结构2006软院期终考题A.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、软件学院2006级<<数据结构>>期终试题姓名学号12345678得分1．填充题（20分，每题5分）1)树的机内表示(实现)有、、。2）最小代价生成树有两种实现算法：Prim算法与Kruscal算法。两者分别适用于何种情况,。3）采用堆排序方法将初始序列{8,23,12,5,28}按从小到大顺序排序,则建立初始堆和排序过程中序列依次变化为、、、、。4)在具有6个结点的无向简单图中，边数最少为条时，才能确保该图一定是连通图。2．算法分析题（10分）利用大“O”记号将下列函数在最坏情况下运行时间表示为n的函数（要求给出推导过程）voidmystery(intn){for(inti
2、=1;i<=n-1;i++)for(intj=i+1;j<=n;j++)for(intk=1;k<=j;k++){SomestatementrequiringO(1)time}}答：3．（15分，每题5分）1）设有一字符串P=”3*y-a/y↑2”,试写出利用栈将P改为”3y*ay2↑/-”的操作步骤。（请用X代表扫描该字符串过程中顺序取一字符进栈的操作，用S代表从栈中取出一字符加入到新字符串尾的出栈操作。例如，要使”ABC”变为”BCA”，则操作步骤为XXSXSS）。答：2)设数组Q[m]表示一个环形队列（下标为0到m–1）,rear为队列中最后一个元素的实际位置，leng
3、th为队列中元素的个数,求队列中第一个元素的实际位置（要求写出计算公式）答：13)试说明一棵二叉树无论进行先序、中序或后序遍历，其叶结点的相对次序不发生改变。答:4．(10分)对下列无向图，按照Dijkstra算法,写出从顶点1到其它各个顶点的最短路径和最短路径长度。（顺序不能颠倒）1737511108652469答：5.（10分）设散列表长度为11,散列函数H(K)=(K的第一个字母在英文字母表中的序号，设A的序号为1)%11,若输入顺序为(B,D,M,CI,I,K,TM,X),处理冲突方法为线性探测法,要求：1)构造此散列表。2).对表中所有键值分别查找1次,求出总的比较
4、次数。答：6.（10分，每题5分）下列各图都是平衡二叉树，请按指定的关键码插入，分别画出插入后的平衡二叉树。1)15825插入567920365185022）MARAUGMAY插入FEB(按字母序)APRJANNOVDECJULY答：7.(10分)假一棵索引的二叉搜索，root指向其根点，中每个点具有如下形式：Lsizeleftdataright其中，Lsize域的点左子中的点个数加1；left,right分指向点的左、右子，且假data域int型。用java言写一个的findk函数，即搜索棵索引的二叉搜索中第K个小的关点。答：8.（15分）已知（k1,k2,k3,⋯,kn）
5、是一个最小堆，写一个函数将（k1,k2,k3,⋯,kn,kn+1）整最小堆。函数privatestaticvoidpercUp(Comparable[]a,intstart),其中start插入堆的位置。答：3
