数据结构复习测试卷附答案（一）

第页数据结构复习测试卷附答案1.设有5个元素的进栈序列为a，b，e,d，e，其榆出序列是c，e，d，b，a，则该栈的容量至少是()A、1B、2C、3D、4【正确答案】：D2.在一个单链表中，已知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;【正确答案】：C3.设栈的初始状态为空，当字符序列“n9_”作为栈的输入时，输出长度为3且可用作C语言标识符的序列有()A、4B、6C、3D、5【正确答案】：C4.如果以链表作为栈的存储结构，则退栈操作时(A、必须判断链栈是否满B、判断链栈元素的类型.C、必须判断链栈是否空D、对链栈不做任何判断【正确答案】：C5.数据的基本单位是()A、数据元素B、数据项C、数据类型D、数据变量【正确答案】：A6.关于线性表的正确说法是()A、每个元素都有一个前驱元素和一个后继元素B、线性表中至少有一个元素C、表中元素的排序顺序必须是由小到大或由大到小D、除第一个元素和最后一个元素外，其余每个元素有且仅有一个直接前驱元素和一个直接后继元素【正确答案】：D7.输入序列为ABC，输出序列为CBA时，经过的栈操作为(A、push,pop,push,pop,push,popB、push,push,push,pop,pop,popC、push,push.pop,pop,push,popD、push,pop,push.push,pop.pop【正确答案】：B8.非空循环单链表的头指针为head，则其尾指针p满足()A、p->next==NULLB、p==NULLC、p->next==headD、p==head【正确答案】：C9.以下属于顺序表的优点的是()。A、插入元素方便B、删除元素方便C、存储密度大D、以上都不对【正确答案】：C10.链栈与顺序栈相比有一个明显的优点，即()A、插入操作更方便B、通常不会出现栈满的情况C、总是不会出现栈空的情况D、删除操作重方便【正确答案】：B11.在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是A、0(1)。B、O(n)C、O(n2)D、0(nlogzn)【正确答案】：B12.算法在发生非法操作时可以做出处理的特性称为算法的()A、正确性B、易读性C、健壮性D、高效性【正确答案】：C13.非线性结构中的每个结点(A、无直接前驱结点B、无直接后继结点C、只有一个直接前驱结点和一个直接后继结点D、可能有多个直接前驱结点和多个直接后继结点【正确答案】：D14.数据结构通言研究数据的()及它们之间的相互联系。A、存储结构和逻辑结构B、存储和抽象C、联系和抽象D、联系与逻辑【正确答案】：A15.从逻辑上可以把数据结构分为()两大类A、动态结构和静态结构B、紧凑结构和非紧凑结构C、线性结构和非线性结构D、内部结构和外部结构【正确答案】：C16.在一个双链表中,在∗p结点之后插入结点∗q的操作是()A、q->prior=p;p->next=q;p->next->prior=q;q-next=p->next;B、q->next=p->next;p->next->prior=q;p->next=q;q->prior=p;C、p->next=q;q->prior=p;q->next=p->next;p->next->prior=q;D、p->next->prior=q;q->next=p->next;q->prior=p;p->next=q;【正确答案】：B17..若A是7×4的二维数组，按行优先方式顺序存储，元素AFOTO]的存储地址为1000，若每个元素占2个字节，则元素A[3[3]的存储地址为()。A、1015B、1016C、1028D、1030【正确答案】：D18.将序列(2,12,16,88,5,10,34排序。若前2趟排序的结果如下：第1趟排序后：2,12,16,10,5,34,88第2趟排序后：2,5,10,12,16,34,88则可能的排序算法是：()。A、冒泡排序B、归并排序C、插入排序D、快速排序【正确答案】：D19.不带头结点的单链表head为空的判定条件是(）A、head==NULLB、head->next==NULLC、head->next==headD、head!=NULL【正确答案】：A20.设abcdef以所给的次序进栈，若在进栈操作时，允许连续进栈操作，则下面得不到的序列为(A、fedcbaB、bcafedC、dcefbaD、cabdef【正确答案】：D21.一颗二又树的先序遍历为A.B.C.D,EF,中序遍历为C,B,A,E,D.F则后序遍历为()。A、C,B,E,F,D,AB、F,E,D,C,B,AC,B,E,D,F,AD、不确定【正确答案】：A22.向一个不带头结点的栈顶指针为lst的链栈中插入一个∗s结点时，则执行（）A、lst->next=s;B、s->next=lst->next;lst->next=s;C、s->next=lst;lst=sD、s->next=lst;lst=lst->next;【正确答案】：C23.若想存储固定数量的数据元素，关于采用不同存储方式的比较，下列说法中正确的是()。A、顺序存储比键式存储少占空间B、顺序存储比链式存储多占空间C、顺序存储和链式存储都要求占用整块存储空间D、链式卉储比顺序存储难于扩充空间【正确答案】：A24.在长度为n的()上，删除第一个元素，其算法的时间复杂度为0(n)。A、只有表头指针的不带表头结点的循环单链表B、只有表尾指针的不带表头结点的循环单键表C、只有表尾指针的带表头结点的循环单链表D、只有表头指针的带表头结点的循环单链表【正确答案】：A25.将两个各有n个元素的递增有序顺序表归并成一个有序顺序表，其最少的比较次数是()A、nB、2n-1C、2nD、n-1【正确答案】：A26.数据在计算机存储器内表示时，物理地址和逻辑地址相同并且是连续的，称为(A、存储结构B、逻辑结构C、顺序存储结构D、链式存储结构【正确答案】：C27.下面关于线性表的权述中，错误的是()A、线性表采用顺序存储，必须占用一片连续的存储单元B、线性表采用顺序存储，使于进行插入和删除操作C、线性表采用键式存储，不必占用一片连续的存储单元D、线性表采用键式存储，便于进行插入和删除操作【正确答案】：B28.以下各链表均不带头结点,其中最不适合用作链栈的链表是()A、只有表头指针没有表尾指针的循环双链表B、只有表尾指针没有表头指针的循环双链表C、只有表尾指针没有表头指针的循环单链表D、只有表头指针没有表尾指针的循环单链表【正确答案】：D29.在一个长度为n的单链表上，设有头指针h和尾指针t，执行()的时间复杂度与链表的长度有关。A、删除单键表中的第一个元素B、删除单链表中的最后一个元素C、在单键表第一个元素前插入一个新元素D、在单键表最后一个元素后插入一个新元素【正确答案】：B30.在单链表中，增加一个头结点的目的是().A、使单链表至少有一个结点B、标识链表中重要结点的位置C、方便运算的实现D、说明单链表是线性表的链式存储结构【正确答案】：C31.下列关于栈的叙述中正确的是A、在栈中只能插入数据B、在栈中只能删除数据C、栈是先进先出的线性表D、栈是先进后出的线性表【正确答案】：D32.以下关于单链表的叙述中，不正确的是()A、结点除自身信息外还包括指针城，因此存储密度小于顺序存储结构B、逻辑上相邻的元素物理上不必相邻C、可以通过头结点直接计算第i个结点的存储地址D、插入、删除运算操作方便，不必移动结点【正确答案】：C33.一个栈的输入序列为1，2,3，….，n，若输出序列的第1个元素是n，则第i(1≤i≤n)个输出的元素是（）A、不确定B、n-i+1C、iD、n-i【正确答案】：B34.设有两个长度为n的单链表，结点类型相同，若以hl为头结点指针的单链表是非循环的，以h2为头结点指针的单链表是循环的，则()。A、对于两个链表来说，删除第一个结点的操作，其时间复杂度都是O(1)B、对于两个链表来说，删除尾结点的操作，其时间复杂度都是0(n)C、循环链表要比非循环链表占用更多的内存空间D、hl和h2是不同类型的变量【正确答案】：B35.栈适合在()中应用。A、递归调用B、括号匹配的检查C、表达式求值D、以上都对【正确答案】：D36.已知last指向单链表的尾结点，将s所指结点插入在表尾，正确的操作是()。A、s->next=s,last=s,last->next=NULL;B、last->next=s,s->next=NULL,last=s;C、s->next=NULL,last->next=s,s=last;D、s->next=last,last->next=NULL,last=s;【正确答案】：B37.一颗二又树叶子结点有12个，度为1的结点有4个，则该二又树共有()个结点。A、27B、28C、29D、30【正确答案】：A38.向一个栈顶指针为hs的带头结点的链栈中插入一个∗s结点时，执行（）A、hs->next=s;B、s->next=hs->next;hs->next=s;C、s->next=hs;hs=sD、s->next=hs;hs=hs->next;【正确答案】：B39.通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着()A、数据具有同一特点B、不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致C、每个数据元素都一样D、数据元素所包含的数据项的个数要相等【正确答案】：B40.算法的时间复杂度取决于()A、问题的规模B、待处理数据的初态C、计算机的配置D、A和B【正确答案】：D41.一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是(A、15432B、54132C、23145D、23415【正确答案】：B42..一棵完全二又树上有1001个结点，其中叶子结点的个数是()。A、250B、500C、254D、501【正确答案】：D43.以下说法正确的是()A、数据元素是数据的最小单位B、数据项是数据的基本单位C、数据结构是带有结构的各数据项的集合D、一些表面上很不相同的数据可以有相同的逻辑结构【正确答案】：D44.循环队列的队满条件为()。A、(sq.rear+1)%maxsize==(sq.front+1)%maxsizeB、(sq.front+1)%-maxsize==sq.rearC、(sq.rear+1)%maxsize==sq.frontD、sq.rear==sq.Front【正确答案】：C1.当栈中元素为n个时，进栈操作发生数据上溢，则说明栈的最大容量为_______A、正确B、错误【正确答案】：B2.删除单链表L中某结点∗p之前的一个结点，其时间复杂度为0(1)A、正确B、错误【正确答案】：B3.栈是运算受限制的线性表。A、正确B、错误【正确答案】：A4.在单链表中，要删除某一指定的结点，必须找到该结点的直接前驱结点。A、正确B、错误【正确答案】：A5.将十进制数转换为二进制数是栈的典型应用之一。A、正确B、错误【正确答案】：A6.健壮的算法不会因非法的输入数据而出现莫名其妙的状态。A、正确B、错误【正确答案】：A7.数据元素是数据的最小单位。A、正确B、错误【正确答案】：B8.栈一定是顺序存储的线性结构。链式存储A、正确B、错误【正确答案】：B9.若一个栈的输入序列为:A，B，C，D，可以得到输出序列:C，A，B，DA、正确B、错误【正确答案】：B10.在栈空的情况下，不能做出栈操作，否则产生下溢。A、正确B、错误【正确答案】：A11.线性表的链式存储结构是一种随机存取的存储结构。A、正确B、错误【正确答案】：B12.数据项是数据不可分割的最小单位A、正确B、错误【正确答案】：A13.当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用顺序存储结构。A、正确B、错误【正确答案】：A14.算法的优劣与算法描述语言无关。A、正确B、错误【正确答案】：A15.链栈与顺序栈相比，其特点之一是通常不会出现栈满的情况。A、正确B、错误【正确答案】：A16.数据的逻辑结构是指数据的各项露类之间的逻辑关系。A、正确B、错误【正确答案】：B17.栈的特点是“后进先出”。A、正确B、错误【正确答案】：A填空题1.______是数据的最小单位是数据的基本单位。【正确答案】：数据项；数据元素2.在单链表中，在p所指结点之后插入s所指向结点，应执行s->next=_______和p->next=_____的操作。【正确答案】：p->next;S3.带头结点的双循环链表L为空表的条件是____【正确答案】：L->next==L，L→prior==L4.对于一个具有n个结点的单链表，在已知p所指结点后插入一个新结点的时间复杂度是_____;在给定值为x的结点后插入一个新结点的时间复杂是______【正确答案】：O(1);O(n)5.下列的代码是实现有序表二分（折半）查找的算法，请在空白处填写适当内容，使该程序功能完整。intbin_search(SqListL,ElemTypee){

intmid,low=0,high=L.length-1；

while(low<=high)

{

mid=__________________

if(e—L.elemfmid])

retunmid+1；

elseif(e<=L.elem[mid)

high=__________

else

low=___________

}

return-1；}

【正确答案】：low+(high–low)/2；mid-1；mid+1；6.在一个长度为n的顺序存储结构的线性表中，当向第i个元素(1≤i≤n+1)之前插入一个新元素时，需要从后向前一次后移_______个元素。【正确答案】：n-i+17.在顺序栈中，当栈顶指针top=0时，表示_____【正确答案】：空栈8.表达式ax(b+c)-d的后缀表达式是_____【正确答案】：abc+xd-三、9.对于双链表，在两个结点之间插入一个新结点时，需要修改_____个指针域;删除其中某个结点时，需要修改____个指针域。【正确答案】：4；210.在长度为n的顺序表中插入一个元素的时间复杂度为_____删除一个元素的时间复杂度为_______,查找特定值的元素的时间复杂度为______【正确答案】：O(n);O(n);O(n)11.若在长度为n的顺序表第i个元素之前插入一个元素，则需要向后移动的元素个数是______。【正确答案】：n-i+112.列代码的功能是返回带头结点的单链表L的逆转链表，请在空白处填写适当内容，使该程序功能完整。ListReverse(ListL){

PositionOld_head,New_head,Temp;

New_head=NULL;

Old_head=L->Next;

while(Old_head)

{

Temp