第二章  线性表

一．名词解释

1.     线性结构  2.数据结构的顺序实现  3.顺序表  4.链表    5.数据结构的链接实现

6. 建表      7.字符串               8.串     9.顺序串  10.链串

二、填空题

1.为了便于讨论，有时将含n(n>=0)个结点的线性结构表示成(a₁，a₂,……a_n)，其中每个a_i代表一个______。a₁称为______结点，a_n称为______结点，i称为a_i在线性表中的________或______。对任意一对相邻结点a_i、a_i┼1(1<=i<n),a_i称为a_i┼1的直接______a_i┼1称为a_i的直接______。

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

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

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

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

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

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

8.顺序表的特点是______。

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

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

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

 

{ 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) 

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

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

  L.last=L.last-1;

}

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

14.以下为顺序表的定位运算，分析算法，请在________处填上正确的语句。

int locate_sqlist(sqlist L,datatype X)

 

{________;

 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)           

    {________;

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

          else return(NULL);

}

26.以下为单链表的定位运算，分析算法，请在____处填上正确的语句。

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

}

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)

   

   { 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()

 

   { ininiate_lklist(head);

i=1;

scanf(“%f”,&x);

while(x!=’$’)

  {________________;

   ________________;

     scanf(“%f”,&x);

}

return(head);

}

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

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

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

  ① 数据元素        ② 数据项        ③ 数据       ④ 数据结构

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

  ① 数据元素        ② 数据项        ③ 数据        ④ 数据结构         

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

  ①链式存储结构     ②顺序存储结构     ③ 索引存储结构      ④ 散列存储结构

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

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

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

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

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

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

  ①条件判断        ②结点移动

  ③算术表达式      ④赋值语句

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

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

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

  ③插人和删除运算较方便

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

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

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

  ①指向某常量        ② 指向某变量

  ③指向某结点        ④存储某数据

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

  ①头指针            ②尾指针

  ③指针型变量        ④空指针

10.单链表表示法的基本思想是指针P表示结点间的逻辑关系，则以下说法错误的是（　　　）

  ①任何指针都不能用打印语句输出一个指针型变量的值

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

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

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

  ⑤结点*ｐ是由两个域组成的记录，p->data是一个数据元素，p->next的值是一个指针

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

  ①数据域或指针域

  ②指针域或链域

  ③指针域和链域

  ④数据域和链域

12.对于单链表表示法，以下说法错误的是　　　　　　　　　（　　　　）

  ①数据域用于存储线性表的一个数据元素

  ②指针域或链域用于存放一个指向本结点所含数据元素的直接后继所在结点的指针

  ③所有数据通过指针的链接而组织成单链表

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

13.对于单链表表示法，以下说法错误的是　　　　　　　　　　（　　　　　）

  ①指向链表的第一个结点的指针，称为头指针

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

  ③任何结点只能通过指向它的指针才能引用

④终端结点的指针域就为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，每种数据结构都具备三个基本操作:插入、删除和查找，这种说法  （  ）

①正确              ②错误

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

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

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

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

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

24．以下说法正确的是

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

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

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

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

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

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

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

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

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

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

①线性表的元素可以是各种各样的，逻辑上相邻的元素在物理位置上不一定相邻

②在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻

③在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻

④线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素

27．以下说法正确的是（  ）

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

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

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

④顺序存储方式只能用于存储线性结构

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

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

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

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

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

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

①线性表采用顺序存储，必须占用一片连续的存储单元

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

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

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

30.线性表L=(a₁,a₂,...,a_i,...,a_n),下列说法正确的是(  )

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

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

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

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

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;

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="mule"，C="old"，D="my",试计算下列运算的结果(注: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,"d")

(j) INSERT(D,2,C)

(k) INSERT(B,1,A)

(l) DELETE(B,2,2)

(m) DELETE(B,2,0)

10.已知:S="(xyz)*",T="(x+z)*y"。试利用连接、求子串和置换等基本运算，将S转换为T。

五、算法设计

1． 设A=（a₁,a₂,a₃,......a_n）和B=(b₁,b₂,.. .,b_m)是两个线性表（假定所含数据元素均为整数）。若n=m且a_i=b_i(i=1,.. .,n),则称A=B;若a_i=b_i(i=1,.. .,j)且a_j+1<b_j+1（j<n<=m）, 则称A<B;在其他情况下均称A>B。是编写一个比较A和B的算法，当A<B,A=B或A>B是分别输出-1，0或者1。

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

3．试编写在不带头结点的单链表上实现线性表基本运算LENGTH(L)的算法。

4．假设有两个按数据元素值递增有序排列的线性表A和B，均以单链表作存储结构。编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许值相同）排列的线性表C，并要求利用原表(即A表和B表的)结点空间存放表C。

5．设有线性表A=(a₁,a₂,.. .,a_m)和B=(b₁,b₂,.. .,b_n).试写合并A、B为线性表C的算法，使得：

C=

假设A、B均以单链表为存储结构(并且m、n显示保存)。要求C也以单链表为存储结构并利用单链表A、B的结点空间。

6，设线性表存放在向量A[arrsize]的前elenum分量中，且递增有序。试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂性。

7．已知单链表L中的结点是按值非递减有序排列的，试写一算法将值为x的结点插入表L中，使得L仍然有序。

8，试分别以顺序表和单链表作存储结构，各写一个实现线性表的就地(即使用尽可能少的附加空间)逆置的算法，在原表的存储空间内将线性表(a₁，a₂,.. .,a_n)逆置为(a_n,.. .,a₂,a₁)。

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中出现的字符。

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

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

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

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