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

第4章数组、字符串与广义表

1.具有什么特征的数据结构被称为数组？

数组可以看成是形如(index,value)的数据集合，其中，index

是元素的索引，表示数据的逻辑位置，任意两个数据的index都不相

同；value表示数据元素的值。

2.设有二维数组a[5][6],每个元素占相邻的8个字节，存储器按

字节编址，已知a的起始地址是1000,试计算：

(1)数组a的最后一个元素起始地址；

1000+(30-1)*8=1232。

(2)按行序优先时，元素a[3][5]的起始地址;

1000+(3*6+5)*8=1184

(3)按行列序优先时，元素a[4][3]的起始地址。

1000+(3*5+4)*8=1152

3.请简述数组和矩阵的关系。

矩阵是指纵横排列的二维数据表格。在高级语言编程中，通常用

二维数组来描述一个矩阵，从而可以对矩阵中的元素进行随机存取。

但矩阵的索引通常从1而不是像数组那样从0开始，并且使用A(i,

j)而不是A[i,j]的形式来引用矩阵中的元素。

4.矩阵有哪些基本运算？

矩阵的操作包括转置'加法'减法和乘法等。

5.稀疏矩阵的特点是什么？为什么要对稀疏矩阵采用压缩存储

技术?

稀疏矩阵的特点是矩阵中非零元素个数远远少于矩阵零元素个

数。

采用压缩存储技术主要是为了节省空间。

6.设A和B是稀疏矩阵，都以三元组作为存储结构，请写出矩

阵相加的算法C=A+Bo

〃稀疏矩阵的三元组表示

#include<iostream>

usingnamespacestd;

#defineM50

#defineN50

#defineMaxSize20

typedefintElemType;

typedefstruct

(

intr;

intc;

ElemTyped;

}TupNode;

typedefstruct

introws;

intcols;

intnums;

TupNodedata[MaxSize];

}TSMatrix;

intA[M][N],B[M][N];

//建立三元组

voidCreateMat(intA[M][N],TSMatrix&t,introw,intcol)

(

inti,j;

t.rows=row;t.cols=col;t.nums=0;

for(i=0;i<M;i++)

(

for(j=0;j<N;j++)

(

if(A[i][j]!=O)

(

t.data[t.nums].r=i;t.data[t.nums].c=j;

t.data[t.nums].d=A[i][j];t.nums++;

)

)

〃矩阵相加

intMatAdd(TSMatrix&a,TSMatrix&b,TSMatrix&c)

(

inti=O,j=O,k=O;

ElemTypev;

if(a.rows!=b.rows||a.cols!=b.cols)return0;

c.rows=a.rows;c.cols=a.cols;

while(i<a.nums&&j<b.nums)

(

if(a.data[i].r==b.data[j].r)

|

if(a.data[i].c<b.data[j].c)

(

c.data[k].r=a.data[i].r;

c.data[k].c=a.data[i].c;

c.data[k].d=a.data[i].d;

i++;k++;

)

elseif(a.data[i].c>b.data[j].c)

(

c.data[k].r=b.data[j].r;

c.data[k].c=b.data[j].c;

c.data[k].d=b.data[j].d;

j++;k++;

)

else

(

v=a.data[i].d+b.data[j].d;

if(v!=O)

(

c.data[k].r=a.data[i].r;

c.data[k].c=a.data[i].c;

c.data[k].d=v;

k++;

)

i++；j++；

)

)

elseif(a.data[i].r<b.data[j].r)

(

c.data[k].r=a.data[i].r;

c.data[k].c=a.data[i].c;

c.data[k].d=a.data[i].d;

i++;k++;

else

c.data[k].r=b.data[j].r;

c.data[k].c=b.data[j].c;

c.data[k].d=b.data[j].d;

j++;k++;

}

)

if(i==a.nums)

while(j<b.nums)

(

c.data[k].r=b.data[j].r;

c.data[k].c=b.data[j].c;

c.data[k].d=b.data[j].d;

j++;k++;

}

if(j==b.nums)

while(i<a.nums)

(

c.data[k].r=a.data[i].r;

c.data[k].c=a.data[i].c;

c.data[k].d=a.data[i].d;

i++;k++;

)

c.nums=k;

return1;

)

//输出三元组

voidDispMat(TSMatrixt)

(

inti;

if(t.nums<=0)

(

cout<<"此矩阵所有元素都为"<<endl;

return;

)

cout«t.rows«,\t'«t.cols«'\t'«t.nums«endl;

cout«"----------------"«endl;

for(i=0;i<t,nums;i++)

cout«t.data[i].r«'\t'«t.data[i].c«'\t'«t.data[i].d«endl«endl;

)

〃主函数

intmain()

introw,col,i,j;

TSMatrixa,b,c;

cout<<"请输入矩阵的行'列数：\n";

cin»row»col;

cout<<"请输入矩阵A的元素：\n";

for(i=0;i<row;i++)

for(j=0;j<col;j++)

cin»A[i][j];

cout<<"请输入矩阵B的元素：\n";

for(i=0;i<row;i++)

for(j=0;j<col;j++)

cin»B[i][j];

CreateMat(A,a,row,col);

CreateMat(B,b,row,col);

cout<<"矩阵A的三元组表示为：\n";

DispMat(a);

cout«"矩阵B的三元组表示为：\n";

DispMat(b);

if(MatAdd(a,b,c))

cout«"矩阵A、B相加后得到的三元组表示为：\n";

DispMat(c);

)

return0;

)

7.简述字符串与一维字符型数组的区别与联系。

字符串简称串，它是一种以字符为元素的特殊线性表。字符串可

以看成是以字符为元素的一维数组。具体实现时，在C/C++中的字符

串使用为字符型数组来表示。为了便于确定字符串的结尾，在字符型

数组中使用\0(就是0)作为字符串的截止符。

8.列举一些需要进行字符串模式匹配的应用场景。

例如，在文本编辑中经常要查找某一特定单词或者一段话在整篇

文章中出现的位置，按照姓名查找某个学生'员工、居民。有效的模

式匹配能极大地提高文本编辑程序的能力。

9.列举几个字符串的其他操作。

求字符串中某个子串出现的次数，删除满足条件的子串，字符串

字符移位等。

10.什么是广义表？广义表与线性表的区别是什么？

广义表又称列表，是由n(n>0)个元素组成的有穷序列：GL=(e,,

e2,……品)，但与线性表不同的是，广义表中的元素允许以不同的形

式出现：它可以是一个原子(逻辑上不能再分解的元素)，也可以是

另一个广义表。

11.一^个广义表是(a,(a,b,c),d,e,(m,n),(w,(i,j),x)),请问该广义

表的长度、深度分别是多少？请画出该广义表的单链表存储结构示意

图。

该广义表的深度是3,长度是6。

该广义表的单链表存储结构示意图如下：

head

~►tup

headuhead，1

.headv

|i|5|11IMN11LoJ^J

mvr^iLiMJGW

12.请列举出一些可以归纳成数组、矩