欢迎来到天天文库
浏览记录
ID:50881853
大小:146.00 KB
页数:19页
时间:2020-03-15
《数据结构(C语言版)考研复习题.doc》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、第一章绪论1.1简述下列概念:数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。1.2常用的存储表示方法有哪几种?1.3算法的时间复杂度仅与问题的规模相关吗?1.4有时为了比较两个同数量级算法的优劣,须突出主项的常数因子,而将低次项用大"O"记号表示。例如,设T1(n)=1.39nlgn+100n+256=1.39nlgn+O(n),T2(n)=2.0nlgn-2n=2.0lgn+O(n),这两个式子表示,当n足够大时T1(n)优于T2(n),因为前者的常数因子小于后者。请用此方法表示下列函数,并指出当n足够大时,哪一个较优,哪一个较
2、劣?函数 大"O"表示 优劣 (1)T1(n)=5n2-3n+60lgn 5n2+O(n) (2)T2(n)=3n2+1000n+3lgn 3n2+O(n) (3)T3(n)=8n2+3lgn 8n2+O(lgn) (4)T4(n)=1.5n2+6000nlgn 1.5n2+O(nlgn)第二章线性表2.1试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。2.2何时选用顺序表、何时选用链表作为线性表的存储结构为宜?2.3为什么在单循环链表中设置尾指针比设置头指针更好?2.4下述算法的功能是什么? Link
3、ListDemo(LinkListL){//L是无头结点单链表 ListNode*Q,*P; if(L&&L->next){ Q=L;L=L->next;P=L; while(P->next)P=P->next; P->next=Q;Q->next=NULL; } returnL; }//Demo2.5设线性表的n个结点定义为(a0,a1,...an-1),重写顺序表上实现的插入和删除算法:InsertList和DeleteList.2.6设顺序表L是一个递减有序表,试写一算法,将x插入其后仍保持L的有序性。2.7写一算
4、法在单链表上实现线性表的ListLength(L)运算。2.8写一算法将单链表中值重复的结点删除,使所得的结果表中各结点值均不相同。第三章栈和队列3.1设将整数1,2,3,4依次进栈,但只要出栈时栈非空,则可将出栈操作按任何次序夹入其中,请回答下述问题: (1)若入、出栈次序为Push(1),Pop(),Push(2),Push(3),Pop(),Pop(),Push(4),Pop(),则出栈的数字序列为何(这里Push(i)表示i进栈,Pop()表示出栈)? (2)能否得到出栈序列1423和1432?并说明为什么不能得到或者如何得到。 (3)请分析
5、1,2,3,4的24种排列中,哪些序列是可以通过相应的入出栈操作得到的。 3.2链栈中为何不设置头结点?3.3循环队列的优点是什么?如何判别它的空和满? 3.4设长度为n的链队用单循环链表表示,若设头指针,则入队出队操作的时间为何?若只设尾指针呢?3.5指出下述程序段的功能是什么? (1)voidDemo1(SeqStack*S){ inti;arr[64];n=0; while(StackEmpty(S))arr[n++]=Pop(S); for(i=0,i6、kS1,S2,tmp; DataTypex; ...//假设栈tmp和S2已做过初始化 while(!StackEmpty(&S1)) { x=Pop(&S1); Push(&tmp,x); } while(!StackEmpty(&tmp)) { x=Pop(&tmp); Push(&S1,x); Push(&S2,x); }(3)voidDemo2(SeqStack*S,intm) {//设DataType为int型 SeqStackT;inti; InitStack(&T); 7、while(!StackEmpty(S)) if((i=Pop(S))!=m)Push(&T,i); while(!StackEmpty(&T)) { i=Pop(&T);Push(S,i); } }(4)voidDemo3(CirQueue*Q) {//设DataType为int型 intx;SeqStackS; InitStack(&S); while(!QueueEmpty(Q)) {x=DeQueue(Q);Push(&S,x);} while(!StackEmpty(&s)8、) {x=Pop
6、kS1,S2,tmp; DataTypex; ...//假设栈tmp和S2已做过初始化 while(!StackEmpty(&S1)) { x=Pop(&S1); Push(&tmp,x); } while(!StackEmpty(&tmp)) { x=Pop(&tmp); Push(&S1,x); Push(&S2,x); }(3)voidDemo2(SeqStack*S,intm) {//设DataType为int型 SeqStackT;inti; InitStack(&T);
7、while(!StackEmpty(S)) if((i=Pop(S))!=m)Push(&T,i); while(!StackEmpty(&T)) { i=Pop(&T);Push(S,i); } }(4)voidDemo3(CirQueue*Q) {//设DataType为int型 intx;SeqStackS; InitStack(&S); while(!QueueEmpty(Q)) {x=DeQueue(Q);Push(&S,x);} while(!StackEmpty(&s)
8、) {x=Pop
此文档下载收益归作者所有