(完整word版)数据结构期末复习题0001

1、数据结构期末复习题 、选择题 1. 以下说法中不正确的是（ D）。 A. 数据元素是数据的基本单位 B. 数据项是不可分割的最小可标识单位 C. 数据可由若干个数据元素构成 D. 数据项可由若干个数据元素构成 2. 计算机所处理的数据一般具备某种内在联系，这是指（ B）。 A. 数据和数据之间存在某种关系 B. 元素和元素之间存在某种关系 C. 元素内部具有某种结构 D. 数据项和数据项之间存在某种关系 3. 在数据结构中，与所使用的计算机无关的是数据的（ A）结构。 A. 逻辑 B. 存储 C. 逻辑和存储 D. 物理 4. 数据的逻辑结构可以分为（C）两类。 A. 动态结构和静态结构 B.

2、 紧凑结构和非紧凑结构 C. 线性结构和非线性结构 D. 内部结构和外部结构 5. 数据的逻辑结构是指（A）关系的整体。 A. 数据元素之间逻辑 B. 数据项之间逻辑 C. 数据类型之间 D. 存储结构之间 6. 以下数据结构中（D）属非线性结构。 A. 栈 B. 串 C. 队列 D. 平衡二叉树 7. 以下属于逻辑结构的是（ C）。 A. 顺序表 B. 哈希表 C. 有序表 D. 单链表 8. 以下不属于存储结构的是（ A）。 A. 栈 B. 线索二叉树 C. 哈希表 D. 双链表 9. 在计算机中存储数据时，通常不仅要存储个数据元素的值，而且还要存储（C） A. 数据的处理方法 B. 数据

3、元素的类型 C.数据元素之间的关系 D.数据的存储方法 10. 数据结构在计算机内存中的表示是指（ A）。 A. 数据的存储结构 B. 数据结构 C. 数据的逻辑结构 D. 数据元素之间的关系 11. 在数据的存储结构中，一个结点通常存储一个（B） A. 数据项 B. 数据元素 C. 数据结构 D. 数据类型 12. 在决定选择何种类型的存储结构时，一般不多考虑（A） A. 各结点的值如何 B. 结点个数的多少 C. 对数据有哪些运算 D. 所用编程语言实现这种结构是否方便 13. 计算机中算法指的是解决某一问题的有限运算序列， 它必须具备输入、 输出、 (B)。 A. 可行性、可移植性和可扩

4、充性 B. 可行性、有穷性和正确性 C. 正确性、有穷性和稳定性D. 易读性、稳定性和正确性 14. 以下关于算法的说法正确的是( D)。 A. 算法最终必须由计算机程序实现 B. 算法等同于程序 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 15. 算法的时间复杂度与(A)有关。 A. 问题规模 B. 计算机硬件性能 C. 编译程序质量 D. 程序设计语言 16. 算法的主要任务之一是分析( D)。 A. 算法是否具有较好的可读性 B. 算法中是否存在语法错误 C.算法的功能是否符合设计要求D.算法的执行时间和问题规模之间的关系 17. 某算法的时间复杂度为0(n2)，表

5、明该算法的(B) A. 问题规模是 n2 B. 执行时间等于 n2 C.执行时间与n2成正比D.问题规模与n2成正比 18. 算法分析的目的是( C)。 A. 找出数据结构的合理性 B. 研究算法中输入和输出的关系 C.分析算法的效率以求改进D.分析算法的易读性和文档性 19. 以下函数中时间复杂度最小的是( D)。 A.n log 2n+5000n B.n2-8000n C.n log 2n-6000n D.20000 log 2n 20. 以下函数中时间复杂度最小的是( A)。 A.1000g2n B.n g 2n-1000g2n C.n2-1000 g 2n D.2n g 2n-1000

6、g 2n 二、判断题 1. 线性表中每个元素都有一个前趋元素和一个后继元素。(X) 2. 线性表中所有元素的排列顺序必须有小到大或由大到小。 (X) 3. 静态链表既有顺序存储的优点， 又有动态链表的优点， 所以， 利用它存取表中 第 i 个元素的时间与元素个数 n 无关。 (X) 4. 静态链表与动态链表在元素的插入、 删除方面类似，不需做元素的移动。(V) 5. 线性表的顺序存储结构优于链式存储结构。 (X) 6. 在循环单链表中， 从表中任一结点出发都可以通过前后移动操作遍历整个循环 链表。 (X) 7. 在单链表中，可以从头结点开始查找任何一个结点。(V) 8. 在双链表中，可以从任一

7、结点开始沿同一方向查找到任何其他结点。 （X） 9. 顺序存储结构只能用于存放线性表。 （X） 10. 线性表的逻辑结构总与其物理顺序一致。 （X） 11顺序表具有随机存取特性。（V） 12. 单链表不具有随机存储特性，而双链表具有随机存取特性。 （X） 13. 顺序栈中元素值的大小是有序的。 （X） 14. 在 n 个元素进栈后，它们的出栈顺序和进栈顺序一定正好相反。 （X） 15. 栈是一种对进栈、出栈操作的次序做了限制的线性表。 （X） 16. 队列是一种对进栈、出栈操作的次序做了限制的线性表。 （X） 17. n 个元素进队列的顺序和出队列的顺序总是一致的。（V） 18. 顺序队列中有

8、多少元素，可以根据队首指针和队尾指针的值来计算。 （V） 19. 串长度为串中不同字符的个数。 （X） 20. 空串就是有空格构成的串。 （X） 三、填空题 1. 线索二叉树中左线索指向其（）结点，右线索指向其（）结点。 前趋；后继 2. 有 n 个顶点的无向图最多有（）条边，而有向图最多有（）条弧。 n（n-1）/2 ； n（n-1） 3. 图的邻接矩阵和邻接表存储结构中， 邻接（）是唯一的， 邻接（）是不唯一的。 矩阵；表 4. 用邻接矩阵存储一个不带权有向图 G其第i行的所有元素之和等于顶点i的 （），而第 i 列的所有元素之和等于顶点 i 的（）。 出度；入度 5. 对 n 个顶点的连

9、通图来说，它的生成树一定有（）条边，它是该图的一个（） 连通分量。 n-1 ；极小 6. Prim 算法特别适合求（）图的最小生成树， Kruskal 特别适合求（）图的最小 生成树。 稠密；稀疏 7. 一个线性表采用折半查找时，该线性表必须具有的特点是顺序存储且（）；而 分块查找法要求将待查找表均匀地分成若个块且块中诸记录的顺序可以是任意 的，但块与块之间（）。 有序；有序 8. 高度为 8 的平衡二叉树的结点数最少有（）个，最多有（）个。 54；255 9. 堆排序是一种（）排序方法，堆实质上是一棵（）二叉树。 选择；完全 10. 对含有 n 个元素的数据序列进行冒泡排序， 其中关键字比较

10、最多的次数是 （）， 关键字比较最少的次数是（）。 n(n-1)/2 ； n-1 1. 重要知识点：构造二叉树 A A C B FEG DB FEG o A A A C B E DG DGB ECF G A A A C B C E DGB ECF G 图(b)图(c) DGBAECF后序遍历序列为GDBEFCA写出构造二叉树的过程。 由后序序列知A为根结点，由中序序列知DGB为左子树而ECF为右子 DGB E B EC 图(a) 3中序遍历序列为 答 树，如图(a)所示。 其次由后序序列确定左右子树的根结点为 B和C,由中序序列知DG为B的 左孩子，B无右孩子，E为C的左孩子，F为C的右孩子，

11、如图(b)所示。 由后序序列确定B的左子树的根结点为D,由中序序列知G为D的右孩子 D无左孩子，这样就得到最终恢复的二叉树如图(c)所示。 B C E F G 图(c) 图图(b) 前序遍历序列为ABDGCEF中序遍历序列为DGBAECF写出构造二叉树的过 2. 程 答：由前序序列知A为根结点，由中序序列知DGB为左子树而ECF为右子 树，如图(a)所示。 其次由前序序列确定左右子树的根结点为 B和C,由中序序列知DG为B的 左孩子，B无右孩子，E为C的左孩子，F为C的右孩子，如图(b)所示。 由前序序列确定B的左子树的根结点为D,由中序序列知G为D的右孩子 D无左孩子，这样就得到最终恢复的二

12、叉树如图(c)所示。 图 (c)所示。 1.前序遍历序列为ABDCEFG中序遍历序列为DBAFEGC写出构造二叉树的过 程。 答：由前序序列知A为根结点，由中序序列知DB为左子树而FEGC为右子 树，如图(a)所示。 其次由前序序列确定左右子树的根结点为 B和C,由中序序列知D为B的左 孩子，B无右孩子，FEG为C的左子树，C无右子树，如图(b)所示。 由前序序列确定C的左子树的根结点为E,由中序序列知F为E的左孩子 而G为E的右孩子，这样就得到最终恢复的二叉树如图 图(b)图(c) 2. 重要知识点：给定树构造与其对应的二叉树 1.给定下树，写出与其对应二叉树的转化过程。 A B C D E

13、 C B D G G E F H I J K 图 2 A B C E D G F G A A B B E C E D C D G F F G G G A C B D 对于图2: (1)连兄弟: 图1 解：对于图1: 连兄弟: 断孩子: 顺时针旋转45度: 断孩子: 顺时针旋转45度: 3.重要知识点：给定森林构造与其对应的二叉树 1.给定下森林，写出该森林与其对应二叉树的转化过程。 图8 解：（1）连兄弟: 断孩子: 1请构造出下面有向图的邻接表和逆邻接表 解：邻接表: 顶点序号data next I 2 3 4 6 1 5 | A 1 4 11 ! 5 into next 巧 巧 A % 6

14、 A 6 A daU next adjivex info next 逆邻接表: 顶点序号 1 2 3 4 5 6 5. 重要知识点：图的深度优先搜索遍历 1.从顶点v1和v4开始进行深度优先遍历，写出顶点访问序列和深度优先生成 树。 解：深度优先搜索遍历序列(分别从 V1和V4开始)分别如下: V1V2 V4V3 V5 V6V7V8 V4 V2 V1 V3 V5 V6V7V8 相应的深度优先生成树如图所示： 从力深度优先生成树 (b)从叫深度优先主成材 6. 重要知识点：Prim算法 1.从顶点V1开始用普利姆算法得到最小生成树。 V7 3 解：使用Prim算法求得的最小生成树的过程如下图所示

15、 （门五条边 fh）七条边 7. 重要知识点：二叉检索树 要建立一颗平衡的二 1.对于一组记录其关键字序列为（18,5,10,15,12,11,20）, 叉检索树，请给出构造过程。 解：构造平衡二叉检索树的过程如下图所示： 8.重要知识点：哈希检索 1.给定关键字序列(19,14,23,1,68,20,84,27,55,11,10,79，设哈希表长为13,哈 希函数为h(k)=k%13试画出用线性探查法消解地址冲突时所构造的哈希表。 解: 地址 0 1 2 3 4 5 6 7 8 9 10 11 12 关键字 14 1 68 27 55 19 20 84 79 23 11 10 9.重要知识点

16、：快速排序 1给定排序码序列为(17,8,21,35,32,150,25,12,23，写出快速排序结果的过程。 解：快速排序过程如下：17,8,21,35,32,151,25,12,23 第一趟结束，结果为： 12,8,21,35,32,15,25,17,23 12.8.17.35.32.1521.25.21.23 12.8.15.35.32.1721.25.21.23 12,8,15,17,32,35,25,21,23 12,8,15,17,32,3521,25,21,23 10.重要知识点：堆排序 17,8,21,35,32,15,25,12,23， 1给定排序码序列为 构建的完全二叉树 17 35 21 32 15 21 23 8 25 12 i=5时不用调整 i=4时将8筛下一层 用堆排序法进行排序，写 接着将8再筛下一层 时不用调整 将17筛下一