当前位置:文档之家› 数据结构作业及答案1

数据结构作业及答案1

第二章
2.22 试写一算法,对单链表实现就地逆置,即利用原表的存储空间将线性表
(a1,a2,…,an)逆置为(an,an-1,…,a1)
提示:将原链表中的头结点和第一个元素结点断开(令其指针域为空),先构成一个空表,然后将原链表中各结点从第一个结点起依次插入这个新表的头部。

答:void LinkList_reverse(Linklist &L)//链表的就地逆置;为简化算法,假设表长大于2
{
p=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(),结果序列是1432
3.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’入队,此时队列是‘cha’while(!QueueEmpty(Q)){ DeQueue (Q,y);printf(y);}; //当队列不为空时依次把队列中元素赋给y出列,并打印。

此时打印出的是cha
Printf(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,4
2) STUDENT,O
3) 3,0
4) "I AM A WORKER"
5) "A GOOD WORKER"
第五章
5.1 假设有二维数组A6×8,每个元素用相邻的6个字节存储,存储器按字节编址。

已知A 的起始存储位置(基地址)为1000,计算:
(1)数组A的体积(即存储量);
(2)数组A的最后一个元素a57的第一个字节的地址;
(3)按行存储时,元素a14的第一个字节的地址;
(4)按列存储时,元素a47的第一个字节的地址。

答:(1)数组A的体积为6×8×6=288字节。

(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=1276
5.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(n>1)的各棵树中,高度最小的树的高度是多少?它有多少个叶结点?多少个分支结点?高度最大的树的高度是多少?它有多少个叶结点?多少个分支结点?
【解答】结点个数为n时,高度最小的树的高度为1,有2层;它有n-1个叶结点,1个分支结点;高度最大的树的高度为n-1,有n层;它有1个叶结点,n-1个分支结点。

2已知一棵二叉树的前序遍历的结果是ABECDFGHIJ, 中序遍历的结果是EBCDAFHIGJ, 试画出这棵二叉树。

【解答】
当前序序列为ABECDFGHIJ,中序序列为EBCDAFHIGJ时,逐步形成二叉树的过程如
下图所示:
3给定权值集合{15, 03, 14, 02, 06, 09, 16, 17},
构造相应的霍夫曼树, 并计算它的带权外部路径长度。

【解答】
此树的带权路径长度
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 },则
F :
(Ⅰ) (Ⅱ) (Ⅲ)
(Ⅳ)
(
(Ⅵ) (Ⅶ)
电文总码数为 4 * 5 + 2 * 25 + 4 * 3 + 4 * 6 + 3 * 10 + 3 * 11 + 2 * 36 + 4 * 4 = 257。

相关主题