线性表

}

#include "stackar.h"

#include "fatal.h"

#include

#define EmptyTOS ( -1 )

#define MinStackSize ( 5 )

struct StackRecord

{

int Capacity;

int TopOfStack;

ElementType *Array;

};

/* START: fig3_48.txt */

int

IsEmpty( Stack S )

{

return S->TopOfStack == EmptyTOS;

}

/* END */

int

IsFull( Stack S )

{

return S->TopOfStack == S->Capacity - 1;

}

/* START: fig3_46.txt */

CreateStack( int MaxElements )

{

Stack S;

/* 1*/ if( MaxElements < MinStackSize )

/* 2*/ Error( "Stack size is too small" );

/* 3*/ S = malloc( sizeof( struct StackRecord ) );

/* 4*/ if( S == NULL )

/* 5*/ FatalError( "Out of space!!!" );

/* 6*/ S->Array = malloc( sizeof( ElementType ) * MaxElements ); /* 7*/ if( S->Array == NULL )

/* 8*/ FatalError( "Out of space!!!" );

/* 9*/ S->Capacity = MaxElements;

/*10*/ MakeEmpty( S );

/*11*/ return S;

}

/* END */

/* START: fig3_49.txt */

void

MakeEmpty( Stack S )

{

S->TopOfStack = EmptyTOS;

}

/* END */

/* START: fig3_47.txt */

void

DisposeStack( Stack S )

{

if( S != NULL )

{

free( S->Array );

free( S );

}

}

/* END */

/* START: fig3_50.txt */

void

Push( ElementType X, Stack S )

{

if( IsFull( S ) )

Error( "Full stack" );

else

S->Array[ ++S->TopOfStack ] = X;

}

/* END */

ElementType

Top( Stack S )

{

if( !IsEmpty( S ) )

return S->Array[ S->TopOfStack ];

Error( "Empty stack" );

return 0; /* Return value used to avoid warning */ }

/* END */

/* START: fig3_52.txt */

void

Pop( Stack S )

{

if( IsEmpty( S ) )

Error( "Empty stack" );

else

S->TopOfStack--;

}

/* END */

/* START: fig3_53.txt */

ElementType

TopAndPop( Stack S )

{

if( !IsEmpty( S ) )

return S->Array[ S->TopOfStack-- ];

Error( "Empty stack" );

return 0; /* Return value used to avoid warning */ }

/* END */

void convert(Stack S,int n,int p)

{

int e;

if(p<=2&&p>=16)

printf("Error!");

else

while(n)

{

Push(n%p,S);

n=n/p;

}

while(!IsEmpty(S))

{

e=TopAndPop(S);

if(e>9)

printf("%c",e+55);

printf("%d",e);

}

}

void main()

{

Stack S;

int n,p;

S=CreateStack(10);

printf("请输入要转换的十进制数和转换的进制:\n");

scanf("%d%d",&n,&p);

printf("转换后的数:\n");

convert(S,n,p);

printf("\n");

}

回文@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ #include

#include"stackar.c"

#include"queue.c"

#include"string.h"

void Text(char str[])

{ int i,j,m,n,lenth;

Stack S;

Queue Q;

S=CreateStack(10);

Q=CreateQueue(10);

lenth=strlen(str);

if(lenth%2==0)

{

i=lenth/2;

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

Push(str[j],S);

for(j=i-1;j<=lenth;j++)

Enqueue(str[j],Q);

}

else

{ i=lenth/2;

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

Push(str[j],S);

for(j=i;j<=lenth;j++)

}

for(j=i;j>=0;j--)

{

m=TopAndPop(S);

n=FrontAndDequeue(Q);

if(m!=n)

break;

}

if(j<0)

printf("是回文");

else

printf("不是回文");

}

main()

{

char str[20];

gets(str);

Text(str);

}

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ # include.

# include

# include

SearchTree CreateTree(SearchTree t)

{

char c;

scanf("%c",&c);

if(c=='#')

t=NULL;

else

{

t=(SearchTree)malloc(sizeof(struct TreeNode));

t->Element=c;

t->Left=CreateTree(t->Left);

t->Right=CreateTree(t->Right);

}

return t;

}

void Preorder(SearchTree t)

{

if(t)

{

printf("%3c",t->Element);

Preorder(t->Left);

Preorder(t->Right);

}

void Inorder(SearchTree t)

{

if(t)

{

Inorder(t->Left);

printf("%3c",t->Element);

Inorder(t->Right);

}

}

void Postorder(SearchTree t)

{

if(t)

{

Postorder(t->Left);

Postorder(t->Right);

printf("%3c",t->Element);

}

}

int NodeNumber(SearchTree T)

{

if (T==NULL) return 0;

else return 1 + NodeNumber (T->Left ) + NodeNumber ( T->Right);

}

int LeafNumber(SearchTree T)

{

if (T)

{

if((T->Left==NULL) && (T->Right==NULL) )

return 1;

else return LeafNumber(T->Left)+LeafNumber(T->Right);

}

else return 0;

}

int FullNodeNumber(SearchTree T)

{

if (T)

{

if((T->Left!=NULL) && (T->Right!=NULL) )

return 1+FullNodeNumber(T->Left)+FullNodeNumber(T->Right);

else return FullNodeNumber(T->Left)+FullNodeNumber(T->Right);

}

else return 0;

}

int FindElement(SearchTree t,ElementType x)

if(t==NULL)

return 0;

if(t->Element==x)

return 1;

else

{

return(FindElement(t->Left,x));

return(FindElement(t->Right,x));

}

}

main()

{

SearchTree t;

int a;

char ch;

t=CreateTree(t);

printf("前序遍历结果：\n");

Preorder(t);

printf("\n");

printf("中序遍历结果：\n");

Inorder(t);

printf("\n");

printf("后序遍历结果：\n");

Postorder(t);

printf("\n");

printf("树中的结点总数为：%d\n",NodeNumber(t));

printf("树中的叶子结点个数为：%d\n",LeafNumber(t));

printf("树中的满结点个数为：%d\n",FullNodeNumber(t));

printf("输入要查找的结点:");

scanf(" %c",&ch);

a=FindElement(t,ch);

if(a=0)

printf("false");

else

printf("true");

printf("\n");

return 0;

}

#include

#include

#include "fatal.h"

typedef struct StudentInfo ElementType;

struct StudentInfo

{ char ID[10];

char * name;

double score;

}StuInfo1[12]=

{

{"0800301105", "JACK", 95},

{"0800201505", "LUN", 85},

{"0400820115", "MARY", 75.5},

{"0400850122", "KATE", 78.9},

{"0500201011", "LILI", 88},

{"0800401105", "JACK", 96},

{"0600830105", "JAN", 98.4},

{"0952520012", "SAM", 75},

{"9721000045", "OSCAR", 64},

{"0700301105", "JACK", 97},

{"0458003312", "ZOE", 68.9},

{"0400830211", "BOBI", 87.6}

};

void

Swap( ElementType *Lhs, ElementType *Rhs )

{

ElementType Tmp = *Lhs;

*Lhs = *Rhs;

*Rhs = Tmp;

}

void

InsertionSort( struct StudentInfo A[], int N )

{

int j, P;

struct StudentInfo Tmp;

for( P = 1; P < N; P++ )

{

Tmp= A[ P ];

for( j = P; j > 0 && strcmp(A[ j - 1 ].name,https://www.wendangku.net/doc/556433132.html,)>0; j-- ) A[ j ] = A[ j - 1 ];

A[ j ] = Tmp;

}

}

void

InsertionSort2( struct StudentInfo A[], int N )

{

int j, P;

struct StudentInfo Tmp;

for( P = 1; P < N; P++ )

{

Tmp= A[ P ];

for( j = P; j > 0 && strcmp(A[ j - 1 ].ID,Tmp.ID)>0; j-- )

A[ j ] = A[ j - 1 ];

A[ j ] = Tmp;

}

}

void

Merge( struct StudentInfo A[ ],struct StudentInfo TmpArray[ ],

int Lpos, int Rpos, int RightEnd )

{

int i, LeftEnd, NumElements, TmpPos;

LeftEnd = Rpos - 1;

NumElements = RightEnd - Lpos + 1;

while( Lpos <= LeftEnd && Rpos <= RightEnd )

if(strcmp(A[Lpos].name,A[Rpos].name)<=0)

TmpArray[ TmpPos++ ] = A[ Lpos++ ];

else

TmpArray[ TmpPos++ ] = A[ Rpos++ ];

while( Lpos <= LeftEnd )

TmpArray[ TmpPos++ ] = A[ Lpos++ ];

while( Rpos <= RightEnd )

TmpArray[ TmpPos++ ] = A[ Rpos++ ];

for( i = 0; i < NumElements; i++, RightEnd-- )

A[ RightEnd ] = TmpArray[ RightEnd ];

}

void

MSort(struct StudentInfo A[ ],struct StudentInfo TmpArray[ ],

int Left, int Right )

{

int Center;

if( Left < Right )

{

Center = ( Left + Right ) / 2;

MSort( A, TmpArray, Left, Center );

MSort( A, TmpArray, Center + 1, Right );

Merge( A, TmpArray, Left, Center + 1, Right );

}

}

void

Mergesort(struct StudentInfo A[ ], int N)

{

struct StudentInfo *TmpArray;

TmpArray = malloc(N * sizeof(struct StudentInfo));

if( TmpArray != NULL )

{

MSort( A, TmpArray, 0, N - 1 );

free( TmpArray );

}

else

FatalError( "No space for tmp array!!!" );

}

Median3(struct StudentInfo A[ ], int Left, int Right )

{

int Center = ( Left + Right ) / 2;

if( strcmp(A[Left].name,A[Center].name)>0 )

Swap( &A[ Left ], &A[ Center ] );

if( strcmp(A[Left].name,A[Right].name)>0 )

Swap( &A[ Left ], &A[ Right ] );

if( strcmp(A[Center].name,A[Right].name)>0 )

Swap( &A[ Center ], &A[ Right ] );

Swap( &A[ Center ], &A[ Right - 1 ] );

return A[ Right - 1 ];

}

#define Cutoff ( 3 )

void

Qsort( struct StudentInfo A[ ], int Left, int Right )

{

int i, j;

struct StudentInfo Pivot;

if( Left + Cutoff <= Right )

{

Pivot = Median3( A, Left, Right );

i = Left; j = Right - 1;

for( ; ; )

{

while( strcmp(A[++i].name,https://www.wendangku.net/doc/556433132.html,)<0 ){ }

while( strcmp(A[--j].name,https://www.wendangku.net/doc/556433132.html,)>0 ){ }

if( i < j )

Swap( &A[ i ], &A[ j ] );

else

break;

}

Swap( &A[ i ], &A[ Right - 1 ] );

Qsort( A, Left, i - 1 );

Qsort( A, i + 1, Right );

}

else

InsertionSort( A + Left, Right - Left + 1 );

}

i = Left + 1; j = Right - 2;

for( ; ; )

{

while( strcmp(A[i].name,Pivot.namme<0) ) i++;

while( strcmp(A[j].name,Pivot.namme>0) ) j--;

if( i < j )

Swap( &A[ i ], &A[ j ] );

else

break;

}

#endif

void

Quicksort( struct StudentInfo A[ ], int N )

{

Qsort( A, 0, N - 1 );

}

main( )

{

int i;

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

printf("%s\n",StuInfo1[i].ID);

InsertionSort2( StuInfo1, 12 );

printf("/////////////////\n");

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

printf("%s\n",StuInfo1[i].ID);

printf("/////////////////\n");

Mergesort(StuInfo1,12);

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

printf("%s\n",StuInfo1[i].name);

printf("/////////////////\n");

Quicksort(StuInfo1,12);

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

printf("%s\n",StuInfo1[i].name);

return 0;

}

#include "string.h"

#include

#include "hashquad.c"

#include "hashquad.h"

void main()

{

int i,x,n;

char s[10];

HashTable H;

char * MyBirds[13] = { "robin", "sparrow", "hawk", "eagle", "seagull", "bluejay", "owl", "cardinal", "Jakana", "Moa", "Egret", "Penguin", "hawk" };

printf(" \n");

printf("原来的MyBirds：\n\n");

printf(" 字符串位置\n");

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

printf("%9s: %2d\n",MyBirds[i],i+1);

H=InitializeTable( 29 );

printf(" \n");

printf("生成散列表：\n\n");

printf(" 字符串散列值位置\n");

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

Insert(MyBirds[i] , H );

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

{

if(H->TheCells[i].Info!=Empty)

printf("%9s: %2d %d\n",

H->TheCells[i].Element,

x=Hash(H->TheCells[i].Element,29),

n=Find( H->TheCells[i].Element,H));

}

printf("请输入要查找的值：");

scanf("%s",s);

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

{

if(strcmp(H->TheCells[i].Element,s)==0)

break;

}

if(i<29)

printf("查找成功，位置在：%d\n ",Find( s,H));

else printf("查找失败\n");

#include

#include

#include "fatal.h"

typedef struct StudentInfo ElementType;

struct StudentInfo

{ char ID[10];

char * name;

double score;

}StuInfo1[12]=

{

{"0800301105", "JACK", 95},

{"0800201505", "LUN", 85},

{"0400820115", "MARY", 75.5},

{"0400850122", "KATE", 78.9},

{"0500201011", "LILI", 88},

{"0800401105", "JACK", 96},

{"0600830105", "JAN", 98.4},

{"0952520012", "SAM", 75},

{"9721000045", "OSCAR", 64},

{"0700301105", "JACK", 97},

{"0458003312", "ZOE", 68.9},

{"0400830211", "BOBI", 87.6}

};

void

Swap( ElementType *Lhs, ElementType *Rhs )

{

ElementType Tmp = *Lhs;

*Lhs = *Rhs;

*Rhs = Tmp;

}

void

InsertionSort( struct StudentInfo A[], int N )

{

int j, P;

struct StudentInfo Tmp;

for( P = 1; P < N; P++ )

{

Tmp= A[ P ];

for( j = P; j > 0 &&(A[j-1].score

A[ j ] = A[ j - 1 ];

A[ j ] = Tmp;

}

}

void

{

int j, P;

struct StudentInfo Tmp;

for( P = 1; P < N; P++ )

{

Tmp= A[ P ];

for( j = P; j > 0 && strcmp(A[ j - 1 ].ID,Tmp.ID)>0; j-- )

A[ j ] = A[ j - 1 ];

A[ j ] = Tmp;

}

}

int BinarySearch(ElementType A[],char X[],int N)

{

int Low,Mid,High;

Low=0;

High=N-1;

while(Low<=High)

{

Mid=(Low+High)/2;

if(strcmp(A[Mid].ID,X)==0)

return Mid;

else if(strcmp(A[Mid].ID,X)>0)

High=Mid-1;

else

Low=Mid+1;

}

return -1;

}

int BinarySearch1(ElementType A[],double Y,int N)

{

int Low,Mid,High;

Low=0;

High=N-1;

while(Low<=High)

{

Mid=(Low+High)/2;

if(A[Mid].score>Y)

Low=Mid+1;

else

if(A[Mid].score<0)

High=Mid-1;

else

return Mid;

}

return -1;

数据结构复习提纲(整理)

复习提纲 第一章数据结构概述 基本概念与术语（P3） 1．数据结构是一门研究非数值计算程序设计问题中计算机的操作对象以及他们之间的关系和操作的学科. 2．数据是用来描述现实世界的数字,字符,图像,声音,以及能够输入到计算机中并能被计算机识别的符号的集合 2．数据元素是数据的基本单位 3．数据对象相同性质的数据元素的集合 4．数据结构包括三方面内容:数据的逻辑结构.数据的存储结构.数据的操作. （1）数据的逻辑结构指数据元素之间固有的逻辑关系. （2）数据的存储结构指数据元素及其关系在计算机内的表示 ( 3 ) 数据的操作指在数据逻辑结构上定义的操作算法,如插入,删除等. 5.时间复杂度分析 -------------------------------------------------------------------------------------------------------------------- 1、名词解释：数据结构、二元组 2、根据数据元素之间关系的不同，数据的逻辑结构可以分为 集合、线性结构、树形结构和图状结构四种类型。 3、常见的数据存储结构一般有四种类型，它们分别是___顺序存储结构_____、___链式存储结构_____、___索引存储结构_____和___散列存储结构_____。 4、以下程序段的时间复杂度为___O(N2)_____。 int i,j,x; for(i=0;i=0)个具有相同性质的数据元素a1,a2,a3……,an组成的有穷序列 //顺序表结构 #define MAXSIZE 100 typedef int DataType; Typedef struct{ DataType items[MAXSIZE]; Int length; }Sqlist,*LinkList; //初始化链表 void InitList(LinkList *L){ (*L)=(LinkList)malloc(sizeof(LNode)); if(!L){ cout<<”初始化失败!”; return;

线性表练习题(答案)

第2章线性表 一选择题 下列程序段的时间复杂度为（ C ）。 for( int i=1;i<=n;i++) for( int j=1;j<= m; j++) A[i][j] = i*j ; A. O(m2) B. O(n2) C. O(m*n) D. (m+n) 下面关于线性表的叙述中，错误的是哪一个？（B ） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 线性表是具有n个（ C ）的有限序列（n>0）。 A．表元素B．字符C．数据元素D．数据项 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。 A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。 A．单链表B．仅有头指针的单循环链表 C．双链表D．仅有尾指针的单循环链表 设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( D )最节省时间。A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ D ）存储方式最节省运算时间。 A．单链表B．双链表C．单循环链表D．带头结点的双循环链表 链表不具有的特点是（ B ） A．插入、删除不需要移动元素B．可随机访问任一元素 C．不必事先估计存储空间D．所需空间与线性长度成正比 下面的叙述不正确的是（B,C ） A．线性表在链式存储时，查找第i个元素的时间同i的值成正比 B. 线性表在链式存储时，查找第i个元素的时间同i的值无关 C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比 D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ C ）(1<=i<=n+1)。 A. O(0) B. O(1) C. O(n) D. O(n2) 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（C ）。 A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) 线性表（a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ C ）A．O（i）B．O（1）C．O（n）D．O（i-1） 循环链表H的尾结点P的特点是（A ）。 A．P->next=H B．P->next= H->next C．P=H D．P=H->next 完成在双循环链表结点p之后插入s的操作是（D ）；

有关线性表的题目及答案

第2章线性表 一选择题 1．下述哪一条是顺序存储结构的优点？（）【北方交通大学 2001 一、4（2分）】A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示 2．下面关于线性表的叙述中，错误的是哪一个？（）【北方交通大学 2001 一、14（2分）】 A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 3．线性表是具有n个（）的有限序列（n>0）。【清华大学 1998 一、4（2分）】A．表元素 B．字符 C．数据元素 D．数据项 E．信息项 4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。【哈尔滨工业大学 2001 二、1（2分）】A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。【南开大学 2000 一、3】 A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表 6．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。 A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表 【合肥工业大学 2000 一、1（2分）】 7．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（）存储方式最节省运算时间。【北京理工大学 2000 一、1（2分）】A．单链表 B．双链表 C．单循环链表 D．带头结点的双循环链表 8. 静态链表中指针表示的是（）. 【北京理工大学 2001 六、2（2分）】 A．内存地址 B．数组下标 C．下一元素地址 D．左、右孩子地址 9. 链表不具有的特点是（）【福州大学 1998 一、8 (2分)】 A．插入、删除不需要移动元素 B．可随机访问任一元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比 10. 下面的叙述不正确的是（）【南京理工大学 1996 一、10（2分）】 A．线性表在链式存储时，查找第i个元素的时间同i的值成正比 B. 线性表在链式存储时，查找第i个元素的时间同i的值无关 C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比 D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关 11. 线性表的表元存储方式有(（1）)和链接两种。试指出下列各表中使用的是何种存储方式：表1是(（2）)存储方式；表2是(（3）)存储方式；表3是(（4）)存储方式；表4是(（5）)存储方式。表左的s指向起始表元。

线性表的基本操作讲解

实验二线性表的基本操作 一、实验目的 1．掌握用C++/C语言调试程序的基本方法。 2．掌握线性表的顺序存储和链式存储的基本运算，如插入、删除等。 二、实验要求 1．C++/C完成算法设计和程序设计并上机调试通过。 2．撰写实验报告，提供实验结果和数据。 3．分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要给出算法设计小结和心得。 三、实验内容： 1. 分析并运行以下各子程序的主要功能。 程序1：顺序存储的线性表和运算 #include #define MAXSIZE 100 int list[MAXSIZE]; int n; /*insert in a seqlist*/ int sq_insert(int list[], int *p_n, int i, int x) {int j; if (i<0 || i>*p_n) return(1); if (*p_n==MAXSIZE) return(2); for (j=*p_n+1; j>i; j--) list[j]=list[j-1]; list[i]=x; (*p_n)++; return(0); } /*delete in a seq list*/ int sq_delete(int list[], int *p_n, int i) {int j; if (i<0 || i>=*p_n) return(1); for (j = i+1; j<=*p_n; j++) list[j-1] = list[j]; (*p_n)--; return(0); } void main() {int i,x,temp; printf("please input the number for n\n"); printf("n="); scanf("%d",&n); for (i=0; i<=n; i++) {printf("list[%d]=",i); scanf("%d",&list[i]);}

作业-概述和线性表

第1章数据结构概述 一、选择题 1．在数据结构中，从逻辑上可以把数据结构分为( )。 A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部结构 2．线性表的顺序存储结构是一种( )的存储结构。 A．随机存取B．顺序存取C．索引存取D．Hash存取 3．计算机算法指的是( (1) )，它必须具备输入、输出和( (2) )等五个特征。 (1) A．计算方法B．排序方法C．解决某一问题的有限运算序列D．调度方法 (2) A．可行性、可移植性和可扩充性B．可行性、确定性和有穷性C．确定性，有穷性和稳定性D．易读性、稳定性和安全性 4．线性表若采用链表存储结构，要求内存中可用存储单元的地址( )。 A．必须是连续的B．部分必须是连续的C．一定是不连续的D．连续不连续都可以 5．根据数据元素之间关系的不同特性，以下四类基本的逻辑结构反映了四类基本的数据组织形式，其中解释错误的是( )。 A．集合中任何两个结点之间都有逻辑关系但组织形式松散B．线性结构中结点按逻辑关系依次排列形成一条“锁链”C．树形结构具有分支、层次特性，其形态有点像自然界中的树D．图状结构中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接 二、判断题 ╳1．数据元素是数据的最小单位。 √2．数据结构是带有结构的数据元素的集合。 √3．数据结构、数据元素、数据项在计算机中的映像分别称为存储结构、结点、数据域。 ╳4．数据项是数据的基本单位。 √5．数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的。 √6．数据的物理结构是数据在计算机中实际的存储形式。 ╳7．算法和程序没有区别，所以在数据结构中二者是通用的。 ╳8．顺序存储结构属于静态结构，链式存储结构属于动态结构。 三、填空题 1．所谓数据的逻辑结构指的是数据元素之间的____逻辑关系_____。 2，数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容___数据的逻辑结构、数据的存储结构、对数据施加的操作___。 3．数据的逻辑结构包括_____集合结构___、_____线性结构___、____树型结构_____和__图状结构_____四种类型。4．在线性结构中，开始结点__没有_前驱结点，其余每个结点有且只有__一个_个前驱结点。 5．在树形结构中，根结点只有___一个___，其余每个结点有且只有___一个___前驱结点；叶结点没有___后继__结点，其余每个结点的后继结点可以有__任意个__· 6．在图形结构中，每个结点的前驱结点和后继结点可以有___任意个___。 7．算法的五个重要特性是__可行性___、___确定性___、___有穷性___、___输入__、___输出__。 8．下列程序段的时间复杂度是__O（n）___。 for (i=1；i<=n；i++) A[i，i]=0； 10．存储结构是逻辑结构的___物理__实现。 11．从数据结构的观点看，通常所说的“数据”应分成三个不同的层次，即__数据__、__数据元素_和__数据项___。12．一个算法的时空性能是指该算法的_时间复杂度___和___空间复杂度_，前者是算法包含的__计算量__，后者是算法需要的___存储量__。 13．数据结构的基本任务是数据结构的__设计__和__实现__。 四、应用题 1．分析下列程序段的时间复杂度。 …… i=1； WHILE (i<=n) i=i*2； …… 答：O(log2n) 2．叙述算法的定义及其重要特性。 答：算法是对特定问题求解步骤的一种描述，是指令的有限序列。其中每一条指令表示一个或多个操作。算法应该具有下列特性：可行性、确定性、有穷性、输入和输出。 3．简述下列术语：数据，数据元素，数据结构，数据对象。 答：数据是信息的载体，是描述客观事物的数、字符，以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据元素是数据的基本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等。数据结构是指相互之间存在着一种或多种关系的数据元素的集合。数据对象是性质相同的数据元素的集合。 4．逻辑结构与存储结构是什么关系？

【数据结构】线性表的基本操作

【数据结构】线性表的基本操作 #include //自定义int类型的ElemType元素 typedef int ElemType; //自定义int类型的Status返回状态 typedef int Status; struct List{ ElemType *list1; //指向线性表的第一个节点 int length; //线性表的实际长度 int listSize; //线性表的最大长度324 }; //***************************************基本操作开始*************************************// //附加1：给线性表增加空间 Status AgainMalloc(struct List *L1) { ElemType *p = (ElemType *)realloc(L1->list1,(L1->listSize + 1)*sizeof(ElemType)); if(!p) { printf("存储空间分配失败！"); exit(1); } L1->list1 = p; /*使list1指向新线性表空间*/ L1->listSize=L1->listSize + 1; /*把线性空间大小修改为新的长度*/ } //附加2：遍历线性表元素 Status Traverse(struct List *L1) { int i; for(i = 0;i < L1->length;i++){ printf("%d ",L1->list1[i]); } } //1.创建线性表,给定长度 Status InitList(struct List *L1,int ms){ if(ms<0){ printf("初始化线性表的长度不能小于0\n"); exit(1); } L1->length = 0;

线性表答案

一选择题 1．下述哪一条是顺序存储结构的优点（ A ） A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示 2．下面关于线性表的叙述中，错误的是哪一个（ B ） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 3．线性表是具有n个（ C ）的有限序列（n>0）。 A．表元素 B．字符 C．数据元素 D．数据 项 E．信息项 4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。 A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表 5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。 A．单链表 B．仅有头指针的单循环链表 C．双链表D．仅有尾指针的单循环链表 6．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( D )最节省时间。 A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表 7．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ D ）存储方式最节省运算时间。 A．单链表 B．双链表 C．单循环链表 D．带头结点的双循环链表 8. 静态链表中指针表示的是（ BC ）. A．内存地址 B．数组下标 C．下一元素地址D．左、右孩子地址 9. 链表不具有的特点是（ C ） A．插入、删除不需要移动元素 B．可随机访问任一元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比

线性表例题

例1说明在线性表的链式存储结构中，头指针与头结点之间的根本区别；头结点与首元结点的关系。 答：在线性表的链式存储结构中，头指针是指指向链表的指针，若链表有头指针则是链表的头结点的指针，头指针具有标识作用，故常用头指针冠以链表的名字。头结点是为了操作的统一、方便而设立的，放在第一数据元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用作监视哨，等等），有了头结点后，对在第一数据元素结点前插入结点和删除第一结点，其操作与对其它结点的操作就统一了。而且无论链表是否为空，头指针均不为空。首元结点也就是第一数据元素结点，它是头结点后边的第一个结点。 例2 为什么在单循环链表中设置尾指针比设置头指针更好？ 答：尾指针是指指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一个带头结点的单循环链表，其尾指针是rear，则开始结点和终端结点分别为指针rear所指结点的后继结点的后继结点和指针rear所指结点（利用C语言分别描述为rear->next->next和rear，利用标准Pascal语言分别描述为rear↑.next↑.next和rear），查找时间均为O(1)。若用头指针来表示该链表，则查找时间均为O(n)。 例3请分析含有n个结点的顺序表，在进行插入和删除操作时的时间复杂度，并对计算的结果进行分析，由此可得到线性表的适用范围的什么结论。 解：值得注意的是，插入操作是指在某个元素前面或后面插入，是针对位置的，因此可插入的位置为n+1个，而删除操作是删除线性表中某个位置上的元素，是针对元素的，因此可删除的元素为n个。 设p i为在第i个元素之前插入一个元素的概率，在等概率的条件下，其值为1/(n+1)。在第i个元素之前插入一个元素需要移动的元素的个数为：n-i+1。所以，在长度为n的线性表中插入一个元素所需要移动的元素次数的数学期望值（平均次数）为： E in=∑+ = + - 1 1 )1 ( n i i i n p=n/2 同理，设q i为删除第i个元素的概率，在等概率的条件下，其值为1/n。删除第i 个元素需要移动的元素的个数为：n-i。所以，在长度为n的线性表中删除一个元素所需要移动的元素次数的数学期望值（平均次数）为： E del=∑ =- n i i i n q 1 ) (=(n-1)/2 由于这两个操作的时间主要消耗在数据元素的移动上，所以插入算法和删除算法的时间复杂度均为：O(n)。 从上述分析可知，在顺序存储结构下，在线性表上插入或删除一个元素时需要平均移动线性表长度一半的元素个数，因此当n的值较大时，在顺序结构下，不宜对它频繁

数据结构与算法(线性表)练习题

三、写一个算法合并两个已排序的线性表。（用两种方法：数组表示的线性表（顺序表）和指针表示的线性表（链表）） 要求：1、定义线性表节点的结构，并定义节点的型和位置的型。 2、定义线性表的基本操作 3、在1，2的基础上，完成本题。 4、在main 函数中进行测试：先构建两个有序的线性表，然后合并这两个线性表。 四、已知一个单向链表，试给出复制该链表的算法。 要求：1、定义线性表的节点的结构以及节点的型和位置的型。 2、定义线性表的基本操作 3、在1，2的基础上，完成本题。 4、在main 函数中进行测试：先构建一个线性表，并定义一个空线性表，然后进行复制。 五、写出从一个带表头的单链表中删除其值等于给定值x 的结点的算法函数： int delete(LIST &L, int x);如果x 在该链表中，则删除对应结点，并返回其在链表中的位置（逻辑位置，第一个结点的逻辑位置为1），否则返回-1。 要求：1、定义线性表的节点的结构以及节点的型和位置的型。 2、定义线性表的基本操作 3、在1，2的基础上，完成本题。 4、在main 函数中进行测试：先构建一个线性表，然后调用函数删除值等于给定值的节点。 六、写出一个将两个静态链表（属于同一个存储池）合并的算法函数： void Merge(cursor M, cursor N); 合并的方法是将N 链表中的所有结点添加到M 链表的后面，并将N 链表的表头结点添加到空闲结点链表中。 要求：1、定义静态链表的结点的结构以及结点的型SPACE 以及位置（position ）和游标（cursor ）的型。 2、定义静态链表的基本操作：void Initialize(); 初始化，将所有存储池中的结点设置为空闲；cursor GetNode(); 从空闲链中获取一个结点；void FreeNode(cursor q); 将结点q 加入到空闲链； void Insert ( elementtype x, position p, cursor M ); 在链表M 中的位置为p 的元素后面添加一个值为x 的结点；void Delete (cursor M, position p ); 在链表M 中删除位置为p 的元素的后一个元素。 3、在1、2的基础上完成本题。 4、在main 函数中进行测试：先构建一个存储池，然后在该存储池中创建两个静态 表，最后将这两个静态表合并。 七、利用指针表示的线性表(链表)表示一个多项式，并实现两个多项式的相加和相乘运算。假设多项式形式为：11 11...)(e e m e m x a x a t a x A m m +++= -- 其中，系数a i ≠0，指数e i 满足e m >e m-1>…>e 2>e 1>=0。 要求：1、定义多项式每一项的结构。 2、定义两个多项式的相加和相乘运算函数。 3、在main 函数中，构建两个多项式，并测试相加和相乘运算。

线性表填空试题 数据结构

数据结构复习题：线性表 填空题 1、在线性结构中第一结点_____前驱结点，其余每个结点有且只有______个前驱结点；最后一个结点______后继结点。 2、对于顺序存储的线性表，当随机插入或删除一个元素时，约需平均移动表长______的元素。 3、对于长度为n的顺序表，插入或删除元素的时间复杂性为________；对于顺序栈或队列，插入或删除元素的时间复杂性为_________。 4、在线性表的顺序存储中，元素之间的逻辑关系是通过__________决定的；在线性表的链接存储中，元素之间的逻辑关系是通过____________决定的。 5、一个单链表中删除*p结点时，应执行如下操作: (1)q=p->next; (2)p->data=p->next->data; (3)p->next=__________; (4)free(q); 6、对于线性表的顺序存储，需要预先分配好存储空间，若分配太多则容易造成存储空间的__________，若分配太少又容易在算法中造成__________，因此适应于数据量变化不大的情况；对于线性表的链接存储(假定采用动态结点)，不需要__________存储空间，存储器中的整个__________都可供使用，分配和回收结点都非常方便，能够有效地利用存储空间，在算法中不必考虑__________的发生，因此适应数据量变化较大的情况。 7、从顺序表中删除第i个元素时，首先把第i个元素赋给__________带回，接着从_____________开始向后的所有元素均___________一个位置，最后使线性表的长度_____________。 8、向一个长度为n的顺序表中的第i个元素(0<=i<=n-1)之前插入一个元素时，需向后移动______个元素。 9、在一个长度为n的顺序表删除第i个元素(0<=i<=n-1)时，需向前移动______个元素。 10、在单链表中设置头结点的作用是___________。 11、在单链表中，要删除某一指定的结点，必须找到该结点的_______结点。 12、访问单链表中的结点，必须沿着________依次进行。 13、在双链表中，每个结点有两个指针域，一个指向________，另一个指向_________。 14、在______链表上，删除最后一个结点，其算法的时间复杂度为O(1)。 15、在一个单链表中的p所指结点之前插入一个s所指结点时，可执行如下操作。 (1)s->next=_________。 (2)p->next=s; (3)t=p->data; (4)p->data=_________。 (5)s-.data=_________。 16、在一个单链表中删除p所指结点时，应执行以下操作： q=p->next; p_data=p->next->data; p->next=______; free(q); 17、在一个单链表中p所指结点之后插入一个s所指结点时，应执行s->next=_______和p->next=________的操作。

线性表编程练习题

1、假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。输入: 1 2 5 6 8 3 4 7 9 10 输出: 10 9 8 7 6 5 4 3 2 1 测试数据 输入：7 9 10 11 8 12 13 14 输出：14 13 12 11 10 9 8 7 链表翻转 2.带头结点且头指针为ha和hb的两线性表A和B 分别表示两个集合。两表中的元素皆为递增有序。请写一算法求A和B的并集AUB。要求该并集中的元素仍保持递增有序。且要利用A和B的原有结点空间。 输入: 1 2 5 6 8 2 5 7 9 输出: 1 2 5 6 7 8 9 测试数据 输入：7 9 10 11 8 9 10 11

输出：7 8 9 10 11 3. 知L1、L2分别为两循环单链表的头结点指针，m,n分别为L1、L2表中数据结点个数。要求设计一算法，用最快速度将两表合并成一个带头结点的循环单链表。 4. 顺序结构线性表LA与LB的结点关键字为整数。LA与LB的元素按非递减有序，线性表空间足够大。试用类PASCAL语言给出一种高效算法，将LB中元素合到LA中，使新的LA的元素仍保持非递减有序。高效指最大限度的避免移动元素。 5. 已知不带头结点的线性链表list，链表中结点构造为（data、link），其中data为数据域，link为指针域。请写一算法，将该链表按结点数据域的值的大小从小到大重新链接。要求链接过程中不得使用除该链表以外的任何链结点空间。 6. 设L为单链表的头结点地址，其数据结点的数据都是正整数且无相同的，试设计利用直接插入的原则把该链表整理成数据递增的有序单链表的算法。 7. 设 Listhead为一单链表的头指针，单链表的每个结点由一个整数域DATA和指针域NEXT组成，整数在单链表中是无序的。编一PASCAL 过程，将 Listhead链中结点分成一个奇数链和一个偶数链，分别由

数据结构 线性表 课后答案

第2章线性表 1．选择题 （1）顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。 A．110 B．108 C．100 D．120 答案：B 解释：顺序表中的数据连续存储，所以第5个元素的地址为：100+2*4=108。 （2）在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（）。 A．访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） B．在第i个结点后插入一个新结点（1≤i≤n） C．删除第i个结点（1≤i≤n） D．将n个结点从小到大排序 答案：A 解释：在顺序表中插入一个结点的时间复杂度都是O(n2)，排序的时间复杂度为O(n2)或O(nlog2n)。顺序表是一种随机存取结构，访问第i个结点和求第i个结点的直接前驱都可以直接通过数组的下标直接定位，时间复杂度是O(1)。 （3）向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（）。 A．8 B．63.5 C．63 D．7 答案：B 解释：平均要移动的元素个数为：n/2。 （4）链接存储的存储结构所占存储空间（）。 A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 B．只有一部分，存放结点值 C．只有一部分，存储表示结点间关系的指针 D．分两部分，一部分存放结点值，另一部分存放结点所占单元数 答案：A （5）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。 A．必须是连续的B．部分地址必须是连续的 C．一定是不连续的D．连续或不连续都可以 答案：D （6）线性表Ｌ在（）情况下适用于使用链式结构实现。 A．需经常修改Ｌ中的结点值Ｂ．需不断对Ｌ进行删除插入 C．Ｌ中含有大量的结点Ｄ．Ｌ中结点结构复杂 答案：B

以下关于线性表的说法不正确的是(

一、选择题 1、以下关于线性表的说法不正确的是( )。 A、线性表中的数据元素可以是数字、字符、记录等不同类型。 B、线性表中包含的数据元素个数不是任意的。 C、线性表中的每个结点都有且只有一个直接前趋和直接后继。 D、存在这样的线性表：表中各结点都没有直接前趋和直接后继。 2、线性表的顺序存储结构是一种( )的存储结构。 A、随机存取 B、顺序存取 C、索引存取 D、散列存取 3、在顺序表中，只要知道( )，就可在相同时间内求出任一结点的存储地址。 A、基地址 B、结点大小 C、向量大小 D、基地址和结点大小 4、在等概率情况下，顺序表的插入操作要移动( )结点。 A、全部 B、一半 C、三分之一 D、四分之一 5、在( )运算中，使用顺序表比链表好。 A、插入 B、删除 C、根据序号查找 D、根据元素值查找 6、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是( )。 A、O(1) B、O(n) C、O(n^2) D、O(log2n) 二、填空题 1、线性表是一种典型的( )结构。 2、在一个长度为n的顺序表中删除第i个元素，要移动( )个元素 3、如果要在第i个元素前插入一个元素，要后移( )个元素。 4、采用( )存储结构的线性表叫顺序表。 5、顺序表中逻辑上相邻的元素的物理位置( )。 6、在无头结点的单链表中，第1个结点的地址存放在头指针中，其他结点的存储地址存放 在( )结点的next域中。 三、简答；

2.1 试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。 2.2 何时选用顺序表、何时选用链表作为线性表的存储结构为宜? 2.3 为什么在单循环链表中设置尾指针比设置头指针更好? 2.4 下述算法的功能是什么? 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 2.5设线性表的n个结点定义为(a0,a1,...a n-1)，重写顺序表上实现的插入和删除算法：InsertList 和DeleteList. 2.6 设顺序表L是一个递减有序表，试写一算法，将x插入其后仍保持L的有序性。2.7 写一算法在单链表上实现线性表的ListLength(L)运算。 2.8 写一算法将单链表中值重复的结点删除，使所得的结果表中各结点值均不相同。

线性表 答案

数据结构与算法上机作业第二章线性表

一、选择题 1、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新的元素算法的时间复杂度为 C 。 A. O(log2n) B. O(1) C. O(n) D. O(n2) 2、以下关于线性表的说法中，不正确的是 C 。 A. 线性表中的数据元素可以是数字、字符、结构等不同类型 B. 线性表中包含的数据元素个数不是任意的 C. 线性表中的每一个结点都有且只有一个直接前驱和直接后继 D. 存在这样的线性表：表中各结点都没有直接前驱和直接后继 3、在有n个结点的顺序表上做插入、删除结点运算的时间复杂度为 B 。 A. O(1) B. O(n) C. O(n2) D. O(log2n) 4、等概率情况下，在有n个结点的顺序表上做插入结点操作，需平均移动的结点数目为 C 。提示：插入的位置有n+1个，移动总数为：1+2+3+……+n A. n B. (n-1)/2 C. n/2 D. (n+1)/2 5、在一个长度为n的顺序存储的线性表中查找值为x的元素时，平均查找长度(及x同元素的平均比较次数，假定查找每个元素的概率都相等)为 C 。 A. n B. n/2 C. (n+1)/2 D. (n-1)/2 6、在顺序表中，只要知道 D ，就可以求出任一结点的存储地址。 A. 基地址 B. 结点大小 C. 向量大小 D. 基地址和结点大小 7、将两个各有n个元素的有序表归并为一个有序表，其最少的比较次数是 A 。 A. n B. 2n-1 C. 2n D. n-1 8、线性表采用链表存储时其存储地址要求 D 。 A. 必须是连续的 B. 部分地址必须是连续的 C. 必须是不连续的 D. 连续的和不连续的都可以 9、下面关于线性表的描述中，错误的是 B 。 A. 线性表采用顺序存储，必须占用一片连续的存储单元 B. 线性表采用顺序存储，便于进行插入和删除操作 C. 线性表采用链式存储，不必占用一片连续的存储单元 D. 线性表采用链式存储，便于插入和删除操作 10、向具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是 B A. O(1) B. O(n) C. O(n2) D. O(log2n) 11、在一个带头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行的语句是 D 。 A. HL=p; p->next=HL; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. p->next=HL->next; HL->next=p; 12、在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行的语句是C 。 A. p=q->next; p->next=q->next; B. p=q->next; q->next=p; C. p=q->next; q->next=p->next; D. q->next=q->next->next; q->next=q; 13、设有编号为1, 2, 3, 4的4辆列车，顺序进入一个栈结构的站台，下列不可能的出栈顺序为 D 。 A. 1234 B. 1243 C. 1324 D. 1423

第二章_线性表(参考答案)

第二章线性表 一、填空题 1、数据逻辑结构包括线性结构、树型结构、图型结构这三种类型，树形结构和图形结构合称为非线性结构。 2、在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有个前驱结点，最后一个结点没有后续结点，其余每个结点有且只有一个后续结点。 3、在顺序表中插入或删除一个元素，需要平均移动一半元素，具体移动的元素个数与插入或删除的位置有关。 4、在顺序表中，逻辑上相邻的元素，其物理位置一定相邻。在单链表中，逻辑上相邻的元素，其物理位置不一定相邻。 5、在带头结点的非空单链表中，头结点的存储位置由头指针指示，首元素结点的存储位置由头结点的next域指示，除首元素结点外，其它任一元素结点的存储位置由其直接前趋结点的next域指示。 6、阅读下列算法，并补充所缺内容。 void purge_linkst( ListNode *& la ) { // 从头指针为 la 的有序链表中删除所有值相同的多余元素，并释放被删结点空间ListNode *p,*q; if(la==NULL) return; q=la; p = la->link; while (p) { if (p && ___(1)p->data!=q->data___) {q=p; p = p->link;} else { q->link= ___(2)p->link___; delete(p); p=___(3)q->link___; } }//while }// purge_linkst 二、选择题 1、在数据结构中，从逻辑上可以把数据结构分成 C。 A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 2、线性表的逻辑顺序与存储顺序总是一致的，这种说法 B。 A、正确 B、不正确 3、线性表若采用链式存储结构时，要求内存中可用存储单元的地址D。 A、必须是连续的 B、部分地址必须是连续的 C、一定是不连续的 D、连续或不连续都可以 4、在以下的述叙中，正确的是B。 A、线性表的线性存储结构优于链表存储结构 B、二维数组是其数据元素为线性表的线性表 C、栈的操作是先进先出 D、队列的操作方式是先进后出 三、综合题 1、已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。 A、在P结点后插入S结点的语句序列是（（4）、（1））； B、在P结点前插入S结点的语句序列是（（7）、（11）、（8）、（4）、（1））； C、在表首插入S结点的语句序列是（（5）、（12））；

线性表作业

一、单项选择题 1．顺序表是线性表的（ B ） A．链式存储结构B．顺序存储结构C．索引存储结构D．散列存储结构 2.对于顺序表，以下说法错误的是（A ） A．顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址 B．顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列 C．顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻 D．顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中 3．线性表是具有n个（C）的有限序列（n>0）。 A．表元素B．字符C．数据元素D．数据项E．信息项 4.以下说法错误的是(A ) A．对于线性表来说，定位运算LocateElem在顺序表和单链表上的时间复杂度均为O（n） B．读表元运算在顺序表上只需常数时间O（1）便可实现，因此顺序表是一种随机存取结构C．在链表上实现读表元运算的平均时间复杂度为O（1） D．插入、删除操作在链表上的实现可在O（1）时间内完成 E．插入、删除操作在顺序表上的实现，平均时间复杂度为O（n） 5.若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ A ）存储方式最节省时间。 A．顺序表B．单链表C．双链表D．单循环链表 6. 静态链表中指针表示的是（ C ）. A．内存地址B．数组下标C．下一元素地址D．左、右孩子地址 7.链表不具有的特点是（ B ） A．插入、删除不需要移动元素B．可随机访问任一元素 C．不必事先估计存储空间D．所需空间与线性长度成正比 8．在循环链表中，将头指针改设为尾指针（rear）后，其头结点和尾结点的存储位置分别是（D ）A．rear和rear->next->next B．rear->next 和rear C．rear->next->next和rear D．rear和rear->next 9.在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（B）。 A．p->next=s;s->next=p->next; B．s->next=p->next;p->next=s; C．p->next=s;p->next=s->next; D．p->next=s->next;p->next=s; 10．对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（B）A．head==NULL B．head→next==NULL C．head→next==head D．head!=NULL 二、填空题 1.以下为顺序表的定位运算，分析算法，请在________处填上正确的语句。 int locate_sqlist(sqlist L,datatype X) /*在顺序表L中查找第一值等于X的结点。若找到回传该结点序号；否则回传0*/ {__int I;______; while((i≤https://www.wendangku.net/doc/556433132.html,st)&&(L.data[i-1]!=X))i++; if(___L.data[i-1]==X_____)return(i); else return(0);

《数据结构》第二章线性表习题及参考答案

《数据结构》 第二章线性表习题 一、单项选择题 1. 线性表是________。 A．一个有限序列，可以为空B．一个有限序列，不可以为空 C．一个无限序列，可以为空D．一个无限序列，不可以为空 2. 在一个长度为n的顺序表中删除第i个元素(0<=i<=n)时，需向前移动个元素。 A．n-i B．n-i+l C．n-i-1 D．i 3. 线性表采用链式存储时，其地址________。 A．必须是连续的B．一定是不连续的 C．部分地址必须是连续的D．连续与否均可以 4. 从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较________个元素结点。 A．n/2 B．n C．（n+1）/2 D．（n-1）/2 5. 在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是____。 A． p->next=s; s->prior=p; p->next->prior=s; s->next=p->next; B． s->prior=p; s->next=p->next; p->next=s; p->next->prior=s; C． p->next=s; p->next->prior=s; s->prior=p; s->next=p->next; D． s->prior=p; s->next=p->next; p->next->prior=s; p->next=s; 6. 设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为________。A．p->next=p->next->next; B．p=p->next; C．p=p->next->next; D．p->next=p; 7. 在一个长度为n的顺序表中向第i个元素(0< inext=p->next; p->next=s B．q->next=s; s->next=p C．p->next=s->next; s->next=p D．p->next=s; s->next=q 9. 以下关于线性表的说法不正确的是______。 A．线性表中的数据元素可以是数字、字符、记录等不同类型。 B．线性表中包含的数据元素个数不是任意的。 C．线性表中的每个结点都有且只有一个直接前趋和直接后继。 D．存在这样的线性表：表中各结点都没有直接前趋和直接后继。