内容发布更新时间 : 2024/12/23 17:38:10星期一 下面是文章的全部内容请认真阅读。
精心整理
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.唯一的B.有多种 C.有多种,但根结点都没有左孩子D.有多种,但根结点都没有右孩子 (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)试找出满足下列条件的二叉树 ①先序序列与后序序列相同②中序序列与后序序列相同 ③先序序列与中序序列相同④中序序列与层次遍历序列相同 先序遍历二叉树的顺序是“根—左子树—右子树”,中序遍历“左子树—根—右子树”,后序遍历顺序是:“左子树—右子树―根",根据以上原则,本题解答如下: (1)?若先序序列与后序序列相同,则或为空树,或为只有根结点的二叉树 (2)?若中序序列与后序序列相同,则或为空树,或为任一结点至多只有左子树的二叉树. (3)?若先序序列与中序序列相同,则或为空树,或为任一结点至多只有右子树的二叉树. (4)?若中序序列与层次遍历序列相同,则或为空树,或为任一结点至多只有右子树的二叉树 (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<