数据结构老师给的复习要点(严蔚敏版)

数据结构⽼师给的复习要点（严蔚敏版）第⼀章1. 怎样理解“算法+数据结构=程序”这个公式？举例说明。

算法是语句序列解决特定问题的固有程序⽚段。

数据结构是确定数据间的关系。

从具体问题抽象出⼀个合适的数学模型、然后设计⼀个解决此数学模型的算法，最后编写出程序。

寻求数学模型的是指就是数据结构要完成的⼯作。

参看书p1前两段的描述。

2. 数据结构的概念，它包含哪三⽅⾯的内容？数据结构：是⼀门研究⾮数值计算的程序设计问题中计算机的操作对象以及它们之间饿关系和操作的学科。

参看书p3包含三⽅⾯的内容:1、数据之间的逻辑关系2、数据在计算机中的存储⽅式3、在数据上定义的运算的集合。

3. 数据、数据元素、数据项的基本概念。

举例说明数据元素和数据项的联系与区别。

数据：描述客观事物的数字、字符以及所有能直接输⼊到计算机中并被计算机程序处理的符号的集合。

数据元素：数据的基本单位，在计算机程序中通常作为⼀个整体进⾏考虑或处理。

数据项：数据项是具有独⽴含义的最⼩标识单位，是数据元的⼀个具体值，是数据记录中最基本的、不可分的有名数据单位。

例1：class A{int c[123];int i;};class B{A a;}B b;b.a是数据项，B是数据元素例2：⼀本书的数⽬信息为⼀个数据元素，⽽数⽬信息中每⼀项（如书名、作者名等）为⼀个数据项4. 从逻辑结构来看，数据结构有哪四种基本结构，各⾃的特点是什么？1、集合（数据元素之间同属于⼀个集合，再⽆其他关系）2、线性结构（数据元素之间存在⼀对⼀的关系）3、树形结构（数据元素之间⼀对多的关系）4、图状结构或⽹状结构（数据元素之间多对多的关系）5. 从物理结构来看，数据结构有哪两种基本结构，各⾃的特点是什么？1、顺序存储结构特点：借助元素在存储器中的相应位置来表⽰数据元素之间的逻辑关系。

2、链式存储结构特定：借助元素在存储地址的指针表⽰数据元素之间的逻辑关系。

6. 算法的5个特征，4个评价标准是什么？特征:有穷性、确定性、可⾏性、输⼊、输出。

期末复习复习第一章绪论数据：计算机处理的信息总称数据项：最小单位数据元素：最基本单数据对象：元素集合数据结构：相互之间存在一种或多种特定关系的数据元素集合。

概念：数据元素之间的关系线性结构：一对逻辑结构非线性结构数据结构树：一对多图：多对多顺序存储结构链表存储结构存储结构。

索引。

基。

散列。

础知数据运算识算法描述：指令的有限有序序列有穷性确定性算法特性可行性算法输入输出时间复杂度算法分析空间复杂度、计算机算法必须具备输入、输出、可行性、确定性、有穷性５个特性。

1 2、算法分析的两个主要方面是空间复杂度和时间复杂度。

3、数据元素是数据的基本单位。

4、数据项是数据的最小单位。

5、数据结构是带结构的数据元素的集合。

6、数据的存储结构包括顺序、链接、散列和索引四种基本类型。

线性表复习第二章定义逻辑关系：前趋后继节省空间基本特点随机存取插、删效率低顺序存储结构插入基本运算删除一个数据一个指针多占空特查找费插、删效率无法查找前趋结单链运算特点：单链表+前趋指针域链表存储双向结构链表插入运算删除特点：单链表的尾结点指针循环指向附加头结点。

链表运算：联接1 、一个指向后继结点的指针、在双链表中，每个结点有两个指针域，包括一个指向前驱结点的指针 2、线性表采用顺序存储，必须占用一片连续的存储单元、线性表采用链式存储，便于进行插入和删除操作3 、线性表采用顺序存储和链式存储优缺点比较。

4 5、简单算法复习栈和队列第三章．栈的概念：在一端操作的线性表LIFO栈的特点：先进后出存储结初始化push 进栈运算算法pop出栈队列概念：在两端操作的线性表FIFO队列特点：先进先出假溢出顺序队列front=rear队空：循环队列front=(rear+1)%MAXSIZE队满：队列front∧队空：链队列rear初始化判空顺序：进队基本运算链队：出队取队首元素1栈和队列的异同点。

、、2栈和队列的基本运算出栈和出队、3 、4基本运算复习串第四章．n(≥)个字符组成的有限序列1定义：由”c……cS=”cc n231串长度、空白串、空串。

数据结构期末复习要点第一章绪论1、掌握基本概念和术语，看教材P4—P6部分内容；2、看P10—P11关于类C的语法描述，算法设计写代码时可用到；3、掌握算法的特征（5个）和要求（5个）（P13—P14），能够结合具体算法分析算法的时间复杂度和空间复杂度（比如线性表的插入、删除操作，查找、排序等操作），理解O(n)、O(1)等时间复杂度的具体含义（P14—P17）。

第二章线性表1、看教材P21—P26，掌握有关线性表顺序存储的内容：（1）顺序表的随机存取（P21计算地址的公式）；（2）顺序表的表示（P22的Typedef）；（3）顺序表为空、为满的判定，插入和删除操作的特征以及时间复杂度的分析（P23—P25）；（4）有关顺序表的编程题。

2、看教材P27—P30，掌握有关线性表链式存储的内容：（1）单链表的表示（P28的Typedef）；（2）单链表为空的判定（带头结点、不带头结点）；（3）单链表插入、删除操作的特征（操作点的确定以和指针的修改）以及时间复杂度分析（P29—P30）；（4）有关单链表的编程。

3、为节约时间，循环链表、双向链表以及多项式加法可以不看；4、算法设计题要求写代码，在本章体现的可能性比较大。

第三章栈和队列1、顺序栈的表示，栈操作的特点以及为空、为满的判定（P46—P47）；2、栈的应用举例看个标题就足够了；3、链队列的表示以及入队、出队操作（P61—P62）；4、循环队列为空、为满的判定（P65的代码中）；5、离散事件模拟这节不用看；6、第四章只需要看P70就够了，掌握串的特点（元素受限），串长度、空串、串的位置、串相等几个概念即可。

第六章树和二叉树1、看教材P120，了解有关树的概念和术语；2、了解二叉树的链式存储结构（P127），掌握二叉树的性质（P123—P125），并会做题（参考课件或指导书相关内容）；3、掌握二叉树的各种遍历算法（P128—P129或课件）：（1）能够根据二叉树写出各种遍历序列；（2）能够由两种遍历序列（必须包含中序序列）恢复二叉树；（3）理解二叉树遍历算法的递归代码，能够读懂代码含义。

1、数据(Data) ：是客观事物的符号表示。

在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素(Data Element)：是数据的基本单位，在程序中通常作为一个整体来进行考虑和处理。

一个数据元素可由若干个数据项(Data Item)组成。

数据项是数据的不可分割的最小单位。

数据项是对客观事物某一方面特性的数据描述。

数据对象(Data Object)：是性质相同的数据元素的集合，是数据的一个子集。

如字符集合C={‘A’,’B’,’C,…} 。

数据结构(Data Structure)：是指相互之间具有(存在)一定联系(关系)的数据元素的集合。

元素之间的相互联系(关系)称为逻辑结构。

数据元素之间的逻辑结构有四种基本类型，如图1-3所示。

①集合：结构中的数据元素除了“同属于一个集合”外，没有其它关系。

②线性结构：结构中的数据元素之间存在一对一的关系。

③树型结构：结构中的数据元素之间存在一对多的关系。

④图状结构或网状结构：结构中的数据元素之间存在多对多的关系。

2、顺序结构：数据元素存放的地址是连续的；链式结构：数据元素存放的地址是否连续没有要求。

数据的逻辑结构和物理结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。

在C语言中，用一维数组表示顺序存储结构；用结构体类型表示链式存储结构。

3、C语言中用带指针的结构体类型来描述typedef struct Lnode{ ElemType data; /*数据域，保存结点的值*/struct Lnode *next; /*指针域*/}LNode; /*结点的类型*/4、循环队列为空：front=rear 。

循环队列满：(rear+1)%MAX_QUEUE_SIZE =front。

5、性质1：在非空二叉树中，第i层上至多有2i-1个结点(i≧1)。

性质2：深度为k的二叉树至多有2k-1个结点（k≧1) 。

第5章数组和广义表5.1 复习笔记一、数组的定义1．二维数组类似于线性表，一个二维数组的逻辑结构形式表示为：2-Array＝（D，R）其中D＝{a ij|i＝c1，c1＋1，…，d l，j＝c2，c2＋1，…，d2，a ij∈D0}R＝{ROW，COL}ROW＝{<a ij，a i，j＋1>|c1≤i≤d1，c2≤j≤d2－1，a ij，a i，j＋1∈D}COL＝{<a ij，a i＋1，j>|c1≤i≤d1－1，c2≤j≤d2，a ij，a i＋1，j∈D}D0为某个数据对象，c1，c2，d1，d2均为整数。

【注意】①二维数组中含有（d1－c1＋1）×（d2－c2＋1）个数据元素，每个数据元素a ij都受行关系、列关系约束。

②a i，j＋1是a ij在行关系中的直接后继元素；而a i＋1，j是a ij在列关系中的直接后继元素。

③数组中所有的数据元素属于同一数据类型。

2．n维数组n 维数组的逻辑结构形式定义如下：n-Array ＝（D ，R ）其中 12120,1,,,1,2,,(0),n n i i i i j j j j j j i i j c c d i n n D a a D c d ⎧⎫=+=>⎪⎪=⎨⎬∈⎪⎪⎩⎭且和均为整数12{,},,n R R R R =11111111,1,i n i n i n i n i j j j j k k k j j i i i j j j j j j R a a c j d k n k c j d a a D ++=<>⎧⎫≤≤≤≤≠⎪⎪≤≤-⎨⎬⎪⎪∈⎩⎭ 且【注意】 ①n 维数组含有)1(1+-∏=i i ni c d 个数据元素，每个数据元素都受n 个关系的约束。

②在每个关系中，数据元素12(1)n j j j i i i a c j d ⋯≤≤-都有一个直接后继元素。

二、数组的顺序表示和实现1．二维数组的两种存储方式二维数组的顺序存储结构有两种存储方式：（1）以列序为主序的存储方式，如图5-1（a）所示；（2）以行序为主序的存储方式，如图5-1（b）所示。

1.复杂性分析对各种操作的时间复杂性的分析。

主要是链表，树，排序等简单一些的分析。

分析的时候,从简单的入手,学会方法。

后续的各种豆可能让你分析时间复杂度。

线性链表（顺序表和单链表）链表循环链表双向链表2.线性结构队列（循环队列)栈链表主要操作:找某一个元素，插入一个（在哪个位置增加），删除一个（在哪个位置删除)。

栈：查找，插入（位置固定），删除(位置固定）队列：查找，插入（位置固定)，删除（位置固定）顺序表（可以视为一个数组）单链表：（删除）(插入）倒置：(查找）循环链表双向链表栈：(插入删除查找)队列(插入删除查找）循环队列的实现，并不是像上面的图那样，实现了一个循环的样子。

3.二叉树基本概念二叉树是每个节点最多有两个子树的有序树。

二叉树常被用于实现二叉查找树和二叉堆。

值得注意的是,二叉树不是树的特殊情形。

二叉树是每个结点最多有两个子树的有序树。

通常根的子树被称作“左子树”(left subtree）和“右子树”（right subtree）。

二叉树常被用作二叉查找树和二叉堆或是二叉排序树。

二叉树的每个结点至多只有二棵子树（不存在出度大于2的结点），二叉树的子树有左右之分,次序不能颠倒。

二叉树不是树的一种特殊情形，尽管其与树有许多相似之处，但树和二叉树有两个主要差别：1. 树中结点的最大度数没有限制,而二叉树结点的最大度数为2；2。

树的结点无左、右之分，而二叉树的结点有左、右之分。

二叉树是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：（1）空二叉树——如图（a)；（2)只有一个根结点的二叉树——如图（b);(3）只有左子树——如图（c）；（4)只有右子树-—如图（d）;(5）完全二叉树-—如图（e)注意:尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形性质（1）在非空二叉树中，第i层的结点总数不超过, i〉=1;(2）深度为h的二叉树最多有2^h—1个结点（h>=1），最少有h个结点；（3）对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2,则N0=N2+1；(4）具有n个结点的完全二叉树的深度为(5）有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系: 若I为结点编号则如果I>1,则其父结点的编号为I/2;如果2*I<=N，则其左儿子(即左子树的根结点）的编号为2*I；若2＊I>N,则无左儿子；如果2＊I+1〈=N,则其右儿子的结点编号为2*I+1；若2*I+1〉N，则无右儿子。

数据结构-（严蔚敏C语⾔版）-学习、复习提纲期末复习第⼀章绪论复习1、计算机算法必须具备输⼊、输出、可⾏性、确定性、有穷性５个特性。

2、算法分析的两个主要⽅⾯是空间复杂度和时间复杂度。

3、数据元素是数据的基本单位。

数据结算法数据：计算机处理的信息总称数据项：最⼩单位数据元素：最基本单概念：数据元素之间的关系线性结构：⼀对⼀⾮线性结构树：⼀对多图：多对多顺序存储结构链表存储结构算法描述：指令的有限有有穷性确定性可⾏性时间复杂4、数据项是数据的最⼩单位。

5、数据结构是带结构的数据元素的集合。

6、数据的存储结构包括顺序、链接、散列和索引四种基本类型。

第⼆章线性表复习1、在双链表中，每个结点有两个指针域，包括⼀个指向前驱结点的指针、⼀个指向后继结点的指针2、线性表采⽤顺序存储，必须占⽤⼀⽚连续的存储单元定义节省空间随机存取插⼊3、线性表采⽤链式存储，便于进⾏插⼊和删除操作4、线性表采⽤顺序存储和链式存储优缺点⽐较。

5、简单算法第三章栈和队列复习1、栈和队列的异同点。

2、栈和队列的基本运算 3、出栈和出队 4、基本运算存储结栈的概念：在⼀端操作的线性运算算栈的特点：先进后出初始化进栈顺序队队列概念：在两端操作的线性假溢出链队列队列特点：先进先出基本运顺序：队空：队满：(1)队初始化判空进队第四章串复习第五章数组和⼴义表复习定义：由n(≥1)个字符组成的有限序列紧缩格式⾮紧缩格式以字节为单位的存储基本运(s) 串长度 (s12) 联接 (s12) ⽐较模式匹失败链接值匹配算法单字符链表串串变量的存储映像：串名、串值对应关系表顺序存储压缩存储⾏优先顺序存放列优先顺序存放稀疏矩应⽤表达式⼴义表定义：n(≥0)个元素的有限序表头：(A)= a 1 概念：长度、深度、原⼦、⼦表尾：(A)=(a23,…)表结特殊矩对称矩阵三⾓矩阵三元组存储：三元组原⼦结第六章树复习1、三个结点可以组成2种不同形态的树。

2、⼀个稀疏矩阵*n 采⽤三元组形式表⽰，若完成了其的转置运算要经过哪⼏步:⼆叉树概定义：递归定义，不为空双亲、孩⼦、叶⼦、兄弟、存储⽅顺序：满、完全⼆⼆叉树已知先根、中根序列画树；先根线索线索线索树的画法树、森林与⼆叉树的相互树、森⼆叉排树的应哈夫曼左中哈夫曼树的矩阵的⾏、列数值互换、矩阵元素所在⾏列值互换、元素在矩阵中排列的位置）重新排列3、若⼆叉树中每⼀层结点的个数都达到了最⼤，则称为⼀棵满⼆叉树。

第1章绪论1.1复习笔记一、数据结构的定义数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。

二、基本概念和术语数据数据（data）是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称，它是计算机程序加工的“原料”。

2.数据元素数据元素（data element）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

3.数据对象数据对象（data object）是性质相同的数据元素的集合，是数据的一个子集。

4．数据结构数据结构（data structure）是相互之间存在一种或多种特定关系的数据元素的集合。

（1）数据结构的基本结构根据数据元素之间关系的不同特性，通常有下列四类基本结构：① 集合。

数据元素之间除了“同属于一个集合”的关系外，别无其它关系。

② 线性结构。

数据元素之间存在一个对一个的关系。

③ 树形结构。

数据元素之间存在一个对多个的关系。

④ 图状结构或网状结构。

数据元素之间存在多个对多个的关系。

如图1-1所示为上述四类基本结构的关系图。

图1-1 四类基本结构的关系图（2）数据结构的形式定义数据结构的形式定义为：数据结构是一个二元组Data_Structure==（D，S）其中：D表示数据元素的有限集，S表示D上关系的有限集。

（3）数据结构在计算机中的表示数据结构在计算机中的表示（又称映象）称为数据的物理结构，又称存储结构。

它包括数据元素的表示和关系的表示。

① 元素的表示。

计算机数据元素用一个由若干位组合起来形成的一个位串表示。

② 关系的表示。

计算机中数据元素之间的关系有两种不同的表示方法：顺序映象和非顺序映象。

并由这两种不同的表示方法得到两种不同的存储结构：顺序存储结构和链式存储结构。

a.顺序映象的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。

b.非顺序映象的特点是借助指示元素存储地址的指针（pointer）表示数据元素之间的逻辑关系。

严蔚敏数据结构复习整理完整版数据结构是计算机科学中的重要基础课程，是指数据组织、存储和处理的方式。

严蔚敏教授是中国计算机教育领域的知名专家，他的《数据结构》一书被广泛使用于计算机相关专业的教学中。

下面是严蔚敏数据结构复习整理的完整版，总结了数据结构的基本概念、常见数据结构的特点和使用场景，以及一些重要的算法思想和应用。

一、数据结构的基本概念1.数据：数据是计算机能识别、处理的符号集合，可以是数字、文字、图像等。

2.数据元素：数据中的一个个基本单位，也称为记录。

3.数据项：数据元素中的一个个最小单位，是不可分割的数据单位。

二、常见数据结构1.数组：一组具有相同数据类型的元素的集合，可以通过下标来访问和操作。

2.链表：一组通过指针连接起来的数据元素的集合，可以分为单向链表和双向链表。

3.栈：一种特殊的线性表，只能在表尾进行插入和删除操作，遵循先进后出的原则。

4.队列：一种特殊的线性表，只能在表尾进行插入操作，在表头进行删除操作，遵循先进先出的原则。

5.树：一种非线性的数据结构，具有层次结构的特点，包括二叉树、二叉树、平衡树等。

6.图：一种非线性的数据结构，由顶点和边组成，包括有向图和无向图。

7.堆：一种完全二叉树的结构，用于实现优先队列等需要快速找到最值的场景。

8.哈希表：一种以键值对形式存储数据的数据结构，通过哈希函数将键映射到对应的位置，常用于快速查找场景。

三、常用算法和应用1.线性查找和二分查找：分别用于在无序数组和有序数组中查找指定的元素。

2.冒泡排序和快速排序：分别用于对数组进行升序排序，冒泡排序的时间复杂度较高，快速排序的时间复杂度较低。

3.广度优先和深度优先：分别用于在图中特定的路径，广度优先适用于找最短路径，深度优先适用于找所有路径。

4.迪杰斯特拉算法和贪心算法：迪杰斯特拉算法用于计算图中最短路径，贪心算法用于求解最优问题时，每一步都选择当前最好的选择。

5.动态规划算法：一种分阶段求解的问题求解方法，适用于具有最优子结构的问题，将问题分解为子问题，并逐步求解。

第11章外部排序11.1 复习笔记一、外存信息的存取1．磁带信息的存取磁带上读写一块信息所需的时间为：T I/O＝t a＋n×t w；其中t a为延迟时间，读/写头到达传输信息所在物理块起始位置所需时间；t w为传输一个字符的时间。

2．磁盘信息的存取磁盘是一种直接存取的存储设备，它是一个扁平的圆盘，盘面上有许多称为磁道的圆圈，信息就记载在磁道上。

由于磁道的圆圈为许多同心圆，所以可以直接存取。

在磁盘上读写一块信息所需的时间为：T I/O＝t seek＋t la＋n×t wm；其中：t seek为寻查时间，即读/写头定位（即使磁头移动到所需柱面）的时间；t la为等待时间（等待要访问的信息转到磁头下），即等待信息块的初始位置旋转到读写头下的时间；t wm为传输时间。

二、外部排序的方法1．外部排序的两个独立阶段（1）按可用内存大小，将外存上含n个记录的文件分成若干长度为len的子文件或段，依次读入内存并利用有效的内部排序方法对它们进行排序，并将排序后得到的有序子文件（又称归并段或者顺串）重新写入外存。

（2）对这些归并段或顺串进行逐趟归并，使其逐渐由小至大，直至得到整个有序文件为止。

2．外部排序所需时间一般情况下，外部排序所需总的时间＝m×t IS＋d×t IO＋s×ut mg；其中：m为经过内部排序之后得到的初始归并段的个数，t IS是为得到一个初始归并段进行内部排序所需时间的均值，则m×t IS表示内部排序（产生初始归并段）所需的时间；d为总的读/写次数，t IO是进行一次外存读/写时间的均值，则d×t IO表示外存信息读写的时间；s为归并的趟数，ut mg是对u个记录进行内部归并所需时间，则s×ut mg表示内部归并所需的时间。

3．影响外部排序效率的因素外部排序中，其所需的时间主要取决于对外存的读/写上，而外存的读/写又取决于多路归并所进行的趟数n＝log k m，其中k表示采用k路归并，m为初始归并段的个数，因此提高外部排序的效率可以从两方面入手：增大k值，即采用多路平衡归并的方法；减小m值，即采用置换选择算法。

严蔚敏数据结构（C语⾔版）知识点总结笔记课后答案第1章绪论1.1复习笔记⼀、数据结构的定义数据结构是⼀门研究⾮数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。

⼆、基本概念和术语数据数据（data）是对客观事物的符号表⽰，在计算机科学中是指所有能输⼊到计算机中并被计算机程序处理的符号的总称，它是计算机程序加⼯的“原料”。

2.数据元素数据元素（data element）是数据的基本单位，在计算机程序中通常作为⼀个整体进⾏考虑和处理。

3.数据对象数据对象（data object）是性质相同的数据元素的集合，是数据的⼀个⼦集。

4．数据结构数据结构（data structure）是相互之间存在⼀种或多种特定关系的数据元素的集合。

（1）数据结构的基本结构根据数据元素之间关系的不同特性，通常有下列四类基本结构：①集合。

数据元素之间除了“同属于⼀个集合”的关系外，别⽆其它关系。

②线性结构。

数据元素之间存在⼀个对⼀个的关系。

③树形结构。

数据元素之间存在⼀个对多个的关系。

④图状结构或⽹状结构。

数据元素之间存在多个对多个的关系。

如图1-1所⽰为上述四类基本结构的关系图。

图1-1 四类基本结构的关系图（2）数据结构的形式定义数据结构的形式定义为：数据结构是⼀个⼆元组Data_Structure==（D，S）其中：D表⽰数据元素的有限集，S表⽰D上关系的有限集。

（3）数据结构在计算机中的表⽰数据结构在计算机中的表⽰（⼜称映象）称为数据的物理结构，⼜称存储结构。

它包括数据元素的表⽰和关系的表⽰。

①元素的表⽰。

计算机数据元素⽤⼀个由若⼲位组合起来形成的⼀个位串表⽰。

②关系的表⽰。

计算机中数据元素之间的关系有两种不同的表⽰⽅法：顺序映象和⾮顺序映象。

并由这两种不同的表⽰⽅法得到两种不同的存储结构：顺序存储结构和链式存储结构。

a.顺序映象的特点是借助元素在存储器中的相对位置来表⽰数据元素之间的逻辑关系。

第一章绪论一、选择题1.组成数据的基本单位是（）（A）数据项（B）数据类型（C）数据元素（D）数据变量2.数据结构是研究数据的（）以及它们之间的相互关系。

（A）理想结构，物理结构（B）理想结构，抽象结构（C）物理结构，逻辑结构（D）抽象结构，逻辑结构3.在数据结构中，从逻辑上可以把数据结构分成（）（A）动态结构和静态结构（B）紧凑结构和非紧凑结构（C）线性结构和非线性结构（D）内部结构和外部结构4.数据结构是一门研究非数值计算的程序设计问题中计算机的（①）以及它们之间的（②）和运算等的学科。

① （A）数据元素（B）计算方法（C）逻辑存储（D）数据映像② （A）结构（B）关系（C）运算（D）算法5.算法分析的目的是（）。

（A）找出数据结构的合理性（B）研究算法中的输入和输出的关系（C）分析算法的效率以求改进（D）分析算法的易懂性和文档性6.计算机算法指的是（①）,它必须具备输入、输出和（②）等5个特性。

① （A）计算方法（B）排序方法（C）解决问题的有限运算序列（D）调度方法② （A）可执行性、可移植性和可扩充性（B）可行性、确定性和有穷性（C）确定性、有穷性和稳定性（D）易读性、稳定性和安全性二、判断题1.数据的机内表示称为数据的存储结构。

（）2.算法就是程序。

（）3.数据元素是数据的最小单位。

（）4.算法的五个特性为：有穷性、输入、输出、完成性和确定性。

（）5.算法的时间复杂度取决于问题的规模和待处理数据的初态。

（）三、填空题1.数据逻辑结构包括、、和四种类型,其中树形结构和图形结构合称为。

2.在线性结构中,第一个结点前驱结点,其余每个结点有且只有个前驱结点；最后一个结点后续结点,其余每个结点有且只有个后续结点。

3.在树形结构中,树根结点没有结点,其余每个结点有且只有个前驱结点；叶子结点没有结点,其余每个结点的后续结点可以。

4.在图形结构中,每个结点的前驱结点数和后续结点数可以。

5.线性结构中元素之间存在关系,树形结构中元素之间存在关系,图形结构中元素之间存在关系。