【MOOC】数据结构与算法-西安邮电大学 中国大学慕课MOOC答案

【MOOC】数据结构与算法-西安邮电大学中国大学慕课MOOC答案测验11、【单选题】数据的逻辑结构有几种？本题答案：【4】2、【单选题】数据的存储结构包括？本题答案：【顺序结构和非顺序结构】测验11、【单选题】数据的逻辑结构包括？本题答案：【线性结构和非线性结构】测验1、【判断题】数据结构包括数据的逻辑结构、存储结构以及相关运算。本题答案：【正确】测验1、【判断题】数据的逻辑结构和机器无关。本题答案：【正确】测验1、【判断题】时间复杂度和频度是一样的。本题答案：【错误】测验1、【判断题】一个算法包含的循环嵌套的层数越多，该算法的时间复杂度越高。本题答案：【正确】单元作业1在线练习11、【单选题】在数据结构中，与所使用的计算机无关的是数据的（）的结构。本题答案：【逻辑】2、【单选题】数据结构在计算机内存中的表示是指（）。本题答案：【数据的存储结构】3、【单选题】在数据结构中，从逻辑上可以将之分为（）结构。本题答案：【线性和非线性结构】4、【单选题】在数据结构中，从存储上可以将之分为（）结构。本题答案：【顺序和非顺序结构】5、【单选题】算法的时间复杂度取决于（）。本题答案：【问题的规模以及待处理数据的初态】6、【单选题】某算法的时间复杂度是O(n^2)，表明该算法的（）。本题答案：【执行时间与n^2成正比】7、【单选题】衡量算法效率优劣的不包括（）。本题答案：【现实性】8、【单选题】算法指（）。本题答案：【解决问题的步骤序列】9、【单选题】下面的程序段时间复杂度为（）。for(i=1;in;i++)for(j=1;jn;j++)x=x+1;本题答案：【O(n^2)】10、【单选题】算法效率分析的两个主要方面是（）。本题答案：【空间复杂度和时间复杂度】11、【单选题】有如下递归函数fact(n)，分析其时间复杂度为（）。intfact(intn){if(n=1)return1;elsereturn(n*fact(n-1));}本题答案：【O(n)】12、【单选题】下面程序段的时间复杂度为（）。for(i=0;in;i++)for(j=0;jm;j++)A[i][j]=0;本题答案：【O(n*m)】13、【单选题】下面程序段的时间复杂度为（）。voidsum(intn)//n为正整数{intp=1,sum=0,i;for(i=1;i=n;i++){p*=i;sum+=p;}}本题答案：【O(n)】14、【判断题】顺序存储方式的优点是存储密度大，且插入、删除运算效率高。本题答案：【错误】15、【判断题】算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。本题答案：【错误】16、【判断题】链式存储的优点是可以随机存储。本题答案：【错误】17、【判断题】在相同的数据规模n下，复杂度为O(n)的算法在时间上总是优于复杂度为O()的算法。本题答案：【正确】18、【判断题】数据的逻辑结构分为线性结构、树型结构、图状结构和集合。本题答案：【正确】19、【判断题】数据的存储结构表示的是数据元素之间的逻辑关系。本题答案：【错误】测验1、【判断题】顺序表是指按照顺序方式进行存储的线性表。本题答案：【正确】测验1、【判断题】单链表的插入、删除效率优于顺序表。本题答案：【正确】测验1、【判断题】单链表的头插建立算法也称为反向建立单链表。本题答案：【正确】测验1、【判断题】带尾指针的循环链表比带头指针的循环链表更便于运算。本题答案：【正确】测验1、【判断题】在双向链表中查找某一结点的前驱或者后继，都非常方便。本题答案：【正确】单元作业2在线练习21、【单选题】下述哪一条是顺序存储结构的优点（）。本题答案：【随机存取】2、【单选题】下面关于线性表叙述中错误的是（）。本题答案：【线性表采用顺序存储，便于进行插入和删除操作。】3、【单选题】若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。本题答案：【顺序表】4、【单选题】设某顺序表中第一个元素的存储地址是Base，下限值为1，每个结点占m个单元，则第i个结点的存储地址为（）。本题答案：【Base+(i-1)×m】5、【单选题】某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。本题答案：【仅有尾指针的单循环链表】6、【单选题】设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用()最节省时间。本题答案：【带头结点的双循环链表】7、【单选题】链表不具有的特点是（）。本题答案：【可随机访问任意元素】8、【单选题】线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。本题答案：【连续或不连续都可以】9、【单选题】静态链表中指针表示的是（）。本题答案：【下一元素在数组中的下标】10、【单选题】若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）。本题答案：【O(n)】11、【单选题】对于顺序表，访问结点和删除结点的时间复杂度分别为（）。本题答案：【O(1)O(n)】12、【单选题】在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（）。本题答案：【s-next=p-next;p-next=s;】13、【单选题】对于一个带头结点的单链表，其头指针为head，判定该表为空表的条件是（）。本题答案：【head→next==NULL】14、【单选题】将两个各有n个元素的有序表合并成一个有序表，其最少的比较次数是（）。本题答案：【n】15、【单选题】在双向链表中，在p所指向的结点前插入一个q所指向的结点，相应的操作语句是（）。注：双向链表的结点结构为(prior，data，next)。本题答案：【q-next=p;q-prior=p-prior;p-prior-next=q;p-prior=q;】16、【单选题】线性表（a1,a2,…,an）以链式方式存储时，访问第i个元素的时间复杂度为（）本题答案：【O（n）】17、【单选题】头指针为H的循环单链表中尾结点P的特点是（）。本题答案：【P-next=H】18、【单选题】两个指针P和Q，分别指向单链表的两个结点，P是Q的前驱结点的条件是（）。本题答案：【P-next==Q】19、【单选题】在单链表中，增加头结点的目的是（）。本题答案：【链表判空、插入第一个结点以及删除第一个结点等运算方便】20、【单选题】下面关于线性表的叙述中，错误的是（）。本题答案：【链表可以随机存取任一元素】21、【单选题】设p为指向长度为n的单循环链表上某结点的指针，则找到p的直接前驱（）。本题答案：【时间复杂度为O（n）】22、【单选题】以下关于线性表的论述，不正确的是（）。本题答案：【线性表中的每个结点都有且仅有一个直接前趋和一个直接后继。】23、【单选题】在（）的运算中，使用顺序表比链表好。本题答案：【根据序号查找】24、【判断题】静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。本题答案：【正确】25、【判断题】线性表的特点是每个元素都有一个前驱和一个后继。本题答案：【错误】26、【判断题】若长度为n的线性表采用顺序存储结构，找到其中第i个元素的时间复杂度为O(n)。本题答案：【错误】27、【判断题】已知带头结点的双向循环链表L，判断其为空表的条件是L-next==LL-prior==L。本题答案：【正确】28、【判断题】顺序表的插入、删除运算更方便。本题答案：【错误】29、【判断题】链表的性能优于顺序表。本题答案：【错误】30、【判断题】顺序表适宜于顺序存取，而链表适宜于随机存取。本题答案：【错误】31、【判断题】顺序表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。本题答案：【错误】32、【判断题】插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用。本题答案：【错误】33、【判断题】线性表的链式存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。本题答案：【正确】测验1、【判断题】栈的特点是先进先出。本题答案：【错误】测验1、【判断题】双端栈有效地共享了存储空间。本题答案：【正确】测验1、【判断题】汉诺塔问题可以使用递归算法来完成。本题答案：【正确】测验1、【判断题】迷宫问题的非递归实现借助的是栈这种结构。本题答案：【正确】测验1、【判断题】队列的特点是先进后出。本题答案：【错误】测验1、【判断题】采用链式结构存储的队列称之为链队列。本题答案：【正确】测验1、【判断题】在表达式求值问题中，我们使用运算符栈和运算数栈协同工作完成整个表达式的求解过程。本题答案：【正确】单元作业3单元测试11、【单选题】栈和队列的共同点是（）。本题答案：【只允许在端点处插入和删除元素】2、【单选题】栈和队都是（）。本题答案：【限制存取点的线性结构】3、【单选题】依照六个元素6，5，4，3，2，1的顺序进栈，下列哪一个出栈序列不可能（）。本题答案：【346521】4、【单选题】设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后随即进入队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1，则栈S的容量至少应该是()。本题答案：【3】5、【单选题】设计一个判别表达式中括号是否匹配出现的算法，采用（）的数据结构最佳。本题答案：【栈】6、【单选题】表达式a*(b+c)-d的后缀表达式是(）。本题答案：【abc+*d-】7、【单选题】函数递归调用时，处理参数及返回地址需要用一种（）的数据结构。本题答案：【栈】8、【单选题】若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为3和1，当从队列中删除一个元素再加入两个元素后，rear和front的值为()。本题答案：【5和2】9、【单选题】最大容量为n的循环队列，队尾指针为rear，队头指针为front，则队空的条件是（）。本题答案：【rear==front】10、【单选题】假设以数组A[m]存放循环队列的元素,其头、尾指针分别为front和rear，front指示实际的队头元素，rear指向实际队尾元素的下一个元素位置，则当前队列中的元素个数为（）。本题答案：【(rear-front+m)%m】11、【单选题】用带头结点的表长大于1的单链表表示队列时，其队头指针指向队头结点，其队尾指针指向队尾结点，则在进行删除操作时()。本题答案：【仅修改队头指针】12、【单选题】下列说法正确的是（）。(1)只有使用了局部变量的递归函数在转换成非递归函数时才必须使用栈。(2)队列是插入与删除操作在表的两端进行的线性表，具有先进后出的特点。(3)队列是一端进行删除另外一端进行插入的线性表。(4)循环队列也存在空间溢出问题。本题答案：【(3)(4)】13、【单选题】以下程序的输出结果为（）。intf(intx){return(x0)?x*f(x-1):2;}voidmain(){inti;i=f(f(1));printf(%d,i);}本题答案：【4】14、【单选题】若一个栈以数组V[0..n-1]存储，初始栈顶指针top为n，则下面关于元素x进栈的正确操作是()。本题答案：【top=top-1;V[top]=x;】15、【单选题】一个递归算法必须包括（）。本题答案：【递归条件和递归体】16、【单选题】输入序列为ABC，想要得到CBA的输出结果，可以经过的栈操作为（）。本题答案：【push,push,push,pop,pop,pop】17、【单选题】一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是（）。本题答案：【54132】18、【单选题】一个栈的输入序列为1,2,3,…,n，若输出序列的第一个元素是i，则输出第j（1=j=i）个元素是（）。本题答案：【i-j+1】19、【单选题】在双向链表（结点包括：data,prior,next）中，删除指针p所指向的结点时须修改指针（）。本题答案：【p-prior-next=p-next;p-next-prior=p-prior;】20、【单选题】以下说法错误的是（）。本题答案：【对循环链表来说，从表中任意结点出发都能通过前后操作而扫描到整个循环链表。】21、【单选题】对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度和在给定值为x的结点后插入一个新结点的时间复杂度分别为（）。本题答案：【O(1),O(n)】22、【单选题】循环队列存储在数组A[0..m-1]中，则入队时rear应该变化为（）。本题答案：【rear=(rear+1)modm;】23、【单选题】当利用大小为n的数组顺序存储一个栈时，假定用top=n表示栈空，则每次向这个栈插入一个元素时，首先应执行（）语句修改top指针。本题答案：【top--;】24、【单选题】若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。本题答案：【顺序表】25、【单选题】链表不具有的特点是（）。本题答案：【可随机访问任意元素】26、【单选题】设某顺序表中第一个元素的地址是Base，下标从1开始，每个结点占m个单元，则第i个结点的地址为（）。本题答案：【Base+(i-1)×m】27、【单选题】在下面的程序段中，对x的赋值语句的频度为（）。for(i=1;in;i++)for(j=1;jn;j++)x=x+1;本题答案：【O(n^2)】28、【单选题】数据结构在计算机内存中的表示是指（）。本题答案：【数据的存储结构】29、【判断题】消除递归不一定需要使用栈，此说法（）。本题答案：【正确】30、【判断题】两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出，应把两个栈的栈底分别设在这片内存空间的两端。（）本题答案：【正确】31、【判断题】顺序栈因为是顺序存储，所以可以随机存取栈中任意元素。（）本题答案：【错误】32、【判断题】任何一个递归过程都可以转换成非递归过程。（）本题答案：【正确】33、【判断题】两顺序栈共享空间，也存在空间溢出问题。（）本题答案：【正确】34、【判断题】栈和队列都是线性表，只是在插入和删除时受到了一些限制。（）本题答案：【正确】35、【判断题】栈和队列的存储方式，既可以是顺序方式，也可以是链式方式。（）本题答案：【正确】36、【判断题】线性表的链式存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。本题答案：【正确】37、【判断题】顺序表适宜于顺序存取，而链表适宜于随机存取。本题答案：【错误】38、【判断题】顺序存储方式的优点是存储密度大，且插入、删除运算效率高。本题答案：【错误】测验1、【判断题】串是一种特殊的线性表。本题答案：【正确】测验1、【判断题】串的简单模式匹配算法的时间复杂度达到平方阶。本题答案：【正确】测验1、【判断题】KMP算法最终只需要讨论模式串本身就可以。本题答案：【正确】测验1、【判断题】模式串ababc对应的next值为01123。本题答案：【正确】单元作业4在线练习41、【单选题】下面关于串的叙述不正确的是（）。本题答案：【空串是由空格构成的串】2、【单选题】串是一种特殊的线性表，其特殊性体现在（）。本题答案：【数据元素是字符】3、【单选题】若串S='software',其前缀真子串的数目是（）。本题答案：【7】4、【单选题】串的长度是指（）。本题答案：【串中所含字符的个数】5、【单选题】两个串相等的充要条件是（）。本题答案：【两个字符串的长度相等且对应位置上的字符也相等】6、【单选题】设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）。本题答案：【串的模式匹配】7、【单选题】已知串S=‘aaab',其next函数值为（）。本题答案：【0123】8、【单选题】模式串‘ababaaababaa'的next函数值为（）。本题答案：【011234223456】9、【单选题】函数strcmp('stcabuc','stbabuc')的返回值是（）。本题答案：【1】10、【单选题】模式串t=‘abcaabbcabcaabdab'，该模式串的next函数值为（）。本题答案：【01112231123456712】11、【单选题】假设空串是任何串的子串，则串S='Computer'的子串个数是（）。本题答案：【37】12、【单选题】StrIndex（‘DATASTRUCTURE'，1,‘STR'）=（）。本题答案：【5】13、【单选题】设正文串长度为n，模式串长度为m，则模式匹配的KMP算法的时间复杂度为（）。本题答案：【O(m+n)】14、【单选题】StrIndex(‘IndexofString’,1,‘Str’）=()。本题答案：【10】15、【单选题】SubStr('IlikeUniversity',8,3)的返回值是（）。本题答案：【Uni】16、【单选题】设S=，则LenStr(S)=（）。本题答案：【0】17、【单选题】设目标串T=aabaababaabaa，模式P=abab，朴素匹配算法的外层循环进行了()次。本题答案：【5】18、【单选题】S1='good'，S2='morning'，执行函数SubStr(S2,4,LenStr(S1))后的结果为()。本题答案：【'ning'】19、【单选题】若串S='SOFT'，其子串的数目最多是（）。本题答案：【11】20、【单选题】以下论述正确的是（）。本题答案：【空串是零个字符的串】21、【单选题】设串S1='IAM'，S2='ASTUDENT'，则ConcatStr(S1,S2)=()。本题答案：【'IAMASTUDENT'】22、【单选题】设串S1='ABCDEFG'，S2='PQRST',则ConcatStr(SubStr(S1,2,LenStr(S2)),SubStr(S1,LenStr(S2),2))的结果串为()。本题答案：【'BCDEFEF'】23、【单选题】设有三个串S1、S2和S3，则StrReplace(S1,S2,S3)运算称作()。本题答案：【串替换】24、【单选题】以下论断正确的是()。本题答案：【是空串，空格串】25、【单选题】某串的长度小于一个常数，则采用（）存储方式最节省空间。本题答案：【顺序】26、【判断题】串是一种数据对象特殊的线性表。本题答案：【正确】27、【判断题】KMP算法的特点是在模式匹配时指示主串的指针不会回溯。本题答案：【正确】28、【判断题】设模式串的长度为m,目标串的长度为n，当n≈m且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。本题答案：【正确】29、【判断题】模式串P=‘abaabcac'的next函数值序列为01122312本题答案：【正确】30、【判断题】串的存储结构有顺序串、堆串和块链串三种。本题答案：【正确】31、【判断题】如果一个串中所有的字母均在另一个串中出现，则说明前者是后者的子串。本题答案：【错误】32、【判断题】串中任意个字符组成的子序列称为该串的子串。本题答案：【错误】33、【判断题】如果两个串含有相同的字符，则说明它们相等。本题答案：【错误】34、【判断题】子串的定位运算称为串的模式匹配。本题答案：【正确】35、【判断题】串'student'和'Student'相等。本题答案：【错误】测验1、【判断题】n维数组可以看成是由“n-1维数组”的数组元素构成的一维数组。本题答案：【正确】测验1、【判断题】为了节省存储空间，我们经常对特殊矩阵和稀疏矩阵进行压缩存储。本题答案：【正确】测验1、【判断题】采用三元组顺序表存储的稀疏矩阵，利用快速转置算法，时间复杂度可以达到线性阶。本题答案：【正确】测验1、【判断题】任何一个非空的广义表其表尾一定还是一个广义表。本题答案：【正确】单元作业5在线练习51、【单选题】设有一个10阶的对称矩阵A，采用下三角的压缩存储方式，以行序为主序，a[1][1]为第一元素，其存储地址为1，每个元素占一个地址空间，则a[8][5]的地址为（）。本题答案：【33】2、【单选题】设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主序存放时，元素A[5][8]的存储首地址为()。本题答案：【BA+180】3、【单选题】假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数组元素占2个存储单元，基地址为10，则arry[5][5]的地址为（）。本题答案：【818】4、【单选题】二维数组A的每个元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放A至少需要（）个字节。本题答案：【540】5、【单选题】二维数组A的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则A的第8列和第5行共占（）个字节。本题答案：【108】6、【单选题】二维数组A的每个元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则如果A按行存放元素A[8][5]的起始地址与A按列存放时元素（）的起始地址一致。本题答案：【A[3][10]】7、【单选题】若对n阶对称矩阵A，下标从1开始，以行序为主序方式将其下三角形的元素依次存放于一维数组B［1..(n(n+1))/2］中，则在B中确定a[i][j](1≤i，j≤n，且i≤j)的位置k的计算公式为()。本题答案：【j(j-1)/2+i】8、【单选题】若对n阶对称矩阵A，下标从1开始，以列序为主序方式将其上三角形的元素依次存放于一维数组B［1..(n(n+1))/2］中，则在B中确定a[i][j](1≤i，j≤n，且i≤j)的位置k的计算公式为()。本题答案：【j(j-l)/2+i】9、【单选题】设二维数组A[1..m，1..n]（即m行n列）按行存储在数组B[1..m*n]中，则二维数组中元素A[i][j]在一维数组B中的下标为()。本题答案：【（i-1）n+j】10、【单选题】有一个100*90的稀疏矩阵，非零元素（int型）有10个，假设int型占2个字节，则用三元组顺序表表示该矩阵时所需的字节数是（）。本题答案：【66】11、【单选题】对稀疏矩阵进行压缩存储的目的是（）。本题答案：【节省存储空间】12、【单选题】已知广义表L=（（x,y,z），a，（u，t，w）），从L表中取出原子项t的运算是（）。本题答案：【head（tail(head（tail（tail（L）））））】13、【单选题】广义表A=(a,b,(c,d),(e,(f,g))),则Head(Tail(Head(Tail(Tail(A)))))的值为（）。本题答案：【d】14、【单选题】设广义表L=（（a,b,c）），则L的长度和深度分别为（）。本题答案：【1和2】15、【单选题】下面说法不正确的是()。本题答案：【广义表的表头总是一个广义表】16、【单选题】广义表运算式Tail(((a,b),(c,d)))的操作结果是（）。本题答案：【((c,d))】17、【单选题】广义表（a,(b,c),d,e）的表头为（）。本题答案：【a】18、【单选题】广义表（（a,b,c,d））的表尾是（）。本题答案：【（）】19、【单选题】数组A[0..4,-3..-1,5..7]中含有元素的个数（）。本题答案：【45】20、【单选题】数组A[0..5,0..6]的每个元素占5个字节，将其按列序为主序存储在起始地址为1000的内存单元中，则元素A[5][5]的地址是()。本题答案：【1175】21、【单选题】将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1‥298]中，元素A[66][65]在B数组中的位置K为（）。本题答案：【195】22、【单选题】已知广义表:A=(a,b),B=(A,A),C=(a,(b,A),B),求tail(head(tail(C)))=()。本题答案：【((a,b))】23、【单选题】在稀疏矩阵的三元组顺序表中，每个三元组表示（）。本题答案：【矩阵中非零元素的行号、列号和数据值】24、【单选题】对矩阵进行压缩存储后，（）矩阵会失去随机存取的优点。本题答案：【稀疏矩阵】25、【单选题】经常对数组进行的两种基本操作是____。本题答案：【查找和修改】26、【单选题】假设整型数组A[1..8，-2..6，0..6]，按行优先存储，第一个元素的首地址是78，每个数组元素占用4个存储单元，那么元素A[4][2][3]的存储首地址为____。本题答案：【958】27、【单选题】tail（head（（（a,b,c,d,e））））=__________。本题答案：【(b,c,d,e)】28、【判断题】从逻辑结构上看，n维数组的每个元素均属于n个向量。本题答案：【正确】29、【判断题】多维数组可以看作是一种特殊的线性表。本题答案：【正确】30、【判断题】数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。本题答案：【错误】31、【判断题】一个稀疏矩阵Am*n采用三元组顺序表形式表示，若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了Am*n的转置运算。本题答案：【错误】32、【判断题】广义表B=(a,B)=(a,(a,(a,×××,)))的长度为无穷大。本题答案：【错误】33、【判断题】一个广义表可以为其它广义表所共享。本题答案：【正确】34、【判断题】一个广义表的表尾一定还是个广义表。本题答案：【错误】35、【判断题】稀疏矩阵中非零元素的个数远小于矩阵中元素的总数。本题答案：【正确】测验1、【判断题】在任何一棵二叉树中，度为0的结点数等于度为2的结点数-1。本题答案：【错误】测验1、【判断题】完全二叉树采用顺序存储是比较方便的。本题答案：【正确】测验1、【判断题】二叉树的按层次遍历算法可以采用递归算法实现。本题答案：【错误】测验1、【判断题】根据二叉树的前序和后序遍历结果可以恢复出一棵二叉树。本题答案：【错误】测验1、【判断题】二叉树的非递归遍历算法借助了栈这种结构。本题答案：【正确】测验1、【判断题】在线索二叉树中，有n+1个线索。本题答案：【正确】测验1、【判断题】在中序线索树中找结点的直接前驱，实际是找左子树中“最右下端”的结点。本题答案：【正确】测验1、【判断题】树的双亲表示法采用的是顺序存储结构。本题答案：【正确】测验1、【判断题】树的后序遍历结果和对应的二叉树的中序遍历结果相同。本题答案：【正确】测验1、【判断题】哈夫曼树中叶子结点数为n，那么内部结点数为n+1。本题答案：【错误】测验1、【判断题】哈夫曼编码是前缀编码。本题答案：【正确】测验1、【判断题】哈夫曼编码是从叶子到根进行编码的。本题答案：【正确】单元测试21、【单选题】树最适合用来表示的结构是（）。本题答案：【元素间具有分支及层次关系的结构】2、【单选题】设一棵二叉树的结点个数为18，则它的高度至少为（）。本题答案：【5】3、【单选题】任意一棵二叉树的叶子结点在其先序、中序、后序序列中的相对位置（）。本题答案：【肯定不发生变化】4、【单选题】判断线索二叉树中某结点p有左孩子的条件是（）。本题答案：【p-LTag==0】5、【单选题】设森林T中有4棵树，其结点个数分别为n1,n2,n3,n4，那么当森林T转换成一棵二叉树后，则根结点的右子树上有（）个结点。本题答案：【n2+n3+n4】6、【单选题】由权值分别为9、2、5、7、4的5个叶子结点构造一棵哈夫曼树，则该树的带权路径长度为（）。本题答案：【60】7、【单选题】设T是一棵哈夫曼树，有8个叶结点，则树T的高度最高可以是（）。本题答案：【8】8、【单选题】以下属于前缀编码的是（）。本题答案：【{0,1101,1110,1100,1111}】9、【单选题】算术表达式a+b*（c+d/e）转为后缀表达式为（）。本题答案：【abcde/+*+】10、【单选题】设树T的度为4，其中度为1,2,3和4的结点个数分别为4,2,1,1，则T中的叶子数为（）。本题答案：【8】11、【单选题】一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。本题答案：【108】12、【单选题】一棵具有N个结点的二叉树采用二叉链表进行存储，其中空指针域有()个。本题答案：【N+1】13、【单选题】深度为K的二叉树中结点总数（）。本题答案：【】14、【单选题】已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有（）个叶子结点。本题答案：【12】15、【单选题】以数据集{4，5，6，7，10，12，18}为叶结点权值所构造的哈夫曼树，其带权路径长度为（）。本题答案：【165】16、【单选题】已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为（）。本题答案：【-+A*BC/DE】17、【单选题】若一个具有n个结点k条边的无向图是一个森林（nk），则该森林必有（）棵树。本题答案：【n-k】18、【单选题】一棵二叉树结点的（）可唯一确定一棵二叉树。本题答案：【前序序列和中序序列】19、【单选题】设a=6,b=4,c=2,d=3,e=2，则后缀表达式abc-/de*+的值为（）。本题答案：【9】20、【单选题】若二叉树有n个结点，当执行中序遍历的递归程序时，在最坏情况下为处理递归调用所设的栈需要（）个单元。本题答案：【n-1】21、【单选题】具有64个结点的完全二叉树的深度为（）。本题答案：【7】22、【单选题】A，B为一棵二叉树上的两个结点，在中序遍历时，A在B前的条件是（）。本题答案：【A在B左方】23、【单选题】把一棵树转换为二叉树后，这棵二叉树的形态是（）。本题答案：【唯一的】24、【单选题】下列陈述正确的是（）。本题答案：【二叉树中最多只有两棵子树，且有左右子树之分】25、【单选题】在哈夫曼树中，若编码长度只允许小于等于4，则除了已确定两个字符的编码为0和10外，还可以最多对个字符进行编码。本题答案：【4】26、【单选题】若串S='software',其前缀真子串的数目是（）。本题答案：【7】27、【单选题】模式串‘ababaaababaa'的next函数值为（）。本题答案：【011234223456】28、【单选题】StrIndex(‘IndexofString’,1,‘Str’）=()。本题答案：【10】29、【单选题】设串S1='IAM'，S2='ASTUDENT'，则ConcatStr(S1,S2)=()。本题答案：【'IAMASTUDENT'】30、【单选题】设有三个串S1、S2和S3，则StrReplace(S1,S2,S3)运算称作()。本题答案：【串替换】31、【单选题】假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数组元素占2个存储单元，基地址为10，则LOC[5，5]=（）。本题答案：【818】32、【单选题】有一个100*90的稀疏矩阵，非零元素（int型）有10个，假设int型占2个字节，则用三元组顺序表表示该矩阵时所需的字节数是（）。本题答案：【66】33、【单选题】广义表（a,(b,c),d,e）的表头为（）。本题答案：【a】34、【单选题】数组A[0..4,-1..-3,5..7]中含有元素的个数（）。本题答案：【45】35、【单选题】对下述矩阵进行压缩存储后，失去随机存取功能的是（）。本题答案：【稀疏矩阵】36、【判断题】完全二叉树一定存在度为1的结点。本题答案：【错误】37、【判断题】一棵树中的叶子数一定等于与其对应的二叉树的叶子数。本题答案：【错误】38、【判断题】在叶子数目和权值相同的所有二叉树中，带权路径长度最小的树一定是完全二叉树。本题答案：【错误】39、【判断题】给定二叉树先、中和后序遍历序列中的两个，可以唯一确定一棵二叉树。本题答案：【错误】40、【判断题】满二叉树一定完全是二叉树。本题答案：【正确】41、【判断题】一棵二叉树中，中序遍历序列的最后一个结点，必定是该二叉树前序遍历的最后一个结点。本题答案：【错误】42、【判断题】在完全二叉树中，若一个结点没有左孩子，则它必然是叶子结点。本题答案：【正确】43、【判断题】具有n个叶子结点的哈夫曼树共有2n-1个结点。本题答案：【正确】44、【判断题】串的存储结构有顺序串、堆串和块链串三种。本题答案：【正确】45、【判断题】串中任意个字符组成的子序列称为该串的子串。本题答案：【错误】46、【判断题】串'student'和'Student'相等。本题答案：【错误】47、【判断题】一个广义表的表头一定还是个广义表。本题答案：【错误】48、【判断题】稀疏矩阵中非零元素的个数远小于矩阵中元素的总数。本题答案：【正确】49、【判断题】数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。本题答案：【错误】50、【判断题】多维数组可以看作是一种特殊的线性表。本题答案：【正确】测验1、【判断题】图中任意两个顶点之间有路径相通我们称之为完全图。本题答案：【错误】测验1、【判断题】图的邻接矩阵是顺序存储方式。本题答案：【正确】测验1、【判断题】图的深度优先遍历算法还可以应用于检查回路问题。本题答案：【正确】测验1、【判断题】图的广度优先算法可以使用递归完成。本题答案：【错误】测验1、【判断题】prim算法适合在稠密图中求解最小生成树。本题答案：【正确】测验1、【判断题】prim算法的时间代价主要取决于顶点个数。本题答案：【正确】测验1、【判断题】Kruskal算法适合在稀疏图中求解最小生成树。本题答案：【正确】测验1、【判断题】拓扑排序可以用于检查图中是否有回路。本题答案：【正确】测验1、【判断题】在AOE网中，从源点到汇点的最长路径长度的路径被称为关键路径。本题答案：【正确】测验1、【判断题】Dijkstra算法思想属于典型的贪心算法。本题答案：【正确】测验1、【判断题】Dijkstra算法需要对图中每条边至少检查一次。本题答案：【正确】单元作业7在线练习71、【单选题】一个具有n个顶点的无向图最多有（）边。本题答案：【n(n-1)/2】2、【单选题】一个具有n个顶点的有向图中，要连通全部顶点至少需要（）条弧。本题答案：【n】3、【单选题】在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。本题答案：【2】4、【单选题】在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。本题答案：【1】5、【单选题】对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则占用的存储空间为（）。本题答案：【n+2e】6、【单选题】如果含有n个顶点的图形成一个环，则它有（）棵生成树。本题答案：【n】7、【单选题】任何一个无向连通网的最小生成树（）。本题答案：【有一棵或多棵】8、【单选题】判断一个有向图是否存在回路，可以用（）。本题答案：【深度优先遍历算法】9、【单选题】设图G有n个顶点和e条边，采用邻接表存储，则拓扑排序算法的时间复杂度为（）。本题答案：【O(n+e)】10、【单选题】下面不正确的说法是（）。本题答案：【任何一个关键活动提前完成，将使整个工程提前完成】11、【单选题】关键路径是事件结点网络中（）。本题答案：【从源点到汇点的最长路径】12、【单选题】图G是一个非连通无向图，共有28条边，则该图至少有（）个顶点。本题答案：【9】13、【单选题】已知一个图的邻接矩阵表示，删除所有从第i个顶点出发的弧方法是（）。本题答案：【将矩阵第i行上的元素全部置0】14、【单选题】深度优先遍历类似于二叉树的（）。本题答案：【先序遍历】15、【单选题】广度优先遍历类似于二叉树的()。本题答案：【层次遍历】16、【单选题】在图的表示法中，表示形式唯一的是（）。本题答案：【邻接矩阵表示法】17、【单选题】连通分量是（）的极大连通子图。本题答案：【无向图】18、【单选题】最小生成树的构造可使用（）算法。本题答案：【prim算法】19、【单选题】在一个具有n个顶点e条边的图中，所有顶点的度数之和等于（）。本题答案：【2e】20、【单选题】下面关于图的存储结构的叙述中正确的是（）。本题答案：【用邻接矩阵存储图，占用空间大小只与图中顶点数有关，而与边数无关】21、【单选题】有8个结点的有向完全图有()条边。本题答案：【56】22、【单选题】下图中，度为3的结点是（）。本题答案：【V2】23、【单选题】下图是（）。本题答案：【连通图】24、【单选题】如下图所示，从顶点a出发，按深度优先进行遍历，则可能得到的一种顶点序列为（）。本题答案：【a，e，d，f，c，b】25、【单选题】如下图所示，从顶点a出发，按广度优先进行遍历，则可能得到的一种顶点序列为（)。本题答案：【a，b，e，c，d，f】26、【判断题】图可以没有边，但不能没有顶点。本题答案：【错误】27、【判断题】关键路径上的活动都是关键活动，它们是否按时完成会影响工期。本题答案：【正确】28、【判断题】求稀疏图的最小生成树，用克鲁斯卡尔算法来求解较好。本题答案：【正确】29、【判断题】迪杰斯特拉算法求最短路径时，是按照路径长度递增的顺序求解的。本题答案：【正确】30、【判断题】任何一个有向图都一定存在拓扑序列。本题答案：【错误】31、【判断题】稠密图更适合采用邻接矩阵存储。本题答案：【正确】32、【判断题】若一个无向图以顶点V1为起点进行深度优先遍历，所得的遍历序列唯一，则可以唯一确定该图。本题答案：【正确】33、【判断题】若从一个无向图中任一顶点出发，进行一次深度优先遍历，就可以访问图中所有的顶点，则该图一定是连通的。本题答案：【正确】34、【判断题】存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的上三角（或下三角）部分就可以了。本题答案：【正确】35、【判断题】有向图不能进行广度优先遍历。本题答案：【错误】测验1、【判断题】对表长为n的线性表进行顺序查找，平均查找长度为(n+1)/2本题答案：【正确】测验1、【判断题】折半查找只适合关键字有序并且顺序存储的查找表。本题答案：【正确】测验1、【判断题】二叉排序树的形态与输入序列的顺序有关。本题答案：【正确】测验1、【判断题】在二叉排序树中，按照中序进行遍历，可以得到一个有序序列。本题答案：【正确】测验1、【判断题】哈希查找的理想情况是平均查找长度为0。本题答案：【正确】测验1、【判断题】构造哈希函数时尽可能减少地址冲突，但又不可能避免。本题答案：【正确】测验1、【判断题】处理冲突实际就是为了产生冲突的地址寻找下一个散列地址。本题答案：【正确】单元作业8在线练习81、【单选题】在关键字随机分布的情况下，用二叉排序树的方法进行查找，其查找长度与（）数量级相当。本题答案：【折半查找】2、【单选题】关于折半查找，以下说法正确的是(）。本题答案：【待查找表必须有序，且只能以顺序方式存储】3、【单选题】具有12个关键字的有序表，折半查找的平均查找长度()。本题答案：【37/12】4、【单选题】分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是（）。本题答案：【（100，60，80，90，120，110，130）】5、【单选题】折半查找适合于存储结构为（）的线性表。本题答案：【顺序】6、【单选题】如果要求用线性表既能较快地查找，又能适应动态变化的要求，则可采用（）查找方法。本题答案：【分块查找】7、【单选题】以下适合用分块查的数据集是（）。本题答案：【数据分成若干块，块内数据不必有序，但块间必须有序】8、【单选题】已知一如下10个记录的表，其关键字序列为（2，15，19，25，30，34，44，55，58，80），用折半查找法查找关键字为55的记录，比较次数是（）。本题答案：【2次】9、【单选题】关于哈希查找，以下说法不正确的是（）。本题答案：【哈希查找的ASL一定可以达到0】10、【单选题】由同一关键字集合构造的各棵二叉排序树()。本题答案：【形态和平均查找长度都不一定相同】11、【单选题】对二叉排序树进行()遍历，可以得到各结点键值的非递减序列。本题答案：【中序】12、【单选题】如果按关键码值递增的顺序依次将99个关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，在等概率情况下查找成功时的平均查找长度ASL为(）。本题答案：【50】13、【单选题】在有N个元素的顺序表中顺序查找，则等概率情况下查找成功的平均查找长度为（）。本题答案：【(N+1)/2】14、【单选题】对线性表进行折半查找时，要求线性表()。本题答案：【关键字有序并按顺序方式存储】15、【单选题】顺序查找法适合于存储结构为（）的线性表。本题答案：【顺序存储或链接存储】16、【单选题】一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值为82的结点时，()次比较后查找成功。本题答案：【4】17、【单选题】下列（）不是利用比较进行查找的方法。本题答案：【散列查找】18、【单选题】设哈希表长m=14，哈希函数H（key）=key％11。表中已有4个结点：addr(15)=4addr(38)=5addr(61)=6addr(84)=7其余地址为空。如用二次