数据结构模拟试卷(8)

1数据结构模拟试卷（8）一、填空。1．算法的健壮性是指对于非法的输入也要能够给予正确的响应。2．对一个线性表分别进行遍历和逆置运算，其最好的时间复杂度分别为和O(n)O(n)。3．n个数入栈，所有可能的出栈序列共有种。4．下面程序段的时间复杂度为O()（n1）。sum=1;for(i=0;sumn;i++)sum+=i;5．若某二叉树有20个叶子节点，有30个节点仅有一个孩子，则该二叉树的总的节点数是20+30+19=69。6．若以{4，5，6，7，8}作为叶子节点的权值构造哈夫曼树，则该Huffman树的根结点权值为30。7．线索二叉树的左线索指向其前驱，右线索指向其后继。8．若含n个顶点的图形成一个环，则它的生成树可能有n种。9．对于具有300个记录的文件，采用分块索引查找法查找，其中用二分查找法查找索引表，用顺序查找法查找块内元素，假定每块长度均为30个元素，则平均查找长度为29/10+31/2=18.4。10．有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值为82的结点时，经4次比较后查找成功。二、设一组记录的关键字为{4，5，7，2，1，3，6}，请回答相关问题：（1）按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树，并求出在等概率情况下查找成功的平均查找长度。查找成功的平均查找长度18/7（2）按表中元素的顺序进行插入生成一棵AVL树，画出该树。并求出在等概率情况下查找成功的平均查找长度。2?查找成功的平均查找长度?17/7三、下图是一个四阶B树，请回答相关问题：（1）B+树和B树的主要区别是什么？（2）插入关键字87，画出插入调整后树的形状。B树：每个结点的关键字个数等于指针个数减1。B+树：每个结点的关键字个数等于指针个数。B+树中所有叶子结点包含了全部关键字信息,以及指向关键字记录的指针,叶子节点依关键字大小自小到大链接。非终端结点作索引,结点中含有其子树根结点的最大(最小)关键字。四、已知记录关键字集合为（53，17，19，61，98，75，79，63，46，49），要求散列到地址区间[0，10]中，散列函数选用除留余数法（mod11）。请回答相关问题：（1）画出形成的散列表（若产生冲突，用开放定址的线性探测再散列法解决）。01234567891075637946491761195398（2）计算在等概率情况下查找成功时的平均查找长度。18/10或1.8或9/5(2)在等概率情况下查找成功时的平均查找长度五、有7个顶点（v1,v2,v3,v4,v5,v6,v7）的有向图的邻接矩阵如右图。请回答相关问题：∞253∞∞∞∞∞2∞∞8∞∞∞∞135∞∞∞∞∞5∞∞∞∞∞∞∞39∞∞∞∞∞∞5∞∞∞∞∞∞∞3（1）画出该有向图（2）画出邻接表（3）写出从v1出发的深度优先遍历和广度优先遍历序列（4分）深度dfsv1v4v5v7v6v3v2广度bfsv1v4v3v2v5v6?v7（4）将图看成AOE网，画出关键活动及相应的有向边，写出关键路径的长度关键路径的长度为20六、设计算法。1．已知一棵树T用二叉树表示，其结点形式如下，试编写一算法求树T中各结点的度数。（1）写出相应的结构定义。（2）编写算法。leftdatarightdegree42．判断有向图是否存在回路。若存在返回1，否则返回0。（1）写出相应的结构定义。（2）编写算法。七、阅读下列函数，回答相关问题：intarrange(inta[],int1,inth,intx){//1和h分别为数据区的下界和上界inti,j,t；i=1；j=h；while(ij){while(ij&&a[j]=x)j--；while(ij&&a[i]x)i++；if(ij){t=a[j]；a[j]=a[i]；a[i]=t；}}if(a[i]x)returni；elsereturni－1；}（1）写出该函数的功能调整整数数组a[]中的元素并返回分界值I,使得所有小于x的元素落在a[1…i]上,大于等于x的元素落在a[I+1…h]上（2）写一个调用上述函数实现下列功能的算法：对一整型数组b[n]中的元素进行重新排列，将所有负数均调整到数组的低下标端，将所有正数均调整到数组的高下标端，若有零值，则置于两者之间，并返回数组中零元素的个数。intf(intb[],intn){intp,q;5p=arrange(b,0,n-1,0);q=arrange(b,p+1,n-1,1);returnq-p;}八、数组a存储了N个整数，请回答相关问题：（1）请完善对数组a进行堆排序的程序。voidHeapAdjust（inta[],inth,ints）{rc=a[h];for（j=2*h;j=s;j*=2）{if（（js）&&（a[j]a[j+1]））++j;if（!（rc=a[j]））break;a[h]=a[j];h=j;}a[h]=rc;}voidHeapSort（inta[],intn）//对a[1]，a[2]，…，a[n]进行堆排序//{for（i=n/2;i0;--i）HeapAdjust（a,i,n）;for（i=n;i1;--i）{t=a[1];a[1]=a[i];a[i]=t;HeapAdjust(a,1,I-1);}}（2）上面程序建成的堆是大顶堆还是小顶堆？（3）对n个元素进行初始建堆的过程中，最多进行n-1次数据比较。（4）堆排序稳定吗？请举例说明。不稳定