数据结构(C语言版)习题及答案第二章

1、习 题2.1选择题1、线性表的顺序存储结构是一种（ A ）的存储结构，线性表的链式存储结构是一种（ B ）的存储结构。A、随机存取 B、顺序存取 C、索引存取 D、散列存取2、对于一个线性，既要求能够进行较快的插入和删除，又要求存储结构能够反映数据元素之间的逻辑关系，则应该选择（ B ）。A、顺序存储方式 B、链式存储方式C、散列存储方式 D、索引存储方式3、已知，L是一个不带头结点的单链表，p指向其中的一个结点，选择合适的语句实现在p结点的后面插入s结点的操作（ B ）。A、p->next=s ; s->next=p->next ; B、s->next=p->n

2、ext ; p->next=s ;C、p->next=s ; s->next=p ; D、s->next=p ; p->next=s ;4、单链表中各结点之间的地址（ C D ）。A、必须连续 B、部分地址必须连续C、不一定连续 D、连续与否都可以5、在一个长度为n的顺序表中向第i个元素（0<i<=n+1）之前插入一个新元素时，需向后移动（ B ）个元素。A、n-i B、n-i+1 C、n-i-1 D、i2.2填空题1、顺序存储的长度为n的线性表，在任何位置上插入和删除操作的时间复杂度基本上都一样。插入一个元素大约移动表中的（ n/2 ）个元素，删除一

3、个元素时大约移动表中的（ (n-1)/2 ）个元素。2、在线性表的顺序存储方式中，元素之间的逻辑关系是通过（物理顺序）来体现的；在链式存储方式，元素之间的逻辑关系是通过（指针）体现的。3、对于一个长度为n的单链表，在已知的p结点后面插入一个新结点的时间复杂度为（o(1)），在p结点之前插入一个新结点的时间复杂度为（o(n)），在给定值为e的结点之后插入一个新结点的时间复杂度为（o(n)）。4、在双向链表中，每个结点包含两个指针域，一个指向（前驱）结点，另一个指向（后继）结点。5、对于循环链表来讲，逐个访问各个结点的结束判断条件是（设P为指向结点的指针，L为链表的头指针，则p->next=

4、 =L）。2.3读下面的程序段，画出执行过程的示意图及所完成的功能。1、 # define N 6void main ( ) ListSq L ; int A N ;int i , elem ;InitList(L); /初始化函数for ( int j=0; j<N; j+)scanf("%d",&A j ) ; for ( int m=0; m<N; m+) InsertList ( L , m ,Am) ; PrintList( L ) ; / 输出函数 1题示意图 2题示意图功能：先初始化一个顺序表，然后根据数组A中元素的顺序创建顺序表，并输出顺

5、序表的全部元素。2、 Lnode *CreateList( ) Lnode *L,*S; int x,y; L=malloc(sizeof(Lnode); L->data=x;s=malloc(sizeof(Lnode);s->data=y; L->next=s; s->next=NULL;return L;功能：创建一个两个结点的不带头结点的单链表，两个结点的值分别为X和Y，L为单链表的头指针。2.4 算法题1、 编写在两种存储方式下，删除线性表中多余的值相同元素的算法。解：顺序存储方式下：void del(ListSq &L) int i=0; while

6、(i<L.len-1) int j=i+1; while (j<L.len)if (L.ei= =L.ej) for (int k=j+1;k<L.len;k+) L.ek-1=L.ek; L.len-;else j+; i+;链式存储方式下：void del(Lnode *L) Lnode *p=L->next; while (p->next!=NULL) Lnode *q=p->next; Lnode *r=p;while (q!=NULL)if (q->data= =p->data) r->next=q->next; free(

7、q); q=r->next; else r=q; q=q->next; p=p->next;2、已知，顺序表的元素类型为整型，编写将该顺序表分成两个顺序表的算法，一个存放所的奇数元素，另一个存放所的偶数元素。解：void fenSq(ListSq L, ListSq &La, ListSq &Lb ) int j=0,k=0; for (int i=0;i<L.len;i+) if (L.ei%2= =0) Lb.ej=L.ei; j+; else La.ek=L.ei; k+; La.len=k; Lb.len=j;3、编写一个统计单循环链表的结点个数

8、的算法。解：int count(Lnode *L) Lnode *p=L->next; int n=0; while(p!=L) n+; p=p->next; return n;4、编写删除有序单链表中元素值大于min并且小于max的全部元素的算法。如果给定的表是无序的，如何改写上面的算法。解：void del4(Lnode *L,Elemtype min , Elemtype max ) Lnode *q,*s,*p ; p=L->next; q=L; while (p!=NULL&&p->date<=min) q=p; p=p->next

9、; if (p!=NULL)/表示存在大于min的结点，最后一个小于等于min的结点为q结点 while (p!=NULL&&p->date<max) p=p->next; if (p!=NULL)/ 表示存在大于等于max的结点，既p结点 while (q->next!=p) /删除q的后继结点到p的前驱结点为止的所有结点 s=q->next; q->next=s->next; free(s); else s=q->next; q->next=NULL;/q以后的结点全部要删除 while (s!=NULL) p=s-&g

10、t;next; free(s); s=p; 5、用顺序表来求集合的并集、交集和差集，也可以用链表来实现以上操作。（作为上机实践题目）# include < stdio.h >typedef int Elemtype ; # define maxlen 100 # define N 30struct ListSqElemtype e maxlen ; int len ; ;/顺序表的创建算法void Create_Sq( ListSq &L , Elemtype A , int n ) int i ;for ( i=0 ; i<n ; i+ )L.ei =Ai; L.l

11、en=n ; /顺序表的输出算法void PrintList( ListSq L ) printf("当前集合为:n");for ( int i=0; i<L.len; i+)printf("%dt" , L.e i ) ; printf ( "n" ) ;void bingji(ListSq L1,ListSq L2,ListSq &L3)for(int k=0;k<L1.len;k+)L3.ek=L1.ek;L3.len=L1.len;for (int i=0;i<L2.len;i+)int j=0;wh

12、ile(j<L1.len)&&(L2.ei!=L1.ej) j+;if (j>=L1.len)L3.eL3.len=L2.ei; L3.len+;void jiaoji(ListSq L1,ListSq L2,ListSq &L3)int k=0;for(int i=0;i<L1.len;i+)int j=0;while(j<L2.len)&&(L1.ei!=L2.ej) j+;if(j<L2.len) L3.ek+=L1.ei;L3.len=k;void chaji(ListSq L1,ListSq L2,ListSq &

13、amp;L3)int k=0;for(int i=0;i<L1.len;i+)int j=0;while(j<L2.len)&&(L1.ei!=L2.ej) j+;if(j>=L2.len) L3.ek+=L1.ei;for(int m=0;m<L2.len;m+)int n=0;while(n<L1.len)&&(L2.em!=L1.en) n+;if(n>=L1.len) L3.ek+=L2.em;L3.len=k;/主函数void main ( ) ListSq L1,L2,L3 ; L3.len=0;int A N ;

14、int m,n,c;printf("请输入线性表L1的元素个数:n");scanf("%d",&m);printf("请输入线性表L1的元素:n");for ( int j=0; j<m; j+)scanf("%d",&A j ) ; Create_Sq( L1 , A , m );PrintList( L1 ) ;printf("请输入线性表L2的元素个数:n");scanf("%d",&n);printf("请输入线性表L2的元素:

15、n");for ( int w=0; w<n; w+)scanf("%d",&A w ) ; Create_Sq( L2 , A , n );PrintList( L2 ) ;while(1)printf("请按提示进行输入：n");printf("实现两个集合的并集，请输入1：n"); printf("实现两个集合的交集，请输入2：n");printf("实现两个集合的差集，请输入3：n");printf("退出，请输入4：n");scanf(&qu

16、ot;%d",&c);switch(c)case 1: bingji(L1,L2,L3); PrintList( L3 ) ;break;case 2: jiaoji(L1,L2,L3); PrintList( L3 ) ;break;case 3: chaji(L1,L2,L3); PrintList( L3 );break; case 4:return;default: printf("输入有误！n");6、用循环单链表来实现约瑟夫问题。（作为上机实践题目）#include <stdio.h>#include <malloc.h>

17、;typedef struct Lnode int data ; Lnode *next ; *Link; void CreateList( Link &L , int n )/建立一个n个结点的循环单链表 int i ; Lnode *p,*s; s= ( Lnode * ) malloc ( sizeof ( Lnode ) ;s->data = 1 ;L=p=s;for ( i=2 ; i<=n ; i+) s= ( Lnode * ) malloc ( sizeof ( Lnode ) ;s->data = i ; p->next = s ; p=s ;

18、 p->next=L;void DeleteList( Link &L , Lnode * p, Lnode *q)/从循环单链表中删除结点pq->next=p->next ; / 修改结点的指针域free (p) ; / 释放p结点所占存储空间void josephus(Link &L,int s , int m ) Lnode *p,*q;p=L;for (int i=1;i<=s-1;i+) p=p->next;q=p->next;while(q->next!=p) q=q->next;while(p->next!=p

19、) for (int j=1;j<m;j+) q=p;p=p->next; printf("%d,",p->data);DeleteList( L , p , q);p=q->next;printf("%d ",p->data);printf("n");void main() Link L=NULL;int m,n,s;printf("请输入围圈人数、报数的开始位置和报数的上限n");scanf("%d,%d,%d",&n,&s,&m);if

20、 (m>1000)|(n>1000) printf("输入值m或n不合法！n");elseif (s>n) printf("输入值s和n不合法！n");else CreateList( L,n );printf("n");josephus( L, s , m );7、某百货公司对仓库中的库存电视进行管理时，按其价格从低到高的次序构成一个循环单链表来保存信息，每个结点包含价格、数量和指针三个域。现新到m台价格为h的电视机，编写修改原信息链表的算法。（作为上机实践题目） # include < malloc.h &

21、gt;# include < stdio.h > struct Elemtypefloat jiage;int shuliang;struct LnodeElemtype data; struct Lnode * next ; ; /单链表的后插入创建算法void Rcreate( Lnode *L , Elemtype A , int n ) int i ; Lnode *p,*s;p=L;for ( i=0 ; i<n ; i+) s= ( Lnode * ) malloc ( sizeof ( Lnode ) ;s->data = Ai; s->next=p

22、->next; p->next=s ; p=s ; /单链表的输出算法void printList( Lnode *L ) Lnode *p ;if(L->next=L)printf("单链表为空！n");elsep=L->next;printf("当前仓库中库存的电视相关信息为:n");printf("价格tt数量n");while ( p->next!=L) printf ("%ft" , p->data.jiage) ;printf ("%dn" , p->data.shuliang) ;p=p->next;printf ("%ft" , p->data.jiage) ;printf ("%dn" , p->data.shuliang) ;void Insert( Lnode *L , Elemtype elem)Lnode *s;s=( Lnode * ) malloc (sizeof (Lnode) ; s->data=elem; if(L->n