线性表作业二

一、填空

1. 在顺序表中插入或删除一个元素，需要平均移动表的一半元素，具体移动的元素个数与插入或删除的位置有关有关。

2. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动n-i+1 个元素。

3. 顺序表中逻辑上相邻的元素的物理位置也相邻。单链表中逻辑上相邻的元素的物理位置不一定相邻。

4. 在单链表中，除了首元结点外，任一结点的存储位置由指针

指示。

5．在n个结点的单链表中要删除已知结点*p，需找到它的指针，其时间复杂度为O(N) 。

二、选择题

1．设指针P指向双链表的某一结点，则双链表结构的对称性可用（ 3 ）式来刻画

①p->prior->next->==p->next->next

②p->prior->prior->==p->next->prior

③p->prior->next->==p->next->prior

④p->next->next==p->prior->prior

2.以下说法错误的是（1 ）

①对循环链表来说，从表中任一结点出发都能通过前后操作而扫描整个循环链表

②对单链表来说，只有从头结点开始才能扫描表中全部结点

③双链表的特点是找结点的前趋和后继都很容易

④对双链表来说，结点*P的存储位置既存放在其前趋结点的后继指针域中，也存放在它的后继结点的前趋指针域中。

3．在循环链表中，将头指针改设为尾指针（rear）后，其头结点和尾结点的存储位置分别是（ 2 ）

①real和rear->next->next

②rear->next 和real

③rear->next->next和rear

④rear和rear->next

4.设REAR是指向非空带头结点的循环单链表的尾指针,则删除表首结点的操作可表示为( 4 )

①p=rear; ②rear=rear->next;

rear=rear->next; free(rear);

free(p)

③rear=rear->next->next; ④ p=rear->next->next;

free(rear); rear->next->next=p->next; free(p);

线性表复习试题二2010.11.24

一、单项选择题（共30题，每题1分，共计30分）

1．对于线性表基本运算，以下结果是正确的是 ( )

A.初始化INITIATE(L)，引用型运算，其作用是建立一个空表L=Ф

B. 求表长LENGTH(L)，引用型运算，其结果是线性表L的长度

C.插入INSERT(L,X,i),加工型运算。其作用是在线性表L的第i+1个位置上增加一个以X为值的新结点

D.删除DELETE(L,i), 引用型运算.其作用是撤销线性表L的第i个结点Ai

2.线性结构中的一个结点代表一个（）

A. 数据元素

B. 数据项

C. 数据

D. 数据结构

3．顺序表的一个存储结点仅仅存储线性表的一个（）

A. 数据元素

B. 数据项

C. 数据

D. 数据结

构

4．顺序表是线性表的（）

A.链式存储结构

B.顺序存储结构

C. 索引存储结构

D. 散列存储结构

5.对于顺序表，以下说法错误的是（）

A.顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址

B.顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列

C.顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻

D.顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中

6.对顺序表上的插入、删除算法的时间复杂性分析来说，通常以（）为标准操作.

A.条件判断

B.结点移动

C.算术表达式

D.赋值语句

7.对于顺序表的优缺点，以下说法错误的是（）

A.无需为表示结点间的逻辑关系而增加额外的存储空间

B.可以方便地随机存取表中的任一结点

C.插人和删除运算较方便

D.由于顺序表要求占用连续的空间，存储分配只能预先进行(静态分配)

E.容易造成一部分空间长期闲置而得不到充分利用

8.指针的全部作用就是（）

A.指向某常量

B. 指向某变量

C.指向某结点

D.存储某数据

9.单链表的一个存储结点包含（）

A.数据域或指针域

B.指针域或链域

C.指针域和链域

D.数据域和链域

10．有时为了叙述方便，可以对一些概念进行简称，以下说法错误的是（）

A.将“指针型变量”简称为“指针”

B.将“头指针变量”称为“头指针”

C.将“修改某指针型变量的值”称为“修改某指针”

D.将“p中指针所指结点”称为“P值”

11．设指针P指向双链表的某一结点，则双链表结构的对称性可用（）式来刻画

A. p->prior->next->==p->next->next

B. p->prior->prior->==p->next->prior

C. p->prior->next->==p->next->prior

D. p->next->next==p->prior->prior

12.以下说法错误的是（）

A.对循环链表来说，从表中任一结点出发都能通过前后操作而扫描整个循环链表

B.对单链表来说，只有从头结点开始才能扫描表中全部结点

C.双链表的特点是找结点的前趋和后继都很容易

D.对双链表来说，结点*P的存储位置既存放在其前趋结点的后继指针域中，也存放在它的后继结点的前趋指针域中。

13．在循环链表中，将头指针改设为尾指针（rear）后，其头结点和尾结点的存储位置分别是（）

A. rear和rear->next->next

B. rear->next 和rear

C. rear->next->next和rear

D. rear和rear->next

14.以下说错误的是 ( )

A.对于线性表来说，定位运算在顺序表和单链表上的量级均为O（n）

B.读表元运算在顺序表上只需常数时间O（1）便可实现，因此顺序表是一种随机存取结构.

C.在链表上实现读表元运算的平均时间复杂性为O（1）

D.链入、摘除操作在链表上的实现可在O（1）时间内完成

E.链入、摘除操作在顺序表上的实现，平均时间复杂性为O（n）

15．循环链表主要优点是（）

A.不再需要头指针了

B.已知某个结点的位置后，能够容易找到它的直接前趋

C.在进行插入、删除运算时，能更好地保证链表不断开

D.从表中任一结点出发都能扫描到整个链表

16．以下说法错误的是（）

A.数据的物理结构是指数据在计算机内实际的存储形式

B.算法和程序没有区别，所以在数据结构中二者是通用的

C.对链表进行插人和删除操作时，不必移动结点

D.双链表中至多只有一个结点的后继指针为空

17．以下说法正确的是

A.线性结构的基本特征是：每个结点有且仅有一个直接前趋和一个直接后继

B.线性表的各种基本运算在顺序存储结构上的实现均比在链式存储结构上的实现效率要低

C.在线性表的顺序存储结构中，插人和删除元素时，移动元素的个数与该元素位置及表长有关

D.顺序存储的线性表的插人和删除操作不需要付出很大的代价，因为平均每次操只有近一半的元素需要移动

18．以下说法错误的是（）

A.求表长、定位这二种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低

B.顺序存储的线性表可以随机存取

C.由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活

D.线性表的链式存储结构优于顺序存储结构

19.以下说法正确的是（）

A.顺序存储方式的优点是存储密度大、且插入、删除运算效率高

B.链表的每个结点中都恰好包含一个指针

C.线性表的顺序存储结构优于链式存储结构

D.顺序存储结构属于静态结构，链式结构属于动态结构

20.下面关于线性表的叙述正确的是( )

A.线性表采用顺序存储，不必占用一片连续的存储单元

B.线性表采用顺序存储，便于进行插人和删除操作

C.线性表采用链接存储，不必占用一片连续的存储单元

D.线性表采用链接存储，不便于插人和删除操作

21.线性表L=(a1,a2,...,a i,...,a n),下列说法正确的是( )

A.每个元素都有一个直接前驱和直接后继

B.线性表中至少要有一个元素

C.表中诸元素的排列顺序必须是由小到大或由大到小的

D.除第一个元素和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接后继

22.线性表的逻辑顺序与存储顺序总是一致的，这种说法( )

A.正确

B.不正确

23.设p,q是指针,若p=q,则*p=*q ,这种说法( )

A.正确

B.不正确

24.设REAR是指向非空带头结点的循环单链表的尾指针,则删除表首结点的操作可表示为( )

A. p=rear;

B. rear=rear->next;

rear=rear->next; free(rear);

free(p)

C. rear=rear->next->next;

D. p=rear->next->next;

free(rear); rear->next->next=p->next;

free(p);

25. 单链表中，增加头结点的目的是为了 ( )

A.使单链表至少有一个结点

B.标示表结点中首结点的位置

C.方便运算的实现

D.说明单链表是线性表的链式存储实现

26.线性结构中的一个结点代表一个数据元素，通常要求同一线性结构的所有结点所代表的数据元素具有相同的特性，这意味着

A.每个结点所代表的数据元素都一样。

B.每个结点所代表的数据元素包含的数据项的个数要相等

C.不仅数据元素包含的数据项的个数要相同，而且对应数据项的类型要一致

D.结点所代表的数据元素有同一特点

27．带头结点的单链表Head为空的判定条件是

A. Head=Null

B. Head->next=NULL

C.Head->next=Head

28.非空的单循环链表L的尾结点*P,满足

A. P->next=NULL

B.P=NULL

C. P->next=L

D. P=L.

29.双向链表结点结构如下：

其中：LLink是指向前驱结点的指针域：

data是存放数据元素的数据域；

Rlink是指向后继结点的指针域。

下面给出的算法段是要把一个新结点*Q作为非空双向链表中的结点*p的前驱，插入到此双向链表中。不能正确完成要求的算法段是

A. Q->LLink=P->LLink;

B. P->LLink=Q;

Q->Rlink=P; Q->Rlink=P;

P->LLink=Q; P->LLink->Rlink=Q;

P->LLink->Rlink=Q; Q->LLink=P->LLink;

C. Q->LLink=P->LLink;

Q->Rlink=P;

P->LLink->Rlink=Q;

P->LLink=Q;

30.若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（）存储方式最节省时间。

A. 顺序表

B. 单链表

C. 双链表

D. 单循环链表

二、填空题（每空4分，共20分）

1、已知p结点是某双链表的中间结点，试从下列提供的答案这选择合适的语句序列。

①在p结点后插入s结点的语句序列是

___ __；

②在p结点前插入s结点的语句序列是

___ __；

③删除p结点的直接后继结点的语句序列是

____ ___；

④删除p结点的直接前驱结点的语句序列是

_ ______；

⑤删除p结点的语句序列是

____ ___。

（1）P->next=p->next->next ; (2) P->prior=p->prior->prior; (3) P->next=S;

(4) p->prior=S; (5) S->next=P; (6)

S->prior=P;

(7) S->next=P->next; (8) S->prior=P->prior; (9)

P->prior->next=P->next;

(10) P->prior->next=P; (11) P->next->prior=P; (12)

P->next->prior=S ;

(13) P->prior->next=S; (14) P->next->prior=P->prior; (15) Q=P->next;

(16) Q=P->prior; (17) free(P); (18) free(Q);

三、读程序写结果（共4题，每题8分，共计32分）

1. #include

int main()

{

int i, a, b, c, d, f[4];

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

scanf ("%d", &f[i]);

a = f[0] + f[1] + f[2] + f[3];

a = a / f[0];

b = f[0] + f[2] + f[3];

b = b / a;

c = (b * f[1] + a) / f[2];

d = f[(b / c ) % 4];

if(f[(a + b + c + d) % 4] > f[2])

printf("%d\n", a + b);

else

printf("%d\n", c + d);

return 0;

}

输入：9 19 29 39

输出：

2．#include

void foo(int a, int b, int c)

{

if(a > b)

foo(c, a, b);

else

printf("%d,%d,%d\n", a, b, c);

}

int main()

{

int a, b, c;

scanf("%d %d %d", &a, &b, &c);

foo(a, b, c);

return 0;

}

输入: 3 1 2 输出: 3．#include

void func(int ary[], int n )

{

int i=0, j, x;

j=n-1;

while(i

{

while (i0) i++;

while (i

if (i

x=ary[i];

ary[i++]=ary[j];

ary[j--]=x;

}

}

}

int main()

{

int a[20], i, m;

m=10;

for(i=0; i

scanf("%d", &a[i]);

func(a, m);

for (i=0; i

printf( "%d ", a[i] );

printf("\n");

return 0;

}

输入：5 4 -6 -11 6 -59 22 -6 1 10 输出：

4. #include

#define MAX 100

void solve(char first[], int spos_f, int epos_f, char mid[], int spos_m, int epos_m)

{

int i, root_m;

if(spos_f > epos_f)

return;

for(i = spos_m; i <= epos_m; i++)

if(first[spos_f] == mid[i])

{

root_m = i;

break;

}

solve(first, spos_f + 1, spos_f + (root_m - spos_m), mid, spos_m, root_m - 1);

solve(first, spos_f + (root_m - spos_m) + 1, epos_f, mid, root_m + 1, epos_m);

printf("%c", first[spos_f]);

}

int main()

{

char first[MAX], mid[MAX];

int len;

scanf("%d", &len);

scanf("%s", first);

scanf("%s", mid);

solve(first, 0, len - 1, mid , 0, len - 1);

printf("\n");

return 0;

}

输入： 7

ABDCEGF

BDAGECF 输出：

四、完善程序（共10题，每题3分，其中第4、7、8题，每题4分，第9题8（3+3+2）分。共38分）

1、INITIATE()的功能是建立一个空表。请在________处填上正确的语句。

lklist initiate_lklist()

{ t = malloc (size);

________________;

return(t);

}

2、以下为顺序表的插入运算，分析算法，请在______处填上正确的语句。

Void insert_sqlist(sqlist L，datatype x，int i)

{ if( https://www.wendangku.net/doc/b018567204.html,st == maxsize) error(“表满”)；

if((i<1)||(i>https://www.wendangku.net/doc/b018567204.html,st+1))error(“非法位置”);

for (j=https://www.wendangku.net/doc/b018567204.html,st;j>=i;j--)______;

L.data [i-1]=x;

https://www.wendangku.net/doc/b018567204.html,st =https://www.wendangku.net/doc/b018567204.html,st+1;

}

3、以下为顺序表的删除运算，分析算法，请在________处填上正确的语句。void delete_sqlist(sqlist L,int i)

{if((i<1)||(i>https://www.wendangku.net/doc/b018567204.html,st))error(“非法位置”)；

for(j=i+1;j<=https://www.wendangku.net/doc/b018567204.html,st;j++)________;

https://www.wendangku.net/doc/b018567204.html,st=https://www.wendangku.net/doc/b018567204.html,st-1;

}

4、以下为求单链表表长的运算，分析算法，请在 ________处填上正确的语句。 int length_lklist(lklist head)

{________;

j=0;

while(p->next!=NULL)

{________________;

j++;

}

return(j);

}

5、以下为单链表按序号查找的运算，分析算法，请在____处填上正确的语句。 pointer find_lklist(lklist head,int i)

{ p=head;j=0;

while(________________)

{ p=p->next; j++; }

if(i==j) return(p);

else return(NULL);

}

6、以下为单链表的定位运算，分析算法，请在____处填上正确的语句。 int locate_lklist(lklist head,datatype x)

{ p=head;j=0;

while(________________________________){p=p->next;j++;}

if (p->data==x) return(j);

else return(0);

}

7、以下为单链表的删除运算，分析算法，请在____处填上正确的语句。 void delete_lklist(lklist head,int i)

{ p=find_lklist(head,i-1);

if(____________________________)

{ q=________________;

p->next=p->next->next;

free(q);

}

else error(“不存在第i个结点”)

}

8、以下为单链表的插入运算，分析算法，请在____处填上正确的语句。 void insert_lklist(lklist head,datatype x,int i)

{ p=find_lklist(head,i-1);

if(p==NULL)error(“不存在第i个位置”)；

else {s= mailloc(size);____________=x;

s->next=________________;

p->next=s;

}

}

9、以下为单链表的建表算法，分析算法，请在____处填上正确的语句。

lklist create_lklist2()

{ head=malloc(size);

p=head;

scanf(“%f”,&x);

while(x!=’$’)

{ q=malloc(size);

q->data=x;

p->next=q;

________________;

scanf(“%f”,&x); }

________________;

return(head);

} 此算法的量级为________________。

10、以下为顺序表的定位运算，分析算法，请在________处填上正确的语句。int locate_sqlist(sqlist L,datatype X)

{i=1;

while((i≤https://www.wendangku.net/doc/b018567204.html,st)&&(L.data[i]!=X))i++;

if(________)return(i);

else return(0);

}

线性表复习试题二答案（满分120分）

一、单项选择题（共30题，每题1分，共计30分）

二、填空题（每空4分，共20分）

①_ 7 3 12 6 __；②__ 8 13 4 5 _；

③____ 15 1 18 ___；④_ 16 2 18 _____；

⑤___ 9 14 17 。

三、阅读程序写结果（共4题，每题8分，共计32分）

1、 23

2、 2 3

1

3、 5 4 10 1 6 22 -59 -6 -11 -6

4、 DBGEFCA

三、完善程序（共10题，每题3分，其中第4、7、8题，每题4分，第9题8（3+3+2）分。共38分）

1、t->next=NULL

2、L．data[j]=L．data[j-1]

3、L.data[j-2]=L.data[j-1]

4、p=head p=p->next

5、(p->next!=NULL)&&(j

6、(p->next!=NULL)&&(p->data!=x)

7、(p!=NULL)&&(p->next!=NULL) p->next

8、s->data, p->next

9、p=q(或者p=p->next) p->next=NULL O(n)

10、L.data[i]==x

第二章 考研试题精选

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

实验1__线性表的应用

实验一线性表的应用 一、实验教学目的 1、熟悉将算法转换成程序代码的过程。 2、了解顺序表的逻辑结构特性，熟练掌握顺序表存储结构的C语言描述方法。 3、熟悉链表数据结构的定义和插入、删除等基本操作，会使用链表的基本操作解决一些实际问题 二、实验教学内容 1、实验题目 (1)用C语言数组实现顺序表,并在顺序表上实现：①在第3个位置插入666; ②将第8个元素删除；③在顺序表中查找值为65的元素。 (2)已知有两个多项式Pn(x)和Qm(x)，基于链表设计算法实现Pn(x)+Qm(x)运算，而且不重新开辟存储空间。 ⑶基于链表编程实现多项式乘法运算 2、实验要求： (1)要求用静态分配的一维数组和动态分配的一维数组来完成实验题目。分析静态分配的一维数组和动态分配的一维数组在顺序表基本操作实现上的共同点和区别。 (2)熟悉链表及其运算的实现。 ①自己编写实现函数； ②对所编写的算法进行时间复杂度分析。 ⑶实验⑴、⑵必做，实验⑶选做。 3、实验预备知识 （1）复习C语言相关知识（如：结构体、用typedef自定义类型、函数）。 （2）阅读顺序表与链表的类型定义和相应的插入、删除、查找等基本操作。 4、实验环境

（1）一台运行 Windows 2000/XP 操作系统的计算机。 （2）选用turbo c、visual c++、delphi、c++ builder 或visual basic等任何一种语言。 5、实验说明 （1）顺序存储定义 #define MAXSIZE 100/*表中元素的最大个数*/ typedef int datatype; /*元素类型*/ typedef struct {datatype data[MAXSIZE]; /*静态线性表*/ int last; /*表的实际长度*/ }seqlist; /*顺序表的类型名*/ （2）建立顺序表时可利用随机函数自动产生数据。 （3）注意问题 ①插入、删除时元素的移动原因、方向及先后顺序。 ②不同的函数形参与实参的传递关系。 （4）链表类型定义 typedef int datatype;/*元素类型*/ typedef struct node {datatype data; struct node *next; }lnode,*linklist;/*单链表的类型定义*/ （5）为了算法实现简单，最好采用带头结点的单向链表。 （6）注意问题 ①重点理解链式存储的特点及指针的含义。 ②注意比较顺序存储与链式存储的各自特点。 ③注意比较带头结点、无头结点链表实现插入、删除算法时的区别。 ④单向链表的操作是数据结构的基础，一定要注意对这部分的常见算法的理解。 三、实验内容和实验步骤：（由学生填写） 四、实验用测试数据和相关结果分析：（由学生填写） 五、实验总结：（由学生填写） 六、程序参考模板

第二章线性表答案

2.11 设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。 Status OrderListInsert-sq(SqList va, ElemType x) { //将x插入到递增有序的顺序表va中，插入后va仍然递增有序(算法1) if (va.length==va.listsize){ newbase=(ElemType *)realloc(va.elem,(va.listsize+LISTINCREMENT)*sizeof(ElemType)); if (!newbase) exit(OVERFLOW); va.elem=newbase; va.listsize+=LISTINCREMENT; }//当前存储空间已满，增加分配空间 if (!va.length) {va.elem[0]=x; ++va.length; return OK;} q=&(va.elem[0]); while (*q<=x)&&(q<=&(va.elem[va.length-1])) ++q; //查找插入位置 for (p=&(va.elem[va.length-1]); p>=q; --p) *(p+1)=*p; *q=x; ++va.length; return OK; }//OrderListInsert-sq Status OrderListInsert-sq(SqList va, ElemType x) { //将x插入到递增有序的顺序表va中，插入后va仍然递增有序(算法2) if (va.length==va.listsize){ newbase=(ElemType *)realloc(va.elem,(va.listsize+LISTINCREMENT)*sizeof(ElemType)); if (!newbase) exit(OVERFLOW); va.elem=newbase; va.listsize+=LISTINCREMENT; }//当前存储空间已满，增加分配空间 if (!va.length) {va.elem[0]=x; ++va.length; return OK;} p=&(va.elem[va.length-1]); while (P>=&(va.elem[0])&&*p>x) {*(p+1)=*p; --p;} *(p+1)=x; ++va.length;

第二章线性表答案

第2章线性表 一选择题 1．下述哪一条是顺序存储结构的优点？（ A ） A．存储密度大 B．插入运算方便 C．删除运算方 便 D．可方便地用于各种逻辑结构的存储表示 2．下面关于线性表的叙述中，错误的是哪一个？（ B ）A．线性表采用顺序存储，必须占用一片连续的存储单元。B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。D．线性表采用链接存储，便于插入和删除操作。 3．线性表是具有n个（ C ）的有限序列（n>0）。 A．表元素 B．字符 C．数据元 素 D．数据项 E．信息项 4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。 AHA12GAGGAGAGGAFFFFAFAF

A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表 5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。 A．单链表 B．仅有头指针的单循环链 表 C．双链表D．仅有尾指针的单循环链表 6．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( D )最节省时间。 A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表 7．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ D ）存储方式最节省运算时间。 AHA12GAGGAGAGGAFFFFAFAF

A．单链表 B．双链表 C．单循环链 表 D．带头结点的双循环链表 8. 静态链表中指针表示的是（ BC ）. A．内存地址 B．数组下标 C．下一元素地址D．左、右孩子地址 9. 链表不具有的特点是（ C ） A．插入、删除不需要移动元素 B．可随机访问任一元素C．不必事先估计存储空间 D．所需空间与线性长度成正比 10. 下面的叙述不正确的是（ BC ） A．线性表在链式存储时，查找第i个元素的时间同i的值成正比 AHA12GAGGAGAGGAFFFFAFAF

数据结构线性表实验报告

《数据结构》实验报告 专业： 学号： 姓名： 实验二线性表 【实验目的】 1.熟悉VC环境，学习如何使用C语言实现线性表的两种存储结构。 2.通过编程、上机调试，进一步理解线性表的基本概念，东运用C语言实现线性表基本操作。 3.熟练掌握线性表的综合应用问题。 【实验内容】 1、一个线性表有n个元素（n-MAXSIZE.MAXSIZE指线性表的最大长度），且递增有。现有一元素x要插入到线性表的适当位置上，并保持线性表原有的顺序不变。设计程序实现。要求：采用顺序存储表示实现；采用链式存储表示方法实现：比较两种方法的优劣。 2.从单链表中删除指定的元素x，若x在单链表中不存在，给出提示信息。 要求： ①指定的值x由键盘输入； ②程序能处理空链表的情况。 3.设有头结点的单链表，编程对表中的任意值只保留一个结点，删除其余值相同的结点。 要求： ①该算法用函数（非主函数)实现； ②在主函数中调用创建链表的函数创建一个单链表，并调用该函数，验证算法的正确性。LinkedList Exchange（LinkedList HEAD,p) //HEAD是单链表头结点的指针，p是链表中的一个结点。本算法将p所指结点与其后 继结点交换。 （q=head->next；//q是工作指针，指向链表中当前待处理结点。 pre=head；//pre是前驱结点指针，指向q的前驱。 while（q'=null &&q1=p)(pre=q；q=q->next；]/未到p结点，后移指针。 if（p->next==null)printf(“p无后继结点\n”）；/p是链表中最后一个结点，无后继。 else/处理p和后继结点交换 （q=p->next；//暂存p的后继。 pre->next=q://p前驱结点的后继指向p的后继。 p->next=q->next；//p的后继指向原p后继的后继。 q->next=p：//原p后继的后继指针指向p。} }//算法结束。 4.已知非空单链表第一个结点由head指出，请写一算法，交换p所指结点与其下一个结点在链表中的位置。 要求：

数据结构第2章作业 线性表(答案)

第2章线性表 班级学号__________-姓名 一、判断正误 （×）1. 链表的每个结点中都恰好包含一个指针。 链表中的结点可含多个指针域，分别存放多个指针。例如，双向链表中的结点可以含有两个指针域，分别存放指向其直接前趋和直接后继结点的指针。 （×）2. 链表的物理存储结构具有同链表一样的顺序。 链表的存储结构特点是无序，而链表的示意图有序。 （×）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。 链表的结点不会移动，只是指针内容改变。 （×）4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 混淆了逻辑结构与物理结构，链表也是线性表！且即使是顺序表，也能存放记录型数据。 （×）5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 正好说反了。顺序表才适合随机存取，链表恰恰适于“顺藤摸瓜” （×）6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 前一半正确，但后一半说法错误，那是链式存储的优点。顺序存储方式插入、删除运算效率较低，在表长为n的顺序表中，插入和删除一个数据元素，平均需移动表长一半个数的数据元素。 （×）7. 线性表在物理存储空间中也一定是连续的。 线性表有两种存储方式，顺序存储和链式存储。后者不要求连续存放。 （×）8. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。 线性表有两种存储方式，在顺序存储时，逻辑上相邻的元素在存储的物理位置次序上也相邻。 （×）9. 顺序存储方式只能用于存储线性结构。 顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构，例如 完全二叉树是属于非线性结构，但其最佳存储方式是顺序存储方式。（后一节介绍） （×）10. 线性表的逻辑顺序与存储顺序总是一致的。 理由同7。链式存储就无需一致。 二、单项选择题 （C ）1．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：（A）存储结构（B）逻辑结构（C）顺序存储结构（D）链式存储结构（ B ）2. 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（A）110 （B）108 （C）100 （D）120 （ A ）3. 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是： （A）访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） （B）在第i个结点后插入一个新结点（1≤i≤n） （C）删除第i个结点（1≤i≤n） （D）将n个结点从小到大排序 （ B ）4. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动个元素（A）8 （B）63.5 （C）63 （D）7 （ A ）5. 链式存储的存储结构所占存储空间：

201560140140--袁若飞--实验1：线性表的基本操作及其应用

数据结构 实验1：线性表的基本操作及其应用 班级：RB软工移151 学号：201560140140 姓名：袁若飞

实验一线性表 一、实验目的 1、帮助读者复习C++语言程序设计中的知识。 2、熟悉线性表的逻辑结构。 3、熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉链表的操作为侧重点。 二、实验内容 本次实验提供4个题目，每个题目都标有难度系数，*越多难度越大，题目一、二是必做题。题目三、题目四选作。 三、实验准备知识 1、请简述线性表的基本特性和线性表的几种基本操作的机制 ①答：线性表的基本特性是：对线性表中某个元素ai来说，称其前面的元素ai-1为ai的直接前驱，称其后前面的元素ai+1为ai的直接后继。显然，线性表中每个元素最多有一个直接前驱和一个直接后继。 ②答：线性表的几种基本操作的机制有六个： （1）初始化线性表initial_List(L)——建立线性表的初始结构，即建空表。这也是各种结构都可能要用的运算。 （2）求表长度List_length(L)——即求表中的元素个数。 （3）按序号取元素get_element(L,i)——取出表中序号为i的元素。（4）按值查询List_locate(L,x)——取出指定值为x的元素，若存在该元素，则返回其地址；否则，返回一个能指示其不存在的地址值或标记。 （5）插入元素List_insert(L,i,x)——在表L的第i个位置上插入值为x的元素。显然，若表中的元素个数为n，则插入序号i应满足1<=i<=n+1。（6）删除元素List_delete（L，i）——删除表L中序号为i的元素，显然，待删除元素的序号应满足1<=i<=n。 2、掌握线性表的逻辑结构。 3、掌握线性表的链式存储结构。 4、熟练掌握线性表的插入、删除等操作。

第2章线性表习题解答

第2章线性表习题解答

第2章习题 (2) 第2章习题 2.1若将顺序表中记录其长度的分量listlen改为指向最后一个元素的位置last，在实现各基本运算时需要做那些修改？ 【解】 //用线性表最后一个元素的下标last代替listLen实现顺序表 #define MAXLEN 100 typedef int elementType; typedef struct sllLast { elementType data[MAXLEN]; int last; }seqList; //初始化 void initialList(seqList &S)

{ https://www.wendangku.net/doc/b018567204.html,st=-1; } //求表长度 int listLength(seqList S) { return https://www.wendangku.net/doc/b018567204.html,st+1; } //按序号取元素 bool getElement(seqList S,int i,elementType &x) { if(i<1 || i>https://www.wendangku.net/doc/b018567204.html,st+1) //i为元素编号，有效范围在https://www.wendangku.net/doc/b018567204.html,st+1之间 return false; else { x=S.data[i-1];

return true; } } //查找元素x，成功：返回元素编号；失败：返回0 int listLocate(seqList S,elementType x) { int i; for(i=0;i<=https://www.wendangku.net/doc/b018567204.html,st;i++) { if(S.data[i]==x) return i+1; //找到，转换为元素编号输出 } return 0; } //插入元素 int listInsert(seqList &S,elementType x, int i)

实验一线性表与应用(I)

姓名学号

ElemType data; //待插入元素 SqList L; //定义SqList类型变量 InitList_Sq(L); //初始化顺序表 printf("※1. 请输入所需建立的线性表的长度："); scanf_s("%d", &LIST_MAX); printf("※2. 请录入数据："); for (i = 0; i

第二章线性表习题及答案

第二章线性表习题及答案 一、基础知识题 2.1 试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。 答：始结点是指链表中的第一个结点，也就是没有直接前趋的那个结点。 链表的头指针是一指向链表开始结点的指针(没有头结点时)，单链表由头指针唯一确定，因此单链表可以用头指针的名字来命名。 头结点是我们人为地在链表的开始结点之前附加的一个结点。有了头结点之后，头指针指向头结点，不论链表否为空，头指针总是非空。而且头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作一致(都是在某一结点之后)。 2.2 何时选用顺序表、何时选用链表作为线性表的存储结构为宜? 答：在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑： 1.基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。 2.基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。 2.3 在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素? 答：在等概率情况下，顺序表中插入一个结点需平均移动n/2个结点。删除一个结点需平均移动(n-1)/2个结点。具体的移动次数取决于顺序表的长度n以及需插入或删除的位置i。i 越接近n则所需移动的结点数越少。 2.4 为什么在单循环链表中设置尾指针比设置头指针更好? 答：尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next 和rear, 查找时间都是O(1)。 若用头指针来表示该链表，则查找终端结点的时间为O(n)。 2.5 在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?若可以，其时间复杂度各为多少? 答：我们分别讨论三种链表的情况。 1. 单链表。当我们知道指针p指向某结点时，能够根据该指针找到其直接后继，但是由于不知道其头指针，所以无法访问到p指针指向的结点的直接前趋。因此无法删去该结点。 2. 双链表。由于这样的链表提供双向链接，因此根据已知结点可以查找到其直接前趋和直接后继，从而可以删除该结点。其时间复杂度为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;

(完整版)数据结构第二章线性表1答案

（A ）需经常修改L 中的结点值 （E ）需不断对L 进行删除插入 第二部分线性表 、选择题 1 ?关于顺序存储的叙述中，哪一条是不正确的 （B ） A. 存储密度大 B. 逻辑上相邻的结点物理上不必邻接 C. 可以通过计算直接确定第 i 个结点的位置 D. 插入、删除操作不方便 2.长度为n 的单链表连接在长度为 m 的单链表后的算法的时间复杂度为 （C ） A 0（ n ） B 0（1） C 0（m ） D 0（m+n ） 3 .在n 个结点的顺序表中，算法的时间复杂度是 0（1）的操作是：（A ） A 访问第i 个结点（1<=i<=n ）和求第i 个结点的直接前趋（2<=i<=n ) B 在第i 个结点（1<=i<=n ）后插入一个新结点 C 删除第i 个结点（1<=i<=n ) D 将n 个结点从小到大排序 4.一个向量第一个兀素的存储地址是 100 ,每个兀素的长度为 2 ,则第5 个兀素的地址是 (B ) ( A ) 110 ( B ) 108 (C ) 100 ( D ) 120 5 .已知一个顺序存储的线性表， 设每个结点需要占 m 个存储单元，若第一个结点的地址为 da , 则第i 个结点的地址为：（A ） 7 .链表是一种采用（ B ）存储结构存储的线性表。 （A ）顺序 （B ）链式 （C ）星式 （D ）网状 8 .线性表若采用链式存储结构时，要求内存中可用存储单兀的地址： （D ） （A ）必须是连续的 （B ）部分地址必须是连续的 （C ）一定是不连续的 （D ）连续或不连续都可以 9 .线性表L 在_ （ B ）情况下适用于使用链式结构实现。 A ） da+（i-1）*m B ） da+i*m 6.在具有n 个结点的单链表中，实现（ A ）遍历链表和求链表的第 i 个结点 C ）删除开始结点 C ） da-i*m D ） da+（i+1）*m A ）的操作，其算法的时间复杂度为 0（n ）。 B ）在地址为p 的结点之后插入一个结点 D ） 删除地址为p 的结点的后继结点

第2章线性表(课堂作业)

第2章线性表 1．下面关于线性表的叙述中，错误的是哪一个？（）A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 2．线性表是具有n个（）的有限序列（n>0）。 A．表元素 B．字符 C．数据元素 D．数据项 E．信息项 3.线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置 元素的时间复杂性为（） A．O（i） B．O（1） C．O（n） D．O（i-1） 4.若长度为n的线性表采用顺序存储结构，在其第i个位置插 入一个新元素的算法的时间复杂度为（）(1<=i<=n+1)。 A. O(0) B. O(1) C. O(n) D. O(n2) 5. 对于顺序存储的线性表，访问结点和增加、删除结点的时间 复杂度为（）。 A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) 6．对于一个头指针为head的带头结点的单链表，判定该表为空 表的条件是（）

A．head==NULL B．head→next==NULL C．head→next==head D．head!=NULL 7.链表不具有的特点是（） A．可随机访问任一元素 B．插入、删除不需要移动元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比 8.在双向链表指针p的结点前插入一个指针q的结点操作是（）。 >Llink=q;q->Rlink=p;p->Llink->Rlink=q;q->Llink=q； >Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink ; C. q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q; >Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q ; 9.在单链表指针为p的结点之后插入指针为s的结点，正确的 操作是：（）。 A． s->next=p->next;p->next=s; B． p->next=s;s->next=p->next; C．p->next=s;p->next=s->next; D． p->next=s->next;p->next=s; 10．对于一个头指针为head的带头结点的单链表，判定该表为

《数据结构》实验一 线性表及其应用

实验一线性表及其应用 一、实验目的 1.熟悉C语言的上机环境，进一步掌握C语言的结构特点。 2.掌握线性表的顺序存储结构的定义及C语言实现。 3.掌握线性表的链式存储结构——单链表的定义及C语言实现。 4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5.掌握线性表在链式存储结构——单链表中的各种基本操作。 二、实验内容 1.顺序线性表的建立、插入及删除。 2.链式线性表的建立、插入及删除。 三、实验步骤 1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。 2.利用前面的实验先建立一个顺序表L={21，23，14，5，56，17，31}，然后在第i个位置插入元素68。 3.建立一个带头结点的单链表，结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。 四、实现提示 1.由于C语言的数组类型也有随机存取的特点，一维数组的机内表示就是顺序结构。因此，可用C语言的一维数组实现线性表的顺序存储。 在此，我们利用C语言的结构体类型定义顺序表： #define MAXSIZE 1024 typedef int elemtype; /* 线性表中存放整型元素*/ typedef struct { elemtype vec[MAXSIZE]; int len; /* 顺序表的长度*/ }sequenlist; 将此结构定义放在一个头文件sqlist.h里，可避免在后面的参考程序中代码重复书写，另外在该头文件里给出顺序表的建立及常量的定义。 2. 注意如何取到第i个元素，在插入过程中注意溢出情况以及数组的下标与位序（顺序表中元素的次序）的区别。 3.单链表的结点结构除数据域外，还含有一个指针域。用C语言描述结点结构如下： typedef int elemtype; typedef struct node

数据结构《线性表的应用》实验报告

实验报告——线性表应用一、实验目的 用单链表储存一元多项式，并实现两个多项式的相加运算。 二、实验内容 1.先创建链表，存储多项式； 2.输出多项式； 3.两个多项式相加； 4.输出多项式。 三、程序代码 #include #include #include //一元多项式链式储存的节点结构 typedef struct Polynode { float coef; int exp; struct Polynode * next; } Polynode , * Polylist; //建立一元多项式的链表 Polylist polycreate() { Polynode * head,* rear,* s; float c; int e; head=(Polynode* )malloc(sizeof(Polynode)); rear=head; scanf("%f,%d",&c,&e); while(c!=0) { s=(Polynode * )malloc(sizeof(Polynode)); s->coef=c; s->exp=e; rear->next=s; rear=s; scanf("%f,%d",&c,&e); } rear->next=NULL; return(head); } //输出多项式

void print(Polynode*L) { Polynode*p; p=L->next; printf("a="); if(p&&p->coef!=0) printf("%.2f*x^%d",p->coef,p->exp); while(p->next!=NULL) { if((p->next->coef)>0&&p) printf("+"); else printf("-"); p=p->next; printf("%.2f*x^%d",fabs(p->coef),p->exp); } } //多项式相加 void polyadd(Polylist polya,Polylist polyb) { Polynode*p,*q,*tail,*temp; int sum; p=polya->next; q=polyb->next; tail=polya; while (p!=NULL&&q!=NULL) { if(p->expexp) {tail ->next=p; tail=p;p=p->next;} else if (p->exp==q->exp); {sum=p->coef+q->coef; if(sum!=0) {p->coef=sum; tail->next=p;tail=p; p=p->next; temp=q;q=q->next;free(temp); } else { temp=p;p=p->next;free(temp); temp=q;q=q->next;free(temp); } }

数据结构线性表的应用实验报告

实验报告 课程名称____数据结构上机实验__________ 实验项目______线性表的应用____________实验仪器________PC机___________________ 系别_____电子信息与通信学院___ 专业________ ___ 班级/学号______ __ 学生姓名______ ___________ 实验日期_______________________ 成绩_______________________ 指导教师_______________________

实验一.线性表的应用 1.实验目的：掌握线性链表的存储、运算及应用。利用链 表实现一元多项式计算。 2.实验内容： 1)编写函数，实现用链表结构建立多项式； 2)编写函数，实现多项式的加法运算； 3)编写函数，实现多项式的显示； 4)测试：编写主函数，它定义并建立两个多项式，显示 两个多项式，然后将它们相加并显示结果。变换测试用的多项式，检查程序的执行结果。 选做内容：修改程序，选择实现以下功能： 5)多项式求值：编写一个函数，根据给定的x值计算并 返回多项式f(x)的值。测试该函数（从终端输入一个x的值，调用该函数并显示返回结果）。 6)多项式相减：编写一个函数，求两个多项式相减的多 项式。 7)多项式相乘：编写一个函数，求两个多项式的乘积多 项式。 3.算法说明： 1)多项式的建立、显示和相加算法见讲义。可修改显示 函数，使输出的多项式更符合表达规范。

2)多项式减法：同次项的系数相减（缺项的系数是0）。 例如a(x)=-5x2+2x+3，b(x)= -4x3+3x，则a(x)-b(x) =4x3-5x2-x+3。提示：a(x)-b(x) = a(x)+(-b(x))。 3)多项式乘法：两个多项式的相乘是“系数相乘，指数 相加”。算法思想是用一个多项式中的各项分别与另 一个多项式相乘，形成多个多项式，再将它们累加在 一起。例如，a(x)=-5x2+2x+3，b(x)=-4x3+3x，则 a(x)*b(x) = (-4x3)*(-5x2+2x+3)+(3x)*(-5x2+2x+3) = (20x5-8x4-12x3) + (-15x3+6x2+9x) = 20x5-8x4-27x3+6x2+9x。 4.实验步骤： 根据实验报告的要求，我对文件夹里的C文件进行了丰 富和修改，步骤如下： 链表结构建立多项式： typedef struct polynode { float coef; //系数 int exp; //指数 struct polynode *next; //下一结点指针 } PNode; 编写函数，实现多项式的加法运算； PNode * PolyAdd (PNode *f1, PNode *f2) //实现加法功能。

数据结构第二章线性表1习题

线性表专题 一、选择题 1．关于顺序存储的叙述中,哪一条是不正确的( ) A.存储密度大 B.逻辑上相邻的结点物理上不必邻接 C.可以通过计算直接确定第i个结点的位置 D.插入、删除操作不方便 2．长度为n的单链表连接在长度为m的单链表后的算法的时间复杂度为( ) A O(n) B O(1) C O(m) D O(m+n) 3．在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是：( ) A 访问第i个结点（1<=i<=n）和求第i个结点的直接前趋（2<=i<=n） B 在第i个结点（1<=i<=n）后插入一个新结点 C 删除第i个结点（1<=i<=n） D 将n个结点从小到大排序 4．一个向量第一个元素的存储地址是100 ，每个元素的长度为2 ，则第5 个元素的地址是：( ) （A ）110 （ B ）108 （C ）100 （D ）120 5．已知一个顺序存储的线性表，设每个结点需要占m个存储单元，若第一个结点的地址为da，则第i个结点的地址为：( ) A）da+(i-1)*m B) da+i*m C) da-i*m D) da+(i+1)*m 6．在具有n个结点的单链表中，实现（）的操作，其算法的时间复杂度为O(n)。 A）遍历链表和求链表的第i个结点B）在地址为p的结点之后插入一个结点 C）删除开始结点D）删除地址为p的结点的后继结点 7．链表是一种采用（）存储结构存储的线性表。 （ A ）顺序（B ）链式（ C ）星式（D ）网状 8．线性表若采用链式存储结构时，要求内存中可用存储单元的地址：（） （ A ）必须是连续的（ B ）部分地址必须是连续的 （ C ）一定是不连续的（ D ）连续或不连续都可以 9．线性表Ｌ在（）情况下适用于使用链式结构实现。 （Ａ）需经常修改Ｌ中的结点值（Ｂ）需不断对Ｌ进行删除插入 （Ｃ）Ｌ中含有大量的结点（Ｄ）Ｌ中结点结构复杂 10．在长度为n 的顺序表的第i (1≤i≤n+1) 个位置上插入一个元素，元素的移动次数为( )

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

第二章线性表 一、填空题 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））；

线性表的应用举例实验报告(燕山大学)

数据结构实验报告一 题目：线性表的应用举例班级：信息一班 姓名：冯琴琴 学号： 120108010001 得分：

实验一线性表的应用举例 1. 求两个线性表La和Lb的并集 La = La U Lb 2. 已知线性表La和Lb中的数据元素按值非递减有序排列，要求将La和Lb归并成一个新的线性表Lc，且Lc中的数据元素仍按值非递减有序排列。 #include #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -1 const int LIST_INIT_SIZE=100 ;//线性表的初始存储空间 const int LISTINCREMENT= 10 ;//线性表的增量空间 typedef int ElemType ; typedef int Status ; typedef struct { ElemType *elem; int length; int listsize; }Sqlist; Status InitList (Sqlist &L) // 构造一个空的线性表 { L.elem=new ElemType[LIST_INIT_SIZE]; if(L.elem==NULL) return ERROR; L.length=0; L.listsize= LIST_INIT_SIZE; return TRUE; } int ListLength(Sqlist L) { return L.length; } int PutElem(Sqlist &L ) { int i;

第2章线性表习题参考答案

一、选择题 1. D 2. B 3. B 4. B 5. B 6. B 7. D 8. B 9. C 10. B 11. C 12. C 13. B 14. D 15. A 16. B 17. B 18. C 19. A 20. C 21. D 22. A 23. A 24. A 二、填空题 1. 首元素其直接前驱结点的链域的值 2. HL→next =NULL； HL=HL→next 3. 有限、一对一 4. O(1) 随机存取 5. 表中一半表长和该元素在表中的位置 6. 必定不一定 7. O（1） O（n） 8. 前驱结点的地址 O（n） 9. n-i+1 n-i 10. s->left=p p->right 三、判断题 1. × 2. × 3. × 4. × 5. × 6. × 7. √ 8. × 9. × 10. × 11. × 四、简答题 1. 线性表为：（78，50，40，60，34，90） 2. (36, 12, 8, 50, 25, 5, 15) 3. 解答： 尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next和rear, 查找时间都是O(1)。

若用头指针来表示该链表，则查找终端结点的时间为O(n)。 五、编程题 1. 解答：由于在单链表中只给出一个头指针，所以只能用遍历的方法来数单链表中的结点个数了。算法如下： int ListLength ( LinkList L ) { int len=0 ; ListNode *p; p=L; //设该表有头结点 while ( p->next ) { p=p->next; len++; } return len; } 2. int searchmin(linklist l) { int min; int *p; p=l; min=p->data; p=p->next; while (p->next< >nil) { if (min>p->data) min=p->data; p=p->next; } return min; } 3. int searchmax(linklist l) { int max; int *p; p=l; max=p->data; p=p->next; while (p->next< >nil) { if (maxdata) max=p->data; p=p->next; } return max; } 4. 顺序表：要将该表逆置，可以将表中的开始结点与终端结点互换，第二个结点与倒数第二个结点互换，如此反复，就可将整个表逆置了。 算法如下： // 顺序表结构定义同上题 void ReverseList( Seqlist *L) { DataType temp ; //设置临时空间用于存放data int i; for (i=0;i<=L->length/2;i++)//L->length/2为整除运算 { temp = L->data[i]; //交换数据 L -> data[ i ] = L -> data[ L -> length-1-i]; L -> data[ L -> length - 1 - i ] = temp; }