数据结构 数组和广义表以及树的基本概念
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