2015考研计算机冲刺课程讲义-数据结构

2015考研计算机冲刺课程讲义-数据结构内容摘要：

2015考研计算机冲刺课程讲义-数据结构 新东方在线 网络课堂电子教材系列 考研计算机 1 考研 计算机专项精讲课程 讲义 数据结构 主讲： 巩微 欢迎使用新东方在线电子教材 新东方在线 网络课堂电子教材系列 考研计算机 2 目 录 第 1 章 线性表 . 3 点归纳： . 3 题： . 7 第 2 章 栈、队列和数组 . 8 点归纳： . 8 题： . 10 第 3 章 树和二叉树 . 12 点归纳： . 12 第 4 章 图 . 24 点归纳： . 24 第 5 章 查找 . 35 点归纳： . 35 第 6 章 排序 . 41 点归纳： . 41 题： . 45 新东方在线 网络课堂电子教材系列 考研计算机 3 第 1 章 线性表 点归纳： 1、线性表是 具有相同数据类型的 n(n0)个数据元素的有限序列，是最简单、最基本、也是最常用的一种线 性结构。 2、 顺序表上基本运算的实现 （ 1）顺序表具有按数据元素的序号随机存取的特点，时间复杂度为 O(1)。 （ 2）按值 要运算是比较，比较的次数与值 与表长有关，平均比较次数为（ n+1） /2，时间复杂度为 O(n)。 （ 3）插入运算：在第 x，从 移动 n i 1个元素。 等概率情况下，平均移动数据元素的次数： 1111 2)1(11)1(E 说明：在顺序表上做插入操作需移动表中一半的数据元素，时间复杂度为 O(n)。 （ 4）删除运算：删除第 到 移动 元素。 等概率情况下，平均移动数据元素的次数： 111 2 1)(1)(E 说明：顺序表上作删除运算时大约需要移动表中一半的元素，时间复杂度为 O(n)。 【题 1】设线性表有 n 个元素，以下操作中，（ ）在顺序表上实现比链表上实现效率更高。 A输出第 i 个（ 1in）元素的值 B交换第 1 个元素和第 2 个元素的值 C顺序输出这 n 个元素的值 D输出与给定值 x 相等的元素在线性表中的序号 【题 2】 采用顺序存储结构 的线性表的插入算法中，当 n 个空间已满时，可申请再增加分配m 个空间。 若申请失败，则说明系统没有（ ）可分配的存储空间。 A m 个 B m 个连续的 C n+m 个 D n+m 个连续的 3、 单链表上基本运算的实现 新东方在线 网络课堂电子教材系列 考研计算机 4 （ 1）建立带头结点的单链表 头插法 在链表的头部插入结点，建立带头结点的单链表 从一个空表开始，读取数组 成新结点，将读取的数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到结束为止。 采用头插法建表的算法如下： L,a,n) s; i; L=(; 创建头结点 L->i=0;ai; s->-> L->s; 尾插法 在单链 表的尾部插入结点，建立带头结点的单链表 头插入建立单链表简单，但读入的数据元素的顺序与生成的链表中元素的顺序是相反的，若希望次序一致，则用尾插法建立。 该方法是将新结点插入到链表的尾部，为此需加入一个指针 r 用来始终指向当前链表的尾结点。 采用尾插法建表的算法如下： L,a,n) s， *r; i; L=(; 创建头结点 L->r=L； 开始时指向头结点 i=0;ai; r->s; 将 r=s; r-> 终端结点 （ 2） 链表中查找第 i 个元素 新东方在线 网络课堂电子教材系列 考研计算机 5 , i); /在单链表 到返回其指针，否则返回空 * p=L; j=0; p->=& j+; j= =i) p; （ 3）链表的插入运算 设 *入过程如 图 3 s->p-> p->s; 该操作的时间复杂度为 O(1)。 （ 4）链表的删除运算 设 除 *p。 删除过程如图 3 q=L; q->p) q=q-> /找 * q->p->图 1 在 *s p s × 图 2 删除 *p p q × 新东方在线 网络课堂电子教材系列 考研计算机 6 p); 因为找 *(n)，所以该操作的时间复杂度为 O(n)。 【题 3】 在一个长度为 n（ n>1）的带头结点的单链表 h 上，另设有尾指针 r（指向尾结点），执行（ ）操作与链表的长度有关。 4、循环链表： 循环链表的操作实现算法与非循环链表的操作算法基本相同，只是对表尾的判断作了改变，例如，在循环单、双链表 L 中，判断 p 所指的表尾结点的条件是 p->L。 5、双向链表 （ 1）插入： 设 p 指向双向链表中某结点， s 指向待 插入的值为 x 的新结点，将 *s 插入到 *入过程如下图。 操作如下： s->p-> p->s; s->p; p->s; 指针操作的顺序不是唯一的，但也不是任意的，操作 必须要放到操作 的前面完成，否则 *p 的前驱结点的指针就丢掉了。 只要把每条指针操作的涵义搞清楚，就不难理解了。 （ 2）删除： 设 p 指向双向链表中某结点，删除 *p。 操作过程如图。 操作如下： p->p-> p->p->p); 【题 4】 如果对含有 n(n>1)个元素的线性表的运算只有 4 种，即删除第一个元素，删除最后一个元素，在第一个元素前面插入新元素，在最后一个元素的后面插入新元素，最好使用（ ）。 图 3 双向链表中的结点插入 p × × 图 4 双 向链表删除结点， 删除 *p p × × 新东方在线 网络课堂电子教材系列 考研计算机 7。