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

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

习 题

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->next ; 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、i

2.2填空题

1、顺序存储的长度为n的线性表，在任何位置上插入和删除操作的时间复杂度基本上都一样。插入一个元素大约移动表中的（ n/2 ）个元素，删除一个元素时大约移动表中的（ (n-1)/2 ）个元素。

2、在线性表的顺序存储方式中，元素之间的逻辑关系是通过（物理顺序）来体现的；在链式存储方式，元素之间的逻辑关系是通过（指针）体现的。

3、对于一个长度为n的单链表，在已知的p结点后面插入一个新结点的时间复杂度为（o(1)），在p结点之前插入一个新结点的时间复杂度为（o(n)），在给定值为e的结点之后插入一个新结点的时间复杂度为（o(n)）。

4、在双向链表中，每个结点包含两个指针域，一个指向（前驱）结点，另一个指向（后继）结点。

5、对于循环链表来讲，逐个访问各个结点的结束判断条件是（设P为指向结点的指针，L为链表的头指针，则p->next= =L）。

2.3读下面的程序段，画出执行过程的示意图及所完成的功能。

1、 # define N 6

void 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 ,A[m]) ;

PrintList( L ) ; // 输出函数}

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

L.e[0]

L.e[1]

L.e[2]

L.e[3]

L.e[4]

L.e[5] L

1题示意图 2题示意图 功能：先初始化一个顺序表，然后根据数组A中元素的顺序创建顺序表，并输出顺序表的全部元素。

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 (i<L.len-1)

{ int j=i+1;

while (j<L.len)

if (L.e[i]= =L.e[j])

{ for (int k=j+1;k<L.len;k++)

L.e[k-1]=L.e[k];

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)

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

{ r->next=q->next; free(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.e[i]%2= =0)

{ Lb.e[j]=L.e[i]; j++; }

else { La.e[k]=L.e[i]; k++; }

La.len=k;

Lb.len=j;

}

3、编写一个统计单循环链表的结点个数的算法。

解：

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; }

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->next; free(s); s=p; }}}

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

5、用顺序表来求集合的并集、交集和差集，也可以用链表来实现以上操作。（作为上机实践题目）

# include < stdio.h >

typedef int Elemtype ;

# define maxlen 100

# define N 30

struct ListSq

{

Elemtype e [ maxlen ] ;

int len ;

};

//顺序表的创建算法

void Create_Sq( ListSq &L , Elemtype A[ ] ,

{

int i ;

for ( i=0 ; i<n ; i++ )

L.e[i] =A[i];

L.len=n ;

}

//顺序表的输出算法

void PrintList( ListSq L )

{

printf("当前集合为:\n");

for ( int i=0; i<L.len; i++)

printf("%d\t" , L.e [ i ] ) ;

printf ( "\n" ) ;

}

void bingji(ListSq L1,ListSq L2,ListSq &L3)

{

for(int k=0;k<L1.len;k++)

L3.e[k]=L1.e[k];

L3.len=L1.len;

for (int i=0;i<L2.len;i++)

{int j=0;

while((j<L1.len)&&(L2.e[i]!=L1.e[j]))

j++;

if (j> …… 此处隐藏：2732字，全部文档内容请下载后查看。喜欢就下载吧 ……