数据结构章节练习题及答案4.docx

《数据结构章节练习题及答案4.docx》由会员分享，可在线阅读，更多相关《数据结构章节练习题及答案4.docx（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第4章数组、字符串与广义表L具有什么特征的数据结构被称为数组？数组可以看成是形如(index, value)的数据集合，其中,index 是元素的索引，表示数据的逻辑位置，任意两个数据的index都不相 同；value表示数据元素的值。2 .设有二维数组如56,每个元素占相邻的8个字节，存储器按 字节编址，a的起始地址是1000,试计算：(1)数组a的最后一个元素起始地址；1000+ (30-1) *8=1232。(2)按行序优先时，元素a3的起始地址;1000+ (3*6+5) *8=1184(3)按行列序优先时，元素a43的起始地址。1000+ (3*5+4) *8=11523 .请简述数

2、组和矩阵的关系。矩阵是指纵横排列的二维数据表格。在高级语言编程中，通常用 二维数组来描述一个矩阵，从而可以对矩阵中的元素进行随机存取。 但矩阵的索引通常从1而不是像数组那样从0开始，并且使用A (i, j)而不是Ai, j的形式来引用矩阵中的元素。4 .矩阵有哪些基本运算？矩阵的操作包括转置、加法、减法和乘法等。5 .稀疏矩阵的特点是什么？为什么要对稀疏矩阵采用压缩存储表的长度、深度分别是多少？请画出该广义表的单链表存储结构示意 图。该广义表的深度是3,长度是6。该广义表的单链表存储结构示意图如下: head12.请列举出一些可以归纳成数组、矩阵、字符串和广义表数据 结构的实际问题。线性表的顺

3、序存储、学生编号和姓名的问题、各班级的学生编号 和姓名的问题等，都可以归结为数组。不同物品所需原材料的数量、不同产地原材料的价格、不同类型 的住宅需要的物品数量等，不同学生的计算机成绩，不同职工的工资 等都可以归结为矩阵。学生的姓名和学号、学校或各单位的名称、国家名称、一篇文章、 一个高级语言源程序等，都可归结为字符串。应用高斯消元法求解方程组可以归结为广义表。技术？稀疏矩阵的特点是矩阵中非零元素个数远远少于矩阵零元素个数。采用压缩存储技术主要是为了节省空间。6.设A和B是稀疏矩阵，都以三元组作为存储结构，请写出矩阵相加的算法C=A+Bo稀疏矩阵的三元组表示#include using nam

4、espace std;define M 50define N 50define MaxSize 20typedef int ElemType;typedef struct(int r;int c;ElemType d; TupNode;typedef structint rows;int cols;int nums;TupNode dataMaxSize; TSMatrix;int AMN,BMN;/建立三元组void CreateMat(int A|MN,TSMatrix &t,int row,int col) (int i,j;t.rows=row;t.cols=col;t.nums=0;

5、for(i=0;iM;i+)(for(j=();jvN;j+)(if(Aij!=O)(t.datat.nums.r=i;t.datat.nums.c=j;t.datat.nums.d=Aij;t.nums+;矩阵相加int MatAdd(TSMatrix &a,TSMatrix &b,TSMatrix &c) (int i=O,j=O,k=O;ElemType v;if(a.rows!=b.rows|a.cols!=b.cols) return 0;c.rows=a.rows;c.cols=a.cols;while(ia.nums & jb.nums)(if(a.datai.r=b.dataj

6、.r)(if(a.datai.cb.dataj.c)(c.datak.r=b.dataj.r;c.datak.c=b.dataj.c;c.datak.d=b.data|j.d;j+;k+;else(v=a.datai.d+b.datajj.d;if(v!=O)(c.datak.r=a.datai.r;c.datak.c=a.datai.c;c.datak.d=v;k+;)i+；j+；)else if(a.datai.rb.dataj.r)(c.datak.r=a.datai.r;c.datak.c=a.datai.c;c.datak.d=a.datai.d;i+;k+;elsec.datak.

7、r=b.dataj.r;c.datak.c=b.dataj.c;c.datak .d=b.dataj .d; j+;k+;)if (i=a.nums)while (jb.nums)c.datak.r=b.datajj.r;c.datakj.c=b.dataj.c;c.datak.d=b.data|j.d; j+；k+;if (j=b.nums)while (ia.nums)c.datak.r=a.datai.r;c.datak.c=a.datai.c;c.datak.d=a.datai.d;i+;k+;c.nums=k;return 1;/输出三元组void DispMat(TSMatrix

8、t) (int i;if(t.nums=0)cout ”此矩阵所有元素都为“ endl;return;coutt.rows,tt.colst,t.numsendl;coutMcoutMcoutMHendl;for(i=0;it.nums;i+)coutt.datai.r,tt.datai.ctt.datai.dendlendl;主函数int main()int row,col,i,j;TSMatrix a,b,c;coutv”请输入矩阵的行、列数:n”;cinrowcol;cout”请输入矩阵A的元素：n;for(i=0;irow;i+)for(j=0;jcol;j+)cinAij;coutv

9、”请输入矩阵B的元素：nu;for(i=0;irow;i+)for(j=0;jcol;j+)cinBij;CreateMat(A,a,row,col);CreateMat(B,b,row,col);cout”矩阵A的三元组表示为：nH;DispMat(a);coutv矩阵B的三元组表示为：nM;DispMat(b);if(MatAdd(a,b,c)coutv0)个元素组成的有穷序列：GL二(e., e2,en),但与线性表不同的是，广义表中的元素允许以不同的形 式出现：它可以是一个原子(逻辑上不能再分解的元素)，也可以是 另一个广义表。11 .一个广义表是(a, (a, b, c), d, e, (m, n),(w, (i, j), x),请问该广义