文档库 最新最全的文档下载
当前位置:文档库 › 数据结构课后习题答案第五章数组与广义表

数据结构课后习题答案第五章数组与广义表

数据结构课后习题答案第五章数组与广义表
数据结构课后习题答案第五章数组与广义表

第五章数组与广义表

一、假设有二维数组A6*8,每个元素用相邻的6个字节存储,存储器按字节

编址。已知A的起始存储位置(基地址)为1000。计算:

1、数组A的体积(即存储量);

2、数组A的最后一个元素a57的第一个字节的地址;

3、按行存储时,元素a14的第一个字节的地址;

4、按列存储时,元素a47的第一个字节的地址;

答案:

1、(6*8)*6=288

2、loc(a57)=1000+(5*8+7)*6=1282或=1000+(288-6)=1282

3、loc(a14)=1000+(1*8+4)*6=1072

4、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/2i2

f2(j)=j

c=-(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中。

解:

矩阵相加就是将两个矩阵中同一位置的元素值相加。由于两个稀疏矩阵的非零元素按三元组表形式存放,在建立新的三元组表C时,为了使三元组元素仍按行优先排列,所以每次插入的三元组不一定是A的,按照矩阵元素的行列去找A 中的三元组,若有,则加入C,同时,这个元素如果在B中也有,则加上B的这个元素值,否则这个值就不变;如果A中没有,则找B,有则插入C,无则查找下一个矩阵元素。

#define MaxSize 10 //用户自定义

typedef int DataType; //用户自定义

typedef struct

{ //定义三元组

int i,j;

DataType v;

}TriTupleNode;

typedef struct

{ //定义三元组表

TriTupleNode data[MaxSize];

int m,n,t;//矩阵行,列及三元组表长度

}TriTupleTable;

//以下为矩阵加算法

void AddTriTuple( TriTupleTable *A, TriTupleTable *B, TriTupleTable *C)

{//三元组表表示的稀疏矩阵A,B相加

int k,l;

DataType temp;

C->m=A->m;//矩阵行数

C->n=A->n;//矩阵列数

C->t=0; //三元组表长度

k=0; l=0;

while (kt&&lt)

{if((A->data[k].i==B->data[l].i)&&(A->data[k].j==B->data[l].j))

{temp=A->data[k].v+B->data[l].v;

if (!temp)//相加不为零,加入C

{C->data[c->t].i=A->data[k].i;

C->data[c->t].j=A->data[k].j;

C->data[c->t++].v=temp;

}

k++;l++;

}

if

((A->data[k].i==B->data[l].i)&&(A->data[k].jdata[l].j))

||(A->data[k].idata[l].i)//将A中三元组加入C

{C->data[c->t].i=A->data[k].i;

C->data[c->t].j=A->data[k].j;

C->data[c->t++].v=A->data[k].v;

k++;

}

if

((A->data[k].i==B->data[l].i)&&(A->data[k].j>B->data[l].j))

||(A->data[k].i>B->data[l].i)//将B中三元组加入C

{C->data[c->t].i=B->data[l].i;

C->data[c->t].j=B->data[l].j;

C->data[c->t++].v=B->data[l].v;

l++;

}

}

while (kt)//将A中剩余三元组加入C

{C->data[c->t].i=A->data[k].i;

C->data[c->t].j=A->data[k].j;

C->data[c->t++].v=A->data[k].v;

k++;

}

while (lt)//将B中剩余三元组加入C

{C->data[c->t].i=B->data[l].i;

C->data[c->t].j=B->data[l].j;

C->data[c->t++].v=B->data[l].v;

l++;

}

}

二十六、试编写一个以三元组形式输出用十字链表表示的稀疏矩阵中非零元素及其下标的算法。

解:

void Print_OLMatrix(OLMatrix A)//以三元组格式输出十字链表表示的矩阵

{

for(i=0;i

{

if(A.rhead[i])

for(p=A.rhead[i];p;p=p->right) //逐次遍历每一个行链表

printf("%d %d %d\n",i,p->j,p->e;

}

}//Print_OLMatrix

补充题:

一、现有如下的稀疏矩阵A (如图所示),要求画出以下各种表示方法。

(1)三元组表示法。

(2)十字链表法。

① 三元组表示法

0 0 0 22 0 -

15 0 13 3 0 0 0 0 0 0 -6 0 0 0 0 0 0 0 0 91 0 0 0 0 0 0 0 28 0 0 0

②略

二、画出下列广义表的存储结构示意图。

(1)A=((a,b,c),d,(a,b,c))

(2)B=(a,(b,(c,d),e),f)

三、有数组A[4][4],把1到16个整数分别按顺序放入A[0][0]...A[0][3],A[1][0]...A[1][3],A[2][0]...A[2][3],A[3][0]...A[3][3]中,编写一个算法获取数据并求出两条对角线元素的乘积。

int mul(int A[4][4]){

int i,j;

int k,s;

k=1;

s=1;

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

for (j=0;j<4;j++){

A[i][j]=k;

k++;

}

for (i=0;i<4;i++){

s=s*A[i][i];

s=s*A[i][3-i];

} // 计算两条对角线元素的乘积

return s;

}

四、

19.已知广义表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))))

20. 广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为()。

Head(Tail(Head(Tail(Tail(A)))))

A. (g)

B. (d)

C. c

D. d

21. 已知广义表: A=(a,b), B=(A,A), C=(a,(b,A),B), 求下列运算的结果:

tail(head(tail(C))) =( )。

A.(a)

B. A

C. a

D. (b)

E. b

F.

(A)

22. 广义表运算式Tail(((a,b),(c,d)))的操作结果是()。

A. (c,d)

B. c,d

C. ((c,d))

D. d

23. 广义表L=(a,(b,c)),进行Tail(L)操作后的结果为()。

A. c

B. b,c

C.(b,c)

D.((b,c))

24. 广义表((a,b,c,d))的表头是(),表尾是()。

A. a

B.()

C.(a,b,c,d)

D.(b,c,d)

25. 广义表(a,(b,c),d,e)的表头为()。

A. a

B. a,(b,c)

C. (a,(b,c))

D.

(a)

26. 设广义表L=((a,b,c)),则L的长度和深度分别为()。 A. 1和1

B. 1和3

C. 1和2

D. 2和3

27. 下面说法不正确的是( )。

A. 广义表的表头总是一个广义表

B. 广义表的表尾总是一个广义

C. 广义表难以用顺序存储结构

D. 广义表可以是一个多层次的结构

《数据结构》课后习题答案

第1章绪论 1.简述下列概念:数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。 答案: 数据:是客观事物的符号表示,指所有能输入到计算机中并被计算机程序处理的符号的总称。如数学计算中用到的整数和实数,文本编辑所用到的字符串,多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。 数据元素:是数据的基本单位,在计算机中通常作为一个整体进行考虑和处理。在有些情况下,数据元素也称为元素、结点、记录等。数据元素用于完整地描述一个对象,如一个学生记录,树中棋盘的一个格局(状态)、图中的一个顶点等。 数据项:是组成数据元素的、有独立含义的、不可分割的最小单位。例如,学生基本信息表中的学号、姓名、性别等都是数据项。 数据对象:是性质相同的数据元素的集合,是数据的一个子集。例如:整数数据对象是集合N={0,±1,±2,…},字母字符数据对象是集合C={‘A’,‘B’,…,‘Z’,‘a’,‘b’,…,‘z’},学生基本信息表也可是一个数据对象。 数据结构:是相互之间存在一种或多种特定关系的数据元素的集合。换句话说,数据结构是带“结构”的数据元素的集合,“结构”就是指数据元素之间存在的关系。 逻辑结构:从逻辑关系上描述数据,它与数据的存储无关,是独立于计算机的。因此,数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 存储结构:数据对象在计算机中的存储表示,也称为物理结构。 抽象数据类型:由用户定义的,表示应用问题的数学模型,以及定义在这个模型上的一组操作的总称。具体包括三部分:数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。 2.试举一个数据结构的例子,叙述其逻辑结构和存储结构两方面的含义和相互关系。 答案: 例如有一张学生基本信息表,包括学生的学号、姓名、性别、籍贯、专业等。每个学生基本信息记录对应一个数据元素,学生记录按顺序号排列,形成了学生基本信息记录的线性序列。对于整个表来说,只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录),其他的结点则各有一个也只有一个直接前趋和直接后继。学生记录之间的这种关系就确定了学生表的逻辑结构,即线性结构。 这些学生记录在计算机中的存储表示就是存储结构。如果用连续的存储单元(如用数组表示)来存放这些记录,则称为顺序存储结构;如果存储单元不连续,而是随机存放各个记录,然后用指针进行链接,则称为链式存储结构。 即相同的逻辑结构,可以对应不同的存储结构。 3.简述逻辑结构的四种基本关系并画出它们的关系图。 答案: (1)集合结构 数据元素之间除了“属于同一集合”的关系外,别无其他关系。例如,确定一名学生是否为班级成员,只需将班级看做一个集合结构。 (2)线性结构 数据元素之间存在一对一的关系。例如,将学生信息数据按照其入学报到的时间先后顺序进行排列,将组成一个线性结构。 (3)树结构

第五章 数组和广义表

第五章数组和广义表 一.选择题 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. 473 4.在稀疏矩阵的十字链接存储中,每个列单链表中的结点都具有相同的_____。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]的地址是________。 A.52 B.48 C.54 D.53 11.数组通常具有的两种基本操作是________。 A.建立与删除 B.索引和修改 C.查找和修改 D.查找与索引12.二维数组M 的成员是 6 个字符(每个字符占一个存储单元)组成的串,行下标 i 的范围从0 到 8,列下标j 的范围从1到10,则存放M 至少需要________个字节。 A.90 B.180 C.240 D.540 13.二维数组M 的元素是4 个字符(每个字符占一个存储单元)组成的串,行下标 i 的范围从0 到 4 ,列下标j 的范围从0 到 5,M 按行存储时元素M[3 Ⅱ5]的起始地址与M 按列存储时元素________的起始地址相同。

(完整word版)数据结构第五章数组和广义表习题及答案

习题五数组和广义表 一、单项选择题 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]*k B.Loc[i,j]=loc[0,0]+[(m+n)*i+j]*k C.Loc[i,j]=loc[0,0]+[(n+1)*i+j]*k D.Loc[i,j]=[(n+1)*i+j]*k 3.稀疏矩阵的压缩存储方法是只存储 ( ) A.非零元素 B. 三元祖(i,j, aij) C. aij D. i,j 4. 数组A[0..5,0..6]的每个元素占五个字节,将其按列优先次序存储在起始地址为1000的内存单元中,则元素A[5,5]的地址是( )。 A. 1175 B. 1180 C. 1205 D. 1210 5. A[N,N]是对称矩阵,将下面三角(包括对角线)以行序存储到一维数组T[N(N+1)/2]中,则对任一上三角元素a[i][j]对应T[k]的下标k是()。 A. i(i-1)/2+j B. j(j-1)/2+i C. i(j-i)/2+1 D. j(i-1)/2+1 6. 用数组r存储静态链表,结点的next域指向后继,工作指针j指向链中结点,使j 沿链移动的操作为( )。 A. j=r[j].next B. j=j+1 C. j=j->next D. j=r[j]-> next 7. 对稀疏矩阵进行压缩存储目的是()。 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))的表头是(),表尾是()。 A. a B.() C.(a,b,c,d) D.(b,c,d) 10. 设广义表L=((a,b,c)),则L的长度和深度分别为()。 A. 1和1 B. 1和3 C. 1和2 D. 2和3 11. 下面说法不正确的是( )。 A. 广义表的表头总是一个广义表 B. 广义表的表尾总是一个广义表 C. 广义表难以用顺序存储结构 D. 广义表可以是一个多层次的结构 二、填空题 1.通常采用___________存储结构来存放数组。对二维数组可有两种存储方法:一种是以___________为主序的存储方式,另一种是以___________为主序的存储方式。 2. 用一维数组B与列优先存放带状矩阵A中的非零元素A[i,j] (1≤i≤n,i-2≤j≤i+2),B 中的第8个元素是A 中的第_ _行,第_ _列的元素。

严蔚敏版数据结构课后习题答案-完整版

第1章绪论 1.1 简述下列术语:数据,数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解:数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合,是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解:抽象数据类型包含一般数据类型的概念,但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义,直接提供给编程者定义用户数据,因此称它们为预定义数据类型。抽象数据

类型通常由编程者定义,包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时,要求只定义到数据的逻辑结构和操作说明,不考虑数据的存储结构和操作的具体实现,这样抽象层次更高,更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R),其中 {}4,3,2,1d d d d D =,{}r R =,()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解: 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义(有理数是其分子、分母均为自然数且分母不为零的分数)。 解: ADT Complex{ 数据对象:D={r,i|r,i 为实数} 数据关系:R={} 基本操作: InitComplex(&C,re,im) 操作结果:构造一个复数C ,其实部和虚部分别为re 和im DestroyCmoplex(&C)

第 5 章 数组和广义表答案

第 5 章数组和广义表 一、选择 1.设有一个10阶的对称矩阵A,采用压缩存储方式,以行序为主存 储,a11为第一元素,其存储地址为1,每个元素占一个地址空间,则 a85的地址为( B )。 A. 13 B. 33 C. 18 D. 40 2. 设有数组A[i,j],数组的每个元素长度为3字节,i的值为1 到 8 ,j的值为1 到10,数组从内存首地址BA开始顺序存放,当用以 列为主存放时,元素A[5,8]的存储首地址为(B )。 A. BA+141 B. BA+180 C. BA+222 D. BA+225 3. 假设以行序为主序存储二维数组A=array[1..100,1..100],设 每个数据元素占2个存储单元,基地址为10,则LOC[5,5]=( B )。 A. 808 B. 818 C. 1010 D. 1020 4. 二维数组A的元素都是6个字符组成的串,行下标i的范围从0 到8,列下标j的范围从0到9。从供选择的答案中选出应填入下列 关于数组存储叙述中()内的正确答案。 (1)存放A至少需要( E )个字节; (2)A的第8列和第5行共占( A )个字节; (3)若A按行存放,元素A[8,5]的起始地址与A按列存放时的元 素( B )的起始地址一致。 供选择的答案: (1)A. 90 B. 180 C. 240 D. 270 E. 540

(2)A. 108 B. 114 C. 54 D. 60 E. 150 (3)A. A[8,5] B. A[4,9] C. A[5,8] D. A[0,9] 5. 若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括 主对角线上所有元素)依次存放于一维数组B[1..(n(n+1))/2]中, 则在B中确定aij(i

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

第五章数组和广义表:习题 习题 一、选择题 1.假设以行序为主序存储二维数组A[1..100,1..100],设每个数据元素占两个存储单元,基地址为10,则LOC(A[5,5])=( )。 A. 808 B. 818 C. 1010 D. 1020 2.同一数组中的元素( )。 A. 长度可以不同B.不限C.类型相同 D. 长度不限 3.二维数组A的元素都是6个字符组成的串,行下标i的范围从0到8,列下标j的范圈从1到10。从供选择的答案中选出应填入下列关于数组存储叙述中( )内的正确答案。 (1)存放A至少需要( )个字节。 (2)A的第8列和第5行共占( )个字节。 (3)若A按行存放,元素A[8]【5]的起始地址与A按列存放时的元素( )的起始地址 一致。 供选择的答案: (1)A. 90 B. 180 C. 240 D. 270 (2) A. 108 B. 114 C. 54 D. 60 (3)[8][5] B. A[3][10] [5][8] [O][9] 4.数组与一般线性表的区别主要是( )。 A.存储方面 B.元素类型方面 C.逻辑结构方面 D.不能进行插入和删除运算 5.设二维数组A[1..m,1..n]按行存储在数组B[1..m×n]中,则二维数组元素A[i,j]在一维数组B中的下标为( )。 A. (i-l)×n+j B. (i-l)×n+j-l C.i×(j-l) D. j×m+i-l 6.所谓稀疏矩阵指的是( )。 A.零元素个数较多的矩阵 B.零元素个数占矩阵元素中总个数一半的矩阵 C.零元素个数远远多于非零元素个数且分布没有规律的矩阵 D.包含有零元素的矩阵 7.对稀疏矩阵进行压缩存储的目的是( )。 A.便于进行矩阵运算 B.便于输入和输出 C.节省存储空间 D. 降低运算的时间复杂度 8.稀疏矩阵一般的压缩存储方法有两种,即( )。 A.二维数组和三维数组 B.三元组和散列 C.三元组和十字链表 D.散列和十字链表 9.有一个100×90的稀疏矩阵,非0元素有10个,设每个整型数占两字节,则用三元组表示该矩阵时,所需的字节数是( )。 A. 60 B. 66 C.18000 D.33 10. A[N,N]是对称矩阵,将下面三角(包括对角线)以行序存储到一维数组T[N(N+I)/2] 中,则对任一上三角元素a[i][j]对应T[k]的下标k是( )。 A. i(i-l)/2+j B. j(j-l)/2+i C. i(j-i)/2+1 D. j(i-l)/2+1 11.已知广义表L=((x,y,z),a,(u,t,w)),从L表中取出原子项t的运算是( ) A. head(tail(tail(L))) B. tail(head(head(taiI(L)))) C. head(tail(head(taiI(L)))) D. head(tail(head(tail(tail(L)))))

(完整word版)数据结构课后习题及答案

填空题(10 * 1 '= 10') 一、概念题 22当对一个线性表经常进行的是插入和删除操作时,采用链式存储结构为宜。 23当对一个线性表经常进行的是存取操作,而很少进行插入和删除操作时,最好采用顺序存储结构。 2.6. 带头结点的单链表L中只有一个元素结点的条件是L->Next->Next==Null。 36循环队列的引入,目的是为了克服假溢出。 4.2. 长度为0的字符串称为空串。 4.5. 组成串的数据元素只能是字符。 4.8. 设T和P是两个给定的串,在T中寻找等于P的子串的过程称为模式匹配,又称P为模式。 7.2. 为了实现图的广度优先搜索,除一个标志数组标志已访问的图的结点外,还需要队列存放被访问的结点实现遍历。 5.7. 广义表的深度是广义表中括号的重数 7.8. 有向图G可拓扑排序的判别条件是有无回路。 7.9. 若要求一个稠密图的最小生成树,最好用Prim算法求解。 8.8. 直接定址法法构造的哈希函数肯定不会发生冲突。 9.2. 排序算法所花费的时间,通常用在数据的比较和交换两大操作。 1.1. 通常从正确性、可读性、健壮性、时空效率等几个方面评价算法的(包括程序)的质量。 1.2. 对于给定的n元素,可以构造出的逻辑结构有集合关系、线性关系树形关系、图状关系四种。 1.3. 存储结构主要有顺序存储、链式存储、索引存储、散列存储四种。 1.4. 抽象数据类型的定义仅取决于它的一组逻辑特性,而与存储结构无关,即不论其内部结构如何变化,只要它的数学特性不 变,都不影响其外部使用。 1.5. 一个算法具有五大特性:有穷性、确定性、可行性,有零个或多个输入、有一个或多个输入。 2.8. 在双向链表结构中,若要求在p指针所指的结点之前插入指针为s所指的结点,则需执行下列语句: s_>prior= p_>prior; s->next= p; p_>prior- next= s; p_>prior= s;。 2.9. 在单链表中设置头结点的作用是不管单链表是否为空表,头结点的指针均不空,并使得对单链表的操作 (如插入和删除)在各种情况下统一。 3.1. 队列是限制在表的一端进行插入和在另一端进行删除的线性表,其运算遵循先进先出原则。 3.2 .栈是限定尽在表位进行插入或删除操作的线性表。 3.5. 在链式队列中,判定只有一个结点的条件是(Q->rear==Q->fro nt)&&(Q->rear!=NULL) 。 3.7. 已知链队列的头尾指针分别是f和r,则将x入队的操作序列是node *p=(node *)malloc(node); p->next=x;] p_>next=NULL; if(r) {r->next=p; r=p;} else {r=p; f=p;}。 3.8. 循环队列的满与空的条件是(rear+1)%MAXSIZE==fornt 和(fron t=-1 &&rear+ ^=MAXSIZE) 。 4.3. 串是一种特殊的线性表,其特殊性表现在数据元素都是由字符组成。 4.7. 字符串存储密度是串值所占存储位和实际分配位的比值,在字符串的链式存储结构中其结点大小是可变的。 5.3. 所谓稀疏矩阵指的是矩阵中非零元素远远小于元素总数,则称该矩阵为矩阵中非零元素远远小于元素总数,则称该矩阵为稀 疏矩阵。 5.4. —维数组的逻辑结构是线性结构,存储结构是顺序存储结构;对二维或多维数组,分别按行优先和列优先两种?不同的存储 方式。 7.4. 在有向图的邻接矩阵表示中,计算第i个顶点入度的方法是求邻接矩阵中第?i列非10元素的个数。 7.10. AOV网中,结点表示活动,边表示活动之间的优先关系,AOE网中,结点表示事件,边表示活动。 9.1. 按排序过程中依据不同原则对内部排序方法进行分类,主要有选择排序、交换排序、插入排序归并排序等4类。 9.3 .在堆排序、快速排序和归并排序中若只从排序结果的稳定性考虑,则应选择归并排序方法;若只从平均情况下 排序最快考虑,则应选择快速排序方法;若只从最坏情况下排序最快且要节省类存考虑,则应选择堆排序方法。 9.4. 直接插入排序用监视哨的作用是存当前要的插入记录,可又省去查找插入位置时对是否出界的判断。 9.6. 设表中元素的初始状态是按键值递增的,则直接插入排序最省时间,快速排序最费时间。 4.9. 下列程序判断字符串s是否对称,对称则返回1,否则返回0;如?(abba”返回1, ? (”abab”)返回0. Int f (char*s) { Int i=0,j=0;

数据结构课后习题答案

数据结构习题集答案 第1章绪论 1.1 简述下列术语:数据,数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解:数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合,是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解:抽象数据类型包含一般数据类型的概念,但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义,直接提供给编程者定义用户数据,因此称它们为预定义数据类型。抽象数据

类型通常由编程者定义,包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时,要求只定义到数据的逻辑结构和操作说明,不考虑数据的存储结构和操作的具体实现,这样抽象层次更高,更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R),其中 {}4,3,2,1d d d d D =,{}r R =,()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解: 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义(有理数是其分子、分母均为自然数且分母不为零的分数)。 解:ADT Complex{ 数据对象:D={r,i|r,i 为实数} 数据关系:R={} 基本操作: InitComplex(&C,re,im) 操作结果:构造一个复数C ,其实部和虚部分别为re 和im DestroyCmoplex(&C) 操作结果:销毁复数C Get(C,k,&e) 操作结果:用e 返回复数C 的第k 元的值

第五章 数组和广义表

第5章数组和广义表习题 一、选择题 1.设有一个10阶的对称矩阵A,采用压缩存储方式,以行序为主存储,a11为第一元素,其存储地址为1,每个元素占一个地址空间,则a85的地址为(B)。 i×(i-1)/2+j-1~~~~(i>=j) 8×7÷2+5=33因为a11从1开始所以要加1 A. 13 B. 33 C. 18 D. 40 2. 数组A[0..5,0..6]的每个元素占五个字节,将其按列优先次序存储在起始地址为1000的内存单元中,则元素A[5,5]的地址是( A)。 所求=a+(j*n+j)*l A. 1175 B. 1180 C. 1205 D. 1210 3. 若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B[1..(n(n+1))/2]中,则在B中确定aij(i

最全数据结构课后习题答案耿国华版

绪论第1章 √(2)×(3)2.(1)×C )C(3(1)A(2)3. 的语句频度5.计算下列程序中x=x+1for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; 的语句频度为:【解答】x=x+1=n(n+1)(n+2)/6 )+……+(1+2+……+n)T(n)=1+(1+2)+(1+2+3 并确定算法中每一),p(xx+ax+a+…….+ax的值6.编写算法,求一元多项式p(x)=a n20nn20n1规定算法中不能使用要求时间复杂度尽可能小,语句的执行次数和整个算法的时间复杂度,算法的输入和输出)。n,输出为P(x求幂函数。注意:本题中的输入为a(i=0,1,…n)、x和0in采用下列方法1)通过参数表中的参数显式传递()通过全局变量隐式传递。讨论两种方法的优缺点,并在算法中以你认为较好的一种实(2 现输入输出。【解答】1)通过参数表中的参数显式传递(优点:当没有调用函数时,不占用存,调用结束后形参被释放,实参维持,函数通用 性强,移置性强。缺点:形参须与实参对应,且返回值数量有限。 )通过全局变量隐式传递(2 优点:减少实参与形参的个数,从而减少存空间以及传递数据时的时间消耗 缺点:函数通用性降低,移植性差 算法如下:通过全局变量隐式传递参数PolyValue() { int i,n; float x,a[],p; nn=”);printf(“\ scanf(“%f”,&n); nx=”);printf(“\ scanf(“%f”,&x); for(i=0;i

最全数据结构课后习题答案(耿国华版[12bb]

第1章绪论工程大数电习题答案册工程大数电习题答案 册 2.(1)×(2)×(3)√ 3.(1)A(2)C(3)C 5.计算下列程序中x=x+1的语句频度 for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; 【解答】x=x+1的语句频度为: T(n)=1+(1+2)+(1+2+3)+……+(1+2+……+n)=n(n+1)(n+2)/6 6.编写算法,求一元多项式p n(x)=a0+a1x+a2x2+…….+a n x n的值p n(x0),并确定算法中每一语句的执行次数和整个算法的时间复杂度,要求时间复杂度尽可能小,规定算法中不能使用求幂函数。注意:本题中的输入为a i(i=0,1,…n)、x和n,输出为P n(x0)。算法的输入和输出采用下列方法 (1)通过参数表中的参数显式传递 (2)通过全局变量隐式传递。讨论两种方法的优缺点,并在算法中以你认为较好的一种实现输入输出。 【解答】 (1)通过参数表中的参数显式传递 优点:当没有调用函数时,不占用内存,调用结束后形参被释放,实参维持,函数通用性强,移置性强。 缺点:形参须与实参对应,且返回值数量有限。 (2)通过全局变量隐式传递 优点:减少实参与形参的个数,从而减少内存空间以及传递数据时的时间消耗 缺点:函数通用性降低,移植性差 算法如下:通过全局变量隐式传递参数 PolyValue() { int i,n; float x,a[],p; printf(“\nn=”); scanf(“%f”,&n); printf(“\nx=”); scanf(“%f”,&x); for(i=0;i

数据结构课后习题答案清华大学出版社殷人昆

1-1什么是数据? 它与信息是什么关系? 【解答】 什么是信息?广义地讲,信息就是消息。宇宙三要素(物质、能量、信息)之一。它是现实世界各种事物在人们头脑中的反映。此外,人们通过科学仪器能够认识到的也是信息。信息的特征为:可识别、可存储、可变换、可处理、可传递、可再生、可压缩、可利用、可共享。 什么是数据?因为信息的表现形式十分广泛,许多信息在计算机中不方便存储和处理,例如,一个大楼中4部电梯在软件控制下调度和运行的状态、一个商店中商品的在库明细表等,必须将它们转换成数据才能很方便地在计算机中存储、处理、变换。因此,数据(data)是信息的载体,是描述客观事物的数、字符、以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。在计算机中,信息必须以数据的形式出现。 1-2什么是数据结构? 有关数据结构的讨论涉及哪三个方面? 【解答】 数据结构是指数据以及相互之间的关系。记为:数据结构= { D, R }。其中,D是某一数据对象,R是该对象中所有数据成员之间的关系的有限集合。 有关数据结构的讨论一般涉及以下三方面的内容: ①数据成员以及它们相互之间的逻辑关系,也称为数据的逻辑结构,简称为数据结构; ②数据成员极其关系在计算机存储器内的存储表示,也称为数据的物理结构,简称为存储结构; ③施加于该数据结构上的操作。 数据的逻辑结构是从逻辑关系上描述数据,它与数据的存储不是一码事,是与计算机存储无关的。因此,数据的逻辑结构可以看作是从具体问题中抽象出来的数据模型,是数据的应用视图。数据的存储结构是逻辑数据结构在计算机存储器中的实现(亦称为映像),它是依赖于计算机的,是数据的物理视图。数据的操作是定义于数据逻辑结构上的一组运算,每种数据结构都有一个运算的集合。例如搜索、插入、删除、更新、排序等。 1-3数据的逻辑结构分为线性结构和非线性结构两大类。线性结构包括数组、链表、栈、 队列、优先级队列等; 非线性结构包括树、图等、这两类结构各自的特点是什么? 【解答】 线性结构的特点是:在结构中所有数据成员都处于一个序列中,有且仅有一个开始成员和一个终端成员,并且所有数据成员都最多有一个直接前驱和一个直接后继。例如,一维数组、线性表等就是典型的线性结构 非线性结构的特点是:一个数据成员可能有零个、一个或多个直接前驱和直接后继。例如,树、图或网络等都是典型的非线性结构。 1-4.什么是抽象数据类型?试用C++的类声明定义“复数”的抽象数据类型。要求 (1) 在复数内部用浮点数定义它的实部和虚部。 (2) 实现3个构造函数:缺省的构造函数没有参数;第二个构造函数将双精度浮点数赋给复数的实部,虚部置为0;第三个构造函数将两个双精度浮点数分别赋给复数的实部和虚部。 (3) 定义获取和修改复数的实部和虚部,以及+、-、*、/等运算的成员函数。

第5章 数组和广义表 自测题含答案

第5章 数组和广义表 自测题含答案 一、单选题 1. 假设有二维数组A 6×8,每个元素用相邻的6个字节存储,存储器按字节编址。已知A 的起始存储位置(基地址)为1000,则数组A 的体积(存储量)为 288 B ;末尾元素A 57的第一个字节地址为 1282 ;若按行存储时,元素A 14的第一个字节地址为 (8+4)×6+1000=1072 ;若按列存储时,元素A 47的第一个字节地址为 (6×7+4)×6+1000)=1276 。 2. 〖00年计算机系考研题〗设数组a[1…60, 1…70]的基地址为2048,每个元素占2个存储单元,若以列序为主序顺序存储,则元素a[32,58]的存储地址为 8950 。 答:不考虑0行0列,利用列优先公式: LOC(a ij )=LOC(a c 1, c 2)+[(j-c 2)*( d 1-c 1+1)+i-c 1)]*L 得:LOC(a 32,58)=2048+[(58-1)*(60-1+1)+32-1]]*2=8950 3. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素,它包含有三个数据项,分别表示该元素的 行下标 、 列下标 和 元素值 。 4. 求下列广义表操作的结果: (1) GetHead 【((a,b),(c,d))】=== (a, b) ; //头元素不必加括号 (2) GetHead 【GetTail 【((a,b),(c,d))】】=== (c,d) ; (3) GetHead 【GetTail 【GetHead 【((a,b),(c,d))】】】=== b ; (4) GetTail 【GetHead 【GetTail 【((a,b),(c,d))】】】=== (d ) ; 二、单选题( A )1. 〖01年计算机系考研题〗假设有60行70列的二维数组a[1…60, 1…70]以列序为主序顺序存储,其基地址为10000,每个元素占2个存储单元,那么第32行第58列的元素a[32,58]的存储地址为 。(无第0行第0列元素) A.16902 B.16904 C.14454 D.答案A, B, C 均不对 答:此题与填空题第8小题相似。(57列×60行+31行)×2字节+10000=16902 ( B )2. 设矩阵A 是一个对称矩阵,为了节省存储,将其下三角部分(如下图所示)按行序存放在一维数组B[ 1, n(n-1)/2 ]中,对下三角部分中任一元素a i,j (i ≤j), 在一维数组B 中下标k 的值是: A.i(i-1)/2+j-1 B.i(i-1)/2+j C.i(i+1)/2+j-1 D.i(i+1)/2+j ??????????????=n n n n a a a a a a A ,2 ,1,2 ,21,21 ,1

数据结构课后习题及答案

填空题(10 * 1’ = 10’) 一、概念题 .当对一个线性表经常进行的是插入和删除操作时,采用链式存储结构为宜。 .当对一个线性表经常进行的是存取操作,而很少进行插入和删除操作时,最好采用顺序存储结构。 .带头结点的单链表L中只有一个元素结点的条件是L->Next->Next==Null。 .循环队列的引入,目的是为了克服假溢出。 .长度为0的字符串称为空串。 .组成串的数据元素只能是字符。 .设T和P是两个给定的串,在T中寻找等于P的子串的过程称为模式匹配,又称P为模式。 .为了实现图的广度优先搜索,除一个标志数组标志已访问的图的结点外,还需要队列存放被访问的结点实现遍历。 .广义表的深度是广义表中括号的重数 .有向图G可拓扑排序的判别条件是有无回路。 .若要求一个稠密图的最小生成树,最好用Prim算法求解。 . 直接定址法法构造的哈希函数肯定不会发生冲突。 .排序算法所花费的时间,通常用在数据的比较和交换两大操作。 .通常从正确性﹑可读性﹑健壮性﹑时空效率等几个方面评价算法的(包括程序)的质量。 .对于给定的n元素,可以构造出的逻辑结构有集合关系﹑线性关系树形关系﹑图状关系四种。 .存储结构主要有顺序存储﹑链式存储﹑索引存储﹑散列存储四种。 .抽象数据类型的定义仅取决于它的一组逻辑特性,而与存储结构无关,即不论其内部结构如何变化,只要它的数学特性不变,都不影响其外部使用。 .一个算法具有五大特性:有穷性﹑确定性﹑可行性,有零个或多个输入﹑有一个或多个输入。 .在双向链表结构中,若要求在p指针所指的结点之前插入指针为s所指的结点,则需执行下列语句:s->prior= p->prior; s->next= p; p->prior- next= s; p->prior= s;。 .在单链表中设置头结点的作用是不管单链表是否为空表,头结点的指针均不空,并使得对单链表的操作(如插入和删除)在各种情况下统一。 .队列是限制在表的一端进行插入和在另一端进行删除的线性表,其运算遵循先进先出原则。 .栈是限定尽在表位进行插入或删除操作的线性表。 .在链式队列中,判定只有一个结点的条件是(Q->rear==Q->front)&&(Q->rear!=NULL)。 .已知链队列的头尾指针分别是f和r,则将x入队的操作序列是node *p=(node *)malloc(node); p->next=x; p->next=NULL; if(r) {r->next=p; r=p;} else {r=p; f=p;}。 .循环队列的满与空的条件是(rear+1)%MAXSIZE==fornt和(front=-1&&rear+1==MAXSIZE)。 .串是一种特殊的线性表,其特殊性表现在数据元素都是由字符组成。 .字符串存储密度是串值所占存储位和实际分配位的比值,在字符串的链式存储结构中其结点大小是可变的。 .所谓稀疏矩阵指的是矩阵中非零元素远远小于元素总数,则称该矩阵为矩阵中非零元素远远小于元素总数,则称该矩阵为稀疏矩阵。 .一维数组的逻辑结构是线性结构,存储结构是顺序存储结构;对二维或多维数组,分别按行优先和列优先两种不同的存储方式。 .在有向图的邻接矩阵表示中,计算第i个顶点入度的方法是求邻接矩阵中第i列非0元素的个数。 网中,结点表示活动,边表示活动之间的优先关系,AOE网中,结点表示事件,边表示活动。 .按排序过程中依据不同原则对内部排序方法进行分类,主要有选择排序﹑交换排序﹑插入排序归并排序等4类。 .在堆排序、快速排序和归并排序中若只从排序结果的稳定性考虑,则应选择归并排序方法;若只从平均情况下排序最快考虑,则应选择快速排序方法;若只从最坏情况下排序最快且要节省类存考虑,则应选择堆排序方法。 .直接插入排序用监视哨的作用是存当前要的插入记录,可又省去查找插入位置时对是否出界的判断。 .设表中元素的初始状态是按键值递增的,则直接插入排序最省时间,快速排序最费时间。 .下列程序判断字符串s是否对称,对称则返回1,否则返回0;如?(“abba”)返回1,?(”abab”)返回0. Int f (char*s) { Int i=0,j=0; 求串长*/

数据结构课后习题及解

数据结构课后习题及解析第五章

第五章习题 5.1 假设有6行8列的二维数组A,每个元素占用6个字节,存储器按字节编址。已知A的基地址为 1000,计算: 数组A共占用多少字节; 数组A的最后一个元素的地址; 按行存储时元素A 36 的地址; 按列存储时元素A 36 的地址; 5.2 设有三对角矩阵A n×n ,将其三条对角线上的元素逐行地存于数组B(1:3n-2)中,使得B[k]= a ij , 求: (1)用i,j表示k的下标变换公式; (2)用k表示i,j的下标变换公式。 5.3假设稀疏矩阵A和B均以三元组表作为存储结构。试写出矩阵相加的算法,另设三元组表C存放 结果矩阵。 5.4在稀疏矩阵的快速转置算法5.2中,将计算position[col]的方法稍加改动,使算法只占用一个 辅助向量空间。 5.5写一个在十字链表中删除非零元素a ij 的算法。 5.6画出下面广义表的两种存储结构图示: ((((a), b)), ((( ), d), (e, f))) 5.7求下列广义表运算的结果: (1)HEAD[((a,b),(c,d))]; (2)TAIL[((a,b),(c,d))]; (3)TAIL[HEAD[((a,b),(c,d))]]; (4)HEAD[TAIL[HEAD[((a,b),(c,d))]]]; (5)TAIL[HEAD[TAIL[((a,b),(c,d))]]];

实习题 若矩阵A m×n 中的某个元素a ij 是第i行中的最小值,同时又是第j列中的最大值,则称此元素为该 矩阵中的一个马鞍点。假设以二维数组存储矩阵,试编写算法求出矩阵中的所有马鞍点。 第五章答案 5.2设有三对角矩阵A n×n,将其三条对角线上的元素逐行的存于数组B[1..3n-2]中,使得B[k]=a ij,求:(1)用i,j表示k的下标变换公式;(2)用k表示i、j的下标变换公式。 【解答】(1)k=2(i-1)+j (2) i=[k/3]+1, j=[k/3]+k%3 ([ ]取整,%取余) 5.4在稀疏矩阵的快速转置算法5.2中,将计算position[col]的方法稍加改动,使算法只占用一个辅助向量空间。 【解答】算法(一) FastTransposeTSMatrix(TSMartrix A, TSMatrix *B) {/*把矩阵A转置到B所指向的矩阵中去,矩阵用三元组表表示*/ int col,t,p,q; int position[MAXSIZE]; B->len=A.len; B->n=A.m; B->m=A.n; if(B->len>0) { position[1]=1; for(t=1;t<=A.len;t++) position[A.data[t].col+1]++; /*position[col]存放第col-1列非零元素的个数, 即利用pos[col]来记录第col-1列中非零元素的个数*/ /*求col列中第一个非零元素在B.data[ ]的位置,存放在position[col]中*/ for(col=2;col<=A.n;col++) position[col]=position[col]+position[col-1]; for(p=1;p

相关文档
相关文档 最新文档