知道智慧树数据结构（西安理工大学）满分测试答案

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