数据结构知到智慧树章节测试课后答案2024年秋海南师范大学

数据结构知到智慧树章节测试课后答案2024年秋海南师范大学第一章单元测试

从一个二维数组b[m][n]中找出最大值元素的时间复杂度为

A:mB:nC:m*nD:m+n

答案:m*n在以下时间复杂度的数量级中，数量级最大的是

A:B:C:D:

答案:下面程序段的时间复杂度为____________。for(inti=0;i<m;i++)

for(intj=0;j<n;j++)

a[i][j]=i*j;

A:O(m*n)B:O(n2)C:O(m2)D:O(m+n)

答案:O(m*n)执行下面程序段时，执行S语句的次数为（

）。for(inti=1;i<=n;i++)

for(intj=1;j<=i;j++)

S;

A:n(n+1)B:n2C:n(n+1)/2D:n2/2

答案:n(n+1)/2线性结构是数据元素之间存在一种：（

）。

A:多对一关系B:多对多关系C:一对多关系D:一对一关系

答案:一对一关系数据结构中，与所使用的计算机无关的是数据的（

）结构。

A:物理B:物理和存储C:逻辑D:存储

答案:逻辑算法分析的目的是：（

）。

A:分析算法的易懂性和文档性B:研究算法中的输入和输出的关系C:分析算法的效率以求改进D:找出数据结构的合理性

答案:分析算法的效率以求改进算法分析的两个主要方面是：（

）。

A:数据复杂性和程序复杂性B:空间复杂性和时间复杂性C:正确性和简明性D:可读性和文档性

答案:空间复杂性和时间复杂性计算机算法指的是：（

）。

A:解决问题的有限运算序列B:调度方法C:排序方法D:计算方法

答案:解决问题的有限运算序列计算机算法必须具备输入、输出和（

）等5个特性。

A:易读性、稳定性和安全性B:可行性、可移植性和可扩充性C:可行性、确定性和有穷性D:确定性、有穷性和稳定性

答案:可行性、确定性和有穷性一个算法的好坏可以通过复杂性、可读性、健壮性、高效性这四个方面进行评价。

A:对B:错

答案:错数据结构是一门研究算法的学科。

A:对B:错

答案:错数据结构中，数据的逻辑结构包括线性结构、图结构、树形结构、集合。

A:对B:错

答案:对线性表的逻辑顺序与存储顺序总是一致的。

A:错B:对

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

A:对B:错

答案:错线性结构中元素之间只存在多对多关系。

A:错B:对

答案:错在线性结构中，第一个结点没有前驱结点。

A:对B:错

答案:对在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。

A:对B:错

答案:对算法分析的目的是分析算法的效率以求改进。

A:对B:错

答案:对同一逻辑结构采用不同的存储方法，可以得到不同的存储结构。

A:错B:对

答案:对

第二章单元测试

在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：（

）

A:在第i个结点后插入一个新结点（1≤i≤n）B:删除第i个结点（1≤i≤n）C:访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）D:将n个结点从小到大排序

答案:访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（

）个元素。

A:63.5B:63C:7D:8

答案:63.5线性表若采用链式存储结构时，要求内存中可用存储单元的地址:（

）

A:一定是不连续的B:连续或不连续都可以C:必须是连续的D:部分地址必须是连续的

答案:连续或不连续都可以若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用_______存储方式最节省时间。

A:带头节点的双循环链表B:顺序表C:双链表D:单循环链表

答案:顺序表在一个以h为头结点的单循环链表中，使指针p指向链尾结点的条件是（

）。

A:p->next==h;B:p->next==h->nextC:p->next->next==hD:p->next==NULL

答案:p->next==h;链表是一种采用（

）存储结构存储的线性表

A:链式

B:顺序C:网状D:星式

答案:链式

单链表包括两个域：（

）。

A:数据域和指针域B:数据域和星式C:数据域和表位D:链式和数字

答案:数据域和指针域单链表可以用（

）来命名。

A:KB:LC:结点名D:头指针的名字

答案:头指针的名字单链表的插入操作其时间复杂度为（

）。

A:O（n2）B:O（1）C:O（n）D:O（n3）

答案:O（n）

顺序表的插入操作的时间复杂度为（

）。

A:O（n）B:O（n2）C:O（1）

D:O（n3）

答案:O（n）线性表的逻辑结构特性是一对多的。

A:对B:错

答案:错顺序表在进行插入和删除操作时不需要移动元素。

A:错B:对

答案:错对于链表是依靠指针来反映其线性逻辑关系的。

A:对B:错

答案:对在单链表的第一个结点之前是不允许附设结点的。

A:对B:错

答案:错在单链表中首元结点就是头结点。

A:错B:对

答案:错循环单链表的最大优点是从任一结点出发都可访问到链表中每一个元素。

A:错B:对

答案:对线性表采用链式存储，便于插入和删除操作。

A:对B:错

答案:对线性表采用顺序存储，必须占用一片连续的存储单元。

A:对B:错

答案:对单链表可以有多个指针域。

A:对B:错

答案:错顺序表的每个元素所占的存储单元是相等的。

A:错B:对

答案:对

第三章单元测试

栈的插入和删除操作在（

）

A:指定位置

B:栈顶

C:栈底

D:任意位置

答案:栈顶

五节车厢以编号a，b，c，d，e顺序进入铁路调度站（栈），可以得到（

）的编组

A:b，d，a，c，e

B:c，d，e，a，b

C:c，e，d，b，a

D:a，c，e，b，d

答案:c，e，d，b，a

判定一个顺序栈S（栈空间大小为n）为空的条件是（）

A:S->top==n

B:S->top!=0

C:S->top==0

D:S->top!=n

答案:S->top==0

在一个链队列中，front和rear分别为头指针和尾指针，则插入一个结点s的操作为（

）

A:s->next=front;front=s;

B:s->next=rear;rear=s

C:front=front->next

D:rear->next=s;rear=s;

答案:rear->next=s;rear=s;

一个队列的入队序列是1，2，3，4，则队列的出队序列是（

）

A:1，4，3，2

B:4，3，2，1

C:1，2，3，4

D:3，4，1，2

答案:4，3，2，1

依次在初始为空的队列中插入元素a,b,c,d以后，紧接着做了两次删除操作，此时的队头元素是（）

A:a

B:cC:bD:d

答案:c栈是一种非线性结构。

A:对B:错

答案:错队列允许在一端进行插入，另一端进行删除操作。

A:错B:对

答案:对在程序设计语言中实现递归操作是用到栈实现的。

A:错B:对

答案:对递归程序在执行时是用队列来保存调用过程中的参数、局部变量和返回参数的。

A:对B:错

答案:错在表达式求值算法中运用到队列来实现的。

A:对B:错

答案:错队列假溢出问题的一个解决方法是运用循环队列。

A:错B:对

答案:对队列Q满的条件是：Q.front==Q.rear。

A:错B:对

答案:错每当在新队列中插入一个新元素时，尾指针rear增1。

A:对B:错

答案:对在顺序队列中，头指针始终指向队列的最后一个元素。

A:错B:对

答案:错在顺序队列中，尾指针始终指向队列尾元素的下一个位置。

A:对B:错

答案:对

第四章单元测试

串的长度是指（

）

A:串中所含非空格字符的个数B:串中所含不同字符的个数C:串中所含不同字母的个数D:串中所含字符的个数

答案:串中所含不同字母的个数设有串t='I

am

a

good

student

'，那么Substr(t,6,6)=（

）

A:studentB:a

good

sC:goodD:agood

答案:agood串“ababaaababaa”的next数组为（

）

A:012121111212B:012345678999C:0123012322345D:011234223456

答案:011234223456函数substr(“DATASTRUCTURE”，5，9)的返回值为（

）

A:“ASTRUCTUR”B:“DATASTRUCTURE”C:“DATA”D:“STRUCTURE”

答案:“STRUCTURE”设有两个串p和q，求q在p中首次出现的位置的运算称作（

）

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

答案:模式匹配设串s1=’ABCDEFG’，s2=’PQRST’，函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是（

）

A:BCDEFB:BCDEFGC:BCPQRSTD:BCDEFEF

答案:BCDEFEF若串S1=‘ABCDEFG’,S2=‘9898’,S3=‘；’,S4=‘012345’,执行concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,‘8’),length(S2)))其结果为（）

A:ABC；G1234

B:ABCD；2345

C:ABC；G2345

D:ABC；G0123

答案:ABC；G1234

主串为’abaababaddecab’

,模式串为’abad’。使用KMP算法需要（

）次匹配成功。

A:5B:12C:10D:4

答案:4

不包含任何字符的串称为空白串。

A:错B:对

答案:错在串的模式匹配运算中，被匹配的主串称为模式。

A:错B:对

答案:错组成串的数据元素只能是字符。

A:对B:错

答案:对串不能采用顺序存储结构进行存储。

A:对B:错

答案:错模式匹配简单算法时间复杂度是O(m*n)。

A:错B:对

答案:对空格串与空串的没有区别。

A:错B:对

答案:错设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为O(m+n)。

A:错B:对

答案:对两个字符串相等的充分必要条件是两串的长度相等且两串中对应位置的字符也相等。

A:错B:对

答案:对串是一种非线性结构。

A:对B:错

答案:错串的模式匹配算法只能采用串的链式存储结构来实现。

A:错B:对

答案:错

第五章单元测试

设二维数组A[0..m-1][0..n-1]按行优先顺序存储在内存中，每个元素aij占d个字节，则元素aij的地址为（

）

A:LOC(a00)+(i*n+j)*dB:LOC(a00)+(j*n+i-1)*dC:LOC(a00)+((i-1)*n+j-1)*dD:LOC(a00)+((j-1)*n+i-1)*d

答案:LOC(a00)+(i*n+j)*d若数组A[0..m-1][0..n-1]按列优先顺序存储，则aij地址为（）

A:LOC(a00)+(j-1)*m+I-1B:LOC(a00)+(j-1)*n+i-1C:LOC(a00)+j*n+ID:LOC(a00)+j*m+i

答案:LOC(a00)+j*m+i若下三角矩阵An*n，按行顺序压缩存储在数组a[0..(n+1)n/2]中，则非零元素aij的地址为（）（设每个元素占d个字节）

A:LOC(a00)+((i-1)i/2+i-1)*dB:LOC(a00)+((i-1)i/2+j-1)*dC:LOC(a00)+((i+1)i/2+j)*dD:LOC(a00)+((j-1)j/2+i)*d

答案:LOC(a00)+((i-1)i/2+j-1)*d稀疏矩阵一般的压缩存储方法有两种，即（）

A:散列和十字链表B:三元组和十字链表C:三元组和散列D:二维数组和三维数组

答案:三元组和十字链表广义表A=((x,(a,b)),((x,(a,b)),y))，则运算head(head(tail(A)))为（

）

A:AB:(x,(a,b))

C:xD:(a,b)

答案:(x,(a,b))

二维数组可以看成是一个线性表。

A:错B:对

答案:对不做插入删除操作的数组，采用顺序存储结构表示数组比较合适。

A:对B:错

答案:对二维数组的顺序存储方法只可以行序为主序的存储方式。

A:错B:对

答案:错对称矩阵在存储时可进行压缩存储。

A:对B:错

答案:对稀疏矩阵是非零值元素分布有一定规律的矩阵。

A:错B:对

答案:错

第六章单元测试

一棵具有67个结点的完全二叉树，它的深度为（

）。

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

答案:7给定树如图所示，请列出的中序遍历序列（

）

。

A:ABDCEFB:DBEFCAC:DBAECFD:DABECF

答案:DBAECF设有树如图所示，则结点g的度为（

）。

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

答案:3用4个权值{7,2,4,5}构造的哈夫曼（Huffman）树的带权路径长度是（

）。

A:35B:34C:32D:33

答案:35对于任何一棵具有n个结点的线索二叉树，具有（

）个线索。

A:

n-1B:

n+1C:

0D:

n

答案:

n+1一棵深度为5的满二叉树有（

）个分支结点。

A:7B:14C:15D:16

答案:15一棵深度为5的满二叉树有（

）个叶子。

A:31B:32C:17D:16

答案:16给定二叉树如图所示，请列出的后序遍历序列（

）

。

A:BADCEB:BDECAC:BACDED:ABCDE

答案:BDECA设有二叉树如图所示，按其中序遍历次序遍历，对于根a的右子树最先访问的结点是（

）。

A:bB:hC:dD:a

答案:h若按层序对深度为6的完全二叉树中全部结点从１开始编号，则编号为10的结点其右孩子的编号为（

）。

A:12B:11

C:20

D:21

答案:21二叉树的子树无左右之分的。

A:对B:错

答案:错二叉树的度大于2的树。

A:对B:错

答案:错二叉树是非线性数据结构。

A:对B:错

答案:错二叉树不能转换为树，树也不能转换为二叉树。

A:错B:对

答案:错哈夫曼（Huffman）树的带权路径长度是最小的。

A:错B:对

答案:对满二叉树就是一种特殊的完全二叉树。

A:对B:错

答案:对假设n(n>0)个结点的树，它有且只有1个根结点。

A:错B:对

答案:对n个结点的线索二叉树中线索的数目是不确定的。

A:对B:错

答案:错不含任何结点的空树，它可以是一棵树也是一棵二叉树。

A:错B:对

答案:对可以采用递归的方法计算二叉树的深度。

A:错B:对

答案:对

第七章单元测试

无向图的邻接矩阵是一个(

)

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

答案:对称矩阵若图G(V,E)中含有7个顶点，则保证图G在任何情况下都是连通的需要的边数最少是(

)

A:6B:16C:21D:15

答案:16如果从无向图的任一顶点出发进行一次深度优先遍历即可访问所以顶点，则该图一定是(

)

A:连通图B:完全图C:有回路D:一棵树

答案:连通图用Prim算法求一个连通的带权图的最小代价生成树，在算法执行的某时刻，已选取的顶点集合U={1,2,3},已选取的边的集合TE={(1,2),(2,3)},要选取下一条权值最小的边，应该从(

)组中选取。

A:{(3,4),(3,5),(4,5),(1,4)}B:{(1,4),(3,4),(3,5),(2,5)}C:{(4,5),(1,3),(3,5)}D:{(1,2),(2,3),(3,5)}

答案:{(1,4),(3,4),(3,5),(2,5)}已知图的顶点集合U={1,2,3,4},边的集合TE={(1,2),(1,3),(2,3),(3,4)}，则从顶点1出发按深度优先遍历的结点序列是（

）。

A:1234B:1423C:1432

D:2314

答案:1234已知图的顶点集合U={1,2,3,4},边的集合TE={(1,2),(1,3),(2,3),(3,4)}，则从顶点1出发按广度优先遍历的结点序列是（

）。

A:1324B:1432C:1243D:1342

答案:1324任何一个无向连通图的最小生成树（

）。

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

答案:只有一棵有8个结点的无向图最多有（

）条边。

A:56B:112C:14D:28

答案:28有8个结点的无向连通图最少有（

）条边。

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

答案:7有8个结点的有向完全图有（

）条边。

A:14B:28C:56D:112

答案:56已知无向图的顶点集合U={1,2,3,4},边的集合TE={(1,2),(1,3),(2,3),(3,4)}，则顶点3的度是（

）。

A:2B:1C:3D:0

答案:3已知有向图的顶点集合U={1,2,3,4},弧的集合TE={<1,2>,<1,3>,<2,3>,<3,4>}，则该有向图的拓扑排序序列是（

）。

A:1234B:1324C:4321D:1423

答案:1234图的深度优先遍历序列（

）。

A:无B:不存在C:可以有多个D:只有一个

答案:可以有多个拓扑排序算法是通过重复选择具有（

）个前驱顶点的过程来完成的。

A:3

B:1C:0D:2

答案:0n个顶点e条边的图采用邻接表存储，该算法的时间复杂度为（

）。

A:O(n+e)

B:O(n)

C:O(n2)D:O(e)

答案:O(n+e)

n个顶点e条边的图采用邻接矩阵存储，该算法的时间复杂度为（

）。

A:O(n)

B:O(e)C:O(n+e)D:O(n2)

答案:O(n2)

第八章单元测试

在表长为ｎ的链表中进行线性查找，它的平均查找长度为（

）。

A:ＡＳＬ＝（ｎ＋１）／２B:ＡＳＬ＝ｎC:ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１D:

答案:ＡＳＬ＝（ｎ＋１）／２有一个有序表（1，3，9，12，32，41，45，62，75，77，82，95，100），当折半查找有序表中值为82的结点时，则它与表元素中比较了（

）次后查找成功。

A:1B:4C:8D:2

答案:4采用折半查找方法查找长度为n的线性表时，每个元素的平均查找长度为（

）。

A:O(n)B:O(n2)C:O(nlog2n)D:O(log2n)

答案:O(log2n)链表适用于以下（

）查找

A:二分法B:顺序C:随机D:顺序，也能二分法

答案:顺序

顺序表查找法适合于以下（

）存储结构的线性表。

A:顺序存储或链接存储B:索引存储C:压缩存储D:散列存储

答案:顺序存储或链接存储对线性表进行二分查找时，要求线性表必须（

）。

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

答案:以顺序方式存储，且结点按关键字有序排序有一个长度为12的有序表，按二分查找对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为（

）。

A:35/12B:39/12C:37/12D:43/12

答案:37/12碰撞（冲突）指的是（

）。

A:两个元素具有相同序号B:两个元素的关键码值不同，而非码属性相同C:负载因子过大D:不同关键码值对应到相同的存储地址

答案:不同关键码值对应到相同的存储地址在各种查找方法中，平均查找长度与结点个数n无关的查找方法是（

）。

A:顺序查找B:分块查找C:折半查找D:散列查找

答案:散列查找散列法存储的基本思想是（

）。

A:顺序查找B:由关键字的值决定数据的存储地址C:查找与结点个数n无关D:以顺序方式且结点按关键字有序排序

答案:由关键字的值决定数据的存储地址在散列函数H(key)=key%p，p应取（

）。

A:整数B:素数C:偶数D:小数

答案:素数采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分（

）个结点最佳。

A:6B:25C:10D:625

答案:25平衡二叉树上的平衡因子只能取（

）。

A:-1B:-1,0,1C:0D:1

答案:-1,0,1以下对二叉排序树的描述不正确的是（

）。

A:二叉排序树左子树上所有结点的值均小于它的根结点的值B:中序遍历一棵二叉树时可以得到一个结点值递减的序列C:二叉排序树右子树上所有结点的值均大于它的根结点的值

D:左、右子树也分别是二叉排序树

答案:中序遍历一棵二叉树时可以得到一个结点值递减的序列

假设在平衡二叉树上插入一个结点后造成了不平衡，其最近不平衡点为A，且已知A的左子树的平衡因子为-1，其右子树的平衡因子为0，应该进行（

）型调整可使二叉树平衡。

A:RRB:RLC:LRD:LL

答案:LR

第九章单元测试

从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，这种排序方法称为（

）。

A:冒泡排序B:插入排序C:归并排序D:选择排序

答案:插入排序从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（

）。

A:冒泡排序B:归并排序C:选择排序D:插入排序

答案:选择排序对n个关键字作快速排序，在最坏情况下，算法的时间复杂度是（

）。

A:O(n2)B:O(n3)C:O(n)D:O(nlog2n)

答案:O(n2)下列关键字序列中，（

）是堆。

A:16，23，53，31，94，72B:16，72，31，23，94，53C:94，23，31，72，16，53D:16，53，23，94，31，72

答案:16，23，53，31，94，72下述几种排序方法中，（

）是稳定的排序方法。

A:快速排序B:归并排序C:堆排序D:希尔排序

答案:归并排序在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是（

）。

A:选择排序B:插入排序C:起泡排序D:希尔排序

答案:选择排序在待排序的元素序列基本有序的前提下，效率最高的排序方法是（

）。

A:选择排序B:归并排序C:插入排序D:快速排序

答案:插入排序在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置至少需比较（

）次。

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

答案:6