当前位置：文档之家 › 数据结构第4章 数组和广义表

数据结构第4章 数组和广义表

  • 格式：doc
  • 大小：46.00 KB
  • 文档页数：4

第4章数组和广义表【例4-1】二维数组A的每一个元素是由6个字符组成的串，其行下标i=0，1，…，8，列下标j=1，2，…，10。

若A以行为主序存储元素，A[8][5]的物理地址与当A按列为主序存储时的元素（）的物理地址相同。

设每个字符占一个字节。

A．A[8][5] B．A[3][10] C．A[5][8] D．A[0][9]解：二维数A是一个9行10列的矩阵，即A[9][10]。

按行存储时，A[8][5]是第85个元素存储的元素。

而按列存储时，第85个存储的元素是A[3][10]。

即正确答案为B。

【例4-2】若对n阶对称矩阵A以行序为主序方式将其下三角形的元素（包括主对角线上所有元素）依次存放于一维数组B[n（n+1）/2]中，则在B中确定的位置k的关系为（）。

A．jii+-2)1(*B．ijj+-2)1(*C．jii++2)1(*D．ijj++2)1(*解：如果a ij按行存储，那么它的前面有i-1行，其有元素个数为：1+2+3+…+（i-1）=i（i-1）/2。

同时它又是所在行的第j列，因此它排列的顺序还得加上j，一维数组B[n(n+1)/2]中的位置k与其下标的关系是：jii+-2)1(*。

因此答案为A。

【例4-3】已知n阶下三角矩阵A，按照压缩存储的思想，可以将其主对角线以下所有元素（包括主对角线上元素）依次存放于一维数组B中。

请写出从第一列开始以列序为主序分配方式时在B中确定元素a ij的存放位置的公式。

解：如果a ij按列存储，那么它的前面有j-1列，共有元素：n+(n-1)+(n-2)+ …+[n-(j-2)]=(j-1)*n-2)1)(2(--jj而它又是所在列的第i行，因此在它前的元素个数还得加上i。

因此它在一维数组B中的存储顺序为：(j-1)*n-2)1)(2(--jj+i【例4-4】已知广义表L=((x,y,z),a,(u,t,w))，从L表中取出的原子项ASCII码最大的运算是（）。

A．head(tail(tail(L)))B．tail(head(head(tail(L))))C．head(tail(tail(head(L))))D．head(tail(tail(tail(L))))解：选项A的结果是字符串“u”；选项B的结果是空表，无字符；选项C的结果是字符“z”；选项D的结果是字符“t”。

从所有选项的结果可以看出，ASCII码最大的是字符“z”。

因此正确答案是C。

习题4一、单项选择题1.设二维数组A[0…m-1][0…n-1]按行优先顺序存储在内存中，第一个元素的地址为p，每个元素占k个字节，则元素a ij的地址为（ 1. A）。

A.p +[i*n+j-1]*kB.p+[(i-1)*n+j-1]*kC.p+[(j-1)*n+i-1]*kD.p+[j*n+i-1]*k2.已知二维数组A10×10中，元素a20的地址为560，每个元素占4个字节，则元素a10的地址为（ 2. A）。

A.520B.522C.524D.5183.若数组A[0…m][0…n]按列优先顺序存储，则a ij地址为（3. A ）。

A.LOC(a00)+[j*m+i]B. LOC(a00)+[j*n+i]C.LOC(a00)+[(j-1)*n+i-1]D. LOC(a00)+[(j-1)*m+i-1]4. 若下三角矩阵A n×n，按列顺序压缩存储在数组Sa[0…(n+1)n/2]中，则非零元素a ij的地址为（4. B）。

（设每个元素占d个字节）A. [(j-1)*n-2)1)(2(--jj+i-1]*dB. [(j-1)*n-2)1)(2(--jj+i]*dC．[(j-1)*n-2)1)(2(--jj+i+1]*dD．[(j-1)*n-2)1)(2(--jj+i-2]*d5.设有广义表D=(a,b,D)，其长度为（B），深度为（A）。

A.无穷大B.3C.2D.56. 广义表A=（a），则表尾为（6. C）。

A.aB.(( ))C.空表D.(a)7. 广义表A=((x,(a,B)),(x,(a,B),y))，则运算head(head(tail(A)))的结果为（7. A ）。

A.xB.(a,B)C.(x,(a,B))D.A8.下列广义表用图来表示时，分支结点最多的是（8. A）。

A.L=((x,(a,B)),(x,(a,B),y))B.A=(s,(a,B))C.B=((x,(a,B),y))D.D=((a,B),(c,(a,B),D)9.通常对数组进行的两种基本操作是（9. C）。

A.建立与删除B.索引和修改C.查找和修改D.查找与索引10. 假定在数组A 中，每个元素的长度为3个字节，行下标i 从1到8，列下标j 从1到10，从首地址SA 开始连续存放在存储器内，存放该数组至少需要的单元数为（10. C ）。

A.80B.100C.240D.27011. 数组A 中，每个元素的长度为3个字节，行下标i 从1到8，列下标j 从1到10，从首地址SA 开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为（11.C ）。

A.SA+141B.SA+144C.SA+222D.SA+22512. 稀疏矩阵一般的压缩存储方法有两种，即（12. C ）。

A.二维数组和三维数组B.三元组和散列C.三元组和十字链表D.散列和十字链表13. 若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点（13. B ）。

A.正确B.不正确14. 一个广义表的表头总是一个（14. D ）。

A.广义表B.元素C.空表D.元素或广义表15. 一个广义表的表尾总是一个（ 15.A ）。

A.广义表B.元素C.空表D.元素或广义表16. 数组就是矩阵，矩阵就是数组，这种说法（16.B ）。

A.正确B.错误C.前句对，后句错D.后句对二、填空题1. 一维数组的逻辑结构是______________，存储结构是______________；对于二维或多维数组，分为______________和______________两种不同的存储方式。

1. 线性结构，顺序结构，以行为主序，以列为主序2. 对于一个二维数组A[m][n]，若按行序为主序存储，则任一元素A[i][j]相对于A[0][0]的地址为______________。

2. i ×n+j 个元素位置3. 一个广义表为(a,(a,b),d,e,((i,j),k))，则该广义表的长度为_____，深度为_____。

3. 5，34. 一个稀疏矩阵为 ，则对应的三元组线性表为_____________。

4.（（0，2，2），（1，0，3），（2，2，-1），（2，3，5））5. 一个n ×n 的对称矩阵，如果以行为主序或以列为主序存入内存，则其容量为______________。

5. n ×(n+1)/26. 已知广义表A=((a,b,c ),(d,e,f ))，则运算head(tail(tail(A)))=____________。

6. e7. 设有一个10阶的对称矩阵A ，采用压缩存储方式以行序为主序存储，a 00为第一个元素，其存储地址为0，每个元素占有1个存储地址空间，则a 85的地址为______________。

7. 41 ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡-00005100000302008. 已知广义表Ls=(a,(b,c,d),e)，运用head和tail函数取出Ls中的原子b的运算是______________。

8. head(head(tail(Ls)))9. 三维数组R[c1…d1,c2…d2,c3…d3]共含有______________个元素。

（其中：c1≤d1,c2≤d2,c3≤d3）9.（d1-c1+1）×（d2-c2+1）×（d3-c3+1）10. 数组A[1…10，-2…6，2…8]以行优先的顺序存储，设第一个元素的首地址是100，每个元素占3个存储长度的存储空间，则元素A[5，0，7]的存储地址为______________。

10. 913三、判断题1. 数组可看作基本线性表的一种推广，因此与线性表一样，可以对它进行插入、删除等操作。

（ 1.×）2. 多维数组可以看作数据元素也是基本线性表的基本线性表。

（2.√）3. 以行为主序或以列为主序对于多维数组的存储没有影响。

（3.√）4. 对于不同的特殊矩阵应该采用不同的存储方式。

（4.√ ）5. 采用压缩存储之后，下三角矩阵的存储空间可以节约一半。

（5.×）6. 在一般情况下，采用压缩存储之后，对称矩阵是所有特殊矩阵中存储空间节约最多的。

（6.×）7. 矩阵不仅是表示多维数组，而且是表示图的重要工具。

（7.√）8. 距阵中的数据元素可以是不同的数据类型。

（8.×）9. 矩阵中的行列数往往是不相等的。

（9.×）10. 广义表的表头可以是广义表，也可以是单个元素。

（10.√）11. 广义表的表尾一定是一个广义表。

（11.√）12. 广义表的元素可以是子表，也可以是单元素。

（12.√）13. 广义表不能递归定义。

（13.×）14. 广义表实际上是基本线性表的推广。

（14.√）15. 广义表的组成元素可以是不同形式的元素。

（15.√ ）。

合集下载

数据结构实验报告-数组和广义表

数据结构实验报告-数组和广义表

《数据结构》实验报告实验序号： 7实验项目名称：数组和广义表学号姓名专业班级实验地点指导教师实验时间一、实验目的及要求本次实验目的是通过上机练习，熟悉和掌握课堂所讲授的基本知识点。

要求上机以前要认真复习课堂教学内容。

完成稀疏矩阵的三元组顺序存储。

二、实验设备（环境）及要求计算机；学生不许把食物带到机房吃；不许上网做与实验无关的内容；不许同学之间聊天；保持实验室安静卫生。

下课把键盘，座椅放回原处。

三、实验内容与步骤稀疏矩阵压缩存储，三元组顺序表的实现。

然后完成操作CreateSMatrix(&M) 创建稀疏矩阵，和求稀疏矩阵的转置 TransposeSMatrix(TSMatrix &M, TSMatrix &T) 。

编写一个函数，按照矩阵的形式打印出稀疏矩阵。

Header.h#include<stdio.h>#include<stdlib.h>//稀疏矩阵的三元组顺序表存储#define MAXSIZE 125 //非零元个数的最大值typedef int ElemType;typedef struct//三元组节点{int i,j;//非零元的行下标、列下标ElemType e;//矩阵的元素值。

}Triple;typedef struct{Triple data[MAXSIZE+1];//非零元数组，data[0]不用。

int mu,nu,tu;//矩阵的行数、列数、非零元个数。

}TSMatrix;//-------稀疏矩阵的操作函数-------//void CreateSMatrix(TSMatrix *M)//以行为主序，创建稀疏矩阵{char sign='y';int tu;(*M).tu=0;(*M).mu=0;(*M).nu=0;printf("请输入矩阵的行数： \n");scanf("%d",&(*M).mu);printf("请输入矩阵的列数： \n");scanf("%d",&(*M).nu);while(sign=='y'){++(*M).tu;tu=(*M).tu;printf(" 请输入第 %d个非零元 \n",tu);printf("\n请输入行号： ");scanf("%d",&(*M).data[tu].i);printf("\n请输入列号： ");scanf("%d",&(*M).data[tu].j);printf("\n请输入元素值： ");scanf("%d",&(*M).data[tu].e);printf("\n\n如果继续输入其他非零元素，请输入字母'y' ，否则请输入 'n' : ");scanf("%c%c",&sign,&sign);}}void PrintSMatrix(TSMatrix *M){int *p,k,i,j;int mu,nu,tu;mu=(*M).mu;nu=(*M).nu;tu=(*M).tu;p=(int *)malloc((nu+1)*sizeof(ElemType));//用来保存每行元素。

数据结构各章概要

数据结构各章概要

数据结构各章概要数据结构是计算机科学中非常重要的一个学科，其主要研究各种数据的组织方式和操作方法。

善于运用合适的数据结构可以提高算法的效率，并优化程序的性能。

本文将对数据结构的各个章节进行概要介绍，帮助读者了解不同章节的主要内容和应用。

第一章：引论在引论章节，我们将引入数据结构的基本概念和术语，例如什么是数据、数据项、数据对象等等。

同时，还将介绍数据结构的分类和基本操作，如搜索、遍历、插入、删除和排序。

这些基础知识是后续章节的基础。

第二章：线性表线性表是数据结构中最简单、最基本的一种结构。

其特点是数据元素之间的前驱和后继关系非常明确。

线性表可以用数组和链表两种方式实现。

在本章节中，我们将分别介绍顺序表和链表的实现原理、插入、删除、合并以及应用场景。

第三章：栈和队列栈和队列是两种特殊的线性表结构，它们对数据的访问具有限制性。

栈具有“先进后出”的特点，而队列则具有“先进先出”的特点。

在本章节中，我们将介绍栈和队列的实现方式以及常见的应用场景，如递归、表达式求值、广度优先搜索等。

第四章：串串是由零个或多个字符组成的有限序列，其长度可以为零。

在本章节中，我们将介绍串的定义和操作，包括字符串的模式匹配、模式识别和编辑操作。

串的相关算法在文本处理、计算机网络等领域具有广泛的应用。

第五章：数组和广义表数组是一种在内存中以连续方式存储的数据结构，它具有高效的随机访问特性。

广义表是线性表的一种扩展，可以包含表结构、原子结构以及其他广义表。

本章节将介绍数组和广义表的定义、操作和应用。

第六章：树树是一种非线性的数据结构，具有分层次、递归和层次遍历等特点。

在本章节中，我们将介绍树的基本概念、二叉树、树的遍历算法、平衡树以及树的应用，如编译器中的语法树、文件系统的目录结构等。

第七章：图图是一种复杂的非线性数据结构，由顶点集合和边集合组成。

在本章节中，我们将介绍图的各种表示方式，图的遍历算法、最短路径算法以及常用的图算法，如最小生成树算法和拓扑排序。

数据结构C语言版(第2版)严蔚敏人民邮电出版社课后习题答案

数据结构C语言版(第2版)严蔚敏人民邮电出版社课后习题答案

数据结构（C语言版）（第2版）课后习题答案李冬梅2015.3目录第1章绪论 (1)第2章线性表 (5)第3章栈和队列 (13)第4章串、数组和广义表 (26)第5章树和二叉树 (33)第6章图 (43)第7章查找 (54)第8章排序 (65)第1章绪论1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。

如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。

数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。

在有些情况下，数据元素也称为元素、结点、记录等。

数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。

数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。

例如，学生基本信息表中的学号、姓名、性别等都是数据项。

数据对象：是性质相同的数据元素的集合，是数据的一个子集。

例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’，‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。

逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。

因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

存储结构：数据对象在计算机中的存储表示，也称为物理结构。

抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。

具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。

数据结构答案第4章

数据结构答案第4章

第 4 章广义线性表——多维数组和广义表2005-07-14第 4 章广义线性表——多维数组和广义表课后习题讲解1. 填空⑴数组通常只有两种运算：（）和（），这决定了数组通常采用（）结构来实现存储。

【解答】存取，修改，顺序存储【分析】数组是一个具有固定格式和数量的数据集合，在数组上一般不能做插入、删除元素的操作。

除了初始化和销毁之外，在数组中通常只有存取和修改两种操作。

⑵二维数组A中行下标从10到20，列下标从5到10，按行优先存储，每个元素占4个存储单元，A[10][5]的存储地址是1000，则元素A[15][10]的存储地址是（）。

【解答】1140【分析】数组A中每行共有6个元素，元素A[15][10]的前面共存储了(15-10)×6+5个元素，每个元素占4个存储单元，所以，其存储地址是1000+140=1140。

⑶设有一个10阶的对称矩阵A采用压缩存储，A[0][0]为第一个元素，其存储地址为d，每个元素占1个存储单元，则元素A[8][5]的存储地址为（）。

【解答】d+41【分析】元素A[8][5]的前面共存储了(1+2+…+8)+5=41个元素。

⑷稀疏矩阵一般压缩存储方法有两种，分别是（）和（）。

【解答】三元组顺序表，十字链表⑸广义表((a), (((b),c)),(d))的长度是（），深度是（），表头是（），表尾是（）。

【解答】3，4，(a)，((((b),c)),(d))⑹已知广义表LS=(a，(b，c，d)，e)，用Head和Tail函数取出LS中原子b的运算是（）。

【解答】Head(Head(Tail(LS)))2. 选择题⑴二维数组A的每个元素是由6个字符组成的串，行下标的范围从0~8，列下标的范围是从0~9，则存放A至少需要（）个字节，A的第8列和第5行共占（）个字节，若A按行优先方式存储，元素A[8][5]的起始地址与当A按列优先方式存储时的（）元素的起始地址一致。