《数据结构 教学课件 ppt 作者 周颜军 王玉茹 关伟洲 编著 习题选解与样例试卷》由会员分享，可在线阅读，更多相关《数据结构 教学课件 ppt 作者 周颜军 王玉茹 关伟洲 编著 习题选解与样例试卷（18页珍藏版）》请在金锄头文库上搜索。
1、 习题选解1设树中含有的分支结点的个数为n，与它对应的二叉树中其右子树为空的结点数为m，试求出两者之间的关系式，并证明之。 解：两者之间的关系式为：m = n + 1。 证明：因为树中含有的分支结点的个数为n，而树中每个分支结点都对应着一个“最右边”(即最后一个)的子女，这样的子女个数为n，显然这样的结点在对应的二叉树中其右子树必为空(因为在树中它没有右邻的兄弟)。另外，树的根在其对应的二叉树中仍为根，它也没有右子树。因此，树对应的二叉树中其右子树为空的结点数应该比该树中含有的分支结点的个数多一个。即：m = n + 1。 证毕2设T是具有n个内部结点的扩充二叉排序树，I是它的内部路径长度，E
2、是它的外部路径长度；S n为查找成功的平均查找长度，U n为查找失败的平均查找长度。试证明：S n = (1+1/n）U n -1，n 1。证明：因为查找成功的平均查找长度S n 与查找失败的平均查找长度U n 分别为： （1） （2）其中li 是第i个内部结点的层数； li 是第i个外部结点的层数。已知扩充二叉排序树的内部路径长度I与外部路径长度E的关系为：（3）因此，将式 (1)、式(2)、式(3) 联立，可推得：证毕3以下命题是否为真？若真请证明之。一棵二叉树的所有叶结点，在前序序列、对称序序列以及后序序列中都按相同的相对位置出现。答：命题为真。证明：（数学归纳法）当叶结点个数 = 2时
3、，总可以找到某个度为2的结点x，它的左子树L上有一个叶结点l，右子树R上有一个叶结点r。 无论按三种次序的哪一种次序遍历，都是先遍历x的左子树L，后遍历x的右子树R。所以得到的结点的线性序列均有l在r之前，即叶结点按相同的相对位置出现。具体描述如下：前序序列：root x l r中序序列： l x r 后序序列： l r x root假设叶结点个数 m ( m2 )时，结论成立。往证叶结点个数 = m 时，结论亦成立。我们总可以从根开始，沿链向下层搜索，找到第一次遇到的度为2的结点x，并把此二叉树分为三部分：x的左子树L、x的右子树R及 root x 。因为无论是在x的左子树L中还是在x的右子
4、树R中，叶结点的个数显然小于m，因此，由归纳假设可知，在三种次序下L与R中的叶结点均以相同的相对位置出现。具体描述如下：因此有：结点的前序序列为：root x L前R前 (其中 L前表示前序遍历 L 的结点序列，其他类同。)结点的中序序列为： L中 x R中 结点的后序序列为：L后R后 x root因为三种次序都是将右子树R遍历的结点序列排在(连接在)左子树L遍历的结点序列之后，所以，在三种次序下叶结点出现的相对位置是相同的。即在三种次序下叶结点均以相同的相对位置出现。 证毕4证明：快速排序的平均时间代价为O( nlog2n )。证明：(方法一：数学归纳法)设Tavg(n)为n记录排序所需的平
5、均时间。调用算法quicksort ( R, 1, n )后，R1 得到一个位置j , 这样下次就分别对大小为j-1和 n-j的两部分进行排序，其平均时间为：Tavg ( j-1) + Tavg ( n-j )，其余部分是为了安排一个记录到正确位置而交换项的时间为c n 。由于j取1到n的任一值的概率相同，因此有：Tavg ( n ) c n + = c n + （式1） 假定Tavg ( 0 ) b与Tavg ( 1 ) b （b为某一常数），当k = 2( b + c )及n 2时，有Tavg ( n ) knln n 。 （式2）下面用数学归纳法证明此不等式：当n = 2时，此不等式（式
6、2）显然成立。因为从（式1）得：Tavg ( n ) 2 c + 2 c + 2 b = 2( b + c ) 1 )假设，对于所有的n 1，将( 式1 )n -( 式2 )( n-1)可得：n Tavg (n) - ( n-1)Tavg (n-1) = 2 c n c + 2 Tavg ( n-1 )整理后得：Tavg (n) = = = = ( 注: 从1 n的倒数之和称为调和级数，且有： ) 1.386 nlog2n = O( nlog2n ) ( 注: ln 2 = 0.6931 ) 证毕 样例试卷数据结构课程考试试卷总 分题号一二三四五核分人题分3020202010复查人得分第一部分
7、 选择题 （共30分）得分评卷人一、单选题（每小题2分，共30分）1若一个算法的时间复杂度用T(n)表示，其中n的含义是 ( )。A问题规模 B语句条数 C循环层数 D函数数量2具有线性结构的数据结构是 ( )。A树 B图 C栈和队列 D广义表3. 将长度为n的单链表连接在长度为m的单链表之后，其算法的时间复杂度为 ( )。AO( 1 ) BO( m ) CO( n ) DO( m + n )4. 在带头结点的双向链表中插入一个新结点，需要修改的指针域数量是 ( )。A2个 B3个 C4个 D6个5. 假设以数组A60 存放循环队列的元素，其头指针是front = 47，当前队列有50个元素，
8、则队列的尾指针为( )。A3 B37 C50 D976. 若栈采用链式存储结构，则下列说法中正确的是 ( )。A需要判断栈满且需要判断栈空B不需要判断栈满但需要判断栈空C需要判断栈满但不需要判断栈空D不需要判断栈满也不需要判断栈空7. 若串str = Software，其子串的数目是 ( )。A8个 B9个 C36个 D37个8. 设有一个10阶的下三角矩阵A，采用行优先压缩存储方式，a11为第一个元素，其存储地址为1000，每个元素占一个地址单元，则a85的地址为 ( )。A1012 B1017 C1032 D10399允许结点共享的广义表称为 ( )。A纯表 B线性表 C递归表 D再入表1
9、0下列数据结构中不属于二叉树的是 ( )。AB树 BAVL树 C二叉排序树 D哈夫曼树11对右下图所示的有向图给出了四种可能的拓扑序列，其中错误的是 ( )。A1 5 2 6 3 4 B1 5 6 2 3 4C5 1 6 3 4 2D5 1 2 6 4 312以V1为起始结点对右下图进行深度优先遍历，正确的遍历序列是 ( )。AV1 V2 V3 V4 V5 V6 V7 BV1 V2 V5 V4 V3 V7 V6CV1 V2 V3 V4 V7 V5 V6DV1 V2 V5 V6 V7 V3 V413下列排序算法中不稳定的是 ( )。A快速排序 B归并排序 C冒泡排序 D直接插入排序14设关键字序列为( 1, 3, 9, 12, 32, 41, 45, 62, 75, 77, 82, 95, 100 )，当采用折半查找方法查找值32时，查找成功需要的比较次数是( )。A2 B3 C4 D815采用ISAM组织文件的方式属于 ( )。A链组织
