A.邻接矩阵表示时，占用的存储空间数只与图中结点个数有关,而与边数无关
B.邻接矩阵表示时，占用的存储空间数只与图中边数有关,而与结点个数无关
C.邻接表表示时，占用的存储空间数只与图中结点个数有关，而与边数无关
D.邻接表表示时，占用的存储空间数只与图中边数有关，而与结点个数无关
判断下列叙述正确与否。
①顺序存储方式只能用于存储线性结构。
②顺序存储方式的优点是存储密度大，且插入、删除运用算效率高。
③链表的每个结点中都恰好包含一个指针。
④散列法存储的基本思想是由关键码的值决定数据的存储地址。
⑤散列表的结点中只包含数据元素自身的信息，不包含任何指针。
⑥负载因子(装填因子)是散列法的一个重要参数，它反映散列表的装满程度。
⑦栈和队列的存储方式既可是顺序方式，也可是链接方式。
⑧用二叉链表法(llink-rlink法)存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。
⑨用相邻矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。
⑩邻接表法只能用于有向图的存储，而相邻矩阵法对于有向图和无向图的存储都适用。
● 邻接矩阵和邻接表是图（网）的两种基本存储结构，对于具有 n个顶点、e条边的图， （59） 。
（59）A. 进行深度优先遍历运算所消耗的时间与采用哪一种存储结构无关
B. 进行广度优先遍历运算所消耗的时间与采用哪一种存储结构无关
C. 采用邻接表表示图时，查找所有顶点的邻接顶点的时间复杂度为O(n*e)
D. 采用邻接矩阵表示图时，查找所有顶点的邻接顶点的时间复杂度为O(n2)
用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中的结点个数有关，而与图的边数无关。()
从供选择的答案中选出应填入下列叙述中()内的正确答案：
堆是一种有用的数据结构。例如关键码序列(A) 是一个堆。
堆排序是一种(B) 排序，它的一个基本问题是如何建堆，常用的建堆算法是1964年 Floyd提出的(C) 。对含n个元素的序列进行排序时，堆排序的时间复杂性是(D) ，所需的附加存储结点是(E)。
供选择的答案
A：①16，72，31，23，94，53
②94，53，31，72，16，53
③16，53，23，94，31，?2
④16，31，23，94，53，72
⑤94，11，53，23，16，72
B：①插入 ②选择 ③交换 ④基数 ⑤归并
C：①淘汰法 ②筛选法 ③递推法 ④LRU算法
D、E：①O(nlog2n) ②O(n) ③O(log2n)
④O(n2) ⑤O(1)
万维试题库系统第 页一、判断题每题分共分线性表的逻辑顺序总是与其物理顺序一致。（）【答案】错线性表的顺序存储优于链式存储。（）【答案】错在长度为n的顺序表中，求第i个元素的直接前驱算法的时间复杂度为0（1）。（）【答案】对若一棵二叉树中的结点均无右孩子，则该二叉树的中根遍历和后根遍历序列正好相反。（）【答案】错顺序表和一维数组一样，都可以按下标随机（或直接）访问。（）【答案】对内部排序是指排序过程在内存中进行的排序。（）【答案】对当待排序序列初始有序时，简单选择排序的时间复杂性为O（n）。（）【答案】错用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。【答案】对任何一棵二叉树的叶结点在三种遍历中的相对次序是不变的。（）【答案】对若将一批杂乱无章的数据按堆结构组织起来则堆中数据必然按从小到大的顺序线性排列。【答案】错如果采用如下方法定义一维字符数组：则这种数组在程序执行过程中不能扩充。（）【答案】错使用三元组表示稀疏矩阵中的非零元素能节省存储空间。（）【答案】对对稀疏矩阵进行压缩存储是为了节省存储空间。（）【答案】对当向一个最小堆插入一个具有最小值的元素时，该元素需要逐层向上调整，直到被调整到堆顶位置为止。【答案】对哈希查找法中解决冲突问题的常用方法是除留余数法。（）【答案】错对具有个结点的堆进行插入一个元素运算的时间复杂度为。【答案】错堆排序是一种稳定的排序算法。【答案】错如果有向图中各个顶点的度都大于，则该图中必有回路。【答案】错在一个顺序存储的循环队列中队头指针指向队头元素的后一个位置。（）【答案】错对平衡二叉树进行中根遍历，可得到结点的有序排列。（）【答案】对在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和中根遍历，则具有相同的结果。【答案】错拓扑排序是指结点的值是有序排序的。（）【答案】错在散列法中采取开散列（链地址）法来解决冲突时其装载因子的取值一定在之间。【答案】错在一棵具有个结点的线索二叉树中，每个结点的指针域可能指向子女结点，也可能作为线索，使之指向某一种遍历次序的前驱或后继结点，所有结点中作为线索使用的指针域共有个。【答案】错图的深度优先搜索是一种典型的回溯搜索的例子，可以通过递归算法求解。【答案】对对二叉排序树进行中根遍历，可得到结点的有序排列。（）【答案】对任何一棵二叉树的叶结点在三种遍历中的相对次序是不变的。（）【答案】对边数很少的稀疏图，适宜用邻接矩阵表示。（）【答案】错二叉树是一棵无序树。【答案】错对于一棵具有个结点，其高度为的二叉树，进行任一种次序遍历的时间复杂度为。【答案】对当待排序序列初始有序时，快速排序的时间复杂性为O（n）。（）【答案】错顺序表的空间利用率高于链表。（）【答案】对采用不同的遍历方法，所得到的无向图的生成树是不同的。（）【答案】对有回路的有向图不能完成拓扑排序。【答案】对存在这样的二叉树，对它采用任何次序的遍历，结果相同。【答案】对装载因子是散列表的一个重要参数，它反映了散列表的装满程度。【答案】对算法分析的目的是找出数据结构的合理性。（）【答案】错单链表可以实现随机存取。（）【答案】错边数很多的稠密图，适宜用邻接矩阵表示。（）【答案】对理想情况下哈希查找的等概率查找成功的平均查找长度是O（1）。【答案】对边数很少的稀疏图，适宜用邻接表表示。（）【答案】对对于同一组关键码互不相同的记录，若生成二叉搜索树时插入记录的次序不同则得到不同形态的二叉搜索树。【答案】对强连通分量是有向图中的极大强连通子图。【答案】对哈希查找法中解决冲突问题的常用方法是除留余数法。（）【答案】错顺序查找法适用于存储结构为顺序或链接存储的线性表。（）【答案】对若让元素依次进栈，则出栈次序是不可能出现的情况。（）【答案】错在线性链表中删除中间的结点时，只需将被删结点释放。（）【答案】错线性表若采用链式存储表示在删除时不需要移动兀素。（）【答案】对对任何用顶点表示活动的网络（网）进行拓扑排序的结果都是唯一的。【答案】错邻接矩阵适用于稠密图（边数接近于顶点数的平方），邻接表适用于稀疏图（边数远小于顶点数的平方）。【答案】对算法和程序原则上没有区别，在讨论数据结构时二者是通用的。【答案】错在一棵树中，所有叶结点都处在同一层上，所有叶结点中空指针数等于所有关键码的总数加。【答案】对循环链表的结点与单链表的结点结构完全相同，只是结点间的连接方式不同。（）【答案】对能够在链接存储的有序表上进行折半查找，其时间复杂度与在顺序存储的有序表上相同。【答案】错在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的结果。【答案】对一个无向连通图的生成树是图的极小的连通子图。（）【答案】对对稀疏矩阵进行压缩存储是为了节省存储空间。（）【答案】对快速排序的时间复杂性不受数据初始状态影响，恒为O（nlog）。（【答案】错两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。（）【答案】对只有用面向对象的计算机语言才能描述数据结构算法。（）【答案】错如果无向图中每个顶点的度都大于等于，则该图中必有回路。【答案】对顺序存储方式只适用于存储线性表。（）【答案】错若一棵二叉树中的结点均无右孩子，则该二叉树的中根遍历和后根遍历序列正好相同。（）【答案】对邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。【答案】错完全二叉树的某结点若无左孩子，则它必是叶结点。【答案】对在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和后序遍历，则具有相同的结果。【答案】错折半查找所对应的判定树，既是一棵二叉查找树，又是一棵理想
下面关于图的存储的叙述中正确的是()。
A.用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与顶点个数无关
B.用邻接表法存储图，占用的存储空间大小与图中边数和顶点个数都有关
C.用邻接矩阵法存储图，占用的存储空间大小与图中顶点个数和边数无关
D.用邻接矩阵存储图，占用的存储空间大小只与图中边数有关，而与顶点个数无关
用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中边数有关。
此题为判断题(对，错)。
下面关于图的存储的叙述中，哪一个是正确的。________
A.用相邻矩阵法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关
B.用相邻矩阵法存储图,占用的存储空间数只与图中边数有关,而与结点个数无关
C.用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关
D.用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关
