发布时间 : 星期五 文章数据结构与算法习题及答案更新完毕开始阅读
精心整理
if(*p=='\\0'){printf(\字符串s1为空串或空格串\\n\}
while(*p!='\\0'&&i while(*p==''&&*p!='\\0')p++;//往后查找一个非空格字符作串s2的尾字符 if(*p=='\\0'){printf(\串没有%d个两端对齐的字符串\\n\} *q=*p;//字符串s2最后一个非空字符 *(++q)='\\0';//置s2字符串结束标记 } *q=s3;p++;//将s1串其余部分送字符串s3。 while(*p!='\\0'){*q=*p;q++;p++;} *q='\\0';//置串s3结束标记 } (9)设二维数组a[1..m,1..n]含有m*n个整数。 ①写一个算法判断a中所有元素是否互不相同?输出相关信息(yes/no)； ②试分析算法的时间复杂度。 [题目分析]判断二维数组中元素是否互不相同，只有逐个比较,找到一对相等的元素，就可结论为不是互不相同。如何达到每个元素同其它元素比较一次且只一次？在当前行，每个元素要同本行后面的元素比较一次（下面第一个循环控制变量p的for循环），然后同第i+1行及以后各行元素比较一次，这就是循环控制变量k和p的二层for循环。 intJudgEqual(inga[m][n],intm,n) //判断二维数组中所有元素是否互不相同，如是，返回1；否则，返回0。 {for(i=0;i 4 总的时间复杂度是O(n)。 (10)设任意n个整数存放于数组A(1:n)中，试编写算法，将所有正数排在所有负数前面（要求算法复杂性为0(n)）。 [题目分析]本题属于排序问题，只是排出正负，不排出大小。可在数组首尾设两个指针i和j，i自小至大搜索到负数停止，j自大至小搜索到正数停止。然后i和j所指数据交换，继续以上过程，直到i=j为止。 voidArrange(intA[],intn) //n个整数存于数组A中，本算法将数组中所有正数排在所有负数的前面 {inti=0,j=n-1,x;//用类C编写，数组下标从0开始 精心整理 精心整理 while(i {while(i if(i }//算法Arrange结束. [算法讨论]对数组中元素各比较一次，比较次数为n。最佳情况(已排好,正数在前,负数在后)不发生交换，最差情况(负数均在正数前面)发生n/2次交换。用类c编写，数组界偶是0..n-1。空间复杂度为O(1). 第5章树和二叉树 1．选择题 （1）把一棵树转换为二叉树后，这棵二叉树的形态是（）。 A．唯一的Ｂ．有多种 C．有多种，但根结点都没有左孩子Ｄ．有多种，但根结点都没有右孩子 （2）由3个结点可以构造出多少种不同的二叉树？（） A．2B．3 C．4D．5 （3）一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。 A．250B．500 C．254D．501 （4）一个具有1025个结点的二叉树的高h为（）。 A．11B．10 C．11至1025之间D．10至1024之间 （5）深度为h的满m叉树的第k层有（）个结点。(1= A．前序B．中序C．后序D．按层次 （9）在下列存储形式中，（）不是树的存储形式？ A．双亲表示法B．孩子链表表示法C．孩子兄弟表示法D．顺序存储表示法 （10）一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（）。 A．所有的结点均无左孩子B．所有的结点均无右孩子 C．只有一个叶子结点D．是任意一棵二叉树 （11）某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。 A．空或只有一个结点B．任一结点无左子树 C．高度等于其结点数D．任一结点无右子树 （12）若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为（）。 A．X的双亲B．X的右子树中最左的结点 C．X的左子树中最右结点D．X的左子树中最右叶结点 （13）引入二叉线索树的目的是（）。 A．加快查找结点的前驱或后继的速度B．为了能在二叉树中方便的进行插入与删除 精心整理 精心整理 C．为了能方便的找到双亲D．使二叉树的遍历结果唯一 （14）线索二叉树是一种（）结构。 A．逻辑B．逻辑和存储C．物理D．线性 （15）设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（）个。 A．n-1B．nC．n+1D．n+2 2．应用题 （1）试找出满足下列条件的二叉树 ①先序序列与后序序列相同②中序序列与后序序列相同 ③先序序列与中序序列相同④中序序列与层次遍历序列相同 先序遍历二叉树的顺序是“根—左子树—右子树”，中序遍历“左子树—根—右子树”，后序遍历顺序是：“左子树—右子树―根＂，根据以上原则，本题解答如下： （１）?若先序序列与后序序列相同，则或为空树，或为只有根结点的二叉树 （２）?若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树． （３）?若先序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树． （４）?若中序序列与层次遍历序列相同，则或为空树，或为任一结点至多只有右子树的二叉树 （2）设一棵二叉树的先序序列：ABDFCEGH，中序序列：BFDAGEHC ①画出这棵二叉树。 ②画出这棵二叉树的后序线索树。 ③将这棵二叉树转换成对应的树（或森林）。 ? AC(1)(2) （3）假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.19，0.020.06，0.32，BD0.07，EH，0.03，0.21，0.10。 FG①试为这8个字母设计赫夫曼编码。 ②试设计另一种由二进制表示的等长编码方案。 ③对于上述实例，比较两种方案的优缺点。 (解：方案1；哈夫曼编码 先将概率放大100倍，以方便构造哈夫曼树。 w={7,19,2,6,32,3,21,10}，按哈夫曼规则：【[（2,3），6],(7,10)】,……19,21,32 （100） 01 （40）（60） 192132（28） 0101 （17） （11） 19 2132 0 1 7106（5） 0101 23 7 106 0 1 方案比较： 23 字母对应出现字母对应出现方案1的WPL＝2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61 编号 编码 频率 编号 编码 频率 方案2的WPL＝3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3 1 1100 0.07 1 000 0.07 结论：哈夫曼编码优于等长二进制编码 2 00 0.19 2 001 0.19 ?（4）已知下列字符A、B、C、D、E、F、G的权值分别为3、12、7、4、2、8，11，试填写出其对应哈夫曼3 11110 0.02 3 010 0.02 树HT的存储结构的初态和终态。 4 1110 0.06 4 011 0.06 初态: 5 10 0.32 5 100 0.32 weight parent lchild rchild 6 101 0.03 1 3 0 0 0 精心整理 精心整理 2 3 4 5 6 7 8 9 10 11 12 13 是否是叶子返回1 12 7 4 2 1 8 2 11 3 4 5 6 7 8 9 10 11 12 13 0 0 0 weight 0 3 0 12 0 7 0 4 0 2 0 8 0 11 0 5 0 9 15 20 27 47 0 0 0 parent 0 8 0 12 0 10 0 9 0 8 0 10 0 11 0 9 0 11 12 13 13 0 0 0 0 lchild 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 4 3 9 2 11 终态 3．算法设计题 以二叉链表作为二叉树的存储结构，编写rchild 以下算法： （1）统计二叉树的叶结点个数。 0 intLeafNodeCount(BiTreeT) 0 { 0 if(T==NULL) 0 return0;//如果是空树，0 则叶子结点个数为0 0 elseif(T->lchild==NULL&&T0 ->rchild==NULL) 1 return1;//判断该结点8 结点（左孩子右孩子都为空），若是则6 7 10 12 else returnLeafNodeCount(T->lchild)+LeafNodeCount(T->rchild); } （2）判别两棵树是否相等。 （3）交换二叉树每个结点的左孩子和右孩子。 voidChangeLR(BiTree&T) { BiTreetemp; if(T->lchild==NULL&&T->rchild==NULL) return; else { temp=T->lchild; T->lchild=T->rchild; T->rchild=temp; } ChangeLR(T->lchild); ChangeLR(T->rchild); } （4）设计二叉树的双序遍历算法（双序遍历是指对于二叉树的每一个结点来说，先访问这个结点，再按双序遍历它的左子树，然后再一次访问这个结点，接下来按双序遍历它的右子树）。 voidDoubleTraverse(BiTreeT) { if(T==NULL) return; elseif(T->lchild==NULL&&T->rchild==NULL) cout<