MOOC 数据结构-西北大学 中国大学慕课答案

MOOC数据结构-西北大学中国大学慕课答案数据结构的基础概念随堂测验1、问题：一个抽象类型包括数据对象、和一组处理数据的操作。选项：A、数据对象中各元素间的结构关系B、数据元素集C、接口D、数据对象集正确答案:【数据对象中各元素间的结构关系】2、填空题：抽象数据类型具有、信息隐蔽的特点。正确答案:【数据抽象】第2讲数据结构的内容随堂测验1、问题：线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。（）选项：A、正确B、错误正确答案:【错误】2、填空题：1、数据结构的逻辑结构分为集合、线性、层次和四种。正确答案:【网状】3、填空题：2、数据结构的存储结构分为和非顺序两种。正确答案:【顺序】4、填空题：3、在线性结构、树形结构和图结构中，数据元素之间分别存在着一对一、一对多和联系。正确答案:【多对多】第3讲数据结构与C语言表示随堂测验1、问题：当需要用一个形式参数直接改变对应实参的值时，该形式参数应说明为。选项：A、与实参同类型指针参数B、不需要参数C、与实参同类型的参数D、全局变量正确答案:【与实参同类型指针参数】第4讲算法性能评价随堂测验1、问题：1、执行下面的程序段的时间复杂度为。for(inti=0;im;i++)for(intj=0;jn;j++)a[i][j]=i*j;选项：A、O()B、O()C、O(m*n)D、O(m+n)正确答案:【O(m*n)】2、问题：2、执行下面程序段时，语句S的执行次数为。for(inti=0;i=n;i++)for(intj=0;ji;j++)S;选项：A、B、C、n(n+1)D、正确答案:【】第5讲算法与算法描述随堂测验1、问题：算法设计的要求是：正确性、可读性、和高效率和低存储。选项：A、确定性B、健壮性C、可行性D、有限性正确答案:【健壮性】2、问题：算法具有有限性、确定性、、输入、输出五大特性。选项：A、可行性B、可读性C、健壮性D、正确性正确答案:【可行性】第一章单元测试1、问题：下面程序段的时间复杂度为（）。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)】2、问题：执行下面程序段时，语句S的执行次数为（）。for(inti=0;i=n;i++)for(intj=0;j=i;j++)S;选项：A、n*nB、n*n/2C、(n+1)*(n+2)/2D、n(n+1)/2正确答案:【(n+1)*(n+2)/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、问题：某算法的时间复杂度是O（n*n）,表明该算法的（）。选项：A、问题规模是n*nB、问题规模与n*n正比C、执行时间与n*n正比D、执行时间等于n*n正确答案:【执行时间与n*n正比】9、问题：如下程序段:for(i=1;i=n-1;i++)for(j=i+1;j=n;j++)x=x+1;其中语句x=x+1执行的语句频度为（）。选项：A、n*nB、n*(n-1)/2C、n*(n+1)/2D、n*(n-1)正确答案:【n*(n-1)/2】10、问题：以下算法的时间复杂度为（）。if(n=0){for(inti=0;in;i++)for(intj=0;jn;j++)printf(输入数据大于等于零\n);}else{for(intj=0;jn;j++)printf(输入数据小于零\n);}选项：A、O(1)B、O(n*n+n)C、O(n)D、O(n*n)正确答案:【O(n*n)】11、问题：在数组A[0..n-1]中查找给定值K的算法大致如下：i=n-1;while(i=0(A[i]!=k))i--;returni;该算法的时间复杂度为（）。选项：A、O(n-i+1)B、O(n-i)C、O(n)D、无法确定正确答案:【O(n)】12、问题：下面算法的时间复杂度为（）。x=100;y=100;while(y0)if(x100){x=x-10;y--;}elsex++;选项：A、O(n)B、O(100)C、O(1)D、O(n*n)正确答案:【O(1)】13、问题：假设sqrt(n)函数中涉及的算法时间复杂度为O(1)，那么下面的算法是判断n是否为素数，其时间复杂度为（）。voidprime(intn){for(i=2;isqrt(n)(n%i)!=0;i++);if(isqrt(n))printf(%disaprimenumber,n);elseprintf(%disnotaprimenumber,n);}选项：A、O(n)B、O(1)C、O(sqrt(n))sqrt表示对n取根方D、O(n-i)正确答案:【O(sqrt(n))sqrt表示对n取根方】14、问题：某算法中，执行频率最高的语句的执行次数为则该算法的时间复杂度应该是（）。选项：A、T(n)=O(n*n*n)B、T(n)=O(n*n)C、T(n)=O((n*n*n+n*n+n)/n)D、T(n)=O(n*n+n)正确答案:【T(n)=O(n*n)】15、问题：数据结构中，数据处理的最小单位是（）。选项：A、数据B、数据对象C、数据元素D、数据项正确答案:【数据元素】16、问题：以下属于数据元素间基本逻辑结构的是（）。选项：A、集合B、线性C、树D、图正确答案:【集合#线性#树#图】17、问题：以下属于算法特性的是（）。选项：A、0个或多个输入；至少1个输出B、正确性C、确定性D、可行性和有限性正确答案:【0个或多个输入；至少1个输出#确定性#可行性和有限性】18、问题：算法设计的要求包括（）。选项：A、正确性B、可读性C、健壮性D、高效率和低存储正确答案:【正确性#可读性#健壮性#高效率和低存储】19、问题：数据元素在计算机内存中的存储映像包括（）。选项：A、顺序存储B、非顺序存储C、图结构D、树结构正确答案:【顺序存储#非顺序存储】20、问题：抽象数据类型包括了（）。选项：A、一个数据对象B、元素的存储结构C、元素间的关系D、一组操作正确答案:【一个数据对象#元素间的关系#一组操作】21、问题：具有线性结构的元素只能用顺序存储，具有非线性结构的元素只能非顺序存储。选项：A、正确B、错误正确答案:【错误】22、问题：算法就是程序。选项：A、正确B、错误正确答案:【错误】23、问题：算法的优劣与算法描述的语言无关。选项：A、正确B、错误正确答案:【正确】24、问题：算法的可行性是指每一条指令具有明确含义。选项：A、正确B、错误正确答案:【错误】25、问题：健壮的算法不会因为非法输入数据而出现莫名其妙的执行结果。选项：A、正确B、错误正确答案:【正确】26、问题：算法设计的要求就是要设计高效率和低存储的算法。选项：A、正确B、错误正确答案:【错误】27、问题：数据类型就是变量。选项：A、正确B、错误正确答案:【错误】28、问题：数据元素的存储结构分为顺序存储和非顺序存储。选项：A、正确B、错误正确答案:【正确】29、问题：数据元素的顺序存储结构优于非顺序存储。选项：A、正确B、错误正确答案:【错误】30、问题：元素间的逻辑关系可分为线性和非线性关系两种。选项：A、正确B、错误正确答案:【错误】第1讲线性表的概念随堂测验1、问题：线性表是具有n个（）的有限序列（n0）选项：A、数据对象B、数据元素C、字符D、数据项正确答案:【数据元素】2、问题：线性表是一个（）。选项：A、有限序列，可以为空B、有限序列，不可以为空C、无限序列，可以为空D、无限序列，可以为空正确答案:【有限序列，可以为空】3、问题：线性表的特点是每个元素都有一个前驱和一个后继。（）选项：A、正确B、错误正确答案:【错误】第2讲线性表的顺序存储随堂测验1、问题：若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）(1=i=n+1)。选项：A、O(1)B、O(n)C、O(n*n)D、O（）正确答案:【O(n)】2、问题：若长度为n的线性表采用顺序存储结构，删除第i个位置的元素，需要移动的元素个数为（）。选项：A、iB、n-iC、n-i+1D、n-i-1正确答案:【n-i】第3讲随堂测验1、问题：对一个长度为n的顺序表，假设在任何位置上插入一个元素的概率是相等的，那么插入一个元素时要移动表中的（）个元素。选项：A、nB、n+1C、D、正确答案:【】2、问题：线性表的顺序存储是指将表中元素按照从大到小或从小到大存储。选项：A、正确B、错误正确答案:【错误】第4讲线性表的链式存储随堂测验1、问题：通过表达式可以获取带头结点的单链表L中首元素结点的数据值。选项：A、L-nextB、(L-next)-dataC、L-dataD、L-next正确答案:【(L-next)-data】2、问题：单链表中必须设有头结点。（）选项：A、正确B、错误正确答案:【错误】第5讲单链表的基本运算随堂测验1、问题：下列选项中，项是链表不具有的特点。选项：A、插入和删除运算不需要移动元素B、所需要的存储空间与线性表的长度成正比C、不必事先估计存储空间大小D、可以随机访问表中的任意元素正确答案:【可以随机访问表中的任意元素】2、问题：有一个带头结点的单链表HEAD，则判断其是否为空链表的表达式是选项：A、HEAD==NULLB、HEAD-〉NEXT==NULLC、HEAD-〉NEXT==HEADD、HEAD！=NULL正确答案:【HEAD-〉NEXT==NULL】3、问题：在一个单链表中P所指结点后插入一个S所指结点时，应执行语句：。选项：A、P-next=S;S-next=P-next;B、S-next=P-next;P-next=S;C、S-next=P-next;P=S;D、S-next=P;P-next=S;正确答案:【S-next=P-next;P-next=S;】第6讲随堂测验1、问题：设指针变量p指向单链表中结点A的直接前驱，若删除单链表中结点A，则需要修改指针的操作序列为（）。选项：A、q=p-next；p-next=q-next；free(q)；B、q=p-next；p-next=q-next；C、p-next=p-next-next；D、q=p-next；p-data=q-data；free(q)；正确答案:【q=p-next；p-next=q-next；free(q)；】2、问题：对链表进行插入和删除操作时不必移动链表中结点。()选项：A、正确B、错误正确答案:【正确】3、问题：在单链表中，可以从头结点出发，查找到表中所有结点。（）选项：A、正确B、错误正确答案:【正确】第二章单元测试（1）1、问题：在长度为n的顺序表中的第i(1=i=n+1)个位置上插入一个元素，其算法时间复杂度为（）。选项：A、O(logn)(以2为底)B、O(1)C、O(n)D、O(n*n)正确答案:【O(n)】2、问题：在长度为n的顺序表中的第i(1=i=n+1)个位置上插入一个元素，需要移动的元素个数为（）。选项：A、n-iB、iC、n-i+1D、n-i-1正确答案:【n-i+1】3、问题：链表不具有的特点是（）。选项：A、插入、删除不需要移动元素B、可随机访问任一元素C、不必事先估计存储空间D、所需存储空间与线性表程度成正比正确答案:【可随机访问任一元素】4、问题：在一单链表中，删除指针p所指的后继结点，以下语句正确的是（）。选项：A、p-next=p-next-next;free(p-next);B、free(p-next);p-next=p-next-next;C、p=p-next;D、s=p-next;p-next=s-next;free(s);正确答案:【s=p-next;p-next=s-next;free(s);】5、问题：假设删除长度为n的顺序表中的每个元素的概率相同，则删除一个元素平均要移动的元素个数是（）。选项：A、nB、(n+1)/2C、(n-1)/2D、n/2正确答案:【(n-1)/2】6、问题：设某顺序表中第一个元素的地址是Base，每个结点占m个单元，则第i个结点的地址为（）。选项：A、Base+(i-1)×mB、Base+i×mC、Base-i×mD、Base+(i+1)×m正确答案:【Base+(i-1)×m】7、问题：长度为n的非空线性表采用顺序存储结构，在表的第i个位置插入一个数据元素，i的合法值应该是（）。选项：A、i0B、1≤i≤n+1C、1≤i≤n-1D、0≤i≤n+1正确答案:【1≤i≤n+1】8、问题：非空单链表结点结构为【data,next】，若指针p所指结点是尾结点，则（）表达式为真。选项：A、p==NULLB、p-next==NULLC、p-next==PD、p-next!=NULL正确答案:【p-next==NULL】9、问题：某顺序表的第一个元素的存储地址是500，每个元素占4个单元，则第8个元素的起始地址是()。选项：A、504B、508C、516D、528正确答案:【528】10、问题：在长度为n的顺序表中删除第i(1=i=n)个位置上的元素，需要移动的元素个数为（）。选项：A、n-iB、n-i+1C、n-i-1D、i正确答案:【n-i】11、问题：在长度为n的顺序表中的的末尾位置上插入一个元素，其算法时间复杂度为（）。选项：A、O(1)B、O(n)C、O(logn）（以2为底）D、O(nlogn)正确答案:【O(1)】12、问题：以下算法的功能是在一个非递减的顺序存储线性表中，删除所有值相等的多余元素。时间复杂度为O(n)，空间复杂度为O(1)。划线部分应填入的语句是（）。voidDelRepeatData(SeqList*L){i=0;j=1;while(j=L-last){if(L-elem[i]==L-elem[j]);else{L-elem[i+1]=L-elem[j];i++;j++;}}L-last=i;}选项：A、i++B、j++C、i--D、j--正确答案:【j++】13、问题：以下算法是删除带头结点单链表L中的最小的元素，横线处应填入的语句是（）。voidDelMinNode(LinkListL){p=L-next;pre=L;if(L==NULL)return;while(p-next!=NULL)//pre指向最小元素的前驱元素，开始默认第一个结点最小，pre指向头结点{if(p-next-datapre-next-data)pre=p;}//删除pre后面的结点p=pre-next;;}选项：A、free(p);pre-next=p-next;B、free(p-next);pre-next=p-next;C、pre-next=p-next;free(p);D、p-next=pre-next;free(p);正确答案:【pre-next=p-next;free(p);】14、问题：单链表中增加头结点的目的是存储链表的长度。选项：A、正确B、错误正确答案:【错误】15、问题：线性表在链式存储时，查找第i个元素的时间同i的值无关。选项：A、正确B、错误正确答案:【错误】16、问题：线性表在顺序存储时，查找第i个元素的时间同i的值成正比。选项：A、正确B、错误正确答案:【错误】17、问题：线性表的特点是每个元素都有一个前驱和一个后继。选项：A、正确B、错误正确答案:【错误】18、问题：线性表的链式存储结构优于顺序存储。选项：A、正确B、错误正确答案:【错误】19、问题：顺序存储方式的优点是存储密度大，插入、删除效率高。选项：A、正确B、错误正确答案:【错误】20、问题：顺序表的每个结点只能是一个基本类型，而链表的每个结点可以是一个构造类型。选项：A、正确B、错误正确答案:【错误】21、问题：插入和删除操作是线性表的基本操作。这两种操作在数组中也经常使用。选项：A、正确B、错误正确答案:【错误】22、问题：在顺序表中，逻辑上相邻的两个元素物理存储上也一定也相邻。选项：A、正确B、错误正确答案:【正确】23、问题：在线性表的链式存储结构中，逻辑上相邻的两个元素在物理存储上并不一定紧邻。选项：A、正确B、错误正确答案:【正确】24、问题：线性表采用顺序存储，必须占用一段地址连续的存储单元。选项：A、正确B、错误正确答案:【正确】25、问题：顺序表结构适宜进行随机访问，而链表适宜进行插入、删除。选项：A、正确B、错误正确答案:【正确】第7讲循环链表随堂测验1、问题：有一个带头结点的循环单链表HEAD，则判断其是否为空链表的条件是。选项：A、HEAD==NULLB、HEAD-〉NEXT==NULLC、HEAD-〉NEXT==HEADD、HEAD！=NULL正确答案:【HEAD-〉NEXT==HEAD】2、问题：在单向循环链表中，从表中任意结点出发都可以顺着next域访问到表中所有元素（）选项：A、正确B、错误正确答案:【正确】第8讲双向链表--随堂测验1、问题：与单链表相比，双向链表的优点之一是。选项：A、插入删除操作更加方便ꢀB、可以进行随机访问C、可以省略表头指针和表尾指针ꢀD、访问前后相邻结点更方便。正确答案:【访问前后相邻结点更方便。】2、问题：在双向链表L中，可以从任一结点p出发沿同一方向的指针域查找到表中所有元素。（）选项：A、正确B、错误正确答案:【错误】第9讲静态链表--随堂测验1、问题：静态链表中与动态链表的插入和删除运算类似，不需要做元素的移动。（）选项：A、正确B、错误正确答案:【正确】2、问题：静态链表既有顺序存储结构的优点，又有动态链表的优点。所以，它存取表中第ｉ个元素的时间与位置序号ｉ无关，可以实现随机存取。（）选项：A、正确B、错误正确答案:【错误】第10讲链式结构小结--随堂检测1、问题：已知单链表的头指针为head且该链表不带头结点，则该单链表为空的条件是。选项：A、head==NULLB、head-next==NULLC、head-next==headD、head!=NULL正确答案:【head==NULL】2、问题：设指针变量p指向单链表中某结点的直接前驱，若删除单链表中该结点，需要修改指针的操作序列为。选项：A、q=p-next；p-next=q-next；free(q)；B、q=p-next；free(q)；C、p-next=p-next-next；free(p-next)；D、q=p-next；free(q)；正确答案:【q=p-next；p-next=q-next；free(q)；】3、问题：设带有头结点的单向循环链表的头指针变量为head，则其判空条件是。选项：A、head==NULLB、head-next==NULLC、head-next==headD、head!=NULL正确答案:【head-next==head】4、问题：在双向循环链表中，可以从任一结点p出发沿同一方向的指针域查找到表中所有元素。（）选项：A、正确B、错误正确答案:【正确】第12讲随堂测验1、问题：下列选项中，项是链表不具有的特点。选项：A、插入和删除运算不需要移动元素B、所需要的存储空间与线性表的长度成正比C、不必事先估计存储空间大小D、可以随机访问表中的任意元素正确答案:【可以随机访问表中的任意元素】2、问题：在线性表中最常用的操作是存取第i个元素及其前趋的值，可采用存储方式最省时间？选项：A、顺序表B、带头指针的双向循环链表C、带头指针的单向循环链表D、带头指针的单向链表正确答案:【顺序表】3、问题：下面关于线性表的叙述错误的是（）。选项：A、线性表采用顺序存储必须占用一片连续的存储空间B、线性表采用链式存储不必占用一片连续的存储空间C、线性表采用链式存储便于插入和删除操作的实现D、线性表采用顺序存储便于插入和删除操作的实现正确答案:【线性表采用顺序存储便于插入和删除操作的实现】总结与提高随堂测验1、问题：某线性表中最常用的操作是存取序号为i的元素和在最后进行插入和删除运算，则采用存储方式时间性能最好。选项：A、双向链表B、双向循环链表C、单向循环链表D、顺序表正确答案:【顺序表】2、问题：已知一个带头结点的非空循环单链表，其尾指针是R，则其首元素结点的地址为：选项：A、R-nextB、*(R-next-next)C、(R-next-next)D、R-next-next正确答案:【R-next-next】3、问题：线性表的顺序存储优于链式存储结构。（）选项：A、正确B、错误正确答案:【错误】4、填空题：在带头结点的非空单链表中，头结点的存储位置由指示正确答案:【头指针】第1讲随堂测验1、问题：栈操作的特性是（）选项：A、FIFOB、LIFOC、FCFSD、插入和删除操作限制在表的两端进行正确答案:【LIFO】2、问题：栈中，允许进行插入和删除的一端称为（）选项：A、栈顶B、栈底C、栈头D、栈尾正确答案:【栈顶】3、问题：栈是线性结构，是操作受限制的线性表。（）选项：A、正确B、错误正确答案:【正确】第2讲随堂测验1、问题：1、已知顺序栈的地址为s,此时栈不满且栈顶指示器top指向真实栈顶,执行元素x进栈操作正确的语句是（）选项：A、s-top++;s-elem[s-top]=x;B、s-top=s-top+1;s-elem[s-top]=x;C、s-elem[++s-top]=x;D、s-elem[s-top]=x;s-top++;正确答案:【s-top++;s-elem[s-top]=x;#s-top=s-top+1;s-elem[s-top]=x;#s-elem[++s-top]=x;】2、问题：2、已知顺序栈的地址为s,此时栈不空且栈顶指示器top指向真实栈顶，执行出栈操作并将出栈元素赋值给x所指向的单元，则下列语句中，正确的是（）选项：A、s-top--;*x=s-elem[s-top];B、*x=s-elem[s-top];s-top=s-top-1;C、*x=s-elem[s-top--];D、*x=s-elem[s-top];s-top--;正确答案:【*x=s-elem[s-top];s-top=s-top-1;#*x=s-elem[s-top--];#*x=s-elem[s-top];s-top--;】3、问题：1、已知顺序栈的地址为s,此时栈不空且栈顶指示器top指向真实栈顶，执行取栈顶操作的语句是*x=s-elem[s-top--];()选项：A、正确B、错误正确答案:【错误】第3讲随堂测验1、问题：已知一个双端栈的地址为dS，则该双端栈不满时，，元素x进1号栈（高端栈）操作的语句是（）选项：A、dS-stack[--dS-top[1]]=x;B、dS-stack[dS-top[1]]=x;dS-top[1]--;C、dS-top[1]--;dS-stack[dS-top[1]]=x;D、dS-stack[++dS-top[1]]=x;正确答案:【dS-top[1]--;dS-stack[dS-top[1]]=x;】2、问题：已知一个双端栈dStack,则判断该双端栈栈满的条件是（）选项：A、dStack.top[0]+1==dStack.top[1]B、dStack.top[0]==dStack.top[1]C、dStack.top[0]-1==dStack.top[1]D、dStack.top[0]==dStack.top[1]-1正确答案:【dStack.top[0]+1==dStack.top[1]#dStack.top[0]==dStack.top[1]-1】3、问题：已知一个双端栈的地址为dS，则该双端栈不空时，1号栈（高端栈）出栈操作的语句是*x=dS-stack[dS-top[1]--]（）选项：A、正确B、错误正确答案:【错误】第4讲随堂测验1、问题：已知带头结点的链栈top,则该链栈不空时,出栈操作的语句是()选项：A、top-next=top-next-next;*x=top-next-data;B、*x=top-next-data;top-next=top-next-next;free(top-next);C、*x=top-data;p=top;top=p-next;free(p);D、*x=top-next-data;p=top-next;top-next=p-next;free(p);正确答案:【*x=top-next-data;p=top-next;top-next=p-next;free(p);】2、问题：已知带头结点的链栈top,则该链栈为空的条件是()选项：A、top==NULLB、top-next==NULLC、top-next-next==NULLD、top-next==top正确答案:【top-next==NULL】3、问题：已知带头结点的链栈top,则元素x对应的新结点s进栈操作的语句是（）选项：A、s-next=top-next;top-next=s;B、top-next=s;s-next=top-next;C、s-next=top;top=s;D、top=s;s-next=top;正确答案:【s-next=top-next;top-next=s;】第5讲栈的应用1、问题：在括号匹配算法中，当正扫描检测的符号是右括号，此时的栈是空栈，则（）。选项：A、右括号进栈；B、继续向下扫描；C、取出栈顶元素做匹配检查；D、此时出现“右括号多了”的不匹配现象。正确答案:【此时出现“右括号多了”的不匹配现象。】2、问题：在算术表达式求值的算法中，若当前正扫描的符号是运算符s，且s的优先级比运算符栈栈顶元素的优先级高，则（）选项：A、运算符栈出栈，运算数出栈，做运算；B、s进运算符栈；C、取运算符栈栈顶，运算数栈顶，做运算；D、s进运算数栈；正确答案:【s进运算符栈；】3、填空题：在括号匹配算法中，当正扫描的符号是左括号时，则该做左括号（）。正确答案:【进栈】第6讲随堂测验1、问题：递归进层（i→i+1层）系统需要做三件事是（）选项：A、保留本层参数与返回地址；B、保留下层参数和函数地址；C、为被调用函数的局部变量分配存储区，给下层参数赋值；D、将程序转移到被调函数的入口。正确答案:【保留本层参数与返回地址；#为被调用函数的局部变量分配存储区，给下层参数赋值；#将程序转移到被调函数的入口。】2、问题：从被调用函数返回调用函数之前，递归退层（i←i+1层）系统也应完成三件工作是（）选项：A、保存被调函数的计算结果；B、释放被调函数的数据区，恢复上层参数；C、保存返回上层函数的地址；D、依照被调函数保存的返回地址，将控制转移回调用函数。正确答案:【保存被调函数的计算结果；#释放被调函数的数据区，恢复上层参数；#依照被调函数保存的返回地址，将控制转移回调用函数。】3、问题：递归是指在定义自身的同时又出现了对自身的引用。（）选项：A、正确B、错误正确答案:【正确】4、填空题：系统需设立一个递归工作栈作为整个递归函数运行期间使用的数据存储区。每层递归所需信息构成一个（）。正确答案:【工作记录】第三章单元测验（1）1、问题：栈的特点是（）。选项：A、先进先出B、先进后出C、后进后出D、没有顺序正确答案:【先进后出】2、问题：队列的特点是（）。选项：A、先进先出B、先进后出C、后进先出D、没有顺序正确答案:【先进先出】3、问题：栈之说以叫限定性线性表，是因为（）。选项：A、栈的操作位置受限制B、栈中的元素类型受限制C、栈的应用范围受限制D、栈的存储结构受限制正确答案:【栈的操作位置受限制】4、问题：输入序列为123，若进栈、出栈操作可以交替进行，则不能得到的出栈序列是（）。选项：A、321B、312C、123D、132正确答案:【312】5、问题：以下会用到栈的应用是（）。选项：A、递归B、子程序调用C、括号匹配D、以上选项均有可能正确答案:【以上选项均有可能】6、问题：循环队列存储在数组A[0..m-1]中，则入队时rear应该变化为（）选项：A、rear++B、rear=(rear+1)mod(m-1)C、rear=(rear+1)modmD、rear=(rear+1)mod(m+1)正确答案:【rear=(rear+1)modm】7、问题：循环队列A[0..n-1]存放其元素值，F表示队头元素所在的位置，R表示队尾元素的下一个位置。则当前队列中的元素数是()。选项：A、(R-F+n)%nB、R-F+1C、R-F-1D、R-F正确答案:【(R-F+n)%n】8、问题：栈和队列的共同点是（）。选项：A、都是先进先出B、都是先进后出C、只允许在端点处插入和删除元素D、它们没有共同点正确答案:【只允许在端点处插入和删除元素】9、问题：当利用大小为n的数组(下标从1到n)顺序存储一个栈时，假定用top==n表示栈空，则每次向这个栈插入一个元素时，首先应执行（）语句修改top指针。选项：A、top++;B、top--;C、top=0;D、top=n;正确答案:【top--;】10、问题：设栈S和队列Q的初始状态均为空，元素a,b,c,d,e,f,g依次进入栈S。如果每个元素出栈后立即进入队列Q，且7个元素出队的顺序为b,d,e,f,c,a,g，则栈S的容量至少是（)。选项：A、1B、2C、3D、4正确答案:【3】11、问题：以下属于递归求解问题的前提条件的是（）。选项：A、原问题可层层分解为子问题，且子问题比原问题规模小B、子问题的解法与原问题解法相同C、最小的子问题有解D、其他选项均是正确答案:【其他选项均是】12、问题：以下属于消除递归的主要原因是（）。选项：A、递归程序不容易理解B、递归程序时空效率较差C、递归程序容易写错D、其他选项均是正确答案:【递归程序时空效率较差】13、问题：一个栈的输入序列为123……n，若输出序列的第一个元素是n，输出第i（1=i=n）个元素是（）选项：A、iB、n-iC、n-i+1D、不确定正确答案:【n-i+1】14、问题：凡是元素的保存次序与使用顺序相反的，都可以使用（）。选项：A、栈B、队列C、顺序表D、链表正确答案:【栈】15、问题：若栈采用顺序存储方式存储，现两栈共享空间S[1~N]，top[i]代表第i个栈(i=1,2)栈顶。栈1的底在S[1]，栈2的底在S[N]，则栈满的条件是（）。选项：A、top[1]+top[2]==NB、top[1]+1==top[2]C、top[1]+top[2]==N-1D、top[2]-top[1]==0正确答案:【top[1]+1==top[2]】16、问题：消除递归肯定要用到栈，否则无法完成。选项：A、正确B、错误正确答案:【错误】17、问题：若输入序列为1234,则通过一个栈可以得到输出序列3124。选项：A、正确B、错误正确答案:【错误】18、问题：若输入序列为1234,则通过栈只能得到4321的输出序列。选项：A、正确B、错误正确答案:【错误】19、问题：有些问题，比如汉诺塔问题等，只能用递归来解，无法转换成非递归算法。选项：A、正确B、错误正确答案:【错误】20、问题：顺序栈因为是顺序存储，所以可以随机存取栈中任意元素。选项：A、正确B、错误正确答案:【错误】21、问题：两顺序栈共享空间，也存在空间溢出问题。选项：A、正确B、错误正确答案:【正确】22、问题：栈和队列都是限制插入和删除位置的线性结构。选项：A、正确B、错误正确答案:【正确】23、问题：函数或过程调用需要用到栈。选项：A、正确B、错误正确答案:【正确】第7讲随堂测验1、问题：递归算法具有两个特性分别是（）选项：A、递归算法求解问题，方法简单。B、递归算法效率高C、递归算法求解问题，方法复杂D、递归算法的效率较低正确答案:【递归算法求解问题，方法简单。#递归算法的效率较低】2、问题：下列可以直接用循环结构即可将递归转换为非递归的是（）选项：A、斐波那契数列问题B、N!问题C、汉诺塔问题D、尾递归问题正确答案:【斐波那契数列问题#N!问题#尾递归问题】第8讲随堂测验1、问题：已知带头结点的链队列指针Q，则该队列做新元素结点s进队操作的语句是（）选项：A、Q-rear-next=s;Q-rear=s;B、s-next=Q-front-next;Q-front-next=s;C、Q-next=s;Q=s;D、s-next=Q-next;Q-next=s;正确答案:【Q-rear-next=s;Q-rear=s;】2、问题：已知带头结点的链队列指针Q，则该非空队列取队头元素操作的语句是（）选项：A、*x=Q-next-data;B、*x=Q-front-data;C、*x=Q-front-next-data;D、*x=Q-rear-data;正确答案:【*x=Q-front-next-data;】3、问题：队列操作的特性是LIFO。（）选项：A、正确B、错误正确答案:【错误】4、问题：队列允许做插入的一端称为队头，允许删除的一端称为队尾（）选项：A、正确B、错误正确答案:【错误】第9讲随堂测验1、问题：已知循环队列Q-element[MAXSIZE],队头指示器为Q-front，队尾指示器为Q-rear（指向真实队尾的下一个位置），则该队列中元素个数为：（）选项：A、Q-rear-Q-frontB、Q-rear-Q-front+1C、（Q-rear-Q-front+MAXSIZE）%MAXSIZED、（Q-rear-Q-front+1+MAXSIZE）%MAXSIZE正确答案:【（Q-rear-Q-front+MAXSIZE）%MAXSIZE】2、问题：已知循环队列Q-element[MAXSIZE],队头指示器为Q-front，队尾指示器为Q-rear（指向真实队尾的下一个位置），则该队列为空队列的条件为（）选项：A、Q-rear==Q-frontB、Q-rear+1==Q-frontC、（Q-rear+1）%MAXSIZE==Q-frontD、（Q-rear-1）%MAXSIZE==Q-front正确答案:【Q-rear==Q-front】3、问题：已知循环队列Q-element[MAXSIZE],队头指示器为Q-front，队尾指示器为Q-rear（指向真实队尾的下一个位置），则该队列为满队列的条件为（）（采用少用一个空间的方法）选项：A、Q-rear==Q-frontB、Q-rear+1==Q-frontC、（Q-rear+1）%MAXSIZE==Q-frontD、（Q-rear-1）%MAXSIZE==Q-front正确答案:【（Q-rear+1）%MAXSIZE==Q-front】第10讲随堂测验1、问题：在打印杨辉三角形前N行的算法中，需要申请一个N*N的二维数组存放杨辉三角形N行数据。（）选项：A、正确B、错误正确答案:【错误】第三章单元测验（2）1、问题：队列对数据的操作顺序是（）。选项：A、先进先出B、先进后出C、随机存取D、其余三个均正确正确答案:【先进先出】2、问题：设rear是非空循环单链表的尾指针，则删除表中第一个元素结点的操作可表示为（）（该链表不带头结点）。选项：A、p=rear-next;rear-next=p-next;free(p);B、p=rear-next;free(p);rear-next=p-next;C、free(rear-next);rear-next=rear-next-next;D、p=rear-next;free(p);rear-next=rear-next;正确答案:【p=rear-next;rear-next=p-next;free(p);】3、问题：设栈S和队列Q的初始状态均为空，元素a,b,c,d,e,f,g依次进入栈S（进栈和出栈可交替进行）。如果每个元素出栈后立即进入队列Q，且7个元素出队的顺序为b,d,e,f,c,a,g，则栈S的容量至少是（）。选项：A、1B、2C、3D、4正确答案:【3】4、问题：以下应用可能会用到栈的是（）。选项：A、递归调用B、表达式求值C、函数调用D、其余三个答案均正确正确答案:【其余三个答案均正确】5、问题：一个队列的元素入队顺序是1,2,3,4，则出队顺序为（）。选项：A、1,2,3,4B、4,3,2,1C、2,1,3,4D、3,4,2,1正确答案:【1,2,3,4】6、问题：某循环队列用数组A[0..n-1]表示，指示器为front指向队头元素，指示器rear指向队尾后的空单元。则当前队列中的元素个数为（）。选项：A、(rear-front+n)%nB、rear-frontC、（rear-front+n+1)%nD、(rear-front+n-1)%n正确答案:【(rear-front+n)%n】7、问题：以下函数的功能是（）。voidfun(Queue*Q){StackS;intd;InitStack(S);while(!EmptyQueue(*Q)){DeleteQueue(Q,d);Push(S,d);}while(!EmptyStack(S)){Pop(S,d);EnterQueue(Q，d);}}选项：A、将队列Q中的元素逆置。B、将队列Q中的元素放入栈中。C、将队列Q中的元素放入栈中，然后再从栈中取出来放入队列中。D、删除队列Q中的元素正确答案:【将队列Q中的元素逆置。】8、问题：栈和队列都是限制存取位置的线性结构。选项：A、正确B、错误正确答案:【正确】9、问题：循环队列用数组A[0..n-1]表示，则入队时的队尾指针变换语句为：rear=(rear+1)%n;选项：A、正确B、错误正确答案:【正确】10、问题：一般的缓冲区用队列做为数据结构。选项：A、正确B、错误正确答案:【正确】11、问题：循环队列因为是顺序存储，因此可以随机存取。选项：A、正确B、错误正确答案:【错误】12、问题：判断表达式中的括号是否匹配，采用队列数据结构最佳。选项：A、正确B、错误正确答案:【错误】第1讲随堂测验1、问题：设s=‘abcd’,s1=‘123’，则执行语句StrInsert(s,2,s1)后，s=.选项：A、‘123abcd’B、‘a123bcd’C、‘ab123cd’D、‘abc123d’正确答案:【‘a123bcd’】2、问题：设s=‘abcd’，则执行语句StrDelete(s,2,2)后，s=.选项：A、‘abcd’B、‘abc’C、‘ad’D、‘a’正确答案:【‘ad’】第2讲随堂测验1、填空题：假设主串S=‘aaabbbababaabb’,模式串T=‘abaa’,用串匹配算法从主串的第6个字符开始模式匹配，需要做趟匹配，方能找到匹配串。正确答案:【4】2、填空题：假设主串S=‘aaabbbababaabb’,模式串T=‘abaa’,用串匹配算法从主串的第6个字符开始模式匹配，在第2趟匹配中，要做次比较。正确答案:【4】第3讲随堂测验1、问题：用带头结点的单链表来表示串s,则串s为空串的条件是（）选项：A、s-next==NULLB、s==NULLC、s-next==sD、s-next-next==NULL正确答案:【s-next==NULL】随堂测验1、问题：假设有6行8列的二维数组A(下标从1开始),每个元素占用6个字节,存储器按字节编址。已知A的基地址为1000,计算按行存储时元素A36的地址是;选项：A、1126B、1138C、1192D、无法确定正确答案:【1126】2、问题：假设有6行8列的二维数组A(下标从1开始),每个元素占用6个字节,存储器按字节编址。已知A的基地址为1000,计算按列存储时元素A36的地址是;选项：A、1192B、1126C、1138D、无法确定正确答案:【1192】随堂测验1、问题：已知一个n行n列的三对角带状矩阵A，其中非零元素的个数是（）。选项：A、3n-2B、3n+2C、3nD、n*n正确答案:【3n-2】2、问题：若将n阶上三角矩阵A按列优先压缩存放在一维数组B中，第一个非零元素存放在B[0]中，则非零元素aij存放在B[k]中，则k=()。选项：A、B、C、D、正确答案:【】第3讲随堂测验1、问题：对稀疏矩阵进行压缩存储的目的是（）选项：A、便于进行矩阵运算B、便于输入和输出C、节省存储空间D、减低运算的时间复杂度正确答案:【节省存储空间】2、问题：稀疏矩阵压缩存储后，不会失去（）功能输入输出选项：A、顺序存储B、随机存取C、输入输出D、输入输出正确答案:【随机存取】第4讲随堂测验1、填空题：对于一个m行n列的稀疏矩阵中有len个非零元素，则用十字链表存储时，需要（）个头指针。正确答案:【m+n】2、填空题：对于一个m行n列的稀疏矩阵中有len个非零元素，则用十字链表存储时，需要（）个三元组结点。正确答案:【len】第5讲随堂测验1、问题：任意一个广义表都可以表示为由表头和表尾构成（）。选项：A、正确B、错误正确答案:【错误】2、问题：非空的广义表的表尾可能是单个元素也可能是表元素（）。选项：A、正确B、错误正确答案:【错误】3、填空题：已知广义表L=((x,y,z),a,(u,t,w)),则head(head(tail(tail(L))))的结果是（）。正确答案:【u】4、填空题：已知数组M[1..10,-1..6,0..3],)若数组以行序为主序存储,起始地址为1000,且每个数据元素占用3个存储单元,则M[2,4,2]的地址为（）正确答案:【1162】第1讲随堂测验1、问题：树最适合用来表示（）选项：A、有序数据元素B、无序数据元素C、元素之间具有分支层次关系的数据D、元素之间无联系的数据正确答案:【元素之间具有分支层次关系的数据】2、填空题：若一棵树的广义表法表示为：A（B（E,F），C（G（H,I,J,K），L），D（M（N）））则该树的度为（）；正确答案:【4】3、填空题：若一棵树的广义表法表示为：A（B（E,F），C（G（H,I,J,K），L），D（M（N）））该树的深度为（）；正确答案:【4】4、填空题：若一棵树的广义表法表示为：A（B（E,F），C（G（H,I,J,K），L），D（M（N）））该树中叶子结点的个数为：（）正确答案:【8】第2讲随堂测验1、问题：按照二叉树的定义，具有3个结点的二叉树有（）种选项：A、3B、4C、5D、6正确答案:【5】2、问题：若一棵二叉树有10个度为2的结点，5个度为1的结点，则度为0的结点有（）个。选项：A、9B、11C、15D、不确定正确答案:【11】3、问题：一个高度为h的完全二叉树至少有（）个结点选项：A、B、C、D、正确答案:【】4、问题：二叉树就是结点度不大于2的树。（）选项：A、正确B、错误正确答案:【错误】5、问题：不存在这样的二叉树：它有n个度为0的结点，n-1个度为1的结点，n-2个度为2的结点。（）选项：A、正确B、错误正确答案:【正确】6、填空题：具有n个结点的二叉树采用二叉链表存储结构，共有（）非空的指针域。正确答案:【n-1】7、填空题：拥有100个结点的完全二叉树的最大层数是（）正确答案:【7】第3讲随堂测验1、问题：某二叉树的先序序列和中序序列正好相同，则该二叉树一定是（）选项：A、空树或只有一个结点B、完全二叉树C、每个结点都没有左子D、高度等于其结点数正确答案:【每个结点都没有左子】2、问题：在二叉树中，p所指向的结点为度为1的分支点的条件是（）选项：A、p-lchild==NULL||p-rchild==NULLB、!(p-lchild!=NULLp-rchild!=NULL)C、!(p-lchild==NULLp-rchild==NULL)D、(p-lchild==NULLp-rchild!=NULL)||(p-lchild!=NULLp-rchild==NULL)正确答案:【(p-lchild==NULLp-rchild!=NULL)||(p-lchild!=NULLp-rchild==NULL)】3、问题：已知二叉树的先序和后序遍历序列可以唯一确定该二叉树。（）选项：A、正确B、错误正确答案:【错误】第六章单元测验11、问题：已知一算术表达式的中缀形式为A-B/C+D*E，前缀形式为+-A/BC*DE，其后缀形式为()。选项：A、ABCDE/-*+B、AB/C-D*E+C、ABC/-DE*+D、A-BC/DE*+正确答案:【ABC/-DE*+】2、问题：有关二叉树下列说法正确的是（）。选项：A、二叉树中每个结点的度都为2B、一棵二叉树的度可以小于2C、二叉树中至少有一个结点的度为2D、二叉树中任何一个结点的度都为2正确答案:【一棵二叉树的度可以小于2】3、问题：在一棵高度为k的满二叉树中，结点总数为（）。选项：A、-1B、2kC、D、正确答案:【-1】4、问题：某二叉树中有60个叶子结点，则该二叉树中度为2的结点个数为（）。选项：A、59B、60C、61D、不确定正确答案:【59】5、问题：100个结点的完全二叉树采用顺序存储，从1开始按层次编号，则编号最小的叶子结点的编号应该是（）。选项：A、100B、49C、50D、51正确答案:【51】6、问题：高度为7的完全二叉树，最少有（）个结点。选项：A、64B、127C、63D、128正确答案:【64】7、问题：高度为7的二叉树，最少有（）个结点。选项：A、7B、13C、64D、127正确答案:【7】8、问题：对任意一棵有n个结点的树，这n个结点的度之和为()。选项：A、n-1B、nC、n+2D、2*n正确答案:【n-1】9、问题：完全二叉树一定存在度为1的结点。选项：A、正确B、错误正确答案:【错误】10、问题：完全二叉树中，若一个结点没有左孩子，则它必是叶子。选项：A、正确B、错误正确答案:【正确】11、问题：二叉树只能用二叉链表表示。选项：A、正确B、错误正确答案:【错误】12、问题：树形结构中，每个元素都有一个前驱，0个或多个后继。选项：A、正确B、错误正确答案:【错误】第4讲随堂检测1、问题：设二叉树采用二叉链表方式存储，root指向根结点，r所指结点为二叉树中任一给定的结点。则可以通过改写（）算法，求出从根结点到结点r之间的路径。选项：A、先序遍历B、中序遍历C、后序遍历D、层次遍历正确答案:【后序遍历】2、问题：已知二叉树用二叉链表存储，则若实现二叉树实现左右子树交换，可以借助改写（）遍历算法实现。选项：A、先序遍历B、中序遍历C、后序遍历D、以上三种都可以正确答案:【先序遍历#后序遍历】第5讲随堂测验1、问题：在中序遍历非递归算法中，在进入子树进行访问前，需要在自定义栈中保存（）选项：A、本层根结点指针B、本层根结点的右孩子指针C、本层根结点的左孩子指针D、无需保留任何信息正确答案:【本层根结点指针】第6讲随堂测验1、问题：引入线索二叉树的目的是()选项：A、加快查找指定遍历过程中结点的直接前驱和直接后继B、为了能在二叉树中方便地插入和删除结点C、为了方便找到结点的双亲D、使二叉树遍历结果唯一正确答案:【加快查找指定遍历过程中结点的直接前驱和直接后继】2、问题：若判断线索二叉树中的p结点有右孩子结点则下列（）表达式为真。选项：A、p!=NULLB、p-rchild!=NULLC、p-rtag==0D、p-rtag==1正确答案:【p-rtag==0】3、问题：若线索二叉树中的p结点没有左孩子结点则下列（）表达式为真。选项：A、p==NULLB、p-lchild==NULLC、p-ltag==0D、p-ltag==1正确答案:【p-ltag==1】第7讲随堂测验1、问题：一棵二叉树的后序序列是：CBEFDA,中序序列是：CBAEDF,则该二叉树的先序序列是（）选项：A、ABCDEFB、ABCEDFC、ABDEFCD、ABFECD正确答案:【ABCDEF】2、问题：一棵二叉树的先序序列是：CEDBA,中序序列是：DEBAC,则该二叉树的后序序列是（）选项：A、DABECB、DCBAEC、DEABCD、CBADE正确答案:【DABEC】第8讲随堂测验1、问题：如图所示的二叉树BT是由森林T1转换而来的二叉树，那么森林T1中有（）叶子结点。选项：A、4B、5C、6D、7正确答案:【6】2、填空题：与树等价的二叉树，根没有（）子树。正确答案:【右】第9讲随堂测验1、问题：有13个叶子结点的哈夫曼树，该树中结点总数为（）选项：A、13B、26C、12D、25正确答案:【25】2、问题：在哈夫曼树中，权值相同的叶子点一定在同一层上。（）选项：A、正确B、错误正确答案:【错误】3、问题：在哈夫曼树中，权值较大的叶子点一般离根比较近。（）选项：A、正确B、错误正确答案:【正确】4、填空题：若以{4,5,6,7,8}作为叶子点构造哈夫曼树，则其带全路径长度为（）正确答案:【69】第10讲随堂测验1、问题：在哈夫曼编码中，当两个字符出现的频率相等时，则两个字符的哈夫曼编码也相同。（）选项：A、正确B、错误正确答案:【错误】第六章单元测验21、问题：已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历的结果为（）。选项：A、CBEFDAB、FEDCBAC、CBEDFAD、不确定正确答案:【CBEFDA】2、问题：线索二叉树中，判断p所指向的结点为叶子结点的条件是（）。选项：A、p-LC==NULLp-RC==NULLB、p-LTag==1C、p-LC==NULLp-LTag==0D、p-LTag==0p-RTag==0正确答案:【p-LTag==0p-RTag==0】3、问题：以下属于前缀编码的是（）。选项：A、{0,1,01,010,110}B、{00,01,10,11,101}C、{0,1101,1110,1100,1111}D、{01,00,10,001,110,101}正确答案:【{0,1101,1110,1100,1111}】4、问题：在下列存储形式中，（）不是树的存储形式。选项：A、双亲表示法B、孩子链表表示法C、孩子-兄弟表示法D、顺序存储表示法正确答案:【顺序存储表示法】5、问题：对二叉树中的结点进行编号，要求根结点的编号最小，左孩子结点编号比右孩子结点编号小。则应该采用（）遍历方法对其进行编号。选项：A、先序B、中序C、后序D、层次正确答案:【先序】6、问题：已知某二叉树的后序遍历序列是CEFDBA，中序遍历序列是CBEDFA。与该二叉树对应的树或森林中，叶子的数目是（）个。选项：A、1B、2C、3D、4正确答案:【3】7、问题：某二叉树中有60个叶子结点，则该二叉树中度为2的结点个数为（）。选项：A、59B、60C、61D、不一定正确答案:【59】8、问题：某二叉树的逻辑结构如下图所示，则其扩展先序序列为（）。选项：A、ABB、DFE、CF、EH、（I、表示空）J、ABK、DFN、CO、E（P、表示空）Q、ABDFCER、ABCDEF正确答案:【AB#DF###C#E##（#表示空）】9、问题：树的后根遍历，相当于对应二叉树的（）遍历。选项：A、中序B、先序C、后序D、层次正确答案:【中序】10、问题：哈夫曼树的带权路径长度等于其中所有结点的带权路径之和。选项：A、正确B、错误正确答案:【错误】11、问题：给定二叉树的先序、中序和后序遍历序列中的任意两个，就可以唯一确定一棵二叉树。选项：A、正确B、错误正确答案:【错误】12、问题：在叶子数目和权值相同的所有二叉树中，带权路径长度最小的树一定是哈夫曼树。选项：A、正确B、错误正确答案:【正确】13、问题：将一棵树转成二叉树，根结点一定没有右子树。选项：A、正确B、错误正确答案:【正确】14、填空题：有10个叶子结点的哈夫曼树，总结点个数是。正确答案:【19】15、填空题：将一棵树转换为二叉树时，遵循的规则是左孩子、。正确答案:【右兄弟】16、填空题：用权值{1,2,3,4,5}构造一棵哈夫曼树，则该树的带权路径长度为。正确答案:【33】17、填空题：假设T是一棵高度为5的二叉树,T中只有度为0和度为2的结点，那么T树最少应该有个结点。正确答案:【9】第1讲随堂测验1、问题：一个有n个顶点的有向图最多有边选项：A、nB、n(n-1)C、n(n-1)/2D、2n正确答案:【n(n-1)】2、问题：具有n个顶点的有向图至少应有弧才能确保是一个强连通图。选项：A、n-1B、nC、n(n-1)D、n(n-1)/2正确答案:【n】3、填空题：在一个无向图中，所有顶点的度之和等于边条数的倍。正确答案:【2】4、填空题：具有6个顶点的无向图至少应有条边才能确保是一个连通图。正确答案:【5】5、填空题：一个有向图G中所有顶点的入度之和是所有顶点出度之和的倍。正确答案:【1】第2讲随堂测验1、问题：对于一个n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小为（）选项：A、nB、n(n-1)C、D、正确答案:【】2、问题：有向图的邻接矩阵一定是对称矩阵。（）选项：A、正确B、错误正确答案:【错误】3、问题：用邻接矩阵存储无向图G时，其第i行中1的个数与第i列中1的个数相等。（）选项：A、正确B、错误正确答案:【正确】4、填空题：对于一个有n个顶点，e条边的无向图，若采用邻接表表示，则表头结点数组的大小为。正确答案:【n】5、填空题：对于一个有n个顶点，e条边的无向图，若采用邻接表表示，则边结点有个。正确答案:【2e##%_YZPRLFH_%##2*e】6、填空题：用邻接矩阵存储有向图G时，其第i列的所有元素之和等于该顶点的。正确答案:【入度】第3讲随堂测验1、问题：如果从一个无向图的任意一个顶点出发进行一次深度优先搜索即可访问所有顶点,则该图一定是()选项：A、完全图B、连通图C、有回路D、森林正确答案:【连通图】2、问题：图的深度优先遍历类似于树的（）遍历选项：A、先序遍历B、中序遍历C、后序遍历D、层次遍历正确答案:【先序遍历】3、问题：图的广度优先遍历类似于树的（）遍历选项：A、先序遍历B、中序遍历C、后序遍历D、层次遍历正确答案:【层次遍历】第4讲随堂测验1、问题：任何一个连通图（）生成树。选项：A、只有一棵B、有一棵或多棵C、一定有多棵D、可能不存在正确答案:【有一棵或多棵】2、问题：Prim算法适合求（）的最小生成树。选项：A、边稠密连通网B、边稀疏连通网C、边稠密无向网D、边稀疏无向网正确答案:【边稠密连通网】3、问题：对于n个顶点的连通图G来说，如果其中的某个子图有n个顶点，n-1条边，则该子图一定是G的生成树。（）选项：A、正确B、错误正确答案:【错误】4、填空题：对于n个顶点的连通图而言，它的生成树一定有条边。正确答案:【n-1】第5讲随堂测验1、问题：若一个有向图中的顶点不能排成一个拓扑序列，则可断定该有向图（）选项：A、是个有向无环图B、是个含有回路的有向图C、含有多个入度为0的顶点D、是个强连通图正确答案:【是个含有回路的有向图】2、问题：任何有向无环图的顶点都可以排成拓扑排序序列，且拓扑排序序列唯一（）选项：A、正确B、错误正确答案:【错误】3、填空题：在ＡＯＶ网中，顶点表示。正确答案:【活动】第6讲随堂测验1、问题：关键路径是ＡＯE网中（ꢀ）选项：A、从源点到汇点的最长路径B、从源点到汇点的最短路径C、最长回路D、最短回路正确答案:【从源点到汇点的最长路径】2、问题：关键活动若不能按期完成就会影响整个工程的完成时间，若某些关键活动能提前完成，将可能使整个工程提前完成。（）选项：A、正确B、错误正确答案:【正确】3、填空题：在ＡＯE网中，关键路径上的活动称为。正确答案:【关键活动】第7讲随堂测验1、问题：求最短路径的Dijkstra算法的时间复杂度为（）n为图中顶点数，e为图中边数。选项：A、O（n）B、O（n+e）C、O（）D、O(ne)正确答案:【O（）】2、问题：求最短路径的Dijkstra算法不适用于有回路的有向网（）选项：A、正确B、错误正确答案:【错误】第七章单元测验1、问题：在一个图中，所有顶点的度之和是所有边数的()倍。选项：A、1/2B、1C、2D、3正确答案:【2】2、问题：在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的()倍。选项：A、1/2B、1C、2D、4正确答案:【1】3、问题：一个有n个顶点的无向图最多有()条边。选项：A、nB、n*(n-1)C、(n*(n-1))/2D、2*n正确答案:【(n*(n-1))/2】4、问题：在一个具有n个顶点的无向图中，要连通全部顶点至少需要()条边。选项：A、nB、n+`C、n-1D、n/2正确答案:【n-1】5、问题：对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是()。选项：A、nB、n*nC、2*(n-1)D、n-1正确答案:【n*n】6、问题：对于一个具有n个顶点和e条边的无向图，若采用邻接表存储，则邻接表中的结点总数是()。选项：A、e/2B、2C、2*eD、n+e正确答案:【2*e】7、问题：以下说法错误的是()。选项：A、用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。B、邻接表只能用于有向图的存储，而邻接矩阵对于有向图和无向图的存储都适用。C、存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的下（或上）三角部分就可以了D、用邻接矩阵M表示图，判定任意两个结点Vi和Vj之间是否有长度为n的路径相连，则只要检查M的n次方后，第i行第j列的元素是否为0即可。正确答案:【邻接表只能用于有向图的存储，而邻接矩阵对于有向图和无向图的存储都适用。】8、问题：已知一个图的邻接矩阵表示，删除所有从第i个顶点出发的方法是（）。选项：A、将矩阵第i行删除，后序行上移B、将矩阵第i列删除，后序列左移C、将矩阵第i行上的元素全部置0D、将矩阵第i列上的元素全部置0正确答案:【将矩阵第i行上的元素全部置0】9、问题：某图的邻接表存储结构如下图所示，则从6号点出发，深度优先遍历的序列是（）选项：A、6-5-2-1-4-3B、6-5-1-2-4-3C、6-5-1-4-3-2D、6-5-2-1-4-3正确答案:【6-5-1-2-4-3】10、问题：某图的邻接矩阵存储结构如下图所示，则从6号点出发，广度优先遍历的序列是（）选项：A、6-1-2-5-4-3B、6-1-2-4-5-3C、6-5-1-4-3-2D、6-5-2-1-4-3正确答案:【6-1-2-5-4-3】11、问题：对具有n个顶点的连通图，其生成树有且仅有()条边。选项：A、n-1B、nC、n*nD、不确定正确答案:【n-1】12、问题：稀疏图采用（）存储较省空间。选项：A、邻接表B、邻接矩阵C、邻接多重表D、以上都可以正确答案:【邻接表】13、问题：关键路径是从源点到汇点的（）路径。选项：A、最长的B、最短的C、结点个数最少的D、结点个数最多的正确答案:【最长的】14、问题：在有向图的邻接矩阵上，第i行中的非零且非无穷元素个数是第i个结点的（）。选项：A、出度B、入度C、度D、邻接点个数正确答案:【出度】15、问题：关键路径上的活动都是关键活动，它们是否按时完成会影响工期。选项：A、正确B、错误正确答案:【正确】16、问题：求稀疏图的最小生成树，用克鲁斯卡尔算法来求解较高效。选项：A、正确B、错误正确答案:【正确】17、问题：求稠密图的最小生成树，用普里姆算法来求解较好。选项：A、正确B、错误正确答案:【正确】18、问题：迪杰斯特拉算法求最短路径时，是按照路径长度递增的顺序求解的。选项：A、正确B、错误正确答案:【正确】19、问题：一个有向图的拓扑排序只有一个。选项：A、正确B、错误正确答案:【错误】20、问题：每一个有向图肯定至少有一个拓扑排序。选项：A、正确B、错误正确答案:【错误】21、问题：具有6个顶点的无向图至少应有6条边才能确保是一个连通图。选项：A、正确B、错误正确答案:【错误】22、问题：非关键活动，可以无限期延迟。选项：A、正确B、错误正确答案:【错误】第1讲随堂测验1、问题：采用顺序查找法查找长度为n的线性表时，平均查找长度为。选项：A、nB、C、D、正确答案:【】2、问题：通常将作为衡量一个查找算法效率优劣的标准。选项：A、平均查找长度B、比较次数C、WPLD、ASL正确答案:【平均查找长度#ASL】3、问题：顺序查找方法只能在顺序存储结构上进行。（）选项：A、正确B、错误正确答案:【错误】4、填空题：顺序查找含n个元素的顺序表，若查找成功，则比较关键字的次数最多为次。正确答案:【n】5、填空题：顺序查找含n个元素的顺序表，若查找不成功，则比较关键字的次数为次。正确答案:【n+1】第2讲随堂测验1、问题：对列表进行折半查找时，要求列表必须。选项：A、顺序存储B、链式存储C、顺序存储且元素按关键字有序存储D、链式存储且元素按关键字有序存储正确答案:【顺序存储且元素按关键字有序存储】2、问题：当采用分块查找时，数据的组织方式要求。选项：A、数据分成若干块，每块内元素有序B、数据分成若干块，每块内元素不必有序，但块间必须有序，且每块内最大（或最小）的数据组成索引块；C、数据分成若干块D、数据分成若干块，每块（除最后一块外）中元素个数相等。正确答案:【数据分成若干块，每块内元素不必有序，但块间必须有序，且每块内最大（或最小）的数据组成索引块；】3、问题：有一个有序表{1,3,9,12,32,41，45,62,75,77,82,95,99}当采用折半查找法查找关键字为82的元素时，需经过次比较后查找成功。选项：A、1B、2C、4D、8正确答案:【4】4、问题：折半查找可以在有序的双向链表上进行。（）选项：A、正确B、错误正确答案:【错误】第3讲随堂测验1、问题：如图所示的二叉排序树，，起查找成功时的平均查找长度是。选项：A、B、C、D、正确答案:【】2、问题：在一棵平衡二叉树中，每个结点的平衡因子的取值范围是。选项：A、-1——1B、-2——2C、1——2D、0——1正确答案:【-1——1】3、问题：查找效率最高的二叉排序树