数据结构判断题

1、万维试题库系统第 页一、判断题每题分共分线性表的逻辑顺序总是与其物理顺序一致。（）【答案】错线性表的顺序存储优于链式存储。（）【答案】错在长度为n的顺序表中，求第i个元素的直接前驱算法的时间复杂度为0（1）。（）【答案】对若一棵二叉树中的结点均无右孩子，则该二叉树的中根遍历和后根遍历序列正好相反。（）【答案】错顺序表和一维数组一样，都可以按下标随机（或直接）访问。（）【答案】对内部排序是指排序过程在内存中进行的排序。（）【答案】对当待排序序列初始有序时，简单选择排序的时间复杂性为O（n）。（）【答案】错用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关

2、，而与图的边数无关。【答案】对任何一棵二叉树的叶结点在三种遍历中的相对次序是不变的。（）【答案】对若将一批杂乱无章的数据按堆结构组织起来则堆中数据必然按从小到大的顺序线性排列。【答案】错如果采用如下方法定义一维字符数组：则这种数组在程序执行过程中不能扩充。（）【答案】错使用三元组表示稀疏矩阵中的非零元素能节省存储空间。（）【答案】对对稀疏矩阵进行压缩存储是为了节省存储空间。（）【答案】对当向一个最小堆插入一个具有最小值的元素时，该元素需要逐层向上调整，直到被调整到堆顶位置为止。【答案】对哈希查找法中解决冲突问题的常用方法是除留余数法。（）【答案】错对具有个结点的堆进行插入一个元素运算的时间复杂

3、度为。【答案】错堆排序是一种稳定的排序算法。【答案】错如果有向图中各个顶点的度都大于，则该图中必有回路。【答案】错在一个顺序存储的循环队列中队头指针指向队头元素的后一个位置。（）【答案】错对平衡二叉树进行中根遍历，可得到结点的有序排列。（）【答案】对在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和中根遍历，则具有相同的结果。【答案】错拓扑排序是指结点的值是有序排序的。（）【答案】错在散列法中采取开散列（链地址）法来解决冲突时其装载因子的取值一定在之间。【答案】错在一棵具有个结点的线索二叉树中，每个结点的指针域可能指向子女结点，也可能作为线索，使之指向某一种遍历次序的前

4、驱或后继结点，所有结点中作为线索使用的指针域共有个。【答案】错图的深度优先搜索是一种典型的回溯搜索的例子，可以通过递归算法求解。【答案】对对二叉排序树进行中根遍历，可得到结点的有序排列。（）【答案】对任何一棵二叉树的叶结点在三种遍历中的相对次序是不变的。（）【答案】对边数很少的稀疏图，适宜用邻接矩阵表示。（）【答案】错二叉树是一棵无序树。【答案】错对于一棵具有个结点，其高度为的二叉树，进行任一种次序遍历的时间复杂度为。【答案】对当待排序序列初始有序时，快速排序的时间复杂性为O（n）。（）【答案】错顺序表的空间利用率高于链表。（）【答案】对采用不同的遍历方法，所得到的无向图的生成树是不同的。（）

5、【答案】对有回路的有向图不能完成拓扑排序。【答案】对存在这样的二叉树，对它采用任何次序的遍历，结果相同。【答案】对装载因子是散列表的一个重要参数，它反映了散列表的装满程度。【答案】对算法分析的目的是找出数据结构的合理性。（）【答案】错单链表可以实现随机存取。（）【答案】错边数很多的稠密图，适宜用邻接矩阵表示。（）【答案】对理想情况下哈希查找的等概率查找成功的平均查找长度是O（1）。【答案】对边数很少的稀疏图，适宜用邻接表表示。（）【答案】对对于同一组关键码互不相同的记录，若生成二叉搜索树时插入记录的次序不同则得到不同形态的二叉搜索树。【答案】对强连通分量是有向图中的极大强连通子图。【答案】对哈

6、希查找法中解决冲突问题的常用方法是除留余数法。（）【答案】错顺序查找法适用于存储结构为顺序或链接存储的线性表。（）【答案】对若让元素依次进栈，则出栈次序是不可能出现的情况。（）【答案】错在线性链表中删除中间的结点时，只需将被删结点释放。（）【答案】错线性表若采用链式存储表示在删除时不需要移动兀素。（）【答案】对对任何用顶点表示活动的网络（网）进行拓扑排序的结果都是唯一的。【答案】错邻接矩阵适用于稠密图（边数接近于顶点数的平方），邻接表适用于稀疏图（边数远小于顶点数的平方）。【答案】对算法和程序原则上没有区别，在讨论数据结构时二者是通用的。【答案】错在一棵树中，所有叶结点都处在同一层上，所有叶结

7、点中空指针数等于所有关键码的总数加。【答案】对循环链表的结点与单链表的结点结构完全相同，只是结点间的连接方式不同。（）【答案】对能够在链接存储的有序表上进行折半查找，其时间复杂度与在顺序存储的有序表上相同。【答案】错在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的结果。【答案】对一个无向连通图的生成树是图的极小的连通子图。（）【答案】对对稀疏矩阵进行压缩存储是为了节省存储空间。（）【答案】对快速排序的时间复杂性不受数据初始状态影响，恒为O（nlog）。（【答案】错两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设

8、在这片内存空间的两端。（）【答案】对只有用面向对象的计算机语言才能描述数据结构算法。（）【答案】错如果无向图中每个顶点的度都大于等于，则该图中必有回路。【答案】对顺序存储方式只适用于存储线性表。（）【答案】错若一棵二叉树中的结点均无右孩子，则该二叉树的中根遍历和后根遍历序列正好相同。（）【答案】对邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。【答案】错完全二叉树的某结点若无左孩子，则它必是叶结点。【答案】对在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和后序遍历，则具有相同的结果。【答案】错折半查找所对应的判定树，既是一棵二叉查找树，又是一棵理想

9、平衡二叉树。【答案】对存储无向图的邻接矩阵是对称的，因此可以只存储邻接矩阵的下（上）三角部分。【答案】对在对双向循环链表做删除一个结点操作时，应先将被删除结点的前驱结点和后继结点链接好再执行删除结点操作。（）【答案】对在用单链表表示的链式队列中，队头指针为，队尾指针为，则队空条件为，（）【答案】错对稀疏矩阵进行压缩存储是为了便于进行矩阵运算。（）【答案】错理想情况下哈希查找的等概率查找成功的平均查找长度是O（1）。（）【答案】对在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系都相同。（）【答案】对递归调用算法与相同功能的非递归算法相比，主要问题在于重复计算太多，而且调用本身需要

10、分配额外的空间和传递数据和控制，所以时间与空间开销通常都比较大。（）【答案】对采用不同的遍历方法，所得到的无向图的生成树总是相同的。（）【答案】错对于同一组记录，生成二叉搜索树的形态与插入记录的次序无关。【答案】错对一个有向图进行拓扑排序，一定可以将图的所有顶点按其关键码大小排列到一个拓扑有序的序列中。【答案】错链式栈与顺序栈相比一个明显的优点是通常不会出现栈满的情况。（）【答案】对对于两棵具有相同记录集合而具有不同形态的二叉搜索树，按中序遍历得到的结点序列是相同的。【答案】对在用散列表存储关键码集合时，可以用双散列法寻找下一个空位置。在设计再散列函数时，要求计算出的值与表的大小互质。【答案】

11、对边数很少的稀疏图，适宜用邻接矩阵表示。（）【答案】错递归的算法简单、易懂、容易编写，而且执行效率也高。（）【答案】错如果采用如下方式定义一维字符数组:线索二叉树中的每个结点通常包含有个数据成则这种数组在程序执行过程中不能扩充。（）【答案】对链队列的出队操作总是需要修改尾指针。（）【答案】错栈和队列都是顺序存取的线性表但它们对存取位置的限制不同。（）【答案】对数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。【答案】对直接选择排序是一种稳定的排序方法。【答案】错当从一个最小堆中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止

12、。【答案】对线性表的逻辑顺序总是与其物理顺序一致。（）【答案】错将转化为递TOC o 1-5 h z归函数时，递归部分为/递归结束条件为）（）【答案】对对平衡二叉树进行中根遍历，可得到结点的有序序列。（）【答案】对双向循环链表的结点与单链表的结点结构相同，只是结点间的连接方式不同。（）【答案】错在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻。（）【答案】错数组是一种静态的存储空间分配，就是说,在程序设计时必须预先定义数组的数据类型和存储空间大小，由编译程序在编译时进行分配。（）【答案】错员。【答案】对对于一棵具有个结点，其高度为的任何二叉树，进行任一种次序遍历的时间复杂度均为h【答案】错当

13、输入序列已经基本有序时，起泡排序需要比较关键码的次数，比快速排序还要少。【答案】对顺序查找法适用于存储结构为顺序或链接存储的线性表。【答案】对插入与删除操作是数据结构中最基本的两种操作，因此这两种操作在数组中也经常被使用。（）【答案】错哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。【答案】对在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和。（）【答案】对在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。（）【答案】对向一棵树插入关键码的过程中，若最终引起树根结点的分裂，则新树比原树的高度减少。【答案】错多维数组是一种复杂的数据结构，数组元素之间的关

14、系既不是线性的也不是树形的。（）【答案】对在二叉排序树中插入新结点时，新结点总是作为叶子结点插入。（）【答案】对边数很少的稀疏图，适宜用邻接表表示。（）【答案】对链队列的出队操作总是需要修改尾指针。（）【答案】错在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和按层遍历，则具有相同的结果。【答案】对二叉树中每个结点的两棵子树的高度差等于1【答案】错二叉树中不存在度大于2的结点，当某个结点只有一棵子树时无所谓左、右子树。【答案】错链队列的出队操作是不需要修改尾指针的。（）【答案】错图的广度优先搜索算法通常采用非递归算法求解。【答案】对拓扑排序是指结点的值是有序排序的。（）

15、【答案】错数据的逻辑结构与数据元素本身的内容和形式无关。【答案】对在树的存储中，若使每个结点带有指向双亲结点的指针，这为在算法中寻找双亲结点带来方便。【答案】对二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。【答案】错边数很多的稠密图，适宜用邻接表表示。（）【答案】错从一棵树删除关键码的过程中，若最终引起树根结点的合并，则新树比原树的高度增加。【答案】错在索引顺序结构的搜索中，对索引表既可以采取顺序搜索，也可以采用折半搜索。【答案】对算法和程序都应具有下面一些特征：有输入，有输出，确定性，有穷性，有效性。（）【答案】错对一个连通图进行一次深度优先搜索可以遍访图中的所有顶点。【答案】对对于一棵具有个结点的任何二叉树，进行前序、中序或后序的任一种次序遍历的空间复杂度为g【答案】错用字符数组存储长度为的字符串，数组长度至少为+（）【答案】对线性表若采用链式存储表示时，其存储结点的地址可连续也可不连续。（）【答案】对在二叉排序树中插入新结点时，新结