数据结构习题及标准答案

1/5第一章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!=null3.在线性表的下列存储结构中，读取元素花费时间最少的是（D）A单链表B双链表C循环链表D顺序表4.对于只在表的首、尾两端进行手稿操作的线性表，宜采用的存储结构为(C)A顺序表B用头指针表示的单循环链表C用尾指针表示的单循环链表D单链表5.在一个具有n个结点的有序单链表中插入一个新的结点，并保持链表元素仍然有序，则操作的时间复杂度为(D)AO(1)BO(log2n)CO(n2)DO(n)6.在一个长度为n(n1)的单链表上，设有头和尾两个指针，执行(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.若对线性表进行的操作主要不是插入删除，则该线性表宜采用（顺序）存储结构，若频繁地对线性表进行插入和删除操作，则该线性表宜采用(链)存储结构。2/513、一个顺序表所占用存储空间的大小与（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.41216、若长度为n的线性表采用顺序存储结构，在表的第i个位置插入一个数据元素，i的合法值应该是(D)。A.i0B.i=nC.1=i=nD.1=i=n+117、若长度为n的非空线性表采用顺序存储结构，删除表的第i个数据元素，i的合法值应该是（C）。A.i0B.y=nC.1=i=nD.d=i=i+118、若长度为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)/223、给定具有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;3/527、在非空双向循环链表中由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）堆栈允许删除的一端称为栈顶，而栈底元素是不能删除的。X4/55、设有一个顺序栈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.3125414、若堆栈采用顺序存储结构，正常情况下，向堆栈中插入一个元素，栈顶指针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-next5/520、若队列采用链式存储结构，队头元素指针与队尾元素指针分别为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-nex