知道网课《数据结构（上海电力大学）》课后章节测试答案

第一章测试1【单选题】(2分)数据结构中，与所使用的计算机无关的是数据的（)结构。A.物理B.逻辑C.物理和存储D.存储2【单选题】(2分)从逻辑上可以把数据结构分为（）两大类。A.动态结构、静态结构B.顺序结构、链式结构C.初等结构、构造型结构D.线性结构、非线性结构3【单选题】(2分)算法分析的目的是（）A.分析算法的效率以求改进B.找出数据结构的合理性C.研究算法中的输入和输出的关系D.分析算法的易懂性和文档性4【多选题】(2分)一个"好"的算法应达到的目标有()。A.正确性B.健壮性C.高时间效率和低存储率D.可读性5【判断题】(2分)健壮的算法不会因非法的输入数据而出现莫名其妙的状态。A.对B.错6【判断题】(2分)数据的逻辑结构和数据的存储结构是相同的。A.对B.错7【判断题】(2分)算法的实现依赖于数据的逻辑结构。A.错B.对8【判断题】(2分)算法是对解题方法和步骤的描述。A.对B.错9【单选题】(2分)链式存储结构所占存储空间（）。A.只有一部分，存储表示结点间关系的地址。B.分两部分，一部分存放结点的值，另一个部分存放表示结点间关系的地址。C.只有一部分，存放结点的值。D.分两部分，一部分存放结点的值，另一部分存放结点所占存储单元值。10【单选题】(2分)下列时间复杂度中最坏的是（）。A.O（n）B.O（1）C.O(logn)D.O(n2)第二章测试1【单选题】(2分)在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：A.将n个结点从小到大排序B.删除第i个结点（1≤i≤n）C.在第i个结点后插入一个新结点（1≤i≤n）D.访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）2【单选题】(2分)链式存储结构的最大优点是A.无需预分配空间B.便于进行插入和删除操作C.便于随机存取D.存储密度高3【单选题】(2分)假设在顺序表{a0,a1,……,an－1}中，每一个数据元素所占的存储单元的数目为4，且第0个数据元素的存储地址为100，则第7个数据元素的存储地址是A.124B.128C.107D.1064【单选题】(2分)在一个单链表中的p和q两个结点之间插入一个新结点，假设新结点为s,则修改链的java语句序列是A.s.next=q;p.next=s;B.s.next=p;p.next=q;C.q.next=p;p.next=s;D.p.next=q;q.next=s;5【判断题】(2分)顺序存储方式的优点是存储密度大，且插入、删除运算效率高A.错B.对6【单选题】(2分)在单链表中，增加一个头结点的目的是为了A.标识表结点中首结点的位置B.方便运算的实现C.使单链表至少有一个结点D.说明单链表是线性表的链式存储7【单选题】(2分)一维数组第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是A.110B.108C.120D.1008【判断题】(2分)链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动A.错B.对9【判断题】(2分)链表的每个结点中都恰好包含一个指针A.错B.对10【判断题】(2分)顺序存储方式只能用于存储线性结构A.对B.错第三章测试1【单选题】(2分)若将整数1、2、3、4依次进栈，则不可能得到的出栈序列是A.1423B.1324C.4321D.12342【单选题】(2分)在顺序栈中，若栈顶指针top指向栈顶元素的下一个存储单元，且顺序栈的最大容量是maxSize，则顺序栈的判空条件是A.top==maxSizeB.top==0C.top==-1D.top==maxSize-13【单选题】(2分)在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，front指向队首元素，rear指向队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的判满条件是A.front==rearB.front!=rearC.front==(rear+1)%maxSizeD.front==rear+14【单选题】(2分)在链栈中，进行出栈操作时A.无需对栈作任何差别B.需要判断栈是否为空C.需要判断栈是否满D.需要判断栈元素的类型5【判断题】(2分)栈和队列是一种非线性数据结构A.对B.错6【单选题】(2分)在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的判空条件是A.front!=rearB.front==(rear+1)%maxSizeC.front==rearD.front==rear+17【单选题】(2分)循环顺序队列是将顺序队列的存储区域看成是一个首尾相连的环，首尾相连的状态是通过数学上的哪种运算实现的？A.除运算B.减运算C.求和D.求余8【单选题】(2分)设数组Data[0..m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为A.front=front+1B.rear=(rear+1)%mC.front=(front+1)%mD.front=(front+1)%(m+1)9【单选题】(2分)假定利用数组a[n]顺序存储一个栈，用top表示栈顶指针，top==-1表示栈空，并已知栈未满，当元素x进栈时所执行的操作为A.a[--top]=xB.a[top++]=xC.a[top--]=xD.a[++top]=x10【单选题】(2分)在不带表头结点的链栈中，若栈顶指针top直接指向栈顶元素，则将一个新结点p入栈时修改链的两条对应语句为A.p.next=top;top=p;B.top.next=p;p=top;C.top=p;p.next=top;D.p=top;top.next=p.next;第四章测试1【单选题】(2分)下面关于串的叙述中，哪一个是不正确的？()A.模式匹配是串的一种重要运算B.串既可以采用顺序存储，也可以采用链式存储C.串是字符的有限序列D.空串是由空格构成的串2【单选题】(2分)串的长度是指()A.串中包含的不同字符个数B.串中包含的不同字母个数C.串中除空格以外的字符个数D.串中包含的字符个数3【单选题】(2分)设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为()A.求串长B.联接C.求子串D.模式匹配4【单选题】(2分)设主串的长度为n，模式串的长度为m，则串匹配的KMP算法时间复杂度是()A.O(n+m)B.O(n)C.O(m)D.O(n×m)5【单选题】(2分)串也是一种线性表，只不过()A.表长受到限制B.数据元素数据类型不受限制C.数据元素是子串D.数据元素均为字符6【判断题】(2分)一个串的任意连续字符组成的子序列称为串的子串，该串称为主串。A.对B.错7【判断题】(2分)空串和空格串的串长度都为0。A.错B.对8【判断题】(2分)若两个串的长度相等且对应位置上的字符也相等，则称两个串相等。A.对B.错9【判断题】(2分)寻找子串在主串中的位置，称为模式匹配。其中，主串又称为模式串。A.对B.错10【判断题】(2分)模式串t="ababaab"的next[]数组值依次为-1、0、0、1、2、1、1。A.错B.对第五章测试1【单选题】(2分)设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主进行存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）A.18B.33C.13D.402【单选题】(2分)有一个二维数组A[1..6,0..7]，每个数组元素用相邻的6个字节存储，存储器按字节编址，那么这个数组占用的存储空间大小是（）个字节A.48B.288C.96D.2523【单选题】(2分)设有数组A[1..8,1..10]，数组的每个元素占3字节，数组从内存首地址BA开始以列序为主序顺序存放，则数组元素A[5，8]的存储首地址为（）A.BA+180B.BA+141C.BA+222D.BA+2254【单选题】(2分)稀疏矩阵的三元组存储表示方法（）A.比十字链表更高效B.实现转置操作很简单，只需将每个三元组中行下标和列下标交换即可C.是一种链式存储方法D.矩阵的非零元素个数和位置在操作过程中变化不大时较有效5【单选题】(2分)用十字链表表示一个稀疏矩阵，每个非零元素一般用一个含有（）域的结点表示A.2B.3C.5D.46【判断题】(2分)设数组A[1..5,1..6]的基地址为1000，每个元素占5个存储单元，若以行序为主序顺序存储，则元素A[5,5]的存储地址为1170。A.错B.对7【判断题】(2分)在稀疏矩阵的三元组顺序表存储结构中，除表示非零元的三元组表以外，还需要表示矩阵的行数、列数和非零元个数。A.错B.对8【判断题】(2分)一个n×n的对称矩阵，如果以相同的元素只存储一次的原则进行压缩存储，则其元素压缩后所需的存储容量为n(n-1)/2。A.错B.对9【判断题】(2分)对矩阵压缩的目的是为了节省存储空间。A.错B.对10【判断题】(2分)对于稀疏矩阵采用的三元组表和十字链表两种方法，其中非零元素的表示方法都是一样的。A.对B.错第六章测试1【单选题】(2分)有关二叉树下列说法正确的是（）A.二叉树中任何一个结点的度都为2B.一棵二叉树的度可以小于2C.二叉树的度为2D.二叉树中至少有一个结点的度为22【单选题】(2分)由3个结点可以构造出多少种不同的二叉树？（）A.4B.2C.3D.53【单选题】(2分)若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A.11B.不确定C.9D.154【单选题】(2分)利用二叉链表存储树时，根结点的右指针是（）A.指向最左孩子B.指向最右孩子C.非空D.空5【判断题】(2分)完全二叉树一定存在度为1的结点（）A.对B.错6【判断题】(2分)用二叉链表存储n个结点的二叉树时，结点的2n个指针中有n+1个空指针（）A.错B.对7【判断题】(2分)完全二叉树中，若一个结点没有左孩子，则它必是树叶（）A.错B.对8【单选题】(2分)一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（）A.是任意一棵二叉树B.所有的结点均无右孩子C.所有的结点均无左孩子D.只有一个叶子结点9【单选题】(2分)已知一棵二叉树的后序遍历序列为DABEC，中序遍历序列为DEBAC，则它的先序遍历序列为（）A.ACBEDB.CEDBAC.DEABCD.DECAB10【判断题】(2分)哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近（）A.对B.错第七章测试1【判断题】(2分)在AOE网中一定只有一条关键路径。A.对B.错2【判断题】(2分)对任意一个图，从某顶点出发进行一次广度优先遍历或深度优先遍历，可访问图的所有顶点。A.错B.对3【单选题】(2分)在一个有n个顶点的有向图中，若所有顶点的出度之和为s，则所有顶点的入度之和为（）。A.s-1B.sC.nD.s+14【单选题】(2分)对某个无向图的邻接矩阵来说，下列叙述正确的是()。A.矩阵中非全零行的行数等于图中的顶点数B.矩阵中的非零元素个数等于图中的边数C.第i行与第i列上的非零元素的总数等于顶点vi的度数D.第i行上的非零元素个数和第i列上的非零元素个数一定相等5【单选题】(2分)已知一个有向图的邻接矩阵，要删除所有以第i个顶点为孤尾的边，应该（）。A.将邻接矩阵的第i行删除B.将邻接矩阵的第i列删除C.将邻接矩阵的第i列元素全部置为0D.将邻接矩阵的第i行元素全部置为06【多选题】(2分)以下说法正确的是：（）。A.无向图中的极大连通子图称为连通分量B.图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点C.有向图的遍历不可以采用广度优先搜索方法D.图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点7【判断题】(2分)有向图中顶点V的度等于其邻接矩阵中第V行中的1的个数。A.对B.错8【单选题】(2分)含有n个顶点的连通图中的任意一条简单路径，其长度不可能超过（）。A.n/2B.n-1C.nD.19【单选题】(2分)设无向图G=（V，E）和G´=（V´，E´），如果G´是G的生成树，则下面说法的是（）。A.G´为G的连通分量B.G´为G的子图C.G´为G的无环子图D.G´为G的极小连通子图，且V=V´10【多选题】(2分)判断一个有向图是否存在回路，可以用（）。A.深度优先遍历算法B.广度优先遍历算法C.拓扑排序方法D.求最短路径的方法第八章测试1【单选题】(2分)在表长为ｎ的链表中进行线性查找，它的平均查找长度为A.ＡＳＬ＝ｎB.ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１C.ＡＳＬ＝（ｎ＋１）／２D.ＡＳＬ＝＋１2【单选题】(2分)折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中比较大小，查找结果是失败。A.30，88，50B.30，88，70，50C.20，70，30，50D.20，503【单选题】(2分)用线性探测法解决冲突问题时，所产生的一系列后继散列地址A.必须小于或等于原散列地址B.无具体限制C.必须大于或等于原散列地址D.可以大于或小于但不能等于原散列地址4【单选题】(2分)在关键字序列（12，23，34，45，56，67，78，89，91）中二分查找关键字为45、89和12的结点时，所需进行的比较次数分别为（）。A.4，3，3B.4，4，3C.3,4,4D.3,3,45【单选题】(2分)由同一关键字集合构造的各棵二叉排序树（）。A.其形态不一定相同，平均查找长度也不一定相同B.其形态均相同，平均查找长度也都相同C.其形态不一定相同，但平均查找长度相同D.其形态均相同，但平均查找长度不一定相同6【单选题】(2分)对于哈希函数H(key)=key%13，被称为同义词的关键字是（）。A.35和41B.25和51C.23和39D.15和447【单选题】(2分)设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为（）。A.41B.21C.62D.238【单选题】(2分)已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于（）。A.2.9B.3.4C.1.0D.5.59【多选题】(2分)构造散列函数时通常考虑的因素有A.关键字的分布情况B.散列表长C.计算函数的工作量D.关键字的长度10【判断题】(2分)二叉树为二叉排序树的充要条件是，其任意结点的值均大于其左孩子的值且小于其右孩子的值A.对B.错第九章测试1【单选题】(2分)排序方法中，从未排序序列中