数据结构（海南联盟） 知到智慧树网课答案

数据结构（海南联盟）-知到答案、智慧树答案第一章单元测试1、问题：从一个二维数组b[m][n]中找出最大值元素的时间复杂度为选项：A:mB:nC:m+nD:m*n答案:【m*n】2、问题：在以下时间复杂度的数量级中，数量级最大的是选项：A:B:C:D:答案:【】3、问题：下面程序段的时间复杂度为____________。for(inti=0;i选项：A:O(m2)B:O(n2)C:O(m*n)D:O(m+n)答案:【O(m*n)】4、问题：执行下面程序段时，执行S语句的次数为（）。for(inti=1;i<=n;i++)for(intj=1;j<=i;j++)S;选项：A:n2B:n2/2C:n(n+1)D:n(n+1)/2答案:【n(n+1)/2】5、问题：线性结构是数据元素之间存在一种：（）。选项：A:一对多关系B:多对多关系C:多对一关系D:一对一关系答案:【一对一关系】6、问题：数据结构中，与所使用的计算机无关的是数据的（）结构。选项：A:存储B:物理C:逻辑D:物理和存储答案:【逻辑】7、问题：算法分析的目的是：（）。选项：A:找出数据结构的合理性B:研究算法中的输入和输出的关系C:分析算法的效率以求改进D:分析算法的易懂性和文档性答案:【分析算法的效率以求改进】8、问题：算法分析的两个主要方面是：（）。选项：A:空间复杂性和时间复杂性B:正确性和简明性C:可读性和文档性D:数据复杂性和程序复杂性答案:【空间复杂性和时间复杂性】9、问题：计算机算法指的是：（）。选项：A:计算方法B:排序方法C:解决问题的有限运算序列D:调度方法答案:【解决问题的有限运算序列】10、问题：计算机算法必须具备输入、输出和（）等5个特性。选项：A:可行性、可移植性和可扩充性B:可行性、确定性和有穷性C:确定性、有穷性和稳定性D:易读性、稳定性和安全性答案:【可行性、确定性和有穷性】11、问题：一个算法的好坏可以通过复杂性、可读性、健壮性、高效性这四个方面进行评价。选项：A:对B:错答案:【错】12、问题：数据结构是一门研究算法的学科。选项：A:对B:错答案:【错】13、问题：数据结构中，数据的逻辑结构包括线性结构、图结构、树形结构、集合。选项：A:对B:错答案:【对】14、问题：线性表的逻辑顺序与存储顺序总是一致的。选项：A:对B:错答案:【错】15、问题：每种数据结构都具备三个基本运算：插入、删除和查找。选项：A:对B:错答案:【错】16、问题：线性结构中元素之间只存在多对多关系。选项：A:对B:错答案:【错】17、问题：在线性结构中，第一个结点没有前驱结点。选项：A:对B:错答案:【对】18、问题：在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。选项：A:对B:错答案:【对】19、问题：算法分析的目的是分析算法的效率以求改进。选项：A:对B:错答案:【对】20、问题：同一逻辑结构采用不同的存储方法，可以得到不同的存储结构。选项：A:对B:错答案:【对】第二章单元测试1、问题：在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：（）选项：A:访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）B:在第i个结点后插入一个新结点（1≤i≤n）C:删除第i个结点（1≤i≤n）D:将n个结点从小到大排序答案:【访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）】2、问题：向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。选项：A:8B:63.5C:63D:7答案:【63.5】3、问题：线性表若采用链式存储结构时，要求内存中可用存储单元的地址:（）选项：A:必须是连续的B:部分地址必须是连续的C:一定是不连续的D:连续或不连续都可以答案:【连续或不连续都可以】4、问题：若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用_______存储方式最节省时间。选项：A:顺序表B:双链表C:带头节点的双循环链表D:单循环链表答案:【顺序表】5、问题：在一个以h为头结点的单循环链表中，使指针p指向链尾结点的条件是（）。选项：A:p->next==h;B:p->next==NULLC:p->next->next==hD:p->next==h->next答案:【p->next==h;】6、问题：链表是一种采用（）存储结构存储的线性表选项：A:顺序B:链式C:星式D:网状答案:【链式】7、问题：单链表包括两个域：（）。选项：A:数据域和表位B:链式和数字C:数据域和星式D:数据域和指针域答案:【数据域和指针域】8、问题：单链表可以用（）来命名。选项：A:结点名B:LC:KD:头指针的名字答案:【头指针的名字】9、问题：单链表的插入操作其时间复杂度为（）。选项：A:O（n）B:O（1）C:O（n2）D:O（n3）答案:【O（n）】10、问题：顺序表的插入操作的时间复杂度为（）。选项：A:O（n）B:O（1）C:O（n2）D:O（n3）答案:【O（n）】11、问题：线性表的逻辑结构特性是一对多的。选项：A:对B:错答案:【错】12、问题：顺序表在进行插入和删除操作时不需要移动元素。选项：A:对B:错答案:【错】13、问题：对于链表是依靠指针来反映其线性逻辑关系的。选项：A:对B:错答案:【对】14、问题：在单链表的第一个结点之前是不允许附设结点的。选项：A:对B:错答案:【错】15、问题：在单链表中首元结点就是头结点。选项：A:对B:错答案:【错】16、问题：循环单链表的最大优点是从任一结点出发都可访问到链表中每一个元素。选项：A:对B:错答案:【对】17、问题：线性表采用链式存储，便于插入和删除操作。选项：A:对B:错答案:【对】18、问题：线性表采用顺序存储，必须占用一片连续的存储单元。选项：A:对B:错答案:【对】19、问题：单链表可以有多个指针域。选项：A:对B:错答案:【错】20、问题：顺序表的每个元素所占的存储单元是相等的。选项：A:对B:错答案:【对】第三章单元测试1、问题：栈的插入和删除操作在（）选项：A:栈底B:栈顶C:任意位置D:指定位置答案:【栈顶】2、问题：五节车厢以编号a，b，c，d，e顺序进入铁路调度站（栈），可以得到（）的编组选项：A:c，d，e，a，bB:b，d，a，c，eC:c，e，d，b，aD:a，c，e，b，d答案:【c，e，d，b，a】3、问题：判定一个顺序栈S（栈空间大小为n）为空的条件是（）选项：A:S->top==0B:S->top!=0C:S->top==nD:S->top!=n答案:【S->top==0】4、问题：在一个链队列中，front和rear分别为头指针和尾指针，则插入一个结点s的操作为（）选项：A:front=front->nextB:s->next=rear;rear=sC:rear->next=s;rear=s;D:s->next=front;front=s;答案:【rear->next=s;rear=s;】5、问题：一个队列的入队序列是1，2，3，4，则队列的出队序列是（）选项：A:1，2，3，4B:4，3，2，1C:1，4，3，2D:3，4，1，2答案:【4，3，2，1】6、问题：依次在初始为空的队列中插入元素a,b,c,d以后，紧接着做了两次删除操作，此时的队头元素是（）选项：A:aB:bC:cD:d答案:【c】7、问题：栈是一种非线性结构。选项：A:对B:错答案:【错】8、问题：队列允许在一端进行插入，另一端进行删除操作。选项：A:对B:错答案:【对】9、问题：在程序设计语言中实现递归操作是用到栈实现的。选项：A:对B:错答案:【对】10、问题：递归程序在执行时是用队列来保存调用过程中的参数、局部变量和返回参数的。选项：A:对B:错答案:【错】11、问题：在表达式求值算法中运用到队列来实现的。选项：A:对B:错答案:【错】12、问题：队列假溢出问题的一个解决方法是运用循环队列。选项：A:对B:错答案:【对】13、问题：队列Q满的条件是：Q.front==Q.rear。选项：A:对B:错答案:【错】14、问题：每当在新队列中插入一个新元素时，尾指针rear增1。选项：A:对B:错答案:【对】15、问题：在顺序队列中，头指针始终指向队列的最后一个元素。选项：A:对B:错答案:【错】16、问题：在顺序队列中，尾指针始终指向队列尾元素的下一个位置。选项：A:对B:错答案:【对】第四章单元测试1、问题：串的长度是指（）选项：A:串中所含不同字母的个数B:串中所含字符的个数C:串中所含不同字符的个数D:串中所含非空格字符的个数答案:【串中所含不同字母的个数】2、问题：设有串t='Iamagoodstudent'，那么Substr(t,6,6)=（）选项：A:studentB:agoodsC:goodD:agood答案:【agood】3、问题：串“ababaaababaa”的next数组为（）选项：A:012345678999D:0123012322345答案:【】4、问题：函数，5，9)的返回值为（）选项：A:“STRUCTURE”C:“ASTRUCTUR”答案:【“STRUCTURE”】5、问题：设有两个串p和q，求q在p中首次出现的位置的运算称作（）选项：A:连接B:模式匹配C:求子串D:求串长答案:【模式匹配】6、问题：设串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】7、问题：若串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###G0123B:ABCD###2345C:ABC###G2345D:ABC###G1234答案:【ABC###G1234】8、问题：主串为’abaababaddecab’,模式串为’abad’。使用KMP算法需要（）次匹配成功。选项：A:5B:12C:4D:10答案:【4】9、问题：不包含任何字符的串称为空白串。选项：A:对B:错答案:【错】10、问题：在串的模式匹配运算中，被匹配的主串称为模式。选项：A:对B:错答案:【错】11、问题：组成串的数据元素只能是字符。选项：A:对B:错答案:【对】12、问题：串不能采用顺序存储结构进行存储。选项：A:对B:错答案:【错】13、问题：模式匹配简单算法时间复杂度是O(m*n)。选项：A:对B:错答案:【对】14、问题：空格串与空串的没有区别。选项：A:对B:错答案:【错】15、问题：设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为O(m+n)。选项：A:对B:错答案:【对】16、问题：两个字符串相等的充分必要条件是两串的长度相等且两串中对应位置的字符也相等。选项：A:对B:错答案:【对】17、问题：串是一种非线性结构。选项：A:对B:错答案:【错】18、问题：串的模式匹配算法只能采用串的链式存储结构来实现。选项：A:对B:错答案:【错】第五章单元测试1、问题：设二维数组A[0..m-1][0..n-1]按行优先顺序存储在内存中，每个元素aij占d个字节，则元素aij的地址为（）选项：A:LOC(a00)+(i*n+j)*dB:LOC(a00)+((i-1)*n+j-1)*dC:LOC(a00)+((j-1)*n+i-1)*dD:LOC(a00)+(j*n+i-1)*d答案:【LOC(a00)+(i*n+j)*d】2、问题：若数组A[0..m-1][0..n-1]按列优先顺序存储，则aij地址为（）选项：A:LOC(a00)+j*m+iB:LOC(a00)+j*n+IC:LOC(a00)+(j-1)*n+i-1D:LOC(a00)+(j-1)*m+I-1答案:【LOC(a00)+j*m+i】3、问题：若下三角矩阵An*n，按行顺序压缩存储在数组a[0..(n+1)n/2]中，则非零元素aij的地址为（）（设每个元素占d个字节）选项：A:LOC(a00)+((j-1)j/2+i)*dB:LOC(a00)+((i+1)i/2+j)*dC:LOC(a00)+((i-1)i/2+i-1)*dD:LOC(a00)+((i-1)i/2+j-1)*d答案:【LOC(a00)+((i-1)i/2+j-1)*d】4、问题：稀疏矩阵一般的压缩存储方法有两种，即（）选项：A:二维数组和三维数组B:三元组和散列C:三元组和十字链表D:散列和十字链表答案:【三元组和十字链表】5、问题：广义表A=((x,(a,b)),((x,(a,b)),y))，则运算head(head(tail(A)))为（）选项：A:xB:(a,b)C:(x,(a,b))D:A答案:【(x,(a,b))】6、问题：二维数组可以看成是一个线性表。选项：A:对B:错答案:【对】7、问题：不做插入删除操作的数组，采用顺序存储结构表示数组比较合适。选项：A:对B:错答案:【对】8、问题：二维数组的顺序存储方法只可以行序为主序的存储方式。选项：A:对B:错答案:【错】9、问题：对称矩阵在存储时可进行压缩存储。选项：A:对B:错答案:【对】10、问题：稀疏矩阵是非零值元素分布有一定规律的矩阵。选项：A:对B:错答案:【错】第六章单元测试1、问题：一棵具有67个结点的完全二叉树，它的深度为（）。选项：A:6B:7C:8D:9答案:【7】2、问题：给定树如图所示，请列出的中序遍历序列（）。选项：A:DBAECFB:ABDCEFC:DBEFCAD:DABECF答案:【DBAECF】3、问题：设有树如图所示，则结点g的度为（）。选项：A:1B:2C:3D:4答案:【3】4、问题：用4个权值{7,2,4,5}构造的哈夫曼（）树的带权路径长度是（）。选项：A:32B:33C:34D:35答案:【35】5、问题：对于任何一棵具有n个结点的线索二叉树，具有（）个线索。选项：A:0B:n-1C:nD:n+1答案:【n+1】6、问题：一棵深度为5的满二叉树有（）个分支结点。选项：A:7B:14C:15D:16答案:【15】7、问题：一棵深度为5的满二叉树有（）个叶子。选项：A:32B:31C:17D:16答案:【16】8、问题：给定二叉树如图所示，请列出的后序遍历序列（）。选项：A:ABCDEB:BADCEC:BDECAD:BACDE答案:【BDECA】9、问题：设有二叉树如图所示，按其中序遍历次序遍历，对于根a的右子树最先访问的结点是（）。选项：A:aB:bC:dD:h答案:【h】1（0、问题：若按层序对深度为6的完全二叉树中全部结点从１开始编号，则编号为10的结点其右孩子的编号为）。选项：B:12C:20D:21答案:【21】11、问题：二叉树的子树无左右之分的。选项：A:对B:错答案:【错】12、问题：二叉树的度大于2的树。选项：A:对B:错答案:【错】13、问题：二叉树是非线性数据结构。选项：A:对B:错答案:【错】14、问题：二叉树不能转换为树，树也不能转换为二叉树。选项：A:对B:错答案:【错】15、问题：哈夫曼（）树的带权路径长度是最小的。选项：A:对B:错答案:【对】16、问题：满二叉树就是一种特殊的完全二叉树。选项：A:对B:错答案:【对】17、问题：假设n(n>0)个结点的树，它有且只有1个根结点。选项：A:对B:错答案:【对】18、问题：n个结点的线索二叉树中线索的数目是不确定的。选项：A:对B:错答案:【错】19、问题：不含任何结点的空树，它可以是一棵树也是一棵二叉树。选项：A:对B:错答案:【对】20、问题：可以采用递归的方法计算二叉树的深度。选项：A:对B:错答案:【对】第七章单元测试1、问题：无向图的邻接矩阵是一个()选项：A:对称矩阵B:零矩阵C:上三角矩阵D:对角阵答案:【对称矩阵】2、问题：若图中含有7个顶点，则保证图G在任何情况下都是连通的需要的边数最少是()选项：A:6B:15C:16D:21答案:【16】3、问题：如果从无向图的任一顶点出发进行一次深度优先遍历即可访问所以顶点，则该图一定是()选项：A:完全图B:连通图C:有回路D:一棵树答案:【连通图】4{、问题：用Prim算法求一个连通的带权图的最小代价生成树，在算法执行的某时刻，已选取的顶点集合U=1,2,3},已选取的边的集合TE={(1,2),(2,3)},要选取下一条权值最小的边，应该从()组中选取。选项：A:{(1,4),(3,4),(3,5),(2,5)}B:{(4,5),(1,3),(3,5)}C:{(1,2),(2,3),(3,5)}D:{(3,4),(3,5),(4,5),(1,4)}答案:【{(1,4),(3,4),(3,5),(2,5)}】5、问题：已知图的顶点集合U={1,2,3,4},边的集合TE={(1,2),(1,3),(2,3),(3,4)}，则从顶点1出发按深度优先遍历的结点序列是（）。选项：A:1432B:2314C:1423D:1234答案:【1234】6、问题：已知图的顶点集合U={1,2,3,4},边的集合TE={(1,2),(1,3),(2,3),(3,4)}，则从顶点1出发按广度优先遍历的结点序列是（）。选项：A:1243B:1324C:1342D:1432答案:【1324】7、问题：任何一个无向连通图的最小生成树（）。选项：A:只有一棵B:一棵或多棵C:一定有多棵D:可能不存在答案:【只有一棵】8、问题：有8个结点的无向图最多有（）条边。选项：A:14B:28C:56答案:【28】9、问题：有8个结点的无向连通图最少有（）条边。选项：A:5B:6C:7D:8答案:【7】10、问题：有8个结点的有向完全图有（）条边。选项：A:14B:28C:56答案:【56】11、问题：已知无向图的顶点集合U={1,2,3,4},边的集合TE={(1,2),(1,3),(2,3),(3,4)}，则顶点3的度是（）。选项：A:1B:2C:3D:0答案:【3】12、问题：已知有向图的顶点集合U={1,2,3,4},弧的集合TE={<1,2>,<1,3>,<2,3>,<3,4>}，则该有向图的拓扑排序序列是（）。选项：A:1234B:1324C:1423D:4321答案:【1234】13、问题：图的深度优先遍历序列（）。选项：A:不存在B:可以有多个C:只有一个D:无答案:【可以有多个】14、问题：拓扑排序算法是通过重复选择具有（）个前驱顶点的过程来完成的。选项：A:1B:2C:3D:0答案:【0】15、问题：n个顶点e条边的图采用邻接表存储，该算法的时间复杂度为（）。选项：A:O(n2)B:O(n+e)C:O(n)D:O(e)答案:【O(n+e)】16、问题：n个顶点e条边的图采用邻接矩阵存储，该算法的时间复杂度为（）。选项：A:O(n2)B:O(n+e)C:O(n)D:O(e)答案:【O(n2)】第八章单元测试1、问题：在表长为ｎ的链表中进行线性查找，它的平均查找长度为（）。选项：A:ＡＳＬ＝ｎB:ＡＳＬ＝（ｎ＋１）／２C:D:ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１答案:【ＡＳＬ＝（ｎ＋１）／２】28、问题：有一个有序表（1，3，9，12，32，41，45，62，75，77，82，95，100），当折半查找有序表中值为2的结点时，则它与表元素中比较了（）次后查找成功。选项：A:1B:2C:4D:8答案:【4】3、问题：采用折半查找方法查找长度为n的线性表时，每个元素的平均查找长度为（）。选项：A:O(n2)B:O(nlog2n)C:O(n)D:O(log2n)答案:【O(log2n)】4、问题：链表适用于以下（）查找选项：A:顺序B:二分法C:顺序，也能二分法D:随机答案:【顺序】5、问题：顺序表查找法适合于以下（）存储结构的线性表。选项：A:散列存储B:顺序存储或链接存储C:压缩存储D:索引存储答案:【顺序存储或链接存储】6、问题：对线性表进行二分查找时，要求线性表必须（）。选项：A:以顺序方式存储B:以链接方式存储C:以顺序方式存储，且结点按关键字有序排序D:以链接方式存储，且结点按关键字有序排序答案:【以顺序方式存储，且结点按关键字有序排序】7、问题：有一个长度为12的有序表，按二分查找对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为（）。选项：A:35/12B:37/12C:39/12D:43/12答案:【37/12】8、问题：碰撞（冲突）指的是（）。选项：A:两个元素具有相同序号B:两个元素的关键码值不同，而非码属性相同C:不同关键码值对应到相同的存储地址D:负载因子过大答案:【不同关键码值对应到相同的存储地址】9、问题：在各种查找方法中，平均查找长度与结点个数n无关的查找方法是（）。选项：A:顺序查找B:折半查找C:散列查找D:分块查找答案:【散列查找】10、问题：散列法存储的基本思想是（）。选项：A:顺序查找B:以顺序方式且结点按关键字有序排序C:查找与结点个数n无关D:由关键字的值决定数据的存储地址答案:【由关键字的值决定数据的存储地址】11、问题：在散列函数H(key)=key%p，p应取（）。选项：A:整数B:偶数C:素数D:小数答案:【素数】12、问题：采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分（）个结点最佳。选项：A:10B:25C:6D:625答案:【25】13、问题：平衡二叉树上的平衡因子只能取（）。选项：A:-1B:0C:1D:-1,0,1答案:【-1,0,1】14、问题：以下对二叉排序树的描述不正确的是（）。选项：A:二叉排序树左子树上所有结点的值均小于它的根结点的值B:二叉排序树右子树上所有结点的值均大于它的根结点的值C:左、右子树也分别是二叉排序树D:中序遍历一棵二叉树时可以得到一个结点值递减的序列答案:【中序遍历一棵二叉树时可以得到一个结点值递减的序列】15、问题：假设在平衡二叉树上插入一个结点后造成了不平衡，其最近不平衡点为A，且已知A的左子树的平衡因子为-1，其右子树的平衡因子为0，应该进行（）型调整可使二叉树平衡。选项：A:LLB:RRC:LRD:RL答案:【LR】第九章单元测试1、问题：从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，这种排序方法称为（）。选项：A:归并排序B:冒泡排序C:插入排序D:选择排序答案:【插入排序】2、问题：从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（）。选项：A:归并排序B:冒泡排序C:插入排序D:选择排序答案:【选择排序】3、问题：对n个关键字作快速排序，在最坏情况下，算法的时间复杂度是（）。选项：A:O(n)B:O(n2)C:O(nlog2n)D:O(n3)答案:【O(n2)】4、问题：下列关键字序列中，（）是堆。选项：A:16，72，31，23，94，53B:94，23，31，72，16，53C:16，53，23，94，31，72D:16，23，53，31，94，72答案:【16，23，53，31，94，72】5、问题：下述几种排序方法中，（）是稳定的排序方法。选项：A:希尔排序B:快速排序C:归并排序D:堆排序答案:【归并排序】6、问题：在所有排序方法中，关