数据结构试卷期末试卷(2007年06级C)(信息)

1数据结构试题（C卷）学号：姓名：评分：.一．单项选择题(30分)1.对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用_______次序的遍历实现编号。a．先序b．中序c．后序d．从根开始的层次遍历2.在有n个叶子结点的哈夫曼树中，其结点总数为_________。a.不确定b.2nc.2n+1d.2n-13.任何一个无向连通图的最小生成树_______。a.只有一棵b.有一棵或多棵c.一定有多棵d.可能不存在4.将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为_________。a.98b.99c.50d.485.下列排序算法中，______算法可能会出现下面情况：初始数据有序时，花费的时间反而最多。a．堆排序b．冒泡排序c．快速排序d．SHELL排序6.下图为AOV网，其可能的拓扑有序序列为________。a.CAEBDF;b.CABFED;c.CABEDFd.CEABFD7.将上图看作无向图，其从C出发的广度优先遍历结果为_______：a.CABDEFb.CDFEBAc.CDEAFBd.CABFED8.一个二叉树按顺序方式存储在一个维数组中，如图01234567891011121314ABCDEFGHIJ则结点E在二叉树的第层。a、1b、2c、3d、49.下列序列中，_______是执行第一趟快速排序后得到的序列(排序的关键字类型是字符串)。a.[da，ax，eb，de，bb]ff[ha，gc]b.[cd，eb，ax，da]ff[ha，gc，bb]c.[gc，ax，eb，cd，bb]ff[da，ha]d.[ax，bb，cd，da]ff[eb，gc，ha]ADEFCB210.二分查找法要求查找表中各元素的键值必须是________排列。a.递增或递减b.递增c.递减d.无序二．填空作图简答题（共70分）：1.如下图已知哈希表为空，哈希函数为H（Key）=KeyMOD11,冲突解决方法分别用线性探测再散列和二次探测再散列。填入在依次插入关键字14，37，25，16之后的情况，并求等概率情况下查找不成功时的平均查找长度。（1）线性探测再散列012345678910（2）二次探测再散列0123456789102.已知图G的邻接表如下，画出图G的所有连通分量。33.已知一字符串bbcbdebcecbcab，试设计赫夫曼编码并画出相应的赫夫曼树。4.用堆排序算法(“大顶堆”排序算法)对关键字进行排序，请先建“大顶堆”，然后输出一个堆顶元素,再调整成堆：初始状态{40，33，24，67，46，79，30，70}所建大顶堆{}输出一个堆顶元素调整后{}5.用快速排序（取第一个元素作为枢轴或支点）对下列关键字进行排序（图示）7033796746243040写出两趟排序的结果。一次划分之后:;分别进行快速排序分别再一次划分之后:.6.对下面的3阶B树依次插入关键码60，14，6，画出插入三个关键码后并删除关键码20后的结果（每一步的结果）。201040121630502847.设初始归并段为(10,15,31,∞),(9,20,∞),(22,34,37,∞),(6,15,42,∞),(12,37,∞),(84,95,∞),试利用败者树进行6路归并，画出选出最小的2个关键码的过程。5数据结构期末试题答案数据结构期末试题答案一、单选题：判断下列各小题叙述的正误。对，在题号前的括号内填入“√”；错，在题号前的括号内填入“×”。（每小题3分，共24分）(1)向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。A8B63.5C63D7(2)设有一个二元数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，则A[4][5]在（）位置，(10)表明用10进数表示。A692(10)B626(10)C709(10)D724(10)(3)一个有顺序表有255个对象，采用顺序搜索法查表，平均搜索长度为（）A128B127C126D255(4)含5个节点(元素值均不相同)的二叉搜索树有（）种A54B42C36D65(5)在分析折半搜索的性能时常加入失败结点，即外结点，从而形成扩充的二叉树。若设失败结点i所在层为l，那么搜索失败到达失败结点时所做的数据比较次数是（）。Ali+1Bli+2Cli-1Dli(6)设有一个含200个表项的散列表，用线性探查法解决冲突，按关键码查询时找到一个表项的平均探查次数不超过1.5，则散列存储空间应能够至少容纳（）个表项。（搜索成功的平均搜索长度为Snl=(1+1/(1-a))/2,其中a为装填因子A400B526C624D676(7)n个顶点的连通图至少有（）条边An-1BnCn+1D0(8)一个二叉树按顺序方式存储在一个一维数组中，如图则结点E在二叉树的第（）层。A1B2C3D4二、阅读理解题：说明下面递归过程的功能（10分）intunknown(BinTreeNode*t){//指针t是二叉树的跟指针。if(t==NULL)return0;elseif(t->leftChild==NULL&&t->rightChild==NULL)return1;elsereturnunknown(t->leftChild)+unknown(t->rightChild);}三、简答题（每小题12分，共36分）1.如下所示的连通图，请画出（1）以顶点为根的深度优先生成树；（6分）（2）如果有关节点，请找出所有的关节点。（6分）62、设有13个初始归并段，其长度分别为28，16，37，42，5，9，13，14，20，17，30，12，18。试画出4路归并时的最佳归并树，并计算它的带权路径长度WPL。3、设散列表HT[0..12]，即表的大小为m=13。采用双散列法解决冲突。散列函数和再散列函数分别为：H0(key)=key%13;注：%是求余数运算(=mod)Hi=(hi-1+REV(key+1)%11+1)%13;i=1,2,3,...,m-1其中，函数REV(x)表示颠倒10进制数x的各位，如REV(37)=73REV(7)=7等。若插入的关键码序列为{2，8，31，20，19，18，53，27}。试画出插入这8个关键码后的散列表。四、（10分）已知一棵二叉树如下，请分别写出按前序、中序、后序和层次遍历时得到的结点序列。五、综合算法题（10）分有一种简单的排序算法，叫做记数排序(countSorting)。这种排序算法对一个待排序的表(用数组表示)进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键码互不相同。记数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键码比该记录的关键码小。假设针对某一个记录，统计出的记数值为c，那么，这个记录在新的有序表中的合适的存放位置即为c。(1)给出适用于记数排序的数据表定义；(4分)(2)使用C++语言编写实现记数排序的算法；(4分)(3)对于有n个记录的表，关键码比较次数是多少？(2分)六、程序填空题(10分)下面给出的是一个在二叉树中查找值为x的结点，并打印该结点所有祖先结点的算法。在此算法中，假设值为x的结点不多于一个。此算法采用后序的非递归遍历形式。因退栈时需要区分其左、右子树是否已经遍历，故在结点进栈时附带有一个标志，=0，进入左子树，=1，进入右子树。用栈ST保存结点指针ptr以及标志tag。top是栈顶指针。voidprint(BintreeNode*t;Type&x){stackST;inti,top;top=0;//置空栈while(t!=NULL&&t->data!=xlltop!=0){while(t!=NULL&&t->data!=x){//寻找值为x的结点1____________;7ST[top].ptr=t;//进栈ST[top].tag=0;2_____________;}if(t!=NULL&&t->data==x)//找到值为x的结点for(i=1;3_______________;i++)cout<<ST.ptr->data<<endl;else{while(top>0&&ST[top].tag==1)//未找到值为x的结点top--;if(top>0){ST[top].tag=1;//转向右子树4__________________;}}}}/*print*/(1)请将缺失的语句补上(共4分，每空1分)(2)请给出对于右图所示的二叉树，使用上述算法搜索值为9的结点和值为10的结点的结果，以及在栈ST中的变化。(top是栈顶指针)(6分)引用:试题答案试题一、(1)B(2)C(3)A(4)B(5)D(6)A(7)A(8)B二、计算二叉树的叶结点个数。三、1.(1)该连通图从出发做深度优先搜索，得到的深度优先生成树为：(2)关节点为2.因为(13-1)%(4-1)=12%3=0，所以不需要添加空段。最佳归并树为WPS=(5+9+13+12+16+14+17+18+28+37+20+30)*2+42=4803.散列表HT[0..12]，散列函数与再散列函数为H0(key)=keymod13;Hi=(Hi-1+REV(key+1)mod11+1)mod13插入关键码序列为{2，8，31，20，19，18，53，27}H0(2)=2，比较次数为1H0(8)=8，比较次数为1H0(31)=5，比较次数为1H0(20)=7，比较次数为1H0(19)=6，比较次数为1H0(18)=5，冲突,H1=9，比较次数为28H0(53)=1，比较次数为1H0(27)=1，冲突,H1=7,冲突H2=0，比较次数为3插入8个关键码后的散列表四、前序：A，B，D，G，C，E，F，H中序：D，G，B，A，E，C，H，F后序：G，D，B，E，H，F，C，A层次：A，B，C，D，E，F，G，H五、(1)constintDefaultSize=100;template<classType>classdatalist;//数据表的前视声明template<classType>classElement{//数据表无元素类的定义private:Typekey;//关键码fieldotherdata;//其它数据成员public:TypegetKey(){returnkey;}//取当前结点的关键码voidsetKey(constTypex){key=x;}//将当前结点的关键码修改为x}template<classType>classdatalist{//用顺序表来存储待排序的元素，这些元素的类型是Typepublic:datalist(intMaxSz=DefaultSize):MaxSize(Maxsz),CurrentSize(0){Vector=newElement<Type>[MaxSz];}private:Element<Type>*Vector;//存储待排序元素的向量intMaxSize,CurrentSize;//最大元素个数与当前元素个数}(2)[解答1]template<classType>voidcountsort(datalist<Type>&initList,datalist<Type>&resultList){inti,,j,c;Typerefer;for(i=0;i<initList,CurrentSize;i++){c=0;refer:=initList.Vector.getKey();for(j=0;j<initList.CurrentSize;j