数据结构答案 第6章 多维数组和广义表学习指导

第6章多维数组和广义表

6.1 知识点分析

1．多维数组概念

多维数组是向量的推广，对于二维数组A m×n既可以看成m行向量组成的向量，也可以看成n行向量组成的向量。多维数组在计算机中有两种存储形式：按行优先顺序存储和按列优先顺序存储。

2．多维数组的存储

二维数组a ij的地址为：LOC(a ij) = LOC(a00) + ( i×n + j ) × d （0下标起始的语言）三维数组a ijk的地址为：LOC(a ijk)=LOC(a000)+( (i×n×p+ j×p +k) ×d （0下标起始的语言）d为每个数据元素占有的字节数。

3．特殊矩阵

在矩阵中非零元素或零元素的分布有一定规律的矩阵称为特殊矩阵，如三角矩阵、对称矩阵、稀疏矩阵等。当矩阵的阶数很大时，用普通的二维数组存储这些特殊矩阵将会占用很多的存储单元。从节约存储空间的角度考虑，以下特殊矩阵的存储方法。

（1）对称矩阵

对称矩阵是一种特殊矩阵，n阶方阵的元素满足性质：a ij=a ji（0≤i , j≤n-1）。对称矩阵是关于主对角线的对称，因此只需存储上三角或下三角部分的数据即可。

（2）三角矩阵

三角矩阵的特殊性是以主对角线划分矩阵。下三角矩阵，主对角线以上均为同一个常数；上三角矩阵，主对角线以下均为同一个常数，可以采用压缩存储。

（3）稀疏矩阵

在m*n的矩阵中有t个非零元素，且t远小于m×n，这样的矩阵称稀疏矩阵。为了节约存储空间，稀疏矩阵中零元素无需存储，只需存储矩阵中的非零元素。稀疏矩阵常用的有：三元组表存储、带行指针的链表存储、十字链表存储等存储方法。

4．广义表

广义表是n（n≥0）个数据元素的有序序列，广义表的元素可以是单元素，也可以是一个广义表。由于广义表的元素有两种形式，所以其结点的存储形式也有两种：

（1）表结点由标志域、表头指针域、表尾指针域组成。

（2）原子结点由标志域和值域组成。

5．广义表与线性表的区别和联系

线性表是具有相同类型的n个数据元素的有限序列，记为a1、a2、a3、……、a n。广义表也是n个数据元素的有限序列，记为a1、a2、a3、……、a n。线性表中的元素必须具有相同的类型，而广义表中的成员，既可以是单个元素（原子），也可以是一个广义表（子表）。当广义表中的每一个a i元素都是数据元素，且具有相同类型时，则它就是一个线性表，因此可以说广义表是线性表的一种推广，或者说线性表是广义表的一个特例。

6.2 典型习题分析

【例1】设二维数组A5×6的每个元素占4个字节，存储器按字节编址。已知A的起始地址为2000，计算：

（1）数组的大小？

（2）A的终端结点a45的存储地址？

（3）按行优先顺序存储时，a25的存储地址？

（4）按列优先顺序存储时，a25的存储地址？

答：

（1）数组的大小（即数组A共占多少字节）：5×6×4=120B。

（2）一个结点a ij的存储地址是该结点所占用的存储空间的第1个字节的地址（即起始地址），它等于：基地址+排在a ij之前的结点个数×每个结点所占用的字节数。

a45的起始地址：LOC(a45)=2000+(4×6+5)×4=2116

（3）在按行优先顺序存储时，排在a ij之前的结点的个数为：在前i行（即0~i-1行）上共有i×n个结点，在第i行上a ij之前有j个结点（0~j-1列）。所以按行优先存储的地址计算公式为：LOC(a ij)= LOC(a00)+(i×n+j)×d

LOC(a25)= 2000+(2×6+5)×4=2068

（4）在按列优先顺序存储时，排在a ij之前的结点的个数为：在前j列（即0~j-1列）上共有j×m个结点，在第j列上a ij之前有i个结点（0~i-1行）。所以按列优先存储的地址计算公式为：LOC(a ij)= LOC(a00)+(j×m+i)×d

LOC(a25)=2000+(5×5+2)×4=2108

【例2】特殊矩阵和稀疏矩阵哪一种压缩存储后会失去随机存储功能？为什么？

答：对于像三角矩阵等特殊矩阵由于压缩存储时将其存储在一个线性数组向量中，矩阵元素a ij的下标i，j与它在向量中的对应元素b k下标k有一对应关系，故不会失去随机存储功能。而像稀疏矩阵，其压缩存储的方式是将其非零元素存储在一个三元组中，以三元组数组a[k]形式存储，矩阵元素a ij下标i，j与数组中对应元素a[k]行下标k无对应关系，故失去随机存储功能。

【例3】求矩阵的转置矩阵

分析：对于一个m×n的矩阵A mn，其转置矩阵是一个n×m的矩阵B nm，且B[i][j]=A[j][i]，

0≤i

void trs(A,B)

maxix A,B;

{ int i,j;

for (i=0;i

for (j=0;j

B[j][i]=A[i][j];

}

【例4】求两个矩阵的乘

分析：设两个矩阵相乘：C=A×B，

其中A是一个m×n的矩阵，B是一个n×k的矩阵，则C为一个m×k的矩阵。其函数如下：void mut(C,A,B)

maxix A,B,C;

{ int i,j,k;

for (i=0;i

for (j=0;j

{ C[i][j]=0;

for (k=0;k

C[i][j]=C[i][j]+A[i][k]*B[k][j];

}

}

中存在一个元素a ij，满足a ij是第i行最小的元素，且是第j列最大的【例5】若矩阵A m

×n

元素，则称a ij是矩阵A的鞍点，请编写一个算法，找出矩阵A的所有鞍点。

分析：找矩阵A的所有鞍点的基本思想是：先逐行找出本行值最小的元素，确定其所在的列，并在此列中选值最大的元素，若两者值相等，即选中一个鞍点。

void Spoint(int *a,int m,int n)

{ int i,j,k,c,max,min,r=0;

for (i=0;i

{ min=a[i][0]; // 假设a[i][0]为最小

c=0;

for (j=1;j

if a[i][j]

{ min=a[i][j];

c=j; // c记录最小值的列值

}

max=a[0][c];

for (k=1;k

if (a[k][c]>max)

max=a[k][c];

if (max==min) // max==min,即鞍点

{ printf(“\ni=%d,j=%d,a[i][j]=%d”,i,j,max);

r++; // r记录鞍点的个数

}

}

if (r==0)

printf(“\n no saddlepoin ter”); // 无鞍点

}

【例6】试编写一个在以H为头的十字链表中查找数据为k的结点的算法。

分析：每个非零元素作为一个结点，结点中除了表示非零元素所在的行（i）、列（j）、值（v）的三元组以外还有两个指针域，其结构如图6-1所示。其中：列指针域down用来指向本列中下一个非零元素；行指针域right用来指向本行中下一个非零元素。

图6-1 十字链表的结点结构

结点的结构定义如下：

typedef struct node

{ int row,col; // 定义行、列

struct node *down ,*right; // 定义列指针、行指针

union // 定义一个共用体

{ int v; // 定义值域

struct node *next;// 表头结点使用的next域

}tag;

};

int Searchmat(struct node *H, int k, int *rown, int *coln)

{ struct node *p, *q;

p=H->tag.next;

while (p!=H)

{ q=p->right;

while (p!=q)

{ if (q->tag.v= =k) // 查找成功处理

{ *rown=q->row;

*coln=q->col

return 1;

}

q=q->right;

}

p=p->tag.next; }

return 0;

}

main() // 主函数 { struct node *H; int i,j,k;

H=Createmat(); // 设创建十字链表的函数Createmat()已存在 printf(“输入要查找的值：”);

scanf(“%d “, &k); // 输入要查找的值 if (Searchmat(H,k,&i,&j)) // 调用查找函数 printf(“%d 在第%d 行第%d 列\n “,k,i,j); else

printf(“查无此值！“); }

【例7】 已知广义表LS=((a,b,c),(d,e,f,g))，写出用取表头（Head ）和取表尾（Tail ）函数驱除取出原子e 的运算。

分析：L1=Tail(LS)=（(d,e,f,g)）

L2=Head(L1)= (d,e,f,g) L3=Tail(L2)=( e,f,g) L4=Head(L3)=e

所以取出原子的运算是Head （Tail(Head(Tail(L2))))=e

【例8】画出广义表：A(a,B(b,d),C(e,B(b,d),L(A,f,g))) 的图形表示。

分析：在广义表中为了把单元素和表区分开来，一般用小写字母表示元素，用大写字母表示子表；在画图时用圆圈表示表，用方框表示元素，并用线段把表和它的元素连接起来，则可以得到如图6-2所示广义表的图形表示。

【例9

表结点为： 元素结点为：

其C语言描述如下：

typedef enum{ATOM,LIST} Elemtag；

typedef struct GLNode

{ Elemtag tag; // 公共部分，用于区分原素和表

union // 元素结点和表结点的联合部分

{ char data; // 元素结点的值域

struct

{ struct GLNode *hp,*tp;

}ptr; // ptr是表结点的指针域，ptr.hp指向表头，ptr.tp指向表尾}

}*Glist;

在求广义表深度的递归算法中，若结点为原子则深度为0，若是空表深度为1，否则返回头指针与尾指针所指广义表的深度最大值，填空求表深度的递归算法。

int GlistDepth(Glist L)

{ int m,n;

if (!L->tag)

①

else if( ②)

return 1;

m= GlistDepth ( ③)+1;

n= GlistDepth ( ④);

return m>n ? ⑤;

}

答：①return 0;

②!L

③L->ptr.hp

④L->ptr.tp

⑤m:n

【例10】写一个算法，判断广义表中左、右括号是否配对。

分析：可以将广义表视为一个字符串，依次扫描字符串中的字符，遇到“（”时入栈，遇到“）”时，出栈。扫描完毕，若栈空说明括号配对；否则括号不配对。其算法如下：int BracketMatch(char *s) // s为广义表

{

char *c;

SeqStack T;

c=S;

InitStack(&T); // 初始化栈

While (*c!=?\0?);

{ if (*c==?(…)

Push(&T,*c);

else

if (*c==?)?)

if(StackEmpty(&T))

return (0); // 栈空，不能匹配，返回0

else

Pop(&T);

c++;

}

if (StackEmpty(&T))

return(0); // 栈不空，说明括号不配对，返回0 else

return(1); // 栈空，说明括号配对，返回1 }

6.3 单元练习6解答

一．判断题答案

二．填空题答案

（1）按列优先顺序存储（2）随机

（3）n （4）O(n*m)

（5）LOC[1,2]=2000+(1*4+2)*4=2024 （6）3

（7）行数（8）n（n-1）/2

（9） 4 （10）十字链表

（11）广义表（或子表）（12）b

（13）head(tail(tail(head(L)))) （14）（c,d）

（15）n（n-1）/2+1 （16）n

（17） 3 （18）4

（19）∞（20）((b),((c,(d))))

三．选择题答案

四．算法阅读题答案

（1）分析：注意k的变化依次为：0，2，5，9，14，正好是a ii在A中的存储位置。在循环中k每次增加i+2。

第i行主对角线上的元素a ii，其在A中的位置为:

i(i+1)/2+i；(1) 第i+1行主对角线上的元素a i+1 i+1，其在A中的位置为:

(i+1)(i+2)/2+(i+1), (2) 式(2)-式(1)得：i-2。

（2）程序填空

①a->t<=0

②col<0 || col >=a->n

③k=0

④k++

⑤sum + a->data[k].v

五．编程题答案

（1）【程序代码】

#include "stdio.h"

#define ERROR –99999

typedef struct

{ int row;

int col;

int data;

}Triple;

int MDSum(Triple *a)

{ int i;

int sum=0;

if (a[0].row!=a[0].col)

return ERROR;

for (i=1;i<=a[0].data;i++)

{ if (a[i].row==a[i].col)

sum+=a[i].data;

}

return sum;

}

（2）分析：设j为原子个数，则求广义表中原子元素个数的算法可递归定义如下：

0 LS为空

表尾原子元素个数+1 LS非空且表头为原子元素j=

表头子表原子元素个数+表尾原子元素个数+1 LS非空且表头子表

【程序代码】

int atomnum(Gnode *head)

{

if (head==NULL)

return 0;

if (head->tag==0)

return(atomnum(head->next)+1);

else

return(atomnum(head->next)+atomnum(head->v.sublist));

}

（3）【程序代码】

int maxele(Gnode *head)

{

int m=0,a;

while(head)

{

if (head->tag==1)

{ a=maxele(head->v.sublist);

if (a>m)

m=a;

}

else

if (head->v.data>m)

m=head->v.data;

head=head->next;

}

return m;

}

数组和广义表习题

一、填空题 1．通常采用___________存储结构来存放数组。对二维数组可有两种存储方法：一种是以___________为主序的存储方式，另一种是以___________为主序的存储方式。 2. 用一维数组B与列优先存放带状矩阵A中的非零元素A[i,j] (1≤i≤n,i-2≤j≤i+2),B 中的第8个元素是A 中的第_ _行，第_ _列的元素。 3．设n行n列的下三角矩阵A已压缩到一维数组B[1..n*（n+1）/2]中，若按行为主序存储，则A[i,j]对应的B中存储位置为_______。 4. 所谓稀疏矩阵指的是_ 。 5. 广义表简称表，是由零个或多个原子或子表组成的有限序列，原子与表的差别仅在于____ 。为了区分原子和表，一般用 ____表示表，用 _____表示原子。一个表的长度是指 __，而表的深度是指__ __ 6、设数组a[1..50，1..80]的基地址为2000，每个元素占2个存储单元，若一行序为主序顺序存储，则元素a[45，68]的存储地址为；若以列序为主序存储，则元素a[45，68]的存储地址为。 7、有一个8ⅹ8的下三角矩阵A，若采用行序为主序顺序存储于一维数组a[1..n]，则n的值为。 8、三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素 的、和。 9、已知广义表A=（（（a））），则A的表头为：，A的表尾为：。 10、求下列广义表操作的结果： （1）Head ((a,b),(c,d)) == ; //头元素不必加括号 （2）Head（Tail((a,b),(c,d))）== ; （3）Head（Tail（Head((a,b),(c,d))））== ; （4）Tail(Head(Tail((a,b),(c,d))))== ; 11、设W为一个二维数组，其每个数据元素占用4个字节，行下标i从0到7 ，列下标j从0到3 ，则二维数组W的数据元素共占用＿_____＿个字节。W中第6 行的元素和第4 列的元素共占用＿_______＿个字节。若按行顺序存放二维数组W，其起始地址为100，则二维数组元素W[6，3]的起始地址为＿________＿。 12、广义表A= (a,(a,b),((a,b),c)),则它的深度为____________，它的长度为____________。 13、设有一个n阶的下三角矩阵A，如果按照行的顺序将下三角矩阵中的元素（包括对角线上元素）存放在n(n+1)个连续的存储单元中，则A[i][j]与A[0][0]之间有_______个数据元素。 14、广义表的深度是__表展开后所含括号的层数 ____ 二、选择题 1、一个nⅹn的对称矩阵，如果以行或列为主序放入内存，则其容量为( )。 A、n*n B、n*n/2 C、(n+1)*n/2 D、(n+1)*(n+1)/2 2、对数组经常进行的两种基本操作是( ) 。

数据结构 严蔚敏 清华大学出版社 习题及答案

第1章绪论 (3) 1、填空题 (3) 2、应用题 (3) 第2章线性表 (4) 1、填空题 (4) 2、选择题 (5) 3、判断题 (5) 4、程序设计题 (5) 第3章栈和队列 (8) 1、填空题 (8) 2、选择题 (8) 3、判断题 (9) 第4章串 (9) 1、选择题 (9) 2、判断题 (9) 第5章数组和广义表 (9) 1、填空题 (9) 2、选择题 (9) 3、判断题 (10) 第6章树和二叉树 (10) 1、填空题 (10) 2、选择题 (11)

4、应用题 (11) 5、读程序写结果 (18) 第7章图 (19) 1、填空题 (19) 2、选择题 (19) 3、判断题 (20) 4、应用题 (20) 5、程序设计题 (25) 第8章动态存储管理 (25) 1、填空题 (25) 2、选择题 (25) 3、判断题 (25) 4、应用题 (25) 5、程序设计题 (25) 第9章查找 (26) 1、选择题 (26) 2、判断题 (27) 3、应用题 (27) 4、程序设计题 (28) 第10章内部排序 (29) 1、填空题 (29)

3、判断题 (30) 4、应用题 (30) 第11章外部排序 (31) 第12章文件 (31) 第1章绪论1、填空题 1.常见的数据结构有_线性__结构，__树形___结构，__图形__结构等三种。 2.常见的存储结构有__顺序存储_______结构，__链式存储____结构等两种。 3.数据的基本单位是_数据元素___，它在计算机中是作为一个整体来处理的。 4.数据结构中的结构是指数据间的逻辑关系，常见的结构可分为两大类，__线性结构____和__非线性结构___。 2、应用题 1、给出以下算法的时间复杂度. void fun(int n) { int i=1,k=100; while(i

数据结构习题广义线性表-多维数组和广义表

第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 数组的基本操作有存取、修改、检索和排序等，没有插入与删除操 【解答】C 【分析】数组属于广义线性表，数组被创建以后，其维数和每维中的元素个数是确定的，所以，数组通常没有插入和删除操作。 ⑷ 对特殊矩阵采用压缩存储的目的主要是为了（） A 表达变得简单 B 对矩阵元素的存取变得简单 C 去掉矩阵中的多余元素 D 减少不必要的存储空间 【解答】D 【分析】在特殊矩阵中，有很多值相同的元素并且他们的分布有规律，没有必要为值相同的元素重复存储。 ⑸ 下面（）不属于特殊矩阵。 A 对角矩阵 B 三角矩阵 C 稀疏矩阵 D 对称矩阵 【解答】C ⑹ 若广义表A满足Head(A)=Tail(A)，则A为（） A ( ) B (( )) C (( ),( )) D(( ),( ),( )) 【解答】B

(完整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．假设以行序为主序存储二维数组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)))))

习题2参考答案及数组广义表习题

习题2参考答案 一、单项选择题 1．A 2．A 3．D 4．C 5．D 6．A 7．B 8．B 9．C 10．A 11．D 12．B 13．C 14．B 15．C 16．C 17．B 18．D 19．C 20．A 二、填空题 1．线性 2．n-i+1 3．相邻 4．前移，前，后 5．物理存储位置，链域的指针值 6．前趋，后继 7．顺序，链接 8．一定，不一定 9．线性，任何，栈顶，队尾，队头 10．单链表，双链表，非循环链表，循环链表 11．使空表和非空表统一；算法处理一致 12．O(1)，O(n) 13．栈满，栈空，m，栈底，两个栈的栈顶在栈空间的某一位置相遇 14．2、3 15．O(1) 三、简答题 1．头指针是指向链表中第一个结点（即表头结点）的指针；在表头结点之前附设的结点称为头结点；表头结点为链表中存储线性表中第一个数据元素的结点。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空，否则表示空表的链表的头指针为空。 2．线性表具有两种存储结构即顺序存储结构和链接存储结构。线性表的顺序存储结构可以直接存取数据元素，方便灵活、效率高，但插入、删除操作时将会引起元素的大量移动，因而降低效率：而在链接存储结构中内存采用动态分配，利用率高，但需增设指示结点之间关系的指针域，存取数据元素不如顺序存储方便，但结点的插入、删除操作较简单。 3．应选用链接存储结构，因为链式存储结构是用一组任意的存储单元依次存储线性表中的各元素，这里存储单元可以是连续的，也可以是不连续的：这种存储结构对于元素的删除或插入运算是不需要移动元素的，只需修改指针即可，所以很容易实现表的容量的扩充。 4．应选用顺序存储结构，因为每个数据元素的存储位置和线性表的起始位置相差一个

目前最完整的数据结构1800题包括完整答案 第五章 数组和广义表

第 5 章数组和广义表 一、选择题 1.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其 存储地址为1，每个元素占一个地址空间，则a85的地址为（）。【燕山大学 2001 一、2 （2分）】 A. 13 B. 33 C. 18 D. 40 2. 有一个二维数组A[1:6，0:7] 每个数组元素用相邻的6个字节存储，存储器按字节编址， 那么这个数组的体积是（①）个字节。假设存储数组元素A[1，0]的第一个字节的地址是0， 则存储数组A的最后一个元素的第一个字节的地址是（②）。若按行存储，则A[2，4]的第 一个字节的地址是（③）。若按列存储，则A[5，7]的第一个字节的地址是（④）。就一般情 况而言，当（⑤）时，按行存储的A[I，J]地址与按列存储的A[J，I]地址相等。供选择的 答案：【上海海运学院 1998 二、2 （5分）】 ①-④： A．12 B. 66 C. 72 D. 96 E. 114 F. 120 G. 156 H. 234 I. 276 J. 282 K. 283 L. 288 ⑤： A．行与列的上界相同 B. 行与列的下界相同 C. 行与列的上、下界都相同 D. 行的元素个数与列的元素个数相同 3. 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10， 数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为( )。 A. BA+141 B. BA+180 C. BA+222 D. BA+225 【南京理工大学 1997 一、8 （2分）】 4. 假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存 储单元，基地址为10，则LOC[5，5]=（）。【福州大学 1998 一、10 (2分)】 A. 808 B. 818 C. 1010 D. 1020 5. 数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000 的内存单元中，则元素A[5，5]的地址是( )。【南京理工大学 2001 一、13 （1.5分）】 A. 1175 B. 1180 C. 1205 D. 1210 6. 有一个二维数组A[0:8,1:5],每个数组元素用相邻的4个字节存储，存储器按字节编址， 假设存储数组元素A[0,1]的第一个字节的地址是0，存储数组A的最后一个元素的第一个字 节的地址是（①）。若按行存储，则A[3,5]和 A[5,3]的第一个字节的地址是（②） 和（③）。若按列存储，则A[7,1]和A[2,4]的第一个字节的地址是（④）和（⑤）。【上海海运学院 1996 二、1 （5分）】 ①-⑤:A.28 B.44 C.76 D.92 E.108 F.116 G.132 H.176 I.184 J.188 7. 将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1‥298]中，A中元 素A6665（即该元素下标i=66，j=65），在B数组中的位置K为（）。供选择的答案： A. 198 B. 195 C. 197 【北京邮电大学 1998 二、5 （2分）】 8. 二维数组A的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范圈 从1到10。从供选择的答案中选出应填入下列关于数组存储叙述中（）内的正确答案。（1）存放A至少需要（）个字节； （2）A的第8列和第5行共占（）个字节； （3）若A按行存放，元素A[8，5]的起始地址与A按列存放时的元素（）的起始地

第 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

第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列元素） Ａ．16902 Ｂ．16904 Ｃ．14454 Ｄ．答案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 的值是： Ａ．i(i-1)/2+j-1 Ｂ．i(i-1)/2+j Ｃ．i(i+1)/2+j-1 Ｄ．i(i+1)/2+j ??????????????=n n n n a a a a a a A ,2 ,1,2 ,21,21 ,1

数据结构复习题 答案 新编新

第5章数组与广义表 一、选择题（每小题1分，共10分） 1.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ A ）。 A.110 B.108 C.100 D.120 2.在数组A中，每一个数组元素A[i][j]占用3个存储字节，行下标i从1到8，列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字节数是（ C ）。 A.80 B.100 C.240 D.270 3.假设有60行70列的二维数组a[1…60, 1…70]以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为（ C ）。（无第0行第0列元素） A.16902 B.16904 C.14454 D.答案A, B, C均不对 4.将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1‥298]中，A中元素A6665（即该元素下标i=66，j=65），在B数组中的位置K为（ A ）。 A. 198 B. 195 C. 197 D.196

5.数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是（ A ）。 A. 1175 B. 1180 C. 1205 D. 1210 6.假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]= （ B ）。 A. 808 B. 818 C. 1010 D. 1020 7. 设有数组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 8.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ B ）。 A、 13 B、 33 C、 18 D、 40 9. 二维数组A的每个元素是由6个字符组成的串，其行下标i=0,1,…,8,列下标j=1,2,…,10。若A按行先存储，元素A[8,5]的起始地址与当A按列先存储时的元素（ B ）的起始地址相同。设每个字符占一个字节。 A、 A[8,5] B、 A[3,10] C、 A[5,8] D、 A[0,9]

数组和广义表习题

习题五数组 5.1 单项选择题（其中A[i..j]表示下标从i到j） 1. 常对数组进行的两种基本操作是__C__。 A. 建立与删除 B. 索引和修改 C. 查找和修改 D. 查找与索引 2. 二维数组M的成员是6个字符（每个字符占一个存储单元，即一个字节）组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M 至少需要__①D__个字节；M 的第8列和第5行共占__②B__个字节。 ①A. 90 B. 180 C. 240 D. 540 ②A. 108 B. 114 C. 54 D. 60 4. 数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数是__C__。 A. 80 B. 100 C.240 D. 270 5. 数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为_C___。 A. SA+141 B. SA+144 C. SA+222 D. SA+225 (7*10+4)*3=222 6. 数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[5][8]的起始地址为_B___。 A. SA+141 B. SA+180 C. SA+222 D. SA+225 (7*8+4)*3=180 5.2 填空题（将正确的答案填在相应的空中，其中A[i,j]表示下标从i到j） 1. 已知二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC(A[0][0])，则A[i][j]的地址是_ LOC(A[0][0]) +(i*n+j)*k___。 2. 二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元并且A[0][0]的存储地址是200，则A[6][12]的地址是_326___。200+(12*10+6)*1=326 3. 二维数组A[10..20][5..10]采用行序为主方式存储，每个元素占4个存储单元，并且A[10][5]的存储地址是1000，则A[18][9]的地址是__1000+(8*6+4)*4=1208__。 5.3算法设计题: 1. 假设稀疏矩阵A和B均以三元组顺序表作为存储结构。试写出矩阵相加的算法，另设三元组表C存放结果矩阵。 2. 假设系数矩阵A和B均以三元组顺序表作为存储结构。试写出满足以下条件的矩阵相加

第五章 数组和广义表

第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 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（ B ）。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2 2若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，p N,若p N是n，则p i是( D )。 A. i B. n-i C. n-i+1 D. 不确定 3 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( B ) A. 1和 5 B. 2和4 C. 4和2 D. 5和1 4 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( C )。 A． 6 B. 4 C. 3 D. 2 5 设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ C ） A．求子串 B．联接 C．匹配 D．求串长 6 设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ B ）。 A. 13 B. 33 C. 18 D. 40 7 已知广义表LS＝((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是( C )。 A. head(tail(LS)) B. tail(head(LS)) C. head(tail(head(tail(LS))) D. head(tail(tail(head(LS)))) 8 模式串t=‘abcaabbcabcaabdab’，该模式串的next数组的值为（ D ），nextval数组的值为（ F ）。 A．0 1 1 1 2 2 1 1 1 2 3 4 5 6 7 1 2 B．0 1 1 1 2 1 2 1 1 2 3 4 5 6 1 1 2 C．0 1 1 1 0 0 1 3 1 0 1 1 0 0 7 0 1 D．0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2 E．0 1 1 0 0 1 1 1 0 1 1 0 0 1 7 0 1 F．0 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 1 二、填空题 1 在作进栈运算时应先判别栈是否_(1)满_;在作退栈运算时应先判别栈是否_(2)空_；当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为_(3)n_。 2 设循环队列存放在向量sq.data[0:M]中，则队头指针sq.front在循环意义下的出队操作可表示为__return(sq.data(sq.front))；sq.front=(sq.front+1)%(M+1)；_____，若用牺牲一个单元的办法来区分队满和队空（设队尾指针sq.rear）,则队满的条件为_(sq.rear+1)%(M+1)==sq.front；_。 3 串是一种特殊的线性表，其特殊性表现在__(1) 其数据元素都是字符__；串的两种最基本的存储方式是__(2) 顺序存储__、__(3) 和链式存储__；两个串相等的充分必要条件

数据结构练习题-数组和广义表

已知二维数组A[3][5]，其每个元素占3个存储单元，并且A[0][0]的存储地址为1200。 求元素A[1][3]的存储地址（分别对以行序和列序为主序存储进行讨论），该数组共占用多少个存储单元？ 【解答】按照以行序为主序存储公式： LOC(i，j)=LOC(c1，c2)+[(i-c1)*(d2-c2+1)+(j-c2)]*L 在C语言中有：LOC(i，j)=LOC(0，0)+(i*(d2+1)+j)*L 则： LOC(A[1][3])=1200+(1*5+3)*3=1224 (按行序存储) LOC(A[1][3])=1200+(3*3+1)*3=1230 (按列序存储) 有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，A[1][1]为第一元素，其存储地址为1，每个元素占一个地址空间，求A[7][5]和A[5][6]的地址。 【解答】按照公式： LOC(A[7][5])=7(7-1)/2＋5 = 26 LOC(A[5][6])=LOC(A[6][5])=6(6-1)/2+5=20 设有一个二维数组A[m][n]，设A[0][0]存放位置在644，A[2][2]存放位置在676，每个元素占一个空间，问A[3][3]存放在什么位置？ 因为A[0][0]存放位置在644，A[2][2]存放位置在676，每个元素占一个空间，说明一行有15个元素（算法：（676－2－644）/2）。A[3][3]存放位置是692。 二维数组A[9][10]的元素都是6个字符组成的串，请回答下列问题： （1）存放A至少需要( )个字节； （2）A的第7列和第4行共占( )个字节； （3）若A按行存放，元素A[7][4]的起始地址与A按列存放时哪一个元素的起始地址一致。 【解答】按照题5.1给出的公式： （1）存放A需要9*10*6=540个字节 （2）A的第7列和第行共占(9+10-1)*6=108个字节（3） LOC(A[7][4])= LOC(A[0][0])+[7*10+4]*L (按行序存储) LOC(A[i][j])= LOC(A[0][0])+[j*9+i]*L （按列序存储，0<=i<=8,0<=j<=9)所以,i=2,j=8。 即元素A[7][4]的起始地址与A按列存放时A[2][8]的起始地址一致。 什么是广义表？请简述广义表和线性表的主要区别。 【解答】广义表是零至多个元素的有限序列，广义表中的元素可以是原子，也可以是子表。 从“元素的有限序列”角度看，广义表满足线性结构的特性：在非空线性结构中，只有一个 称为“第一个”的元素，只有一个称为“最后一个”的元素，第一元素有后继而没有前驱， 最后一个元素有前驱而没有后继，其余每个元素有唯一前驱和唯一后继。从这个意义上说， 广义表属于线性结构。当广义表中的元素都是原子时，广义表就蜕变为线性表。 求广义表D=(a，(b，()，c)，((d)，e))的长度和深度。 【解答】3和3

数据库系统l试题库及答案 第5章数组和广义表

第5章 数组和广义表 5.1数组 一、填空题 1. 假设有二维数组A 6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A 的起始存储位置 （基地址）为1000，则数组A 的体积（存储量）为 ；末尾元素A 57的第一个字节地址为 。 2. 三元组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素 的 、 和 。 3. 设数组a[1…60, 1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则 元素a[32,58]的存储地址为 。 4. 设n 行n 列的下三角矩阵A 已压缩到一维数组B[1..n*（n+1）/2]中，若按行为主序存储，则A[i,j] 对应的B 中存储位置为 。 5. 设有一个10阶对称矩阵A 采用压缩存储方式（以行为主序存储：a 11=1），则a 85 的地址为 。 6. 设下三角矩阵A 如果按行序为主序将下三角元素A i j (i ≤j)存储在一个一维数组B[1..n(n+1)/2]中， 对任一个三角矩阵元素A ij ,它在数组B 中的下标为 。 二、选择题 1. （ ）假设有60行70列的二维数组a[1…60, 1…70]以列序为主序顺序存储，其基地址为10000， 每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为 。 A ．16902 B ．16904 C ．14454 D ．答案A, B, C 均不对 2. （ ）对特殊矩阵采用压缩存储的目的主要是为了 。 A ．表达变得简单 B ．对矩阵元素的存取变得简单 C ．去掉矩阵中多余元素 D ．减少不必要的存储空间 3. （ ）对于n 阶对称矩阵，如果以行序或列序放入内存中，则需要 个存储单元。 A ．n(n+1)/2 B ．n(n-1)/2 C ． n 2 D ．n 2 /2 4. 有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时， 所需的字节数是 。 A. 60 B. 66 C. 18000 D. 33 5. 对稀疏矩阵进行压缩存储目的是（ ）。 A ．便于进行矩阵运算 B ．便于输入和输出 C ．节省存储空间 D ．降低运算的时间复杂度 6. （ ）设矩阵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 三、判断题： 1．（ ）一个稀疏矩阵Am*n 采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把 ?????? ? ???????=n n n n a a a a a a A ,2,1 ,2,21,21,1Λ Λ

数据结构1800试题-第5章 数组和广义表 - 答案

第五章数组和广义表答案 部分答案解释如下。 1. 错误。对于完全二叉树，用一维数组作存储结构是效率高的（存储密度大）。 4. 错误。数组是具有相同性质的数据元素的集合，数据元素不仅有值，还有下标。因此，可以说数祖是元素值和下标构成的偶对的有穷集合。 5. 错误。数组在维数和界偶确定后，其元素个数已经确定，不能进行插入和删除运算。 6. 错误。稀疏矩阵转置后，除行列下标及行列数互换外，还必须确定该元素转置后在新三元组中的位置。 8. 错误。广义表的取表尾运算，是非空广义表除去表头元素，剩余元素组成的表，不可能是原子。 9. 错误。广义表的表头就是广义表的第一个元素。只有非空广义表才能取表头。 10. 错误。广义表中元素可以是原子，也可以是表（包括空表和非空表）。 11. 错误。广义表的表尾，指去掉表头元素后，剩余元素所组成的表。 三、填空题 1. 顺序存储结构 2.（1）9572（2）1228 3.（1）9174（2）8788 4. 1100 5. 1164 公式：LOC(a ijk)=LOC(a000)+[v2*v3*(i-c1)+v3*(j-c2)+(k-c3)]*l (l为每个元素所占单元数) 6. 232 7. 1340 8. 1196 9. 第1行第3列 10. (1)270 (2)27 (3)2204 11. i(i-1)/2+j (1<=i,j<=n) 12. (1)n(n+1)/2 (2)i(i+1)/2 (或j(j+1)/2) (3)i(i-1)/2+j (4)j(j-1)/2+i (1<=i,j<=n) 13. 1038 三对角矩阵按行存储：k=2(i-1)+j (1<=i,j<=n) 14. 33 (k=i(i-1)/2+j) (1<=i,j<=n) 15. 非零元很少(t<