数据结构期末试题答案1.如下所示的连通图，请画出2009-01-0908:17（1）以顶点为根的深度优先生成树；（6分）一、单选题：判断下列各小题叙述的正误。对，（2）如果有关节点，请找出所有的关节点。（6在题号前的括号内填入“√”；错，在题号前的括分）号内填入“×”。（每小题3分，共24分）(1)向一个有127个元素的顺序表中插入一个新元2、设有13个初始归并段，其长度分别为28，16，素并保持原来顺序不变，平均要移动（）个元素。37，42，5，9，13，14，20，17，30，12，18。试A8B63.5C63D7画出4路归并时的最佳归并树，并计算它的带权路(2)设有一个二元数组A[m][n]，假设A[0][0]存放径长度WPL。位置在644(10)，A[2][2]存放位置在676(10)，3、设散列表HT[0..12]，即表的大小为m=13。采每个元素占一个空间，则A[4][5]在（）位置，用双散列法解决冲突。散列函数和再散列函数分别(10)表明用10进数表示。为：A692(10)B626(10)C709(10)D724(10)H0(key)=key%13;注：%是求余数运算(=mod)(3)一个有顺序表有255个对象，采用顺序搜索法Hi=(hi-1+REV(key+1)%11+1)%13;查表，平均搜索长度为（）i=1,2,3,...,m-1A128B127C126D255其中，函数REV(x)表示颠倒10进制数x的各位，(4)含5个节点(元素值均不相同)的二叉搜索树有如REV(37)=73REV(7)=7等。若插入的关键码序列（）种为{2，8，31，20，19，18，53，27}。试画出插入A54B42C36D65这8个关键码后的散列表。(5)在分析折半搜索的性能时常加入失败结点，即四、（10分）外结点，从而形成扩充的二叉树。若设失败结点i已知一棵二叉树如下，请分别写出按前序、中序、所在层为l，那么搜索失败到达失败结点时所做的后序和层次遍历时得到的结点序列。数据比较次数是（）。五、综合算法题（10）分Ali+1Bli+2Cli-1Dli有一种简单的排序算法，叫做记数排序(count(6)设有一个含200个表项的散列表，用线性探查Sorting)。这种排序算法对一个待排序的表(用数法解决冲突，按关键码查询时找到一个表项的平均组表示)进行排序，并将排序结果存放到另一个新探查次数不超过1.5，则散列存储空间应能够至少的表中。必须注意的是，表中所有待排序的关键码容纳（）个表项。（搜索成功的平均搜索长度为互不相同。记数排序算法针对表中的每个记录，扫Snl=(1+1/(1-a))/2,其中a为装填因子描待排序的表一趟，统计表中有多少个记录的关键A400B526C624D676码比该记录的关键码小。假设针对某一个记录，统(7)n个顶点的连通图至少有（）条边计出的记数值为c，那么，这个记录在新的有序表An-1BnCn+1D0中的合适的存放位置即为c。(8)一个二叉树按顺序方式存储在一个一维数组(1)给出适用于记数排序的数据表定义；(4分)中，如图(2)使用C++语言编写实现记数排序的算法；(4分)(3)对于有n个记录的表，关键码比较次数是多则结点E在二叉树的第（）层。少？(2分)A1B2C3D4六、程序填空题(10分)二、阅读理解题：说明下面递归过程的功能（10下面给出的是一个在二叉树中查找值为x的结点，分）并打印该结点所有祖先结点的算法。在此算法中，intunknown(BinTreeNode*t){假设值为x的结点不多于一个。此算法采用后序的//指针t是二叉树的跟指针。非递归遍历形式。因退栈时需要区分其左、右子树if(t==NULL)return0;是否已经遍历，故在结点进栈时附带有一个标志，elseif=0，进入左子树，=1，进入右子树。用栈ST保存(t->leftChild==NULL&&t->right结点指针ptr以及标志tag。top是栈顶指针。Child==NULL)return1;voidprint(BintreeNode*t;Type&x){elsereturnunknownstackST;inti,top;(t->leftChild)+unknowntop=0;//置空栈(t->rightChild);while(t!=NULL&&t->data!=xll}top!=0){三、简答题（每小题12分，共36分）while(t!=NULL&&t->data!=x){//寻找值为x的结点插入8个关键码后的散列表1______