数据结构作业及答案1.doc

第二章2.22 试写一算法,对单链表实现就地逆置,即利用原表的存储空间将线性表（a1,a2,an）逆置为（an,an-1,a1）提示：将原链表中的头结点和第一个元素结点断开（令其指针域为空），先构成一个空表，然后将原链表中各结点从第一个结点起依次插入这个新表的头部。答：void LinkList_reverse(Linklist &L)/链表的就地逆置;为简化算法,假设表长大于2p=L-next;q=p-next;s=q-next;p-next=NULL;while(s-next)q-next=p;p=q;q=s;s=s-next; /把L的元素逐个插入新表表头q-next=p;s-next=q;L-next=s;/LinkList_reverse分析:本算法的思想是,逐个地把L的当前元素q插入新的链表头部,p为新表表头. 第三章3.1 设将整数1、2、3、4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下有问题： （1）若入栈次序为push(1)，pop()，push(2），push(3)，pop()，pop( )，push(4)，pop( )，则出栈的数字序列为什么？ (2) 能否得到出栈序列1423和1432?并说明为什么不能得到或者如何得到。答：(1)1 3 2 4 后进先出，先进后出(2) 1423无法得到，因为只能这样操作，Push(1), Pop(), Push(2), Push(3), Push(4), Pop(),Pop(), Pop(),结果序列是14323.12 写出以下程序段的输出结果（队列中的元素类型QElemType 为char）。Void main( ) Queue Q; InitQueue(Q); Char x=e, y=c; EnQueue(Q, h); EnQueue(Q, r); EnQueue(Q, y); DeQueue(Q, x); EnQueue(Q, x); DeQueue(Q, x); EnQueue(Q, a); While ( !QueueEmpty(Q) ) DeQueue(Q, y); Printf(y); Printf(x);答：输出结果是 char。EnQueue (Q,h); EnQueue (Q,r); EnQueue (Q, y); /hrc入队此时队列是 hrc(h是头)DeQueue (Q,x); EnQueue (Q,x); /h赋给x出队，然后x再入队此时x=h即h入队,此时队列是rch。DeQueue (Q,x); EnQueue (Q,a); /r赋给x出队，a入队，此时队列是chawhile(!QueueEmpty(Q) DeQueue (Q,y);printf(y); /当队列不为空时依次把队列中元素赋给y出列，并打印。此时打印出的是chaPrintf(x); /打印x的值就是前面赋给x的r 所以打印出的是 char第四章4.3 设 s=I AM A STUDENT，t=GOOD， q=WORKER，求： （1） StrLength(s)，StrLength(t)（2） SubString(s, 8, 7) ，SubString(t, 2, 1) （3） Index(s, A,1)，Index(s,t,3)（4） Replace(s, STUDENT, q)（5） Concat(SubString(s,6,2),Concat(t,SubString(s,7,8)答： 1) 14，42) STUDENT，O3) 3，04) I AM A WORKER5) A GOOD WORKER第五章5.1 假设有二维数组A 68，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，计算：（1）数组A的体积（即存储量）；（2）数组A的最后一个元素a57的第一个字节的地址；（3）按行存储时，元素a14的第一个字节的地址；（4）按列存储时，元素a47的第一个字节的地址。答：(1)数组A的体积为686288字节。(2)LOC(5,7)=LOC(0,0)+(5*8+7)*6=1000+282=1282(3) LOC(1,4)=LOC(0,0)+(1*8+4)*6=1000+72=1072(4)按列存储LOC(4,7)=LOC(0,0)+(7*6+4)*6=1000+276=12765.10 求下列广义表操作的结果：（1）GetHead( (p, h, w) );（4） GetTail( (a ,b) ,(c ,d) );（5） GetHead ( GetTail ( (a,b),(c,d) ) )。答：(1)head (p,h,w)=p;(4)tail(a,b),(c,d)=(c,d);(5)head(tail(a,b),(c,d)=(c,d);5.12 按教科书5.5节中图5.8所示结点结构，画出下列广义表的存储结构图，并求它的深度。（1）( ( ( ) ) , a , ( ( b , c ) , ( ) , d ) , ( ( ( e ) ) ) )（2） ( ( ( ( a ) , b ) ) , ( ( ( ) , d ) , ( e , f ) ) )答：(1)和(2)深度都为4.第六章1 在结点个数为n (n1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？ 【解答】结点个数为n时，高度最小的树的高度为1，有2层；它有n-1个叶结点，1个分支结点；高度最大的树的高度为n-1，有n层；它有1个叶结点，n-1个分支结点。2已知一棵二叉树的前序遍历的结果是ABECDFGHIJ, 中序遍历的结果是EBCDAFHIGJ, 试画出这棵二叉树。【解答】当前序序列为ABECDFGHIJ，中序序列为EBCDAFHIGJ时，逐步形成二叉树的过程如下图所示： AAAAFBBFFBGECGECHIGJCDEFHIGJHDJHIJDIEBCD3给定权值集合15, 03, 14, 02, 06, 09, 16, 17, 构造相应的霍夫曼树, 并计算它的带权外部路径长度。【解答】()05171609061415F：17160906021415020303()171609141520161415()17110911060502030605()332029020329161720()16171109151414110915050606050203020382()4933()4933172920161716292014110915110915140605060503020302此树的带权路径长度WPL = 229。4 假定用于通信的电文仅由8个字母c1, c2, c3, c4, c5, c6, c7, c8组成, 各字母在电文中出现的频率分别为5, 25, 3, 6, 10, 11, 36, 4。试为这8个字母设计不等长Huffman编码, 并给出该电文的总码数。【解答】已知字母集 c1, c2, c3, c4, c5, c6, c7, c8 ，频率 5, 25, 3, 6, 10, 11, 36, 4 ，则Huffman编码为 c1 c2 c3 c4 c5 c6 c7 c8 0110 10