山农大《数据结构复习题-高起本》期末考试复习题及参考答案.pdf

谋事在人，成事在天！——《增广贤文》 《数据结构》复习题 一、填空题 1、数据的物理结构主要包括_____________和______________两种情况。 2、设一棵完全二叉树中有 500 个结点，则该二叉树的深度为__________；若用二叉链表作 为该完全二叉树的存储结构，则共有___________个空指针域。 3、设输入序列为 1、2、3，则经过栈的作用后可以得到___________种不同的输出序列。 4、设有向图 G 用邻接矩阵 A[n][n]作为存储结构，则该邻接矩阵中第 i 行上所有元素之和等 于顶点 i 的________，第 i 列上所有元素之和等于顶点 i 的________。 5、设哈夫曼树中共有n 个结点，则该哈夫曼树中有________个度数为 1 的结点。 6.设有向图 G 中有n 个顶点 e 条有向边，所有的顶点入度数之和为 d，则 e 和 d 的关系为 _________。 7、__________遍历二叉排序树中的结点可以得到一个递增的关键字序列（填先序、中序或 后序）。 8、不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为 ____________。 9、设有 n 个无序的记录关键字，则直接插入排序的时间复杂度为________，快速排序的平 均时间复杂度为_________。 10．设指针变量p 指向双向循环链表中的结点 X，则删除结点X 需要执行的语句序列为 _________________________________________________________ （设结点中的两个指针 域分别为 llink 和 rlink）。 11．根据初始关键字序列(19，22，01，38，10)建立的二叉排序树的高度为____________。 12．深度为k 的完全二叉树中最少有____________个结点。 13．设初始记录关键字序列为 (K1，K2，…，Kn)，则用筛选法思想建堆必须从第______个元 素开始进行筛选。 14．设哈夫曼树中共有 99 个结点，则该树中有_________个叶子结点；若采用二叉链表作为 存储结构，则该树中有_____个空指针域。 15．设有一个顺序循环队列中有 M 个存储单元，则该循环队列中最多能够存储________个队 列元素；当前实际存储________________个队列元素 （设头指针 F 指向当前队头元素的前 一个位置，尾指针指向当前队尾元素的位置）。 宠辱不惊，看庭前花开花落；去留无意，望天上云卷云舒。——《洪应明》 老当益壮，宁移白首之心；穷且益坚，不坠青云之志。——唐·王勃 二、选择题 1、下面关于NP 问题说法正确的是（ ） A NP 问题都是不可能解决的问题 B P 类问题包含在 NP 类问题中 C NP 完全问题是 P 类问题的子集 D NP 类问题包含在 P 类问题中 2、蒙特卡罗算法是（ ）的一种。 A、分支界限算法 B、概率算法 C、贪心算法 D、回溯算法 3.下列哪一种算法不是随机化算法（ ） A. 蒙特卡罗算法 B. 拉斯维加斯算法 C.动态规划算法 D.舍伍德算法 4. （ ）是贪心算法与动态规划算法的共同点。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、最优子结构性质 5. 矩阵连乘问题的算法可由（ ）设计实现。 A、分支界限算法 B、动态规划算法 C、贪心算法 D、回溯算法 6. 分支限界法解旅行售货员问题时，活结点表的组织形式是（ ）。 A、最小堆 B、最大堆 C、栈 D、数组 7.Strassen 矩阵乘法是利用（