2012数据结构复习

2012上《数据结构》复习提纲

第1章 绪论

数据结构的研究目的和研究内容；有关术语；算法、算法复杂度的分析和计算方法

例题：

1．下面算法的时间复杂度为O( n )。

int f( unsigned int n ){

if ( n = = 0 || n = = 1 ) return 1;

else returen n *f ( n – 1 ); }

2．一个算法应具备的5个特性为有穷性、确定性、可行性、输入、输出

3．同类问题见第一次作业

第2-3章 线性表，栈和队列

线性表的概念、存储结构、插入与删除操作； 栈和队列的概念，理解栈顶指针、队首、队尾指针的意义和作用，特别是循环队列的头、尾指针的设置。为什么要这样设置。它们基本操作的实现。判空和判满？了解有关应用。

例题：

1．已知指针p所指结点不是尾结点，若在*p之后插入结点*S，则应执行和操作是s- >link =p->link; p->link =s;

2．同类问题：在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p之间插入一个s所指的结点,则执行的语句？（答：q->next=s;

s->next=p）；注意在某个已知结点前插需要执行的语句？

3．注意循环（链）队列的判空和判满的条件？（看书理解！）

4．在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是s->prior=p; s->next=p->next;

p->next->prior=s; p->next=s;

5．设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为p->next=p->next->next。

6. 在一个具有n个结点的有序单链表中插入一个新结点并保持该表有序的时间复杂度是O(n)。

7. 向一个栈顶指针为hs的链栈中插入一个s结点时，应执行s->next=hs;

hs=s;。当利用大小为N 的数组顺序存储一个栈时，假定用top = = N表示栈空，则退栈时，用（top++）语句修改top指针。

8. 在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为front=front->next。

9．对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为 O(1)，在给定值为x的结点后插入一个新结点的时间复杂度为 O(n)。 10．在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为 (rear+l)％n= = front。

11. 队列的插入操作是在队尾进行。

第6章 树和二叉树

树和二叉树的定义、完全二叉树及其性质、存储表示及遍历算法（递归和非递归）、哈夫曼树的概念。

例题：

1．在一棵二叉树中，度为0的结点个数为n0，度为2的结点个数为n2，则n0= n2+1。（完全二叉树性质）例：二叉树上叶结点数等于（双分支结点数加1 ）;对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为2n个，其中 n-1个用于链接孩子结点， n+1个空闲着。

2．用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组中R[1..n]，结点R[i]若有左孩子，其左孩子的编号为结点 R[2i]。（完全二叉树性质5）

对于一棵具有n个结点的二叉树，若一个结点的编号为i(1≤i≤n)，则它的左孩子结点的编号为2i，右孩子结点的编号为2i+1，双亲结点的编号为 i/2（或i/2）。

3．设一棵完全二叉树具有1000个结点，则此完全二叉树有 500__ 个叶子结点，有 499 ___ 个度为2的结点，有 1 个结点只有非空左子树，有 0 个结点只有非空右子树。(课堂例题)

4. 由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为53。（仔细验算一下）

5. 假定一棵二叉树的结点数为18，则它的最小深度为5，最大深度为18。

6. 一棵深度为k的满二叉树的结点总数为 2k-1，一棵深度为k的完全二叉树的结点总数的最小值为2k-1，最大值为2k-1。

7．在一棵二叉排序树中，每个分支结点的左子树上所有的结点的值一定小于该结点的值，右子树上所有结点的值一定大于该结点的值。

8． 设n , m 为一棵二叉树上的两个结点，在中序遍历序列中n在m前的条件是 n在m 左方 。

第7章 图

图的存储及遍历算法，图的有关概念，最短路径,（最小）生成树

例题：

1．由一个具有n个顶点的连通图生成的最小生成树中，具有n-1 条边。

2．在一个具有n个顶点的无向图中，若具有e条边，则所有顶点的度数之和为2e。

3. 若要把n个顶点连接为一个连通图，则至少需要n-1 条边。

4. 对于一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵大小至少为nn。

5. 对于具有n个顶点和e条边的有向图和无向图，在它们对应的邻接表中，所含边结点的个数分别为2e和e。

6.掌握Dijkstra算法求从某顶点到其他各个顶点间的最短路径。

7．在一个图中，所有顶点的度数之和等于所有边数的 2 倍。

8.在一个具有n个顶点的无向完全图中，包含有n(n-1)/2条边，在一个具有n个顶点的有向完全图中，包含有n(n-1)条边。

第9章 查找

掌握二分（折半）查找，二叉排序树的概念及其上的插入和删除有何特点，掌握哈希查找。

例题：

1．从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较（n+1）/2个元素结点。

2． 对于长度为18的顺序存储的有序表，若采用折半查找，则查找第15个元素的比较次数为4。

3. 对于顺序存储的有序表(5,12,20,26,37,42,46,50,64)，若采用折半查找，则查找元素26的比较次数为4。

4. 从具有n个结点的二叉排序树中查找一个元素时，在平均情况下的时间复杂度大致为O(log2n)。

5. 若根据查找表(23,44,36,48,52,73,64,58)建立哈希表，采用h(K)=K%7计算哈希地址，则哈希地址等于3的元素个数2。

6．从有序表(12,18,30,43,56,78,82,95)中分别折半查找43和56元素时，其比较次数分别为1和3。

7．在一棵二叉排序树上按中序遍历得到的结点序列是一个有序序列。

8．假定对长度n=50的有序表进行折半查找，则对应的判定树高度为6，最后一层的结点数为19。

9. 假定对线性表(38,25,74,52,48)进行哈希存储，采用H(K)=K % 7作为哈希函数，采用线性探测法处理冲突，则在建立哈希表的过程中，将会碰到5次存储冲突。

10．理解并掌握二叉排序树的概念，查找、插入和删除操作。

11. 一个线性表为B=（12，23，45，57，20，03，78，31，15，36），设散列表为HT[0..12]，散列函数为H（key）= key % 13并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。

78 15 03 57 45 20 31 23 36 12

查找成功的平均查找长度：ASL SUCC=14/10= 1.4 0 1 2 3 4 5 6 7 8 9 10 11 12

第10章 内部排序

掌握基本排序方法的实现思想。

例题：

1. 假定对元素序列（7, 3, 5, 9, 1, 12, 8, 15）进行快速排序，则进行第一次划分后，得到的左区间中元素的个数为3。

2．每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做（插入）排序.

考试题型：

一.单项选择题（15×2分=30分）

二.算法填空题（5×6分=30分）

1. 构造一个空的顺序表；2. 在顺序线性表L中删除第i个元素；3. 在带头结点的单链表中第i 个位置前插入元素；4. 中序打印（输出）二叉树；5. 将有序序列归并。

三.应用题（5×6分=30分）

1．有向图的强连通分量概念，写出邻接表和逆邻接表；2. 已知邻接表存储的图，画出此图并写出按深度优先遍历该图的结果；3. 已知哈希函数构造哈希表；4. Prim算法构造最小生成树过程；5. Dijkstra算法求图中从某顶点到其他各顶点间的最短路径并写出执行算法过程中各步的状态。

四.算法设计题（2×5分=10分）

1. 二叉树遍历应用；

2. 单链表应用。

以上各例题中的答案并不保证完全正确，希望自己亲自验证。找到并对照书本上的相应内容仔细阅读3遍以上。切实理解和掌握每个知识点的实质，决不可以似是而非，侥幸过关。

祝同学们考出好成绩！