1 / 18 《数据结构》复习题（一）一、判断题 （下列各题，你认为正确的，请在前面的括号内打√，错误的打×。每题 1 分，共 10 分）（）1. 数据的存贮结构是数据的逻辑结构的存贮映象。（）2. 用顺序表来存储线性表时，不需要另外开辟空间来保存数据元素之间的相互关系。（）3. 非线性结构中，至少存在一个元素不止一个直接前趋或不止一个直接后继。（）4. 树的最大特点是层次结构。（）5. 队列的特点是先进先出。（）6. 图的最小生成树是唯一的。（）7. 线性表是广义表的特殊形式。（）8. 后序序列和中序序列能唯一确定一棵二叉树。（）9. 散列表是一种链式存贮结构。（）10. 快速排序并非在任何情况下都比其它排序方法速度快。二、填空题 （每空 2 分，共 20 分）1．数据的存贮结构的四种形式为存贮、存贮、存贮和存贮。2．所有插入和删除都在表的一端进行的线性表称为。3．n 个结点的完全二叉树，其深度h=。4．对于顺序循环队列Q[M]，下标从 0 到 M-1，头尾指针分别为F 和 R，入队时，队尾指针循环加 1 可表示为 R=。5．散列法既是一种查找方法，又是一种方法。6．n 个顶点的有向完全图具有条弧。7．n 个元素的顺序查找的平均查找长度为。三、单选题 （本题的每一备选答案中，只有一个是正确的，请把你认为正确的答案的题号填入题干的括号内，多选不给分，每小题3 分，共 15 分）。1．若进栈序列为1，2，3，4，则不可能得到的出栈序列是（）（1）3,2,1,4 （2）3,2,4,1 （3）4,2,3,1 （4） 2,3,4,1 2．对于下列二叉树，其后序序列为（）（1）ABDECFG （2）DBEAFCG （3）DEBFGCA （4）GFCEBDA 3．对于下列 AOV网，不能出现的拓扑序列为（）（1） 1 2 3 4 5 （2）1 2 4 3 5 （3）2 4 1 3 5 （4）2 1 4 3 5 2 / 18 A B C D E F G 题三2 图1 3 5 4 2 题三、3 图4．深度为 k 的完全二叉树所含叶结点的个数最多为（）（1）2k（2） 2k-1（3） k （4） 2k 5．衡量查找算法效率的主要标准是（）（1） 元素个数（2） 所需的存贮量（3） 平均查找长度（4） 算法难易程度四、应用题 （25 分）1．将下列森林转化为二叉树。（3 分）G F A B D E C 2．对下图：（1）写出其邻接矩阵。（ 2 分）（2）按 Kruskal 算法求其最小生成树；并写出相应的边集数组。（4 分）V 3 V 6 3 V 1 V 4 5 V 2 V 5 10 12 6 11 8 3 / 18 3．...
