《数据结构复习资料及答案.doc》由会员分享，可在线阅读，更多相关《数据结构复习资料及答案.doc（28页珍藏版）》请在三一办公上搜索。
1、数 据 结 构 习 题 一 1.1 简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。 数据：指能够被计算机识别、存储和加工处理的信息载体。 数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干数据项组成。 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。 数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。 逻辑结构：指各数据元素之间的逻辑关系。 存储结构：就是数据的逻辑结构用计算机语言的实现。 线性结构：数据逻辑结构中的一
2、类，它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。 非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。1.2 试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。（看教材）1.3 常用的存储表示方法有哪几种?常用的存储表示方法有四种: 顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构。 链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦
3、相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构。 索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。 散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。1.4 设三个函数f,g,h分别为 f(n)=100n3+n2+1000 , g(n)=25n3+5000n2 , h(n)=n1.5+5000nlgn 请判断下列关系是否成立：1 f(n)=O(g(n) 2 g(n)=O(f(n) 3 h(n)=O(n1.5) (4) h(n)=O(nlgn) (1)成立。 这里我们复习一下渐近时间复杂度的表示法T(n)=O(f(n)，这里
4、的O是数学符号，它的严格定义是若T(n)和f(n)是定义在正整数集合上的两个函数，则T(n)=O(f(n)表示存在正的常数C和n0 ,使得当nn0时都满足0T(n)Cf(n)。用容易理解的话说就是这两个函数当整型自变量n趋向于无穷大时，两者的比值是一个不等于0的常数。这么一来，就好计算了吧。第(1)题中两个函数的最高次项都是n3,因此当n时，两个函数的比值是一个常数，所以这个关系式是成立的。 （2）成立。 （3）成立。 （4）不成立。1.5 设有两个算法在同一机器上运行，其执行时间分别为100n2和2n,要使前者快于后者，n至少要多大? 15最简单最笨的办法就是拿自然数去代呗。假定n取为10，
5、则前者的值是10000，后者的值是1024,小于前者，那我们就加个5，用15代入得前者为22500，后者为32768，已经比前者大但相差不多，那我们再减个1，用14代入得，前者为19600,后者为16384，又比前者小了，所以结果得出来就是n至少要是15. 1.6 设n为正整数，利用大O记号，将下列程序段的执行时间表示为n的函数。(1) i=1; k=0 while(in) k=k+10*i;i+; T(n)=n-1 T(n)=O(n) 这个函数是按线性阶递增的(2) i=0; k=0;dok=k+10*i; i+;while(in); T(n)=n T(n)=O(n) 这也是线性阶递增的(3
6、) i=1; j=0; while(i+j=n) if (i1 while (x=(y+1)*(y+1)y+; T(n)=n1/2 T(n)=O(n1/2) 最坏的情况是y=0，那么循环的次数是n1/2次，这是一个按平方根阶递增的函数。(5) x=91; y=100; while(y0)if(x100)x=x-10;y-;else x+; T(n)=O(1) 这个程序总共循环运行了1000次，但是我们看到n没有? 没。这段程序的运行是和n无关的，只是一个常数阶的函数。1.7 算法的时间复杂度仅与问题的规模相关吗? No,事实上，算法的时间复杂度不仅与问题的规模相关，还与输入实例中的元素取值等相
7、关，但在最坏的情况下，其时间复杂度就是只与求解问题的规模相关的。我们在讨论时间复杂度时，一般就是以最坏情况下的时间复杂度为准的。1.8 按增长率由小至大的顺序排列下列各函数：2100, (2/3)n，(3/2)n， nn , , n! ，2n ，lgn ,nlgn, n(3/2) 分析如下：2100 是常数阶； (2/3)n和 (3/2)n是指数阶,其中前者是随n的增大而减小的； nn是指数方阶； n 是方根阶, n! 就是n(n-1)(n-2). 就相当于n次方阶；2n 是指数阶，lgn是对数阶 ,nlgn是对数方阶, n(3/2)是3/2次方阶。根据以上分析按增长率由小至大的顺序可排列如下
8、： (2/3)n 2100 lgn n n(3/2) nlgn (3/2)n 2n n! next-next 和 rear, 查找时间都是O(1)。若用头指针来表示该链表，则查找终端结点的时间为O(n)。 2.5 在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?若可以，其时间复杂度各为多少?1. 单链表。当我们知道指针p指向某结点时，能够根据该指针找到其直接后继，但是由于不知道其头指针，所以无法访问到p指针指向的结点的直接前趋。因此无法删去该结点。2. 双链表。由于这样的链表提供双向链接，因此根据已知结点可以查找到其直接前趋和直接后继，
9、从而可以删除该结点。其时间复杂度为O(1)。3. 单循环链表。根据已知结点位置，我们可以直接得到其后相邻的结点位置(直接后继)，又因为是循环链表，所以我们可以通过查找，得到p结点的直接前趋。因此可以删去p所指结点。其时间复杂度应为O(n)。 2.6 下述算法的功能是什么?LinkList Demo(LinkList L) / 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;return L;/ Demo该算法的功能是：将开始结点摘下链接到终端结
10、点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。二、算法设计题 2.7 设线性表的n个结点定义为(a0,a1,.an-1)，重写顺序表上实现的插入和删除算法：InsertList 和DeleteList.解：#define ListSize 100/ 假定表空间大小为100#include #include void Error(char * message)fprintf(stderr,错误:%sn,message);exit(1);/从0开始计， 表空间大小应为101了typedef int Datatype ;/假定Datatype的类型为int型type
11、def structDatatype dataListSize;/ 向量data用于存放表结点int length; / 当前的表长度 Seqlist;/以上为定义表结构/-以下为要求算法-void InsertList ( Seqlist *L, Datatype x, int i)/将新结点x插入L所指的顺序表的第i个结点ai的位置上int j;if ( i L - length )Error(position error);/ 非法位置，退出if ( L-length=ListSize )Error(overflow); for ( j=L-length-1 ; j = i ; j -)
12、L-dataj+1=L-data j;L-datai=x ;L-length+ ;void DeleteList ( Seqlist *L, int i )/ 从L所指的顺序表中删除第i个结点aiint j; if ( i L- length-1)Error( position error ) ; for ( j = i+1 ; j length ; j+ ) L-data j-1 =L-data j; / 结点前移L- length- ; /表长减小 2.8 试分别用顺序表和单链表作为存储结构，实现将线性表(a0,a1,.an-1)就地逆置的操作，所谓就地指辅助空间应为O(1)。2.8 解：
13、按题意，为将线性表逆置，但辅助空间不能随表的规模增大。我们分别讨论顺序表和单链表的情况：1. 顺序表：要将该表逆置，可以将表中的开始结点与终端结点互换，第二个结点与倒数第二个结点互换，如此反复，就可将整个表逆置了。算法如下：/ 表结构定义同上void ReverseList( Seqlist *L)Datatype t ; /设置临时空间用于存放dataint i;for ( i=0 ; i length/2 ; i+) t = L-datai;/交换数据 L - data i = L - data L - length - 1 - i ; L - data L - length - 1 -
14、i = t ;2. 链表：也是可以用交换数据的方式来达到逆置的目的，但是由于是单链表，数据的存取不是随机的，因此算法效率太低，我们可以利用指针的指向转换来达到表逆置的目的。算法是这样的：/ 结构定义略LinkList ReverseList( LinkList head )/ 将head 所指的单链表逆置ListNode *p ,*q ;/设置两个临时指针变量if( head-next & head-next-next)/当链表不是空表或单结点时p=head-next;q=p-next;p - next=NULL;/将开始结点变成终端结点while (q)/每次循环将后一个结点变成开始结点p=
15、q;q=q-next ;p-next = head- next ;head-next = p;return head;return head;/如是空表或单结点表，直接返回head 2.9 设顺序表L是一个递增有序表，试写一算法，将x插入L中，并使L仍是一个有序表。2.9 解：因已知顺序表L是递增有序表，所以只要从头找起找到第一个比它大(或相等)的结点数据，把x插入到这个数所在的位置就是了。算法如下：void InsertIncreaseList( Seqlist *L , Datatype x )int i;for ( i=0 ; i length & L-data i next & p-n
16、ext-datax ) p=p-next;s=(ListNode *)malloc(sizeof(ListNode); s-data=x; s-next=p-next; p-next=s; return L; 2.11 写一算法在单链表上实现线性表的ListLength(L)运算。求单链表长只能用遍历的方法了，从头数到尾，总能数出来吧。算法如下：int ListLength ( LinkList L )int len=0 ;ListNode *p;p=L;/设该表有头结点while ( p-next )p=p-next;len+;return len; 2.12 已知L1和L2分别指向两个单链
17、表的头结点，且已知其长度分别为m和n。试写一算法将这两个链表连接在一起，请分析你的算法的时间复杂度。LinkList Link( LinkList L1 , LinkList L2 )/将两个单链表连接在一起ListNode *p , *q ;p=L1;q=L2;while ( p-next ) p=p-next;/查找终端结点p-next = q-next ;/将L2的开始结点链接在L1之后return L1 ;本算法的主要操作时间花费在查找L1的终端结点上，与L2的长度无关，所以本算的法时间复杂度为：m+1=O(m) 2.13 设A和B是两个单链表，其表中元素递增有序。试写一算法将A和B归
18、并成一个按元素值递减有序的单链表C，并要求辅助空间为O(1)，请分析算法的时间复杂度。根据已知条件，A和B是两个递增有序表，所以我们可以以A表为基础，按照插入单个元素的办法把B表的元素插入A表中，完成后，将表逆置就得到了一个按元素值递减有序的单链表C了。算法如下：LinkList MergeSort ( LinkList A , LinkList B )/ 归并两个递增有序表为一个递减有序表ListNode *pa , *pb , *qa , *qb ;pa=A;pb=B ;qa=A-next;qb=B-next;while ( qa & qb)if ( qb-data data )/ 当B中
19、的元素小于A中当前元素时，插入到它的前面pb=qb;qb=qb-next ;/ 指向B中下一元素pa-next=pb;pb-next=qa;pa=pb; else if ( qb-data = pa-data & qb-data data)/ 当B中元素大于等于A中当前元素且小于等于A中后一元素时，将此元素插入到A的当前元素之后pa=qa;qa=qa-next; / 保存A的后一元素位置pb=qb; qb=qb-next; / 保存B的后一元素位置pa-next=pb; /插入元素pb-next=qa;else / 如果B中元素总是更大,指针移向下一个A元素pa=qa;qa=qa-next;i
20、f ( qb )/ 如果A表已到终端而B表还有结点未插入/ 将B表接到A表后面pa-next=qb;LinkList C=ReverseList ( A );/ 调用前面2.8题所设计的逆置函数return C; /返回新的单链表C, 已是递减排列该算法的时间复杂度分析如下：算法中只有一个while 循环，在这个循环中，按照最坏的情况是B元素既有插到A的最前的，也有插到最后的，也就是说需要把A中元素和B中元素全部检查比较过，这时的所费时间就是m+n. 而新链表的长度也是m+n+1 (有头结点)，这样逆置函数的执行所费时间为m+n+1.所以可得整个算法的时间复杂度为：m+n+m+n+1=2(m+
21、n)+1= O(m+n)-以下是一位学友鲁周航提供的算法：我的算法思路为：当A、B都不空时，各取A、B表中的第一个结点比较，哪个值小，就把它用头插法插入C表。（利用原来的头结点，始终是取第一个结点比较）继续取值比较。当A表为空，或B表为空，则把剩余结点用头插法插入C表。void LinkList(Nodetype *A,Nodetype *B, Nodetype *C)/假设A和B已建立，C表的头结点已初始化 Nodetype *p, *q;p=A-Next;q=B-Next;while(p&q)/两表中都有数if(p-DataData)/如A中的结点值大于B中结点值A-Next=p-Next
22、;/A指向A表的下一个结点p-Next=C-Next;/把P的结点用头插法，插入C表。C-Next=p;p=A-Next;/P指向A表的第一个结点，继续比较elseB-Next=q-Next;/算理同上面q-Next=C-Next;C-Next=q;q=B-Next;if(p)/如A表还有结点，则把剩余结点，用头插法插入C表while(p)A-Next=p-Next;p-Next=C-Next;C-Next=p;p=A-Next;elseif(q)/如B表还有结点，则把剩余结点，用头插法插入B表while(q)B-Next=q-Next;q-Next=C-Next;C-Next=q;q=B-N
23、ext;free(A);/释放原头结点空间free(B);你的算法要排表两次，第一次为插入，第二次为逆序。 2.14 已知单链表L是一个递增有序表，试写一高效算法，删除表中值大于min 且小于max的结点(若表中有这样的结点)，同时释放被删结点的空间，这里min 和 max是两个给定的参数。请分析你的算法的时间复杂度。要解这样的问题，我们首先想到的是拿链表中的元素一个个地与max和min比较，然后删除这个结点，其实因为已知其是有序链表，所以我们只要找到大于min的结点的直接前趋结点，再找到小于max的结点，然后一并把中间的全部摘掉就可以了。 算法如下：void DeleteList ( Lin
24、kList L, DataType min , DataType max )ListNode *p , *q ,*r;p=L-next;while( p & p-data next;while( p & p-data next; free(r);/释放这个结点空间q-next=p;/把断点链上 2.15 写一算法将单链表中值重复的结点删除，使所得的结果表中各结点值均不相同。 本题 可以这样考虑，先取开始结点中的值，将它与其后的所有结点值一一比较，发现相同的就删除掉，然后再取第二结点的值，重复上述过程直到最后一个结点。第二种算法是将单链表按值的大小排序，排好后的结点按相同的删除。以下为周鲁航提供
25、的算法void DeleteList(Nodetype *L)Nodetype *p,*q,*s;if(L-Next=NULL|L-Next=NULL)printf(删除错误n);exit(0);p=L-Next;q=p-Next;while(p-Next!=NULL)while(q)s=q;if(q-Data=p-Data)s-Next=q-Next;free(q);q=s-Next;elseq=q-Next;p=p-Next; 2.16 假设在长度大于1的单循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点*s的直接前趋结点。已知指向这个结点的指针是*s，那
26、么要删除这个结点的直接前趋结点，就只要找到一个结点，它的指针域是指向*s的，把这个结点删除就可以了。算法如下：void DeleteNode( ListNode *s)/删除单循环链表中指定结点的直接前趋结点ListNode *p, *q;p=s;while( p-next!=s) q=p;p=p-next;q-next=s;/删除结点free(p);/释放空间 2.17 已知由单链表表示的线性表中，含有三类字符的数据元素(如：字母字符、数字字符和其它字符)，试编写算法构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。
27、解：要解决这样的问题，只要新建三个头结点，然后在原来的单链表中依次查询，找到一类字符结点时，就摘下此结点链接到相应头结点指明的新链表中就是了。算法如下：/设已建立三个带头结点的空循环链表A,B,C./以下是void DivideList( LinkList L, LinkList A, LinkList B, LinkList C) ListNode *p=L-next, *q;ListNode *a=A,ListNode *b=B;ListNode *c=C;while ( p )if ( p-data=a &p-datadata=A &p-datanext;/指向下一结点a-next=q;
28、/将字母结点链到A表中q-next=A;/ 形成循环链表a=a-next; / 指向下一结点else if( p-data=0 & p-datanext;b-next=q;q-next=B;b=b-next;else /分出其他字符结点q=p;p=p-next;c-next=q;q-next=C;c=c-next;/结束 2.18 设有一个双链表，每个结点中除有prior、data和next三个域外，还有一个访问频度域freq，在链表被起用之前，其值均初始化为零。每当在链表进行一次LocateNode(L,x)运算时，令元素值为x的结点中freq域的值加1，并调整表中结点的次序，使其按访问频度
29、的递减序排列，以便使频繁访问的结点总是靠近表头。试写一符合上述要求的LocateNode运算的算法。 给freq域的值加1比较容易。就是每次加1后需进行排序比较麻烦。我们可以这样考虑，每次访问一个值为x的结点后，从表头开始找，根据结点中的freq值，如果找到比它小的结点，就把当前结点摘下，插入到freq值比它小的结点前面，就完成排序了。算法如下：void LocateNode( LinkList L, DataType x)ListNode *p, *q;p=L-next;/带有头结点q=L-next;while( p )if( p-data!=x) p=p-next;else p-freq+
30、;break;while ( q )if( q-freq p-freq) q=q-next;else p-prior-next=p-next; /摘下当前结点p-next=q; /插入到freq不大于它的结点前p-prior=q-prior;第三章 线性表 习题及答案一、基础知识题3.2 链栈中为何不设置头结点?答：链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。3.3 循环队列的优点是什么? 如何判别它的空和满? 答：循环队列的优点是：它可以克服顺序队列的假上溢现象，能够使存储队列的向
31、量空间得到充分的利用。判别循环队列的空或满不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间。每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。3.4 设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何? 若只设尾指针呢? 答：当只设头指针时，出队的时间为1，而入队的时间需要n，因为每次入队均需从头指针开始查找，找到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为1。因为是循环链表，尾指针所指的下一个
32、元素就是头指针所指元素，所以出队时不需要遍历整个队列。3.5 指出下述程序段的功能是什么? (1) void Demo1(SeqStack *S)int i; arr64 ; n=0 ;while ( StackEmpty(S) arrn+=Pop(S);for (i=0, i n; i+) Push(S, arri); /Demo1 (2) SeqStack S1, S2, tmp;DataType x;./假设栈tmp和S2已做过初始化while ( ! StackEmpty (&S1) x=Pop(&S1) ;Push(&tmp,x);while ( ! StackEmpty (&tmp
33、) )x=Pop( &tmp);Push( &S1,x);Push( &S2, x); (3) void Demo2( SeqStack *S, int m) / 设DataType 为int 型SeqStack T; int i;InitStack (&T);while (! StackEmpty( S)if( i=Pop(S) !=m) Push( &T,i);while (! StackEmpty( &T)i=Pop(&T); Push(S,i); (4)void Demo3( CirQueue *Q)/ 设DataType 为int 型int x; SeqStack S;InitSta
34、ck( &S);while (! QueueEmpty( Q )x=DeQueue( Q); Push( &S,x);while (! StackEmpty( &s) x=Pop(&S); EnQueue( Q,x );/ Demo3(5) CirQueue Q1, Q2; / 设DataType 为int 型int x, i , m = 0;. / 设Q1已有内容， Q2已初始化过while ( ! QueueEmpty( &Q1) ) x=DeQueue( &Q1 ) ; EnQueue(&Q2, x); m+;for (i=0; i n; i+) x=DeQueue(&Q2) ; EnQ
35、ueue( &Q1, x) ; EnQueue( &Q2, x); (1)程序段的功能是将一栈中的元素按反序重新排列，也就是原来在栈顶的元素放到栈底，栈底的元素放到栈顶。此栈中元素个数限制在64个以内。 (2)程序段的功能是利用tmp栈将一个非空栈的所有元素按原样复制到一个空栈当中去。(3)程序段的功能是将一个非空栈中值等于m的元素全部删去。(4)程序段的功能是将一个循环队列反向排列，原来的队头变成队尾，原来的队尾变成队头。(5)首先指出程序可能有印刷错误，for语句中的n应为m才对。这段程序的功能是将队列1的所有元素复制到队列2中去，但其执行过程是先把队列1的元素全部出队，进入队列2，然后再把队列2的元素复制到队列1中。二、算法设计题 3.6 回文是指正读反读均相同的字符序列，如abba和abdba均是回文，但good不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈) /ishuiwen.h 存为头文件int IsHuiwen( char *S)SeqStack T;int i , l;char t;InitStack( &T);l=strlen(S);/求向量长度for ( i=0; il/2; i+)/将一半字符入栈Push( &T, Si);while( !EmptyStac
