数据结构复习提纲(共5页).doc

《数据结构复习提纲(共5页).doc》由会员分享，可在线阅读，更多相关《数据结构复习提纲(共5页).doc（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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 n; i+)for( j = 0; j prior = p-p

3、rior; p-prior = 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（普里姆）算法构造出下图的一棵最小生成树，请写出该最小生成树产生的每一步。5. 根据下图所示的AOE网（顶点v1,v2,v3,v4,v5,v6表示事件；弧A,B,C,D,E,F,G,H表示活动），请回答以下问题：(1) 求出所有事件的最早发生时间与最迟发生时间。(2) 列出所有关键活动。6. 已知下图所示的二叉树是由某森林转换而来，请画出其原来的森林7.

5、 从空树开始，(1) 画出按以下次序向3阶B-树中插入关键码后建立的树（不用写建树的过程，只写最终建立的树）。依次插入的关键字是：20，30，50，52，60，68，70。(2) 画出基于第（1）步建立的3阶B-树，删除关键字50之后的B-树。(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中各值，构造出

6、满足所给条件的Hash表，画出该哈希表的存储结构图；(2) 写出基于集合K中的关键字，采用快速排序法对其进行升序排序时第一趟之后的结果。四、 算法设计题1. 已知一个如下图所示的不带头结点的单链表head（注：若头指针名是head，则把单链表称为表head），其存储结构为：typedef struct LNode ElemType data; struct LNode *next;LNode, *LinkList;编写在该单链表中删除具有重复值的多余结点，最终使表中的每个结点的值均不同的函数void Delete(LinkList &head)。2. 二叉树采用二叉链表作为存储结构，链表中结点的结构为：struct BTreeNodeElemType data;struct BTreeNode *left;struct BTreeNode *right;请写一个递归算法计算二叉树的深度，算法对应的函数定义为int BTreeDepth (BTreeNode *BT)专心-专注-专业