下载文档原格式
北京市考研计算机科学与技术复习资料数据结构重要知识点归纳数据结构是计算机科学与技术中的重要知识点，对于考研的学生来说，熟练掌握数据结构的理论和应用是非常关键的。
本文将为大家整理归纳北京市考研计算机科学与技术复习资料中的数据结构重要知识点，希望对考生们的复习提供参考。
本文将分为以下几个部分进行阐述。
一、线性表1.1 顺序表：顺序存储结构、插入和删除操作、顺序表的基本运算。
1.2 链表：链式存储结构、单链表、双链表、循环链表、链表的插入和删除操作、链表的基本运算。
二、树2.1 二叉树：二叉树的定义、二叉树的性质、二叉树的遍历算法（前序、中序、后序）、二叉排序树。
2.2 平衡二叉树：平衡二叉树的定义、平衡二叉树的调整策略、红黑树。
2.3 B树：B树的定义、B树的插入和删除操作、B+树。
三、图3.1 图的存储结构：邻接矩阵、邻接表、十字链表。
3.2 图的遍历算法：深度优先搜索（DFS）、广度优先搜索（BFS）。
3.3 最小生成树：Prim算法、Kruskal算法。
3.4 最短路径：Dijkstra算法、Floyd算法。
四、排序与查找4.1 内部排序：插入排序、选择排序、冒泡排序、希尔排序、快速排序、归并排序、堆排序。
4.2 外部排序：多路归并排序。
4.3 查找算法：二分查找、哈希查找。
五、其他重要知识点5.1 哈夫曼编码：哈夫曼编码的思想、哈夫曼树的构建、编码和译码过程。
5.2 搜索树：二叉搜索树、平衡二叉搜索树、B树。
5.3 线索二叉树：线索二叉树的定义、中序线索二叉树的构建与遍历。
5.4 排序算法的稳定性和时间复杂度分析。
以上是本文对于北京市考研计算机科学与技术复习资料中的数据结构重要知识点的归纳总结。
考生们在复习过程中，可以按照这些知识点有序地进行学习和理解，并通过大量的练习题提高自己的应用能力。
希望考生们能够充分掌握数据结构的理论知识，提高解题能力，在考试中取得好成绩。
祝愿大家顺利通过考研！。
目前刚整理了2009-2015的试题过几天2016的也会上传上去希望对你有帮助。
20091.为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。
该缓冲区的逻辑结构应该是A.栈B.队列C.树D.图2.设栈S和队列Q的初始状态均为空，元素abcdefg依次进入栈S。
若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是bdcfeag，则栈S的容量至少是A．1 B.2 C.3 D.43.给定二叉树图所示。
设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。
若遍历后的结点序列为3，1，7，5，6，2，4，则其遍历方式是A．LRN B.NRL C.RLN D.RNL4.下列二叉排序树中，满足平衡二叉树定义的是5.已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则完全二叉树的结点个数最多是A．39 B.52 C.111 D.1196.将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是I．父子关系II.兄弟关系III.u的父结点与v的父结点是兄弟关系A.只有IIB.I和IIC.I和IIID.I、II和III7.下列关于无向连通图特性的叙述中，正确的是I．所有顶点的度之和为偶数II.边数大于顶点个数减1 III.至少有一个顶点的度为1A.只有IB.只有IIC.I和IID.I和III8.下列叙述中，不符合m阶B树定义要求的是A．根节点最多有m棵子树 B.所有叶结点都在同一层上C．各结点内关键字均升序或降序排列 D.叶结点之间通过指针链接9.已知关键序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后得到的小根堆是A．3，5，12，8，28，20，15，22，19B.3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D.3，12，5，8，28，20，15，22，1910.若数据元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是A ．起泡排序 B.插入排序 C.选择排序 D.二路归并排序41.（10分）带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。
科目名称：数据结构请注意：答案必须写在答题纸上（写在试题上无效）。
请完成：（1）画出图G；（2）画出图G的邻接表表示；（3）根据（2）中画出的邻接表，写出从顶点a出发进行深度优先搜索（DFS）产生的深度优先序列；（4）从顶点a开始，用Prim算法构造图G的一棵最小生成树，并画出生成过程。
（20分）五、下图是一带权有向图，试采用Dijkstra算法求从顶点a到其他各顶点的最短路径，要求给出整个计算过程。
（13分）六、若一棵树中有度数为 1 至m 的各种结点数为n1,n2,…,n m(n m表示度数为m 的结点个数)请推导出该树中共有多少个叶子结点n0的公式。
（10分）七、在堆排序、快速排序和合并排序中：(1)若只从存储空间考虑，则应首先选取哪种排序方法，其次选取工作计划怎么写一、工作计划的概念工作计划是指机关、团体、企事业单位的各级机构,对定时期的工作预先作出安排和打算时所使用的文种。
工作计划是行政活动中使用范围很广的重要公文,也是应用写作的一个重头戏。
二、工作计划的特点(一)严肃性。
工作计划作为机关团体和企事业单位对工作的规划安排,往往会受到高度重视,因此工作计划的严肃性不可或缺。
(二)方向性、指导性。
工作计划往往是对本机关、本单位的发展或者工作的要点指明了方向,具有很强的指导性。
(三)战略性。
工作计划往往是机关单位发展战略的集中体现。
(四)科学性和可行性。
相关机关单位在制订工作计划的时候,往往要经过充分的论证和讨论,这就决定了工作计划先天的科学性和可行性特点。
三、工作计划的分类工作计划的分类多种多样,大致可以按照紧急程度、时间、制订计划的主体和任务的类型四个方面来分。
(一)工作计划按紧急程度可分为正常的、紧急的、非常紧急的工作计划。
(二)工作计划按时间的长短可分为长期工作计划、中期工作计划和短期工作计划,或者是年度工作计划、季度工作计划、月工作计划和周工作计划。
(三)工作计划按制订计划的主体可以分为自己制订的工作计划、上司下达的工作计划或者是同等职位请求协助完成的工作计划。
湖南省考研计算机科学与技术复习资料数据结构常考考点湖南省考研计算机科学与技术复习资料：数据结构常考考点数据结构是计算机科学与技术专业中的一门重要课程，也是考研的重要内容之一。
在湖南省考研计算机科学与技术专业的复习中，数据结构常被问及的考点包括以下几个方面。
一、线性表线性表是数据结构中最基本的一种结构，它包括顺序表和链表。
顺序表是将数据按顺序存放在一段连续的存储空间中，通过下标访问元素；链表则是将数据存放在一系列不连续的存储空间中，通过指针关联各个节点。
在考研中，常见的考点有顺序表和链表的实现、插入、删除、查找等操作的时间复杂度分析，以及静态链表的应用等。
二、栈和队列栈和队列是两种特殊的线性表。
栈是一种后进先出（LIFO）的数据结构，支持的操作包括压栈、弹栈和取栈顶元素等；队列是一种先进先出（FIFO）的数据结构，支持的操作包括入队、出队和取队头元素等。
在考研中，常见的考点有栈的顺序存储实现、链式存储实现以及栈的应用，以及队列的顺序存储实现、链式存储实现以及队列的应用等。
三、树和二叉树树是一种非线性的数据结构，它的节点之间存在一对多的关系。
二叉树是一种特殊的树结构，它的每个节点最多有两个子节点。
在考研中，常见的考点有二叉树的存储结构（顺序存储和链式存储）、遍历算法（前序遍历、中序遍历和后序遍历）以及二叉树的应用等。
四、图图是一种复杂的非线性数据结构，它由节点和边组成。
节点表示图中的实体，边表示节点之间的关系。
图分为有向图和无向图，其中有向图的边是有方向的，无向图的边没有方向。
在考研中，常见的考点有图的存储结构（邻接矩阵和邻接表）、图的遍历算法（深度优先搜索和广度优先搜索）以及最短路径算法（Dijkstra算法和Floyd-Warshall算法）等。
五、查找和排序查找和排序是数据结构中非常重要的内容。
查找是在给定数据集合中寻找指定元素的过程，常见的查找算法有顺序查找、二分查找和哈希查找等；排序是将数据按照一定的规则排列的过程，常见的排序算法有冒泡排序、选择排序、插入排序、快速排序和归并排序等。
第3章栈和队列3.1 考点归纳【考纲指定考点】一、栈和队列的基本概念二、栈和队列的顺序存储结构三、栈和队列的链式存储结构四、栈和队列的应用五、特殊矩阵的压缩存储【题型及考点分析】从历年考研真题来看，本章常以选择题的形式考查，主要的考点分布在判断某个出栈序列的合法性，或是出栈序列的可能性；各种形式的栈以及队列的空和满的判定条件；栈和队列的操作特性。
一、栈和队列的基本概念1．栈的基本概念（1）栈（Stack）：是限制在表的一端进行插入和删除操作的线性表。
又称为后进先出LIFO （Last In First Out）或先进后出FILO（First In Last Out）的线性表。
（2）栈顶（Top）：允许进行插入、删除操作的一端，又称为表尾。
用栈顶指针（top）来指示栈顶元素。
（3）栈底（Bottom）：是固定端，又称为表头。
（4）空栈：当表中没有元素时称为空栈。
设栈S=（a1，a2，…an），则a1称为栈底元素，an为栈顶元素，如图3-1所示。
栈中元素按a1，a2，…an的次序进栈，退栈的第一个元素应为栈顶元素。
即栈的修改是按后进先出的原则进行的。
图3-1 栈的示意图（5）栈的基本运算栈的基本运算包括初始化栈、判断栈是否为空、进栈、出栈、读栈顶元素以及销毁栈。
2．队列的基本概念（1）队列（Queue）：也是运算受限的线性表。
是一种先进先出（First In First Out，简称FIFO）的线性表。
只允许在表的一端进行插入，而在另一端进行删除。
（2）队首（front）：允许进行删除的一端称为队首。
（3）队尾（rear）：允许进行插入的一端称为队尾。
（4）空队列：队列中没有元素时称为空队列。
在空队列中依次加入元素a1，a2，…，an之后，a1是队首元素，an是队尾元素。
显然退出队列的次序也只能是a1，a2，…，an，即队列的修改是依先进先出的原则进行的，如图3-2所示。
图3-2 队列的示意图二、栈和队列的顺序存储结构1．栈的顺序存储结构（1）栈的顺序存储结构的定义栈的顺序存储结构简称为顺序栈，指的是用一组连续的存储单元依次存放自栈底到栈顶的数据元素。
一、单项选择题1. 下列对顺序存储的有序表（长度为n）实现给定操作的算法中平均时间复杂度为O(1)的是（）。
A、查找包含指定值元素的值B、插入包含指定值元素的算法C、删除第i(1≤i≤n)个元素的算法D、获取第i(1≤i≤n)个值的算法2、现有非空双向链表L，其结点结构为，prev是指向直接前驱结点的指针，next是指向直接后继结点的指针。
若要在L中指针p 所指向的结点（非尾结点）之后插入指针s指向的新结点，则在执行了语句序列：“s->next=p->next;p->next=s;”，后，还要执行（）。
A、s->next->prev=p;s->prev=p;B、p->next->prev=s;s->prev=p;C、s->prev=s->next->prev; s->next->prev=s;D、p->next->prev=s->prev;s->next->prev=p;3、若采用三元组表存储结构存储稀疏矩阵M，则除三元组外，下列数据中还需要保存的是（）。
I. M的行数；II.M中包含非零元素的行数；III.M的列数；IV.M中包含非零元素的列数。
A、仅I、IIIB、仅I、IIC、仅III、IVD、I、II、III、IV4、在由6个字符组成的字符集S中，各个字符出现的频次分别为3，4，5，6，8，10，为S构造的哈夫曼树的加权平均长度为（）。
A、2.4B、2.5C、2.67D、2.75注：每个关键字的查找长度为：图片加权平均长度为：(3×3+3×4+3×5+3×6+2×8+2×10)/(3+4+5+6+8+10)=2.5。
如果不考虑权重，会错误计算为(3+3+3+3+2+2)/6≈2.67，从而误选C。
5、已知一棵二叉树的树形如下图所示，若其后序遍历为fdbeca，则其先序列为（）。
5.2 典型题（含历年真题）详解一、单项选择题1．设有向图G＝（V，E），顶点集V＝{V0，V1，V2，V3}，边集E＝{<V0，V1>，<V0，V2>，<V0，V3>，<V1，V3>}，若从顶点V0开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是（）。
[2015年联考真题]A．2B．3C．4D．5【答案】D【解析】根据题意知有向图的结构如图所示。
深度优先遍历的特点是尽可能先对纵深方向进行搜索，所以可能得到的不同遍历序列分别是：①V0→V2→V1→V3；②V0→V2→V3→V1；③V0→V1→V3→V2；④V0→V3→V2→V1；⑤V0→V3→V1→V2。
2．对如下所示的有向图进行拓扑排序，得到的拓扑序列可能是（）。
[2014年联考真题] A．3，1，2，4，5，6B．3，1，2，4，6，5C．3，1，4，2，5，6D．3，1，4，2，6，5【答案】D【解析】拓扑排序方法如下：（1）从有向图中选择一个没有前驱（即入度为0）的顶点并且输出它；（2）从图中删去该顶点，并且删去从该顶点发出的全部有向边；（3）重复上述两步，直到剩余的网中不再存在没有前趋的顶点为止。
对于此有向图进行拓扑排序所有序列为：3，1，4，6，2，5和3，1，4，2，6，5。
所以选D3．设图的邻接矩阵A如下所示，各顶点的度依次是（）。
[2013年联考真题]A．1，2，1，2B．2，2，1，1C．3，4，2，3D．4，4，2，2【答案】C【解析】当图用邻接矩阵存储时，各顶点的度是矩阵中此结点对应的横行和纵列非零元素之和。
4．下列AOE网表示一项包含8个活动的工程。
通过同时加快若干进度可以缩短整个工程的工期。
下列选项中，加快其进度就可以缩短工程工期的是（）。
[2013年联考真题]A．c和eB．d和eC．f和dD．f和h【答案】C【解析】根据AOE网的定义可知，同时缩短几条关键路径上的活动时间，可以缩短整个工期。
云南省考研计算机科学与技术复习资料数据结构重点习题解析数据结构是计算机科学与技术专业的一门核心课程，也是考研复习中非常重要的一部分内容。
本文将为大家解析云南省考研计算机科学与技术复习资料中的数据结构重点习题，以帮助大家更好地理解和掌握相关知识。
一、栈和队列1. 栈的特点是后进先出（LIFO），队列的特点是先进先出（FIFO）。
请写出栈和队列的基本操作，并给出时间复杂度的分析。
解析：栈的基本操作包括压栈(Push)和出栈(Pop)，时间复杂度均为O(1)。
队列的基本操作包括入队(Enqueue)和出队(Dequeue)，时间复杂度均为O(1)。
2. 利用两个栈实现一个队列，实现队列的入队和出队操作。
解析：可以用一个栈作为入队栈，一个栈作为出队栈。
当进行入队操作时，直接将元素压入入队栈。
当进行出队操作时，首先判断出队栈是否为空，如果为空，则将入队栈的所有元素逐个弹出并压入出队栈，然后对出队栈进行出栈操作。
这样实现的队列满足先进先出的原则。
二、链表和树1. 请实现链表的插入操作和删除操作。
解析：链表的插入操作和删除操作是常见的链表操作。
插入操作可以在指定位置插入一个新节点，删除操作可以删除指定位置的节点。
在进行插入和删除操作时，需要注意链表的连接关系，确保链表的完整性。
2. 请实现二叉树的前序遍历、中序遍历和后序遍历。
解析：二叉树的前序遍历按照根左右的顺序访问节点；中序遍历按照左根右的顺序访问节点；后序遍历按照左右根的顺序访问节点。
可以通过递归或非递归的方式实现二叉树的遍历。
三、图1. 请实现图的深度优先搜索（DFS）和广度优先搜索（BFS）。
解析：深度优先搜索按照访问一个节点后立即访问其未访问过的邻居节点的方式遍历图；广度优先搜索按照访问一个节点后先访问其邻居节点，再逐层访问其未访问过的邻居节点的方式遍历图。
可以通过递归或非递归的方式实现图的深度优先搜索和广度优先搜索。
2. 请实现图的最小生成树算法：Prim算法和Kruskal算法。
考研计算机数据结构常考题精讲一、概述数据结构是计算机科学中非常重要的基础知识，它涉及到数据的组织、存储和操作方法。
在考研计算机专业的学习过程中，数据结构也是常考的重点内容。
本文将对考研计算机数据结构中的常考题进行深入解析，帮助考生更好地理解和掌握这一重要知识点。
二、线性结构1. 数组数组是一种线性结构，它是一系列连续的内存单元，用于存储相同类型的数据。
常考题包括数组的创建、访问、插入和删除等操作。
考生需要掌握数组的基本概念和操作方法，并理解数组的内存分配方式。
2. 链表链表也是一种线性结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。
常考题包括链表的创建、插入、删除和逆序等操作。
考生需要了解链表的结构特点和基本操作，掌握链表的插入和删除方法。
三、树形结构1. 二叉树二叉树是一种特殊的树形结构，每个节点最多有两个子节点。
常考题包括二叉树的遍历方法，包括前序、中序和后序遍历。
考生需要熟悉二叉树的遍历算法，并能够灵活运用。
2. 平衡二叉树平衡二叉树是一种特殊的二叉树，它的左右子树高度差不超过1。
常考题包括平衡二叉树的插入和删除操作。
考生需要了解平衡二叉树的构造和调整方法，掌握平衡二叉树的插入和删除算法。
四、图形结构图是一种非线性结构，它由节点和边组成。
常考题包括图的遍历方法，包括深度优先搜索和广度优先搜索。
考生需要了解图的基本概念和遍历算法，掌握图的深度优先搜索和广度优先搜索方法。
五、查找和排序1. 顺序查找顺序查找是一种简单的查找方法，逐个比较待查找元素和数组中的元素，直到找到或遍历完所有元素。
常考题包括顺序查找的实现和性能分析。
考生需要了解顺序查找的基本思想和性能特点。
2. 二分查找二分查找是一种高效的查找方法，要求待查找的数组必须是有序的。
常考题包括二分查找的实现和性能分析。
考生需要了解二分查找的基本思想和性能特点，掌握二分查找的实现算法。
3. 快速排序快速排序是一种常用的排序算法，它基于分治的思想，通过将数组分为较小和较大的两个子数组，递归地排序子数组。
第6章查找6.1 考点归纳【考纲指定考点】一、查找的基本概念二、顺序查找法三、分块查找法四、折半查找法五、B树及其基本操、B＋树的基本概念六、散列表七、字符串模式匹配算法八、查找算法分析及应用【题型及考点分析】本章是数据结构考试中的重点章节，一般会考一到两个选择题，在近五年中，有三年的综合题考涉及到本章知识点。
选择题中一般考察各个查找算法的基本概念，以及计算特性。
比如各个算法查找成功与查找失败的平均长度计算。
在综合题中比较容易考察我们对算法的理解，比如哈希表的构造，冲突处理方法等。
对于本章所涉及的查找算法，需要深入理解各个算法思想以及特性，能计算ASL。
本章的难点是B树与B＋树。
对于B＋树只用了解概念即可。
Ｂ树需要掌握插入，删除、查找过程。
字符串匹配，要着重掌握KMP匹配算法。
一、查找的基本概念1．查找查找是指在数据集合中，通过一定的方法找出与给定关键字相同的数据元素的过程。
如果在数据集中找到所指定的元素则称查找成功，反之，则称查找不成功。
2．关键字关键字是指数据元素中某个数据项的值，用它可以标志一个数据元素。
当数据元素只有一个数据项时，其关键字即为该数据元素的值。
3．查找表查找表是指由同一类型的数据元素构成的集合。
一般情况下，我们可以对查找表进行四种操作：查询特定的数据是否在表中；检索摸个特定元素的各种属性；在查找表中插入数据；从查找表中删除数据元素。
4．静态查找表静态查找表是指如果只在查找表中进行查找特定元素与检索数据属性操作，则该查找表就被称为静态查找表。
5．动态查找表动态查找表是指若在查找过程中同时向查找表中插入不存在的数据元素或者从查找表中删除某个已存在的数据元素，则称此查找表为动态查找表。
6．平均查找长度平均查找长度（ASL）是指在查找过程中，一次查找长度指的是查找关键字过程中的比较次数。
平均查找长度指查找过程中进行关键字比较次数的平均值。
二、顺序查找法1．顺序查找概念顺序查找，又称为线性查找，其基本思想是从表的一端开始扫描，顺序扫描线性表，依次扫描到的结点关键字与给定值K相比较。
第1章绪论
1.1考点归纳
【考纲指定考点】
本章初步了解数据结构的基本概念。
分析算法的时间复杂度和空间复杂度是本章的重点。
一、数据结构的基本概念
1．基础概念和术语
（1）数据（Data）：数据是客观事物的符号表示。
在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。
（2）数据元素（Data Element）：数据元素是数据的基本单位，在程序中通常作为一个整体来进行考虑和处理。
（3）数据项（Data Item）：数据项是数据的不可分割的最小单位，数据项是对客观事物的某一方面的数据描述。
一个数据元素可由若干个数据项（Data Item）组成。
（4）数据对象（Data Object）：数据对象是性质相同的数据元素的集合，是数据的一个子集。
如字符集合C＝{‘A’，‘B’，‘C’，…}。
（5）数据结构（Data Structure）：数据结构是指相互之间存在一定联系（关系）的数据元素的集合。
元素之间的相互联系（关系）称为逻辑结构。
2．数据结构的形式定义
数据结构的形式定义是一个二元组：
Data Structure＝（D，S）
其中D是数据元素的有限集，S是D上关系的有限集。
数据元素之间的关系可以是元素之间本身代表的某种自然关系，也可以是为了处理问题方便而人为定义的关系，这种自然或人为定义的关系称为数据元素之间的逻辑关系，相应的结构称为逻辑结构。
3．数据结构的组成
数据结构的三个组成部分：
（1）逻辑结构
数据元素之间的逻辑关系的描述。
数据元素之间的逻辑结构有四种基本类型：
①集合：结构中的数据除了“同属于一个集合”外，没有其它关系。
②线性结构：结构中的数据元素之间存在一对一的关系。
③树形结构：结构中的数据元素之间存在一对多的关系。
④图形结构或网状结构：结构中的数据元素之间存在多对多的关系。
（2）存储结构
数据结构在计算机中的实际表达方式，它包括对数据元素的表示和对关系的表示。
存储结构主要有：顺序存储、链式存储、索引存储和散列存储。
①顺序存储结构：用数据元素在存储器中的相对位置来表示数据元素之间的逻辑结构。
数据元素存放的地址是连续的。
其优点是可以实现随机存取，存储空间小；缺点是只能使用相邻的一整块存储单元，容易产生碎片。
②链式存储结构：在每一个数据元素中增加一个存放另一个元素地址的指针，用该指针
来表示数据元素之间的逻辑结构。
对数据元素存放的地址是否连续没有要求。
其优点是能充分利用所有存储单元；缺点是每个结点都需要额外的存储空间，且只能实现顺序存取。
③索引存储结构：在存储元素信息的同时，还建立附加的索引表。
索引表中的每一项称为索引项，索引项的一般形式是：（关键字.地址），关键字唯一标识一个元素，地址作为指向元素的指针。
其优点是检索速度快；缺点是需要额外的存储空间来存放索引表。
④散列（或哈希）存储结构：根据元素的关键字通过哈希函数直接计算出该元素的存储地址。
其优点是检索速度快，缺点是可能存在冲突，而解决冲突会增加时空开销。
（3）数据操作
数据操作指对数据要进行的运算。
【例】下列有关数据存储结构的叙述中，正确的是（）。
A．顺序存储方式只能用于存储线性结构
B．顺序存储方式的优点是占用存储空间小，插入、删除等操作效率高
C．链表的每个结点中都恰好含有一个指针
D．Hash存储的基本思想是由关键词的值决定数据的存储地址
【答案】D
【解析】顺序存储方式除了用于存储线性结构外，还能存储数组或完全二叉树等非线性结构，但在插入、删除操作时，由于要移动大量的数据，执行效率低。
链表的形式有单链表、双链表和多重链表，除了单链表外，其他链表中的结点需要两个以上的指针。
二、抽象数据类型
1．数据类型
数据类型（Data Type）是一个值的集合和定义在该集合上的一组操作的总称。
2．抽象数据类型
抽象数据类型（ADT）是指一个数学模型以及定义在该数据模型上的一组操作。
ADT的定义仅是一组逻辑特性的描述，与其在计算机内的表示和实现无关。
因此，不论ADT内部结构如何变化，只要其数学特性不变，都不影响其外部使用。
ADT的形式化定义是三元组：ADT＝{D，S，P}。
其中：D是数据对象，S是D上的关系集，P是对D的基本操作集。
三、算法分析
1．算法
（1）概念
算法（Algorithm）是对特定问题求解方法（步骤）的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。
（2）特性
算法有五个特性：
①有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。
②确定性：算法中每一条指令必须有确切的含义，不存在二义性，且算法只有一个入口和出口。
③可行性：算法描述的操作都可以通过已经实现的基本运算执行有限次来实现。
④输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。
⑤输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。
（3）评价标准
评价一个好的算法有以下几个标准：
①正确性：算法应满足具体问题的需求。
②可读性：算法应容易供人阅读和交流。
可读性好的算法有助于对算法的理解和修改。
③健壮性：算法应具有容错处理。
当输入非法或错误数据时，算法能适当地做出反应或进行处理。
④通用性：算法应具有一般性，处理结果对于一般数据集合都成立。
⑤效率和存储量需求：效率指的是算法执行的时间；存储量需求指的是执行过程中所需要的最大存储空间。
2．效率的度量
（1）时间复杂度
算法中的基本操作重复执行的次数是问题规模n的某个函数，其时间度量记做T（n）＝O（f（n））（其中“O”是指T（n）的数量级），称作算法的渐进时间复杂度，简称时间复杂度。
算法的时间复杂度一般用最深层循环内的语句中的原操作的执行频度（重复执行的次数）来表示。
常用的时间复杂度的关系：O（1）＜O（log2n）＜O（n）＜O（n log2n）＜O（n2）＜O（n3）
指数时间复杂度关系为：O（2n）＜O（n!）＜O（n n）
有的情况下，算法中基本操作重复执行的次数会随问题的输入数据集的不同而不同
（2）空间复杂度
空间复杂度指的是算法编写成程序后，在计算机中运行时所需存储空间大小的度量。
记
做：S（n）＝O（f（n）），其中n为问题的规模。
空间复杂度一般包括三个方面：
①指令常数变量所占用的存储空间。
②输入数据所占用的存储空间。
③辅助存储空间。
【例】有以下算法，其时间复杂度为（）。
A．O（1）
B．O（log2n）
C．O（n）
D．O（nlog2n）
【答案】B。
【解析】基本运算语句为d＝d/2（或f＝f*f），设其执行时间为T（n），则有：d＝n/2T(n)＞0≥1，2T(n)≤n
则T（n）≤log2n＝O（log2n）。
注意算法中while循环的if条件中包含的p＝p*f语句可以不考虑，因为它执行的次数不超过d＝d/2语句的执行次数。
