数据结构考试复习题(绝密版)-副本.pdf

乐民之乐者，民亦乐其乐；忧民之忧者，民亦忧其忧。——《孟子》

页眉内容

一、填空题

1、栈和队列的共同点是（只允许在端点处插入和删除元素）。

2、数据的逻辑结构有线性结构和(非线性结构)两大类。

3、在最坏情况下，堆排序需要比较的次数为（O(nlog2n)）

4、一棵有n个结点的满二叉树有（0）个度为1的结点、有（(n-1)/2）个分支（非终端）结

点和（(n+1)/2）个叶子，该满二叉树的深度为（log2n+1）。

5、n(n﹥0)个顶点的无向图最多有（n(n-1)/2）条边，最少有0条边。

6、判定一个栈ST(最多元素为m)为栈满的条件是（top==m0）。

0

7、头结点是指：（指向链表中第一个结点(或为头结点或为首元结点)的指针），称为头结点。

8.指出树和二叉树的三个主要差别

①树的结点个数至少为1，而二叉树的结点个数可以为0；

②树种结点的最大读书没有限制，而二叉树结点的最大度数不能超过2；

③树的结点无左右之分，而二叉树的结点有左右之分。

9.从概念上讲,树与二叉树是两种不同的数据结构,将树转化为二叉树的基本目的是（树可采用二叉树

的存储结构并利用二叉树的已有算法解决树的有关问题。）

10.若结点A有三个兄弟(包括A本身),并且B是A的双亲结点,B的度是(4)

11.若一棵具有n个结点的二叉树采用标准链接存储结构,那么该二叉树所有结点共有（n+1）个空指

针域。

12.已知二叉树的前序序列为ABDEGCFHIJ,中序序列为DBGEAHFIJC,写出后序序列

（DGEBHJIFCA）。

13.已知二叉树的后序序列为FGDBHECA,中序序列为BFDGAEHC,并写出前序序列

（ABDEGCEH）。

14.找出满足下列条件的二叉树答案

1）先序和中序遍历，得到的结点访问顺序一样。(无左子树)

2）后序和中序遍历，得到的结点访问顺序一样。(无右子树)

3）先序和后序遍历，得到的结点访问顺序一样。(仅一个结点的二叉树)

15.一棵含有n个结点的k叉树，可能达到的最大深度和最小深度各是多少？

最大n,最小┕log2n┙+1

16.一棵二叉树有67个结点，这些结点的度要么是0，要么是2。这棵二叉树中度为2的结点有(22)

个。

17.含有100个结点的树有(99)条边。

18.一棵哈夫曼树有19个结点，则其叶子结点的个数是(10)。

19.设一棵二叉树结点的先根序列为ABDECFGH，中根序列为DEBAFCHG，则二叉树中叶子结点是

(EFH)。

20.己知二维数组A[m][n]采用行序为主方式存储,每个元素占k个存储单元,并且第一个元素的存储地

址是LOC(A[0][0]),则A[0][0]的地址是（LOC（A[0][0]）+（n*i+j）*k）。

21.二维数组A[10][20]采用列序为主方式存储,每个元素占一个存储单元,并且A[0][0]的存储地址是

200,则A[6][12]的地址是（332）。

22.有一个10阶对称矩阵A,采用压缩存储方式(以行序为主,且A[0][0]=1),则A[8][5]的地址是（42）。

23.设n行n列的下三角矩阵A已压缩到一维数组S[1..n*(n+1)/2]中,若按行序为主存储,则A[i][j]对应

的S中的存储位置是（i*(i+1)/2+j+1）。

1

乐民之乐者，民亦乐其乐；忧民之忧者，民亦忧其忧。——《孟子》