数据结构练习题 第二章 线性表 习题及答案

第二章 线性表

一．名词解释

1. 线性结构 2.数据结构的顺序实现 3.顺序表 4.链表 5.数据结构的链接实现 6. 建表 7.字符串 8.串 9.顺序串 10.链串 二、填空题

1.为了便于讨论，有时将含n(n>=0)个结点的线性结构表示成(a1，a2,??an)，其中每个ai代表一个______。a1称为______结点，an称为______结点，i称为ai在线性表中的________或______。对任意一对相邻结点ai、ai┼1(1<=i

2.为了满足运算的封闭性，通常允许一种逻辑结构出现不含任何结点的情况。不含任何结点的线性结构记为______或______。

3.线性结构的基本特征是:若至少含有一个结点，则除起始结点没有直接______外，其他结点有且仅有一个直接______;除终端结点没有直接______外，其它结点有且仅有一个直接______.

4.所有结点按1对1的邻接关系构成的整体就是______结构。

5.线性表的逻辑结构是______结构。其所含结点的个数称为线性表的______，简称______.

6.表长为O的线性表称为______

7.线性表典型的基本运算包括:______、______、______、______、______、______等六种。

8.顺序表的特点是______。

9.顺序表的类型定义可经编译转换为机器级。假定每个datatype类型的变量占用k(k>=1)个内存单元，其中，b是顺序表的第一个存储结点的第一个单元的内存地址，那么，第i个结点ai的存储地址为______。

10.以下为顺序表的插入运算，分析算法，请在______处填上正确的语句。 Void insert_sqlist(sqlist L，datatype x，int i)

/*将X插入到顺序表L的第i-1个位置*/ { if( L.last == maxsize) error(“表满”)； if((i<1)||(i>L.last+1))error(“非法位置”); for(j=L.last;j>=i;j--)______; L.data[i-1]=x; L.last=L.last+1; }

11.对于顺序表的插入算法insert_sqlist来说，若以结点移动为标准操作，则插入算法的最坏时间复杂性为________，量级是________。插入算法的平均时间复杂性为________，平均时间复杂性量级是________。

12.以下为顺序表的删除运算，分析算法，请在________处填上正确的语句。 void delete_sqlist(sqlist L,int i) /*删除顺序表L中的第i-1个位置上的结点*/

{if((i<1)||(i>L.last))error(“非法位置”)；

for(j=i+1;j=L.last;j++)________; L.last=L.last-1;

}

13.对于顺序表的删除算法delete_sqlist来说，若以结点移动为标准操作，最坏情况时间复杂性及其量级分别是________和________,其平均时间复杂性及其量级分别为________

1

和________。

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

/*在顺序表L中查找第一值等于X的结点。若找到回传该结点序号；否则回传0*/ {________;

while((i≤L.last)&&(L.data[i-1]!=X))i++; if(________)return(i); else return(0); }

15.对于顺序表的定位算法，若以取结点值与参数X的比较为标准操作，平均时间复杂性量级为________。求表长和读表元算法的时间复杂性为________。

16.在顺序表上，求表长运算LENGTH（L）可通过输出________实现，读表元运算 GET（L，i）可通过输出________实现。

17.线性表的常见链式存储结构有________、________和________。

18.单链表表示法的基本思想是用________表示结点间的逻辑关系。 19.所有结点通过指针的链接而组织成________。

20.为了便于实现各种运算，通常在单链表的第一个结点之前增设一个类型相同的结点，称为________，其它结点称为________。

21.在单链表中，表结点中的第一个和最后一个分别称为________和________。头结点的数据域可以不存储________，也可以存放一个________或________。

22.单链表INITIATE（L）的功能是建立一个空表。空表由一个________和一个________组成。

23.INITIATE()的功能是建立一个空表。请在________处填上正确的语句。 lklist initiate_lklist() /*建立一个空表*/

{________________;

________________; return(t);

}

24.以下为求单链表表长的运算，分析算法，请在 ________处填上正确的语句。 int length_lklist(lklist head) /*求表head的长度*/ {________;

j=0;

while(p->next!=NULL) {________________; j++;

}

return(j); /*回传表长*/

}

25.以下为单链表按序号查找的运算，分析算法，请在____处填上正确的语句。 pointer find_lklist(lklist head,int i) { p=head;j=0;

while(________________) { p=p->next; j++; } if(i==j) return(p);

2

else return(NULL);

}

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

/*求表head中第一个值等于x的结点的序号。不存在这种结点时结果为0*/ { p=head;j=0;

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

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

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

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

if(____________________________) { q=________________; p->next=p->next;

free(q); }

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

}

28.以下为单链表的插入运算，分析算法，请在____处填上正确的语句。 void insert_lklist(lklist head,datatype x,int i) /*在表head的第i个位置上插入一个以x为值的新结点*/ { p=find_lklist(head,i-1);

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

else {s=________________;s->data=x; s->next=________________; p->next=s; } }

29.以下为单链表的建表算法，分析算法，请在____处填上正确的语句。 lklist create_lklist1()

/*通过调用initiate_lklist和insert_lklist算法实现的建表算法。假定$是结束标志*/ { ininiate_lklist(head);

i=1;

scanf(“%f”,&x); while(x!=’$’) {________________; ________________; scanf(“%f”,&x); }

return(head); }

该建表算法的时间复杂性约等于____________，其量级为____________。

3

30.以下为单链表的建表算法，分析算法，请在____处填上正确的语句。 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);

}

此算法的量级为________________。

31．除单链表之外，线性表的链式存储结构还有_________和_________等。 32．循环链表与单链表的区别仅仅在于其尾结点的链域值不是_________，而是一个指向_________的指针。

33．在单链表中若在每个结点中增加一个指针域,所含指针指向前驱结点，这样构成的链表中有两个方向不同的链，称为______。

34．C语言规定，字符串常量按______处理，它的值在程序的执行过程中是不能改变的。而串变量与其他变量不一样，不能由______语句对其赋值。

35．含零个字符的串称为______串，用______表示。其他串称为______串。任何串中所含______的个数称为该串的长度。

36．当且仅当两个串的______相等并且各个对应位置上的字符都______时，这两个串相等。一个串中任意个连续字符组成的序列称为该串的______串，该串称为它所有子串的______串。

37．串的顺序存储有两种方法：一种是每个单元只存一个字符，称为______格式，另一种是每个单元存放多个字符，称为______格式。

38．通常将链串中每个存储结点所存储的字符个数称为______。当结点大小大于1时，链串的最后一个结点的各个数据域不一定总能全被字符占满，此时，应在这些未用的数据域里补上______。 三、单向选择题

1．对于线性表基本运算，以下结果是正确的是 ( ) ①初始化INITIATE(L)，引用型运算，其作用是建立一个空表L=Ф . ② 求表长LENGTH(L)，引用型运算，其结果是线性表L的长度

③读表元GET(L,i), 引用型运算。若1<=i<=LENGTH(L),其结果是线性表L的第i个结点； 否则，结果为0

④定位LOCATE(L,X), 引用型运算.若L中存在一个或多个值与X相等的结点，运算结果为这些结点的序号的最大值；否则运算结果为0

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

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

4

2.线性结构中的一个结点代表一个 （ ） ① 数据元素 ② 数据项 ③ 数据 ④ 数据结构

3．顺序表的一个存储结点仅仅存储线性表的一个 （ ） ① 数据元素 ② 数据项 ③ 数据 ④ 数据结构 4．顺序表是线性表的 （ ） ①链式存储结构 ②顺序存储结构 ③ 索引存储结构 ④ 散列存储结构 5.对于顺序表，以下说法错误的是 （ ）

①顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址 ②顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列 ③顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻

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

6.对顺序表上的插入、删除算法的时间复杂性分析来说，通常以（ ）为标准操作 ①条件判断 ②结点移动 ③算术表达式 ④赋值语句

7.对于顺序表的优缺点，以下说法错误的是 （ ） ①无需为表示结点间的逻辑关系而增加额外的存储空间

②可以方便地随机存取表中的任一结点 ③插人和删除运算较方便

④由于顺序表要求占用连续的空间，存储分配只能预先进行(静态分配) ⑤容易造成一部分空间长期闲置而得不到充分利用

8.指针的全部作用就是 （ ） ①指向某常量 ② 指向某变量 ③指向某结点 ④存储某数据

9.除了( ) ，其它任何指针都不能在算法中作为常量出现，也无法显示。 ①头指针 ②尾指针

③指针型变量 ④空指针

10.单链表表示法的基本思想是指针P表示结点间的逻辑关系，则以下说法错误的是（ ） ①任何指针都不能用打印语句输出一个指针型变量的值

②如果要引用(如访问)p所指结点，只需写出p(以后跟域名)即可

③若想修改变量p的值(比如让P指向另一个结点)，则应直接对p赋值

④对于一个指针型变量P的值。只需知道它指的是哪个结点

⑤结点*ｐ是由两个域组成的记录，p->data是一个数据元素，p->next的值是一个指针 11.单链表的一个存储结点包含 （ ） ①数据域或指针域 ②指针域或链域 ③指针域和链域 ④数据域和链域

12.对于单链表表示法，以下说法错误的是 （ ） ①数据域用于存储线性表的一个数据元素

②指针域或链域用于存放一个指向本结点所含数据元素的直接后继所在结点的指针 ③所有数据通过指针的链接而组织成单链表

④NULL称为空指针，它不指向任何结点，只起标志作用

13.对于单链表表示法，以下说法错误的是 （ ） ①指向链表的第一个结点的指针，称为头指针

5

②单链表的每一个结点都被一个指针所指

③任何结点只能通过指向它的指针才能引用 ④终端结点的指针域就为NULL

⑤尾指针变量具标识单链表的作用，故常用尾指针变量来命名单链表

14．有时为了叙述方便，可以对一些概念进行简称，以下说法错误的是 （ ） ①将“指针型变量”简称为“指针” ②将“头指针变量”称为“头指针”

③将“修改某指针型变量的值”称为“修改某指针” ④将“p中指针所指结点”称为“P值”

15．设指针P指向双链表的某一结点，则双链表结构的对称性可用（ ）式来刻画 ① p->prior->next->==p->next->next ② p->prior->prior->==p->next->prior ③ p->prior->next->==p->next->prior ④ p->next->next==p->prior->prior

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

①对循环链表来说，从表中任一结点出发都能通过前后操作而扫描整个循环链表 ②对单链表来说，只有从头结点开始才能扫描表中全部结点 ③双链表的特点是找结点的前趋和后继都很容易

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

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

①real和rear->next->next ②rear->next 和real

③rear->next->next和rear ④rear和rear->next 18.以下说错误的是 ( )

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

②读表元运算在顺序表上只需常数时间O（1）便可实现，因此顺序表是一种随机存取结构 ③在链表上实现读表元运算的平均时间复杂性为O（1）

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

⑤链入、摘除操作在顺序表上的实现，平均时间复杂性为O（n） 19．在串的基本运算中，属于加工型运算的有 （ ）

①EQAL(S,T) ②LENGTH(S) ③CONCAT(S,T) ④REPLACE(S,T,R) ⑤INDEX(S,T) 20. 在串的基本运算中，属于引用型运算的有 （ ）

①ASSIGN(S,T) ②INSERT(S1,i,S2)

③DELETE(S,i,j) ④SUBSTR(S,i,j) ⑤REPLACE(S,T,R) 21．循环链表主要优点是 （ ）

①不再需要头指针了

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

③在进行插入、删除运算时，能更好地保证链表不断开 ④从表中任一结点出发都能扫描到整个链表

22，每种数据结构都具备三个基本操作:插入、删除和查找，这种说法 （ ）

6

①正确 ②错误

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

①数据的物理结构是指数据在计算机内实际的存储形式 ②算法和程序没有区别，所以在数据结构中二者是通用的 ③对链表进行插人和删除操作时，不必移动结点 ④双链表中至多只有一个结点的后继指针为空 24．以下说法正确的是

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

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

低

③在线性表的顺序存储结构中，插人和删除元素时，移动元素的个数与该元素位置有关 ④顺序存储的线性表的插人和删除操作不需要付出很大的代价，因为平均每次操只有近一半的元素需要移动

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

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

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

③由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活 ④线性表的链式存储结构优于顺序存储结构

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

①线性表的元素可以是各种各样的，逻辑上相邻的元素在物理位置上不一定相邻 ②在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻 ③在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻

④线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素 27．以下说法正确的是（ ）

①在单链表中，任何两个元素的存储位置之间都有固定的联系，因为可以从头结点进行查找任何一个元素

②在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构

③顺序存储结构属于静态结构，链式结构属于动态结构 ④顺序存储方式只能用于存储线性结构 28.以下说法正确的是（ ）

①顺序存储方式的优点是存储密度大、且插入、删除运算效率高 ②链表的每个结点中都恰好包含一个指针

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

④顺序存储结构属于静态结构，链式结构属于动态结构 29.下面关于线性表的叙述正确的是( )

①线性表采用顺序存储，必须占用一片连续的存储单元 ②线性表采用顺序存储，便于进行插人和删除操作 ③线性表采用链接存储，不必占用一片连续的存储单元 ④线性表采用链接存储，不便于插人和删除操作 30.线性表L=(a1,a2,...,ai,...,an),下列说法正确的是( )

①每个元素都有一个直接前驱和直接后继 ②线性表中至少要有一个元素

7

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

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

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

①正确 ②不正确 32.设p,q是指针,若p=q,则*p=*q ,这种说法( )

①正确 ②不正确

33.线性表若采用链表存储结构时，要求内存中可用存储单元的地址( )

①必需是联系的 ②部分地址必须是连续的

③一定是不连续的 ④连续不连续都可以

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

①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); 35. 单链表中，增加头结点的目的是为了 ( )

①使单链表至少有一个结点 ②标示表结点中首结点的位置

③方便运算的实现 ④说明单链表是线性表的链式存储实现

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

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

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

③ 不仅数据元素包含的数据项的个数要相同，而且对应数据项的类型要一致 ④ 结点所代表的数据元素有同一特点

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

①Head=Null ②Head->next=NULL ③Head->next=Head 38.非空的单循环链表L的尾结点*P,满足

P->next=NULL P=NULL P->next=L P=L. 39.双向链表结点结构如下：

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

data是存放数据元素的数据域； Rlink是指向后继结点的指针域。

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

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

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

8

P->LLink->Rlink=Q;

P->LLink=Q;

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

①顺序表 ②单链表 ③双链表 ④单循环链表 41．串是任意有限个

①符号构成的集合 ②符号构成的序列 ③字符构成的集合 ④字符构成的序列 四、简答及应用

1． 请用类C语言描述顺序表，并予以解释说明。

2． 请用类C语言描述单链表的类型定义，并予以解释说明。 3． 请用类C语言描述双链表的类型定义，并予以解释说明。 4． 请用类C语言描述顺序串的类型定义。 5． 请用类C语言描述链串的类型定义。

6.叙述以下概念的区别：头指针变量、头指针、头结点、首结点，并说明头指针变量和头结点的作用。

7．有哪些链表可仅由一个尾指针来惟一确定，即从尾指针出发能访问到链表上任何一个结点。 8．简述下列每对术语的区别：

空串和空格串;串变量和串常量;主串和子串;串变量的名字与串变量的值。 9．设有 A=” ”,B=\，C=\，D=\试计算下列运算的结果(注:A+B是CONCAT（A,B）的简写,A=\的 \含有两个空格)。 (a) A+B (b) B+A (c) D+C+B

(d) SUBSTR(B,3,2) (e) SUBSTR(C,1,0) (f) LENGTH(A) (g) LENGTH(D) (h) INDEX(B,D) (i) INDEX(C,\(j) INSERT(D,2,C) (k) INSERT(B,1,A) (l) DELETE(B,2,2) (m) DELETE(B,2,0)

10.已知:S=\。试利用连接、求子串和置换等基本运算，将S转换为T。 五、算法设计

1． 设A=（a1,a2,a3,......an）和B=(b1,b2,.. .,bm)是两个线性表（假定所含数据元素均为整数）。若n=m且ai=bi(i=1,.. .,n),则称A=B;若ai=bi(i=1,.. .,j)且aj+1B。是编写一个比较A和B的算法，当AB是分别输出-1，0或者1。

2，试编写在无头结点的单链表上实现线性表基本运算LOCATE(L,X)、INSERT(L,X，i)和DELETE(L,i)的算法，并和在带头结点的单链表上实现相的算法进行比较。 3．试编写在不带头结点的单链表上实现线性表基本运算LENGTH(L)的算法。

4．假设有两个按数据元素值递增有序排列的线性表A和B，均以单链表作存储结构。编写算

9

法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许值相同）排列的线性表C，并要求利用原表(即A表和B表的)结点空间存放表C。

5．设有线性表A=(a1,a2,.. .,am)和B=(b1,b2,.. .,bn).试写合并A、B为线性表C的算法，使得：

?(a1,b1,...,am,bm,bm?1,bn)当m??n;C=? ?(a1,b1,...,an,bn,an?1,...,am)当m?n;假设A、B均以单链表为存储结构(并且m、n显示保存)。要求C也以单链表为存储结构并利用单链表A、B的结点空间。

6，设线性表存放在向量A[arrsize]的前elenum分量中，且递增有序。试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂性。 7．已知单链表L中的结点是按值非递减有序排列的，试写一算法将值为x的结点插入表L中，使得L仍然有序。

8，试分别以顺序表和单链表作存储结构，各写一个实现线性表的就地(即使用尽可能少的附加空间)逆置的算法，在原表的存储空间内将线性表(a1，a2,.. .,an)逆置为(an,.. .,a2,a1)。 9．假设分别以两个元素值递增有序的线性表A、B表示两个集合(即同一线性表中的元素各不相同)，现要求构成一个新的线性表C，C表示集合A与B的交，且C中元素也递增有序。试分别以顺序表和单链表为存储结构，填写实现上述运算的算法。

10，已知A、B和C为三个元素值递增有序的线性表，现要求对表A作如下运算： 删去那些既在表B中出现又在表C中出现的元素。试分别以两种存储结构(一处种顺序结构，一种链式的)编写实现上述运算的算法。

11．假设在长度大于1的循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点*s的前趋结点。

12．已知一单链表中的数据元素含有三个字符(即:字母字符、数字字符和其它字符)。试编写算法，构造三个循环链表，使每个循环链表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间(头结点可另辟空间)。

13.(Josephus环)任给正整数n、k，按下述方法可得排列1，2，??,n的一个置换:将数字1，2，.. .,n环形排列(如图算法设计题13.所示)，按顺时针方向从1开始 计数；计满K时输出该为之上的数字(并从环中删去该数字)，然后从下一个数字开始继续计数，直到环中所有数字均被输出为止。例如，n=10,k=3时，输出的置换是3，6，9，2，7，1，8，5，10，

4。试编写一算法，对输人的任意正整数n、k，输出相应的置换

14·在双链表上实现线性表的下列基本运算(a)初始化； (b)定位(c)插入(d)删除。 15·设有一双链表，每个结点中除有prior、data和next三个域外，还有一个访问频度域freq，在链表被起用之前，其值均初始化为零。每当在双链表上进行一次LOCATEL，X)运算时，令元素值为X的结点中freq域的值增1，并使此链表中结点保持按访问频度递减的顺序排列，以便使频繁访问的结点总是靠近表头。试编写实现符合上述要求的LOCATE运算的算法。 16·若X和Y是用结点大小为1单链表表示的串，设计一个算法找出X中第一个不在y中出

10

现的字符。

17．在顺序串上实现串的判等运算EQUAL(S,T)。 18．在链串上实现判等运算EQUAL(S,T)。

19．若S和T是用结点大小为1的单链表存储的两个串（S、T为头指针），设计一个算法将串S中首次与串T匹配的子串逆值。

20．用串的其他运算构造串的子串定位运算index。

第二章 参考答案 一、名词解释 （略） 二、填空题 1、结点 起始 终端 序号 位置 前趋 后趋 2、（） ф 3、前趋 前趋 后趋 后趋 4、线性 5、线性 长度 表长 6、空表 7、初始化INITLATE（L） 求表长LENGTH（L） 读表长GET（L，i） 定位LOCATE （L，X） 插入INSERT（L，X，i） 删除DELETE（L，i） 8、逻辑结构中相邻的结点在存储结构中仍相邻 9、b+（i-1）x k 10、L．data[j]=L．data[j-1] 11、n O(n) n/2 O(n) 12、L.data[j-2]=l.data[j-1] 13、n-1 o(n) (n-1)/2 O(n) 14、i=1 i≦L.last 15、O(n) O(1) 16、L.last L.data[i-1] 17、单链表 循环链表 双链表 18、指针 19，单链表 20、头结点 表结点 21、首结点 尾结点 任何信息、特殊标志 表长 22、头结点 头结点 23、t=malloc(size) t->next=NULL 24、p=haed p=p->next 25、(p->next!=NULL)&&(jnext!=NULL)&&(p->data!=x) 27、(p!=NULL)&&(p->next!=NULL) p->next 28、mailloc(size) p->next 29、insert_lklist(head,x,I) I++ n(n-1)/2 O(n2) 30、p=q p->next=NULL O(n) 11

31、单向循环链表（简称循环链表） 双向循环链表（简称双链表） 32、NULL 头结点 33、双链表 三、单项选择题 1、②2、①3、①4、②5、① 6、②7、③8、③9、④10、② 11、④12、③13、⑤14、④15、③ 16、①17、②18、③19、④20、④ 21、④22、223、②24、③25、④ 26、②27、③28、④29、①30、④ 31、②32、②33、④34、④35、③ 36、③37、②38、③39、②40、① 四、简答及应用 1、线性表的数据元素的类型为datatype，则在语言上可用下述类型定义来描述顺序表： const maxsize=顺序表的容量； typedef struct { datatype data[maxsize] int last; }sqlist; sqlist L; 数据域data是一个一维数组，线性表的第1，2??，n个元素分别存放在此数组的第0，1，??，last-1个分量中，数据域last表示线性表当前的长度，而last-1是线性表的终端结点在顺序表中的位置。常数maxsize称为顺序表的容量，从last到maxsize-1为顺序表当前的空闲区（或称备用区）。 Sqlist类型完整地描述了顺序表的组织。L被说明为sqlist类型的变量，即为一顺序表，其表长应写为L.last，而它的终端结点则必须写为 L.data[L.last-1]。 2、假设数据元素的类型为datatype。单链表的类型定义如下： typedef struct node *pointer struct node {datatype data; pointer next; }; typedef pointer lklist; 其中，①ponter是指向struct node类型变量的指针类型;②struct node是结构体类型规定一个结点是由两个域data和next组成的记录，其中data的结点的数据域,next是 12

结点的链域；③lklist与pointer相同类型，用来说明头指针变量的类型，因而lklist也就被用来作为单链表的类型。 3、typedef struct dnode *dpointer; struct dnode {datatype data; dpointer prior,next; } typedaf dpinter dlklist; 链域prior和next分别指向本结点数据域data所含数据元素的直接前趋和直接后继所在的结点。所有结点通过前趋和后继指针链接在一起，再加上起标识作用的头指针，就得到双向循环链表。 4、顺序串的类型定义与顺序表类似，可描述如下： const maxlen=串的最大长度 typedef struct {char ch[maxlen] int curlen; }string 5、链串的类型定义为： const nodesize=用户定义的结点大小; typedef struct node *pointer; struct node {char ch[nodesize] poinernext; } typedef pointer strlist; 当结点大小为1时，可将ch域简单地定义为：char ch 6、head称为头指针变量，该变量的值是指向链表的第一个结点的指针，称为头指针。头指针变量是用于存放头指针的变量。 为了便于实现各种运算，通常在单链表的第一个结点之前增设一个类型相同的结点，称为头结点。其它结点称为表结点。表结点中和第一个和最后一个分别称为首结点和尾结点。

头指针变量的作用：对单链表中任一结点的访问，必须首先根据头指针变量中存放的头指针找到第一个结点，再依次按各结点链域存放的指针顺序往下找，直到找到或找不到。头指针变量具有标识单链表的作用，故常用头指针变量为命名单链表。 头结点的作用：头结点的数据域可以不存储任何信息，也可以存放一个特殊标志或表长。其作用是为了对链表进行操作时，将对第一个结点煌处理和对其它结点的处理统一起来。 7、循环单链表、循环双链表。 ; 五、算法设计 13

1、 分析：(1)当A、B表都不为空时，比较A，B表中各元素对应位置的内容的大小，进而判断A，B的大小。 (2)当A，B表都不为空时，且A，B表中各各元素对应位置的内容相同时，比较A，B的长度，进而判断A，B的大小或是否相等。 const maxsize=顺序表的容量; typedef struct {int data[maxsize] int last; }sqlist; int CMP_sqlist(sqlist A ,sqlist B) { for (i=0;(iB.data[i])return(1); } if(A.last= =B.last) return(0); else if(A.last>B.last) return(1); else return(-1); } 2、(1)定位LOCATE(L，X) 在带头结点类单链表上实现的算法为： int locate_lklist(lklist head,datatype x) /*求表head中第一个值等于x的的序号，不存在这种结点时结果为0*/ {p=head->next;j=1; /*置初值*/ while((p!=NULL)&&(p->data!=x)) {p=p->next;j++}/*未达表结点又未找到值等于X的结点时经，继续扫描*/ if (p->data = =x) return(j); else return(0); } 在无头结点的单链表上实现的算法为： int Wlocate(lklist head,datatype X) /*求表head中第一个值等于x的结点的序号。不存在这种结点时结果为0*/ {p=head; j=1; /*置初值*/ while((p!=NULL)&&(p->data!=x)) {p=p->next;j++}/*未达表结点又未找到值等于X的结点时经，继续扫描*/ if( p->data = =X) return(j); else return(0); 14

} (2)按序号查找find(L,i) 在带头结点的单链表上实现的算法为： pointer find_lklist(lklist head , int i); { j=1; p=head->next; while((j<1)&&(p!=NULL)){p=p->next; j++} if(i= = j) return(p); else return(NULL); } 在无头结点的单链表上实现的算法为： pointer find_lklist(lklist head , int i); { j=1; p=head; while((j<1)&&(p!=NULL)){p=p->next; j++} if(i= = j) return(p); else return(NULL); } (3)、插入INSERT(L，X，i) 在带头结点单链表上实现的算法为： void insert_lklist(lklist head,datatype x,int I) /*在表haed的第i个位置上插入一人以x为值的新结点*/ {p=find_lklist(head,i-1); /*先找第i-1个结点*/ if(p= =NULL)reeor(“不存在第i个位置”)/*若第i-1个结点不存在，退出*/ else{s=malloc(size);s->data=x /*否则生成新结点*/ s->next=p->next /*结点*p在链域值传给结点*s的链域*/ p->next=s; /*修改*p的链域*/ } } 在无头结点的单链表上实现的算法为： void Winsert(lklist head,dataytpe X,int i) /*在表haed的第i个位置上插入一人以x为值的新结点*/ {if(i<=0) error(“i<=0”); else{ s=malloc(size);s->data=X; /*否则生成新结点*/ if(i= =1){s->next=head;head=s;} else{ p=wfind_lklist(lklist head,i-1); if(p= =NULL) error(“i>n+1”); else{s->next=p->next;p->next=s;} } } 15

(4)删除DELDTE(L,i) 在带头结点的单链表上实现的算法为： void delete_lklist(lklist head,int i) /*删除表head的第i个结点*/ {p=find_lklist(head,i-1) /*先找待删结点的直接前驱*/ if((p!==NULL)&&(p->next!=NULL))/*若直接前趋存在且待结点存在*/ (q=p->next; /*q指向待删结点*/ p->next=q->next/*摘除待结点*/; free(q);/*释放已摘除结点q*/ } else error(“不存在第i个结点”)/*否则给出相关信息*/ } 在无头结点的单链表上实现的算法为： void Wdelete(lklist head,int i) /* 删除表head的第i个结点，若该链表仅有一个结点时，赋该结点指针NULL*/ {if(i<=0) error(“I＜＝0” else{if(i= =0){q=head;head=head->next;free(q);} else{p=wfind_lklist(head,i-1);/*找链表head中第i-1结点指针*/ if(p!=NULL)&&(p->next!=NULL) ｛q=p->next; p->next=q->next; free(q);｝ else error(“不存在第I个结点”)； ｝ ｝ ｝ 3、 分析：从第一个结点开始访问，只要是非空计数一次。 Int wlength_lklist(lklist head) /*求表head的长度*/ {p=head;j=0; while(p!=NULL){p=p->next;j++;} return(j); /*回传表长*/ ｝ 4、 设A,B,C均为无头结点单链表 分析：（1）当有序表A，B均非空时，找出两表中元素最小的一个元素，然后将此结点插入到C表中，重复上述步骤。 （2）当A，B两表有一个为空表时，将另一表中元素顺序地插入到C表中。 （3）由于C按递减排序，因此在C表中插入元素时，应始终插入到C表表头。 Lklist Wlink_lklist(lklist A,lklist B) { while((A!=NULL)&&(B!=NULL)) if(A->datadata){p=A;A=A->next;} else 16

p->next=C;C=p; } if(A= =NULL) A=B; while(A!=NULL) {p=A;A=A->next; p->next=C;C=p;} return(C); } 5、 分析：（1）当有序表A、B均非空时，依次分别从A、B表头部取下结点，插入C表中。 （2）当A、B两表有一个为空表时，将非空表插入到C表尾部。 设A，B，C均为带头结点的单链表 lklist HB_lklist(lklist A,lklist B) { C=A; A=A->next;B=B->next; //去除头结点 While((A!=NULL)&&(B!=NULL)) {p->next=A;p=p->next;A=A->next; p->next=B;p=p->next;B=B->next; } if((B= =NULL)&&(A!=NULL)) p->next=A; else if((A= =NULL)&&(B!=NULL)) p->next=B; Return(c); } 6、 分析：从有序表的尾部开始依次取元素与插入元素比较，若大于插入元素，此元素后移一位，再取它前面一个元素重复上述步骤；则将待插入元素插入。 Void CR(datatype A[],datatype X,int elenum) { i=elenum-1; while((i>=0)&&Xnext; while((p!=NULL)&&(p->datanext;}/*查X插入位置q*/ 17

s=malloc(size);s->data=s; } 8、 (1)顺序表 分析：将顺序表的第一个元素与最后一个元素互换，第二个元素与倒数第二个元素互换。 Void NZ_sqlist(sqlist A) {for{i=0;i<((A.last-1)/2);i++} {x=A.data[i]; A.data[i]=A.data[A.last-i-1]; A.data[A.last-i-1]=x; } } (2)单链表 分析：将原单链表的元素依次取出，再插入另一个单链表的头部。 设该单链表为无头结点，s为指向表的第一个结点的指针。 Void NZ_lklist(lklist s) {p=NULL; /*p指向当前结点的前趋结点*/ /*将原单链表的元素依次取出到q*/ /*再插入另一个单链表p的头部*/ while(s!=NULL) { q=s;s=s->next; q->next=p;p=q; } s=p; /*s指向新单链表的第一个结点*/ } 9、 分析：A与B的交是指A与B的相同部分元素，即那些在A中出现又在B中出现的元素。由于A、B是有序表，故从表头开始依次比较当前指针所指元素的值是否相同，若相同，在C表中插入该元素，然后将两个表的指针后移，否则指向较小元素的指针后移。重复上述步骤，直到A，B表中有一个表到表尾。 (1)顺序表 sqlist HDZ_sqlist(sqlist A,sqlist B) { t=0;j=0;k=0; while((t<=A.last-1)&&(j<=B.last-1)) switch{ case A.data[i]B.data[j];j++;break; case A.data[i]= =B.data[j];C.data[k]=A.data[i];k++;i++;j++;break; } C.last=k; Return(c ); } (2)单链表（设带头结点） 18

lklist HDZ_lklist(lklist A,lklist B) { C=initiate_lklist(); r=C;p=A->next;q=B->next:; While ((p!=null)&&(q!=null)) Switch { case p->data data: p=p->next;break; case p->data data: q=q->next;break; case p->data==q->data; s=malloc(size);s->data=p->data; s->next=r->next; r->next=s; r=s; p=p->next;q=q->next; } return(c); } 10.分析：①在有序表B、C中找出相同元素X； ②若X在表A中出现则删除，否则转①； ③重复①②直到B、C表有一个表查找完毕。 （1） 顺序表 void ASBC_sqlist(sqlist A, sqlist B, sqlist C) {I=0;j=0;k=0; while ((jnext;q= A; 19

pb= B ->next;pc= C ->next; while ((pb!=null)&&(pc!=null)) switch { case pb->datadata: pb=pb->next;break; case pb->datadata: pc=pc->next;break; case pb->data= =pc->data:/* B、C中找到相同元素*/ if(pa= =null)return; if (pa->data= =pb->data)/*在 A中存在 B、C 表共有元素，删除*/ {q->next=pa->next; free(pa);pa=q->next;} pb=pb->next;pc=pc->next; } } } 11．分析设置两个指针，分别指向*S及其后继，然后按循环链表特性，顺序往下查找*s的 直接前趋，找到后删除； void DELETE_Xlklist(lklist S) {p=s; q=p->next; while (q->nest!=s) { p=q; q=q->next;} p->next=s; free(q); } 12．分析：在链表L中依次取元素，若取出的元素是字母，把它插入到字母B中，然后在L中删除该元素；若取出的元素是数字，把它插入到数字链D中，然后在L中删除该元素。继续取下一个元素，直到链表的尾部。最后B、D、L中分别存放的是字母字符、数字字符和其它字符。 设原表有头结点、头指针L，新建数字字符链D，字母字符链B，其它字符链R。 void DISM_lklist(lklist L,lklist D,lklist B,lklist R) { D =malloc(size of(int)); D ->next= D; /*建D循环链表头结点*/ B =malloc(sizeof(char)); B ->next= B; /*建B循环链表头结点*/ p= L;q=p->next; while(q!=null) {if((q->data<=’9’)&&(q->data>=’0’)) {p->next=q->next; /*在表L 中摘除q结点*/ q->next= D ->next; D ->next=q; /*将q结点插入D中*/ q=p->next; /*移动q指针*/ } else if (q->data<=’z’)&&(q->data>=’a’)||(q->data<=’z’)&&(q->data>=’a’)) 20

{p->next=q->next; /*在表L中删除q 结点*/ q->next= B ->next; B ->next=q; /*将q结点插入B中*/ q=p->next; /*移动q指针*/ }else {p=q;q=p->next;} /*移动q指针*/ } p->next=L;R=L; /*使R为循环表*/ } 13．分析：使用一维数组，数组下标表示元素的序号，数组值为1表示元素存在，数组 值为0表示此元素不存在。若累加数组的下标大于N，再从1开始继续累加数组值，直到 所有元素都输出。 Void JSP( int n, k, a[n]) {for(I=0;Inext =null; t->prior=null; return(t); } (2)定位（设含头结点） int locate_dlklist (dlklist head, datatype x) /*求表head中第一个值等于x 的结点的序号。不存在这种结点时结果为0 */ {p=head->next;j=1; /*置初值*/ while((p!=null)&&(p->data!=x)) {p=p->next;j++;} /*未达尾结点又未找到值等于x的结点时继续扫描*/ if (p->data = = x) return (j); else return (0); } （3） 插入（设含头结点） void insert_dlklist (dlklist head, datatype x, int I) 21

/*在表head的第I 个位置上插入一个以x为值的新结点*/ {p=head->next; j=1; /*先找第I-1个结点*/ while ((p!=null) &&(jdata=x;/*否则生成新结点*/ s->prior=p; s->next=p->next; p->next->prior=s; p->next=s; } } （4） 删除（设含头结点） void deldtd_dlklist(dlklist head, int I) /*删除表head的第i个结点*/ {p=head->next;j=1; /*先找第i个结点*/ while((p!=null)&&(jnext;j++;} if(I!=j) error(“不存在第I个位置”)/*若第i个结点不存在，退出*/ if(p!=null) /*若直接前趋存在且待删结点存在*/ {p->prior->next=p->next; p->next->prior=p->prior; free(p);/*释放已摘除结点p*/ } else error(“不在存在第I 结点”) /*否则给出相关信息*/ } 15．分析：首先在链表中查找元素值为X的结点，若找到则让freq域的值增1；然后 依次和它的前趋的freq域值比较，若比前freq域值大，和前趋结点位置交换，直到比 前趋结点的freq域值小为止。 Typedef struct dfnode *dfpointer; Struct dfnode {datatype data; int freq; dfpointer prior,next; } typedef dfpointer dflklist; 设该双链表含头结点。 Int LOCATE_dflklist(dflklist L,datatype X) {/*定位值等于X的结点*/ p=L->next; I=1; while ((p!=null)&&(p->data!=X)) 22

{o=p->next; I++;} if ((p->data!=X||(p= = null)) error(“不存在值为X的结点 ”); else { p->freq++; /*令元素值为X的结点中freq域的值增1*/ q=p->prior; while((q!= L)&&(q->freqfreq)) {I=I-1; p->prior->next=p->next; /*摘除p*/ p->next->prior=p->prior; q->prior-prior=q->prior; p->next=q; q->prior=p; q=p->prior; /*q重新指向p的前趋*/ } return(i); } 23

本文来源：https://www.bwwdw.com/article/84xw.html