知道智慧树网课《数据结构（山东联盟-青岛大学）》课后章节测试答案

第一章测试1【单选题】(10分)在Data_Structure=(D，R)中，D是（）的有限集合。A.数据元素B.数据对象C.数据操作D.算法2【单选题】(10分)计算机所处理的数据一般具有某种关系，这是指（）。A.数据元素与数据元素之间存在的某种关系B.数据与数据之间存在的某种关系C.元素内数据项与数据项之间存在的某种关系D.数据文件内记录与记录之间存在的某种关系3【单选题】(10分)算法的时间复杂度与（）有关。A.计算机硬件的运行速度B.问题规模C.编译后执行程序的质量D.源程序的长度4【单选题】(10分)以下关于数据结构的说法正确的是（）。A.数据结构仅由其逻辑结构和存储结构决定B.数据结构的逻辑结构唯一地决定了该数据结构的存储结构C.数据结构的逻辑结构独立于其存储结构D.数据结构的存储结构独立于该数据结构的逻辑结构5【单选题】(10分)某算法的时间复杂度是O(n2)，表明该算法（）。A.问题规模是n^2B.执行时间等于n^2C.问题规模与n^2成正比D.执行时间与n^2成正比6【单选题】(10分)从逻辑上可将数据结构分为（）。A.线性结构和非线性结构B.动态结构和静态结构C.内部结构和外部结构D.紧凑结构和非紧凑结构7【判断题】(10分)数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的。A.错B.对8【判断题】(10分)数据的物理结构是指数据结构在计算机内的实际存储形式。A.错B.对9【判断题】(10分)每种数据结构都具备三种基本运算：插入、删除和查找。A.对B.错10【判断题】(10分)算法的时间效率和空间效率往往相互冲突，有时很难两全其美。A.错B.对第二章测试1【单选题】(5分)线性表是一个（）。A.数据元素的有限序列，数据元素还可以是线性表B.数据元素的有限序列，元素不可以是线性表C.数据元素的有限序列，数据元素的类型可以不同D.数据元素的无限序列，元素个数可以是零个，也可以有多个2【单选题】(5分)以下关于线性表的说法中正确的是（）。A.线性表中至少有一个元素B.除第一个元素和最后一个元素外，其他每个元素有且仅有一个直接前趋元素和一个直接后继元素C.线性表中的元素必须按照从小到大或从大到小的次序排列D.线性表中所有的元素都可以直接（或随机）存取3【单选题】(5分)以下关于线性表的说法中正确的是（)。A.每个元素最多有一个直接前趋和一个直接后继B.线性表中的元素还可以是线性表，但数据类型必须相同C.每个元素有且仅有一个直接前趋，有且仅有一个直接后继D.每个元素最少有一个直接前趋和一个直接后继4【单选题】(5分)如果线性表中的表元素既没有直接前趋，也没有直接后继，则该线性表中应有（）个表元素。A.nB.2C.0D.15【单选题】(5分)在线性表中的每一个表元素都是数据对象，它们是不可再分的（）。A.数据项B.数据字段C.数据记录D.数据元素6【单选题】(5分)顺序表是线性表的（）表示。A.顺序存储B.有序C.顺序存取D.连续7【单选题】(5分)以下关于顺序表的说法中正确的是（）。A.顺序表利用一维数组表示，因此顺序表与一维数组在结构上一致，它们可以通用B.顺序表和一维数组一样，都可以按下标随机（或直接）访问，顺序表还可以从某一指定元素开始，向前或向后逐个元素顺序访问C.在顺序表中每一表元素的数据类型还可以是顺序表D.在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻8【单选题】(5分)顺序表的优点是（）。A.存储密度（存储利用率）高B.插入操作的时间效率高C.适用于各种逻辑结构的存储表示D.删除操作的时间效率高9【单选题】(5分)以下关于单链表的叙述中的是（）。A.结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构B.逻辑上相邻的结点物理上不必相邻C.插入、删除运算操作方便，不必移动结点D.可以通过计算直接确定第i个结点的存储地址10【单选题】(5分)以下关于单链表的叙述中的是（）。A.结点的指针域用于存放一个指针，指示本结点所存储数据元素的直接后继元素所在结点的地址B.结点的数据域用于存储线性表的一个数据元素C.单链表中各结点地址不可能连续D.所有数据通过指针的链接而组织成单链表11【单选题】(5分)在单链表上实施插入和删除操作（）。A.只需移动结点，不需改变结点指针B.不需移动结点，只需改变结点指针C.既需移动结点，又需改变结点指针D.不需移动结点，不需改变结点指针12【单选题】(5分)在单链表最终增加头结点的目的是（)。A.标识链表首元结点的位置B.方便对链表的统一命名C.方便插入、删除等运算的实现D.使得链表遍历有一个终结结点13【单选题】(5分)已知单链表中结点*q是结点*p的直接前趋，若在*q与*p之间插入结点*s,则应执行以下（）操作。A.q->next=s;s->next=p;B.p->next=s->next;s->next=p;C.s->next=p->next;p->next=s;D.p->next=s;s->next=q;14【单选题】(5分)已知单链表中结点*p不是链尾结点，若在*p之后插入结点*s，则应执行以下（）操作。A.s->next=p;p->next=s；B.p->next=s；s->next=p;C.s->next=p->next;p->next=s;D.s->next=p->next;p=s;15【判断题】(5分)顺序表中元素的逻辑顺序和物理顺序总是一致的。A.对B.错16【判断题】(5分)在单链表中插入新元素时，必须先找到要插入位置的前一个结点。A.对B.错17【判断题】(5分)顺序表是静态存储结构，而链表是动态存储结构。A.对B.错18【判断题】(5分)循环单链表可以仅在链表尾部设置链尾指针。A.错B.对19【判断题】(5分)在为顺序表分配连续的存储空间时，必须预估该空间的最大容量。但想估计得准确很不容易，而为链表分配存储空间则不会为此烦恼。A.错B.对20【判断题】(5分)在顺序表中插入和删除时效率太低，因此它不如链表好。A.错B.对第三章测试1【单选题】(5分)栈的插入和删除操作在（）进行。A.指定位置B.栈底C.栈顶D.任意位置2【单选题】(5分)对一个初始为空的栈s执行操作Push(s,5),Push(s,2),Push(s,4),Pop(s,x),getTop(s,x)后，x的值应是（）。A.2B.4C.5D.03【单选题】(5分)用S表示进栈操作，用X表示出栈操作，若元素的进栈顺序是1234，为了得到1342出栈顺序，相应的S和X的操作序列为（）。A.SXSSXSXXB.SXSXSSXXC.SXSSXXSXD.SSSXXSXX4【单选题】(5分)假设一个栈的输入序列是1,2,3,4，则不可能得到的输出序列是（）。A.4,1,2,3B.4,3,2,1C.1,2,3,4D.1,3,4,25【单选题】(5分)已知一个栈的进栈序列为1,2,3,…,n，其输出序列的第一个元素是i，则第j个出栈元素是（）。A.不确定B.j-i+1C.n-iD.j-i6【单选题】(5分)已知一个栈的进栈序列为1,2,3,…,n，其输出序列是p1,p2,p3,…,pn。若p1=n，则pi的值是（）。A.n-i+1B.n-iC.不确定D.i7【单选题】(5分)已知一个栈的进栈序列为1,2,3,…,n，其输出序列是p1,p2,p3,…,pn。若p1=3，则p2的值（）。A.一定是1B.可能是2C.可能是1D.一定是28【单选题】(5分)已知一个栈的进栈序列为p1,p2,p3,…,pn，其输出序列是1,2,3,…,n。若p3=1，则p1的值（）。A.可能是2B.一定是3C.一定是2D.不可能是29【单选题】(5分)设一个循环队列Q[maxSize]的队头指针为front，队尾指针为rear，队列最大容量为maxSize，除此之外该队列再没有其他数据成员，则该队列的队满条件是（）。A.Q.front==Q.rearB.Q.rear==(Q.front+1)%maxSizeC.Q.front==(Q.rear+1)%maxSizeD.Q.front+Q.rear>=maxSize10【单选题】(5分)设循环队列的存储容量为maxSize，队头和队尾指针分别为front和rear。若有一个循环队列Q，可应用下列语句（）计算队列元素个数？A.(Q.rear-Q.front+maxSize)%maxSizeB.Q.rear-Q.frontC.(Q.rear-Q.front)%maxSize+1D.Q.rear-Q.front+111【单选题】(5分)一个队列的进队顺序是1,2,3,4，则该队列可能的输出序列是（）。A.4,3,2,1B.1,3,2,4C.1,4,2,3D.1,2,3,412【单选题】(5分)对于链式队列，在执行插入操作时（）。A.仅修改头指针B.头、尾指针可能都要修改C.头、尾指针都要修改D.仅修改尾指针13【单选题】(5分)最适合用作链式队列的链表是（）。A.只带队头指针的非循环单链表B.带有队头指针和队尾指针的循环单链表C.只带队头指针的循环单链表D.带有队头指针和队尾指针的非循环单链表14【单选题】(5分)最不适合用作链式队列的链表是（）。A.只带队尾指针的循环单链表B.带有队头指针的双向非循环链表C.只带队尾指针的双向循环链表D.带有队头指针的双向循环链表15【单选题】(5分)设一个链式队列q的队头指针和队尾指针分别为front和rear，则判断队列空的条件是（）。A.q.front==q.rearB.q.front!=NULLC.q.rear==NULLD.q.front==NULL16【单选题】(5分)将递归算法转换成非递归算法时，通常要借助的数据结构是（）。A.队列B.线性表C.树D.栈17【单选题】(5分)栈与一般线性表的区别在于（）。A.数据元素的类型不同B.数据元素的个数不同C.逻辑数据不同D.运算是否受限制18【判断题】(5分)栈和队列都是顺序存取结构。A.错B.对19【判断题】(5分)对循环队列初始化时·要求队头指针与队尾指针指向同一个位置，不论队列存储中什么位置都可以。A.错B.对20【判断题】(5分)栈是实现过程和函数等子程序调用所必需的结构。A.对B.错第四章测试1【单选题】(10分)字符串可定义为n(n≥0)个字符的有限（），其中，n是字符串的长度，表明字符串中字符的个数。A.集合B.聚合C.序列D.数列2【单选题】(10分)串是一种特殊的线性表，其特殊性体现在（）。A.可以顺序存储B.数据元素是一个字符C.数据元素可以是多个字符D.可以链接存储3【单选题】(10分)有n个字符的字符串的非空子串个数最多有（）。A.nB.n(n+1)/2C.n(n-1)/2D.n-14【单选题】(10分)两个字符串相等的条件是（）。A.两个串的长度相等，并且对应位置上的字符相同B.两个串的长度相等，并且两个串包含的字符相同C.两个串的长度相等D.两个串包含的字符相等5【单选题】(10分)设有两个串：T和P，求P在T中首次出现的位置的运算叫做（）。A.串连接B.串替换C.求子串D.模式匹配6【单选题】(10分)在以下关于串的说法中正确的是（）。A.用块链存储表示实现的串的结点大小为4,说明每个结点可存储4个字符B.串长度是指串中不同字符的个数C.空串是由空格组成的串D.子串是从串中抽取出若干字符组成的串7【单选题】(10分)设有两个串T和P，求P在T中首次出现的位置的运算叫做（）。A.串替换B.串连接C.求子串D.模式匹配8【单选题】(10分)设T="aaaaaacaaaca”，P=“aaac”，使用BF算法的模式匹配过程需要执行的趟数为（）。A.7B.3C.4D.29【判断题】(10分)应用KMP算法进行模式匹配时，next函数值序列的产生仅与模式串有关。A.错B.对10【判断题】(10分)KMP算法的特点是在模式匹配时指示目标串当前比对位置的指针不会回退。A.对B.错第五章测试1【单选题】(10分)对稀疏矩阵进行压缩存储的目的是（）。A.节省存储空间B.便于输入和输出C.降低运算的时间复杂度D.便于进行矩阵运算2【单选题】(10分)一个稀疏矩阵采用压缩后，和直接采用二维数组存储相比会失去（）特性。A.其余选项都不对B.顺序存储C.随机存取D.输入输出3【单选题】(10分)稀疏矩阵常用的压缩存储方法有（）。A.三元组和散列表B.三元组和十字链表C.散列表和十字链表D.二维数组4【单选题】(10分)以下关于一维数组与顺序表不同之处的说法中的是（）。A.前者既可以是逻辑结构也可以是存储结构，后者是线性表的存储结构B.前者的长度不变，后者的长度可变C.前者的元素可以不连续存放，后者的元素必须相继存放D.前者的元素数据类型相同，后者的元素数据类型可以不相同5【单选题】(10分)将一个n*n的对称矩阵A的对角线和对角线以上的部分按列优先存放于一个一维数组中，那么A有()个矩阵元素未被存于sa中。A.n(n-1)/2B.n(n-1)C.n(n+1)/2D.n^2/26【单选题】(10分)设一维数组A[n]中每个元素占用6个存储单元，若A[5]的存储地址从100开始，则该数组的首地址是（)。A.30B.64C.95D.767【单选题】(10分)在二维数组A[9][10]中，每个数组元素占用3个存储单元，从首地址SA开始按行优先连续存放。在这种情况下，元素A[8][5]的起始地址为（）。A.SA+141B.SA+255C.SA+144D.SA+2228【单选题】(10分)设一个稀疏矩阵有1000行850列，其中有1000个非零元素。设每个整数占2字节，数据占4字节。则用三元组表存储该矩阵时所需字节数是（）。A.8000B.4000C.18000D.10009【判断题】(10分)二维数组是其数组元素为线性表的线性表。A.错B.对10【判断题】(10分)用一维数组存储特殊矩阵，可以简化对矩阵的存取操作。A.对B.错第六章测试1【单选题】(5分)树最合适用来表示（）。A.元素之间具有分支层次关系的数据B.无序数据元素C.元素之间无联系的数据D.有序数据元素2【单选题】(5分)一棵有n个结点的树的所有结点的度数之和为（）。A.nB.n-1C.n+1D.2n3【单选题】(5分)设树中某结点不是根结点，则离它最近的祖先结点是（）。A.父结点B.父结点的父结点C.该结点本身D.根结点4【单选题】(5分)在二叉树中某一结点的深度为3,高度为4,该树的髙度至少为（）。A.6B.8C.5D.75【单选题】(5分)设一棵高度为h的满二叉树有n个结点，其中有m个叶结点，则（）。A.n=2^h-1B.m=h-1C.n=h+mD.h+m=2n6【单选题】(5分)具有33个结点的完全二叉树，有（）个度为1的结点。A.1B.16C.12D.07【单选题】(5分)一颗有124个叶子结点的完全二叉树最多有（）个结点。A.249B.247C.248D.2508【单选题】(5分)一颗有129个叶结点的完全二叉树最少有（）个结点。A.258B.255C.254D.2579【单选题】(5分)如果二叉树T2是由一棵树T1转换而来的二叉树，那么T1中结点的先根序列对应T2的（）序列。A.先序遍历B.层次遍历C.中序遍历D.后序遍历10【单选题】(5分)如果二叉树T2是由一棵树T1转换而来的二叉树，那么T1中结点的后根序列对应T2的（）序列。A.先序遍历B.中序遍历C.层次遍历D.后序遍历11【单选题】(5分)一个深度为k且只有k个结点的二叉树，按照完全二叉树顺序存储的方式存放于一个一维数组A[n]中，那么n应至少是（）。A.2^k-1B.2^kC.2kD.2k+112【单选题】(5分)二叉树的叶子结点在前序、中序和后序遍历过程中的相对顺序（）。A.无法确定B.不发生改变C.其余选项都不对D.发生改变13【单选题】(5分)设n、m为一棵二叉树上的两个结点，在中序遍历序列中，n在m前的条件是（）。A.n是m的子孙B.n在m左方C.n是m的祖先D.n在m右方14【单选题】(5分)在一棵二叉树中有两个结点n和m。在该二叉树的前序遍历序列中n在m之前，而在其后序遍历序列中n在m之后，则n和m的关系是（）。A.n是m的右兄弟B.n是m的子孙C.n是m的左兄弟D.n是m的祖先15【单选题】(5分)前序序列与中序序列正好相反的非空二叉树是（）。A.左单支树B.满二叉树C.右单支树D.完全二叉树16【单选题】(5分)在中序线索二叉树中，指针t所指结点的左子树为空的充要条件是（）。A.t->ltag==1B.t->ltag==1且t->lchild==NULLC.其余选项都不对D.t->lchild==NULL17【单选题】(5分)设森林F对应的二叉树为A，它有m个结点。A的根为p，p的右子树中结点个数为n，则森林F中第一棵树的结点个数是（）。A.m-n-1B.n+1C.m-nD.无法确定18【单选题】(5分)设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶结点，则B中右指针域为空的结点有（）个。A.nB.n+2C.n+1D.n-119【单选题】(5分)用n个权重构造出来的Huffman树共有（）个结点。A.2n-1B.n+1C.2n+1D.2n20【单选题】(5分)设T是Huffman树，具有5个叶结点，树T的高度最高可以是（）。A.3B.4C.5D.6第七章测试1【单选题】(4分)在无向图中定义顶点的度为与它相关联的（）的数目。A.顶点B.边C.权值D.权2【单选题】(4分)具有n个顶点且每一对不同的顶点之间都有一条边的无向图被称为（）。A.无向树图B.无向完全图C.无向强连通图D.无向连通图3【单选题】(4分)一个有n个顶点的无向图最多有（）边。A.n(n-1)/2B.n(n-1)C.nD.2n4【单选题】(4分)具有6个顶点的无向图至少应有（）条边才能确保是一个连通图。A.6B.8C.7D.55【单选题】(4分)图的简单路径是指（）不重复的路径。A.边与顶点均B.边C.权值D.顶点6【单选题】(4分)在一个具有n个顶点的有向图中，若所有顶点的出度之和为s，则所有顶点的入度之和为（）。A.sB.nC.s+1D.s-17【单选题】(4分)在下列有关图的说法中正确的是（）。A.在图结构中，顶点可以没有任何前驱和后继B.具有n个顶点的无向图最多有n(n-1)条边，最少有n-1条边C.在无向图中，边的条数是结点度数之和D.在有向图中，各顶点的入度之和等于各顶点的出度之和8【单选题】(4分)对于一个具有n个顶点和e条边的无向图，若采用邻接矩阵表示，则该矩阵中的非零元素个数是（）。A.e^2B.eC.n^2D.2e9【单选题】(4分)无向图的邻接矩阵是一个（）。A.对称矩阵B.对角矩阵C.上三角矩阵D.零矩阵10【单选题】(4分)有n个顶点和e条边的无向图采用邻接矩阵存储，零元素的个数为（）。A.n^2-2eB.n^2-eC.2eD.e11【单选题】(4分)从邻接矩阵可知，该有向图共有（）条有向边。A.2B.9C.4D.312【单选题】(4分)带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中（）。A.第i行非∞的元素之和B.第i列非∞的元素之和C.第i行非∞且非0的元素个数D.第i列非∞且非0的元素个数13【单选题】(4分)下列说法中正确的是（）。A.一个图的邻接矩阵表示不唯一，邻接表表示唯一B.一个图的邻接矩阵表示是唯一的，邻接表表示也唯一C.一个图的邻接矩阵表示是唯一的，邻接表表示不唯一D.一个图的邻接矩阵表示不唯一，邻接表表示也不唯一14【单选题】(4分)用邻接表存储图所用的空间大小（）。A.只与图的顶点数有关B.与图的顶点数和边数都有关C.与边数的平方有关D.只与图的边数有关系15【单选题】(4分)在下列有关图的存储结构的说法中的是（）。A.邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用B.对同一个有向图来说，邻接表中边结点数与逆邻接表中边结点数相等C.用邻接矩阵存储一个图时所占用的存储空间大小与图中的顶点个数有关，而与图的边数无关D.邻接矩阵只适用于稠密图（边数接近于顶点数的平方），邻接表适用于稀疏图（边数远小于顶点数的平方）16【单选题】(4分)设图有n个顶点和e条边，采用邻接矩阵时，遍历图时的顶点所需时间为（）。A.O(n^2)B.O(e)C.O(n)D.O(ne)17【单选题】(4分)设图有n个顶点和e条边，采用邻接表时，遍历图的顶点所需时间为（）。A.O(ne)B.O(n^2)C.O(e)D.O(n+e)18【单选题】(4分)如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（）。A.—棵树B.连通图C.有回路D.强连通图19【单选题】(4分)如果一个连通网络G中各边权值互不相同，权值最小的边一定包含在G的()生成树中。A.广度优先B.任何C.最小D.深度优先20【单选题】(4分)任何一个连通图的最小生成树（）。A.一定有多棵B.有一棵或多棵C.可能不存在D.只有一棵21【单选题】(4分)Dijkstra算法是（）来求出图中从某顶点到其余顶点最短路径的。A.按长度递增的顺序求出图的某顶点到其余顶点的最短路径B.按长度递减的顺序求出图的某项点到其余顶点的最短路径C.通过深度优先遍历求出图的某顶点到其余顶点的所有路径D.通过广度优先遍历求出图的某顶点到其余顶点的最短路径22【单选题】(4分)已知一个带权有向图如图所示，依据Dijkstra算法求从顶点1到其余各顶点的最短路径的顺序应是（）。A.25346B.25463C.54632D.2354623【单选题】(4分)如果一个有向图具有拓扑有序序列，并且顶点按拓扑有序序列编号，那么它的邻接矩阵必定为（）。A.三对角矩阵B.下三角矩阵C.对称矩阵D.上三角矩阵24【单选题】(4分)若一个有向图中的部分顶点不能通过拓扑排序排到一个拓扑有序序列里，则可断定该有向图是一个（）。A.含有多个入度为0的顶点的图B.DAG图C.含有顶点数大于1的强连通分量D.强连通图25【单选题】(4分)在如图所示的AOE网中，关键路径长度为（）。A.22B.16C.23D.13第八章测试1【单选题】(4分)顺序查找算法适用于（）结构。A.线性表B.连通图C.查找树D.查找网2【单选题】(4分)在顺序存储的线性表R[30]上进行顺序查找的平均查找长度为（）。A.15B.20C.16D.15.53【单选题】(4分)对长度为10的顺序表进行查找，若查找前面5个元素的概率相同，均为1/8，查找后面5个元素的概率相同，均为3/40，则查找到表中任一元素的平均查找长度为（）。A.39/8B.5.5C.5D.19/44【单选题】(4分)如果有5个关键字{a,b,c,d,e}放在顺序表中，它们的查找概率分别为{0.35,0.25，0.20,0.15,0.05}，按照（）顺序存放可使平均查找长度达到最小。A.a,c,e,d,bB.e,d,c,b,aC.a,b,c,d,eD.d,a,b,c,e5【单选题】(4分)对长度为n的有序单链表，若查找每个元素的概率相等，则顺序查找表中任一元素的查找成功的平均查找长度为（）。A.(n-1)/2B.(n+1)/2C.n/4D.n/26【单选题】(4分)对线性表进行折半查找时，要求线性表必须（）。A.以链接方式存储B.以顺序方式存储，且结点按关键字有序排序C.以链接方式存储，且结点按关键字有序排序D.以顺序方式存储7【单选题】(4分)采用折半查找方式查找一个长度为n的有序顺序表时，其平均查找长度为（）。A.O(nlog2n)B.O(n^2)C.O(log2n)D.O(n)8【单选题】(4分)采用折半查找法查找长度为n的有序顺序表，查找每个元素的数据比较次数（）对应二叉判定树的高度（设高度≥2）。A.小于B.小于等于C.大于D.等于9【单选题】(4分)折半查找和二叉排序树的时间性能（）。A.不定B.有时不相同C.相同D.完全不同10【单选题】(4分)在常用的描述二叉排序树的存储结构中，关键字值最大的结点（）。A.左指针一定为空B.左右指针均不为空C.右指针一定为空D.左右指针均为空11【单选题】(4分)m阶B-树是一棵（）。A.m-1叉高度平衡查找树B.m+1叉高度平衡查找树C.m叉高度平衡查找树D.m叉查找树12【单选题】(4分)下列关于m阶B-树的说法中的是（）。A.根结点中的数据是有序的B.所有叶结点都在同一层次上C.非失败结点至少有m/2（m为偶数）或m/2+1（m为奇数）棵子树D.根结点至多有m棵子树13【单选题】(4分)下面关于B-树和B+树的叙述中的是（）。A.B-树和B+树都能有效地支持随机查找B.B-树和B+树都是平衡的多叉查找树C.B-树和B+树都能有效地支持顺序查找D.B-树和B+树都可用于文件的索引结构14【单选题】(4分)散列法存储的基本思想是根据（）来决定元素的存储地址。A.元素的序号B.关键字值C.元素个数D.非码属性15【单选题】(4分)设一个散列表中有n个元素，用散列法进行查找，理想情况下的平均查找长度是（）。A.O(n)B.O(1)C.O(log2n)D.O(n^2)16【单选题】(4分)使用散列函数将元素的关键字值映射为散列地址时，常会产生冲突。此时的冲突是指（）。A.装填因子过大，数据元素过多B.两个元素具有相同的序号C.两个元素的关键字值不同，而非关键字值相同D.不同关键字值对应到相同的存储地址17【单选题】(4分)以下关于散列函数选择原则的叙述中，不正确的是（）。A.装填因子必须限制在0.8以下B.散列函数计算出来的地址应能均匀分布在整个地址空间中C.散列函数应是简单的，能在较短的时间内计算出结果D.散列函数的定义域应包括全部关键字值,值域必须在表范围之内18【单选题】(4分)计算出的地址分布最均匀的散列函数是（）。A.除留余数法B.折叠法C.平方取中法D.数字分析法19【单选题】(4分)除留余数法的基本思路是：设散列表的地址空间为0～m-1，元素的关键字值为k，用p去除k，将余数作为元素的散列地址，即h(k)=k%p，为了减少发生冲突的可能性，一般取p为（）。A.小于或等于m的最大素数B.mC.小于或等于m的最大合数D.大于m的最小素数20【单选题】(4分)解决散列法中出现的冲突问题常采用的方法是（）。A.数字分析法、除留余数法、线性探测法B.线性探测法、二次探测散列法、链地址法C.数字分析法、线性探测法、双散列法D.数字分析法、除留余数法、平方取中法21【单选题】(4分)在用开放定址法构造出的散列表中，散列到同一个地址而引起的“二次聚集”问题是由于（）引起的。A.同义词之间发生冲突B.非同义词之间发生冲突C.散列表“溢出”D.同义词之间或非同义词之间发生冲突22【单选题】(4分)散列表的平均查找长度（）。A.与处理冲突方法无关而与表的长度有关B.与处理冲突方法有关且与表的长度有关C.与处理冲突方法有关而与表的长度无关D.与处理冲突方法无关且与表的长度无关23【判断题】(4分)在由n个元素组成的有序表上进行折半查找时，对任一个元素进行查找的长度都不会大于。A.错B.对24【判断题】(4分)对于两棵具有相同关键码集合而形状不同的二叉查找树，按中序遍历它们得到的序列的各元素的顺序是一样的。A.对B.错25【判断题】(4分)在一棵AVL树中删除一个结点后，失去平衡的结点多于一个。A.错B.对第九章测试1【单选题】(4分)每次从未排序的序列中取出一个元素与已排序的序列中的元素依次进行比较，然后把它插入到已排序序列中的适当位置，此种排序方法叫做（）排序。A.简单选择排序B.起泡排序C.二路归并排序D.直接插入排序2【单选题】(4分)对5个不同的数据元素进行直接插入排序，最多需要进行（）次比较。A.15B.25C.8D.103【单选题】(4分)有一种排序方法，如果最小的元素位于待排序序列的最后，则在最后一趟排序开始之前，所有元素都不在其最终位置上，这种排序方法是（）。A.直接插入排序B.简单选择排序C.快速排序D.起泡排序4【单选题】(4分)每次直接比较两个元素，若出现逆序排列时就交换它们的位置，此种排序方法叫做（）排序。A.选择排序B.冒泡排序C.堆排序D.基数排序5【单选题】(4分)每次从待排序序列中挑选出一个最小或最大元素，把它交换到该序列的最前端，此种排序方法叫做（）排序。A.简单选择排序B.直接插入排序C.起泡排序D.二路归并排序6【单选题】(4分)在内排序的过程中，通常需要对待排序元素序列的关键字做多趟扫描。采用不同的排序方法将产生不同的排序中间结果，设要将序列{tang,deng,an,wan,shi,bai,fang,li}中的关键字按升序排列，则（）是冒泡排序一趟扫描的结果。A.deng,tang,an,wan,bai,shi,fang,liB.deng,tang,an,wan,bai,shi,li,fangC.an,deng,bai,li,shi,tang,fang,wanD.deng,an,tang,shi,bai,fang,li,wan7【单选题】(4分)在内排序的过程中，通常需要对待排序元素序列的关键字做多趟扫描。采用不同的排序方法将产生不同的排序中间结果，设要将集合{tang,deng,an,wan,shi,bai,fang,li}中的关键字按升序排列，则（）是初始步长为4的希尔排序一趟扫描的结果。A.an,bai,deng,fang,li,shi,tang,wanB.li,deng,an,shi,bai,fang,tang,wanC.shi,bai,an,li,tang,deng,fang,wanD.an,tang,deng,wan,shi,bai,fang,li8【单选题】(4分)在内排序的过程中，通常需要对待排序元素序列的关键字做多趟扫描。采用不同的排序方法将产生不同的排序中间结果，设要将集合{tang,deng,an,wan,shi,bai,fang,li}中的关键字按升序排列，则（）是以第一个元素为分界元素的快速排序一趟扫描的结果。A.shi,bai,an,li,tang,deng,fang,wanB.deng,tang,an,wan,bai,shi,fang,liC.deng,an,tang,shi,bai,fang,li,wanD.li,deng,an,shi,bai,fang,tang,wan9【单选题】(4分)一个元素序列的关键字为{46,79,56,38,40,84}，采用快速排序（以位于最左位置的元素为基准）得到的第一次划分结果为（）。A.{38,46,56,79,40,84}B.{38,79,56,46,40,84}C.{38,46,79,56,40,84}D.{40,38,46,79,56,84}10【单选题】(4分)在快速排序中，要使最坏情况下的空间复杂度为O(log2n)，要对快速排序做（）修改。A.采用链表排序B.划分轴点为三者取中C.先排小子区间D.先排大子区间11【单选题】(4分)在内排序的过程中，通常需要对待排序元素序列的关键字做多趟扫描。采用不同的排序方法将产生不同的排序中间结果，设要将集合{tang,deng,an,wan,shi,bai,fang,li}中的关键字按升序排列，则（）是大根堆排序初始建堆的结果。A.an,bai,deng,fang,li,shi,tang,wanB.deng,tang,an,wan,bai,shi,fang,liC.an,tang,deng,wan,shi,bai,fang