还剩6页未读,继续阅读
文本内容:
肂虿螈聿膅蒂蚄肈芇蚇薀肇荿蒀罿肆腿芃袅肅芁薈螁肄莃莁蚇肄肃薇薃肃膅荿袁膂芈薅螇膁莀莈蚃膀肀薃虿腿节莆羈膈莄蚁袄膈蒇蒄螀膇膆蚀蚆螃艿蒃薂袂莁蚈袀袂肁蒁螆袁膃蚆螂袀莅葿蚈衿蒇莂羇袈膇薇袃袇艿莀蝿袆莂薆蚅羆肁荿薁羅膄薄袀羄芆莇袆羃蒈蚂螂羂膈蒅蚈羁芀蚁薃羀莃蒃袂羀肂虿螈聿膅蒂蚄肈芇蚇薀肇荿蒀罿肆腿芃袅肅芁薈螁肄莃莁蚇肄肃薇薃肃膅荿袁膂芈薅螇膁莀莈蚃膀肀薃虿腿节莆羈膈莄蚁袄膈蒇蒄螀膇膆蚀蚆螃艿蒃薂袂莁蚈袀袂肁蒁螆袁膃蚆螂袀莅葿蚈衿蒇莂羇袈膇薇袃袇艿莀蝿袆莂薆蚅羆肁荿薁羅膄薄袀羄芆莇袆羃蒈蚂螂羂膈蒅蚈羁芀蚁薃羀莃蒃袂羀肂虿螈聿膅蒂蚄肈芇蚇薀肇荿蒀罿肆腿芃袅肅芁薈螁肄莃莁蚇肄肃薇薃肃膅荿袁膂芈薅螇膁莀莈蚃膀肀薃虿腿节莆羈膈莄蚁袄膈蒇蒄螀膇膆蚀蚆螃艿蒃薂袂莁蚈袀袂肁蒁螆袁膃蚆螂袀莅葿蚈衿蒇莂羇袈膇薇袃袇艿莀蝿袆莂薆蚅羆肁荿薁羅膄薄袀羄芆莇袆羃蒈蚂螂羂膈蒅蚈羁芀蚁薃羀莃蒃袂羀肂虿螈聿膅蒂蚄肈芇蚇薀肇荿蒀罿肆腿芃袅肅芁薈螁肄莃莁蚇肄肃薇薃肃膅荿袁《数据结构》试题(开卷)(电信系本科2002级2003年12月)题号一二三总分题分323830100得分
一、回答下列问题每题4分,共32分
1.对于一个有10000个结点的二叉树,树叶最多有多少个?最少有多少个?答最多是完全二叉树的形态,即5000个叶子;最少是单支树的形态,即1个叶子
2.已知一棵二叉树的中序序列和后序序列分别为DBGEACHF和DGEBHFCA,则该二叉树的前序序列是什么?答是ABDEGCFH
3.设有1000个无序的元素,需排出前10个最大(小)的元素,你认为采用哪种排序方法最快?为什么?答用锦标赛排序或堆排序很合适,因为不必等全部元素排完就能得到所需结果,时间效率为Onlog2n;即O(1000log21000)=O10000锦标赛排序的准确比较次数为n-1+9log2n=999+9log21000=999+9×10=1089堆排序的准确比较次数为n-1+9log2n=999+9log21000=999+9×10=1089若用冒泡排序也较快,最多耗费比较次数为(n-1+n-2+……+n-10)=10n-55=10000-55=9945(次)
4.在KMP算法中,已知模式串为ADABCADADA,请写出模式串的next[j]函数值答
01121123435.中序遍历的递归算法平均空间复杂度为多少?答要考虑递归时占用了栈空间,但递归次数最多不超过树的高度,所以空间复杂度为Olog2n
6.欲将无序序列(247913367096121036*4910027)中的关键码按升序重新排列,请写出快速排序第一趟排序的结果序列另外请画出堆排序(小根堆)的初始堆答
①快速排序第一趟排序的结果序列为10,12,13,
[24],70,96367936*4910027(注意要按振荡式逼近算法实现)
②堆排序的初始堆如下,注意要从排无序堆开始,从最后一个非终端结点开始,自下而上调整而且要排成小根堆!初始堆序列为10,24,12,79,49,27,13,36,36*7010096无序堆有序初始堆
7.已知一组关键字为(10,24,32,17,31,30,46,47,40,63,49),设哈希函数H(key)=keyMOD13请写出用线性探测法处理冲突构造所得的哈希表答
012345678910111249401731323046471024638.算法复杂度O
(1)的含义是什么?答它表示与输入的元素规模无关,是一个常数(但不一定是1)或它表示该算法执行时耗费时间的长短或占用辅助空间的多少与元素个数n无关,若能达到这样的时间效率或空间效率,将是最理想的算法
二、综合题(4小题,共38分)
1.下图为某无向图的邻接表,按教材算法
7.5和
7.6分别写出深度优先搜索和广度优先搜索的结果,并画出逻辑结构图10分A5^B37^C267^D^E1^F3^G23^H910^I8^J8^答深度优先搜索(DFS)结果为AEBCFGDHIJ广度优先搜索(BFS)结果为AEBCGFDHIJ这是有着4个连通分量的非连通图AEBCFGHIDJ
2.设A~H8个字符出现的概率为:={
0.
100.
160.
010.
020.
290.
100.
070.25}设计最优二进制码并计算平均码长如果设计最优三进制编码(即可用012三种符号进行编码),画出最优三叉树并计算平均码长10分答最优二进制编码不惟一,但WPL惟一对三进制编码,由于总共有8个字符,8%3=2故第一次构建最优树只有2个结点,则最优三叉树为
3.给定一个由n个关键字不同的记录构成的序列,你能否用2n-3次比较找出n个元素中的最大值和最小值?如果有,请描述你的方法最快需多少次比较?(无需写算法)8分答可以实现选用锦标赛算法两两元素比较,淘汰较小的,形如一棵二叉树树根为最大值(此时用掉n-1次比较?)而最小者一定位于首次被淘汰之列故只有n/2个一共需n-1+n/2次比较
4.分析下面算法中l和h变量表示什么含义?初始调用时,l和h应取什么值?其中p为指向二叉树的根结点,如果去掉形参中的“”符号,会得到什么结果?10分解依分析,l、h表示二叉树的层次数和深度l之前千万不能加符号,否则不通开始调用时,应为ABC(p00)去掉形参中的“”号,则上次计算的结果不能正确返回故h不变,得不到正确结果这里的inth应当理解为push形参,每次返回就要return实参所以l和h其实是每一层当前的状态L代表当前结点所在的层数(从根结点计算起);而h代表当前结点所在的深度附教材习题集?求深度的函数如下intBTreeDepthBtree*BT//*BT为二叉树某结点的指针{intleftdeprightdep;//设左右两个深度/层次计数器ifBT==NULLreturn0;//当前结点指针为空则立即返回else{leftdep=BTreeDepthBT-left;//遍历当前结点左子树rightdep=BTreeDepthBT-right;//遍历当前结点右子树ifleftdeprightdepreturnleftdep+1;//从叶子计数elsereturnrightdep+1;}}//BTreeDepth
三、算法设计题(每题10分,共30分)
1.试用C或类C语言编写一高效算法,将一顺序存储的线性表(设元素均为整型量)中所有零元素向表尾集中,其他元素则顺序向表头方向集中解voidSortAsqlistL{inti=0zerosum=0;ifL.length==0return0;//空表else{fori=1;i=L.length;i++{ifL.v[i]0L.v[i-zerosum]=L.v[i];elsezerosum++;}}
2.试编写一个算法,判断一给定的整型数组a[n]是不是一个堆解提示堆的定义是kik2i和K2i+1voidSortAsqlistAintn{ifn==0return0;//空表ifa
[1]a
[2]{fori=1;i=n/2;i++ifa[i]a[2*i]||a[i]a[2*i+1]return-1;returnminleap};else{fori=1;i=n/2;i++ifa[i]a[2*i]||a[i]a[2*i+1]return-1;return“maxleap”};}
3.一棵二叉树的繁茂度定义为各层结点数的最大值与树的高度的乘积试写一高效算法,求二叉树的繁茂度法一要用层次遍历以及队列来处理,可以增设一个宽度计数器,在统计完每一层的结点个数之后再从计数器中挑出最大值typedefstruct{BTNodenode;intlayer;//layer是结点所在层数}BTNRecordr;intWidthBitreeT{//求树宽intcount[];//增开count向量,存放各层对应的结点数InitQueueQ;//队列初始化,Q的元素为BTNRecord类型EnQueueQ{T0};//根结点入队0表示count
[0],下标值while!QueueEmptyQ{DeQueueQr;//结点出队count[r.layer]++;//出队时再把结点对应层的计数器加ifr.node-lchildEnQueueQ{r.node-lchildr.layer+1};ifr.node-rchildEnQueueQ{r.node-rchildr.layer+1};}//按层序入队时要随时标注结点所在层号h=r.layer;//最后一个队列元素所在层就是树的高度formaxn=count
[0]i=1;h;i++ifcount[i]maxnmaxn=count[i];//求出哪一层结点数最多returnh*maxn}//Width附加题(15分)设p、t分别表示两棵没有度为1的结点的二叉树设计一种算法,找出p和t中最大的同构子树并分析算法的时间复杂度(无需写出算法,描述思路即可)注“同构”是指两个二叉树不仅结点数相同、并且它们的左右子树之间的关系也相同,但各结点的数据值可以不同“最大的同构子树”即结点最多的同构子树解我们把一棵二叉树用树描述符来表示,则问题会变得容易解决所谓树描述符,即对每个结点按二叉树先序遍历并输出结点的度例如左边二叉树的描述符为
202202000.在此描述符中,如果一个子串的字符数等于此子串中每个数字之和加1,则此子串一定是一个子树如上面的字符串中,2202000是一个子树,因为他有7个字符,每个字符数字和为2+2+2=
6.同理,20200200也是子树问题转化为两个字符串中寻找满足上述条件的最长公共子串最长公共子串的算法已有(见习题),只需在此算法中加上判断此子串是否是一个子树的条件即可判断一个子串是否为一个子树的复杂度为O(n)n为字符串长度由于求最长公共子串的复杂度为Omn,m、n分别为p和t的结点数,判子串是否为子树的过程可以和求最长公共子串相结合,即在求最长公共子串中完成则求最大同构子树的复杂度为Omn螃袈膆蒈螂肁羈莄螁螀芄芀螀袃肇薈蝿羅节蒄螈肇肅莀袇螇芀芆蒄衿肃膂蒃羁艿薁蒂螁肂蒇蒁袃莇莃蒀羆膀艿蒀肈羃薈葿螈膈蒄薈袀羁莀薇羂膆芆薆蚂罿节薅袄芅薀薅羇肇蒆薄聿芃莂薃蝿肆芈薂袁芁膄蚁羃肄蒃蚀蚃芀荿虿螅肂莅虿羇莈芁蚈肀膁蕿蚇蝿羃蒅蚆袂腿莁蚅羄羂芇螄蚄膇膃螃螆羀蒂螃袈膆蒈螂肁羈莄螁螀芄芀螀袃肇薈蝿羅节蒄螈肇肅莀袇螇芀芆蒄衿肃膂蒃羁艿薁蒂螁肂蒇蒁袃莇莃蒀羆膀艿蒀肈羃薈葿螈膈蒄薈袀羁莀薇羂膆芆薆蚂罿节薅袄芅薀薅羇肇蒆薄聿芃莂薃蝿肆芈薂袁芁膄蚁羃肄蒃蚀蚃芀荿虿螅肂莅虿羇莈芁蚈肀膁蕿蚇蝿羃蒅蚆袂腿莁蚅羄羂芇螄蚄膇膃螃螆羀蒂螃袈膆蒈螂肁羈莄螁螀芄芀螀袃肇薈蝿羅节蒄螈肇肅莀袇螇芀芆蒄衿肃膂蒃羁艿薁蒂螁肂蒇蒁袃莇莃蒀羆膀艿蒀肈羃薈葿螈膈蒄薈袀羁莀薇羂膆芆薆蚂罿节薅袄芅薀薅羇肇蒆薄聿芃莂薃蝿肆芈薂袁芁膄蚁羃肄蒃蚀蚃芀荿虿螅肂莅虿羇莈芁蚈肀膁蕿蚇蝿羃蒅蚆袂腿莁蚅羄羂芇螄蚄膇膃螃螆羀蒂螃袈膆蒈螂肁羈莄螁螀芄芀螀袃肇薈蝿羅节蒄螈肇肅莀袇螇芀芆蒄衿肃膂蒃羁艿得分
1.
000120.
290.
5100.
20200.
030.
070.
100.
100.
160.
250.
010.02平均码长为ΣPiWi=1×
0.29+2×
0.1+
0.16+
0.10+
0.07+
0.25+3×
0.01+
0.02=
0.29+
1.36+
0.09=
1.74得分编码为A02B:21C:000D:001E:1F:20G:01H:22得分12345678910姓名班级102412794927133636*7010096247913367096121036*4910027法二若不用辅助数组,不用层数分量也可以,关键在于如何区别层与层有两种方法
一、通过比较指针判断是否到达新的一层的开始;
二、通过比较指针判断是否到达当前层的末尾.由于方法一对新的一层的开始点不易确定,比较次数要多于第二种,因此推荐第二种对任意种类的树都适用,二叉树类似可得算法如下//------------------------------------------------------------------------------------------//TreeWidth求树的宽度//不用辅助数组,不用层数分量//思路//
1.以两个整型变量存宽度,一个表示当前层的节点数,一个表示当前已知最大宽度,当遍历完一层后立即判断两者大小,保留大者//
2.通过比较指针判断是否到达本层的末尾,以确定层与层间的关系//-------------------------------------------------------------------------------------------intTreeWidthTreeNode*T{intiMaxCount=0iRecCount=0;//iRecCount当前层的节点数iMaxCount当前已知最大宽度TreeNode*pP=T*pLastChild=T;//pP指向当前节点pFirstChild指向本层最末节点InitQueueQ;//队列初始化,Q的元素为TreeNode*类型EnQueueQT;//根结点入队while!QueueEmptyQ{DeQueueQpP;//结点出队iRecCount++;//出队时再把结点所在层的计数器加1ifhasChildpPEnQueueQpP-Child;//有孩子则孩子入队ifpP=pLastChild//若到达本层的末尾{//先决定iMaxCount,再重置iRecCount//求繁茂度不能清零此变量iMaxCount=maxiMaxCountiRecCount;iRecCount=0;QueueTailQpLastChild;//读出队尾元素,注意不是出队!!!//既已到本层末尾,又已将其孩子入队若有的话,则队尾元素必为下一层的最末元素}}returniMaxCount;}
01.
0000.
450.
5500.
200.
250.
260.
2900.
100.
1000.
030.07A
0.
100.
160.
010.
021.
000.
550.
450.
260.
290.
200.
250.
100.
160.
030.
070.
100.
100.
010.02A001B:101C:00000D:00001E:11F:100G:0001H:01平均码长为ΣPiWi==3×(
0.1+
0.16+
0.1)+5×(
0.01+
0.02)+2×(
0.29+
0.25)+4×
0.07=
2.59A100B:001C:00000D:00001E:01F:101G:0001H:11平均码长仍为ΣPiWi=
2.59若按教材算法,合并规律应当如下VoidABCBitreepintlinth{ifp≠NILthen{l=l+1;iflhthenh=l;ABCp-Lchildlh;ABCp-Rchildlh;}}此题含义是求树的深度(h)但求解方法是从根开始计算层次反而比从叶子往上计算要简单顺序表的存储结构为typedefstruct{Elemtypev[];intlength;}L;算法的核心部分为voidSortAsqlistL{inti=0zerosum=0;ifL.length==0return0;//空表else{fori=1;i=L.length;i++{ifL.v[i]0L.v[i-zerosum]=L.v[i];elsezerosum++;}fori=i-zerosum+1;i=L.length;i++L.v[i]=0;}PAGE8。