数据结构(第版)习题及实验参考答案-数据结构复习资料完整版(c语言版).doc

《数据结构(第版)习题及实验参考答案-数据结构复习资料完整版(c语言版).doc》由会员分享，可在线阅读，更多相关《数据结构(第版)习题及实验参考答案-数据结构复习资料完整版(c语言版).doc（44页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、数据结构基础及深入及考试复习资料 习题及实验参考答案见附录结论 1、数据得逻辑结构就是指数据元素之间得逻辑关系。即从逻辑关系上描述数据,它与数据得存储无关,就是独立于计算机得。 2、数据得物理结构亦称存储结构,就是数据得逻辑结构在计算机存储器内得表示(或映像)。它依赖于计算机。存储结构可分为4大类:顺序、链式、索引、散列 3、抽象数据类型:由用户定义,用以表示应用问题得数据模型。它由基本得数据类型构成,并包括一组相关得服务(或称操作)。它与数据类型实质上就是一个概念,但其特征就是使用与实现分离,实行封装与信息隐蔽(独立于计算机)。 4、算法:就是对特定问题求解步骤得一种描述,它就是指令得有限序

2、列,就是一系列输入转换为输出得计算步骤。 5、在数据结构中,从逻辑上可以把数据结构分成( C ) A、动态结构与表态结构 B、紧凑结构与非紧凑结构 C、线性结构与非线性结构 D、内部结构与外部结构6、算法得时间复杂度取决于( A ) A、问题得规模 B、待处理数据得初态 C、问题得规模与待处理数据得初态线性表 1、线性表得存储结构包括顺序存储结构与链式存储结构两种。 2、表长为n得顺序存储得线性表,当在任何位置上插入或删除一个元素得概率相等时,插入一个元素所需移动元素得平均次数为( E ),删除一个元素需要移动得元素得个数为( A )。 A、(n-1)/2 B、n C、n+1 D、n-1 E、

3、n/2 F、(n+1)/2 G、(n-2)/2 3、“线性表得逻辑顺序与存储顺序总就是一致得。”这个结论就是( B ) A、正确得 B、错误得 C、不一定,与具体得结构有关 4、线性表采用链式存储结构时,要求内存中可用存储单元得地址( D ) A、必须就是连续得 B、部分地址必须就是连续得C一定就是不连续得D连续或不连续都可以 5、带头结点得单链表为 空得判定条件就是( B ) A、head=NULL B、head-next=NULL C、head-next=head D、head!=NULL 6、不带头结点得单链表head为空得判定条件就是( A )A、head=NULL B、head-ne

4、xt=NULL C、head-next=head D、head!=NULL 7、非空得循环单链表head得尾结点P满足( C ) A、p-next=NULL B、p=NULL C、p-next=head D、p=head 8、在一个具有n个结点得有序单链表中插入一个新结点并仍然有序得时间复杂度就是( B ) A、O(1) B、O(n) C、O(n2) D、O(nlog2n) 9、在一个单链表中,若删除p所指结点得后继结点,则执行( A )A、p-next=p-next-next;B、p=p-next;p-next=p-next-next;C、p-next=p-next;D、p= p-next-

5、next; 10、在一个单链表中,若在p所指结点之后插入s所指结点,则执行( B ) A、s-next=p;p-next=s; B、s-next=p-next;p-next=s;C、s-next=p-next;p=s;D、p-next=s;s-next=p;11、在一个单链表中,已知q就是p得前趋结点,若在q与p之间插入结点s,则执行( C )A、s-next=p-next;p-next=s;B、p-next=s-next;s-next=p;C、q-next=s;s-next=p;D、p-next=s;s-next=q;12、在线性结构中,第一个结点 没有 前趋结点,其余每个结点有且只有 1

6、个前趋结点。栈与队列1、在栈操作中,输入序列为(A,B,C,D),不可能得到得输出数列就是( D ) A、(A,B,C,D) B、(D,C,B,A) C、(A,C,D,B) D、(C,A,D,B)2、设栈ST用顺序存储结构表示,则栈ST为空得条件( B ) A、ST、top=ST、base0 B、ST、top=ST、base=0 C、ST、top=ST、basen D、ST、top=ST、base=n3、向一个栈顶指针为HS得链栈中插入一个s结点时,执行( C ) A、HS-next=s; B、s-next=HS-next;HS-next=s; C、s-next=HS;HS=S; D、s-ne

7、xt=HS;HS=HS-next;4、从一个栈顶指针为HS得链栈中删除一个结点,用x保存被删结点得值,则执行( C ) A、x=HS;HS=HS-next; B、HS=HS-next;x=HS-data; C、x=HS-data;HS=HS-next; D、s-next=HS;HS=HS-next;5、用单链表表示得链示队列得队头在链表得( A )位置。 A、链头 B、链尾 C、链中6、判定一个链队列(最多元素个数为n)为空得条件就是(A)、front=Q、rear B、Q、front!=Q、rearC、Q、front=(Q、rear+1)%n D、Q、front!=(Q、rear+1)%n7

8、、在链队列中,插入要所指结点需顺序执行得指令就是(B)A、Q、front-next=s;f=s;B、Q、rear-next=s;Q、rear=s;C、s-next=Q、rear;Q、rear=s;D、s-next=Q、front;Q、front=s;8、在一个链队列Q中,删除一个结点需要执行得指令就是( C ) A、Q、rear=Q、front-next; B、Q、rear-next=Q、rear-next-next; C、Q、front-next=Q、front-next-next; D、Q、front=Q、rear-next; 9、栈与队列得共同点( C ) A、都就是先进后出 B、都就是

9、先进先出 C、只允许在端点处插入与删除元素D、没有共同点10、栈得特点就是_先进后出,队列得特点就是先进先出11、线性表、栈与队列都就是线性结构,可以在线性表得任何位置插入与删除元素;对于栈只能在栈顶插入与删除元素;对于队列只能在队尾插入元素与在队首删除元素。串与数组1、设串s1=ABCDEFG,s2=PQRST,函数Concat(x,y)返回x与y串得连接串,Substr(s,I,j)返回串s从序号i开始得j个字符组成得子串,length(s)返回串s得长度,则Concat(Substr(s1,2, length(s2), Substr(s1,length(s2),2)得结果串就是( D )

10、A、BCDEF B、BCDEFG C、BCPQRST D、BCDEFEF2、串就是一种特殊得线性表,其特殊性体现在( D ) A、可以顺序存储 B、数据元素就是一个字符C、可以链接存储 D、数据元素可以就是多个字符3、设有两个串p与q,求q在p中首次出现得位置得运算称作( B )A、连接 B、模式匹配 C、求子串联 D、求串长4、串得两种最基本得存储方式就是顺序存储方式与链接存储方式。树与二叉树1、树最合适用来表示( B )A、有序数据元素 B、元素之间具有分支层次关系得数据C、无序数据元素 D、元素之间无联系得数据2、按照二叉树得定义,具有3个结点得二叉树有( C )种。A、3 B、4 C、

11、5 D、63、在一棵有n个结点得二叉树中,若度为2得结点数为n2,度为1得结点数为n1,度为0得结点数为n0,则树得最大高度为( E ),其叶结点数为( G );树得最小高度为( B ),其叶结点数为( G );若采用链表存储结构,则有( I )个空链域。A、n/2 B、log2n+1 C、log2n D、n E、n0 + n1 + n2 F、n1 + n2 G、n2 +1 H、1 I、n+1 J、n1 K、n2 L、n1 +14、在一棵二叉树上第5层得结点数最多为( B )。(假设根结点得层数为0)A、8 B、16 C、15 D、325、深度为5得二叉树至多有( C )个结点。A、16 B、

12、32 C、31 D、106、在一非空二叉树得中序遍历序列中,根结点得右边( A )A、只有右子树上得所有结点 B、只有右子树上得部分结点C、只有左子树上得部分结点 D、只有左子树上得所有结点7、一棵完全二叉树按层次遍历得序列为ABCDEFGHI,则在先序遍历中结点E得直接前趋为( D ),后序遍历中结点B得直接后继就是( E )。A、B B、D C、A D、I E、F F、C8、已知某二叉树得后序遍历序列就是dabec,中序遍历序列就是debac,它得前序遍历序列就是( D )A、acbed B、decab C、deabc D、cedba9、在树形结构中,树根结点没有_前趋_结点,其余每个结点

13、有且只有_1_个前趋结点;叶子结点没有_后继_结点,其余每个结点得后继结点可以_任意多个_。10、有一棵树如图所示,回答下面得问题:K1K7K6K5K2K3K4这棵树得根结点就是_K1_,这棵树得叶子结点就是_K2,K5,K7,K4_;结点k3得度就是_2_;这棵树得度为_3_;这棵树得深度就是_4_;结点k3得子女就是_K5,K6_;结点k3得父结点就是_K1_、11、已知一棵二叉树得中序遍历序列为CDBAEGF,前序遍历序列为ABCDEFG,试问能不能惟一确定一棵二叉树,若能请画出该二叉树。若给定前序遍历序列与后序遍历序列,能否惟一确定一棵二叉树,说明理由。答:由中序遍历序列与前序遍历序列

14、或中序遍历序列与后序遍历序列可以惟一确定一棵二叉树。基本思想就是前序(后序)定根,中序分左右。对于给定得前序与中序序列。可确定根结点为A,以A为根得左子树结点为B,C,D,右子树结点为E,F,G。进一步可确定所有子树得根结点,因而也就确定了整个二叉树。对应得二叉树如图所示:FADGFECB由前序遍历与后序遍历序列不能惟一确定一棵二叉树。如图所示为4棵不同得二叉树,它们得前序遍历序列都就是ABC,而后序遍历序列都就是CBA。ACBCBAACBACB12、设二叉树bt得存储结构如下:12345678910left00237580101datajhfdbacegiright0009400000其中b

15、t为树根结点指针,left,right分别为结点得左右孩子指针域,data为结点得数据域,请完成下列各题:画出二叉树bt得逻辑结构写出按前序、中序与后序遍历二叉树bt所得到得结点序列。答:二叉树bt得逻辑结构如图所示:12ajighfdecb前序遍历:abcedfhgij中序遍历:ecbhfdjiga后序遍历:echfjigdba13、给定一棵以二叉链表存储结构表示得二叉树,其根结点指针为T,试写出求二叉树得叶子数目得算法。int CountLeaf (BiTree T)/返回指针T所指二叉树中所有叶子结点个数 if (!T ) return 0; if (!T-lchild & !T-rch

16、ild) return 1; else m = CountLeaf( T-lchild); n = CountLeaf( T-rchild); return (m+n); /else / CountLeaf14、给定一棵以二叉链表存储结构表示得二叉树,其根结点指针为T,试写出求二叉树得深度得算法。int Depth (BiTree T ) / 返回二叉树得深度 if ( !T ) depthval = 0; else depthLeft = Depth( T-lchild ); depthRight= Depth( T-rchild ); depthval = 1 + (depthLeft d

17、epthRight ? depthLeft : depthRight); return depthval;图1、一个有n个顶点得无向图最多有( C )条边。A、n B、n(n-1) C、n(n-1)/2 D、2n2、具有6个顶点得无向图至少应有( A )条边才能确保就是一个连通图。A、5 B、6 C、7 D、83、存储稀疏图得数据结构常用得就是( C )A、邻接矩阵 B、三元组 C、邻接表 D、十字链表4、在有向图得邻接表存储结构中,顶点V在表结点中出现得次数就是( C )A、顶点V得度 B、顶点V得出度 C、顶点V得入度 D、依附于顶点V得边数5、用DFS遍历一个无环有向图,并在DFS算法退

18、栈返回时,打印出相应得顶点,则输出得顶点序列就是( A )A、逆拓扑有序得 B、拓扑有序得 C、无序得6、已知一个图如图所示,若从顶点a出发按深度优先搜索法进行遍历,则可能得到得一种顶点序列为( D ),按广度优先搜索法进行遍历,则可能得到得一种顶点序列为( B )。A、abecdf B、acfebd C、acebfd D、acfdebA、abcedf B、abcefd C、abedfc D、acfdebCacfdeb7、采用邻接表存储得图得广度优先搜索遍历算法类似于二叉树得( D )A、中序遍历 B、先序遍历 C、后序遍历 D、按层遍历8、已知一个图如图所示,则由该图得到得一种拓扑序列为(

19、A )165432A、V1,V4,V6,V2,V5,V3 B、V1,V2,V3,V4,V5,V6C、V1,V4,V2,V3,V6,V5 D、V1,V2,V4,V6,V3,V59、在图形结构中,每个结点得前趋结点数与后续结点数可以_任意多个_。10、在AOE网中,从源点到汇点各活动时间总与最长得路径称为关键路径。11、给出图G,如图所示:1111098765432(1)给出图G得邻接表(画图即可)(2)在您给出得邻接表得情况下,以顶点V4为根,画出图G得深度优先生成树与广度优先生成树。(3)将您画出得广度优先生成树转换为对应得二叉树。答: (1)图得邻接表如下图所示:略(2)以顶点V4为根得深度

20、优先生成树与广度优先生成树如图所示1111098765432d1111098765432(3)广度优先生成树转换成二叉树如下图所示11109117863452附录 习题及实验参考答案习题1参考答案1、1、选择题(1)、 A、 (2)、 A、 (3)、 A、 (4)、 B、,C、 (5)、 A、 (6)、 A、 (7)、 C、 (8)、 C、 (9)、 B、 (10、) A、1、2、填空题(1)、 数据 关系(2)、 逻辑结构 物理结构(3)、 线性数据结构 树型结构 图结构(4)、 顺序存储 链式存储 索引存储 散列表(Hash)存储(5)、 变量得取值范围 操作得类别(6)、 数据元素间得逻

21、辑关系 数据元素存储方式或者数据元素得物理关系(7)、 关系 网状结构 树结构(8)、 空间复杂度与时间复杂度(9)、 空间 时间(10)、 (n)1、3 名词解释如下:数据:数据就是信息得载体,就是计算机程序加工与处理得对象,包括数值数据与非数值数据。数据项:数据项指不可分割得、具有独立意义得最小数据单位,数据项有时也称为字段或域。数据元素:数据元素就是数据得基本单位,在计算机程序中通常作为一个整体进行考虑与处理,一个数据元素可由若干个数据项组成。数据逻辑结构:数据得逻辑结构就就是指数据元素间得关系。数据存储结构:数据得物理结构表示数据元素得存储方式或者数据元素得物理关系。数据类型:就是指变

22、量得取值范围与所能够进行得操作得总与。算法:就是对特定问题求解步骤得一种描述,就是指令得有限序列。1、4 语句得时间复杂度为:(1) (n2) (2) (n2)(3) (n2)(4) (n-1)(5) (n3)1、5 参考程序:main()int X,Y,Z;scanf(“%d, %d, %d”,&X,&Y,Z);if (X=Y) if(X=Z) if (Y=Z) printf(“%d, %d, %d”,X,Y,Z);else printf(“%d, %d, %d”,X,Z,Y);else printf(“%d, %d, %d”,Z,X,Y); else if(Z=X) if (Y=Z) pr

23、intf(“%d, %d, %d”,Y,Z,X);else printf(“%d, %d, %d”,Z,Y,X);else printf(“%d, %d, %d”,Y,X,Z);1、6 参考程序:main() int i,n;float x,a,p;printf(“nn=”);scanf(“%f”,&n);printf(“nx=”);scanf(“%f”,&x);for(i=0;i=n;i+)scanf(“%f ”,&ai); p=a0;for(i=1;inext=p-next; p-next=s ;(10)、 s-next 2、3、 解题思路:将顺序表A中得元素输入数组a,若数组a中元素个数

24、为n,将下标为0,1,2,(n-1)/2得元素依次与下标为n,n-1, (n-1)/2得元素交换,输出数组a得元素。参考程序如下:main() int i,n;float t,a;printf(“nn=”);scanf(“%f”,&n);for(i=0;i=n-1;i+)scanf(“%f ”,&ai); for(i=0;i=(n-1)/2;i+) t=ai; ai =an-1-i; an-1-i=t; for(i=0;i=n-1;i+) printf(“%f”,ai);2、4 算法与程序:main() int i,n;float t,a;printf(“nn=”);scanf(“%f”,&n

25、);for(i=0;in;i+)scanf(“%f ”,&ai); for(i=1;ia0 t=ai; ai =a0; a0=t; printf(“%f”,a0);for(i=2;ia1 t=ai; ai =a1; a1=t; printf(“%f”,a0);2、5 算法与程序:main() int i,j,k,n;float x,t,a;printf(“nx=”);scanf(“%f”,&x);printf(“nn=”);scanf(“%f”,&n);for(i=0;in;i+)scanf(“%f ”,&ai); / 输入线性表中得元素for (i=0; in; i+) / 对线性表中得元素

26、递增排序 k=i; for (j=i+1; jn; j+) if (ajak) k=j; if (kj) t=ai;ai=ak;ak=t; for(i=0;ix) break;for(k=n-1;k=i;i-) / 移动线性表中元素,然后插入元素x ak+1=ak; ai=x; for(i=0;i=n;i+) / 依次输出线性表中得元素printf(“%f”,ai);2、6 算法思路:依次扫描A与B得元素,比较A、B当前得元素得值,将较小值得元素赋给C,如此直到一个线性表扫描完毕,最后将未扫描完顺序表中得余下部分赋给C即可。C得容量要能够容纳A、B两个线性表相加得长度。有序表得合并算法:voi

27、d merge (SeqList A, SeqList B, SeqList *C) int i,j,k; i=0;j=0;k=0; while ( i=A、last & j=B、last ) if (A、dataidatak+=A、datai+; else C-datak+=B、dataj+;while (idatak+= A、datai+;while (jdatak+=B、dataj+;C-last=k-1;2、7 算法思路:依次将A中得元素与B得元素比较,将值相等得元素赋给C,如此直到线性表扫描完毕,线性表C就就是所求递增有序线性表。算法:void merge (SeqList A, S

28、eqList B, SeqList *C) int i,j,k; i=0;j=0;k=0; while ( i=A、last)while(jdatak+=A、datai+; C-last=k-1;习题3参考答案3、1、选择题(1)、 D (2)、 C (3)、 D (4)、 C (5)、 B (6)、 C (7)、 C (8)、 C (9)、 B (10)、AB (11)、 D (12)、 B (13)、 D (14)、 C (15)、 C (16)、 D(17)、 B (18)、 C (19)、 C (20)、 C 3、2、填空题（1） FILO, FIFO（2） -1, 3 4 X * +

29、 2 Y * 3 / -（3） stack、top+, stack、sstack、top=x（4） pllink-rlink=p-rlink, p-rlink-llink=p-rlink（5） (R-F+M)%M（6） top1+1=top2（7） F=R（8） front=rear（9） front=(rear+1)%n（10） N-13、3 答:一般线性表使用数组来表示得线性表一般有插入、删除、读取等对于任意元素得操作而栈只就是一种特殊得线性表栈只能在线性表得一端插入(称为入栈,push)或者读取栈顶元素或者称为“弹出、出栈”(pop)。3、4 答:相同点:栈与队列都就是特殊得线性表,只在

30、端点处进行插入,删除操作。不同点:栈只在一端(栈顶)进行插入,删除操作;队列在一端(top)删除,一端(rear)插入。3、5 答:可能序列有14种:ABCD; ACBD; ACDB; ABDC; ADCB; BACD; BADC; BCAD; BCDA; BDCA; CBAD; CBDA; CDBA; DCBA。3、6 答:不能得到4,3,5,6,1,2,最先出栈得就是4,则按321得方式出,不可能得到1在2前得序列,可以得到1,3,5,4,2,6,按如下方式进行push(1), pop(), push(2), push(3), pop(), push(4), push(5), pop(),

31、 pop(), pop(), push(6), pop()。 3、7 答:stack3、8 非递归:int vonvert (int no,int a) /将十进制数转换为2进制存放在a,并返回位数int r;SeStack s,*p;P=&s;Init_stack(p);while(no)push(p,no%2);no/=10;r=0;while(!empty_stack(p)pop(p,a+r);r+;return r;递归算法:void convert(int no)if(no/20)Convert(no/2);Printf(“%d”,no%2);elseprintf(“%d”,no);

32、 3、9 参考程序:void view(SeStack s)SeStack *p; /假设栈元素为字符型 char c;p=&s;while(!empty_stack(p)c=pop(p);printf(“%c”,c);printf(”n”);3、10 答:char3、11 参考程序:void out(linkqueue q) int e; while(q、rear !=q、front ) dequeue(q,e); print(e); /打印 习题4参考答案4、1 选择题:(1)、 A (2)、 D (3)、 C (4)、 C (5)、 B (6)、 B (7)、 D (8)、 A (9)、

33、 B (10)、 D4、2 填空题:（1） 串长相等且对应位置字符相等（2） 不含任何元素得串,0（3） 所含字符均就是空格,所含空格数（4） 10（5） “helloboy”（6） 18（7） 1066（8） 由零个或多个任意字符组成得字符序列（9） 串中所含不同字符得个数（10） 364、3 StrLength (s)=14, StrLength (t)=4, SubStr( s,8,7)=” STUDENT”, SubStr(t,2,1)=”O”,StrIndex(s,“A”)=3, StrIndex (s,t)=0, StrRep(s,“STUDENT”,q)=” I AM A WOR

34、KER”,4、4 StrRep(s,”Y”,”+”);StrRep(s,”+*”,”*Y”);4、5 空串:不含任何字符;空格串:所含字符都就是空格串变量与串常量:串常量在程序得执行过程中只能引用不能改变;串变量得值在程序执行过程中就是可以改变与重新赋值得主串与子串:子串就是主串得一个子集串变量得名字与串变量得值:串变量得名字表示串值得标识符 4、6 int EQUAl(S,T)char *p,*q;p=&S;q=&T;while(*p&*q)if(*p!=*q)return *p-*q;p+;q+;return *p-*q; 4、7 (1)6*8*6=288(2)1000+47*6=1282

35、(3)1000+(8+4)*6=1072(4)1000+(6*7+4)*6=12764、8 i j v1 1 2 12 1 5 -13 2 1 44 3 4 75 4 2 66 5 1 87 5 3 9矩阵得三元组表习题5参考答案5、1 选择(1)C(2)B(3)C(4)B(5)C(6)D(7)C(8)C(9)B(10)C(11)B(12)C(13)C(14)C(15)C5、2 填空(1)1(2)1036;1040(3)2i(4) 1 ; n ; n-1 ; 2 (5)2k-1;2k-1(6)ACDBGJKIHFE(7)p!=NULL(8)Huffman树(9)其第一个孩子; 下一个兄弟(10

36、)先序遍历;中序遍历5、3 叶子结点:C、F、G、L、I、M、K;非终端结点:A、B、D、E、J;各结点得度:结点: A B C D E F G L I J K M 度: 4 3 0 1 2 0 0 0 0 1 0 0树深:45、4 无序树形态如下:二叉树形态如下:5、5 二叉链表如下:ABCDEFGHIJ三叉链表如下:ACBFGDEJIH5、6 先序遍历序列:ABDEHICFJG中序遍历序列:DBHEIAFJCG后序遍历序列:DHIEBJFGCA5、7 (1) 先序序列与中序序列相同:空树或缺左子树得单支树;(2) 后序序列与中序序列相同:空树或缺右子树得单支树;(3) 先序序列与后序序列相

37、同:空树或只有根结点得二叉树。5、8 这棵二叉树为:5、9 先根遍历序列:ABFGLCDIEJMK后根遍历序列:FGLBCIDMJKEA层次遍历序列:ABCDEFGLIJKM5、10 证明:设树中结点总数为n,叶子结点数为n0,则n=n0 + n1 + + nm (1)再设树中分支数目为B,则B=n1 + 2n2 + 3n3 + + m nm (2)因为除根结点外,每个结点均对应一个进入它得分支,所以有n= B + 1 (3)将(1)与(2)代入(3),得n0 + n1 + + nm = n1 + 2n2 + 3n3 + + m nm + 1从而可得叶子结点数为:n0 = n2 + 2n3 + + (m-1)nm + 1 5、11 由5、10结论得,n0 = (k-1)nk + 1 又由 n=n0 + nk ,得nk= n-n0,代入上式,得n0 = (k-1)(n-n0)+ 1叶子结点数为:n0 = n (k-1) / k5、12 int NodeCo