数据结构自测题

经典word整理文档，仅参考，双击此处可删除页眉页脚。本资料属于网络整理，如有侵权，请联系删除，谢谢！一．绪论1.1单项选择题①②DR是D①②。。①②①②1.2填空题（将正确的答案填在相应的空中）、和为。。。,_。,,_,。1。。。{}。第二章基础知识一、选择题1、线性表是_______。A.一个有限序列，可以为空C.一个无限序列，可以为空一个有限序列，不能为空D.一个无限序列，不能为空2、在一个长度为n的顺序存储的线性表中，向第i1i）位置插入一个新元素时，需要从后向前依次后移______个元素。A.n-iB.n-i+1C.n-i-1D.i3、在一个长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次数为_______。A.(n+1)/2B.n/2C.nD.n+14、在一个顺序表的表尾插入一个元素的时间复杂性的量级为_______。A.O(n)B.O(1)C.O(n)D.O(logn)225、设单链表中指针p指向结点a，若要删除aii2改指针的操作为____________。A.p->next=p->next->next;C.p=p->next->next;B.p=p->next;D.next=p;6、设单链表中指针p指向结点a，指针f指向将要插入的新结点x，问：i（1）当x插在链表中两个数据元素a和a之间时，只要先修改______后修改ii+1______即可。A.p->next=fC.p->next=f->nextE.f->next=NULLB.p->next=p->next->nextD.f->next=p->nextF.f->next=p（2）在链表中最后一个结点a______后修改______即n可。A.f->next=pC.p->next=fE.f=NULLB.f->next=p->nextD.p->next=f->next7、在一个单链表中，若要在p所指向的结点之前插入一个新结点，则此算法的时间复杂度为________。A.O(n)B.O(n/2)C.O(1)D.O(n)8、不带头结点的单链表L为空的判定条件为_________。A.L==NULLC.L->next==LB.L->next==NULLD.L!=NULL9、带头结点的单链表L为空的判定条件为_________。A.L==NULLC.L->next==LB.L->next==NULLD.L!=NULL10、指针p指向双向链表中的结点a，为a的前驱结点，指针f指向将要插aii1i入的新结点x。x插在a和a之间，此时需要修改指针的操作依次为i1i_________________。A.p->prior->next=fC.f->next=pB.p->prior=fD.f->prior=p->priorp所指的结点之后插入一个q指针所指向的结点，则需要对q->next赋值为______。A.p->priorB.p->nextC.p->next->nextC.p->prior->prior二、填空题：1、线性表的两种存储结构分别为__________和_______________。2_______经常需要对线性表进行查找运算，则最好采用________存储结构。3、访问一个线性表中具有给定值元素的时间复杂度为__________。34、对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为______，在表尾插入元素的时间复杂度为___________。5、单链表是____________的链接存储表示。6p所指向的结点的后面插入一个指针q所指向的结点时，首先把_______的值赋给q->next，然后把__________的值赋给p->next。7p所指结点之前插入一个s（1）s->next=______________;（2）p->next=s;（3）t=p->data;（4）p->data=______________;（5）s->data=______________;8、假定指向单链表中第一个结点的表头指针为，则向该单链表的表头插入指针p所指向的新结点时，首先执行____________赋值操作，然后执行________________赋值操作。9p_____________的值赋给p->next指针域。10、在一个单链表中删除指针p所指结点时，应执行以下操作：q=p->next;p->data=p->next->data;p->next=___________;free(q);________来确定它，即通过头指针或尾指针可以访问到该链表中的每个结点。12p复杂性的量级为___________________。三、简答题1、对于线性表的两种存储结构，如果线性表的总数基本稳定，并且很少进行插储结构？试说明理由。2、有哪些链表可仅由一个尾指针来唯一确定，即从尾指针出发能访问到链表上任何一个结点？3、在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删除？若可以，其时间复杂度各为多少？4四、算法阅读题读下面的程序段，画出执行过程的示意图及所完成的功能。1.#defineN6voidmain(){SqListL;intA[N];inti,j,m,elem;InitList_Sq(L);//初始化顺序表for(j=0;j<N;j++)scanf("%d",&A[j]);for(m=0;m<N;m++)ListInsert_Sq(L,m+1,A[m]);PrintList(L);//输出函数，顺序输出表中元素}2.intA(LinkListL){/*L是无表头结点的单链表*/if(L&&L->next){Q=L;L=L->next;P=L;while(P->next)P=P->next;P->next=Q;Q->next=NULL;}return1;}3.voidBB(LNode*s,LNode*q){p=s;while(p->next!=q)p=p->next;p->next=s;}voidAA(LNode*pa,LNode*pb){/*pa和pb分别指向单循环链表中两个节点*/5BB(pa,pb);BB(pb,pa);}五、算法设计题1、分别编写在顺序表和带头结点的单链表上统计出值为x的元素个数的算法，统计结果由函数值返回。2An将x插入到线性表的适当位置，以保持线性表的有序性。3、已知两个单链表A和，指向头结点的指针分别为La和，试编写一个算法从单链表A中删除自第i个元素起的共length表B的第j个元素之前。4B和CA作如下运算：删去那些既在表B中出现又在表C中出现的元素。试分别以两种存储结构（一种顺序的，一种链式的）编写实现上述运算的算法。5、已知线性表的元素是无序的，且以带头结点的单链表作为存储结构。试编写一个删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素）的算法。6、有两个循环不带头结点的单链表如图所示，编写一个算法将链表1连接到链表2之后，并仍然保持循环链表形式。67、假设有一个单向循环链表，其结点含有三个域：，data和next，其中data为数据域；next为指针域，它指向后继结点；pre为指针域，它的值为空指针（8、编写算法实现顺序表的就地逆置，即利用原顺序表的存储单元把数据元素序列如（a,a,...,aa,a,...,a）。12nnn119、假设在长度大于1的循环单链表中，既无头结点也无头指针，p为指向该链表中某个结点的指针，编写一个算法删除该结点的前趋结点。10、设头指针为，编写算法实现带头结点单链表head的就地逆置，即利用原带头结点单链表head的结点空间把数据元素序列（a,a,...,a）逆置为01n1（a,...,a,an110数据元素x素的递增有序。12、设head为单链表的头指针，并设单链表带有头结点，编写算法将单链表中的数据元素按照元素值递增有序的顺序就地排序。13、编写不带头结点单链表的初始化操作、插入操作和删除操作。一、选择题1、栈的插入和删除操作在（A、栈顶B、栈底2123，np1p2p3pn,那么p1=n；pi为（Ａ、iＢ、n-i3、假设以I和O分别表示入栈和出栈操作，栈的初态和终态均为空，入栈）进行。C、任意位置D、指定位置Ｃ、n－i＋1Ｄ、不确定和出栈的操作序列可表示为仅由I和OＡ、IOIIOIOO4、递归函数可以调用自身（Ａ、至多1次Ｂ、任意次数Ｂ、IOOIOIIOCIIIOIOIOＣ、0次DOIIOIOIO）次。2次二、填空题1、线性表、栈和队列都是（）结构，可以在线性表的（）位置插入7和删除元素；对于栈只能在（）插入和删除元素；对于队列只能在（）插入元素和在（）删除元素。2应先判别栈是否为（m时，作进栈运算时发生上溢，则说明栈的可用最大容量为（3、设有一个空栈，现有输入序列1，2，3，4，5，经过push，push，pop，push，pop，push，push后，输出序列是（4、无论对于顺序存储还是链式存储的栈和队列来说，进行插入或删除操作的时间复杂度均相同为（5、有一个循环队列，分配到的存储空间大小为n，则其队满条件是（三、应用题１、若依次读入数据元素序列{a,b,c,d}进栈，进栈过程中允许出栈，试写出各种可能的出栈元素序列。2、以下代码段执行什么操作？StackS1，tmp；ElemtypeX；„While(！StackEmpty(S1)){Pop(S1,X)；Push(tmp，X)；}While(!StackEmpty(tmp)){Pop(tmp,X)；Push(S1，X)；}四、算法设计题1、有两个栈s1和s2共享存储空间c[m]（下标为0,...,m-1c[0]c[m-1]s1和s2的进栈Push(i,x)Pop(i,x)和设置栈空Setnull(i)的函数，其中i=1,2。注意：仅当整个空间c占满时才产生上溢。2、假设一个算术表达式中包含圆括弧、方括弧和花括弧3种类型的括弧，编写一个判别表达式中括弧是否正确配对的函数。以字符“#”作为算术表达式的结束符。3、回文是指正读和反读均相同的字符序列，如“”和“abdba”均是回文，但“”不是回文。试写一个算法判定给定的字符串是否回文，该字符串是从84、如果用一个循环数组q[num]表示队列时，该队列只有一个头指针front指向队首元素，不设队尾rear，而设置计数器count用以记录队列中结点的个数。编写实现队列的5EmptyqGetHead，OutQueue。提示]算法的思想：依照题意，可以得出以下条件：队列为空：count==0;队列为满：count==num;(front+count)%num;出队时新的队列首元素的位置：(front+1)%num;5、在一个循环队列中，设计一个标志flag用于标识是否为