数据结构作业.ppt

数据结构
教材: 《数据结构》(C语言版)
严蔚敏吴伟民编著
清华大学出版社
计算机科学与技术学院
第二章作业
补充作业:写出按正位序建立一个单链表的算法。
在什么情况下用顺序表比链表好?
设顺序表va中的数据元素递增有序。试写一算法,将x插入到顺序表的适当位置上,以保持该表的有序性。
第三章作业
2. 写出检验括号匹配的算法。
补充作业:
1. 设将整数1、2、3、4依次进栈,但只要出栈时栈非空,则可将出栈操作按任何次序夹入其中,请回答下有问题:
(1)若入栈次序为push(1),pop(),push(2),push(3),pop(),pop( ),push(4),pop( ),则出栈的数字序列为什么?
(2)请分析1、2、3、4的24种排列中,哪些序列可以通过相应的入出栈得到
写出以下程序段的输出结果(队列中的元素类型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);
}
第四章作业
设 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’),Index(s,t)
(4) Replace(s, ‘STUDENT’, q)
(5)
Concat(SubString(s,6,2),Concat(t,SubString(s,7,8)))
令s=‘aaab’, t=‘abcabaa’,
u=‘abcaabbabcabaacbacba’。
试分别求出它们的next函数值和nextval函数值。
第五章作业
假设有二维数组A 68,每个元素用相邻的6个字节存储,存储器按字节编址。已知A的起始存储位置(基地址)为1000,计算:
(1)数组A的体积(即存储量);
(2)数组A的最后一个元素a57的第一个字节的地址;
(3)按行存储时,元素a14的第一个字节的地址;
(4)按列存储时,元素a47的第一个字节的地址。
求下列广义表操作的结果:
(1)GetHead( (p, h, w) );
(4) GetTail( ((a ,b) ,(c ,d)) );
(5) GetHead ( GetTail ( ((a,b),(c,d)) ) )。
,画出下列广义表的存储结构图,并求它的深度。
(1)( ( ( ) ) , a , ( ( b , c ) , ( ) , d ) , ( ( ( e ) ) ) )
(2 ( ( ( ( a ) , b ) ) , ( ( ( ) , d ) , ( e , f ) ) )
第六章作业
已知一棵树边的集合为{ <I,M>,<I,N>, <E,I>,<B,E>, <B,D>,<A,B>,<G,J>,<G,K>,<C,G>,<C,F>,<H,L>,
<C,H>, <A,C>},
请画出这棵树,并回答下列问题:
(1) 哪个是根结点?
(2) 哪些是叶子结点?
(3) 哪个是结点G的双亲?
(4) 哪些是结点G的祖先?
(5) 哪些是结点G的子孙?
(6) 哪些是结点E的子孙?
(7) 哪些是结点E的兄弟?哪些是结点F的兄弟?
(8) 结点B和N的层次号分别是什么?
(9) 树的深度是多少?
(10) 以结点C为根的子树的深度是多少?
试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。
,分别写出前序、中序和后序遍历的序列。
请对如图所示二叉树进行后序线索化,为每个空指针建立相应的前驱或后继线索。
B
A
C
F
E
D
H
G
阅读下列算法,若有错,则改征之。
BiTree (BiTree q){
//已知q是指向中序线索二叉树上某个结点的指针,
//本函数返回指向*q的后继的指针。
r = qrchild;
if ( !r rtag