《数据结构(第4版)习题及实验参考答案-数据结构复习资料完整版(c语言版).docx》由会员分享，可在线阅读，更多相关《数据结构(第4版)习题及实验参考答案-数据结构复习资料完整版(c语言版).docx（46页珍藏版）》请在金锄头文库上搜索。
1、数据结构基础及深入及考试复习资料习题及实验参考答案见附录结论1、数据的逻辑结构是指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据 的存储无关，是独立于计算机的。2、数据的物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。 它依赖于计算机。存储结构可分为4大类：顺序、链式、索引、散列3、抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构 成，并包括组相关的服务（或称操作）。它与数据类型实质上是一个概念，但其特征是使 用与实现分离，实行封装和信息隐蔽（独立于计算机）。4、算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转
2、换 为输出的计算步骤。5、在数据结构中，从逻辑上可以把数据结构分成（C ）A、动态结构和表态结构B、紧凑结构和非紧凑结构C、线性结构和非线性结构D、内部结构和外部结构6、算法的时间复杂度取决于（A ）A、问题的规模 B、待处理数据的初态 C、问题的规模和待处理数据的初态线性表1、线性表的存储结构包括顺序存储结构和链式存储结构两种。2、表长为n的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时， 插入一个元素所需移动元素的平均次数为（E ）,删除一个元素需要移动的元素的个数 为（A ）oA、（n-l）/2 B、n C、n+1 D、n-1 E、n/2 F、（n+l）/2 G、（n-2
3、）/23、“线性表的逻辑顺序与存储顺序总是一致的。”这个结论是（ B ）A、正确的B、错误的C、不一定，与具体的结构有关4、线性表采用链式存储结构时，要求内存中可用存储单元的地址（D ）A、必须是连续的B、部分地址必须是连续的C 一定是不连续的D连续或不连续都可 以5、带头结点的单链表为空的判定条件是（B ）A、hcad=NULL B、hcad-ncxt=NULL C、hcad-next=hcad D、hcad!=NULL6、不带头结点的单链表head为空的判定条件是（A ）A、hcad=NULL B、hcad-ncxt=NULL C、hcad-ncxt=hcad D、head!二NULL7、
4、非空的循环单链表head的尾结点P满足（C ）A、p-ncxt=NULL B、p=NULL C、p-ncxt=hcad D、p=hcad8、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是 （B ）附录习题及实验参考答案习题1参考答案1.1.选择题(1). A.A. (3). A. (4). B.,C. (5). A. (6). A. (7). C. (8). C. (9). B. (10.) A.12填空题.数据关系.逻辑结构物理结构.线性数据结构树型结构图结构(1) .顺序存储链式存储索引存储散列表(Hash)存储.变量的取值范围操作的类别.数据元素间的逻辑关系数据元
5、素存储方式或者数据元素的物理关系.关系网状结构树结构(2) .空间复杂度和时间复杂度.空间时间. O(n)1.3名词解释如下：数据：数据是信息的载体，是计算机程序加工和处理的对象，包括数值数据和非数值数据。 数据项：数据项指不可分割的、具有独立意义的最小数据单位，数据项有时也称为字段或域。 数据元素:数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理, 一个数据元素可由若干个数据项组成。数据逻辑结构：数据的逻辑结构就是指数据元素间的关系。数据存储结构：数据的物理结构表示数据元素的存储方式或者数据元素的物理关系。数据类型：是指变ht的取值范围和所能够进行的操作的总和。算法：是
6、对特定问题求解步骤的种描述，是指令的有限序列。1.4语句的时间复杂度为：。(的。(盼。(殆O(n-l)(3) 。(砖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); elseif(Z=X)if(Y=Z) printf( “d, %d, %d”，Y,Z,X); else printf( “d, %d, %d”，Z,Y,X);else
7、 printf( d, %d, %d”，Y,X,Z);1.6参考程序：mainQint i,n;float x,a|J,p;printf( nn= );scanf( ，&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;.O(n)O(n)(4).n-i+1n-i(5).链式(6).数据指针.前驱后继(8).0(1)。(9) . s-next解题思路:将顺序表A中的元素输入数组a,若数组a中元素个数为n,将下标为0,1,2，, (n-1)
8、/2的元素依次与下标为，(n-1) /2的元素交换，输出数组a的元素。参考程序如下：main。(int i,n;floatprintf( nn= );scanf( %，&n);for(i=0;i =n-1 ;i+)scanf( f”，&ai);for(i=0;i=(n-l)/2;i+) t=ai; aij =an-l-i; an-l-ij=t;for(i=0;i=n-l ;i+)printf( %，ai)；2.4算法与程序：mainQint i,n;float t,aQ；printf( nn= );scanf( %f” ，&n);for(i=0;in;i+)scanf( %f ,&a国)；fo
9、r(i=l;in;i+) t=ai; ai =a0;a0=t;printf( f ,a0);fbr(i=2;in;i+)t=ai; ai =al;al=t;printf( %f” ,a0);2.5算法与程序: mainQint i,j,k,n;float x,t,a；printf( nx= );scanf( %广，&x);printf( nn= );scanf( %f ，&n); fbr(i=O;iVn;i+)scanf( f”，&ai);/输入线性表中的元素tor (i=0; in; i+) /对线性表中的元素递增排序k=i；for (j=i+l; jvn; j+) if (ajak) k=
10、j;if (kj) (t=ai;ai=ak;ak=t;)for(i=0;ix) break; for(k=n-l;k=i;i-)ak+l=ak;ai=x;for(i=0;i=n;i+)printf( ,ai);2.6算法思路：依次扫描A和B的元素，比较A、B当前的元素的值，将较小值的元素赋给 C,如此直到一个线性表扫描完毕，最后将未扫描完顺序表中的余下部分赋给C即可。C的 容量要能够容纳A、B两个线性表相加的长度。有序表的合并算法：void merge (SeqList A, SeqList B, Seql Jst *Q际 i, j, k；i=0； j=0； k=0；while (i=A.la
11、st & j=B.last)if (A.dataidatak+=A.datai+；elseC-datak+=B.dataj+；while (idatak+ = A.datai+；while (jdatak+=B.dataj+；C-last=k-l ；2.7算法思路：依次将A中的元素和B的元素比较，将值相等的元素赋给C,如此直到线性 表扫描完毕，线性表C就是所求递增有序线性表。算法：void tnerge (SeqList A, SeqList B, SeqList *C)血 i, j, k；i=0; j=0; k =0;while (idatak+=A.datai+；C-last = k-1;
12、习题3参考答案3.1.选择题. D (2). C (3). D (4). C (5). B (6). C (7). C (8). C (9). B (10).AB(I) . D (12). B (13). D (14). C (15). C (16). D(17). B (18). C (19). C (20). C 32填空题3.3答：一般线性表使用数组来表示的线性表一般有插入、删除、读取等对于任意元素的操作而栈只是一种特殊的线性表(1)FILO, FIFO(2)-1,34X* + 2Y*3/-(3)srack.top+, stack.sstack.top=x(4)pllink-rlink=
13、p-rlink, p-dink-llink=p-rlink(5)(R-F+M)%M(6)top! +I=top2(7)F=R(8)front=rcar(9)front=(rcar+l)%n(10)N-l栈只能在线性表的一端插入（称为入栈,push）或者读取栈顶元素或者称为“弹出、出 栈”（pop）。3.4答：相同点：栈和队列都是特殊的线性表，只在端点处进行插入，删除操作。不同点：栈只在一端（栈顶）进行插入，删除操作；队列在一端（砰）删除，一端（河）插 入。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(l),popO, push(2), push(3), pop。, push(4), push(5), popO, popO, pop。, push(6), pop。3.7 答：stack3.8非递归：int vonvcrt (int no,int a) 将十进制数转换为2进制存放在a,并返回位数 int r;SeStack s,*p;P=&s;
