MOOC 数据结构-华中农业大学 中国大学慕课答案

MOOC数据结构-华中农业大学中国大学慕课答案绪论1、问题：在数据结构中，从逻辑上可以把数据结构分成________。选项：A、动态结构和静态结构B、紧凑结构和非紧凑结构C、线性结构和非线性结构D、内部结构和外部结构正确答案:【线性结构和非线性结构】2、问题：算法分析的目的是________。选项：A、找出数据结构的合理性B、研究算法中的输入和输出的关系C、分析算法的效率以求改进D、分析算法的易懂性和文档性正确答案:【分析算法的效率以求改进】3、问题：算法分析的两个主要方面是________。选项：A、空间复杂度和时间复杂度B、正确性和简单性C、可读性和文档性D、数据复杂性和程序复杂性正确答案:【空间复杂度和时间复杂度】4、问题：计算机算法指的是解决问题的有限运算序列，它必须具备输入、输出和________等5个特性。选项：A、可执行性、可移植性和可扩充性B、可行性、确定性和有穷性C、确定性、有穷性和稳定性D、易读性、稳定性和安全性正确答案:【可行性、确定性和有穷性】5、问题：下面程序段的时间复杂度为____________。for(inti=0;im;i++)for(intj=0;jn;j++)a[i][j]=i*j;选项：A、O(m2)B、O(n2)C、O(m*n)D、O(m+n)正确答案:【O(m*n)】6、问题：执行下面程序段时，执行S语句的次数为____________。for(inti=1;i=n;i++)for(intj=1;j=i;j++)S;选项：A、n2B、n2/2C、n(n+1)D、n(n+1)/2正确答案:【n(n+1)/2】7、问题：下面算法的时间复杂度为____________。intf(unsignedintn){if(n==0||n==1)return1;elsereturnn*f(n-1);}选项：A、O(1)B、O(n)C、O(n2)D、O(n!)正确答案:【O(n)】8、问题：下面程序段的时间复杂性的量级为____________。for(i=1;i＜＝n;i++)for(j=1;j＜＝m;j++){c[i][j]=0;for(k=1;k＜＝w;k++)c[i][j]+=a[i][k]*b[k][j]}选项：A、O(i*j*k)B、O(n*m*k)C、O(n*j*k)D、O(n*m*w)正确答案:【O(n*m*w)】9、问题：下面关于算法说法错误的是____________。选项：A、算法最终必须由计算机程序实现B、为解决某问题的算法同为该问题编写的程序含义是相同的C、算法的可行性是指指令不能有二义性D、以上几个都是错误的正确答案:【算法的可行性是指指令不能有二义性】10、问题：数据结构是一门研究非数值计算的程序设计问题中计算机的①以及它们之间的②和运算等的学科。选项：A、数据元素B、关系C、逻辑存储D、数据映象正确答案:【数据元素#关系】线性表1、问题：线性表是_______。选项：A、一个有限序列，可以为空B、一个有限序列，不能为空C、一个无限序列，可以为空D、一个无序序列，不能为空。正确答案:【一个有限序列，可以为空】2、问题：对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的_______个元素。选项：A、n/2B、(n+1)/2C、(n–1)/2D、n正确答案:【n/2】3、问题：线性表采用链式存储时，其地址_______。选项：A、必须是连续的B、部分地址必须是连续的C、一定是不连续的D、连续与否均可以正确答案:【连续与否均可以】4、问题：用链表表示线性表的优点是_______。选项：A、便于随机存取B、花费的存储空间较顺序存储少C、便于插入和删除D、数据元素的物理顺序与逻辑顺序相同正确答案:【便于插入和删除】5、问题：某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用_______存储方式最节省运算时间。选项：A、单链表B、双链表C、单循环链表D、带头结点的双循环链表正确答案:【带头结点的双循环链表】6、问题：循环链表的主要优点是_______。选项：A、不再需要头指针了B、已知某个结点的位置后，能够容易找到他的直接前趋C、在进行插入、删除运算时，能更好的保证链表不断开D、从表中的任意结点出发都能扫描到整个链表正确答案:【从表中的任意结点出发都能扫描到整个链表】7、问题：下面关于线性表的叙述错误的是_______。选项：A、线性表采用顺序存储，必须占用一片地址连续的单元B、线性表采用顺序存储，便于进行插入和删除操作C、线性表采用链式存储，不必占用一片地址连续的单元D、线性表采用链式存储，便于进行插入和删除操作正确答案:【线性表采用顺序存储，便于进行插入和删除操作】8、问题：单链表中，增加一个头结点的目的是为了_______。选项：A、使单链表至少有一个结点B、标识表结点中首结点的位置C、方便运算的实现D、说明单链表是线性表的链式存储正确答案:【方便运算的实现】9、问题：若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用_______存储方式最节省运算时间。选项：A、单链表B、仅有头指针的单循环链表C、双链表D、仅有尾指针的单循环链表正确答案:【仅有尾指针的单循环链表】10、问题：若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用_______存储方式最节省运算时间。选项：A、单链表B、顺序表C、双链表D、单循环链表正确答案:【顺序表】11、问题：一个向量(一种顺序表)第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是_______。选项：A、110B、108C、100D、120正确答案:【108】12、问题：不带头结点的单链表head为空的判定条件是______。选项：A、head==NULL;B、head-next==NULL;C、head-next==head;D、head!=NULL;正确答案:【head==NULL;】13、问题：带头结点的单链表head为空的判定条件是______。选项：A、head==NULL;B、head-next==NULL;C、head-next==head;D、head!=NULL;正确答案:【head-next==NULL;】14、问题：在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行____。选项：A、s-next=p;p-next=s;B、s-next=p-next;p-next=s;C、s-next=p-next;p=s;D、p-next=s;s-next=p;正确答案:【s-next=p-next;p-next=s;】15、问题：在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行______。选项：A、s-next=p-next;p-next=s;B、p-next=s-next;s-next=p;C、q-next=s;s-next=p;D、p-next=s;s-next=q;正确答案:【q-next=s;s-next=p;】16、问题：从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较_____个结点。选项：A、nB、n/2C、(n-1)/2D、(n+1)/2正确答案:【(n+1)/2】17、问题：给定有n个结点的向量，建立一个有序单链表的时间复杂度_______。选项：A、O(1)B、O(n)C、O(n^2)D、O(nlogn)正确答案:【O(n^2)】18、问题：顺序存储结构是一种___的存储结构。选项：A、随机存取B、索引存取C、顺序存取D、散列存取正确答案:【随机存取】19、问题：在以下的叙述中，正确的是___。选项：A、线性表的顺序存储结构优于链表存储结构B、线性表的顺序存储结构适用于频繁插入/删除数据元素的情况C、线性表的链表存储结构适用于频繁插入/删除数据元素的情况D、线性表的链表存储结构优于顺序存储结构正确答案:【线性表的链表存储结构适用于频繁插入/删除数据元素的情况】20、问题：非空的循环单链表head的尾结点（由p所指向）满足____。选项：A、p-next==NULLB、p==NULLC、p-next==headD、p==head正确答案:【p-next==head】21、问题：在一个单链表中，若删除p所指结点的后续结点，则执行____。选项：A、p-next=p-next-next；B、p=p-next;p-next=p-next-next；C、p-next=p-next;D、p=p-next-next；正确答案:【p-next=p-next-next；】22、问题：在一个长度为n的顺序存储线性表中，向第i个元素(1≤i≤n+1)之前插入一个新元素时，需要从后向前依次后移____个元素。选项：A、n-iB、n-i+1C、n-i-1D、i正确答案:【n-i+1】23、问题：在一个长度为n的顺序存储线性表中，删除第i个元素(1≤i≤n+1)时，需要从前向后依次前移____个元素。选项：A、n-iB、n-i+1C、n-i-1D、i正确答案:【n-i】24、问题：在一个长度为n的线性表中顺序查找值为x的元素时，查找时的平均查找长度（即x同元素的平均比较次数，假定查找每个元素的概率都相等）为____。选项：A、nB、n/2C、(n+1)/2D、(n-1)/2正确答案:【(n+1)/2】25、问题：在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行____。选项：A、HL=p;p-next=HL;B、p-next=HL;HL=p;C、p-next=HL;p=HL;D、p-next=HL-next;HL-next=p;正确答案:【p-next=HL;HL=p;】26、问题：一个带头结点head的循环单链表为空的判断条件是____。选项：A、head==NULLB、head-next==NULLC、head-next==headD、head!=NULL正确答案:【head-next==head】27、问题：在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行____。选项：A、p=q-next;p-next=q-next;B、p=q-next;q-next=p;C、p=q-next;q-next=p-next;D、q-next=q-next-next;q-next=q;正确答案:【p=q-next;q-next=p-next;】28、问题：将两个各有n个元素的有序表归并成一个有序表，在最坏的情况下，其比较次数是____。选项：A、2n-1B、nC、n+1D、n-1正确答案:【2n-1】29、问题：线性表的逻辑顺序与存储顺序总是一致的。选项：A、正确B、错误正确答案:【错误】30、问题：顺序存储的线性表可以按序号随机存取。选项：A、正确B、错误正确答案:【正确】31、问题：顺序表的插入和删除一个数据元素，每次操作平均只有近一半的元素需要移动。选项：A、正确B、错误正确答案:【正确】32、问题：线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。选项：A、正确B、错误正确答案:【正确】33、问题：在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。选项：A、正确B、错误正确答案:【错误】34、问题：在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。选项：A、正确B、错误正确答案:【正确】35、问题：线性表的链式存储结构优于顺序存储结构。选项：A、正确B、错误正确答案:【错误】36、问题：在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。选项：A、正确B、错误正确答案:【正确】37、问题：线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。选项：A、正确B、错误正确答案:【正确】38、问题：在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。选项：A、正确B、错误正确答案:【错误】39、问题：线性表中，每一个元素均存在前驱。选项：A、正确B、错误正确答案:【错误】40、问题：线性表中，每一个元素均存在后继。选项：A、正确B、错误正确答案:【错误】41、问题：线性表中，存在唯一一个被称为第一元素的元素。选项：A、正确B、错误正确答案:【正确】42、问题：线性表中，存在唯一一个被称为最后一个元素的元素。选项：A、正确B、错误正确答案:【正确】43、问题：线性结构是一种一对一的结构。选项：A、正确B、错误正确答案:【正确】栈和队列1、问题：一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是____。选项：A、edcbaB、decbaC、dceabD、abcde正确答案:【dceab】2、问题：若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为____。选项：A、iB、n=iC、n-i+1D、不确定正确答案:【n-i+1】3、问题：栈结构通常采用的两种存储结构是____。选项：A、顺序存储结构和链式存储结构B、散列方式和索引方式C、链表存储结构和数组D、线性存储结构和非线性存储结构正确答案:【顺序存储结构和链式存储结构】4、问题：判定一个顺序栈ST（最多元素为m0）为空的条件是____。选项：A、top!=0B、top==0C、top!=m0D、top==m0-1正确答案:【top==0】5、问题：判定一个顺序栈ST（最多元素为m0）为栈满的条件是____。选项：A、top！=0B、top==0C、top！=m0D、top==m0-1正确答案:【top==m0-1】6、问题：队列操作的原则是____。选项：A、先进先出B、后进先出C、只能进行插入D、只能进行删除正确答案:【先进先出】7、问题：向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行____。(不带空的头结点)选项：A、HS—＞next=s;B、s—＞next=HS—＞next;HS—＞next=s;C、s—＞next=HS;HS=s;D、s—＞next=HS;HS=HS—＞next;正确答案:【s—＞next=HS;HS=s;】8、问题：从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行____。(不带空的头结点)选项：A、x=HS;HS=HS—＞next;B、x=HS—＞data;C、HS=HS—＞next;x=HS—＞data;D、x=HS—＞data;HS=HS—＞next;正确答案:【x=HS—＞data;】9、问题：一个队列的数据入列序列是1，2，3，4，则队列的出队时输出序列是____。选项：A、4，3，2，1B、1，2，3，4C、1，4，3，2D、3，2，4，1正确答案:【1，2，3，4】10、问题：判定一个循环队列QU（最多元素为m）为空的条件是____。选项：A、rear-front==mB、rear-front-1==mC、front==rearD、front==rear+1正确答案:【front==rear】11、问题：判定一个循环队列QU（最多元素为m,m==Maxsize-1）为满队列的条件是____。选项：A、((rear-front)+Maxsize)%Maxsize==mB、rear-front-1==mC、front==rearD、front==rear+1正确答案:【((rear-front)+Maxsize)%Maxsize==m】12、问题：循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是____。选项：A、(rear-front+m)%mB、rear-front+1C、rear-front-1D、rear-front正确答案:【(rear-front+m)%m】13、问题：栈和队列的共同点是____。选项：A、都是先进后出B、都是先进先出C、只允许在端点处插入和删除元素D、没有共同点正确答案:【只允许在端点处插入和删除元素】14、问题：栈操作的原则是____。选项：A、先进先出B、后进先出C、只能进行插入D、只能进行删除正确答案:【后进先出】15、问题：在顺序栈中，判断栈s为空的条件是____。选项：A、t.base==NULLB、st.top==st.stacksizeC、st.top-st.base=st.stacksizeD、st.top==st.base正确答案:【st.top==st.base】16、问题：在顺序栈中，判断栈s满的条件是____。选项：A、st.base==NULLB、st.top==st.stacksizeC、st.top-st.base=st.stacksizeD、st.top==st.base正确答案:【st.top-st.base=st.stacksize】17、问题：当利用大小为N的一维数组顺序存储一个栈时，假定用top==N表示栈空，则向这个栈插入一个元素时，首先应执行语句修改top指针____。选项：A、top++B、top--C、top=0D、top正确答案:【top--】18、问题：当利用大小为N的一维数组顺序存储一个循环队列时，该队列的最大长度为____。选项：A、N-2B、N-1C、ND、N+1正确答案:【N-1】19、问题：从一个循环顺序队列删除元素时，首先需要____。选项：A、前移一位队首指针B、后移一位队首指针C、取出队首指针所指位置上的元素D、取出队尾指针所指位置上正确答案:【后移一位队首指针】20、问题：假定一个循环顺序队列的队首和队尾指针分别为f和r，则判断队空的条件是____。选项：A、f+1==rB、r+1==fC、f==0D、f==r正确答案:【f==r】21、问题：假定一个链队的队首和队尾指针分别为front和rear，则判断队空的条件是____。选项：A、front==rearB、front!=NULLC、rear!=NULLD、front==NULL正确答案:【front==NULL】串1、问题：以下叙述中正确的是____。选项：A、串是一种特殊的线性表B、串的长度必须大于零C、串中无素只能是字母D、空串就是空白串正确答案:【串是一种特殊的线性表】2、问题：串是一中特殊的线性表，其特殊性体现在____。选项：A、可以顺序存储B、数据元素是一个字符C、可以链接存储D、数据元素可以是多个字符正确答案:【数据元素是一个字符】3、问题：设有两个串p和q，求q在p中首次出现的位置的运算称作____。选项：A、连接B、模式匹配C、求子串D、求串长正确答案:【模式匹配】4、问题：设串s1=’ABCDEFG’，s2=’PQRST’，函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是____。选项：A、BCDEFB、BCDEFGC、BCPQRSTD、BCDEFEF正确答案:【BCDEFEF】5、问题：设串的长度为n，则它的子串个数为____。选项：A、nB、n(n+1)C、n(n+1)/2D、n(n+1)/2+1正确答案:【n(n+1)/2】6、问题：下列那些为空串____。选项：A、S=“”B、S=“”C、S=“φ”D、S=“θ”正确答案:【S=“”】7、问题：S1=“ABCD”，S2=“CD”则S2在S3中的位置是____。选项：A、1B、2C、3D、4正确答案:【3】8、问题：串是一种特殊的线性表，其特殊性体现在____。选项：A、可以顺序存储B、数据元素是一个字符C、可以链接存储D、数据元素可以是多个字符正确答案:【数据元素是一个字符】9、问题：串的长度是____。选项：A、串中不同字母的个数B、串中不同字符的个数C、串中所含的字符的个数D、串中所含字符的个数，且大于0正确答案:【串中所含的字符的个数】10、问题：若某串的长度小于一个常数，则采用____存储方式最为节省空间。选项：A、链式B、堆结构C、顺序表D、循环链表正确答案:【顺序表】11、问题：空串是由空白字符组成的串。选项：A、正确B、错误正确答案:【错误】12、问题：串的定长顺序结构是用一组地址连续的存储单元存储串值的字符序列，按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区。选项：A、正确B、错误正确答案:【正确】13、问题：串的堆分配存储表示是用一组地址连续的存储单元存储串值的字符序列，但它们的存储空间是在程序执行过程中动态分配得到的。选项：A、正确B、错误正确答案:【正确】14、问题：如果一个串中的所有字符均在另一串中出现，那么则说明前者是后者的子串。选项：A、正确B、错误正确答案:【错误】15、问题：串是由有限个字符构成的连续序列，串长度为串中字符的个数，子串是主串中字符构成的有限序列。选项：A、正确B、错误正确答案:【错误】16、问题：空串的长度为零。选项：A、正确B、错误正确答案:【正确】17、问题：串是不少于一个字符的序列。选项：A、正确B、错误正确答案:【错误】18、问题：两个串相等当且仅当两个串的长度相等并且各个对应位置上的字符都想等。选项：A、正确B、错误正确答案:【正确】19、问题：KMP算法的特点是在模式匹配时指示主串的指针不会变小。选项：A、正确B、错误正确答案:【正确】20、问题：设模式串的长度为m,目标串的长度为n，当n≈m且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。选项：A、正确B、错误正确答案:【错误】数组广义表测验题1、问题：常对数组进行的两种基本操作是选项：A、建立与删除B、索引与修改C、查找与修改D、查找与索引正确答案:【查找与修改】2、问题：稀疏矩阵的压缩存储方法是只存储选项：A、非零元素B、三元组（i,j,aij）C、aijD、i,j正确答案:【非零元素】3、问题：数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为选项：A、SA+141B、SA+144C、SA+222D、SA+225正确答案:【SA+222】4、问题：若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B[1..(n(n+1))/2]中，则在B中确定aij(ij)的位置k的关系为选项：A、i*(i-1)/2+jB、j*(j-1)/2+iC、i*(i+1)/2+jD、j*(j+1)/2+i正确答案:【j*(j-1)/2+i】5、问题：有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是选项：A、60B、66C、18000D、33正确答案:【66】6、问题：数组A[0..4,-1..-3,5..7]中含有元素的个数选项：A、55B、45C、36D、16正确答案:【45】7、问题：对稀疏矩阵进行压缩存储目的是选项：A、便于进行矩阵运算B、便于输入和输出C、节省存储空间D、降低运算的时间复杂度正确答案:【节省存储空间】8、问题：已知广义表LS＝((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是选项：A、head(tail(LS))B、tail(head(LS))C、head(tail(head(tail(LS)))D、head(tail(tail(head(LS))))正确答案:【head(tail(head(tail(LS)))】9、问题：广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为选项：A、(g)B、(d)C、cD、d正确答案:【d】10、问题：下面说法不正确的是选项：A、广义表的表头总是一个广义表B、广义表的表尾总是一个广义表C、广义表难以用顺序存储结构D、广义表可以是一个多层次的结构正确答案:【广义表的表头总是一个广义表】11、问题：数组不适合作为任何二叉树的存储结构。选项：A、正确B、错误正确答案:【错误】12、问题：从逻辑结构上看，n维数组的每个元素均属于n个向量。选项：A、正确B、错误正确答案:【正确】13、问题：稀疏矩阵压缩存储后，必会失去随机存取功能。选项：A、正确B、错误正确答案:【正确】14、问题：数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。选项：A、正确B、错误正确答案:【错误】15、问题：广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。选项：A、正确B、错误正确答案:【错误】树和二叉树测验题1、问题：已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为选项：A、-A+B*C/DEB、-A+B*CD/EC、-+*ABC/DED、-+A*BC/DE正确答案:【-+A*BC/DE】2、问题：设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为选项：A、5B、6C、7D、8正确答案:【8】3、问题：设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是选项：A、m-nB、m-n-1C、n+1D、条件不足，无法确定正确答案:【m-n】4、问题：若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是选项：A、9B、11C、15D、不确定正确答案:【11】5、问题：在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为选项：A、4B、5C、6D、7正确答案:【6】6、问题：设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是选项：A、M1B、M1+M2C、M3D、M2+M3正确答案:【M2+M3】7、问题：具有10个叶结点的二叉树中有几个度为2的结点选项：A、8B、9C、10D、11正确答案:【9】8、问题：一棵完全二叉树上有1001个结点，其中叶子结点的个数是选项：A、250B、500C、254D、505E、以上答案都不对正确答案:【以上答案都不对】9、问题：设给定权值总数有n个，其哈夫曼树的结点总数为选项：A、不确定B、2nC、2n+1D、2n-1正确答案:【2n-1】10、问题：有关二叉树下列说法正确的是选项：A、二叉树的度为2B、一棵二叉树的度可以小于2C、二叉树中至少有一个结点的度为2D、二叉树中任何一个结点的度都为2正确答案:【一棵二叉树的度可以小于2】11、问题：一个具有1025个结点的二叉树的高h为选项：A、11B、10C、11至1025之间D、10至1024之间正确答案:【11至1025之间】12、问题：一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有多少结点选项：A、2hB、2h+1C、2h-1D、h+1正确答案:【2h-1】13、问题：一棵具有n个结点的完全二叉树的树高度（深度）是选项：A、?logn?+1B、logn+1C、?logn?D、logn-1正确答案:【?logn?+1】14、问题：利用二叉链表存储树，则根结点的右指针是选项：A、指向最左孩子B、指向最右孩子C、空D、非空正确答案:【空】15、问题：在下列存储形式中，哪一个不是树的存储形式？选项：A、双亲表示法B、孩子链表表示法C、孩子兄弟表示法D、顺序存储表示法正确答案:【顺序存储表示法】16、问题：二叉树是度为2的有序树。选项：A、正确B、错误正确答案:【错误】17、问题：完全二叉树一定存在度为1的结点。选项：A、正确B、错误正确答案:【错误】18、问题：二叉树的遍历结果不是唯一的选项：A、正确B、错误正确答案:【正确】19、问题：二叉树的遍历只是为了在应用中找到一种线性次序。选项：A、正确B、错误正确答案:【正确】20、问题：对一棵二叉树进行层次遍历时，应借助于一个栈。选项：A、正确B、错误正确答案:【错误】21、问题：中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。选项：A、正确B、错误正确答案:【正确】22、问题：任何一棵二叉树都可以不用栈实现前序线索树的前序遍历。选项：A、正确B、错误正确答案:【正确】23、问题：由一棵二叉树的前序序列和后序序列可以唯一确定它。选项：A、正确B、错误正确答案:【错误】24、问题：完全二叉树中，若一个结点没有左孩子，则它必是树叶。选项：A、正确B、错误正确答案:【正确】25、问题：当一棵具有n个叶子结点的二叉树的WPL值为最小时，称其树为哈夫曼树，且其二叉树的形状必是唯一的。选项：A、正确B、错误正确答案:【错误】图测试题1、问题：图中有关路径的定义是（）选项：A、由相邻顶点序偶所形成的序列B、由不同顶点所形成的序列C、由不同边所形成的序列D、上述定义都不是正确答案:【由相邻顶点序偶所形成的序列】2、问题：设无向图的顶点个数为n，则该图最多有（）条边选项：A、n(n-1)/2B、n-1C、n(n+1)/2D、n*n正确答案:【n(n-1)/2】3、问题：n个节点的完全有向图含有边的数目为（）选项：A、n(n-1)B、n(n+1)C、n/2D、n*n正确答案:【n(n-1)】4、问题：一个有n个节点的无向图，最多有（）个连通分量选项：A、nB、0C、n-1D、1正确答案:【n】5、问题：一个有n个节点的无向图，最少有（）个连通分量选项：A、1B、nC、n-1D、0正确答案:【1】6、问题：下列（）的邻接矩阵是对称矩阵选项：A、无向图B、有向图C、AOV网D、AOE网正确答案:【无向图】7、问题：下列说法不正确的是（）选项：A、图的深度优先遍历不适用于有向图。B、图的遍历是从给定的源点出发，每一个顶点仅被访问一次。C、遍历的基本算法有两种：深度优先搜索遍历和广度优先搜索遍历。D、图的深度遍历是一个递归的过程。正确答案:【图的深度优先遍历不适用于有向图。】8、问题：无向图G=（V，E），其中V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)},以顶点a为源，对该图进行深度优先遍历，得到的顶点序列正确的是（）选项：A、a,e,d,f,c,bB、a,c,f,e,b,dC、a,e,b,c,f,dD、a,b,e,c,d,f正确答案:【a,e,d,f,c,b】9、问题：如图所示，在下面的5个序列中，符合深度优先遍历的序列有多少？（）(1)a,e,b,d,f,c;(2)a,c,f,d,e,b;(3)a,e,d,f,c,b;(4)a,e,f,d,c,b;(5)a,e,f,d,b,c选项：A、2个B、4个C、3个D、5个正确答案:【2个】10、问题：求解最短路径的弗洛伊德算法的时间复杂度为（）选项：A、O（n*n*n）B、O（n+e）C、O（n*n）D、O（n）正确答案:【O（n*n*n）】11、问题：已知有向图G=（V，E），其中V={V1，V2，V3，V4，V5，V6，V7}，E={V1,V2,V1,V3V1,V4V2,V5V3,V5V3,V6V4,V6V5,V7V6,V7},G的拓扑序列是（）选项：A、V1，V3，V4，V6，V2，V5，V7B、V1，V3，V2，V6，V4，V5，V7C、V1，V3，V4，V5，V2，V6，V7D、V1，V2，V5，V3，V4，V6，V7正确答案:【V1，V3，V4，V6，V2，V5，V7】12、问题：在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（）选项：A、G中有一条Vj到Vi的路径B、G中有一条从Vi到Vj的路径C、G中没有边Vi,VjD、G中有边Vi,Vj正确答案:【G中有一条Vj到Vi的路径】13、问题：关键路径是事件结点图中（）选项：A、从源点到汇点的最长路径B、从源点到汇点的最短路径C、最长回路D、最短回路正确答案:【从源点到汇点的最长路径】14、问题：下列关于AOE网的叙述中，不正确的是（）选项：A、任何一个关键活动提前完成，那么整个工程将会提前完成B、关键活动延期完成就会影响整个工程的完成时间C、所有的关键活动提前完成，那么整个工程将会提前完成D、某些关键活动提前完成，那么整个工程可能提前完成正确答案:【任何一个关键活动提前完成，那么整个工程将会提前完成】15、问题：带权有向图G用邻域矩阵A存储，则顶点i的入度等于A中（）选项：A、第i列非∞且非零的元素个数B、第i列非∞的元素之和C、第i行非∞且非零元素个数D、第i行非∞的元素之和正确答案:【第i列非∞且非零的元素个数】16、问题：无向图的邻接矩阵是一个（）选项：A、对称矩阵B、零矩阵C、上三角矩阵D、对角矩阵正确答案:【对称矩阵】17、问题：如果从无向图的任一顶点出发，进行一次深度优先搜索即可访问所有的顶点，则该图一定是（）选项：A、连通图B、完全图C、有回路D、一棵树正确答案:【连通图】18、问题：图的深度优先遍历算法类似于二叉树的（）算法选项：A、先序遍历B、中序遍历C、后序遍历D、层次遍历正确答案:【先序遍历】19、问题：对于图进行从顶点1开始的深度优先搜索遍历，可得到顶点访问序列（）选项：A、1,2,4,3,5,7,6B、1,2,4,3,5,6,7C、1,2,4,5,6,3,7D、1,2,3,4,5,6,7正确答案:【1,2,4,3,5,7,6】20、问题：对图从顶点1进行广度优先搜索遍历，可得顶点访问序列为（）选项：A、1,3,2,4,5,6,7B、1,2,4,3,5,6,7C、1,2,3,4,5,6,7D、2,5,1,4,7,3,6正确答案:【1,3,2,4,5,6,7】21、问题：对于含有n个顶点的带权连通图，它的最小生成树是指图中任意一个（）选项：A、由n个顶点构成的边的权值之和最小的连通子图B、由n-1条权值之和最小的边构成的子图C、由n-1条权值之和最小的边构成的连通子图D、由n-1条权值最小的边构成的子图正确答案:【由n个顶点构成的边的权值之和最小的连通子图】22、问题：一个有向图中的顶点不能排成一个拓扑序列，则断定该有向图（）选项：A、含有顶点数目大于1的强连通分量B、是个强连通图C、含有多个入度为0的顶点D、含有多个出度为0的顶点正确答案:【含有顶点数目大于1的强连通分量】23、问题：下列关于无向连通图特性的叙述中，正确的是（）I所有顶点的度之和为偶数II边数大于顶点个数减1III至少有一个顶点的度为1选项：A、只有IB、只有IIC、I和IID、I和III正确答案:【只有I】24、问题：下列关于图的叙述中，正确的是（）1回路是简单路径2存储稀疏图，用邻接矩阵比邻接表更省空间3若有向图中存在拓扑序列，则该图不存在回路选项：A、仅3B、仅1,2C、仅1D、仅1,3正确答案:【仅3】25、问题：对有n个顶点、e条边且使用邻接表存储的有向图进行广度优先搜索遍历，其算法时间复杂度是（）选项：A、存在，且唯一B、存在，且不唯一C、存在，可能不唯一D、无法确定是否存在正确答案:【存在，且唯一】26、问题：下列关于最小生成树的叙述中，正确的是（）最小生成树的代价唯一所有权值最小的边一定会出现在所有的最小生成树中使用普里姆算法从不同顶点开始得到的最小生成树一定相同使用普里姆算法和克鲁斯卡尔算法得到的最小生成树总不相同选项：A、仅IB、仅IIC、仅I、IID、仅II、IV正确答案:【仅I】27、问题：设图的邻接矩阵A如下图所示，则各顶点的度依次是（）选项：A、2,2,1,1B、1,2,1,2C、3,4,2,3D、4,4,2,2正确答案:【3,4,2,3】28、问题：若对下图所示的无向图进行遍历，不是广度优先遍历序列的是（）选项：A、a,b,c,d,h,e,f,gB、e,a,f,g,b,h,c,dC、d,b,c,a,h,e,f,gD、h,c,a,b,d,e,g,f正确答案:【a,b,c,d,h,e,f,g】29、问题：下图所示的AOE网表示一项包含8个活动的工程。通过同时加快若干活动的进度可以缩短整个工期的工程。下列选项中，加快其进度就可以缩短工程工期的是（）选项：A、f和dB、d和eC、c和eD、f和h正确答案:【f和d】30、问题：对下面的有向图进行拓扑排序，得到的拓扑序列可能是（）选项：A、3,1,4,2,6,5B、3,1,2,4,6,5C、3,1,4,2,5,6D、3,1,2,4,5,6正确答案:【3,1,4,2,6,5】31、问题：含有n个顶点的连通无向图，其边的个数至少为n-1。选项：A、正确B、错误正确答案:【正确】32、问题：要连通具有n个顶点的有向图，至少需要n+1条边。选项：A、正确B、错误正确答案:【错误】33、问题：在一个无向图中，所有顶点的度数之和等于所有边数的2倍选项：A、正确B、错误正确答案:【正确】34、问题：深度优先遍历可以判断出一个有向图是否有环。选项：A、正确B、错误正确答案:【正确】35、问题：当各边上的权值均相等时，BFS算法可以用来解决单源最短路径问题选项：A、正确B、错误正确答案:【正确】36、问题：若一个有向图的邻接矩阵中，主对角线以下的元素均为零，则该图的拓扑有序序列一定不存在。选项：A、正确B、错误正确答案:【错误】37、问题：一个有向无环图的拓扑排序序列是唯一的。选项：A、正确B、错误正确答案:【错误】38、问题：对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是n*n选项：A、正确B、错误正确答案:【正确】39、问题：对图进行广度优先搜索遍历类似于二叉树的先序遍历算法。选项：A、正确B、错误正确答案:【错误】40、问题：用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是拓扑有序的。选项：A、正确B、错误正确答案:【错误】查找测试题1、问题：顺序查找法适合于存储结构为____的线性表。选项：A、散列存储B、顺序存储或链接存储C、压缩存储D、索引存储正确答案:【顺序存储或链接存储】2、问题：对线性表进行二分查找时，要求线性表必须____。选项：A、以顺序方式存储B、以链接方式存储C、以顺序方式存储，且结点按关键字有序排序D、以链接方式存储，且结点按关键字有序排序正确答案:【以顺序方式存储，且结点按关键字有序排序】3、问题：采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为____。选项：A、(n-1)/2B、nC、n/2D、(n+1)/2正确答案:【(n+1)/2】4、问题：采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为____。选项：A、O（n2）B、O(nlog2n)C、O(n)D、O(log2n)正确答案:【O(log2n)】5、问题：从具有n个结点的二叉排序树中查找一个元素时，最坏情况下的时间复杂度为____。选项：A、O(n)B、O(1)C、C.O(log2n)D、D.O(n^2)正确答案:【O(n)】6、问题：有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值82为的结点时，需要____次比较后才能查找成功。选项：A、1B、2C、4D、8正确答案:【4】7、问题：设哈希表长m=14，哈希函数H(key)=key%11。表中已有4个结点：addr(15)=4;addr(38)=5;addr(61)=6;addr(84)=7。如用二次探测再散列处理冲突，关键字为49的结点的地址是____。选项：A、8B、3C、5D、9正确答案:【9】8、问题：有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为____。选项：A、35/12B、37/12C、39/12D、43/12正确答案:【37/12】9、问题：有数据{53,30,37,12,45,24,96}，从空二叉树开始逐个插入数据来形成二叉排序树，若希望树的高度最小，则应选择下面哪个序列输入____。选项：A、45,24,53,12,37,96,30B、37,24,12,30,53,45,96C、12,24,30,37,45,53,96D、30,24,12,37,45,96,53正确答案:【37,24,12,30,53,45,96】10、问题：对于静态表的顺序查找法，若在表头设置岗哨，则正确的查找方式为_______。选项：A、从第0个元素往后查找该数据元素B、从第1个元素往后查找该数据元素C、从第n个元素往开始前查找该数据元D、与查找顺序无关正确答案:【从第n个元素往开始前查找该数据元】11、问题：采用线性探测法解决冲突问题，所产生的一系列后继散列地址______。选项：A、必须大于等于原散列地址B、必须小于等于原散列地址C、可以大于或小于但不能等于原散列地址D、地址大小没有具体限制正确答案:【可以大于或小于但不能等于原散列地址】12、问题：对于查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于_______。选项：A、静态查找表B、动态查找表C、静态查找表与动态查找表D、两种表都不适合正确答案:【动态查找表】13、问题：散列表的平均查找长度_______。选项：A、与处理冲突方法有关而与表的长度无关B、与处理冲突方法无关而与表的长度有关C、与处理冲突方法有关而与表的长度有关D、与处理冲突方法无关而与表的长度无关正确答案:【与处理冲突方法有关而与表的长度有关】14、问题：一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有____个结点。选项：A、2^(k-1)-1B、2^(k-1)C、2^k-1D、2^k+1正确答案:【2^k-1】15、问题：分块查找中，若索引表对各块内均采用顺序查找，有900个元素的线性表若分成25块，其平均查找长度为