数据结构复习笔记数组和广义表以及树的基本概念

2-1

设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为 (2分)

13
33
18
40

/

a85 - a11 = a ( 7 row , 4 col)

7 row : 1 + 2 +3+4+5+6+7 = (1+7)*7/2 = 28

4 col : 4

地址 = 首地址 + (28+4)*sizeof(a) = 1 + 32 = 33

已知aij 求解 auv

&auv = &aij + [(1+2+3+.....(u-i))+(v-j)]*sizeof(a);

这是对于压缩矩阵的运算来说

普通的计算是这样的

m 代表行数目， n 代表列数

已知aij的地址，求解auv

a(u-i)(v-j)

&auv = &aij + [(u-i)*n+(v-j)]*sizeof(a);

/

2-2

设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为（）。 (2分)

BA+141
BA+180
BA+222
BA+225

2-3

将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1‥298]中，A中元素A6665（即该元素下标i=66，j=65），在B数组中的位置K为（）。 (2分)

198
195
197
199

/

形如

的n×n矩阵A称为三对角矩阵，其中第(i,j)个元素在j>i+1和j<i-1时为零

/

2-4

若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B［1..(n(n+1))/2］中，则在B中确定aij（i<j）的位置k的关系为（）。 (2分)

i*(i-1)/2+j
j*(j-1)/2+i
i*(i+1)/2+j
j*(j+1)/2+i

/

n阶对称矩阵中的元素满足下述条件：aij=aji，(1＜=i，j＜=n)。对称矩阵中的每一对数据元素可以共用一个存储空间，因此可以将n2个元素压缩存储到n(n+1)/2个元的空间中，即可以一维数组保存。
假设用一维数组B[n(n+1)/2]作为对称矩阵A的存储结构，则B[k]和矩阵元素aij的下标i、j的对应关系为：
当i＞-j时，k=i(i-1)/2+i；
当i＜j时，k=j(j-1)/2+i；

/

2-5

已知广义表L=（（x,y,z），a，（u，t，w）），从L表中取出原子项t的运算是（）。 (2分)

head（tail（tail（L）））
tail（head（head（tail（L））））
head（tail（head（tail（L））））
head（tail(head（tail（tail（L）））)）

广义表的基本概念和运算

题目理解：

1:利用广义表的head和tail操作写出函数表达式，把以下各题中的单元素banana从广义表中分离出来：


         （1） L1（apple, pear, banana, orange）


         （2） L2（（apple, pear）, （banana, orange））


         （3） L3（（（apple）, （pear）, （bananA）, （orange）））


         （4） L4（（（（apple）））, （（pear））, （bananA）, orange）


         （5） L5（（（（apple）, pear）, bananA）, orange）


         （6） L6（apple, （pear, （bananA）, orange））


　　【答案】


         （1） Head （Tail （Tail （L1） ） ）


         （2） Head （Head （Tail （L2） ） ）


         （3） Head （Head （Tail （Tail （Head （L3） ） ） ） ）


         （4） Head （Head （Tail （Tail （L4） ） ） ）


         （5） Head （Tail （Head（L5） ） ）


         （6） Head （Head （Tail （Head （Tail （L6） ） ） ） ）

code

2-6

广义表A=(a,b,(c,d),(e,(f,g))),则式子Head(Tail(Head(Tail(Tail(A)))))的值为（）。 (2分)

(g)

(d)

c

d

2-7

设广义表L=（（a,b,c）），则L的长度和深度分别为（） (2分)

1和1

1和3

1和2

2和3

广义表长度是第一层括号里逗号的数目 + 1

深度是每个元素的括号匹配数+1

()一层 (())两层（（（）））三层 ( ( ) ( ) ( ( ) ) )三层，取最深的一层作为深度

2-8

树最适合于用来表示 (1分)

有序数据元素

无序数据元素

元素之间无联系的数据

元素之间具有分支层次关系的数据

2-9

设树T的度为4，其中度为1、2、3、4的结点个数分别为4、2、1、1。则T中有多少个叶子结点？ (3分)

4

6

8

10

n0：度为0的结点数，n1:度为1的结点 n2：度为2的结点数。 N是总结点。

在二叉树中：

n0=n2+1；

N=n0+n1+n2

树中结点数 = 总分叉数 +1

分叉数 = 度 .* 对应个数 = 1*4+2*2+3*1+4*1=15

节点数 = 15+1 = 16

叶节点度数为 0

叶节点数目 x = 16 - （4+2+1+1） = 8

2-12

已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（）。 (3分)

CBEFDA

FEDCBA

CBEDFA

不定

二叉树遍历

2-13

已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历是（）。 (3分)

acbed

decab

deabc

cedba

数据结构 复习笔记 数组和广义表以及树的基本概念

2-1

数据结构复习笔记数组和广义表以及树的基本概念