数据结构填空题专项.docx

1. 根据数据元素间关系的不同特性，通常可分为集合、线性 、树形 、图状 四

类基本结构。

2. 算法的 5 个特征包括： 有穷性、确定性 、有效性、输入和输出。

3. 数据结构中的数据元素存在“一对多”的关系称为 树形 结构。

4. 在包含 n 个元素的顺序表中删除一个元素，需要平均移动 (n-1)/2 个元素，其中具体移动的元素个数与 所删除元素索引 有关。

5. 一个长度为 n 的顺序表从 0 开始编号，为了删除位序号为 4 的元素，从前到后依次移动了 15 个元素。则原顺序表的长度为 20 。

6.设顺序存储的线性表从 0 开始编号，长度为 n，要删除第 i（0<=i<=n-1）个元素，

当 i= n-4 时，移动元素的次数为 3。

7. 设有一个长度为 n 的顺序表，要删除第 i(0<=i<=n-1)个元素，需移动元素的个数

为 n-i-1。

8. 采用十字链表表示一个稀疏矩阵，每一个非零元素一般用一个含有 5 个域的结点表示。

9. 设一个 20 阶的对称矩阵 A(其首元素为 A[0][0])，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组 B 中（数组下标从 0 开始），则矩阵中元素 A[8][1]在一维数组 B 中的下标是 37 。

10. 有 n 个顶点的无向完全图具有 n(n-1)/2 条边。

11. 将一个具有 n 个顶点 e 条边的无向图存储在邻接矩阵中，则非零元素的个数是 2e。

12. 一棵完全二叉树共有 30 个结点，则该树的高度是 5。

13. 一棵满二叉树的结点个数为 n，高度为 h，则 n=  2^h  -1。

14. 空 串是任意串的子串，任意串是其自身的子串。

15. 栈的两种最基本的存储方式分别是 顺序存储 和  链式存储 。

16. 哈希法存储的基本思想是根据 哈希函数 来决定存储地址。

17. 假设只有 1 个结点的二叉树的深度为 1，具有 256 个结点的完全二叉树的深度为 9。

18. 具有 20 个顶点的无向图，边的总数最多为  190 条。

19. 有 10 个顶点的连通图用邻接矩阵表示时，该矩阵至少有 9 个非零元素。

20. 若用 n 表示图中顶点数，则有 n(n-1)/2 条边的无向图称为完全图。

21. 对于一个具有 n 个结点的二叉树，当它为一棵 满 二叉树时具有最小高度。

22. 设 n0为哈夫曼树的叶子结点数目，则该哈夫曼树共有 2n0-1 个结点。

23. 对于一个具有 n 个顶点 e 条边的有向图存储在邻接矩阵中，则非零元素的个数是 e。

24. 设只有 1 个结点的二叉树的深度为 1，则深度为 k 的完全二叉树至少有 2k-1 个结点,至多有 2k-1 个结点。

25. 通常对 n 个元素进行冒泡排序要进行 n-1 趟排序；第 i 趟冒泡排序要进行  n-i-1

次元素间的比较。

26. 从 0 开始，自顶向下、自左向右对一棵二叉树进行顺序编号，则编号为 i 的结点，若它存在左、右孩子，则左、右孩子编号分别为____2i+1____、____2i+2____。

27. 一棵有 20 结点的二叉树，其度为 2 的结点数的个数为 8，则该树共有 3 个度为 1

的结点。