《数据结构》判断题中的错误表述
第1章 绪论：
-
数据元素是数据的最小单位 ×
(数据元素是数据的基本单位，数据项是数据的最小单位)
-
数据对象就是一组数据元素的集合 ×
(这里未强调数据元素的性质相同)
-
任何数据结构都具备3个基本运算，即插入、删除和查找 ×
(队列的栈等数据结构并不具备查找运算)
-
数据的逻辑结构与各数据元素在计算机中如何存储有关×
(数据的逻辑结构独立于计算机，与数据的存储无关；数据的存储结构依赖于计算机)
-
如果数据元素值发生改变，则数据的逻辑结构也随之改变 ×
-
逻辑结构不相同的数据必须采用不同的存储方法来存储 ×
-
顺序存储方式只能用于存储线性结构 ×
-
算法可以用计算机语言描述，所以算法等同程序 ×
(程序=数据结构+算法)
-
算法A和算法B用于求解同一问题，算法A的最好时间复杂度为O(n)，而算法B的最坏时间复杂度为O(n³)，则算法A好于算法B ×
(通常用两个算法的平均时间复杂度进行时间性能比较)
-
一个算法的空间复杂度为O(1)，表示执行该算法不需要任何临时空间 ×
(一个算法的空间复杂度为O(1)，表示执行该算法所需要的临时空间大小与问题规模无关)
第2章 线性表：
-
在一个含有n(n≥1)个元素的线性表中，所有元素值不能相同 ×
-
顺序表具有随机存取特性，所以查找值为x的元素的时间复杂度为O(1) ×
(查找的时间复杂度为O(n)，修改/读取的时间复杂度为O(1))
-
线性表(含n个元素)的基本运算之一是删除第i个元素，其中i的有效取值范围是0≤i≤n-1 ×
(基本运算中的元素序号i是指逻辑序号，从1开始，这里的有效取值范是1≤i≤n；数组的下标是从0开始的)
-
顺序表采用一维数组存放线性表中的元素，所以顺序表与一维数组是等同的×
(顺序表要求所有元素连续存储，而一维数组不必这样，另外，一维数组只有存、取元素操作，而顺序表可以插入、删除元素，所以两者不能等同)
-
线性表的顺序存储表示属于静态结构，而链式存储表示属于动态结构 ×
(所谓静态结构是采用固定大小的静态分配方式得到的结果，如“ int a[10]语句就是一种静态分配方式。所谓动态结构是采用动态分配方式得到的结果，如”int*p=(int*)malloc(n*sizeof(int));”语句就是一种动态分配方式。对于链式存储结构，通常采用动态分配方式，而对于顺序存储结构，既可以采用静态分配方式，也可以采用动态分配方式，只不过为了简单，顺序存储结构通常采用静态分配方式)
-
在含有n个结点的单链表L中，将p所指结点(非首结点)与其前驱结点交换，时间复杂度为O(1) ×
(时间复杂度为O(n)，需要循环遍历找到其前驱结点，修改其指向下一个结点的指针)
-
在循环单链表中，从表中任一结点出发都可以通过指针前后移动操作遍历整个循环链表 ×
(单链表只能按从前向后一个方向遍历；双链表可以按从前向后、从后向前两个方向遍历)
-
在含有n个结点的循环单链表L中删除p所指结点(非首结点)的前驱结点，时间复杂度为O(1) ×
(时间复杂度为O(n)，需要循环遍历找到其前驱结点，然后修改相应的指向下一个结点的指针)
-
分配给一个单链表所有结点的内存单元地址必须是连续的 ×
(当线性表采用链式存储结构时，各结点之间的地址连续与否都可以)
-
与顺序表相比，在链表中顺序访问所有结点,其算法的效率比较低 ×
(二者都需要从头开始遍历，对应的时间复杂度为O(n)，效率是相同的)
-
从长度为n的顺序表中删除任何一个元素所需要的时间均为O(n) ×
(删除最后一个元素时，时间复杂度为O(1))
-
空的单链表不含有任何结点 ×
(带头结点的单链表为空时仍有一个头结点)
-
在双链表中删除一个结点(非尾结点)，需要修改4个指针域 ×
(删除操作修改2个指针；插入操作修改4个指针)
-
要想在O(1)的时间内访问尾结点，应采用循环单链表存储结构 ×
(应采用循环双链表。循环单链表访问尾结点的时间复杂度为O(n))
-
顺序存储结构的特点是存储密度大且插入、删除运算的效率高 ×
(顺序表进行插入和删除操作，平均情况下需要移动一半的数据元素，效率低)
-
线性表的顺序存储结构
总是优于
链式存储结构 ×
(在存储密度上，顺序存储结构占有优势；在插入、删除操作时，链式存储结构占有优势。二者各有其优缺点，不能一概而论。)
-
由于顺序表需要一整块连续的存储空间，所以存储空间利用率高 ×
(由于顺序表需要一整块连续的较大存储空间，当在存储器中出现比较多的碎片时，这些碎片空间可能得不到应用，所以存储空间利用率低)
-
在双链表中删除一个结点p的前驱结点所花费的时间是
O(n)
×
(时间复杂度为O(1)，使用双链表能够快速的找到某个结点的前驱结点)
第3章 栈和队列：
-
栈底元素是不能删除的元素 ×
(栈底元素可以出栈即删除)
-
顺序栈中元素值的大小是有序的 ×
(顺序栈和链栈表示两种不同的存储结构，”顺序”不代表元素值是有序的)
-
若用data[1…m]表示顺序栈的存储空间，则对栈的进、出栈操作最多只能进行m次 ×
(进、出栈可以无限次进行，前提是进栈前栈不为满，出栈前栈不为空)
-
栈是一种对进栈、出栈操作总次数做了限制的线性表 ×
(栈是一种操作受限的线性表，指的是栈只能在一端进行插入和删除，而进栈、出栈操作可以反复进行)
-
空的顺序栈没有栈顶指针 ×
(空栈指栈中没有元素，但顺序栈一定要有栈顶指针)
-
若用不带头结点的非循环单链表来表示链队，则可以用“队首指针和队尾指针的值相等”作为队空的标志 ×
(应该用“队首指针和队尾指针的值均为NULL”作为队空的标志，因为当链队中只有一个结点时队首指针和队尾指针的值也相等)
-
栈和线性表是两种不同的数据结构，它们的数据元素的逻辑关系也不同 ×
(栈是特殊的线性表)
-
有n个不同的元素通过一个栈，产生的所有出栈序列恰好构成这n个元素的全排列 ×
(如：1,2,3三个元素的全排列为：1,2,3/1,3,2/2,1,3/2,3,1/3,1,2/3,2,1，共3
2
1=6种，但出栈元素不可能为3,1,2)
-
在顺序栈中，将栈底放在数组的任意位置不会影响运算的时间性能 ×
(在顺序栈中，如果将栈底放在数组的两端，其进栈、出栈运算的时间性能都是最好的。如果将栈底放在数组的中间，要么将数组改为循环的(需要保存该栈底的位置)，要么移动元素，其时间性能都不如将栈底放在数组两端)
-
环形队列不存在空间上溢出的问题 ×
(环形队列只是不存在假溢出，它仍然存在上溢出的问题)
-
若用s[1…m]表示顺序栈的存储空间，以s[1]为栈底，变量top指向栈顶元素的前个位置，当栈未满时，将元素e进栈的操作是
to
p
−
−
；
s
[
t
o
p
]
=
e
top–；s[top]=e
t
o
p
−
−
；
s
[
t
o
p
]
=
e
×
(以s[1]为栈底，进栈操作时top应远离栈底方向移动，所以进栈操作为
”s
[
t
o
p
]
=
e
；
t
o
p
+
+
”
“s[top]=e；top++”
”
s
[
t
o
p
]
=
e
；
t
o
p
+
+
”
)
-
对于链队，可以根据队头、队尾指针的值计算队中元素的个数 ×
(应该是环形队列而不是链队)
第4章 串：
-
串中的每个元素只能是字母 ×
(串中的元素可以是字母、数字或其他字符，串的数据对象限定为字符集)
-
空串是只含有空格的串 ×
(有一个或多个空格(空格是特殊字符)组成的串称为空格串，空格串不是空串，其长度为串中空格字符的个数)
-
含有n个字符的串中所有子串的个数为
n(
n
+
1
)
2
+
1
\frac{n(n+1)}{2}+1
2
n
(
n
+
1
)
+
1
×
(只有在n个字符互不相同时命题才成立)
-
如果一个串中所有字符均在另一个串中出现，那么说明前者是后者的子串 ×
(必须要连续出现才能称之为子串)
-
顺序串采用一个字符数组存放串中元素，所以顺序串等于一个字符数组 ×
(两者逻辑结构相似，但在基本操作上有很大区别)
第5章：递归
-
递归算法的执行效率比功能相同的非递归算法的执行
效率高
×
(递归算法的缺点是算法的执行效率较低，无论是耗费的计算时间还是占用的存储空间都比功能等价的非递归算法要多)
-
任何递归都是尾递归 ×
(尾递归是指递归调用是最后一条语句)
-
通常递归的算法简单、易懂、容易编写，而且
执行效率也高
×
(递归算法的执行效率较低，这是它的显著缺点)
第6章：数组和广义表
-
数组只能采用顺序存储结构 ×
(数组最适合采用顺序存储结构，但不是说只能采用顺序存储结构)
-
特殊矩阵是指用途特殊的矩阵 ×
(特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵)
-
对角矩阵的特点是非零元素只出现在矩阵的两条对角线上 ×
(对角矩阵满足所有非零元素都集中在以主对角线为中心的带状区域中)
-
在n(n>3)阶三对角矩阵中，每一行都有3个非零的元素 ×
(第一行和最后一行只有2个非零元素)
-
稀疏矩阵的特点是矩阵中的元素个数较少 ×
(稀疏矩阵的特点是矩阵中非零元素的个数相对矩阵元素的个数来说非常少)
-
在稀疏矩阵的三元组存储结构中，每个元素
仅包含非零元素的元素值
×
(三元组表示形式：(行标，列标，值))
-
稀疏矩阵采用三元组存储时具有随机存取特性，而采用十字链表法存储时不具有随机存取特性 ×
(系数矩阵的这两种存储结构都不具有随机存取特性)
第7章：树与二叉树
-
在一棵树中，处于同一层上的各结点之间都存在兄弟关系 ×
(处于同一层并且有相同双亲的各结点之间是兄弟关系，处于同一层但是有不同双亲的各结点之间互为堂兄弟)
-
n(n＞2)个结点的二叉树中至少有一个度为2的结点 ×
(m叉树允许所有结点的度都小于m)
-
完全二叉树
中的每个结点或者没有孩子或者有两个孩子 ×
(应该是满二叉树)
-
在哈夫曼树中，权值相同的叶子结点都在同一层上 ×
-
在哈夫曼树中，权值较大的叶子结点一般离根结点
较远
×
(权值较大的叶子结点一般离根结点较近 )
-
在一棵有n个结点的树中，其分支数为n ×
(分支数为n-1)
-
如果树中x结点的层次(深度)大于y结点的深度，则x是y的子孙结点 ×
(当结点y到结点x之间存在路径时，x为y的子孙结点)
-
若一棵二叉树中的所有结点值不相同，可以由其先序序列和层序序列唯一构造出该二叉树 ×
(先序+中序 后序+中序 层序+后序可以唯一构造出一棵二叉树)
-
二叉树就是度为2的树 ×
-
将一棵树转换为二叉树后，根结点没有左子树 ×
(通常根结点有左子树而无右子树)
-
在哈夫曼编码中，当两个字符出现的频率相同时其编码也相同 ×
(哈夫曼编码是一种前缀码，即不允许出现两字符编码相同的情况)
第8章：图
-
n个顶点的无向图最多有n(n-1)条边 ×
(最多的情况是：该图为完全图，此时有
Cn
2
=
n
(
n
−
1
)
2
C_n^2=\frac{n(n-1)}{2}
C
n
2
=
2
n
(
n
−
1
)
条边)
-
如果表示图的邻接矩阵是对称矩阵，则该图一定是无向图 ×
(完全有向图的邻接矩阵也是对称矩阵)
-
对n个顶点的连通图G来说，如果其中的某个子图有n个顶点、n-1条边，则该子图一定是G的生成树 ×
(这样的子图不一定是连通图，而连通图的生成树一定是连通的)
-
最小生成树是指边数最少的生成树 ×
(一个连通图的最小生成树包含图的所有顶点，并且只含尽可能少的边。图的所有生成树的边数是相同的，其中权值之和最小的生成树为最小生成树)
-
从n个顶点的连通图中选取n-1条权值最小的边即可构成最小生成树 ×
(要求最小生成树中不能有回路)
-
只要带权无向图存在权值相同的边，其最小生成树就不可能是唯一的 ×
(这种说法反过来讲才是对的，即：只要带权无向图中没有权值相同的边，其最小生成树就是唯一的)
-
关键路径是由权值最大的边构成的 ×
(从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径。而对于图中所有的关键路径(关键路径可能不止一条)，它们的长度是相同的)
-
一个AOE网可能有多条关键路径，这些关键路径的长度可以不相同 ×
-
求单源最短路径的Dijkstra算法不适用于有回路的带权有向图 ×
(不适用于带负权值以及带负权回路的图)
-
连通分量是无向图中的极小连通子图 ×
(连通分量是无向图的极大连通子图，强连通分量是有向图的极大连通分量；生成树是有向图的极小连通分量)
-
在一个有向图的拓扑序列中若顶点a在顶点b之前，则图中必有一条边くa,b> ×
(表示a到b有路径或边，但不一定是直接相连的)
-
对于有向图G，如果从任一顶点出发进行一次深度优先或广度优先遍历能访问到每个顶点，则该图一定是完全图 ×
(有向图构成一个环时，也满足条件，此时表示完全图)
-
广度优先遍历方法仅仅适合无向图的遍历而不适合有向图的遍历 ×
(两种图都适合)
-
在表示某工程的AOE网中，加速其关键路径上的任意关键活动均可缩短整个工程的完成时间 ×
(一个AOE网中可能存在多条关键路径，只有缩短所有关键路径上共有的关键活动才有可能缩短整个过程的完成时间)
-
在AOE图中，所有关键路径上共有的某个活动的时间缩短C天，整个工程的时间必定缩短C天 ×
(不一定，当C取值不当时，AOE中的关键路径可能发生改变)
-
当一个AOE网中所有活动的时间都不相同时，其关键路径是唯一的 ×
(这样的AOE网的关键路径不一定唯一)
第9章：查找
-
顺序查找方法只能在顺序存储结构上进行 ×
(顺序查找方法既可以在顺序存储结构上进行，也可以在链式存储结构上进行)
-
二分查找适合在有序表的双链表上进行 ×
(二叉查找适合具有随机查找的存储结构上进行，即适合在顺序存储的有序表上进行)
-
二叉排序树是用来排序的 ×
(二叉排序树主要用于改进一般二叉树的查找效率)
-
每个结点的关键字都比左孩子关键字大，比右孩子关键字小，这样的二叉树一定是二叉排序树 ×
(对于二叉排序树，左子树上所有记录的关键字均小于根记录的关键字；右子树上的所有记录的关键字均大于根记录的关键字，而不仅仅是左、右孩子的关键字进行比较)
-
在二叉排序树中，新插入的关键字总是处于最底层 ×
(在二叉排序树中，新结点总是作为树叶来插入的，但不一定处于最底层)
-
在平衡二叉树排序中，每个结点的平衡因子值都是相等的 ×
(AVL中平衡因子的取值范围【-1，1】，只要在合理的取值范围内，可以允许不相等)
-
哈希冲突是指同一个关键字的记录对应多个不同的哈希地址 ×
(哈希冲突是指多个不同关键字的记录对应相同的哈希函数值)
-
在用线性探测法处理冲突的哈希表中，哈希函数相同的关键字总是放在一片连续的存储单元中 ×
-
用顺序表和单链表存储的有序表均适合采用二分查找方法来提高查找速度 ×
(链表存储的有序表不适合采用二分查找)
-
在二叉排序树上删除一个结点时不必移动其他结点，只要将该结点的双亲结点的相应指针域置空即可 ×
(如果删除的是非叶子结点，则必须调整某些结点，使调整后的二叉树仍为二叉排序树)
-
对二叉排序树的查找都是从根结点开始的，则查找失败一定落在叶子上 ×
(查找失败落在外部结点上)
-
若哈希表的装填因子α<1，则可避免冲突的产生 ×
(冲突/碰撞不可避免，只能说α越小，发生冲突的概率越小)
-
在哈希表中进行查找不需要关键字的比较 ×
第10章：内排序&外排序
-
只有在排序数据的初始状态为反序的情况下，简单选择排序过程中元素的移动次数才会达到最大值 ×
(简单选择排序在初始状态为反序时移动元素的次数会达到最大值，但不仅仅只有这种情况，只要每个元素都不在其最终位置上时都会出现这种情况)
-
只有在排序数据的初始状态为反序的情况下，在堆排序过程中，关键字的比较次数才会达到最大值 ×
(选择排序(简单选择排序、堆排序)中，关键字的比较次数与初始序列无关)
-
选择排序和冒泡排序都属于交换类排序方法，每趟产生的有序区都是全局有序的 ×
(选择排序中的堆排序每趟产生的有序区不一定是全局有序的)
-
快速排序方法在任何情况下均可最快得到排序效果 ×
(快速排序在待排序记录关键字为随机分布时效果最好，基本有序时效果最差)
-
基数排序的设计思想是依照对关键字值的比较来实施的 ×
(基数排序不基于比较与移动进行排序)
-
排序的稳定性是指排序算法中比较的次数保持不变，且算法能够终止 ×
(排序的稳定性是指：排序前及排序后Keyᵢ与Keyⱼ的相对位置保持不变)
-
快速排序的速度是所有排序方法中最快的，且所需的辅助空间也最少 ×
(使用递归算法的快速排序，需要借助栈来保存信息，空间复杂度为
O(
l
o
g
2
n
)
O(log_2^n)
O
(
l
o
g
2
n
)
)
-
对一个堆按二叉树层次进行遍历可以得到一个有序序列 ×
(堆的特点是：根结点的关键字大于(或小于)其左右孩子的关键字，此时不能保证左孩子的关键字一定大于右孩子的关键字)
-
在任何情况下二路归并排序都比直接插入排序快 ×
(二路归并排序最好/最差/平均的时间复杂度均为
O(
n
l
o
g
2
n
)
O(nlog_2^n)
O
(
n
l
o
g
2
n
)
，而直接插入排序最好的时间复杂度为O(n))
-
冒泡排序和快速排序都是基于交换的两种排序方法，前者的最坏时间复杂度为
O(
n
2
)
O(n^2)
O
(
n
2
)
，后者的最坏时间复杂度为
O(
n
l
o
g
2
n
)
O(nlog_2^n)
O
(
n
l
o
g
2
n
)
，所以快速排序在任何情况下都比冒泡排序效率高 ×
(快速排序最好/最差/平均的时间复杂度均为
O(
n
l
o
g
2
n
)
O(nlog_2^n)
O
(
n
l
o
g
2
n
)
，而冒泡排序最好的时间复杂度为O(n))
-
在执行某个排序算法的过程中出现了元素朝着最终排序序列位置的相反方向移动，则该算法是不稳定的 ×
-
希尔排序算法的每一趟都要调用一次或多次直接插入排序算法，所以其效率比直接插入排序算法差 ×
(希尔排序的时间复杂度约为
O(
n
1.3
)
O(n^{1.3})
O
(
n
1.3
)
，直接插入排序平均/最坏情况下的时间复杂度为
O(
n
2
)
O(n^2)
O
(
n
2
)
)
-
如果要从100个元素中选择前10个最小的元素，在二路归并排序和冒泡排序之间选择，应选择二路归并排序 ×
(应该选择冒泡排序，此时仅需要进行10趟排序，二路归并则需要全部排序后才能选择出)
-
快速排序每一趟只能归位无序区中的第一个元素 ×
(快速排序每一趟归位一个基准元素，该基准元素可以是无序区中的任何元素)
-
堆排序需要建立初始堆，所以空间复杂度为O(n) ×
(堆排序的空间复杂度为O(1))
-
一个递增的关键字序列一定构成一个
大根堆
×
(小根堆)
-
n个元素采用二路归并排序算法，总的归并趟数为n
(二路归并的趟数为
⌈l
o
g
2
n
⌉
⌈log_2^n⌉
⌈
l
o
g
2
n
⌉
)
-
基数排序只适用于以数字为关键字的情况，不适用以字符串为关键字的情况 ×