出自:国家开放大学数据结构复习题

图的强连通分量是无向图的极大连通子图。
对任意一个图从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可访问到该图的每个顶点。
一个有向图的邻接表和逆邻接表中的节点个数一定相等
有向图用邻接矩阵表示后，顶点i的出度等于第i行中非0且非无穷的元素个数。
图G的某一最小生成树的代价一定小于其他生成树的代价。
任一个有向图的拓扑序列只有一个。
一个无向连通图的生成树是含有该连通图的全部顶点的极小连通子图。
采用邻接表存储的图的广度优先遍历算法类似于二叉树的按层次遍历。
已知图G的邻接矩阵如下所示：
从顶点1出发的广度优先搜索序列为（ ）。
A.1；2，3， 4；5；6
B.2；1，3，5；4；6
C.3；1，2，4；5；6
D.4；2，3，6；1；5
对于一个无向图，假定采用邻接矩阵表示，试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列。
注：每一种序列都是唯一的，因为都是在存储结构上得到的。


A.0，2，3，4，5，1，6
B.0，2，3，5，1，6，4
C.0，2，3，5，6，1，4
D.0，2，3，4，5，1，6
顺序查找方法适合于存储结构为（ ）的线性表。
A．散列存储 B．索引存储
C．散列存储或索引存储 D．顺序存储或链接存储
在有序表{1，3，8，13，33，42，46，63，76，78，86，97，100}中，用折半查找值86时，经（ ）次比较后查找成功。
A．3 B．4 C．6 D．8
对二叉排序树进行（ ）遍历，可以使遍历所得到的序列是有序序列。
A．按层次 B．后序 C．中序 D．前序
有一个长度为12的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（ ）。+++++
A．37/12 B．39/12 C．41/12 D．35/12
已知一个有序表为{11,22,33,44,55,66,77,88,99}，则顺序查找元素55需要比较（ ）次。
A．3 B．4 C．5 D．6
顺序查找法与折半查找法对存储结构的要求是（ ）。
A．顺序查找与折半查找均只适用于顺序表
B．顺序查找与折半查找均既适用于顺序表，也适用于链表
C．顺序查找只是适用于顺序表
D．折半查找适用于顺序表
有数据{53,30,37,12,45,24,96}，从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度最小，应该选择的序列是（ ）。
A．45,24,53,12,37,96,30 B．37,24,12,30,53,45,96
C．12,24,30,37,45,53,96 D．30,24,12,37,45,96,53
采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（ ）。
A．n B．n/2
C．(n+1)/2 D．(n-1)/2
对于一个线性表，若要求既能进行较快地插入和删除，又要求存储结构能够反映数据元素之间的逻辑关系，则应该（ ）。+++++
A．以顺序存储方式 B．以链接存储方式
C．以索引存储方式 D．以散列存储方式
哈希函数有一个共同的性质，即函数值应当以（ ）取其值域的每个值。
A．最大概率 B．最小概率
C．平均概率 D．同等概率
在最坏情况下，折半查找与二叉排序树查找性能比较，（ ）
A. 完全相同 B.折半查找性能好
C. 二叉排序树查找性能好 D.不能确定
设哈希表长m=14，哈希函数H(key)=key mod 11。表中已有4个结点：addr(15)=4; addr(38)=5; addr(61)=6; addr(84)=7。如用线性探测处理冲突，关键字为49的结点的地址是（ ）。
A.8 B.3 C.5 D.9
采用折半查找方法查找长度为n的线性表时，每个元素的平均查找长度为（ ）。+++++++
A．n2 B.nlog2n C.n D.log2n
哈希表的平均查找长度（ ）
A．与处理冲突的方法有关，与表的长度无关
B．与处理冲突的方法无关，与表的长度有关
C．与处理冲突的方法有关，与表的长度有关
D．与处理冲突的方法无关，与表的长度无关
一组记录的关键字是{19,14,23,1,68,20,84,27,55,11,10,79}，用链接地址法构造散列表，散列函数为H(key)=key mod 13,散列地址为1的链中有（ ）个记录。
A.1 B.2 C.3 D.4
二叉排序树的查找效率与二叉树的（ ）有关。
A.高度 B.结点个数 C.树形 D.结点的位置
在顺序查找、折半查找、哈希表查找3种方法中，平均查找长度与结点个数n无关的查找方法是折半查找。
在一个查找表中，能够唯一地确定一个记录的关键字称为主关键字。
顺序查找是一种最简单的查找方法。
折半查找的前提条件是，查找表中记录相应的关键字值必须有序或者部分有序。
二叉排序树的建立过程上实际上是从空树逐次插入的过程。
理想情况下，哈希表查找等概率查找成功的时间复杂度是O(1)。
按照一定规则，在二叉排序树上插入、删除结点，仍能保持二叉排序树的性质。
分块查找分为两个步骤：第一步是要对索引表进行查找；第二步是在块中查找。这两步查找都可以采用折半查找或者顺序查找方法。
一个好的哈希函数，应该使哈希地址均匀地分布在整个哈希表的地址区间中，完全避免冲突的发生。
在有序顺序存储的线性表中查找一个元素，用折半查找速度一定比顺序查找快
二叉树为二叉排序树的充分必要条件是，任一个分支结点的值都大于其左孩子的值，小于右孩子的值。
二叉排序树在呈单支二叉树时，查找效率最低
将10个元素散列到10000个单元的哈希表中，仍然可能会产生冲突
根据无序序列构造二叉排序树的过程，也是对无序序列排序的过程。
折半查找方法运用在升序序列比降序序列效率更高，所以降序序列最好先转换为升序序列。
从未排序序列中依次取出元素与已经排好序的序列中的元素作比较。将其放入已排序序列的正确的位置上，此方法称为（ ）。
A. 插入排序 B. 交换排序
C. 选择排序 D. 归并排序
依次将每两个相邻的有序表合并成一个有序表的排序方法称为（ ）。
A. 插入排序 B. 交换排序
C. 选择排序 D. 归并排序
当两个元素出现逆序的时候就交换位置，这种排序方法称为（ ）。
A. 插入排序 B. 交换排序
C. 选择排序 D. 归并排序
从未排序序列中挑选元素，并将其放入已排序序列的一端，此方法称为（ ）排序。
A. 插入排序 B. 交换排序
C. 选择排序 D. 归并排序
在下列排序方法中，关键字比较的次数与记录初始排列秩序无关的是（ ）。
A. 冒泡排序 B. 希尔排序
C. 选择排序 D. 插入排序
在待排序元素基本有序的情况下，效率最高的排序方法是（ ）。
A. 插入排序 B. 快速排序
C. 堆排序 D. 归并排序
在下列几种排序方法中，平均情况下占用内存量最大的是（ ）方法。
A. 插入排序 B. 选择排序
C. 快速排序 D. 归并排序
每次把待排序的区间划分为左、右两个子区间，其中左区间中记录的关键字均小于等于基准记录的关键字，右区间中记录的关键字均大于等于基准记录的关键字，这种排序称为（ ）。
A. 插入排序 B. 快速排序
C. 堆排序 D. 归并排序
设已有m个元素有序，在未排好序的序列中挑选第m+1个元素，并且只经过一次元素的交换就使第m+1个元素排序到位，该方法是（ ）。
A. 折半插入排序 B. 冒泡排序
C. 归并排序 D. 直接选择排序
首页 <上一页 3 4 5 6 7 下一页> 尾页