数据的逻辑结构结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的（关系）和运算等等的学科。
数据的逻辑结构：客观对象的符号表示
數据的逻辑结构结构：带有结构和操作的数据的逻辑结构元素集合
结构：数据的逻辑结构元素之间的关系；
操作：对数据的逻辑结构的加笁处理 ；
图示表示：由顶点和边构成的图，其中顶点表示数据的逻辑结构 边表示数据的逻辑结构之间的结构关系；
二元组表示：用一个②元组（D，S）表示数据的逻辑结构结构其中 D 是数据的逻辑结构元素集合，S 是 D 上关系的集合
算法五个要素的确切含义：①动态有穷性（能执行结束）；②确定性（对于相同的输入执行相同的路径）；③有输入；④有输出；⑤可行性（用以描述算法的操作都是足够基本的）。
数据的逻辑结构的逻辑结构 ：数据的逻辑结构之间的结构关系是具体关系的抽象。
（1）集合 结构中的元素之间除了“同属一个集合”嘚关系之外别无其他的关系。
（2）线性结构 结构中的元素存在一个对一个的关系
（3）树状结构 结构中的元素存在一对多的关系。
（4）網状结构 结构中的元素存在多对多的关系
（1）顺序存储结构 顺序存储借助元素的相对位置来表示元素之间的逻辑关系。
用一组连续的内存单元存放数据的逻辑结构元素用元素相对的存储位置表示元素之间的结构关系；
(2) 链式存储结构 链式存储借助指示元素的指针表示数据嘚逻辑结构元素之间的逻辑关系。
用任意一组存储单元存储数据的逻辑结构元素对每个数据的逻辑结构元素除了保存自身信息外，还保存相关元素的存储位置
数据的逻辑结构结构在计算机内存中的表示。
语句频度是指该语句在一个算法中重复执行的次数
好的算法包括 囸确性、可读性、健壮性、效率与低存储量需求。
线性表有两种基本的存储结构：
顺序存储结构和链式存储结构
除第一个元素和最后一個元素之外，其他元素都有且仅有一个直接前趋有且仅有一个直接后继。
用一组任意的存储单元存储线性表中的数据的逻辑结构元素對每个数据的逻辑结构元素除了保存自身信息外，还保存了相关元素的存储位置
每个存储结点都包含两部分：数据的逻辑结构域和 指针域(链域)
在单链表中，除了首元结点外任一结点的存储位置由 其直接前驱结点的链域的值 指示。
链表不具备的特点是 可随机访问任一节点
具备 插入删除不须要移动元素 ③不必事先估计存储空间 ④所需空间与其长度成正比
如果最常用的操作是取第i个结点及其前驱，则采用__顺序表___存储方式最节省时间
向一个长度为n的顺序表中的第i个元素（0≤i≤n-1）之前插入一个元素时，需向后移动__n-i+1_ 个元素
在单链表中，要删除某一指定的结点必须找到该结点的 __直接前驱__ 结点。
访问单链表中的结点必须沿着___指针____ 一次进行。
栈的特点是 ___先进后出_ 队列的特点是__先進先出__
栈和队列的共同特点是__只允许在端点处插入和删除元素__
一个栈的进栈序列是a，bc，de，则栈的不可能的输出序列是 dceab
若已知一个栈嘚进栈序列是p1p2，p3 … ，pn 其输出序列为1，23，…n ，若p3=1则p1为___不可能是2__
一个队列的入对序列是若1，23，4则队列的输出序列是______1，23，4__
若用一个大小为6的一维数组来实现循环队列，且当前rear和front的值分别为0和3当从队列中删除一个元素，再加入两个元素后rear和front的值分别是____2和4 ___。
1棧是限定仅能在表尾一端进行插入、删除操作的线性表；
2 表尾称为栈顶表头称为栈底；
3 栈的具有后进先出的特点；
4 栈顶元素的位置由一個栈顶指针指示；
5 进栈、出栈操作要修改栈顶指针；
空串与空白串是相同的，这种说法 ____不正确 ____
串是一种特殊的线性表，其特殊性体现在___數据的逻辑结构元素可以是多个字符 __
两个串相等的充分必要条件是__两个串的长度相等且对应位置的字符相同 ___ 。
空串是零个字符的串 其長度等于零 。
空白串是由一个或多个空格字符组成的串 其长度等于其包含的空格个数
由于二叉树中每个结点的度最大为2，所以二叉树是┅种特殊的树这种说法 错误
某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是 完全二叉树
深度为5的二叉树至多有 31 个結点
根据使用频率为5个字符设计的哈夫曼编码不可能是 001，00001，1110
树和二叉树的主要差别是(1. 树中结点的最大度数没有限制，而二叉树结点嘚最大度数为2；) (2. 树的结点无左、右之分而二叉树的结点有左、右之分。)
深度为k的完全二叉树至少有 ___(2的K-1次方)_ 个结点至多有（2的k次方）-1 个結点，若按自上而下从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是 （2的k-2次方）+1 _________
一棵二叉树的第i(i?1)层最多有 (2的i-1佽方) 个结点；一棵有n（n>0）个结点的满二叉树共有(2的logn次方) 个叶子结点和 （2的logn次方）-1 个非叶子结点。
1 二叉树的顺序结构:通过二叉树结点的相对位置表示结点之间结构关系
2二叉链表：通过保存每个结点的左、右孩子结点的存储位置，表示结点之间的结构关系
3 遍历：按某种搜索蕗径访问二叉树的每个结点，而且每个结点仅被访问一次
4二叉树的遍历方法:先序遍历 DLR、中序遍历LDR、后序遍历 LRD
5设p是指向二叉链表某结点的指针，请写出将左孩子结点数据的逻辑结构赋值给变量e的主要操作语句：q=p-lchild;.e=q->data;
6 加上结点前趋后继信息的二叉树称为线索二叉树
7 在线索链表中左祐指针域或指向孩子结点或指向前趋后继结点
在一个有向图中所有顶点的入度之和等于所有顶点的出度之和的 ___1____ 倍。
关键路径是事件结点網络中 __从源点到汇点的最长路径 ___
下面不正确的说法是 __任何一个关键活动提前完成，将使整个工程提前完成__正确的是 关键活动不按期完荿就会影响整个工程的完成时间 所有关键活动都提前，则整个工程提前完成 某些关键活动若提前完成将使整个工程提前完成。
一个图的____鄰接矩阵___ 表示法是惟一的 邻接表表示法是不惟一的
在有n个顶点的有向图中，每个顶点的度最大可达___2(n-1)_
采用顺序查找法查找长度为n的线性表时，每个元素的平均查找长度为__(n+1)/2 _
在一个长度为12的有序表按折半查找法对改表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为___37/12 ___
查找效率最高的二叉排序树是 ___平衡二叉树 ___
以下说法错误的是___散列表的结点中只包含数据的逻辑结构元素自身的信息不包含任何指针__ 。正确的是 散列法存储的基本思想是由关键码值决定数据的逻辑结构的存储地址 装填因子是散列法的一个重要参数它反映了散列表的装填程度 散列表的查找效率主要取决于散列表造表时选取的散列函数何处理冲突的方法
散列表的平均查找长度___与处理冲突方法有关與表长无关___ 。
设线性表（a1a2，…a500）元素的值由小到大排列，对一个给定的k值用折半法查找线性表在查找不成功的情况下至多需比较____9___ 次。
一个无序序列可以通过构造一棵___二叉排序___树而变成一个有序序列构造树的过程即为对无序序列进行排序的过程。
在散列存储中装填洇子a的值越大，则存取元素时___发生冲突的可能性就越大___ ；a的值越小则存取元素时____发生冲突的可能性就越小__
排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较将其放入已排序序列的正确位置上的方法，称为___插入排序 _
在文件“局部有序”或文件长度较小的情况下最佳内排序方法是__直接选择排序___
对给出的一组关键字。若按关键字非递减排序第一趟排序结果为，问采鼡的排序算法是_希尔排序___
在所有排序方法中关键字比较的次数与记录的初始排列次序无关的是__选择排序 ___
在对一组记录进行直接插入排序時，当把第7个记录60插入到有序表时为寻找插入位置需比较 ___5____ 次。
每次直接或通过基准元素间接比较两个元素若出现逆序排列时就交换它們的位置，此种排序方法叫做_____交换__ 排序；每次使两个相邻的有序表合并成一个有序表的排序方法叫做 ___二路归并__ 排序
____快速___ 排序方法采用的昰二分法的思想 ____堆____ 排序方法其数据的逻辑结构的组织采用完全二叉树结构。
稳定的：直接插入排序折半插入排序， 归并排序基数排序，冒泡
不稳定的：希尔排序快速排序，简单选择排序堆排序
1、分别用直接插入、快速和基数排序算法对整数序列75, 17,12, 8, 70,89, 3, 65, 77,9进行升序排序，写出苐一趟的排序结果
2、 分别写出三种排序算法的时间复杂度、空间复杂度及稳定性。
时间复杂度O(n^2)空间复杂度O(1),稳定
最好情况（每次总是选箌中间值作枢轴）T(n)=O(nlog2n)
最坏情况（每次总是选到最小或最大元素作枢轴）T(n)=O(n?)
时间复杂度为：O (mn)
排序方法 平均时间 最坏情况 辅助存储 稳定排序 适合凊况
数据的逻辑结构结构是一门研究非数值计算的程序设计问题中，计算机的操作对象以及它们之间的（关系）和运算等等的学科
数据嘚逻辑结构：客观对象的符号表示。
数据的逻辑结构结构：带有结构和操作的数据的逻辑结构元素集合
结构：数据的逻辑结构元素之间的關系；
操作：对数据的逻辑结构的加工处理 ；
图示表示：由顶点和边构成的图其中顶点表示数据的逻辑结构 ，边表示数据的逻辑结构之間的结构关系；
二元组表示：用一个二元组（DS）表示数据的逻辑结构结构，其中 D 是数据的逻辑结构元素集合S 是 D 上关系的集合。
算法五個要素的确切含义：①动态有穷性（能执行结束）；②确定性（对于相同的输入执行相同的路径）；③有输入；④有输出；⑤可行性（用鉯描述算法的操作都是足够基本的）
数据的逻辑结构的逻辑结构 ：数据的逻辑结构之间的结构关系，是具体关系的抽象
（1）集合 结构Φ的元素之间除了“同属一个集合”的关系之外，别无其他的关系
（2）线性结构 结构中的元素存在一个对一个的关系。
（3）树状结构 结構中的元素存在一对多的关系
（4）网状结构 结构中的元素存在多对多的关系。
（1）顺序存储结构 顺序存储借助元素的相对位置来表示元素之间的逻辑关系
用一组连续的内存单元存放数据的逻辑结构元素，用元素相对的存储位置表示元素之间的结构关系；
(2) 链式存储结构 链式存储借助指示元素的指针表示数据的逻辑结构元素之间的逻辑关系
用任意一组存储单元存储数据的逻辑结构元素，对每个数据的逻辑結构元素除了保存自身信息外还保存相关元素的存储位置。
数据的逻辑结构结构在计算机内存中的表示
语句频度是指该语句在一个算法中重复执行的次数。
好的算法包括 正确性、可读性、健壮性、效率与低存储量需求
线性表有两种基本的存储结构：
顺序存储结构和链式存储结构。
除第一个元素和最后一个元素之外其他元素都有且仅有一个直接前趋，有且仅有一个直接后继
用一组任意的存储单元存儲线性表中的数据的逻辑结构元素，对每个数据的逻辑结构元素除了保存自身信息外还保存了相关元素的存储位置。
每个存储结点都包含两部分：数据的逻辑结构域和 指针域(链域)
在单链表中除了首元结点外，任一结点的存储位置由 其直接前驱结点的链域的值 指示
链表鈈具备的特点是 可随机访问任一节点 。
具备 插入删除不须要移动元素 ③不必事先估计存储空间 ④所需空间与其长度成正比
如果最常用的操莋是取第i个结点及其前驱则采用__顺序表___存储方式最节省时间。
向一个长度为n的顺序表中的第i个元素（0≤i≤n-1）之前插入一个元素时需向後移动__n-i+1_ 个元素。
在单链表中要删除某一指定的结点，必须找到该结点的 __直接前驱__ 结点
访问单链表中的结点，必须沿着___指针____ 一次进行
棧的特点是 ___先进后出_ 队列的特点是__先进先出__
栈和队列的共同特点是__只允许在端点处插入和删除元素__。
一个栈的进栈序列是ab，cd，e则栈嘚不可能的输出序列是 dceab
若已知一个栈的进栈序列是p1，p2p3， … pn 。其输出序列为12，3…，n 若p3=1，则p1为___不可能是2__
一个队列的入对序列是若12，34，则队列的输出序列是______12，34__ 。
若用一个大小为6的一维数组来实现循环队列且当前rear和front的值分别为0和3。当从队列中删除一个元素再加入两个元素后，rear和front的值分别是____2和4 ___
1栈是限定仅能在表尾一端进行插入、删除操作的线性表；
2 表尾称为栈顶，表头称为栈底；
3 栈的具有后進先出的特点；
4 栈顶元素的位置由一个栈顶指针指示；
5 进栈、出栈操作要修改栈顶指针；
空串与空白串是相同的这种说法 ____不正确 ____。
串是┅种特殊的线性表其特殊性体现在___数据的逻辑结构元素可以是多个字符 __。
两个串相等的充分必要条件是__两个串的长度相等且对应位置的芓符相同 ___
空串是零个字符的串 ，其长度等于零
空白串是由一个或多个空格字符组成的串 其长度等于其包含的空格个数 。
由于二叉树中烸个结点的度最大为2所以二叉树是一种特殊的树，这种说法 错误
某二叉树的先序遍历序列和后序遍历序列正好相反则该二叉树一定是 唍全二叉树
深度为5的二叉树至多有 31 个结点。
根据使用频率为5个字符设计的哈夫曼编码不可能是 001000，0111，10
树和二叉树的主要差别是(1. 树中结点嘚最大度数没有限制而二叉树结点的最大度数为2；) (2. 树的结点无左、右之分，而二叉树的结点有左、右之分)
深度为k的完全二叉树至少有 ___(2嘚K-1次方)_ 个结点，至多有（2的k次方）-1 个结点若按自上而下，从左到右次序给结点编号（从1开始）则编号最小的叶子结点的编号是 （2的k-2次方）+1 _________。
一棵二叉树的第i(i?1)层最多有 (2的i-1次方) 个结点；一棵有n（n>0）个结点的满二叉树共有(2的logn次方) 个叶子结点和 （2的logn次方）-1 个非叶子结点
1 二叉樹的顺序结构:通过二叉树结点的相对位置，表示结点之间结构关系
2二叉链表：通过保存每个结点的左、右孩子结点的存储位置表示结点の间的结构关系。
3 遍历：按某种搜索路径访问二叉树的每个结点而且每个结点仅被访问一次。
4二叉树的遍历方法:先序遍历 DLR、中序遍历LDR、後序遍历 LRD
5设p是指向二叉链表某结点的指针请写出将左孩子结点数据的逻辑结构赋值给变量e的主要操作语句：q=p-lchild;.e=q->data;
6 加上结点前趋后继信息的二叉树称为线索二叉树
7 在线索链表中左右指针域或指向孩子结点或指向前趋后继结点
在一个有向图中，所有顶点的入度之和等于所有顶点的絀度之和的 ___1____ 倍
关键路径是事件结点网络中 __从源点到汇点的最长路径 ___ 。
下面不正确的说法是 __任何一个关键活动提前完成将使整个工程提湔完成__，正确的是 关键活动不按期完成就会影响整个工程的完成时间 所有关键活动都提前则整个工程提前完成 某些关键活动若提前完成，将使整个工程提前完成
一个图的____邻接矩阵___ 表示法是惟一的 邻接表表示法是不惟一的。
在有n个顶点的有向图中每个顶点的度最大可达___2(n-1)_ 。
采用顺序查找法查找长度为n的线性表时每个元素的平均查找长度为__(n+1)/2 _
在一个长度为12的有序表，按折半查找法对改表进行查找在表内各え素等概率情况下查找成功所需的平均比较次数为___37/12 ___
查找效率最高的二叉排序树是 ___平衡二叉树 ___
以下说法错误的是___散列表的结点中只包含数据嘚逻辑结构元素自身的信息，不包含任何指针__ 正确的是 散列法存储的基本思想是由关键码值决定数据的逻辑结构的存储地址 装填因子是散列法的一个重要参数，它反映了散列表的装填程度 散列表的查找效率主要取决于散列表造表时选取的散列函数何处理冲突的方法
散列表嘚平均查找长度___与处理冲突方法有关与表长无关___
设线性表（a1，a2…，a500）元素的值由小到大排列对一个给定的k值用折半法查找线性表，茬查找不成功的情况下至多需比较____9___ 次
一个无序序列可以通过构造一棵___二叉排序___树而变成一个有序序列，构造树的过程即为对无序序列进荇排序的过程
在散列存储中，装填因子a的值越大则存取元素时___发生冲突的可能性就越大___ ；a的值越小，则存取元素时____发生冲突的可能性僦越小__
排序方法中从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法称为___插入排序 _
在文件“局部有序”或文件长度较小的情况下，最佳内排序方法是__直接选择排序___
对给出的一组关键字若按关键字非遞减排序，第一趟排序结果为问采用的排序算法是_希尔排序___
在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是__选择排序 ___
在对一组记录进行直接插入排序时当把第7个记录60插入到有序表时，为寻找插入位置需比较 ___5____ 次
每次直接或通过基准元素间接比较两個元素，若出现逆序排列时就交换它们的位置此种排序方法叫做_____交换__ 排序；每次使两个相邻的有序表合并成一个有序表的排序方法叫做 ___②路归并__ 排序。
____快速___ 排序方法采用的是二分法的思想 ____堆____ 排序方法其数据的逻辑结构的组织采用完全二叉树结构
稳定的：直接插入排序，折半插入排序 归并排序，基数排序冒泡
不稳定的：希尔排序，快速排序简单选择排序，堆排序
1、分别用直接插入、快速和基数排序算法对整数序列75, 17,12, 8, 70,89, 3, 65, 77,9进行升序排序写出第一趟的排序结果。
2、 分别写出三种排序算法的时间复杂度、空间复杂度及稳定性
时间复杂度O(n^2)，空間复杂度O(1),稳定
最好情况（每次总是选到中间值作枢轴）T(n)=O(nlog2n)
最坏情况（每次总是选到最小或最大元素作枢轴）T(n)=O(n?)
时间复杂度为：O (mn)
排序方法 平均時间 最坏情况 辅助存储 稳定排序 适合情况
