数据结构（西安理工大学） 知到智慧树网课答案

数据结构（西安理工大学）-知到答案、智慧树答案第一章单元测试1、问题：研究数据结构就是研究()。选项：A:数据的逻辑结构和存储结构B:数据的逻辑结构、存储结构及其数据在运算上的实现C:数据的逻辑结构D:数据的存储结构答案:【数据的逻辑结构、存储结构及其数据在运算上的实现】2、问题：关于算法的说法，错误的是()。选项：A:为解决某问题的算法和为该问题编写的程序含义是相同的B:其他三项都是错误的C:算法最终必须由计算机程序实现D:算法的可行性是指指令不能有二义性答案:【其他三项都是错误的】3、问题：数据的()包括集合、线性、树和图4种基本类型。选项：A:存储结构B:算法描述C:基本运算D:逻辑结构答案:【逻辑结构】4、问题：数据的存储结构包括顺序、链式、散列和()4种基本类型。选项：A:数组B:集合C:索引D:向量答案:【索引】5、问题：下面算法的时间复杂度为()。for(i=0;i选项：A:O(n2)B:O(m2)C:O(m×n)D:O(m+n)答案:【O(m×n)】6、问题：以下（）属于设计一个“好”的算法应考虑达到的目标。选项：A:健壮性B:正确性C:可读性D:效率与低存储量要求答案:【健壮性;正确性;可读性;效率与低存储量要求】7、问题：依据所有数据成员之间的逻辑关系的不同，数据结构分为（）。??选项：A:物理结构B:逻辑结构C:非线性结构D:线性结构答案:【非线性结构;线性结构】8、问题：在存储数据时，不仅要考虑存储各数据元素的值，而且还要存储数据元素之间的关系。选项：A:错B:对答案:【对】9、问题：在逻辑结构定义的操作与具体实现有关。选项：A:错B:对答案:【错】10、问题：算法是对解题方法和步骤的描述。选项：A:错B:对答案:【对】11、问题：算法分析的两个主要方面是时间复杂度和空间复杂度的分析。选项：A:错B:对答案:【对】第二章单元测试1、问题：线性表是（）。选项：A:一个有限序列，可以为空。B:一个有限序列，不能为空。C:一个无限序列，不能为空。D:一个无限序列，可以为空。答案:【一个有限序列，可以为空。】2、问题：若某线性表中最常用的操作是取第i个元素和查找第i个元素的前驱，则采用（）存储方法最节省时间。选项：A:单链表B:循环链表C:双向链表D:顺序表答案:【顺序表】3、问题：单链表中，增加一个头结点的目的是为了（）。选项：A:方便运算的实现B:说明单链表是线性表的链式存储C:标识表结点中首结点的位置D:使单链表至少有一个结点答案:【方便运算的实现】4、问题：在带有头结点的单链表Head中，要向表头插入一个由指针p指向的结点，则执行（）。选项：A:p->next=Head->next;Head->next=p;B:Head=p;p->next=Head;C:p->next=Head;Head=p;D:p->next=Head;p=Head;答案:【p->next=Head->next;Head->next=p;】5、问题：在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（）。选项：A:访问第i个元素（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）B:将n个元素从小到大排序C:删除第i个元素（1≤i≤n）D:在第i个元素后插入一个新结点（1≤i≤n）答案:【访问第i个元素（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）】6、问题：下列说法正确的有()。选项：A:“同一数据逻辑结构中的所有数据元素都具有相同的特性”是指数据元素所包含的数据项的个数相等B:数据的逻辑结构与数据元素本身的内容和形式无关C:从逻辑关系上讲，数据结构分为两大类：线性结构和非线性结构D:所谓数据的逻辑结构是指数据元素之间的逻辑关系?E:算法和程序原则上没有区别，在讨论数据结构时二者通用答案:【数据的逻辑结构与数据元素本身的内容和形式无关;从逻辑关系上讲，数据结构分为两大类：线性结构和非线性结构;所谓数据的逻辑结构是指数据元素之间的逻辑关系?】7、问题：线性表的逻辑顺序和存储顺序总是一致的。选项：A:对B:错答案:【错】8、问题：在线性表的顺序存储结构中，插入和删除时移动元素的个数与该元素的位置有关。选项：A:对B:错答案:【对】9、问题：顺序存储结构只能存储线性结构，链式存储结构只能存储非线性结构。选项：A:错B:对答案:【错】10、问题：线性表的链式存储结构优于顺序存储结构。选项：A:错B:对答案:【错】11、问题：链式存储方式以指针表示元素间的逻辑关系。选项：A:错B:对答案:【对】第三章单元测试1、问题：在顺序栈空的情况下不能进行出栈操作，否则将产生“下溢”。选项：A:对B:错答案:【对】2、问题：栈和队列都是限制存取位置的线性表。选项：A:错B:对答案:【对】3、问题：若元素a,b,c,d,e,f依次进栈，允许进栈、退栈操作交替进行，则不可能得到出栈序列：a,f,e,d,c,b。选项：A:对B:错答案:【错】4、问题：入栈操作和入队列操作在链式存储结构上实现时一般不需要考虑栈溢出的情况。选项：A:错B:对答案:【对】5、问题：同一个栈内的各个数据元素类型可以不一致。选项：A:对B:错答案:【错】6、问题：以下说法中正确的是（）选项：A:队列被称为“先进后出”表。B:栈是一种只允许在一端进行插入和删除的线性表。C:当队列中无数据元素时，称空队列。D:栈是一种操作不受限制的线性表。答案:【栈是一种只允许在一端进行插入和删除的线性表。;当队列中无数据元素时，称空队列。】7、问题：以下说法中错误的是()?。选项：A:利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，这种形式的栈称为顺序栈。B:栈不能对输入序列部分或全局求逆。C:当top等于数组最大下标时则栈满。D:top=-1时为空栈，元素进栈时指针top不断减1。答案:【栈不能对输入序列部分或全局求逆。;top=-1时为空栈，元素进栈时指针top不断减1。】8、问题：已知一个栈的进栈序列是a1,a2,a3....an.其输出序列为1,2,3...n,若a3=1则a1为（）选项：A:可能是2B:可能是3C:不可能是2D:一定是2E:不可能是3答案:【可能是3;不可能是2;一定是2】9、问题：栈的特点是（）选项：A:先进后出B:进优于出C:先进先出D:出优于进答案:【先进后出】10、问题：设循环队列的容量为20，序号从0到19，经过一系列的入队和出队后，front=5,rear=10,问队列中有多少个元素（采用节省一个队列存储空间的方式）。选项：A:7B:6C:5D:4答案:【5】11、问题：一个队列的入队序列是1，2，3，4，则队列的出队序列是（）选项：A:1，4，3，2B:4，3，2，1C:1，2，3，4D:3，2，4，1答案:【1，2，3，4】12、问题：一般情况下，将递归算法转换成等价的非递归算法应该设置（）选项：A:栈B:栈或队列C:队列D:数组答案:【栈】13、问题：设用链表作为栈的存储结构则退栈操作（）选项：A:必须判别栈是否为满B:对栈不作任何判别C:判别栈元素的类型D:必须判别栈是否为空答案:【必须判别栈是否为空】第四章单元测试1、问题：KMP算法的特点是在模式匹配时指示主串的指针不会变小。选项：A:错B:对答案:【对】2、问题：空串与空格串是相同的。选项：A:对B:错答案:【错】3、问题：串的长度是指串中不同字符的个数。选项：A:错B:对答案:【错】4、问题：设有两个串P和Q，其中Q是P的子串，把Q在P中首次出现的位置作为子串Q在P中的位置的算法称为模式匹配算法。选项：A:错B:对答案:【对】5、问题：设模式串（子串）的长度为m，目标串（主串）的长度为n。当n≈m且处理只匹配一次的模式时，简单模式匹配（BF）算法所花费的时间代价也可能会比KMP算法更节省。选项：A:对B:错答案:【对】6、问题：串是一种特殊的线性表，下列不能体现其特殊性的是（）选项：A:数据元素是字符型数据B:可以链接存储C:可以顺序存储D:数据元素可以是非字符数据答案:【可以链接存储;可以顺序存储;数据元素可以是非字符数据】7、问题：以下说法中错误的是()?选项：A:串的长度必须大于零B:串中的元素只能是字母C:空串就是空白串D:串是一种特殊的线性表答案:【串的长度必须大于零;串中的元素只能是字母;空串就是空白串】8、问题：两个串相等必须有（）选项：A:串中的各位置字符任意B:串中各位置字符均对应相等C:串长度任意D:串长度相等E:串长度不相等答案:【串中各位置字符均对应相等;串长度相等】9、问题：若串S=”software”，其子串的数目是（）选项：A:36B:37C:9D:8答案:【37】10、问题：下面（）不是“abcd321ABCD”的子串（）选项：A:abcABB:321ABC:abcdD:21AB答案:【abcAB】11、问题：已知模式串为“aaab”，其next数组值为（）选项：A:0,1,2,0B:-1,1,0,0C:0,0,1,2D:-1,0,1,2答案:【-1,0,1,2】12、问题：设主串为“abccdcdccdbaa”，模式串为“cdcc”，用BF算法在第（）次匹配成功。选项：A:4B:6C:7D:5答案:【6】13、问题：设串s1=“ABCDEFG”，s2=“12345”，用字符数组从0下标位置存储，函数strcat(s,t)返回s和t串的连接串，strsub(s,i,j)返回串s中从第i个字符开始的连续j个字符组成的子串，strlen(s)返回串s的长度，则strcat(strsub(s1,2,strlen(s2)),strsub(s1,strlen(s2),2))的结果是（）选项：A:CDEFG12B:CD12345C:CDEFGFGD:BCDEFG1答案:【CDEFGFG】第五章单元测试1、问题：稀疏矩阵压缩存储后，必会失去随机存取功能。选项：A:对B:错答案:【对】2、问题：数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。选项：A:对B:错答案:【错】3、问题：数组的存储结构是一组连续的内存单元。选项：A:对B:错答案:【对】4、问题：广义表中原子个数即为广义表的长度。选项：A:错B:对答案:【错】5、问题：广义表中元素的个数即为广义表的深度。选项：A:对B:错答案:【错】6、问题：广义表((a),(a))的表头和表尾是（）选项：A:(a)B:bC:aD:((a))答案:【(a);((a))】7、问题：以下属于特殊矩阵的是()?选项：A:对角矩阵B:上三角矩阵C:对称矩阵D:下三角矩阵答案:【对角矩阵;上三角矩阵;对称矩阵;下三角矩阵】8、问题：以下不属于数组操作的是()?选项：A:查找B:删除C:插入D:修改E:存取答案:【删除;插入】9、问题：对行下标由1到50、列下标由1到80的二维数组a，若该数组的起始地址为2000且每个元素占2个存储单元，并以行为主序顺序存储，则元素a[45][68]的存储地址为（）选项：A:9174B:9175C:9173D:9172答案:【9174】10、问题：在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（）选项：A:非零元素个数B:列号C:行号D:元素值答案:【行号】11、问题：设有一个10阶的下三角矩阵A（包括对角线），按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A[5][4]地址与A[0][0]的地址之差为（）选项：A:28B:19C:55D:10答案:【19】12、问题：设二维数组A[0~m][0~n]按行优先顺序存储在内存中，第一个元素的地址为p，每个元素占k个字节，则a[i][j]的地址为（）选项：A:p+(i*n+j)*kB:p+((j-1)*n+i-1)*kC:p+((i-1)*n+j-1)*kD:p+(j*n+i-1)*k答案:【p+(i*n+j)*k】13、问题：下面说法不正确的是（）选项：A:广义表难以用顺序结构存储B:广义表的表尾总是一个广义表C:广义表可以是一个多层次结构D:广义表的表头总是一个广义表答案:【广义表的表头总是一个广义表】第六章单元测试1、问题：一棵完全二叉树上有1001个结点，其叶子结点的个数是（）。选项：A:250B:A～C都不对C:505D:500答案:【A～C都不对】2、问题：一棵有124个叶结点的完全二叉树最多有（）个结点。选项：A:250B:249C:248D:247答案:【248】3、问题：在n个结点的线索二叉树中，线索的数目为（）选项：A:n+1B:2nC:n-1D:n答案:【n+1】4、问题：设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有（）个结点。选项：A:13B:26C:25D:12答案:【25】5、问题：树的基本遍历策略可分为先根遍历和后根遍历，而二叉树的基本遍历策略可分为先序、中序和后序这三种遍历。我们把由树转化得到的二叉树称为该树对应的二叉树，则（）是正确的。选项：A:树的后根遍历与其对应的二叉树后序遍历序列相同B:树的先根遍历与其对应的二叉树先序遍历序列相同C:树的先根遍历与其对应的二叉树中序遍历序列相同答案:【树的先根遍历与其对应的二叉树先序遍历序列相同】6、问题：完全二叉树（）。选项：A:适合于顺序存储结构存储B:某些结点有左子树时则必有右子树C:叶子结点可在任一层出现D:不一定适合顺序存储结构存储E:某些结点有右子树时则必有左子树答案:【适合于顺序存储结构存储;某些结点有右子树时则必有左子树】7、问题：对于二叉树，下列描述正确的是（）选项：A:高度为k的二叉树结点数最多时一定是满二叉树B:第k层上最多有2k-1个结点C:边的个数比结点个数少1个D:一定有度数为1的结点E:叶子结点数目比度数为2的结点数目多1个F:n个结点共有n-1个非空指针域答案:【高度为k的二叉树结点数最多时一定是满二叉树;边的个数比结点个数少1个;叶子结点数目比度数为2的结点数目多1个;n个结点共有n-1个非空指针域】8、问题：关于哈夫曼编码的说法正确的是（）选项：A:编码无二义性B:两个频度相同的字符其编码长度一定相等C:WPL最小D:是一种最佳编码E:不允许出现频度相同的字符答案:【编码无二义性;WPL最小;是一种最佳编码】9、问题：存在这样的二叉树，对它采用任何次序进行遍历得到的结果都相同。选项：A:对B:错答案:【对】10、问题：二叉树就是结点度为2的有序树。选项：A:对B:错答案:【错】11、问题：若一个结点是二叉树子树的中序遍历序列中的最后一个结点，则它必是该子树的先序遍历序列中的最后一个结点。选项：A:对B:错答案:【错】12、问题：一棵含有n个结点的完全二叉树，它的高度是?log2n?+1。选项：A:错B:对答案:【对】13、问题：线索二叉树的左线索指向其某种遍历序列的直接前驱结点，右线索指向其某种遍历序列的直接后继结点。选项：A:对B:错答案:【对】第七章单元测试1、问题：无向图的邻接矩阵是（）矩阵。选项：A:上三角阵B:下三角阵C:对称D:稀疏矩阵答案:【对称】2、问题：用邻接表存储的图所用空间大小（）选项：A:与边数的平方有关B:与图的顶点数和边数都有关C:只与图的顶点数有关与边数的平方有关D:只与图的边数有关答案:【与图的顶点数和边数都有关】3、问题：不论基于图的邻接表还是基于邻接矩阵存储，图的广度优先遍历算法类似于树的（）选项：A:中序遍历B:后序遍历C:层次遍历D:先序遍历答案:【层次遍历】4、问题：一个连通图的生成树是包含该图的所有顶点的（）选项：A:极大连通子图B:极小子图C:极小连通子图D:极大子图答案:【极小连通子图】5、问题：具有n个顶点的连通有向图中，至少需要（）条边。选项：A:nB:2nC:n+1D:n-1答案:【n】6、问题：下列哪些算法是属于图的应用算法（）选项：A:拓扑排序算法B:克鲁斯卡尔（Kruskal）算法C:欧几里德算法D:哈夫曼（）算法E:迪杰斯特拉（Dijkstra）算法答案:【拓扑排序算法;克鲁斯卡尔（Kruskal）算法;迪杰斯特拉（Dijkstra）算法】7、问题：下列（）算法可用于构造图的生成树。选项：A:FloydB:PrimC:BFSD:kruskalE:DFS答案:【Prim;BFS;kruskal;DFS】8、问题：下列（）是构造最短路径的方法。选项：A:PrimB:FloydC:DijkstraD:KruskalE:BFS答案:【Floyd;Dijkstra】91、问题：n个结点的无向图，若没有顶点到自身的边，也没有一个顶点到另一个顶点的多重边，此时若有n(n-)/2条边，则该无向图一定是连通图。选项：A:错B:对答案:【对】10、问题：用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用空间大小与图的顶点数有关，与图的边数无关。选项：A:错B:对答案:【对】11、问题：对于任意一个图，从它的某个顶点出发进行一次深度或者广度遍历可以访问到该图的每个顶点。选项：A:对B:错答案:【错】12、问题：对于无向图的生成树，从同一顶点出发所得的生成树相同。选项：A:错B:对答案:【错】13、问题：有向图顶点v的度是其邻接矩阵中第v行1的个数。选项：A:错B:对答案:【错】第八章单元测试1、问题：衡量一个查找算法执行效率高低的最重要的指标是（）。选项：A:平均查找长度B:所需的内存大小C:查找表中的元素个数D:查找过程中关键字比较的最大次数答案:【平均查找长度】2、问题：对线性表进行二分查找时，要求线性表必须（）。选项：A:采用顺序存储结构B:采用顺序存储结构且元素按查找关键字有序排列C:采用链接存储结构且结点按查找关键字有序排列D:采用链接存储结构答案:【采用顺序存储结构且元素按查找关键字有序排列】3、问题：哈希查找中的冲突是指（）。.选项：A:不同关键字值对应相同的存储地址B:两个元素的关键字值相同C:两个元素具有相同序号D:两个元素的关键字值不同答案:【不同关键字值对应相同的存储地址】4、问题：对于一棵二叉排序树进行（）遍历可得到按关键字有序排列的数据序列。选项：A:中序B:层序C:先序D:后序答案:【中序】5、问题：顺序查找适合于采用（）存储结构的线性表。选项：A:索引B:顺序或链式C:散列D:压缩答案:【顺序或链式】6、问题：下面关于哈希查找的说法中，正确的是()选项：A:用链地址处理冲突，不会引起二次聚集的现象B:采用链地址法处理冲突时，若规定采用头插法进行插入，则插入任何一个元素的时间是相同的C:用链地址处理冲突，适合表长不确定的情况D:链地址法处理冲突的平均查找长度小于线性探测和二次探测E:采用链地址法处理冲突时，查找任何一个元素的时间都相同答案:【用链地址处理冲突，不会引起二次聚集的现象;采用链地址法处理冲突时，若规定采用头插法进行插入，则插入任何一个元素的时间是相同的;用链地址处理冲突，适合表长不确定的情况;链地址法处理冲突的平均查找长度小于线性探测和二次探测】7、问题：以下关于二叉排序树的说法中，正确的是()选项：A:二叉排序树一定为一棵平衡二叉树B:在二叉排序树上的查找过程与折半查找过程类似C:二叉排序树中左子树上所有结点的关键字值均小于它的根结点D:对某棵二叉排序树进行中序遍历，一定能得到按关键字升序排列的有序序列E:二叉排序树中右子树上所有结点的关键字值均大于它的根结点答案:【在二叉排序树上的查找过程与折半查找过程类似;二叉排序树中左子树上所有结点的关键字值均小于它的根结点;对某棵二叉排序树进行中序遍历，一定能得到按关键字升序排列的有序序列;二叉排序树中右子树上所有结点的关键字值均大于它的根结点】8、问题：在一个结点值按照查找关键字有序排列的单链表上可以采用折半查找方法来提高查找速度。选项：A:错B:对答案:【错】9、问题：折半查找过程所对应的判定树一定是一棵平衡二叉树。选项：A:错B:对答案:【对】10、问题：在任意一个数据表上，采用折半查找一定比采用顺序查找的查找速度快。选项：A:错B:对答案:【错】11、问题：在结点数确定的二叉排序树上进行查找的平均查找长度与二叉树的形态有关，最好的情况是二叉排序树为平衡二叉树的时候。选项：A:对B:错答案:【对】12、问题：折半查找的效率与二叉排序树的查找效率是一样的。选项：A:错B:对答案:【错】第九章单元测试1、问题：对同一组数据分别采用直接插入排序和折半插入排序进行排序，二者可能存在的不同之处在于（）。选项：A:整个排序过程中的元素移动次数B:排序的总趟数C:整个排序过程中的关键字比较次数D:占用的辅助内存空间大小答案:【整个排序