数据结构判断题.doc

习题一三判断题。1. 数据元素是数据的最小单位。（错误）2. 数据的逻辑结构是指数据的各数据项之间的逻辑关系。（错误）3. 算法的优劣与算法描述语言无关，但与所用计算机有关。（错误）4. 程序一定是算法。（错误）5. 数据的物理结构是指数据在计算机内的实际存储形式。（正确）6. 数据的抽象操作的定义与具体实现有关。（错误）7. 数据的逻辑结构表达了数据元素之间的关系，它依赖于计算机的存储结构。（正确）习题二三判断题。1. 链表中的头结点仅起到标识作用。（错误）2. 顺序存储的线性表可以按序号随机存取。（正确）3. 线性表采用链表存储时，存储空间可以是不连续的。（正确）4. 静态链表中地址相邻的元素具有前驱后继的关系。（错误）5. 对任何数据结构，链式存储结构一定优于顺序存储结构。（错误）6. 在线性表的顺序存储结构中，逻辑上相邻的两个元素在无力位置上不一定紧邻。（错误）7. 循环链表可以在尾部设置头指针。（正确）8. 为了方便插入和删除，可以使用双向链表存放数据。（正确）9. 在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。（错误）10. 取顺序表的第i个元素的时间与i的大小有关。（错误）习题三1. 消除递归一定要使用桟。（错误）2. 桟是实现过程和函数调用所必须的结构。（正确）3. 两个桟共享一片连续内存空间时，为提高内存利用率、减少溢出机会，应把两个桟的栈底分别设在这片内存空间的两端。（正确）4. 用递归方法设计的算法效率高。（错误）5. 栈与队列是一种特殊的线性表。（正确）6. 队列逻辑上是一端既能增加又能减少的线性表。（错误）7. 循环队列通常浪费一个存储空间。（正确）8. 循环队列也存在空间溢出问题。（正确）9. 栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。（正确）10. 任何一个递归过程都可以转换成非递归过程。（正确）习题四1. KMP算法的特点是在模式匹配时指示主串的指针不会变小。（正确）2. 只要串采用定长顺序存储，串的长度就可以立即获得，不需要用函数求。（错误）3. next函数值序列的产生仅与模式串有关。（错误）4. 空格串就是由零个字符组成的字符序列。（错误）5. 从串中取若干个字符组成的字符序列称为串的字串。（错误）6. 串名的存储映像就是按串名访问串值的一种方法。（正确）7. 两个串含有相等的字符，它们一定相等。（错误）8. 在插入和删除操作中，链式串一定比顺序串方便。（正确）9. 串的存储密度与结点大小无关。（错误）10. 在串的顺序存储中，通常将“0”作为串结束的标记。（正确）习题五1. 数组是一种复杂的数据结构，数组元素之间的关系既不是线性的，也不是树形的。（错误）2. 二维以上的数组其实是一种特殊的广义表。（正确）3. 稀疏矩阵压缩存储后，必会失去随机存储功能。（正确）4. 一个稀疏矩阵Amn采用三元组形式表示，若把三元组中有关下标与列下标的值互换，并把m和n的值互换，则就完成了Amn转置运算。（错误）5. 线性表可以看成是广义表的特例，如果广义表中的每个元素都是原子，则广义表便成为线性表。（正确）6. 一个广义表可以为其他广义表所共享。（正确）7. 广义表中原子个数即为广义表的长度。（错误）8. 所谓取广义表的表尾就是返回广义表中最后一个元素。（错误）9. 广义表是由零或多个原子或子表所组成的有限序列，所以广义表可能为空表。（正确）10. 任何一个非空广义表，其表头可能是单个元素或广义表，其表尾必定是广义表。（正确）习题六1. 哈夫曼树的结点个数不可能是偶数。（正确）2. 二叉树中序线索化后，不存在空指针域。（错误）3. 二叉树线索化后，任意一个结点均有指向其前驱和后继的线索。（错误）4. 哈弗曼编码是前缀编码。（错误）5. 非空的二叉树一定满足：某结点若有左孩子，则其中序前驱一定没有右孩子。（正确）6. 必须把一般树转换成二叉树后才能进行存储。（错误）7. 由先序和后序遍历序列不能唯一确定一棵二叉树。（正确）8. 一棵树中的叶子数一定等于与其对应的二叉树的叶子数。（错误）9. 一个树的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。（正确）10. 在哈夫曼树中，权值相同的叶结点都在同一层上。（错误）习题七1. 当改编AOE网上某一关键路径上任一关键活动后，必将产生不同的关键路径。2. 在n个结点的无向图中，若边数大于n-1，则该图必是连通图。3. 在AOE网中，关键路径上某个活动的时间缩短，整个工程的时间也就必定缩短。4. 若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。5. 一个有向图的邻接表和逆邻接表中结点的个数可能不相等。6. 强连通图的各顶点间均可达。7. 带权的连通无向图的最小代价生成树是唯一的。8. 广度遍历生成树描述了从起点到各顶点的最短路径。9. 邻接多重表是无向图和有向图的链式存储结构。10. 连通图上各边权值均不相同，则该图的最小生成树是唯一的。习题八1. 折半查找法的查找速度一定比顺序查找快。（错误）2. 就平均查找长度而言，分块查找最小、折半查找次之，顺序查找最大。（错误）3. 对一棵二叉树排序树线序遍历得出的结点序列是从小到大的序列。（错误）4. 哈希查找不需要任何比较。（错误）5. 将线性表中的信息组织成平衡二叉树，其优点之一是无论线性表中数据如何排列，总能保证平均查找长度均为log2n量级（n为线性表中的结点数目）。（争取）6. 在平衡二叉树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。（错误）7. 有序的线性表不论如何存储，都能采用折半查找。（错误）8. B+树既能索引查找也能顺序查找。（正确）9. Hash表的平均查找长度与处理冲突的方法无关。（错误）10. 装填因子是哈希表的一个重要参数，它反映了哈希表的装满程度。（正确）习题九1. 快速排序在所有排序方法中最快，而且所需附加空间也最少。（错误）2. 在大根堆中，最大元素在根的位置，最小元素在某个叶结点处。（正确）3. 用Shell方法排序时，若关键字的初始排序越杂乱无序，则排序效率就越低。（错误）4. 对n个记录进行堆排序，在最坏的情况下的时间复杂度是O(n2)。（错误）5. 在任何情况下，快速排序方法的时间性能总是