电子科大15春 数据结构 在线作业123与答案

电子科大15春数据结构在线作业123与答案29a1c158-7162-11ec-b5c4-7cb59b590d7d电子科大15春数据结构在线作业123与答案电子科技大学，第十五春季和LBRACK；数据结构&rsqb；在线作业123和答案在线作业一：一、单选题（共16道试题，共48分。）已知指针P和Q分别指向单个链表中的第一个节点和最后一个节点。假设指针s指向另一个单链表中的节点，则在s引用的节点之后插入上述链表时要执行的语句为（）。a.q->next=s->next；s->next=pb.s->next=p；q->next=s->nextc、p-〉next=s-〉next；s-〉next=qd。s-〉next=q；p-〉next=s-〉next高度为5的完全二叉树中含有的结点数至少为（）。a、16b。17c。31d。323•设有两个串t和p,求p在t中首次出现的位置的串运算称作（）。a、连接B.子字符串C.字符定位D.子字符串定位正确答案：d对于哈希函数H（key）=key%13，名为synonym的关键字是（）。a.35和41b.23和39c、15和44d25和51算法分析的目的是（）。a、确定数据结构的合理性B.评估算法的效率c.研究算法中输入与输出的关系d.鉴别算法的可读性6•在头指针和表长度大于1的单循环链表中，指针P指向表中的一个节点。如果p-〉next-〉next=head,贝0（）。a、P指头部节点，B.P指尾部节点c.*p的直接后继是头结点d.*p的直接后继是尾结点数据结构为（）a.一种数据类型b.数据的存储结构c.一组性质相同的数据元素的集合d、相互之间有一个或多个特定关系的数据元素的集合采用两类不同存储结构的字符串可分别简称为()。a、主字符串和子字符串B.序列字符串和链字符串C.目标字符串和模式字符串D.变量字符串和常量字符串正确答案：B已知函数sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数scopy(s,t)的功能为复制串t到s。若字符串s二〃sciencestudy〃，则调用函数scopy(p,sub(s,l,7))后得到()。a、p=科学b.p=研究c.s二〃science〃d.s二〃study〃在头指针和表长度大于1的单循环链表中，指针P指向表中的一个节点。如果p-〉next-〉next=head,贝0()。a、P指头部节点，B.P指尾部节点c.*p的直接后继是头结点d.*p的直接后继是尾结点如果一棵二叉树有11个叶节点，则二叉树中有2个节点的节点数为()。a.10b.11c、12天。模棱两可的12•下面程序段的时间复杂度是()°for(i=0;ia、o(n)b.o(m+n+1)c.o(m+n)d.o(m*n)在线性表的下列运算中，不改变数据元素之间结构关系的运算是()。a、插入B.删除c.排序d.定位正确答案：D在计算机内实现递归算法时所需的辅助数据结构是()。a、堆栈B.队列c.树d.图在以单链表作为存储结构的线性表中，数据元素之间的逻辑关系由（）表示。a.数据元素的相邻地址表示b.数据元素在表中的序号表示c、指向后续元素的指针表示D。数据元素的值表示正确答案：c对于只在表的开头和结尾插入的线性表，适当的存储结构是（）。a.顺序表b.用头指针表示的单循环链表c、由尾部指针D表示的单循环链表。单循环链表二、多选题（共2道试题，共8分。）该算法具有以下特点（）。a.有穷性b.确定性c.可行性止输入和输出正确答案：ABCD一个好的算法有（abed）设计要求。a、正确性B.可读性c.健壮性d.效率与低存储量要求正确答案：ABCD三、判断题（共22道试题，共44分。）二叉树中的叶节点是二叉树中没有左右子树的节点。a、错误B.正确2•在队列中，允许进行删除操作的一端称为队尾。a•错误b•正确正确答案：B3•假设以s和x分别表示进栈和退栈操作，则对输入序列a,b,c,d,e进行一系列栈操作ssxsxssxxx之后，得到的输出序列为abbeeddede。a、错误B.正确空串的长度是0a.错误b.正确5•计算机内存中数据逻辑结构的表示称为数据逻辑结构。a、错误B.正确正确答案：a6•在深度为15的完整二叉树上，第11层有2J1个节点。a.错误b.正确如果输入顺序为1、3、5，。。。，97、99，输出序列的第一个元素是99，输出序列的第30个元素是47。a、错误B.正确字符串“sgabacbadfgbacst”中存在有6个与字符串“ba"相同的子串a.错误b.正确正确答案：a9•假设三维数组a[5][6][7]按行优先级顺序存储，其中元素a[0][0][0]的地址为1100，每个元素占用2个存储单元，则a[4][3][2]的地址为1264。a、错误B.正确当问题的规模n趋向无穷大时，算法执行时间t(n)的数量级被称为算法的时间复杂度。a、错误B.正确一棵含999个结点的完全二叉树的深度为12a.错误b.正确在队列中，允许插入的一端称为队列头。a.错误b.正确13•如果一棵完整的三叉戟树包含121个节点，则树的深度为6。a、错误B.正确正确答案：a导致冲突的两个关键字称为哈希函数的同义词。a、错误B.正确在二叉树的第i层上至多可以有2i个结点。a.错误b.正确给定不同的输入序列来构建二叉排序树，我们必须得到不同的二叉排序树。a、正确答案：a已知指针p指向某单链表中的一个结点，则判别该结点有且仅有一个后继结点的条件是p-〉next-〉next==null。a.错误b.正确如果堆栈进入顺序为a、B和C，并且堆栈进入和堆栈退出可以穿插，则可能有6个不同的堆栈退出顺序。。a.错误b.正确在长度为N的循环链表中，删除元素值为x的节点的时间复杂度为0(N)。a.错误b.正确20•在最好和最坏的情况下，时间复杂度为0(nlogn)，稳定的排序方法是堆排序。a.错误b.正确正确答案：a21•二叉树中最多只有两棵子树，并且有左右之分。a.错误b.正确正确答案：B22.不含任何字符的串称为空串。a.错误b.正确网上作业2:1。单选题(共16题，共48分)高度为5的完全二叉树中含有的结点数至少为()。a、16b。17c。31d。32二.二叉树中第5层上的结点个数最多为()。a、8b。15摄氏度。16天。323•在一个具有n个顶点的有向图中，所有顶点的出度之和为dout,则所有顶点的入度之和为()。a、杜特布。dout-1c。dout+1d。N在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用()。a、数据元素的相邻地址表示B.表中数据元素的序列号表示c.指向后继元素的指针表示d.数据元素的值表示已知堆栈的最大容量为4。如果堆栈进入顺序是1、2、3、4、5和6，并且堆栈进入和堆栈退出可以穿插，那么可能的堆栈退出顺序是()。a.5，4，3，2，1，6b.2，3，5，6，1，4c、3,2,5,4,1,6d。1，4，6，5，2，36•若算法中语句的最大频度为t(n)=2021n+6nlogn+29log2n，则其时间复杂度为()。a、o(logn)b.o(n)c.o(n)gn)d.o(log2n)7•下面程序段的时间复杂度为()°for(i=0;ia、o(m2)b.o(n2)c.o(m*n)d.o(m+n)采用两类不同存储结构的字符串可分别简称为（）。a、主字符串和子字符串B.序列字符串和链字符串C.目标字符串和模式字符串D.变量字符串和常量字符串正确答案：B对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为（）。a、序列表B.由标题指针表示的单循环链表c.用尾指针表示的单循环链表d.单链表具有18个节点的二叉树的高度应至少为（）。a.3b.4c.5d.6判断两个字符串大小的基本标准是（）。a.两个串长度的大小b.两个串中首字符的大小c、两个字符串中的大写字母数D.对应于已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为（）。a、Ob。lc。48d。4913•在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若P-〉next-〉next二头部，然后（）。a.p指向头结点b.p指向尾结点c、*P的直接后继节点是头节点，*P的直接后继节点是尾节点与线性表相比，串的插入和删除操作的特点是（）。a、通常，整个字符串用作操作对象。B.需要更多的辅助空间c.算法的时间复杂度较高d.涉及移动的元素更多抽象数据类型的三个组件是（）。a.数据对象、数据关系和基本操作b.数据元素、逻辑结构和存储结构c、数据项、数据元素和数据类型D.数据元素、数据结构和数据类型若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（）。a、3,2,6,1,4,5b。3,4,2,1,6,5c.1，2，5，3，4，6d.5，6，4，2，3，1二、多项选择题（共2题,共8分）构造最小生成树的两个基本算法是（）。a、Prim算法B.kruskar算法C.dijestra算法D.哈希算法正确答案：ab由于排序过程涉及的内存不同,排序方法可分为（）。a.稳定排序b.不稳定排序c、内部排序D.外部排序正确答案：cd三、判断题（共22题,总分44分）含n个顶点的无向连通图中至少含有n条边。a.错误b.正确2•包含999个节点的完整二叉树的深度为6。a、错误B.正确在最好和最坏情况下的时间复杂度均为o（nlogn）且稳定的排序方法是基数排序。а、错误B.正确4•在含100个结点的完全二叉树中，叶子结点的个数为36。a.错误b.正确二叉树中的叶节点是二叉树中没有左右子树的节点。a、错误B.正确б.设s1="good"s2=""s3="book",则s1,s2和s3依次联接后的结果是"goodbook"。a、错误B.正确7•假设以行优先顺序存储三维数组a[5][6][7],其中元素a[0][0][0]的地址为1100,并且每个元素占2个存储单元，则a[4][3][2]的地址是1264。a.错误b.正确如果堆栈序列是1,3,5,。。。,97,99,堆栈序列的第一个元素是99,堆栈序列的第30个元素是47。a、错误B.正确二叉树是度为2的有序树。a.错误b.正确队列的尾部位置通常随队列加入操作而变化。a、错误B.正确串s=”iamaworker〃的长度是10。a.错误b.正确在文本编辑程序中找到特定单词在文本中的位置，可以使用字符串的定位操作。a.错误b.正确根据先进先出的原则修改队列。a、错误B•正确两个串相等的充分必要条件是两个串的长度相等且字母相同。a.错误b.正确正确答案：b堆栈下溢指堆栈为空时的堆栈外操作。A.错误B.正确给出不同的输入序列建造二叉排序树，一定得到不同的二叉排序树。a.错误b.正确正确答案：a如果链节点中的指针占4字节，每个字符占1字节，则节点大小为2的链的存储密度为2/6。a、错误B.正确一个具有4个顶点的无向完全图有6条边。a.错误b.正确数据的逻辑结构描述了数据元素之间的逻辑关系，与存储模式无关。a、正确答案:B产生冲突现象的两个关键字称为该散列函数的同义字。a.错误b.正确如果已知指针P指向单个链表中的节点，则判断该节点有且只有一个后续节点的条件是P-〉next-〉next==null。a、错误B.正确22•假设三维数组a[10][9][8]按行优先顺序存储，若每个元素占3个存储单元，并且首地址为100,则元素a[9][8][7]的存储地址是501。a.错误b.正确在线作业3:1。单选题（共16题，共48分）1•在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next-〉next=head,贝0（）。a、P指头部节点，B.P指尾部节点c.*p的直接后继是头结点d.*p的直接后继是尾结点已知指针P和Q分别指向单个链表中的第一个节点和最后一个节点。假设指针s指向另一个单链表中的节点，则在s引用的节点之后插入上述链表时要执行的语句为（）。a.q-〉next=s-〉next；s-〉next=pb.s-〉next=p；q-〉next=s-〉nextc、p—〉next=s—〉next；s—〉next=qd。s—〉next=q；p—〉next=s—〉next对于有向图，其邻接矩阵表示相比邻接表表示更易于进行的操作为（）。a、求顶点的邻接点B.求顶点的阶C.深度优先遍历D.宽度优先遍历若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（）。a、3,2,6,1,4,5b。3,4,2,1,6,5c.1，2，5，3，4，6d.5，6，4，2，3，15•以下程序段的时间复杂度为（）。对于（i=O；ia.o（m2）b.o（n2）c.o（m*n）d.o（m+n）6•执行以下程序段后，字符串x的值为（）°s=“abcdefgh”；t=“xyzw”；substr（x,s,2,strlen（t））；substr（y,s,stelen（t）,2）；strcat（x,y）；〃1r1//1//1〃〃1r//1//1rP//a.cdefghb.cdxyzwc.cdefxyd.cdefef7•二叉树第5层上的最大节点数为（）。a.8b.15c.16d.32已知一棵有50个节点的二叉树中只有一个叶节点，那么树中有1个节点的节点数为（）。a.0b.1c.48d.49team和stack之间的主要区别是（）。a.逻辑结构不同b.存储结构不同c、包含的操作数量不同。D.限制插入和删除的位置不同判断两个串大小的基本准则是（）。a、两个字符串长度的大小B.两个字符串中第一个字符的大小c.两个串中大写字母的多少d.对应的第一个不等字符的大小在有n个顶点的有向图中，如果所有顶点的向外度之和为dout,则所有顶点的向内度之和为（）。a.doutb.dout-1c.dout+1d.n如果数据结构中的每个数据元素只能有一个直接前驱体，但可以有多个直接后继体，则结构为（）。a.栈b.队列c.树d.图从序列表中删除元素时，表中删除元素后的所有元素必须为（）。a.前移一个位置b.后移一个位置c.不动止视情况而定与线性表相比，字符串插入和删除的特点是（）。a.通常以串整体作为操作对象b.需要更多的辅助空间c、该算法的时间复杂度较高，涉及的运动元素较多若线性表的插入和删除操作频繁地在表头或表尾位置进行，则更适宜采用的存储结构为（）。a、无头节点的双向链表B.带尾指针的循环链表c.无头结点的单链表止带头指针的循环链表已知一棵完整的二叉树有64个叶节点，那么树的最大可能深度是（）。a.7b.8c.9d.10二、多项选择题（共2题，共8分）一.一个好的算法有（）设计要求。a、正确性B.可读性C.健壮性D.效率和低存储要求正确答案：abcd由于排序过程涉及的内存不同，排序方法可分为（）。a.稳定排序b.不稳定排序c.内部排序止外部排序正确答案：CD三、判断题（共22道试题，共44分。）1•给不同的输入序列建立一个二叉排序树，你会得到不同的二叉排序树。a、正确答案:a有向图用邻接矩阵表示后，顶点i的入度等于邻接矩阵中第i列的元素个数。a、错误B.正确抽象数据类型是指数据逻辑结构及与之相关的操作。a.错误b.正确4•包含999个节点的完整二叉树的深度为12。a、错误B.正确在一个长度为100的顺序表中删除第10个元素时，需移动90个元素。a、错误B.正确字符串“sgabacbadfgbac