数据结构(C语言版)考研复习题.doc

《数据结构(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,i

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