数据结构第五章

第五章 练习

1. 假设一个15阶的上三角矩阵A按行优先顺序压缩存储在一维数组B中，则非零元素

A[9,9]在B中的存储位置k=_______。（注：矩阵元素下标从1开始）。

2. 三维数组a[4][5][6](下标从0开始计，a有4*5*6个元素），每个元素的长度是2，则a[2][3][4]

的地址是_______。(设a[0][0][0]的地址是1000,数据以行为主序方式存储)。

3. 假设按低下标优先存储整数数组A[9][3][5][8]时，第一个元素的字节地址是100，每个整数占四个字节。问下列元素的存储地址是什么？ （1）a0000 (2)a1111 (3)a3125 (4) a8247

4. 按高下标优先存储方式（最右的下标为主序），顺序列出数组A[2][2][3][3]中所有元素

aijkl,列出aijkl的序列。 5. 广义表运算式HEAD(TAIL(((a,b,c),(x,y,z))))的结果是_______。 6. 求下列广义表操作的结果 GetHead 【(p,h,w)】 GetTail 【(b,k,p,h)】 GetHead 【((a,b),(c,d))】 GetTa

第五章 练习

1. 假设一个15阶的上三角矩阵A按行优先顺序压缩存储在一维数组B中，则非零元素

A[9,9]在B中的存储位置k=_______。（注：矩阵元素下标从1开始）。

2. 三维数组a[4][5][6](下标从0开始计，a有4*5*6个元素），每个元素的长度是2，则a[2][3][4]

的地址是_______。(设a[0][0][0]的地址是1000,数据以行为主序方式存储)。

3. 假设按低下标优先存储整数数组A[9][3][5][8]时，第一个元素的字节地址是100，每个整数占四个字节。问下列元素的存储地址是什么？ （1）a0000 (2)a1111 (3)a3125 (4) a8247

4. 按高下标优先存储方式（最右的下标为主序），顺序列出数组A[2][2][3][3]中所有元素

aijkl,列出aijkl的序列。 5. 广义表运算式HEAD(TAIL(((a,b,c),(x,y,z))))的结果是_______。 6. 求下列广义表操作的结果 GetHead 【(p,h,w)】 GetTail 【(b,k,p,h)】 GetHead 【((a,b),(c,d))】 GetTa

05 图

【单选题】

1. 设无向图G中有五个顶点，各顶点的度分别为2、4、3、1、2，则G中边数为（C）。 Ａ、4条 Ｂ、5条 Ｃ、6条 Ｄ、无法确定

2. 含n个顶点的无向完全图有（D）条边；含n个顶点的有向图最多有（C）条弧；含n个顶点的有向强连通图最多有（C）条弧；含n个顶点的有向强连通图最少有（Ｆ）条弧；设无向图中有n个顶点，则要接通全部顶点至少需（G）条边。

A、n2 B、n(n+1) C、n(n-1) D、n(n-1)/2 E、n+1 F、n G、n-1

3. 对下图从顶点a出发进行深度优先遍历，则（A）是可能得到的遍历序列。 A、acfgdeb B、abcdefg C、acdgbef D、abefgcd

对下图从顶点a出发进行广度优先遍历，则（D）是不可能得到的遍历序列。 A、abcdefg B、acdbfge C、abdcegf D、adcbgef

?010???4. 设图G的邻接矩阵A=101，则G中共有（C）个顶点；若G为有向图，则G中共有（D）????010??条弧；若G为无向图，则G中共有（B）条边。

A、1 B、2 C、3 D、4 E、5 F、9 G、以上答案都不对

5. 含n个顶点的图，最少有（B）个连通

第5章 数组和广义表

前面几章我们讨论了线性表、栈、队列和串都是线性数据结构，它们的组成元素都是数据元素，元素的值都是不可分解的。而这章将要讨论的数组和广义表是一种复杂的线性结构，它的组成元素是可以分解的。数组与广义表可视为线性表的推广，其特点是数据元素仍然是一个表。

本章讨论多维数组的逻辑结构和存储结构、特殊矩阵、矩阵的压缩存储、广义表的逻辑结构和存储结构等。

5.1 数组的定义与存储

数组是大家都已经很熟悉的一种数据类型，几乎所有高级语言程序设计中都设定了数组类型。

5.1.1 数组的定义

数组是由n(n>1)个相同类型的数据元素a0，al，…，ai，…，an-1构成的有限序列。n是数组的长度。其中数组中的数据元素ai是一个数据结构，它可以是整型、实型等简单数据类型，也可以是数组、结构体、指针等构造类型。根据数组元素ai的组织形式不同，数组可以分为一维数组、二维数组以及多维（n维）数组。

1.一维数组

一维数组可以看成是一个线性表或一个向量，它在计算机内是存放在一块连续的存储单元中，适合于随机查找。一维数组记为A[n]或A=( a0，al，…ai，…，an-1)。

一维数组中，一旦a0的存储地址、一个数据元素所占存储单元数k确定，则

第五章数组和广义表：习题

习 题

一、选择题

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 E.540 (2) A. 108 B. 114 C. 54 D. 60 E.150 (3)A.A[8][5]

第五章习题

5.1 假设有6行8列的二维数组A，每个元素占用6个字节，存储器按字节编址。已知A的基地址为

1000，计算：

数组A共占用多少字节； 数组A的最后一个元素的地址； 按行存储时元素A36的地址； 按列存储时元素A36的地址；

5.2 设有三对角矩阵An×n ,将其三条对角线上的元素逐行地存于数组B(1:3n-2)中，使得B[k]= aij ，

求：

（1） 用i,j表示k的下标变换公式； （2） 用k表示i,j的下标变换公式。

5.3假设稀疏矩阵A和B均以三元组表作为存储结构。试写出矩阵相加的算法，另设三元组表C存放

结果矩阵。 5.4在稀疏矩阵的快速转置算法5.2中，将计算position[col]的方法稍加改动，使算法只占用一个

辅助向量空间。 5.5写一个在十字链表中删除非零元素aij的算法。 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

习题五 数组和广义表

一、单项选择题

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

习题五 数组和广义表

一、单项选择题

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

第五章晶体结构

第五章 晶体结构

一、单项选择题（每小题1分） 1、NaCl晶体的结构基元是（ ）

A、一个Na+ B、一个正当晶胞 C、一个Na+和一个Cl- D、4个Na+和一个Cl-

2、有一AB型离子晶体，若γ+/γ- =0.57，则正离子的配位数为（ ） A、4 B、6 C、8 D、12

3、某正交晶系的晶胞参数为a=500pm、b=1000pm、c=1500pm，有一晶面在三个晶轴上的截长都是3000pm，则该晶面的晶面指标为（ ） A、（321） B、（632） C、（236） D、（123）

4、AgF属于NaCl型晶体，一个晶胞中含有多少个Ag+？（ ） A、6 B、4 C、2 D、1

5、晶体的宏观对称操作的集合可以划分为多少个点群？（ ） A、8 B、32 C、14 D、7

6、已知金属Cs为具有立方体心的晶胞，则其配位数为（ ） A、12 B、8 C、6 D、4 7、立方晶系中，下列哪种点

第四章 串 4.10

void String_Reverse(Stringtype s,Stringtype &r)//求s的逆串r {

StrAssign(r,''); //初始化r为空串 for(i=Strlen(s);i;i--) {

StrAssign(c,SubString(s,i,1));

StrAssign(r,Concat(r,c)); //把s的字符从后往前添加到r中 }

}//String_Reverse 4.11

void String_Subtract(Stringtype s,Stringtype t,Stringtype &r)//求所有包含在串s中而t中没有的字符构成的新串r {

StrAssign(r,'');

for(i=1;i<=Strlen(s);i++) {

StrAssign(c,SubString(s,i,1));

for(j=1;j

for(k=1;k<=Strlen(t)&&StrCompare(c,SubString(t,k,1));k++); //判断当前字符是否包含在t中

if(k>Strlen(t)) StrAssign(r,Concat(r,c)); } }//for

}//String_Subtract 4.12

int Replace(Stringt