数据结构习题

第一章1．在数据结构中，从逻辑上能够把数据结构分为〔C〕A．动向结构和静态结构B.紧凑结构和非紧凑结构C．线性结构和非线性结构D.内部结构和外部结构在数据结构中,与所使用的计算机无关的是(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次序接见相邻结点更容易假定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=148在次序表的〔最后一个结点之后〕插入一个新的数据元素不必移动任何元素。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.144C.148D.41216、假定长度为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.只允许在端点处插入和删除元素没有共同点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〕堆栈允许删除的一端称为栈顶，而栈底元素是不能删除的。X精选5、设有一个次序栈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〕与队头指针和队尾指针的值相关只与队尾指针的值相关，与队头指针的值无关只与数组的大小相关，与队首头指针和队尾指针的值无关与曾经进行过多少次插入操作相关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〕。它们拥有一般线性表所没有的逻辑特性它们的存储结构特殊对它们的使用方法做了限制它们比一般线性表更简单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-next精选20、假定行列采用链式存储结构，队头元素指针与队尾元素指针分别为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.front=p->next22、在循环行列中，假定front与rear分别表示队头元素和队尾元素的地点，那么判断循环行列队空的条件是〔C〕。A.front=rear+1B.rear=front+1C.front==rearD.front==rear==023、假定描绘某循环行列的数组为为Circle[M]，当循环行列满时，行列中有〔B〕个元素。A.MB.M-1C.M+1D.M+224、在解决心算机主机与打印机之间速度不匹配问题时往常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机那么依次从该