第2章 线性表

1、数据结构第2章 线性表 共55题一、单选1. (1)分     题目ID号：10545     题目难度：容易    在一个长度为n的顺序存储的线性表中，向第i个元素(1ii十1)位量插入一个新元素时，需要从后向前依次后移【1】个元素。       A. ni    B. ni十1   &

2、#160;  C. n一i一1    D. i题目答案：B2. (1)分     题目ID号：10546     题目难度：容易    线性表是【1】。    A. 一个有限序列，可以为空    B. 一个有限序列，不能为空    

3、;C. 一个无限序列，可以为空    D. 一个无序序列，不能为空题目答案：A3. (1)分     题目ID号：10548     题目难度：容易     在一个长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次数为【1】  A. (n十1)2    B. n2 

4、0;  C. n    D. n十l题目答案：C4. (1)分     题目ID号：10549     题目难度：容易    在一个顺序表的表尾插入一个元素的时间复杂度的量级为【1】    A. (n)    B. (1)    

5、C. (n*n)   D. (lbn)题目答案：B5. (1)分     题目ID号：10550     题目难度：容易    单链表的存储密度为【1】    A. 大于1    B. 等于1    C. 小于1   &

6、#160;D. 不能确定题目答案：C题目分析：存储密度=单链表数据项所占空间/结点所占空间结点所占空间由数据项所占空间和存放后继结点地址的链域，所以，存储密度小于1 。6. (4)分     题目ID号：10551     题目难度：难     设单链表中指针p指向结点ai，指针q指着将要插入的新结点x，问：     1 当x插在链表中两个数据元素ai和ai+1之间时

7、，只要先修改【1】后修改【2】     即可。     A.p一nextq            B.p一nextp一>next->next     C.p->next=q->next         D.q一nex

8、tp一next     E.q->nextNULL           F.q一nextp    2 在链表中最后一个结点an之后插入时，只要先修改【3】后修改【4】即可。     A.q一next=p           

9、  B.q一nextp一next     C.p一nextq            D.p一nextq一next     E.qNULL     【1】 A.   B.   C.   D.  

10、; E.     【2】 A.   B.   C.   D.   E.     【3】 A.   B.   C.   D.   E.     【4】 A. &#

11、160; B.   C.   D.   E.题目答案：DABC7. (1)分     题目ID号：10552     题目难度：较难    在一个单链表中，若要在p所指向的结点之后插入一个新结点，则需要相继修改【1】个指针域的值    A. 1    B.&#

12、160;2    C. 3    D. 4题目答案：B8. (1)分     题目ID号：10560     题目难度：容易    顺序表的一个存储结点仅仅存储线性表的一个【1】     A. 数据元素    B. 数据项 

13、60;  C. 数据    D. 数据结构题目答案：A9. (1)分     题目ID号：10564     题目难度：容易    L是顺序表，已知LENGTH(L)的值是5，经运算DELETE(L，2)后LENGTH(L)的值是【1】。    A. 5    B. 0

14、    C. 4    D. 6题目答案：C10. (1)分     题目ID号：10565     题目难度：容易    带头结点的单链表head为空的判断条件是【1】。     A. headNULL       &

15、#160;    B. head一nextNULL     C. head一nexthead    D. head!NULL题目答案：B11. (1)分     题目ID号：10566     题目难度：容易    若某线性表最常用的操作是取第i个元素和找第i个元素的前驱元素，则采取【1】

16、存储方式最节省时间。   A. 单链表    B. 双链表     C. 单向循环链表    D. 顺序表题目答案：D12. (1)分     题目ID号：10567     题目难度：容易    链表不具有的特点是【1】  &#

17、160;  A. 随机访问                  B. 不必事先估计存储空间     C. 插入删除时不需移动元素    D. 所需的空间与线性表成正比题目答案：A13. (1)分     题目ID

18、号：10568     题目难度：难     在一个单链表中，已知q所指结点是p所指结点的直接前驱，若在p、q之间插入s结点，    则执行【1】操作。    A. s一nextp一next;p一nexts;      B. q一nexts;s一nextp;    C. p一nexts一next;s

19、一nextp;      D. p一nexts;s一nextq;题目答案：B14. (1)分     题目ID号：10689     题目难度：容易    线性表是【1】    A. 一个有限序列，可以为空       B. 一个有限序列，不可以为空

20、           C. 一个无限序列，可以为空       D. 一个无限序列，不可以为空题目答案：A15. (1)分     题目ID号：10690     题目难度：容易    顺序表的优点是【1】   

21、0;A. 所需空间随线性表长度的变化而变化    B. 可随机访问指定下标的元素    C. 插人和删除不需要移动元素    D. 不必事先估计存储空间的大小题目答案：B16. (1)分     题目ID号：10693     题目难度：容易    假设对一个线性表很少进行插入、删除操作，

22、但经常要访问其中指定下标的元素。该线性表适合采用的存储方式是【1】    A. 单链表     B. 散列表      C. 顺序表      D. 循环链表题目答案：C17. (1)分     题目ID号：10694     题目难度：容

23、易    线性表采用链式存储时，结点的存储地址【1】    A. 必须是不连续的      B. 连续与否均可    C. 必须是连续的        D. 和头结点的存储地址相连续题目答案：B18. (1)分     题目ID号：1069

24、5     题目难度：容易    线性表采用链式存储时，数据元素的逻辑顺序与在内存中的存储顺序【1】     A. 一致     B. 也可能不一致    C. 完全不一致     D. 有一定的关系题目答案：B19. (1)分   

25、60; 题目ID号：10696     题目难度：容易    以下存储结构中不利于线性表长度变化的是【1】    A. 单链表     B. 顺序表     C. 循环链表     D. 双链表题目答案：B20. (1)分   &

26、#160; 题目ID号：10697     题目难度：容易    用链接方式存储线性表的优点是【1】    A. 便于随机存取指定下标的元素    B. 存储密度高    C. 插入和删除不需要移动元素    D. 可以用元素在存储器中的物理位置表示元素之间的逻辑关系题目答案：C21. (

27、1)分     题目ID号：10698     题目难度：容易    在一个长度为n的顺序表中，向第i个元素(0in)之前插人一个新元素时，需要    向后移动的元素个数为【1】    A. ni   B. ni十1    C. ni一1   D.&

28、#160;i题目答案：A22. (1)分     题目ID号：10699     题目难度：容易    在一个长度为n的顺序表中，删除第i个元素(0in-1)时，需要向前移动的元素个数为【1】    A. ni   B. ni十1    C. n一i一l    D.&#

29、160;i题目答案：C23. (1)分     题目ID号：10700     题目难度：容易    设指针P指向单链表中的结点m，若要删除m之后的一个结点(假设其存在)，则需要执行的修改指针操作为【1】    A. p一nextP        B. p一nextp一next 一next 

30、;   C. pp一next        D. pp一next一next题目答案：B24. (1)分     题目ID号：10701     题目难度：容易    如果对某线性表最常用的操作是取第i个结点及其前驱，则采用【1】存储方式最节省时间。    A. 单链表&

31、#160;   B. 双链表   C. 单循环链表   D. 顺序表题目答案：D25. (1)分     题目ID号：10702     题目难度：容易    对某线性表最常用的操作是：在终端结点之后插入一个结点和删除开始结点，为节省运行时间应采用的存储方式是【1】    A. 

32、单链表          B. 仅有头指针的单循环链表    C. 双链表          D. 仅有尾指针的单循环链表题目答案：D26. (1)分     题目ID号：10703     题目难度：容易 &

33、#160;  与单链表相比，双链表的优点之一是【1】    A. 向前后两个方向顺序访问相邻结点更方便   B. 可以进行随机访问    C. 插人、删除操作更简单                   D. 使用的空间更小题目答案：A27.

34、 (1)分     题目ID号：10704     题目难度：容易    链表不具备的特点是【1】    A. 所需空间随线性表长度的变化而变化    B. 可随机访问指定下标的元素    C. 插入和删除不需要移动元素      

35、0;     D. 不必事先估计存储空间题目答案：B28. (1)分     题目ID号：10720     题目难度：容易    一维数组和线性表的区别是【1】    A. 前者长度间定，后者长度可变      B. 两者长度均可变   

36、 C. 两者长度均固定                  D. 前者长度可变，后者长度固定题目答案：A二、是非1. (6)分     题目ID号：10577     题目难度：容易    【1】顺序表可以方便地随机存取表中的任一元素。

37、60;   【2】顺序表上插入一个数据元素的操作的时间复杂度为(1)。    【3】顺序表中做删除操作时不需移动大量数据元素。    【4】线性表的链式存储结构，表中元素的逻辑顺序与物理顺序一定相同。    【5】对双向链表来说，结点*p的存储位置既存放在其前驱结点的后继指针域中也存放在它的后继结点的前驱指针域中。    【6】在顺序表和单锭表上实现读表元运算的平均时间复杂度均为(1)。题目答案：TFFFT

38、F三、填空1. (6)分     题目ID号：10569     题目难度：容易    一线性表表示如下：(a1，a2，an)，其中每个ai代表一个【1】。a1称为【2】结点，an称为【3】结点，i称为an在线性表中的【4】。对任意一对相邻结点ai，ai+1(1in)，ai称为ai+1的直接【5】，ai+l称为ai的直接【6】。题目答案：数据元素结点】起始】终端】位置】前驱】后继】2. (1)分   

39、60; 题目ID号：10570     题目难度：较难    线性表a的元素长度为4，在顺序存储结构下LOC(a1)1000，则LOC(a3)【1】。题目答案：1008】3. (3)分     题目ID号：10571     题目难度：容易    线性表L(a，b，c，d，e)，经运算DELETE(L，3)后，L【1】，再经过INSERT(L，2，

40、w)运算后，L【2】。调用函数GET(L，3)的结果为【3】。题目答案：(a,b,d,e)】(a,w,b,d,e)】b】4. (1)分     题目ID号：10572     题目难度：容易    在一个长度为n的顺序表中，向第i个元素(1in)之前插入一个新元素时，需向后移动【1】个元素。题目答案：n-i+1】5. (1)分     题目ID号：10573  

41、60;  题目难度：容易    在单链表中除首结点外，任意结点的存储位置都由【1】 结点中的指针指示。题目答案：直接前驱】6. (1)分     题目ID号：10574     题目难度：容易    在单链表中设置头结点的作用是在插入和删除首结点时不必对【1】进行特殊处理。题目答案：头指针】7. (1)分     题目

42、ID号：10575     题目难度：容易    设rear是指向非空、带头结点的循环单链表的尾指针，则该链表第一个数据结点的存储位置是【1】。题目答案：rear->next->next】8. (1)分     题目ID号：10576     题目难度：容易    在带有头结点的单链表L中，若要删除第一个数据结点，则需执行下列三条语句： 

43、;   【1】；     L一nextDel一next；     free(Del)；题目答案：Del=L->next;】9. (2)分     题目ID号：10789     题目难度：较难    Reverse是在单链表类Chain中增加的成员函数，它的功能是在原地实现表元素的反转。  &

44、#160;程序如下：     template<class T>     void Chain<T>:Reverse()       Node<T> *current=head->next,   /指向当前处理的结点         &#

45、160;     *next,                 /指向当前结点的直接后继               *last=0;        

46、       /指向反转后当前结点的直接后继       while(count)          next=current->next;          current->next=last;    &

47、#160;    【1】  =current;         current=next;             【2】  = last;            

48、60;     /last指向反转后链表的开始结点    题目答案：last】head->next】10. (2)分     题目ID号：10790     题目难度：较难    Del是在单链表类Chain中增加的成员函数，其功能是删除单链表中值相同的重复结点。   程序如下：   temp

49、late<class T>   void Chain<T>:Del()     Node<T> *p,*pre,*q;     p=head->next;     while(【1】   )       pre=p;  

50、0;    q=p->next;       while(q!=NULL)         while(q!=NULL&&【2】   )            pre=q;    

51、0;       q=q->next;                  if(q!=NULL)            pre->next=q->next;    

52、0;       delete q;            q=pre->next;                       p=p->next;

53、0;       题目答案：p!=NULL】q->data!=p->data】11. (3)分     题目ID号：10794     题目难度：较难     IsSorted是在单链表类Chain中增加的成员函数，它的功能是检查单链表中元素是否为非递减顺序。如果是，返回true，否则返回false。【1】  【2】  【3】

54、题目答案：next】return false】current->next】12. (2)分     题目ID号：10795     题目难度：较难     已知A、B和C为三个递增有序的线性表，现对A表进行如上操作：删去那些既在B表C表中出现的元素。在以上实现上述操作的函数中，假定线性表以顺序方式存储。【1】 【2】题目答案：j+】b>c】13. (1)分    &

55、#160;题目ID号：11109     题目难度：容易    在一个长度为n的向量中的第i个元素(1in)之前插入一个元素时，需向后移动 【1】个元素。题目答案：n-i+1】14. (1)分     题目ID号：11257     题目难度：较易    设计一个算法，在单链表x中内容为a的结点前插入一个内容为b的结点。 【1】题目答案：p->

56、;link!=NULL】15. (2)分     题目ID号：11258     题目难度：较难     设计一个算法，删除向量中第i个元素。【1】【2】题目答案：nodelistith】nodelisti+1】四、问答1. (2)分     题目ID号：10578     题目难度：容易    试

57、述顺序表的优缺点。题目答案：顺序表的优点：便于随机存取；存储空间连续，不必增加额外的存储空间。顺序表的缺点：插入和删除操作要移动大量数据元素，存储单元的分配要预先进行。2. (3)分     题目ID号：10745     题目难度：容易    如果一个线性表中元素的总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取表中指定位置的元素，对该线性表应选用何种存储结构?为什么?题目答案：    应选

58、用顺序存储结构。    因为，在以顺序方式存储线性表时，线性表中元素的存储顺序与逻辑顺序相一致，根据元素的下标可以很快地找到它的存储位置。3. (2)分     题目ID号：10747     题目难度：容易    单链表中设置头结点的作用是什么?题目答案：设置头结点后，由于头指针总是指向头结点，所以在实现对单链表的操作时不必区分空表和非空表，对开始结点的操作与对其他结点的操作也相同，这样，可简化处理。4.

59、 (2)分     题目ID号：11143     题目难度：容易单链表中设置头结点的作用是什么?【1】题目答案：设置头结点后，由于头指针总是指向头结点，所以在实现对单链表的操作时不必区分空表和非空表，对开始结点的操作与对其他结点的操作也相同，这样，可简化处理。5. (2)分     题目ID号：11667     题目难度：容易    

60、设n个人围坐在一个圆桌周围，现在从第s个人开始报数，数到第m个人，让他出局；然后从出局的下一个人重新开始报数，数到第m个人，再让他出局，如此反复直到所有的人全部出局为止。下面要解决的Josephus问题是：对于任意给定的n, s和m，求出这n个人的出局序列。请以n = 9, s = 1, m = 5为例，人工模拟Josephus的求解过程以求得问题的解。题目答案：出局人的顺序为5, 1, 7, 4, 3, 6, 9, 2, 8

61、。6. (1)分     题目ID号：11668     题目难度：容易    试编写一个求解Josephus问题的函数。用整数序列1, 2, 3, , n表示顺序围坐在圆桌周围的人，并采用数组表示作为求解过程中使用的数据结构。然后使用n = 9, s = 1, m = 5，以及n = 9, s&#

62、160;= 1, m = 0，或者n = 9, s = 1, m = 10作为输入数据，检查你的程序的正确性和健壮性。最后分析所完成算法的时间复杂度。题目答案：【解答】函数源程序清单如下：    void Josephus( int A , int n, s, m ) int i, j, k, tm

63、p;if ( m = 0 )             cout << "m = 0是无效的参数！" << endl;            return;   

64、60;              for ( i = 0; i < n; i+ ) Ai = i + 1; /*初始化，执行n次*/i = s - 1; /*报名起始位置*/for ( k = n; k >&

65、#160;1; i- )  /*逐个出局，执行n-1次*/              if ( i = k ) i = 0;     i = ( i + m - 1 ) % k; /*寻找出局位置*/

66、              if ( i != k-1 )                    tmp = Ai;    /*出局者交换到第k-1位置*/&#

67、160;         for ( j = i; j < k-1; j+ ) Aj = Aj+1; Ak-1 = tmp;     for ( k = 0; k < n / 2; k+ 

68、)  /*全部逆置, 得到出局序列*/               tmp = Ak; Ak = An-k+1; An-k+1 = tmp;     7. (2)分     题目ID号：11669   

69、0; 题目难度：容易    设有一个线性表 (e0, e1, , en-2, en-1) 存放在一个一维数组AarraySize中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前n个原址内容置换为 (en-1, en-2, , e1, e0)。题目答案：【解答】template<class Type> void inverse ( Type A

70、 , int n ) Type tmp;for ( int i = 0; i <= ( n-1 ) / 2; i+ ) tmp = Ai;  Ai = An-i-1;  An-i-1 = tmp;8. (4)分     题目

71、ID号：11671     题目难度：容易    设ha和hb分别是两个带表头结点的非递减有序单链表的表头指针, 试设计一个算法, 将这两个有序链表合并成一个非递增有序的单链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中允许有重复的数据。题目答案：见ftp部分习题答案9. (3)分     题目ID号：11672     题目难度：较难

72、     设有一个表头指针为h的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转，如下图所示。要求逆转结果链表的表头指针h指向原链表的最后一个结点。题目答案：【解答1】  template<class Type> void List<Type> : Inverse ( )       if ( first = 

73、NULL ) return;      ListNode<Type> *p = firstlink;, *pr = NULL;      while ( p != NULL ) firstlink = pr; /逆转first指针      

74、60;  pr = first;  first = p;  p = plink; /指针前移        【解答2】  template<class Type> void List<Type> : Inverse ( )     &#

75、160; ListNode<Type> *p, *head = new ListNode<Type> ( );      while ( first != NULL ) p = first;  first = firstlink; /摘下first链头结点     

76、    plink = headlink;  headlink = p; /插入head链前端            first = headlink;  delete head; /重置first  10. (1)分     题目ID号：11673

77、     题目难度：容易     从左到右及从右到左遍历一个单链表是可能的，其方法是在从左向右遍历的过程中将连接方向逆转，如右图所示。在图中的指针p指向当前正在访问的结点，指针pr指向指针p所指结点的左侧的结点。此时，指针p所指结点左侧的所有结点的链接方向都已逆转。    (1) 编写一个算法，从任一给定的位置(pr, p)开始，将指针p右移k个结点。如果p移出链表，则将p置为0，并让pr停留在链表最右边的结点上。  

78、0; (2) 编写一个算法，从任一给定的位置(pr, p)开始，将指针p左移k个结点。如果p移出链表，则将p置为0，并让pr停留在链表最左边的结点上。题目答案：【解答】  (1) 指针p右移k个结点  template<class Type> void List<Type> :  siftToRight ( ListNode<Type> *& p, ListNod

79、e<Type> *& pr, int k )       if ( p = NULL && pr != first )  /已经在链的最右端        cout << "已经在链的最右端，不能再右移。"

80、60;<< endl;        return;            int i;  ListNode<Type> *q;      if ( p = NULL ) /从链头开始  

81、0;      i = 1;  pr = NULL;  p = first;  /重置p到链头也算一次右移      else i = 0;      while ( p != NULL && i

82、0;< k )  /右移k个结点          q = plink;  plink = pr; /链指针plink逆转指向pr          pr = p;  p = q;  i+; /指针pr, p右移&

83、#160;           cout << "右移了" << i << "个结点。" << endl;    (2) 指针p左移k个结点  template<class Type> void List<

84、;Type> :  siftToLeft ( ListNode<Type> *& p, ListNode<Type> *& pr, int k )       if ( p = NULL && pr = first )   /已

85、经在链的最左端         cout << "已经在链的最左端，不能再左移。" << endl;         return;            int i = 0; 

86、; ListNode<Type> *q;      while ( pr != NULL && i < k )   /左移k个结点         q = prlink;  prlink = p;  

87、60;     /链指针prlink逆转指向p         p = pr;  pr = q;  i+; /指针pr, p左移            cout << "左移了" <

88、< i << "个结点。" << endl;      if ( i < k )  pr = p;  p = NULL;  /指针p移出表外，重置p, pr  11. (3)分     题目ID号：116

89、75     题目难度：容易    试设计一个实现下述要求的Locate运算的函数。设有一个带表头结点的双向链表L，每个结点有4个数据成员：指向前驱结点的指针prior、指向后继结点的指针next、存放数据的成员data和访问频度freq。所有结点的freq初始时都为0。每当在链表上进行一次Locate (L, x)操作时，令元素值为x的结点的访问频度freq加1，并将该结点前移，链接到与它的访问频度相等的结点后面，使得链表中所有结点保持按访问频度递减的顺序排列，以使频繁访问的结点总是靠近表头。题目答案：【解答】  #include <iostream.h>  /双向循环链表结点的构造函数  DblNode (Type value, DblNode<Type> *left,&