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

数据结构基础及深入及考试复习资料习题及实验参考答案见附录结论1、数据的逻辑结构是指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据 的存储无关，是独立于计算机的。2、数据的物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。 它依赖于计算机。存储结构可分为4大类：顺序、链式、索引、散列3、抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构 成，并包括组相关的服务（或称操作）。它与数据类型实质上是一个概念，但其特征是使 用与实现分离，实行封装和信息隐蔽（独立于计算机）。4、算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换 为输出的计算步骤。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）/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、非空的循环单链表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)存储.变量的取值范围操作的类别.数据元素间的逻辑关系数据元素存储方式或者数据元素的物理关系.关系网状结构树结构(2) .空间复杂度和时间复杂度.空间时间. O(n)1.3名词解释如下：数据：数据是信息的载体，是计算机程序加工和处理的对象，包括数值数据和非数值数据。 数据项：数据项指不可分割的、具有独立意义的最小数据单位，数据项有时也称为字段或域。 数据元素:数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理, 一个数据元素可由若干个数据项组成。数据逻辑结构：数据的逻辑结构就是指数据元素间的关系。数据存储结构：数据的物理结构表示数据元素的存储方式或者数据元素的物理关系。数据类型：是指变ht的取值范围和所能够进行的操作的总和。算法：是对特定问题求解步骤的种描述，是指令的有限序列。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 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) /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国)；for(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=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.last & 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;习题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=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;Init_stack(p);while(no)(push(p,no%2);no/=10;r=0;whilc(!empty_stack(p)pop(p,a+r);r+;return r;递归算法：void convert(in t no)(if(no/20)Convert(no/2);Printf( d” ,no%2);elseprintf( ,no);3.9参考程序：void view(SeStack s)SeStack *p; 假设栈元素为字符型char c;p=&s;while(!empty_stack(p)c=pop(p);printf( %c” ,c);printff nw );3.10 答：char3.11参考程序：void outflinkqucuc q)int c;while(q.rear !=q.front) dcqucuc(q,c);print(e); 打印习题4参考答案4.1选择题：.A (2). D (3). C (4). C (5). B (6). B 4.2填空题：(7). D (8). A (9). B (10). D(1) 串长相等且对应位置字符相等不含任何元素的串，0所含字符均是空格，所含空格数10(2) hclloboy”181066由零个或多个任意字符组成的字符序列(3) 串中所含不同字符的个数36StrLcngth (s)=14, StrLcngth (t)=4, SubStr( s, 8,7)= STUDENT”，SubStr(t, 2, 1)=” O”， Strlndcx(s, “A” )=3, Strindex (s, t)=0, StrRcp(s, “STUDENT”，q)=” I AM A WORKER,StrRcp(s, Y” + );StrRcp(s,*Y” );4.5空串：不含任何字符；空格串：所含字符都是空格串变量和串常量:串常量在程序的执行过程中只能引用不能改变；串变量的值在程序执行过 程中是可以改变和重新赋值的主串与子串：子串是主串的一个子集串变量的名字与串变量的值:串变量的名字表示串值的标识符4.6int EQUA1(S；Ochar *p,*q;p=&S;q=&T； while(*p&*q)if(*P=*q) rcuirn *p-*q;)+；q+；return *p-*q;4.76*8*6=2881000+47*6=12821000+(8+4)*6=1072(1) 1000+(6*7+4)*6=12764.8矩阵的三元组表ijVi121215-I32144347542665187539习题5参考答案5.1选择(1) C (2) B (3) C (4) B (5) C (6) D (7) C (8) C (9) B (10) C(4) B (12) C (13) C (14) C (15) C5.2填空(1) 1(2) 1036； 1040(3) 2i(4) ； n ;n-1;2(5) 坦；2M(6)(7)(8)(9)ACDBGJKIHFEp!=NULLHuffrnan 树其第一个孩子;下一个兄弟(10) 先序遍历;中序遍历5.3叶子结点:C、F、G、L、I、M、K; 非终端结点：A、 各结点的度： 结点： 度：B、D、E、J;L I J K M0100树深:5.4无序树形态如下:OAYO二叉树形态如下:5.5二叉链表如下:A、0（1） B、O（n） C、OS2） D、O（nlogjn）9、在一个单链表中，若删除p所指结点的后继结点，则执行（A ）A、p-next=p-next-next;B、p=p-next;p-ncxt=p-next-ncxt;C、p-next=p-next;D、p= p-next-next;10、在一个单链表中，若在p所指结点之后插入s所指结点，则执行（B ）A、s-next=p;p-next=s;B、s-ncxt=p-ncxt;p-ncxt=s;C、s-next=p-next;p=s;D、p-ncxt=s;s-ncxt=p;11、在一个单链表中，已知q是p的前趋结点，若在q和p之间插入结点s,则执行（C ）A、s-next=p-ncxt;p-ncxt=s;13、p-next=s-next;s-next=p;C、q-next=s;s-next=p;D、p-ncxt=s;s-ncxt=q;12、在线性结构中，第一个结点没有前趋结点，其余每个结点有且只有1 个前趋结点。栈和队列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.basc0B、Sl.top=ST.basc=0C、ST.top=ST.basenD、ST.top=ST.base=n3、向一个栈顶指针为HS的链栈中插入一个s结点时，执行（C ）A、HS-next=s;s-next=HS-next;HS-next=s;C、s-next=HS;HS=S;D、s-next=HS;HS=HS-next;4、从一个栈顶指针为HS的链栈中删除一个结点，用x保存被删结点的值，则执行（C ）A、x=HS;HS=HS-next;HS=HS-next;x=HS-data;C、x=HS-data;HS=HS-ncxt; D、s-ncxt=HS;HS=HS-ncxt;5、用单链表表示的链示队列的队头在链表的（ A ）位置。A、链头 B、链尾 C、链中6、判定一个链队列Q （最多元素个数为n）为空的条件是（ A ）A、Q.front=Q.rearB、Q.front!=Q.rcarC、Q.front=（Q.rear+ l）%nD、Q.front!=（Q.rear+l）%n7、在链队列Q中，插入要所指结点需顺序执行的指令是（B ）A、Q.front-ncxt=s;f=s;Bn Q.rear-next=s;Q.rear=s;C、s-ncxt=Q.rcar;Q.rcar=s;D、s-next=Q.front;Q.front=s;5.6先序遍历序列:ABDEM1CIJG 中序遍历序列:DBHEIAFJCG 后序遍历序列:DIUE BJFGCA 5.7(1) 先序序列和中序序列相同：空树或缺左子树的单支树；(2) 后序序列和中序序列相同：空树或缺右子树的单支树；(3) 先序序列和后序序列相同：空树或只有根结点的二叉树。5.8这棵二叉树为:5.9先根遍历序列:ABiGLCDlEJMK后根遍历序列:FGLBCIDMJKEA层次遍历序列:ABCDEFGLIJKM5.10证明：设树中结点总数为n,叶子结点数为n。，则n=n0 + rij +nm(1)再设树中分支数目为B,则B=ri| + 2。2 + 3r)3 + m nm(2)因为除根结点外，每个结点均对应一个进入它的分支，所以有 n=B + 1(3)将和(2)代入(3),得rin + n】+ nm = rij + 2。2 + 3由 +m nm + 1从而可得叶子结点数为：n0 = n2 + 2n.3 +(m-l)nrn + 15.11由5.10结论得，山二-1加+1乂由 n=n0+ nk , nk= n-n0,代入上式，得n(l= (k-1) (n-no) + 1叶子结点数为：ntl=n(k-l)/k5.12int NodeCount(BiTrec T)计算结点总数if (T- lchild=NULL)&(T- rchikl=NULL)return 1;elsereturn NodeCount(T- Ichild ) +Node (T rchild )+1;elsereturn 0;5.13void ExchangeLR(Bitree bt)(/*将bt所指二叉树中所有结点的左、右子树相互交换*/if (bt & (bt-lchild | | bt-rchild) (bt-lchildbt-rchild;Exchangc-lr(bt-lchild);Exchange-lr(bt-rchild);/* ExchangeLR */5.14int IsFullBitrec(Birree T)(/*是则返回1,否则返回Oo */Init_Qucue(Q); /* 初始化队列*/flag=0;In_Queue(Q, T);/*根指针入队列，按层次遍历*/while(!Empty_Queuc (Q)(Out_Queue(Q,p);if(!p) flag=1; /*若本次出队列的是空指针时，则修改flag值为1。若以后出队列的指针 存在非空，则可断定不是完全二叉树*/else if (fl疫)return 0; /*断定不是完全二叉树*/elseIn_Queue(Q, p-lchild);In_Queue(Q, p-rchild);/*不管孩子是否为空，都入队列。*/* while */return 1; /*只有从某个孩子指针开始，之后所有孩子指针都为空，才可断定为完全二叉 树*/* IsFullBitree */5.15转换的二叉树为：BG乙O (S) O(c)Be)(a)5.16对应的森林分别为:B(d)5.17typedeF char elemtype;typcdcf struct elemtype data;int parent; NodeType;求树中结点双亲的算法：inr Parent(NodcType t, elemtype x)/* x不存在时返回2否则返回x双亲的下标(根的双亲为-1 */ for(i=0;iMAXN()DE;i+)if(x=ti.data) return t(i.parent;return -2;/*Parent*/求树中结点孩子的算法：void Childrcn(NodcTypc t, elemtype x)( for(i=0;i=MAXNODE) printf( “x 不存在n” );else flag=0；fbrO=0;j=MAXNODE) return -2; /* x 不存在 */*搜索x的双亲*/for(i=0;inextchild)if(loc=p-childcode)return i; /*返回x结点的双亲下标*/ /* ParentL */(2)求树中结点孩子的算法：void ChildrenCL(NodeTpe t , clcmtypc 对for(i=0;inextchild)( printf( x 的孩子:%cnw ,tp- childcodc.data);flag=l;if(flag=0) printf( x 无孩子n)； return;)/*if*/printF( x 不存在n” )；return;/* ChildrcnL */5.19typedef char el cm type;typedef struct TreeNode el em type data;struct TrccNodc *firstchild;struct TreeNode *nextsibling; NodcTypc;void ChildrenCSL(NodeType *t, elemtype 对/* 层次遍历方法 */Init_Queue(Q); /* 初始化队列 */ln_Queue(Q,t);count=0;vhile(!Empty_Qucuc (Q) ()ut_Queue(Q,p);if(p-data=x) /*输出x的孩子*/p=p-firstchild;if(!p) printf(无孩子n)；else printf( x 的第i 个孩子:cn ,+count, p-data);/*输出第一个孩子*/ p=p-nextsibling; /*沿右分支*/whilc(p) printf( x 的第i 个孩子:%cn” , +count, p-data);p=p- nextsibling;return;if(p- firstchild) ln_Qucuc(Q,p- firstchild);if(p- nextsibling) ln_Qucuc(Q,p- nextsibling);/* ChildrenCSL */5.20哈夫曼树为:(2)在上述哈夫曼树的每个左分支上标以1,右分支上标以0,并设这7个字母分别为A、B、C、D、E、F和H,如下图所示：则它们的哈夫曼树为分别为:A: 1100B: 1101C: 10D: OilE: 00F: 010H: 111习题6参考答案条边。(6) B (7) A (8) A (9) B (10) A 6) A (17) C6.1选择题(I) C (2) A (3) B (4) C (5) B(II) A (12) A (13) B (14) A (15) B6.2填空(1) 4(2) 1对多 ； 多对多(3) n-1; n(4) _J(5) 有向图(6) _J(7) 一半(8) 一半(9) 第i个链表中边表结点数(10) _第i个链表中边表结点数_(10深度优先遍历;广度优先遍历(5) C (/)(6) 无回路6.3(1)邻接矩阵：0111010011100011100101110(2)邻接链表:01234每个顶点的度:顶点度VI3V23V32V43V536.4(1)邻接链表:VIAV2V3V4V5V61234503| 5-| 5-L 2.A_-4-L_i_逆邻接链表:123452/(3)顶点 入度出度VIV2V3V4321102238、在一个链队列Q中，删除一个结点需要执行的指令是（C ）A、Q.rear=Q.front-next;B、Q.rear-next=Q.rear-next-next;C、Q.front-ncxt=Q.front-next-ncxt;D、Q. fron t=Q.rear-next;9、栈和队列的共同点（C ）A、都是先进后出B、都是先进先出C、只允许在端点处插入和删除元素D、没有共同点10、栈的特点是先进后出，队列的特点是先进先出11、线性表、栈和队列都是线性结构，可以在线性表的任何位置插入和删除元素；对于栈只 能在栈顶插入和删除元素；对于队列只能在队尾插入元素和在队首删除元素。串和数组1、设串 si=ABCDEFG ,s2=PQRST，函数Concat（x,y）返回 x和y 串的连接串,Substr（s,l,j） 返回串s从序号i开始的j个字符组成的子串，length（s）返Is!串s的长度，则Concat（Substr（sl,2, length（s2）, Substr（slJength（s2）,2）的结果串是（D ）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、5 D、63、在一棵有n个结点的二叉树中，若度为2的结点数为n2,度为1的结点数为n】，度为0 的结点数为所，则树的最大高度为（E ），其叶结点数为（ G ）；树的最小高 度为（B ）,其叶结点数为（ G ）;若采用链表存储结构，则有（I ） 个空链域。A、n/2 B、logjn + lC、logjn D、n E、n（）+ni + ri2 F、n】+ n?G、n2 +1 H、1 I、n+1 J、n】 K、n? L、n】+14、在一棵二叉树上第5层的结点数最多为（B ）。（假设根结点的层数为0）A、8 B、16 C、15 D、325、深度为5的二叉树至多有（C ）个结点。A、16 B、32 C、31 D、106、在一非空二叉树的中序遍历序列中，根结点的右边（ A ）A、只有右子树上的所有结点 B、只有右子树上的部分结点V5V66.5(1) 深度优先查找遍历序列:VI V2 V3 V4 V5; VI V3 V5 V4 V2; VI V4 V3 V5 V2(1) 广度优先查找遍历序列:VI V2 V3 V4 V5; VI V3 V2 V4 V5; VI V4 V3 V2 V56.66.66.66.7最小生成树的示意图如下:最小生成树的示意图如下:6.8顶 点(1)(2)(3)(4)(5)Low CloseI -ow CloseLow CloseIxw CloseLow CloseVI0101010101V21 101010101V31 11 1010101V43122220202V5co 152332404Uvlvl,v2(vl,v2,v3vl, v2, v3, v4)(vl, v2, v3, v4, v5T( (vl,v2) 2),(vl,v3) (vl,v2),(vl,v3), (v2,v4) (v1,v2),(vl,v3), (v2,v4), (v4,v5) 拓扑排序结果：V3 V1 V4 V5 V2 V66.9建立无向图邻接矩阵算法：提示：参见算法6.1因为无向图的邻接矩阵是对称的，所以有for (k=0; ke; k+) /*输入e条边，建立无向图邻接矩阵*/ scanf(n%d,%d”,&i,&j);G-edgesij= G-edgpsji= 1;建立无向网邻接矩阵算法：提示：参见算法6.1 o初始化邻接矩阵：#dcfinc INFINITY 32768 /* 表示极大值*/for(i=03n;i+)for(j=0;jn;j+) G-cdgesij= INFINITY;输入边的信息：不仅要输入边邻接的两个顶点序号，还要输入边上的权值for (k=0; kc; k+) /*输入c条边，建立无向网邻接矩阵*/ scanf(”n%d,%d,%d”,&i,&j,&ccst); /* 设权值为 int 型*/G -cdgcsij= G -cdgcsj(i=cost;/*对称矩阵*/(3)建立有向图邻接矩阵算法：提示：参见算法6.1。6.10建立无向图邻接链表算法：typcdef VcrtexType char;int Create_NgAdjList(ALGraph *G)/*输入无向图的顶点数、边数、顶点信息和边的信息建立邻接表*/scanfC%d,&n); if(nn=n;scanfCWdC&e); if(ee=e;for(m=0;mn ;m+)G- adjlist lm.firstcdgc=NULL; /*置每个单链表为空表*/fc)r(m=0;mn;m+)G-adjlistm.vcrtcx=gctchar(); /*输入各顶点的符号*/ fc)r(m=l;me; m+)scanf( n%d, %d ,&i,&j);/* 输入一对邻接顶点序号*/if(ivO | | jadjvex=j;p-next= G- adjlist i.firstedge;G- adjlist i