数据结构(C语言版)第5章 数组和广义表

严蔚敏数据结构课后习题及答案解析数据结构课程是计算机科学与技术专业中非常重要的一门基础课程，对于学习者来说，课后习题的巩固和答案解析是学习的重要辅助材料。

本文将针对严蔚敏老师所著的《数据结构（C语言版）》中的课后习题及答案解析进行介绍和总结。

1. 第一章：绪论（略）2. 第二章：线性表（略）3. 第三章：栈和队列3.1 课后习题3.1.1 课后习题一：给定一个整数序列，请设计一个算法，其中删除整数序列中重复出现的元素，使得每个元素只出现一次。

要求空间复杂度为O(1)。

3.1.2 课后习题二：使用栈操作实现一个队列（其中队列操作包括入队列和出队列）。

3.2 答案解析3.2.1 答案解析一：我们可以使用双指针法来实现这一算法。

设定两个指针，一个指向当前元素，另一个指向当前元素的下一个元素。

比较两个元素是否相等，如果相等，则删除下一个元素，并移动指针。

如果不相等，则继续移动指针。

这样，当指针指向序列的最后一个元素时，算法结束。

空间复杂度为O(1)，时间复杂度为O(n)。

3.2.2 答案解析二：使用两个栈来实现一个队列。

一个栈用于入队列操作，另一个栈用于出队列操作。

当需要入队列时，将元素直接入栈1。

当需要出队列时，判断栈2是否为空，如果为空，则将栈1中的元素逐个弹出并压入栈2中，然后从栈2中弹出栈顶元素。

如果栈2非空，则直接从栈2中弹出栈顶元素。

这样，就可以实现使用栈操作来实现队列操作。

4. 第四章：串（略）5. 第五章：数组和广义表（略）6. 第六章：树和二叉树（略）7. 第七章：图（略）通过对严蔚敏老师所著《数据结构（C语言版）》中的课后习题及答案解析的介绍，可以帮助学习者更好地理解和掌握数据结构这门课程的知识内容。

课后习题不仅可以帮助巩固所学知识，更加于提升学习者的能力和应用水平。

希望本文对于学习者们有所帮助。

（文章结束）。

第五章数组和广义表一．选择题1．在二维数组A 中引用A[i,j]的时间_________。

A．与i、j的大小有关B．与i、j的大小无关C．与i的大小有关，与j的大小无关D．与i的大小无关，与j的大小有关2．在稀疏矩阵的带行指针向量的链接存储中，每一行单链表中的结点都具有相同的________。

A．行号 B．列号 C．元素值 D.地址3．二维数组A 按行顺序存储，其中每个元素占1个存储单元。

若 A[1][1]的存储地址为420， A[3][3]的存储地址为446，则A[5][5]的存储地址为_______。

A．470 B．471 C．472 D. 4734．在稀疏矩阵的十字链接存储中，每个列单链表中的结点都具有相同的_____。

A．行号 B．列号 C．元素值 D.地址5．下面的说法中，不正确的是________。

A．对称矩阵中只须存放包括主对角线元素在内的下(或上)三角部分的元素即可B．对角矩阵中只须存放的非零元素即可C．稀疏矩阵中值为零的元素较多，因此可以采用三元组表方法存储D．稀疏矩阵中大量值为零的元素分布有规律，因此可以采用三元组表方法存储6．对一些特殊矩阵采用压缩存储的目的主要是为了________。

A．表达变得简单 B．对矩阵元素的存取变得简单C．去掉矩阵中的多余元素 D．减少不必要的存储空间的开销7．若将n 阶对称矩阵 A 按照行序为主序方式将包括主对角线元素在内的下三角形的所有元素依次存放在一个一维数组 B 中，则该对称矩阵在 B 中占用了________个数组元素。

A．n2 B．n*(n-1) C．n*(n+1)／2 D．n*(n-1)8. 稀疏矩阵的三元组顺序表表示的一个三元组中不包括________。

A. 行号B.列号C.元素值D.元素总数9．稀疏矩阵一般的压缩存储方法有两种，即________。

A．二维数组和三维数组 B．三元组和散列C. 三元组和十字链表 D．散列和十字链表10．有一个 10 阶对称矩阵 A，采用压缩存储方式(以行序为主存储，且A[0 Ⅱ0]=1)，则A[8][5]的地址是________。

《数据结构与算法》第五章数组和广义表本章介绍的数组与广义表可视为线性表的推广，其特点是数据元素仍然是一个表。

本章讨论多维数组的逻辑结构和存储结构、特殊矩阵、矩阵的压缩存储、广义表的逻辑结构和存储结构等。

5.1 多维数组5.1.1 数组的逻辑结构数组是我们很熟悉的一种数据结构，它可以看作线性表的推广。

数组作为一种数据结构其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型，比如：一维数组可以看作一个线性表，二维数组可以看作“数据元素是一维数组”的一维数组，三维数组可以看作“数据元素是二维数组”的一维数组，依此类推。

图5.1是一个m行n列的二维数组。

5.1.2 数组的内存映象现在来讨论数组在计算机中的存储表示。

通常，数组在内存被映象为向量，即用向量作为数组的一种存储结构，这是因为内存的地址空间是一维的，数组的行列固定后，通过一个映象函数，则可根据数组元素的下标得到它的存储地址。

对于一维数组按下标顺序分配即可。

对多维数组分配时，要把它的元素映象存储在一维存储器中，一般有两种存储方式：一是以行为主序（或先行后列）的顺序存放，如BASIC、PASCAL、COBOL、C等程序设计语言中用的是以行为主的顺序分配，即一行分配完了接着分配下一行。

另一种是以列为主序（先列后行）的顺序存放，如FORTRAN语言中，用的是以列为主序的分配顺序，即一列一列地分配。

以行为主序的分配规律是：最右边的下标先变化，即最右下标从小到大，循环一遍后，右边第二个下标再变，…，从右向左，最后是左下标。

以列为主序分配的规律恰好相反：最左边的下标先变化，即最左下标从小到大，循环一遍后，左边第二个下标再变，…，从左向右，最后是右下标。

例如一个2×3二维数组，逻辑结构可以用图5.2表示。

以行为主序的内存映象如图5.3（a）所示。

分配顺序为：a11 ，a12 ，a13 ，a21 ，a22，a23 ; 以列为主序的分配顺序为：a11 ，a21 ，a12 ，a22，a13 ，a23 ; 它的内存映象如图5.3（b）所示。

数据结构数组与广义表知识点总结数组是一种线性数据结构，可以存储多个相同类型的元素。

它的特点是元素的大小固定，并且在内存中是连续存储的。

数组的访问方式是通过下标来访问，下标从0开始。

数组可以在编程中应用于各种情况，比如存储一组数字、一组字符串等。

广义表是一种扩展的线性数据结构，可以存储不同类型的元素。

它由元素和表构成，其中表可以是空表、原子或子表。

广义表可以递归定义，即子表可以包含更多的子表。

广义表的访问方式是通过递归来访问，可以对表的元素进行遍历和操作。

在数据结构中，数组和广义表都有自己的特点和用途，下面对它们的知识点进行总结：1.数组的特点及应用：-数组是一种线性数据结构，可以存储多个相同类型的元素。

-数组的内存分配是连续的，可以通过下标来访问元素。

-数组的大小固定，一旦定义后不能改变。

-数组的访问速度快，可以通过下标直接访问元素。

-数组适合用于存储一组相同类型的数据，比如一组数字、一组字符串等。

-数组的应用场景包括但不限于：排序算法、查找算法、图像处理、矩阵运算等。

2.数组的操作和常用算法：-初始化：可以直接赋值或使用循环初始化数组。

-访问元素：通过下标访问元素，下标从0开始。

-修改元素：直接通过下标修改元素的值。

-插入元素：需要移动插入位置之后的元素。

-删除元素：需要移动删除位置之后的元素。

-查找元素：可以使用线性查找或二分查找等算法。

-排序算法：比如冒泡排序、选择排序、插入排序等。

-数组还有一些常用的属性和方法，比如长度、最大值、最小值等。

3.广义表的特点及应用：-广义表是一种扩展的线性数据结构，可以存储不同类型的元素。

-广义表由元素和表构成，表可以是空表、原子或子表。

-广义表可以递归定义，即子表可以包含更多的子表。

-广义表的访问方式是通过递归遍历和操作。

-广义表适合存储一组不同类型的数据，比如存储学生信息、函数调用栈等。

-广义表的应用场景包括但不限于：函数式编程、树的表示、图的表示等。

第五章 数组和广义表一、选择题1、设广义表L=((a ，b ，c))，则L 的长度和深度分别为（ ）。

A. 1和1B. 1和3C. 1和2D. 2和32、广义表((a),a)的表尾是（ ）。

A. aB. (a)C. ()D. ((a))3、设有一个10阶的对称矩阵A ，采用压缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为1，每元素占1个地址空间，则a85的地址为（ ）。

A. 13B. 33C. 18D. 404、一个非空广义表的表头（ ）。

A. 不可能是子表B. 只能是子表C. 只能是原子D. 可以是子表或原子5、设矩阵A 是一个对称矩阵，为了节省存储，将其下三角部分按行序存放在一维数组B[1,n(n-1)/2]中，对下三角部分中任一元素ai,j(i>=j)，在一维数组B 的下标位置k 的值是（ ）。

A. i(i-1)/2+j-1B. i(i-1)/2+jC. i(i+1)/2+j-1D. i(i+1)/2+j6、广义表G=(a,b(c,d,(e,f)),g)的长度是（ ）。

A. 3B. 4C. 7D. 87、采用稀疏矩阵的三元组表形式进行压缩存储，若要完成对三元组表进行转置，只要将行和列对换，这种说法（ ）。

A. 正确B. 错误C. 无法确定D. 以上均不对8、常对数组进行两种基本操作是（ ）。

A. 建立和删除B. 索引和修改C. 查找和修改D. 查找与索引9、对一些特殊矩阵采用压缩存储的目的主要是为了（ ）。

A. 表达变得简单B. 对矩阵元素的存取变得简单C. 去掉矩阵中的多余元素D. 减少不必要的存储空间的开销 10、假设以三元组表表示稀疏矩阵，则与如图所示三元组表对应的4×5的稀疏矩阵是（注：矩阵的行列下标均从1开始）（ ）。

A. ⎪⎪⎪⎪⎪⎭⎫ ⎝⎛--00405000000000706080 B. ⎪⎪⎪⎪⎪⎭⎫ ⎝⎛--00000004053000706080 C. ⎪⎪⎪⎪⎪⎭⎫ ⎝⎛--00405000073000006080D. ⎪⎪⎪⎪⎪⎭⎫ ⎝⎛--00000304050000706080二、判断题1、广义表中原子个数即为广义表的长度。

第五章数组与广义表一、假设有二维数组A6*8，每个元素用相邻的6个字节存储，存储器按字节编址。

已知A的起始存储位置（基地址）为1000。

计算：1、数组A的体积（即存储量）；2、数组A的最后一个元素a57的第一个字节的地址；3、按行存储时，元素a14的第一个字节的地址；4、按列存储时，元素a47的第一个字节的地址；答案：1、（6*8）*6=2882、loc(a57)=1000+(5*8+7)*6=1282或=1000+（288-6）=12823、loc(a14)=1000+(1*8+4)*6=10724、loc(a47)=1000+(7*6+4)*6=1276二、假设按低下标(行优先)优先存储整数数组A9*3*5*8时第一个元素的字节地址是100，每个整数占四个字节。

问下列元素的存储地址是什么？（1）a0000(2)a1111(3)a3125 (4)a8247答案：（1）100（2）loc(a1111)=100+(1*3*5*8+1*5*8+1*8+1)*4=776(3) loc(a3125)=100+(3*3*5*8+1*5*8+2*8+5)*4=1784(4) loc(a8247)=100+(8*3*5*8+2*5*8+4*8+7)*4=4416五、设有一个上三角矩阵（aij）n*n,将其上三角元素逐行存于数组B[m]中，（m 充分大），使得B[k]=aij且k=f1(i)+f2(j)+c。

试推导出函数f1,f2和常数C（要求f1和f2中不含常数项）。

答：K=n+(n-1)+(n-2)+…..+(n-(i-1)+1)+j-i=(i-1)(n+(n-i+2))/2+j-i所以f1(i)=(n+1/2)i-1/2i2f2(j)=jc=-(n+1)九、已知A为稀疏矩阵，试从空间和时间角度比较采用两种不同的存储结构（二维数组和三元组表）完成∑aii运算的优缺点。

（对角线求和）解：1、二维数组For(i=1;i<=n;i++)S=s+a[i][i];时间复杂度：O（n）2、for(i=1;i<=m.tu;i++)If(a.data[k].i==a.data[k].j) s=s+a.data[k].value;时间复杂度：O（n2）二十一、当稀疏矩阵A和B均以三元组表作为存储结构时，试写出矩阵相加的算法，其结果存放在三元组表C中。

数据结构05数组与广义表数组与广义表可以看做是线性表地扩展,即数组与广义表地数据元素本身也是一种数据结构。

5.1 数组地基本概念5.2 数组地存储结构5.3 矩阵地压缩存储5.4 广义表地基本概念数组是由相同类型地一组数据元素组成地一个有限序列。

其数据元素通常也称为数组元素。

数组地每个数据元素都有一个序号,称为下标。

可以通过数组下标访问数据元素。

数据元素受n(n≥1)个线性关系地约束,每个数据元素在n个线性关系地序号 i1,i2,…,in称为该数据元素地下标,并称该数组为n维数组。

如下图是一个m行,n列地二维数组A矩阵任何一个元素都有两个下标,一个为行号,另一个为列号。

如aij表示第i行j列地数据元素。

数组也是一种线性数据结构,它可以看成是线性表地一种扩充。

一维数组可以看作是一个线性表,二维数组可以看作数据元素是一维数组（或线性表）地线性表,其一行或一列就是一个一维数组地数据元素。

如上例地二维数组既可表示成一个行向量地线性表: A1=(a11,a12,···,a1n)A2=(a21,a22, ···,a2n)A=(A1,A2, ···,Am) ············Am=(am1,am2, ···,amn)也可表示成一个列向量地线性表:B1=(a11,a21,···,am1)B2=(a12,a22, ···,am2)A=(B1,B2, ···,Bm) ············Bn=(a1n,a2n, ···,amn)数组地每个数据元素都与一组唯一地下标值对应。

严蔚敏《数据结构（C语言版）习题集》答案第一章绪论void print_descending(int x,int y,int z)....+f[m-k]=f[m-1]+f[m-2]+......+f[m-k]+f[m-k-1]-f[m-k-1]=2*f[m-1]-f[m-k-1]所以上述算法的时间复杂度仅为O(m). 如果采用递归设计,将达到O(k^m). 即使采用暂存中间结果的方法,也将达到O(m^2).typedef struct{char *sport;enum{male,female} gender;char schoolname; port!=NULL){switch(result[i].schoolname){case 'A':score[ 0 ].totalscore+=result[i].score;if(result[i].gender==0) score[ 0 ].malescore+=result[i].score;else score[ 0 ].femalescore+=result[i].score;break;case 'B':score[ 0 ].totalscore+=result[i].score;if(result[i].gender==0) score[ 0 ].malescore+=result[i].score;else score[ 0 ].femalescore+=result[i].score;break;………………}i++；}for(i=0;i<5;i++){printf("School %d:\n",i);printf("Total score of male:%d\n",score[i].malescore);printf("Total score of female:%d\n",score[i].femalescore);printf("Total score of all:%d\n\n",score[i].totalscore);}}void polyvalue(){float temp;float *p=a;printf("Input number of terms:");scanf("%d",&n);printf("Input value of x:");scanf("%f",&x);printf("Input the %d coefficients from a0 to a%d:\n",n+1,n);p=a;xp=1;sum=0;Status Insert(LinkList &L,int i,int b)void merge1(LinkList &A,LinkList &B,LinkList &C)void SqList_Intersect(SqList A,SqList B,SqList &C)void LinkList_Intersect_Delete(LinkList &A,LinkList B,LinkList C)iList为带头结点的单循环链表类型.{s=L->next;A=(CiList*)malloc(sizeof(CiLNode));p=A;B=(CiList*)malloc(sizeof(CiLNode));q=B;C=(CiList*)malloc(sizeof(CiLNode));r=C; .4,2的顺序重排双向循环链表L中的所有结点{p=;while(p->next!=L&&p->next->next!=L){p->next=p->next->next;p=p->next;} 同时进行调整的话,必须使用堆栈保存偶数结点的指针,否则将会破坏链表结构,造成结点丢失.DuLNode * Locate_DuList(DuLinkedList &L,int x) int x;int y;} coordinate;void Repaint_Color(int g[m][n],int i,int j,int color)归形式的算法该怎么写呢?void NiBoLan(char *str,char *new)题中暂不考虑串的具体操作的实现,而将其看作一种抽象数据类型stringtype,对其可以进行连接操作:c=link(a,b).Status g(int m,int n,int &s)void InitCiQueue(CiQueue &Q)Status EnCyQueue(CyQueue &Q,int x)省掉这一句,则在某些情况下,会引起不希望的后果,虽然在大多数情况下没有影响.请思考:设S='place', T='ace', V='face',则省掉i+=Strlen(V);运行时会出现什么结果?int Delete_SubString(Stringtype &s,Stringtype t)读者用此程序取代作者早些时候对题给出的程序.void StrAssign(Stringtype &T,char chars&#;)h&&T[j].ch!=c) j++; h) T[j].num++;else T[j]={c,1};}h;j++)printf("%c: %d\n",T[j].ch,T[j].num);}前一个程序的区别在于,串s业已存在.{for(p=s->next,q=t->next;p&&q;p=p->next,q=q->next){p->ch=q->ch;pre=p;}while(q){p=(LStrNode*)malloc(sizeof(LStrNode));p->ch=q->ch;pre->next=p;pre=p;}p->next=NULL;}算法的思想是,依次把串S的一个副本S2向右错位平移1格,2格,3格,...与自身S1相匹配,如果存在最长重复子串,则必然能在此过程中被发现.用变量lrs1,lrs2,maxlen来记录已发现的最长重复子串第一次出现位置,第二次出现位置和长度.题目中未说明"重复子串"是否允许有重叠部分,本算法假定允许.如不允许,只需在第二个for语句的循环条件中加上k<=i即可.本算法时间复杂度为O(Strlen(S)^2).void Get_LPubSub(Stringtype S,Stringtype T) for(k=0,j=jmin;j<=jmax;j++){if(A[j]==B[j-i]) k++;else k=0;if(k>maxlen){lps1=j-k+1;lps2=j-i-k+1;maxlen=k;}}一的区别是,由于A,B互不相同,因此B不仅要向右错位,而且还要向左错位,以保证不漏掉一些情况.当B相对于A的位置不同时,需要匹配的区间的计算公式也各不相同,请读者自己画图以帮助理解.本算法的时间复杂度是o（strlrn（s）*strlen（t））。

习题五数组和广义表一、单项选择题1．常对数组进行的两种基本操作是（）A.建立与删除B. 索引与修改C. 查找与修改D. 查找与索引2．对于C语言的二维数组DataType A[m][n],每个数据元素占K个存储单元，二维数组中任意元素a[i,j] 的存储位置可由( )式确定.A.Loc[i,j]=A[m,n]+[(n+1)*i+j]*kB.Loc[i,j]=loc[0,0]+[(m+n)*i+j]*kC.Loc[i,j]=loc[0,0]+[(n+1)*i+j]*kD.Loc[i,j]=[(n+1)*i+j]*k3．稀疏矩阵的压缩存储方法是只存储 ( )A.非零元素B. 三元祖（i,j, aij）C. aijD. i,j4. 数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是( )。

A. 1175B. 1180C. 1205D. 12105. A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N（N+1）/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（）。

A. i（i-1）/2+jB. j（j-1）/2+iC. i（j-i）/2+1D. j（i-1）/2+16. 用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j 沿链移动的操作为( )。

A. j=r[j].nextB. j=j+1C. j=j->nextD. j=r[j]-> next7. 对稀疏矩阵进行压缩存储目的是（）。

A．便于进行矩阵运算 B．便于输入和输出C．节省存储空间 D．降低运算的时间复杂度8. 已知广义表LS＝((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是( )。

A. head(tail(LS))B. tail(head(LS))C. head(tail(head(tail(LS)))D. head(tail(tail(head(LS))))9. 广义表（（a,b,c,d））的表头是（），表尾是（）。