数据结构习题及标准答案

1、第一章1 .在数据结构中，从逻辑上可以把数据结构分为（C）A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构2 .在数据Z构中，与所使用的计算机无关的是（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）,带头结点的单链表hea

2、d为空的判定条件为（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）的单链表上，设有头和尾两个指

3、针，执行（B）操作与链表的长度有关A删除单链表中第一个元素B删除单链表中最后一个元素C在第一个元素之前插入一个新元素D在最后一个元素之后插入一个新元素7 .与单链表相比，双向链表的优点之一是（D）A插入删除操作更简单B可以进行随机访问C可以省略表头指针或表尾指针D顺序访问相邻结点更容易8 .若list是某带头结点的循环链表的头结点指针，则该链表最后那个链结点的指针域（头结点的地址）中存放的是（B）Alist的地址Blist的内容Clist指的链结点的值D链表第一个链结点的地址9 .若list1和list2分别为一个单链表与一个双向链表的第一个结点的指针，则（B）Alist2比list1占用更多

4、的存储单元Blist1与list2占用相同的存储单元Clist1和list2应该是相同类型的指针变量D双向链表比单链表占用更多的存储单元10 .链表中的每个链结点占用的存储空间不必连续，这句话正确吗（不正确）11 .某线性表采用顺序存储结构，元素长度为4,首地址为100,则下标为12的（第13个）元素的存储地址为148。V100+4*12=14812 .在顺序表的（最后一个结点之后）插入一个新的数据元素不必移动任何元素。13 .若对线性表进行的操作主要不是插入删除，则该线性表宜采用（顺序）存储结构，若频繁地对线性表进行插入和删除操作，则该线性表宜采用（链）存储结构。13、一个顺序表所占用存储空

5、间的大小与（B）无关。A.表的长度B.元素的存放顺序C.元素的类型D.元素中各的类型14、设存储分配是从低地址到高地址进行的。若每个元素占用4个存储单元，则某元素的地址是指它所占用的单元的（A）。A.第1个单元的地址B.第2个单元的地址C.第3个单元的地址D.第4个单元的地址15、若线性表采用顺序存储结构，每个元素占用4个存储单元，第1个元素的存储地址为100,则第12个元素的存储地址是（B）。A.112B.144C.148D.41216、若长度为n的线性表采用顺序存储结构，在表的第i个位置插入一个数据元素，i的合法值应该是（D）。A.i>0<=n<=i<=nD.1&l

6、t;=i<=n+117、若长度为n的非空线性表采用顺序存储结构，删除表的第i个数据元素，i的合法值应该是（C）。A.i>0<=n<=i<=nD.d<=i<=i+118、若长度为n的非空线性表采用顺序存储结构，删除表的第i个数据元素，首先需要移动表中（B）个数据元素。A.n-i+iC.n-i+1D.n-i-119、若长度为n的非空线性表采用顺序存储结构，在表的第i个位置插入一个数据元素，首先需要移动表中（C）个数据元素。A.iB.n+i+120、若频繁地对线性表进行插入和删除操作，该线性表应该采用（C）存储结构。A.散列B.顺序C.链式D.索引21、链表

7、中的每一个链结点所占用的存储单元（B）。A.不必连续B.一定连续C部分连续D.连续与否无所谓22、在一个具有n个链结点的线性链表中查找某一个链结点，若查找成功，需要平均比较（C）个链结点。A.nB.n/2C.(n+1)/2D.(n-1)/223、给定具有n个元素的顺序表，建立一个有序线性链表的时间复杂度为(C)。A.O(1)(n)(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->ne

8、xt=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所指的链结点的操作依次

9、为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)。>next=p;B.q->prior->next=p;C.p->next->prior=p;

10、D.p->prior->next=p;28、顺序存储的线性表(a1,a2,，an),在任一结点前插入一个新结点时所需移动结点的平均次数为(D)。A.nB.n/2C.n+1D.(n+1)/229、在长度为n的顺序表的第i(1Wiwn+1位置上插入一个元素，元素的移动次数是(A)。A.n-i+1B.n-iC.iD.i-130、在线性表的下列存储结构中，读取元素花费时间最少的是(D)。A.单链表B.双链表C.循环链表D.顺序表31、在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用(C)。A.数据元素的相邻地址表示B.数据元素在表中的序号表示C.指向后继元素的指针表示D.数据元素的

11、值表示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->n

12、ext=q->next;q->next=p;27、构造一个空的线性表L用(A)(&L)(&L)(L)(&L)第三章1、栈和队列的共同点是(C)A.都是先进后出B.都是先进先出在C.只允许在端点处插入和删除元素D.没有共同点2、一个栈的进栈顺序是a,b,c,d,e,则栈的出栈顺序不可能是(C)A.edcbaC.dceabD.adcbe3、设n个元素的进栈序列为1,2,3,n，出栈序列为p1,p2,p3,pn,若p1=n，则pi(1<=i<=n)的值为(C)。A.iB.n-i+1D.有多种可能4、判断下面的说法是否正确(1)插入和删除操作比较简单，是

13、链式栈和链式队列的优点之一。X(2)堆栈允许删除的一端称为栈顶，而栈底元素是不能删除的。X5、设有一个顺序栈S,元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素的出栈顺序为s2,s3,s4,s6,s5,s1,则顺序栈的容量至少应为多少6、若数组s0.n-1为两个栈，si和s2的共用存储空间，且仅当s0.n-1全满时，各栈才不能进行进栈操作，则为这两个栈分配空间的最佳方案是：s1和s2的栈顶指针的初值分别为（C）。A.1和n+1B.1和n/2C.-1和nD.-1和n+17、判定一个顺序栈st（最多元素为Maxsize）为空的条件为（B）,判断栈满的条件为（D）.A.!=-1B.=0C

14、.!=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.逻辑特性

15、B.物理特性C.运算方法D.元素类型12、堆栈和队列都是特殊的线性表，其特殊性在于（C）。A.它们具有一般线性表所没有的逻辑特性B.它们的存储结构特殊C.对它们的使用方法做了限制D.它们比一般线性表更简单13、若5个元素的出栈序列为1,2,3,4,5,则进栈序列可能是（D）。B.23154C.31425D.3125414、若堆栈采用顺序存储结构，正常情况下，向堆栈中插入一个元素，栈顶指针top的变化是（D）A.不变B.top=0C.top-D.top+15、若堆栈采用顺序存储结构，正常情况下，删除堆栈中一个元素，栈顶指针top的变化是（C）A.不变B.top=0C.top-D.top+16、若

16、队列采用顺序存储结构，元素的排列顺序（B）。A.与元素的值的大小有关B.由元素进入队列的先后顺序决定C.与队头指针和队尾指针的取值有关D.与作为顺序存储结构的数组的大小有关17、“链接队列”这一概念不涉及（B）。A.数据的存储结构B.数据的逻辑结构C.对数据进行白操作D.链表的种类18、若堆栈采用链式存储结构，栈顶指针为top,向堆栈插入一个由p所指的新结点的过程是依次执行（C）,top=pA.p=topB.top=pC.p->next=top>next=p19、若非空堆栈采用链式存储结构，栈顶指针为top,删除堆栈一个元素的过程是依次执行p=top;（B）;free（p）=pB.

17、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）=pB.rear=p->nextC.p->next=rearD.front=p->next22、在循环队列中，若front与rear分别表示队头元素和队尾元素的位置，则判断循环队列队空的条件是（C）。A.front=rear+1B.rear=front+1C.front=rearD.front=rear=023、若描述某循环队列的数组为为CircleM,当循环队列满时，队列中有（B）个元素。A.MB.M-1C.M+1D.M+224、在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲