《数据结构》第1-2章练习题——第1-2章(带答案)

一、选择

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、链表不具有的特点是：

A、可随机访问任一个元素        B、插入删除不需要移动元素

C、不必事先估计存储空间        D、所需空间与线性表长度成正比

7、若线性表最常用的操作是存取第i个元素及其前驱的值，则采用（ ）存储方式节省时间

A、单链表    B、双向链表     C、单循环链表    D、顺序表

顺序表可以随机存取

8、设指针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

9、以下说错误的是 （  ）               

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

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

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

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

10、在带头结点的循环链表中，将头指针改设为尾指针(rear)后，其头结点和尾结点的存储位置分别是(  )

A、rear和rear->next->next             B、rear->next 和rear

C、rear->next->next和rear            D、rear和rear->next

11.以下说错误的是  (  )    

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

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

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

D、插入、删除操作在链表上的实现可在O（n）时间内完成

12、循环链表主要优点是（  ）

A、不再需要头指针了                      B、已知某个结点的位置后，能够容易找到它的直接前趋

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

13、以下说法错误的是   （  ）

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

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

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

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

14、以下说法正确的是

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

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

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

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

15、以下说法错误的是  （  ）

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

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

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

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

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

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

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

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

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

17、以下说法正确的是（  ）

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

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

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

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

18、线性表L=(a1,a2,...,ai,...,an),下列说法正确的是(  )

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

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

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

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

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

A、必需是联系的     B、部分地址必须是连续的     C、一定是不连续的    D、连续不连续都可以

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

A、p=rear;rear=rear->next;free(p) B、rear=rear->next;free(rear);

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

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

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

A、使单链表至少有一个结点     B、标示表结点中首结点的位置

C、方便运算的实现             D、说明单链表是线性表的链式存储实现

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

A、Head==Null      B、Head->next==NULL     C、Head->next==Head

23、空的单循环链表L的尾结点*P,满足

A、P->next==NULL B、P==NULL    C、P->next==L D、P==L

24、算法的时间复杂度是指（    ）

A、执行算法程序所需要的时间        B、算法执行过程中所需要的基本运算次数

C、算法程序的长度                    D、算法程序中的指令条数

25、算法的空间复杂度是指（    ）

A、执行算法程序所占的存储空间        B、算法程序中的指令条数

C、算法程序的长度                    D、算法执行过程中所需要的存储空间

26、下列叙述中正确的是（    ）

A、线性表是线性结构                B、栈和队列是非线性结构  

C、线性链表是非线性结构            D、二叉树是线性结构

27、数据的存储结构是指（    ）

A、数据所占的存储空间量               B、数据的逻辑结构在计算机中的表示

C、数据在计算机中的顺序存储方式        D、存储在外存中的数据

28、下列属于线性数据结构的是(  )

  A、队列        B、树         C、图            D、不确定

29、单链表的每个结点中包括一个指针next，它指向该结点的后继结点。现要将指针q指向的新结点插入到指针P指向的单链表结点之后，下面的操作序列中哪一个是正确的？(  )

A、P->next = q->next; q = p->next;    B、P->next = q; q->next = p->next;

C、q->next = p->next; p->next=q;      D、q = p->next; p->next = q->next;

30、在一个单链表中，若删除p所指结点的后续结点，则执行  (  )

A、p->next=p->next->next;        B、p=p->next; p->next=p->next->next;

C、p->next=p->next; D、p=p->next->next;

31、循环链表指(  )

A、最后一个节点的指针域总是指向链表头       B、可以自由膨胀的链表

C、链表含有指向上一级节点的指针域           D、都不是

32、线性表是(  ) 。

A、一个有限序列，可以为空；    B、一个有限序列，不能为空； 

C、一个无限序列，可以为空；    D、一个无序序列，不能为空。

1) (操作系统 答案 A D)

2) (操作系统 答案B) 

3)(数据结构 答案 B)

二、填空题

33、下面程序段的时间复杂度是__ O(n*m)_   

for(i=0;ifor(j=0;jArray[i][j]=0;

34、下面程序段的时间复杂度是____死循环 ____

i=0;

while(i<=n)

i=i*3;

35、在下面程序段中，s=s+p语句的执行次数为  n     ，p*=j语句的执行次数为  n(n+1)/2   ，该程序段的时间复杂度为   O(n2)   。

int i=0,s=0;

while (++i<=n)

 { int p=1;

for (int j=1;j<=i;j++)

p*=j;

    s=s+p   } 

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

  int length_lklist(linklist head)

     /*求表head的长度*/

  {__p=head______;

j=0;

while(p->next!=NULL)

  {__p=p->next____;

   j++;}

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

}

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

  int locate_lklist(lklist head,datatype x)

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

   { p=head;j=0;

while(____p->next!=NULL && p->data!=x __)

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

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

else  return(0);

}

38、以下为单链表按序号查找的运算，分析算法，请在____处填上正确的语句。

  Pointer find_lklist(lklist head,int i)

    { p=head;j=0;

      while(__p->next!=NULL && j { p=p->next; j++; }

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

          else return(NULL);

}

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

  lklist create_lklist()   

/*直接实现的建表算法。*/

{ head=malloc(size);

  p=head;

  scanf(“%f”,&x);

  while(x!=’$’)

    { q=malloc(size);

q->data=x;

p->next=q;

      _ p=q ____;

       scanf(“%f”,&x);

    }

  ___q->next=NULL___;

  return(head);

}

40、循环链表与单链表的区别仅仅在于其尾结点的链域值不是__空（NULL）__，而是一个指向_头指针__的指针。

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

42、一个好的算法应当具有下列好的特性：正确性、（ 可读性 ）、（ 健壮性 ）和效率和低存储需求。

43、采用顺序存储结构的线性表，其每个元素占用Ｌ个单元。第一个元素的地址为Ｎ，则第i个元素的存储位置为（ N+(i-1)*L    ）。

44、数据元素之间的关系在计算机中的表示有两种不同的表示方法，即（ 顺序映像  ）和（ 非顺序映像 ），从而得到两种不同的存储结构（ 顺序存储结构 ）和（ 链式存储结构 ）。

45、带头结点的单链表H为空的条件是_H->next=NULL_。不带头结点的单链表H为空的条件是 H=NULL  

46、非空单循环链表L中*p是尾结点的条件是__p->next=L____。

47、在一个单链表中p所指结点之后插入一个由指针s所指结点，应执行s->next=_p->next__;和p->next=__s_的操作。

48、在一个单链表中p所指结点之前插入一个由指针s所指结点，可依次执行以下操作： s->next=__ p->next _; p->next=s; t=p->data; p->data=__s->data__;  s->data=_t_;

三、判断题

49、在顺序表中取出第i个元素所花费的时间与i成正比  （ X ）

50、线性表的长度是线性表所占用的存储空间的大小  （ X ）

51、已知指针P指向链表L中某结点，执行语句P=P->next不会删除该链表中结点   （ √ ）

52、在带头结点的单循环链表中，任一结点的后继指针均不空  （ √ ）

53、线性表采用链表方式和顺序表方式存储，执行插入和删除运算的时间复杂度都是O(N)，因而两种存储方式的插入、删除运算所花费的时间相同  （ X ）

四、算法设计

带头结点的单链表，其长度存放在头结点的数据域中，设计一算法求倒数第k个结点的值，并且删除该结点。要求：

   （1）用类C语言描述该单链表

   （3）写出解决该问题的类C语言算法过程

类型定义略

算法思路：

1）合法性检查，若不合法，返回error

若合法：2)遍历链表查找倒数第k个结点的前驱结点

3）将倒数第k个结点值保存

4）将倒数第k个结点删除

   Status  del_find(LinkList L,int k,int&e)

   //删除倒数第k个结点，并将该结点的值送到e中返回

{ if(k<1||k>L->data) return error;

i=L->data-k+1;//i为倒数第k个结点的编号

  p=L;j=0;

while(j p=p->next;//查找第i-1个结点

//注意循环条件中没有p->next不为空的条件,原因是不会越界,因为前面已经判断过了.

q=p->next;

e=q->data;

p->next=q->next;

free(q);

return ok;

}