数据结构习题及答案

第一章1．在数据构造中，从逻辑上能够把数据构造分为（C）A．动态构造和静态构造B.紧凑构造和非紧凑构造C．线性构造和非线性构造D.内部构造和外部构造2.在数据构造中,与所使用的计算机无关的是(A)A.逻辑构造B.存储构造C.逻辑和存储构造D.物理构造3.下面程序的时间复杂度为____O（mn）_______。for(inti=1;i<=m;i++)for(intj=1;j<=n;j++)S+=i第二章线性表链表不含有的特点是（A）A能够随机访问任一结点（次序）B插入删除不需要移动元素C不必事先预计空间D所需空间与其长度成正比2.不带头结点的单链表head为空的鉴定条件为（A），带头结点的单链表head为空的鉴定条件为（B）Ahead==nullBhead->next==nullChead->next==headDhead!=null3.在线性表的下列存储构造中，读取元素耗费时间最少的是（D）A单链表B双链表C循环链表D次序表4.对于只在表的首、尾两端进行手稿操作的线性表，宜采用的存储构造为(C)A次序表B用头指针表达的单循环链表C用尾指针表达的单循环链表D单链表5.在一种含有n个结点的有序单链表中插入一种新的结点，并保持链表元素仍然有序，则操作的时间复杂度为(D)AO(1)BO(log2n)CO(n2)DO(n)6.在一种长度为n(n>1)的单链表上，设有头和尾两个指针，执行(B)操作与链表的长度有关A删除单链表中第一种元素B删除单链表中最后一种元素C在第一种元素之前插入一种新元素D在最后一种元素之后插入一种新元素7.与单链表相比，双向链表的优点之一是(D)A插入删除操作更简朴B能够进行随机访问C能够省略表头指针或表尾指针D次序访问相邻结点更容易8.若list是某带头结点的循环链表的头结点指针，则该链表最后那个链结点的指针域(头结点的地址)中寄存的是(B)Alist的地址Blist的内容Clist指的链结点的值D链表第一种链结点的地址9.若list1和list2分别为一种单链表与一种双向链表的第一种结点的指针，则(B)Alist2比list1占用更多的存储单元Blist1与list2占用相似的存储单元Clist1和list2应当是相似类型的指针变量D双向链表比单链表占用更多的存储单元10.链表中的每个链结点占用的存储空间不必持续，这句话对的吗？(不对的)11.某线性表采用次序存储构造，元素长度为4，首地址为100，则下标为12的（第13个）元素的存储地址为148。V100+4*12=14811.在次序表的（最后一种结点之后）插入一种新的数据元素不必移动任何元素。12.若对线性表进行的操作重要不是插入删除，则该线性表宜采用（次序）存储构造，若频繁地对线性表进行插入和删除操作，则该线性表宜采用(链)存储构造。13、一种次序表所占用存储空间的大小与（B）无关。A．表的长度B.元素的寄存次序C.元素的类型D.元素中各的类型14、设存储分派是从低地址到高地址进行的。若每个元素占用4个存储单元，则某元素的地址是指它所占用的单元的（A）。A.第1个单元的地址B.第2个单元的地址C.第3个单元的地址D.第4个单元的地址15、若线性表采用次序存储构造，每个元素占用4个存储单元，第1个元素的存储地址为100，则第12个元素的存储地址是（B）。A.112B.144C16、若长度为n的线性表采用次序存储构造，在表的第i个位置插入一种数据元素，i的正当值应当是(D)。A.i>0B.i<=nC.1<=i<=nD.1<=i<=n+117、若长度为n的非空线性表采用次序存储构造，删除表的第i个数据元素，i的正当值应当是（C）。A.i>0B.y<=nC.1<=i<=nD.d<=i<=i+118、若长度为n的非空线性表采用次序存储构造，删除表的第i个数据元素，首先需要移动表中（B）个数据元素。A.n-iB.n+iC.n-i+1D.n-i-119、若长度为n的非空线性表采用次序存储构造，在表的第i个位置插入一种数据元素，首先需要移动表中（C）个数据元素。A.iB.n+iC.n-i+1D.n-i-120、若频繁地对线性表进行插入和删除操作，该线性表应当采用（C）存储构造。A.散列B.次序C.链式D.索引21、链表中的每一种链结点所占用的存储单元（B）。A.不必持续B.一定持续C.部分持续D.持续与否无所谓22、在一种含有n个链结点的线性链表中查找某一种链结点，若查找成功，需要平均比较（C）个链结点。A.nB.n/2C.(n+1)/2D.(n-1)/223、给定含有n个元素的次序表，建立一种有序线性链表的时间复杂度为（C）。A.O(1)B.O(n)C.O(n2)D.O(log2n)24、在非空线性链表中由p所指的链结点背面插入一种由q所指的链结点的过程是依次执行（B）。A.q->next=p;p->next=q;B.q->next=p->next;p->next=q;C.q->next=p->next;p=q;D.p->next=q;q->next=p;25、若删除非空线性链表中由p所指的链结点的直接后继链结点的过程过程是依次执行（B）。A.r=p->next;p->next=r;free(r);B.r=p->next;p->next=r->next;free(r);C.r=p->next;p->next=r->next;free(p);D.p->next=p->next->next;free(p);26、在非空双向循环链表中由q所指的链结点背面插入一种由p所指的链结点的操作依次为p->prior=q;p->next=q->next;q->next=p;（C）。A.q->prior=pB.q->next->prior=pC.p->next->prior=p;D.p->prior->next=p;27、在非空双向循环链表中由q所指的链结点前面插入一种由p所指的链结点的操作依次为p->next=q;p->prior=q->prior;q->prior=p;（D）。A.q->next=p;B.q->prior->next=p;C.p->next->prior=p;D.p->prior->next=p;28、次序存储的线性表(a1,a2,……,an),在任一结点前插入一种新结点时所需移动结点的平均次数为（D）。A.nB.n/2C.n+1D.(n+1)/229、在长度为n的次序表的第i（1≤i≤n+1）个位置上插入一种元素，元素的移动次数是(A)。A.n-i+1B.n-iC.iD.i-130、在线性表的下列存储构造中，读取元素耗费时间最少的是（D）。A.单链表B.双链表C.循环链表D.次序表31、在以单链表为存储构造的线性表中，数据元素之间的逻辑关系用（C）。A.数据元素的相邻地址表达B.数据元素在表中的序号表达C.指向后继元素的指针表达D.数据元素的值表达25、假设指针p指向单链表中的某一结点，若把p指针背面的结点删除，只需修改下列哪个指针值即可（

）。A．p=p->next;

B．p->next=p->next->nextC．p=p->next->next;

D．p->next=p;26、在一种单链表HL中，若要在指针q所指结点的背面插入一种由指针P所指向的结点，则执行(

D

)。A．q->next＝p->next；p->next＝qB．p->next＝q->next；q＝p；C．q->next＝p->next；p->next＝q；D．p->next＝q->next；q->next＝p；27、构造一种空的线性表L用（

A

）A.InitList(&L)B.DestroyList(&L)

C.ListEmpty(L)D.ClearList(&L)第三章1、栈和队列的共同点是（C）A.都是先进后出B.都是先进先出在C.只允许在端点处插入和删除元素D.没有共同点2、一种栈的进栈次序是a,b,c,d,e，则栈的出栈次序不可能是（C）A.edcbaB.decbaC.dceabD.adcbe3、设n个元素的进栈序列为1,2,3,……,n，出栈序列为p1,p2,p3,……,pn，若p1=n，则pi(1<=i<=n)的值为（C）。A.iB.n-iC.n-i+1D.有多个可能4、判断下面的说法与否对的（1）插入和删除操作比较简朴，是链式栈和链式队列的优点之一。X（2）堆栈允许删除的一端称为栈顶，而栈底元素是不能删除的。X5、设有一种次序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素的出栈次序为s2,s3,s4,s6,s5,s1，则次序栈的容量最少应为多少？6、若数组s[0..n-1]为两个栈，s1和s2的共用存储空间，且仅当s[0..n-1]全满时，各栈才不能进行进栈操作，则为这两个栈分派空间的最佳方案是：s1和s2的栈顶指针的初值分别为（C）。A.1和n+1B.1和n/2C.-1和nD.-1和n+17、鉴定一种次序栈st（最多元素为Maxsize）为空的条件为（B），判断栈满的条件为(D).A.st.top!=-1B.st.top==0C.st.top!=MaxsizeD.st.top==Maxsize8、循环次序队列中与否能够插入下一种元素，（A）A.与队头指针和队尾指针的值有关B.只与队尾指针的值有关，与队头指针的值无关C.只与数组的大小有关，与队首头指针和队尾指针的值无关D.与曾经进行过多少次插入操作有关9、若用一种大小为6的一维数组来实现循环队列，且现在rear和front的值分别为0和3，当从队列中删除1个元素，然后再插入2个新元素后，rear和front的值分别为（B）。A.1和5B.2和4C.4和2D.5和110、用单链表表达队列时，队头应当在单链表的（A）位置。A.链头B.链尾C.链中D.任意11、堆栈和队列的共同之处在于它们含有相似的（A）。A.逻辑特性B.物理特性C.运算办法D.元素类型12、堆栈和队列都是特殊的线性表，其特殊性在于（C）。A.它们含有普通线性表所没有的逻辑特性B.它们的存储构造特殊C.对它们的使用办法做了限制D.它们比普通线性表更简朴13、若5个元素的出栈序列为1，2，3，4，5，则进栈序列可能是（D）。A.24315B.23154C.31425D.14、若堆栈采用次序存储构造，正常状况下，向堆栈中插入一种元素，栈顶指针top的变化是（D）A.不变B.top=0C.top--D.top++15、若堆栈采用次序存储构造，正常状况下，删除堆栈中一种元素，栈顶指针top的变化是（C）A.不变B.top=0C.top--D.top++16、若队列采用次序存储构造，元素的排列次序（B）。A.与元素的值的大小有关B.由元素进入队列的先后次序决定C.与队头指针和队尾指针的取值有关D.与作为次序存储构造的数组的大小有关17、“链接队列”这一概念不涉及（B）。A.数据的存储构造B.数据的逻辑构造C.对数据进行的操作D.链表的种类18、若堆栈采用链式存储构造，栈顶指针为top，向堆栈插入一种由p所指的新结点的过程是依次执行（C）,top=pA.p=topB.top=pC.p->next=topD.top->next=p19、若非空堆栈采用链式存储构造，栈顶指针为top，删除堆栈一种元素的过程是依次执行p=top；（B）;free(p)A.top=pB.top=p->nextC.p=top->nextD.p=p-next20、若队列采用链式存储构造，队头元素指针与队尾元素指针分别为front和rear，向队列中插入一种由p所指的新结点的过程是依次执行：（C）;rear=p;A.rear=pB.front=pC.rear->next=pD.front->next=p21、若非空队列采用链式存储构造，，队头元素指针与队尾元素指针分别为front和rear，删除队列的一种元素的过程是依次执行：p=front;(D);free(p)A.rear=pB.rear=p->nextC.p->next=rearD.f