数据结构（山东联盟-青岛大学）知到智慧树章节测试课后答案2024年秋青岛大学

数据结构（山东联盟-青岛大学）知到智慧树章节测试课后答案2024年秋青岛大学第一章单元测试

在Data_Structure=(D，R)中，D是（）的有限集合。

A:数据元素B:数据操作C:算法D:数据对象

答案:数据元素计算机所处理的数据一般具有某种关系，这是指（）。

A:元素内数据项与数据项之间存在的某种关系B:数据文件内记录与记录之间存在的某种关系C:数据与数据之间存在的某种关系D:数据元素与数据元素之间存在的某种关系

答案:数据元素与数据元素之间存在的某种关系算法的时间复杂度与（

）有关。

A:编译后执行程序的质量B:问题规模

C:计算机硬件的运行速度D:源程序的长度

答案:问题规模

以下关于数据结构的说法正确的是（

）。

A:数据结构的存储结构独立于该数据结构的逻辑结构B:数据结构的逻辑结构唯一地决定了该数据结构的存储结构C:数据结构的逻辑结构独立于其存储结构D:数据结构仅由其逻辑结构和存储结构决定

答案:数据结构的逻辑结构独立于其存储结构某算法的时间复杂度是O(n2)，表明该算法（）。

A:问题规模与n^2成正比B:执行时间与n^2成正比C:问题规模是n^2D:执行时间等于n^2

答案:执行时间与n^2成正比从逻辑上可将数据结构分为（）。

A:线性结构和非线性结构B:内部结构和外部结构C:紧凑结构和非紧凑结构D:动态结构和静态结构

答案:线性结构和非线性结构数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的。

A:错B:对

答案:对数据的物理结构是指数据结构在计算机内的实际存储形式。

A:错B:对

答案:对每种数据结构都具备三种基本运算：插入、删除和查找。

A:错B:对

答案:错算法的时间效率和空间效率往往相互冲突，有时很难两全其美。

A:对B:错

答案:对

第二章单元测试

线性表是一个（）。

A:数据元素的有限序列，数据元素的类型可以不同B:数据元素的有限序列，元素不可以是线性表C:数据元素的无限序列，元素个数可以是零个，也可以有多个D:数据元素的有限序列，数据元素还可以是线性表

答案:数据元素的有限序列，元素不可以是线性表以下关于线性表的说法中正确的是（）。

A:线性表中的元素必须按照从小到大或从大到小的次序排列B:线性表中所有的元素都可以直接（或随机）存取C:线性表中至少有一个元素D:除第一个元素和最后一个元素外，其他每个元素有且仅有一个直接前趋元素和一个直接后继元素

答案:除第一个元素和最后一个元素外，其他每个元素有且仅有一个直接前趋元素和一个直接后继元素以下关于线性表的说法中正确的是（)。

A:每个元素最多有一个直接前趋和一个直接后继B:每个元素最少有一个直接前趋和一个直接后继C:每个元素有且仅有一个直接前趋，有且仅有一个直接后继D:线性表中的元素还可以是线性表，但数据类型必须相同

答案:每个元素最多有一个直接前趋和一个直接后继如果线性表中的表元素既没有直接前趋，也没有直接后继，则该线性表中应有（）个表元素。

A:2B:0

C:1D:n

答案:1在线性表中的每一个表元素都是数据对象，它们是不可再分的（）。

A:数据记录B:数据元素C:数据字段D:数据项

答案:数据元素顺序表是线性表的（）表示。

A:连续B:顺序存取C:有序D:顺序存储

答案:顺序存储以下关于顺序表的说法中正确的是（）。

A:在顺序表中每一表元素的数据类型还可以是顺序表B:顺序表利用一维数组表示，因此顺序表与一维数组在结构上一致，它们可以通用C:在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻D:顺序表和一维数组一样，都可以按下标随机（或直接）访问，顺序表还可以从某一指定元素开始，向前或向后逐个元素顺序访问

答案:顺序表和一维数组一样，都可以按下标随机（或直接）访问，顺序表还可以从某一指定元素开始，向前或向后逐个元素顺序访问顺序表的优点是（）。

A:适用于各种逻辑结构的存储表示B:插入操作的时间效率高C:删除操作的时间效率高D:存储密度（存储利用率）高

答案:存储密度（存储利用率）高以下关于单链表的叙述中错误的是（）。

A:结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构B:可以通过计算直接确定第i个结点的存储地址C:插入、删除运算操作方便，不必移动结点D:逻辑上相邻的结点物理上不必相邻

答案:可以通过计算直接确定第i个结点的存储地址以下关于单链表的叙述中错误的是（）。

A:单链表中各结点地址不可能连续B:结点的数据域用于存储线性表的一个数据元素C:所有数据通过指针的链接而组织成单链表D:结点的指针域用于存放一个指针，指示本结点所存储数据元素的直接后继元素所在结点的地址

答案:单链表中各结点地址不可能连续在单链表上实施插入和删除操作（）。

A:既需移动结点，又需改变结点指针B:不需移动结点，只需改变结点指针C:不需移动结点，不需改变结点指针D:只需移动结点，不需改变结点指针

答案:不需移动结点，只需改变结点指针在单链表最终增加头结点的目的是（)。

A:方便对链表的统一命名B:方便插入、删除等运算的实现C:使得链表遍历有一个终结结点D:标识链表首元结点的位置

答案:方便插入、删除等运算的实现已知单链表中结点*q是结点*p的直接前趋，若在*q与*p之间插入结点*s,则应执行以下（）操作。

A:q->next=s;s->next=p;B:s->next=p->next;p->next=s;C:p->next=s->next;s->next=p;D:p->next=s;s->next=q;

答案:q->next=s;s->next=p;已知单链表中结点*p不是链尾结点，若在*p之后插入结点*s，则应执行以下（）操作。

A:s->next=p->next;p=s;B:s->next=p;p->next=s；C:s->next=p->next;p->next=s;D:p->next=s；s->next=p;

答案:s->next=p->next;p->next=s;顺序表中元素的逻辑顺序和物理顺序总是一致的。

A:对B:错

答案:对在单链表中插入新元素时，必须先找到要插入位置的前一个结点。

A:错B:对

答案:对顺序表是静态存储结构，而链表是动态存储结构。

A:错B:对

答案:错循环单链表可以仅在链表尾部设置链尾指针。

A:错B:对

答案:对在为顺序表分配连续的存储空间时，必须预估该空间的最大容量。但想估计得准确很不容易，而为链表分配存储空间则不会为此烦恼。

A:对B:错

答案:对在顺序表中插入和删除时效率太低，因此它不如链表好。

A:对B:错

答案:错

第三章单元测试

栈的插入和删除操作在（

）进行。

A:栈顶B:栈底C:指定位置D:任意位置

答案:栈顶对一个初始为空的栈s执行操作Push(s,5),Push(s,2),Push(s,4),Pop(s,x),getTop(s,x)后，x的值应是（

）。

A:4B:0C:2D:5

答案:2用S表示进栈操作，用X表示出栈操作，若元素的进栈顺序是1234，为了得到1342出栈顺序，相应的S和X的操作序列为（

）。

A:SSSXXSXXB:SXSSXXSXC:SXSXSSXXD:SXSSXSXX

答案:SXSSXSXX假设一个栈的输入序列是1,2,3,4，则不可能得到的输出序列是（

）。

A:4,1,2,3B:1,2,3,4C:4,3,2,1D:1,3,4,2

答案:4,1,2,3已知一个栈的进栈序列为1,2,3,…,n，其输出序列的第一个元素是i，则第j个出栈元素是（

）。

A:不确定B:n-iC:j-i+1D:j-i

答案:不确定已知一个栈的进栈序列为1,2,3,…,n，其输出序列是p1,p2,p3,…,pn。若p1=n，则pi的值是（

）。

A:iB:不确定C:n-i+1D:n-i

答案:n-i+1已知一个栈的进栈序列为1,2,3,…,n，其输出序列是p1,p2,p3,…,pn。若p1=3，则p2的值（

）。

A:可能是1B:一定是2C:可能是2D:一定是1

答案:可能是2已知一个栈的进栈序列为p1,p2,p3,…,pn，其输出序列是1,2,3,…,n。若p3=1，则p1的值（

）。

A:一定是2B:一定是3C:可能是2D:不可能是2

答案:不可能是2设一个循环队列Q[maxSize]的队头指针为front，队尾指针为rear，队列最大容量为maxSize，除此之外该队列再没有其他数据成员，则该队列的队满条件是（

）。

A:Q.front==Q.rearB:Q.front==(Q.rear+1)%maxSizeC:Q.front+Q.rear>=maxSizeD:Q.rear==(Q.front+1)%maxSize

答案:Q.front==(Q.rear+1)%maxSize设循环队列的存储容量为maxSize，队头和队尾指针分别为front和rear。若有一个循环队列Q，可应用下列语句（

）计算队列元素个数？

A:Q.rear-Q.frontB:(Q.rear-Q.front)%maxSize+1C:Q.rear-Q.front+1D:(Q.rear-Q.front+maxSize)%maxSize

答案:(Q.rear-Q.front+maxSize)%maxSize一个队列的进队顺序是1,2,3,4，则该队列可能的输出序列是（

）。

A:1,4,2,3B:1,3,2,4C:4,3,2,1D:1,2,3,4

答案:1,2,3,4对于链式队列，在执行插入操作时（

）。

A:头、尾指针可能都要修改B:头、尾指针都要修改

C:仅修改尾指针D:仅修改头指针

答案:头、尾指针可能都要修改最适合用作链式队列的链表是（

）。

A:只带队头指针的循环单链表B:只带队头指针的非循环单链表C:带有队头指针和队尾指针的非循环单链表D:带有队头指针和队尾指针的循环单链表

答案:带有队头指针和队尾指针的非循环单链表最不适合用作链式队列的链表是（

）。

A:带有队头指针的双向循环链表B:只带队尾指针的循环单链表C:只带队尾指针的双向循环链表D:带有队头指针的双向非循环链表

答案:带有队头指针的双向非循环链表设一个链式队列q的队头指针和队尾指针分别为front和rear，则判断队列空的条件是（

）。

A:q.front==NULLB:q.front==q.rearC:q.rear==NULLD:q.front!=NULL

答案:q.front==NULL将递归算法转换成非递归算法时，通常要借助的数据结构是（

）。

A:栈B:树C:线性表D:队列

答案:栈栈与一般线性表的区别在于（）。

A:数据元素的个数不同B:运算是否受限制C:逻辑数据不同D:数据元素的类型不同

答案:运算是否受限制栈和队列都是顺序存取结构。

A:错B:对

答案:对对循环队列初始化时·要求队头指针与队尾指针指向同一个位置，不论队列存储中什么位置都可以。

A:错B:对

答案:对栈是实现过程和函数等子程序调用所必需的结构。

A:错B:对

答案:对

第四章单元测试

字符串可定义为n(n≥0)个字符的有限（

），其中，n是字符串的长度，表明字符串中字符的个数。

A:数列B:集合C:聚合D:序列

答案:序列串是一种特殊的线性表，其特殊性体现在（

）。

A:可以顺序存储B:数据元素可以是多个字符C:可以链接存储D:数据元素是一个字符

答案:数据元素是一个字符有n个字符的字符串的非空子串个数最多有（

）。

A:n(n-1)/2B:n-1C:n(n+1)/2D:n

答案:n(n+1)/2两个字符串相等的条件是（

）。

A:两个串的长度相等，并且两个串包含的字符相同B:两个串的长度相等C:两个串的长度相等，并且对应位置上的字符相同D:两个串包含的字符相等

答案:两个串的长度相等，并且对应位置上的字符相同设有两个串：T和P，求P在T中首次出现的位置的运算叫做（

）。

A:串替换B:模式匹配C:求子串D:串连接

答案:模式匹配在以下关于串的说法中正确的是（）。

A:用块链存储表示实现的串的结点大小为4,说明每个结点可存储4个字符B:空串是由空格组成的串C:子串是从串中抽取出若干字符组成的串D:串长度是指串中不同字符的个数

答案:用块链存储表示实现的串的结点大小为4,说明每个结点可存储4个字符设有两个串T和P，求P在T中首次出现的位置的运算叫做（）。

A:求子串B:串连接C:串替换D:模式匹配

答案:模式匹配设T="aaaaaacaaaca”，P=“aaac”，使用BF算法的模式匹配过程需要执行的趟数为（）。

A:4B:2C:3D:7

答案:4应用KMP算法进行模式匹配时，next函数值序列的产生仅与模式串有关。

A:对B:错

答案:对KMP算法的特点是在模式匹配时指示目标串当前比对位置的指针不会回退。

A:对B:错

答案:对

第五章单元测试

对稀疏矩阵进行压缩存储的目的是（

）。

A:便于输入和输出B:节省存储空间C:降低运算的时间复杂度D:便于进行矩阵运算

答案:节省存储空间一个稀疏矩阵采用压缩后，和直接采用二维数组存储相比会失去（

）特性。

A:其余选项都不对B:顺序存储C:输入输出D:随机存取

答案:随机存取稀疏矩阵常用的压缩存储方法有（

）。

A:三元组和十字链表

B:散列表和十字链表C:二维数组

D:三元组和散列表

答案:三元组和十字链表

以下关于一维数组与顺序表不同之处的说法中错误的是（）。

A:前者的元素数据类型相同，后者的元素数据类型可以不相同B:前者的长度不变，后者的长度可变C:前者既可以是逻辑结构也可以是存储结构，后者是线性表的存储结构D:前者的元素可以不连续存放，后者的元素必须相继存放

答案:前者的元素数据类型相同，后者的元素数据类型可以不相同将一个n*n的对称矩阵A的对角线和对角线以上的部分按列优先存放于一个一维数组中，那么A有(

)个矩阵元素未被存于sa中。

A:n(n-1)B:n^2/2

C:n(n-1)/2D:n(n+1)/2

答案:n(n-1)/2设一维数组A[n]中每个元素占用6个存储单元，若A[5]的存储地址从100开始，则该数组的首地址是（)。

A:64B:76

C:30D:95

答案:64在二维数组A[9][10]中，每个数组元素占用3个存储单元，从首地址SA开始按行优先连续存放。在这种情况下，元素A[8][5]的起始地址为（

）。

A:SA+255B:SA+144C:SA+222D:SA+141

答案:SA+255设一个稀疏矩阵有1000行850列，其中有1000个非零元素。设每个整数占2字节，数据占4字节。则用三元组表存储该矩阵时所需字节数是（）。

A:8000

B:1000

C:18000D:4000

答案:8000

二维数组是其数组元素为线性表的线性表。

A:对B:错

答案:错用一维数组存储特殊矩阵，可以简化对矩阵的存取操作。

A:对B:错

答案:错

第六章单元测试

树最合适用来表示（

）。

A:有序数据元素B:元素之间具有分支层次关系的数据C:无序数据元素D:元素之间无联系的数据

答案:元素之间具有分支层次关系的数据一棵有n个结点的树的所有结点的度数之和为（

）。

A:n-1B:nC:2nD:n+1

答案:n-1设树中某结点不是根结点，则离它最近的祖先结点是（

）。

A:父结点的父结点B:根结点C:父结点D:该结点本身

答案:父结点在二叉树中某一结点的深度为3,高度为4,该树的髙度至少为（

）。

A:7B:5C:6D:8

答案:6设一棵高度为h的满二叉树有n个结点，其中有m个叶结点，则（

）。

A:n=h+mB:h+m=2nC:n=2^h-1D:m=h-1

答案:n=2^h-1具有33个结点的完全二叉树，有（

）个度为1的结点。

A:1B:12C:0D:16

答案:0一颗有124个叶子结点的完全二叉树最多有（

）个结点。

A:249B:247C:250D:248

答案:248一颗有129个叶结点的完全二叉树最少有（

）个结点。

A:255B:257C:254D:258

答案:257如果二叉树T2是由一棵树T1转换而来的二叉树，那么T1中结点的先根序列对应T2的（

）序列。

A:中序遍历

B:先序遍历

C:层次遍历D:后序遍历

答案:先序遍历

如果二叉树T2是由一棵树T1转换而来的二叉树，那么T1中结点的后根序列对应T2的（

）序列。

A:层次遍历B:后序遍历

C:中序遍历

D:先序遍历

答案:中序遍历

一个深度为k且只有k个结点的二叉树，按照完全二叉树顺序存储的方式存放于一个一维数组A[n]中，那么n应至少是（）。

A:2^kB:2^k-1C:2k+1D:2k

答案:2^k-1二叉树的叶子结点在前序、中序和后序遍历过程中的相对顺序（

）。

A:无法确定B:其余选项都不对C:发生改变D:不发生改变

答案:不发生改变设n、m为一棵二叉树上的两个结点，在中序遍历序列中，n在m前的条件是（）。

A:n在m左方B:n是m的子孙C:n在m右方D:n是m的祖先

答案:n在m左方在一棵二叉树中有两个结点n和m。在该二叉树的前序遍历序列中n在m之前，而在其后序遍历序列中n在m之后，则n和m的关系是（）。

A:n是m的左兄弟B:n是m的右兄弟C:n是m的子孙D:n是m的祖先

答案:n是m的祖先前序序列与中序序列正好相反的非空二叉树是（）。

A:满二叉树B:右单支树C:左单支树D:完全二叉树

答案:左单支树在中序线索二叉树中，指针t所指结点的左子树为空的充要条件是（）。

A:t->lchild==NULLB:其余选项都不对C:t->ltag==1且t->lchild==NULLD:t->ltag==1

答案:t->ltag==1且t->lchild==NULL设森林F对应的二叉树为A，它有m个结点。A的根为p，p的右子树中结点个数为n，则森林F中第一棵树的结点个数是（）。

A:m-n-1

B:m-nC:无法确定D:n+1

答案:m-n设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶结点，则B中右指针域为空的结点有（）个。

A:n+1B:nC:n-1

D:n+2

答案:n+1用n个权重构造出来的Huffman树共有（）个结点。

A:2n+1B:n+1C:2n-1

D:2n

答案:2n-1

设T是Huffman树，具有5个叶结点，树T的高度最高可以是（）。

A:5B:6C:3D:4

答案:5

第七章单元测试

在无向图中定义顶点的度为与它相关联的（

）的数目。

A:权B:边C:顶点D:权值

答案:边具有n个顶点且每一对不同的顶点之间都有一条边的无向图被称为（）。

A:无向树图B:无向强连通图C:无向完全图D:无向连通图

答案:无向完全图一个有n个顶点的无向图最多有（

）边。

A:n(n-1)B:n(n-1)/2

C:nD:2n

答案:n(n-1)/2

具有6个顶点的无向图至少应有（

）条边才能确保是一个连通图。

A:7

B:6

C:5

D:8

答案:5

图的简单路径是指（

）不重复的路径。

A:顶点

B:权值C:边与顶点均

D:边

答案:顶点

在一个具有n个顶点的有向图中，若所有顶点的出度之和为s，则所有顶点的入度之和为（

）。

A:s+1

B:n

C:s-1

D:s

答案:s

在下列有关图的说法中正确的是（）。

A:在图结构中，顶点可以没有任何前驱和后继B:具有n个顶点的无向图最多有n(n-1)条边，最少有n-1条边C:在有向图中，各顶点的入度之和等于各顶点的出度之和D:在无向图中，边的条数是结点度数之和

答案:在有向图中，各顶点的入度之和等于各顶点的出度之和对于一个具有n个顶点和e条边的无向图，若采用邻接矩阵表示，则该矩阵中的非零元素个数是（

）。

A:n^2

B:eC:2eD:e^2

答案:2e无向图的邻接矩阵是一个（

）。

A:上三角矩阵B:对角矩阵C:对称矩阵D:零矩阵

答案:对称矩阵有n个顶点和e条边的无向图采用邻接矩阵存储，零元素的个数为（

）。

A:n^2-2e

B:eC:2eD:n^2-e

答案:n^2-2e

从邻接矩阵可知，该有向图共有（

）条有向边。

A:3

B:9C:4

D:2

答案:4

带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中（

）。

A:第i列非∞且非0的元素个数B:第i行非∞的元素之和C:第i行非∞且非0的元素个数D:第i列非∞的元素之和

答案:第i列非∞且非0的元素个数下列说法中正确的是（）。

A:一个图的邻接矩阵表示是唯一的，邻接表表示不唯一B:一个图的邻接矩阵表示是唯一的，邻接表表示也唯一C:一个图的邻接矩阵表示不唯一，邻接表表示唯一D:一个图的邻接矩阵表示不唯一，邻接表表示也不唯一

答案:一个图的邻接矩阵表示是唯一的，邻接表表示不唯一用邻接表存储图所用的空间大小（

）。

A:只与图的边数有关系B:只与图的顶点数有关C:与边数的平方有关D:与图的顶点数和边数都有关

答案:与图的顶点数和边数都有关在下列有关图的存储结构的说法中错误的是（

）。

A:邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用B:用邻接矩阵存储一个图时所占用的存储空间大小与图中的顶点个数有关，而与图的边数无关C:邻接矩阵只适用于稠密图（边数接近于顶点数的平方），邻接表适用于稀疏图（边数远小于顶点数的平方）D:对同一个有向图来说，邻接表中边结点数与逆邻接表中边结点数相等

答案:邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用设图有n个顶点和e条边，采用邻接矩阵时，遍历图时的顶点所需时间为（）。

A:O(n)

B:O(ne)C:O(e)D:O(n^2)

答案:O(n^2)

设图有n个顶点和e条边，采用邻接表时，遍历图的顶点所需时间为（）。

A:O(e)B:O(n^2)

C:O(ne)D:O(n+e)

答案:O(n+e)如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（）。

A:有回路B:强连通图C:连通图D:—棵树

答案:连通图如果一个连通网络G中各边权值互不相同，权值最小的边一定包含在G的(

)生成树中。

A:广度优先B:深度优先C:任何D:最小

答案:最小任何一个连通图的最小生成树（）。

A:一定有多棵B:可能不存在C:有一棵或多棵D:只有一棵

答案:有一棵或多棵Dijkstra算法是（）来求出图中从某顶点到其余顶点最短路径的。

A:通过广度优先遍历求出图的某顶点到其余顶点的最短路径B:按长度递增的顺序求出图的某顶点到其余顶点的最短路径C:按长度递减的顺序求出图的某项点到其余顶点的最短路径D:通过深度优先遍历求出图的某顶点到其余顶点的所有路径

答案:按长度递增的顺序求出图的某顶点到其余顶点的最短路径已知一个带权有向图如图所示，依据Dijkstra算法求从顶点1到其余各顶点的最短路径的顺序应是（

）。

A:23546

B:25346

C:54632

D:25463

答案:25346

如果一个有向图具有拓扑有序序列，并且顶点按拓扑有序序列编号，那么它的邻接矩阵必定为（）。

A:三对角矩阵B:下三角矩阵C:对称矩阵D:上三角矩阵

答案:上三角矩阵若一个有向图中的部分顶点不能通过拓扑排序排到一个拓扑有序序列里，则可断定该有向图是一个（）。

A:含有多个入度为0的顶点的图B:DAG图C:含有顶点数大于1的强连通分量D:强连通图

答案:含有顶点数大于1的强连通分量在如图所示的AOE网中，关键路径长度为（

）。

A:13B:23C:16D:22

答案:23

第八章单元测试

顺序查找算法适用于（

）结构。

A:连通图B:线性表

C:查找网

D:查找树

答案:线性表

在顺序存储的线性表R[30]上进行顺序查找的平均查找长度为（

）。

A:15B:15.5

C:16

D:20

答案:15.5

对长度为10的顺序表进行查找，若查找前面5个元素的概率相同，均为1/8，查找后面5个元素的概率相同，均为3/40，则查找到表中任一元素的平均查找长度为（）。

A:19/4

B:39/8

C:5D:5.5

答案:39/8

如果有5个关键字{a,b,c,d,e}放在顺序表中，它们的查找概率分别为{0.35,0.25，0.20,0.15,0.05}，按照（

）顺序存放可使平均查找长度达到最小。

A:a,b,c,d,eB:d,a,b,c,eC:e,d,c,b,aD:a,c,e,d,b

答案:a,b,c,d,e对长度为n的有序单链表，若查找每个元素的概率相等，则顺序查找表中任一元素的查找成功的平均查找长度为（

）。

A:(n-1)/2

B:(n+1)/2

C:n/4D:n/2

答案:(n+1)/2

对线性表进行折半查找时，要求线性表必须（

）。

A:以链接方式存储，且结点按关键字有序排序B:以链接方式存储C:以顺序方式存储D:以顺序方式存储，且结点按关键字有序排序

答案:以顺序方式存储，且结点按关键字有序排序采用折半查找方式查找一个长度为n的有序顺序表时，其平均查找长度为（）。

A:O(n^2)B:O(log2n)C:O(nlog2n)D:O(n)

答案:O(log2n)采用折半查找法查找长度为n的有序顺序表，查找每个元素的数据比较次数（

）对应二叉判定树的高度（设高度≥2）。

A:等于B:小于等于

C:小于D:大于

答案:小于等于

折半查找和二叉排序树的时间性能（

）。

A:有时不相同

B:不定C:相同D:完全不同

答案:有时不相同

在常用的描述二叉排序树的存储结构中，关键字值最大的结点（

）。

A:左指针一定为空

B:左右指针均不为空C:左右指针均为空

D:右指针一定为空

答案:右指针一定为空m阶B-树是一棵（

）。

A:m叉高度平衡查找树B:m-1叉高度平衡查找树C:m+1叉高度平衡查找树D:m叉查找树

答案:m叉高度平衡查找树下列关于m阶B-树的说法中错误的是（

）。

A:根结点中的数据是有序的B:根结点至多有m棵子树C:非失败结点至少有m/2（m为偶数）或m/2+1（m为奇数）棵子树D:所有叶结点都在同一层次上

答案:非失败结点至少有m/2（m为偶数）或m/2+1（m为奇数）棵子树下面关于B-树和B+树的叙述中错误的是（

）。

A:B-树和B+树都能有效地支持顺序查找B:B-树和B+树都能有效地支持随机查找C:B-树和B+树都是平衡的多叉查找树D:B-树和B+树都可用于文件的索引结构

答案:B-树和B+树都能有效地支持顺序查找散列法存储的基本思想是根据（

）来决定元素的存储地址。

A:关键字值

B:非码属性C:元素个数

D:元素的序号

答案:关键字值

设一个散列表中有n个元素，用散列法进行查找，理想情况下的平均查找长度是（

）。

A:O(log2n)

B:O(n)

C:O(1)

D:O(n^2)

答案:O(1)

使用散列函数将元素的关键字值映射为散列地址时，常会产生冲突。此时的冲突是指（

）。

A:两个元素的关键字值不同，而非关键字值相同B:不同关键字值对应到相同的存储地址C:装填因子过大，数据元素过多D:两个元素具有相同的序号

答案:不同关键字值对应到相同的存储地址以下关于散列函数选择原则的叙述中，不正确的是（

）。

A:散列函数计算出来的地址应能均匀分布在整个地址空间中B:装填因子必须限制在0.8以下C:散列函数应是简单的，能在较短的时间内计算出结果D:散列函数的定义域应包括全部关键字值,值域必须在表范围之内

答案:装填因子必须限制在0.8以下计算出的地址分布最均匀的散列函数是（

）。

A:数字分析法

B:折叠法C:除留余数法

D:平方取中法

答案:除留余数法

除留余数法的基本思路是：设散列表的地址空间为0～m-1，元素的关键字值为k，用p去除k，将余数作为元素的散列地址，即h(k)=k%p，为了减少发生冲突的可能性，一般取p为（

）。

A:大于m的最小素数B:mC:小于或等于m的最大合数D:小于或等于m的最大素数

答案:小于或等于m的最大素数解决散列法中出现的冲突问题常采用的方法是（

）。

A:线性探测法、二次探测散列法、链地址法B:数字分析法、线性探测法、双散列法C:数字分析法、除留余数法、平方取中法D:数字分析法、除留余数法、线性探测法

答案:线性探测法、二次探测散列法、链地址法在用开放定址法构造出的散列表中，散列到同一个地址而引起的“二次聚集”问题是由于（

）引起的。

A:非同义词之间发生冲突B:散列表“溢出”C:同义词之间或非同义词之间发生冲突D:同义词之间发生冲突

答案:同义词之间或非同义词之间发生冲突散列表的平均查找长度（

）。

A:与处理冲突方法无关而与表的长度有关B:与处理冲突方法有关且与表的长度有关C:与处理冲突方法有关而与表的长度无关D:与处理冲突方法无关且与表的长度无关

答案:与处理冲突方法有关而与表的长度无关在由n个元素组成的有序表上进行折半查找时，对任一个元素进行查找的长度都不会大于。

A:错B:对

答案:对对于两棵具有相同关键码集合而形状不同的二叉查找树，按中序遍历它们得到的序列的各元素的顺序是一样的。

A:错B:对

答案:对在一棵AVL树中删除一个结点后，失去平衡的结点多于一个。

A:对B:错

答案:错

第九章单元测试

每次从未排序的序列中取出一个元素与已排序的序列中的元素依次进行比较，然后把它插入到已排序序列中的适当位置，此种排序方法叫做（

）排序。

A:二路归并排序B:直接插入排序

C:简单选择排序

D:起泡排序

答案:直接插入排序

对5个不同的数据元素进行直接插入排序，最多需要进行（

）次比较。

A:25

B:8C:10

D:15

答案:10

有一种排序方法，如果最小的元素位于待排序序列的最后，则在最后一趟排序开始之前，所有元素都不在其最终位置上，这种排序方法是（

）。

A:简单选择排序

B:快速排序C:直接插入排序

D:起泡排序

答案:直接插入排序

每次直接比较两个元素，若出现逆序排列时就交换它们的位置，此种排序方法叫做（）排序。

A:基数排序B:冒泡排序

C:堆排序

D:选择排序

答案:冒泡排序

每次从待排序序列中挑选出一个最小或最大元素，把它交换到该序列的最前端，此种排序方法叫做（

）排序。

A:二路归并排序B:直接插入排序

C:简单选择排序

D:起泡排序

答案:简单选择排序

在内排序的过程中，通常需要对待排序元素序列的关键字做多趟扫描。采用不同的排序方法将产生不同的排序中间结果，设要将序列{tang,deng,an,wan,shi,bai,fang,li}中的关键字按升序排列，则（

）是冒泡排序一趟扫描的结果。

A:deng,tang,an,wan,bai,shi,fang,liB:an,deng,bai,li,shi,tang,fang,wanC:deng,an,tang,shi,bai,fang,li,wanD:deng,tang,an,wan,bai,shi,li,fang

答案:deng,an,tang,shi,bai,fang,li,wan在内排序的过程中，通常需要对待排序元素序列的关键字做多趟扫描。采用不同的排序方法将产生不同的排序中间结果，设要将集合{tang,deng,an,wan,shi,bai,fang,li}中的关键字按升序排列，则（

）是初始步长为4的希尔排序一趟扫描的结果。

A:shi,bai,an,li,tang,deng,fang,wanB:li,deng,an,shi,bai,fang,tang,wanC:an,tang,deng,wan,shi,bai,fang,liD:an,bai,deng,fang,li,shi,tang,wan

答案:shi,bai,an,li,tang,deng,fang,wan在内排序的过程中，通常需要对待排序元素序列的关键字做多趟扫描。采用不同的排序方法将产生不同的排序中间结果，设要将集合{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:li,deng,an,shi,bai,fang,tang,wanD:deng,an,tang,shi,bai,fang,li,wan

答案:li,deng,an,shi,bai,fang,tang,wan一个元素序列的关键字为{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}

答案:{40,38,46,79,56,84}在快速排序中，要使最坏情况下的空间复杂度为O(log2n)，要对快速排序做（

）修改。

A:采用链表排序B:划分轴点为三者取中

C:先排小子区间

D:先排大子区间

答案:划分轴点为三者取中

在内排序的过程中，通常需要对待排序元素序列的关键字做多趟扫描。采用不同的排序方法将产生不同的排序中间结果，设要将集合{tang,deng,an,wan,shi,bai,fang,li}中的关键字按升序排列，则（

）是大根堆排序初始建堆的结果。

A:deng,tang,an,wan,bai,shi,fang,liB:wan,tang,fang,li,shi,bai,an,dengC:an,ta