《数据结构复习提纲.doc》由会员分享，可在线阅读，更多相关《数据结构复习提纲.doc（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构复习提纲第 1 章（1）数据结构的四种形式；（2）算法的五大特征；（3）算法设计的要求；（4）算法效率度量方法；第 2 章（1）线性的顺序表示（2）线性表的链式表示及其相操作第 3 章（1）栈和队列的定义（2）栈和队列的基本操作；第 4 章（1）二叉树的定义；（2）二叉树的性质；（3）二叉树的遍历方法；（4）二叉树的递归算法；（5）树和二叉树的转换（6）森林和二叉树的转换；（7）hufuman 树的构造第 5 章（1）图的存储结构（2）最小生成树的求解方法（3）关键路径的求解（4）拓扑排序（5）最短路径的求解方法第 6 章（1）二叉排序树的定义（2）二叉排序树的构造方法（3）平衡二叉树
2、的定义及其构造方法（4）B-树的定义及构造方法（5）哈希表的定义及构造方法第 7 章（1）直接排序（2）希尔排序（3）快速排序（4）选择排序试卷类型一、选择题1. 算法的空间复杂度是指（ ） 。A) 算法执行过程中所需要的基本运算次数B) 算法程序中的指令条数C) 算法执行过程中所需要的存储空间D) 执行算法程序所需要的时间2. 数据结构是一门研究非数值计算的程序设计问题中计算机的（ ）以及它们之间的关系和运算等的科学。A)计算过程 B)数据元素C)数据操作 D)逻辑存储结构3. 下面程序段的时间复杂度为（ ） 。for( i = 0; i prior = p-prior; p-prior =
3、 s;s-next = p;3. 一个结点的子树的个数称为该结点的 。4. 对任何一棵二叉树 T，如果其终端结点数为 n0，度为 2 的结点数为 n2，则 n0和 n2 之间具有性质 。5. 树根的层次是 1，则深度为 8 的完全二叉树至少有 个结点，拥有100 个结点的完全二叉树的最大层次数是 。6. 二叉树的先序和中序遍历序列分别是 ABCDEFGH，CBEDFAGH，则后序遍历序列是 。7. 图的遍历算法有 和广度优先搜索遍历算法。8. 有一个有序表为1,3,9,12,32,41,45,62,75,77,82,95,100, 当二分查找值为 82 的数据时 次比较成功。9. 对于关键字序
4、列：12、13、11、18、60、15、7、20、25、100，用筛选法建堆，必须从值为 的关键字开始。三、简答题1. 什么是栈？栈对数据进行入栈和出栈操作的原则是什么？2. 什么是二叉排序树？3. 简述冒泡排序的基本思想。4. 使用 Prim（普里姆）算法构造出下图的一棵最小生成树，请写出该最小生成树产生的每一步。6 2 4 6 3 5 5 5 6 1 2 3 4 5 6 1 5. 根据下图所示的 AOE 网（顶点 v1,v2,v3,v4,v5,v6 表示事件；弧A,B,C,D,E,F,G,H 表示活动） ，请回答以下问题：x z y p s C 2 B 2 A 3 V1 V2 V3 V4
5、V5 V6 3 D 2 G 4 E 3 F 1 H (1) 求出所有事件的最早发生时间与最迟发生时间。(2) 列出所有关键活动。6. 已知下图所示的二叉树是由某森林转换而来，请画出其原来的森林A B C D E F K H J G 7. 从空树开始，(1) 画 出 按 以 下 次 序 向 3 阶 B-树 中 插 入 关 键 码 后 建 立 的 树 （ 不 用 写 建 树 的 过 程 ，只 写 最 终 建 立 的 树 ） 。 依 次 插 入 的 关 键 字 是 ： 20， 30， 50， 52， 60， 68， 70。(2) 画出基于第（1）步建立的 3 阶 B-树，删除关键字 50 之后的 B
6、-树。(3) 画 出 基 于 第 （ 2） 步 执 行 之 后 产 生 的 B-树 ， 删 除 关 键 字 68 之 后 的 B-树 。8. 设记录的关键字（key）集合是：K = 15,25,26,4,5,20,3,12,2(1) 设 Hash 表表长 m = 16，选取 Hash 函数的方法为“除留余数法” ，其函数形式为 H(key) = key MOD 15，处理冲突的方法为“线性探测再散列” ，请依次取K 中各值，构造出满足所给条件的 Hash 表，画出该哈希表的存储结构图；(2) 写出基于集合 K 中的关键字，采用快速排序法对其进行升序排序时第一趟之后的结果。四、算法设计题1. 已
7、知一个如下图所示的不带头结点的单链表 head（注：若头指针名是 head，则把单链表称为表 head） ，其存储结构为：typedef struct LNodeElemType data;struct LNode *next;LNode, *LinkList; a2 a1 a3 head an NUL 编写在该单链表中删除具有重复值的多余结点，最终使表中的每个结点的值均不同的函数 void Delete(LinkList struct BTreeNode *left;struct BTreeNode *right;请写一个递归算法计算二叉树的深度，算法对应的函数定义为 int BTreeDepth (BTreeNode *BT)