精华内容
下载资源
问答
  • 下述哪一条是顺序存储结构的优点 北方交通大学2001 一4 2分 存储密度大 B ?插入运算方便 C ?删 除运算方便D .可方便地用于各种逻辑结构的 存储表示 下面关于线性表的叙述中错误的是哪 一个 北方交通大学2001 一14 2 ...
  • 1.下述哪一条是顺序存储结构的优点?( A ) A.存储密度大 B.插入运算方便 C.删除运算方便 D.可方便地用于各种逻辑结构的存储表示 2.下面关于线性表的叙述中,错误的是哪一个?(B ) A.线性表采用顺序...

    第2章    线性表

    一  选择题

    1.下述哪一条是顺序存储结构的优点?( 

    A.存储密度大  B.插入运算方便  C.删除运算方便  D.可方便用于各种逻辑结构的存储表示

    2.下面关于线性表的叙述中,错误的是哪一个?(B    )

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

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

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

    D.线性表采用链接存储,便于插入和删除操作。

    3.线性表是具有n个(   C )的有限序列(n>0)。

    A.表元素      B.字符      C.数据元素     D.数据项         E.信息项

    4.若某线性表最常用的操作是存取任指定序号的元素和在最后进行插入和删除运算,则利用( A   )存储方式最节省时间。

    A.顺序表      B.双链表        C.带头结点的双循环链表     D.单循环链表

    5.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用(    D)存储方式最节省运算时间。

    A.单链表     B.仅有头指针的单循环链表     C.双链表       D.仅有尾指针的单循环链表

    6.设一个链表最常用的操作是在末尾插入结点和删除尾结点,则选用( D   )最节省时间。

    A. 单链表   B.单循环链表   C. 带尾指针的单循环链表   D.带头结点的双循环链表

    7.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用(  )存储方式最节省运算时间。

    A.单链表      B.双链表     C.单循环链表     D.带头结点的双循环链表

    8. 静态链表中指针表示的是(  C  )

    A 内存地址       B数组下标     C下一元素地址      D右孩子地址

    9. 链表不具有的特点是(   B

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

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

    10. 下面的叙述不正确的是(   B

    A.线性表在链式存储时,查找第i个元素的时间同i的值成正比

        B. 线性表在链式存储时,查找第i个元素的时间同i的值无关

    C. 线性表在顺序存储时,查找第i个元素的时间同i 的值成正比

    D. 线性表在顺序存储时,查找第i个元素的时间同i的值无关

    11. 线性表的表元存储方式有((1))和链接两种。试指出下列各表中使用的是何种存储方式:表1是((2))存储方式;表2是((3))存储方式;表3是((4))存储方式;表4是((5))存储方式。表左的s指向起始表元。                                                                    

    表元编号

    货号

    数量

    表元间联系

    1

       618

       40

       2

        2

       205

       2

       3

        3

       103

       15

       4

        4

       501

       20

       5

        5

       781

       17

       6

        6

       910

       24

       0

    表1

    s→
                                                  

    表元编号

    货号

    数量

    表元间联系

         1

       618

       40

       5

         2

       205

       2

       1

         3

       103

       15

       4

         4

       501

       20

       2

         5

       781

       17

       6

         6

       910

       24

       3

    表2

     

     

    s→
                                            

    表元编号

    货号

    数量

    表元间联系

         1

       618

       40

       5

         2

       205

       2

       1

    3

       103

       15

       4

         4

       501

       20

       0

         5

       781

       17

       6

         6

       910

       24

       3

    表3

     

    s→           
                                          

    表元编号

    货号

    数量

    表元间联系

     1

     2

         1

       618

       40

     5  

     2

         2

       205

       2

     1

     0

         3

       103

       15

     4

     6

         4

       501

       20

     0

     3

         5

       781

       17

     6

     1

         6

       910

       24

     3

     5

    表4

     

     

    s→
       供选择的答案:

    A.连续  B.单向链接  C.双向链接   D.不连接  E.循环链接

    F.树状   G.网状   H.随机  I.顺序  J.顺序循环

    (1)I(2)I(3)E(4)B(5)C

    12.(1) 静态链表既有顺序存储的优点,又有动态链表的优点。所以它存取表中第i个元素的时间与i无关。

       (2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了,以后不能增加。

       (3) 静态链表与动态链表在元素的插入、删除上类似,不需做元素的移动。

    以上错误的是(  )

     A.(1),(2)      B.(1)       C.(1),(2),(3)      D.(2)

    13. 若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新元素的算法的时间复杂度为(  C  )(1<=i<=n+1)。

    A. O(0)      B. O(1)         C. O(n)          D. O(n2)

    14. 对于顺序存储的线性表,访问结点和增加、删除结点的时间复杂度为(  C  )。

    A.O(n)  O(n)      B. O(n)  O(1)       C. O(1)  O(n)        D. O(1) O(1)

    15.线性表( a1,a2,…,an)以链接方式存储时,访问第i位置元素的时间复杂性为(  C  )

    A.O(i)      B.O(1)      C.O(n)       D.O(i-1)

    展开全文
  • 数据结构【线性表】复习题

    千次阅读 2011-12-20 20:14:53
    1.下述哪一条是顺序存储结构的优点?( A ) A.存储密度大 B.插入运算方便 C.删除运算方便 D.可方便地用于各种逻辑结构的存储表示 2.下面关于线性表的叙述中,错误的是哪一个?( B ) A.线性表采用...

    第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  )存储方式最节省时间。

    A.顺序表      B.双链表        C.带头结点的双循环链表     D.单循环链表

    5.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用(  D  )存储方式最节省运算时间。

    A.单链表     B.仅有头指针的单循环链表     C.双链表       D.仅有尾指针的单循环链表

    6.设一个链表最常用的操作是在末尾插入结点和删除尾结点,则选用(  D  )最节省时间。

    A. 单链表   B.单循环链表   C. 带尾指针的单循环链表   D.带头结点的双循环链表

    7.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用(  D  )存储方式最节省运算时间。

    A.单链表      B.双链表     C.单循环链表     D.带头结点的双循环链表

    8. 静态链表中指针表示的是(  BC  ).

    A. 内存地址       B.数组下标     C.下一元素地址      D.左、右孩子地址

    9. 链表不具有的特点是(  C  )

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

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

    10. 下面的叙述不正确的是( BC   )

    A.线性表在链式存储时,查找第i个元素的时间同i的值成正比

        B. 线性表在链式存储时,查找第i个元素的时间同i的值无关

    C. 线性表在顺序存储时,查找第i个元素的时间同i 的值成正比

    D. 线性表在顺序存储时,查找第i个元素的时间同i的值无关

    11. 线性表的表元存储方式有(顺序)和链接两种。试指出下列各表中使用的是何种存储方式:表1是(顺序)存储方式;表2是(循环链接)存储方式;表3是(单向链接)存储方式;表4是(双向链接)存储方式。表左的s指向起始表元。                                                                    

    表元编号 货号 数量 表元间联系
    1 618· 40 2
    2 205 2 3
    3 103 15 4
    4 501 20 5
    5 781 17 6
    6 901 24 0

    表1

    s→
                                                  

    表元编号 货号 数量 表元间联系
    1 618· 40 5
    2 205 2 1
    3 103 15 4
    4 501 20 2
    5 781 17 6
    6 901 24 3

    表2

     s→
                                           

    表元编号 货号 数量 表元间联系
    1 618· 40 5
    2 205 2 1
    3 103 15 6
    4 501 20 0
    5 781 17 4
    6 901 24 3

    表3

     s—>
                                         

    表元编号 货号 数量

    表元间联系

    1         2

    1 618· 40 5         2
    2 205 2 1         0
    3 103 15 4         6
    4 501 20 0         3
    5 781 17 6          1
    6 901 24 3          5

    表4

    s→
       供选择的答案:

    A.连续  B.单向链接  C.双向链接   D.不连接  E.循环链接

    F.树状   G.网状   H.随机  I.顺序  J.顺序循环

    12.(1) 静态链表既有顺序存储的优点,又有动态链表的优点。所以,它存取表中第i个元素的时间与i无关。

       (2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了,以后不能增加。

       (3) 静态链表与动态链表在元素的插入、删除上类似,不需做元素的移动。

    以上错误的是(  B  )

     A.(1),(2)      B.(1)       C.(1),(2),(3)      D.(2)

    13. 若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新元素的算法的时间复杂度为(  C  )(1<=i<=n+1)。

    A. O(0)      B. O(1)         C. O(n)          D. O(n2)

    14. 对于顺序存储的线性表,访问结点和增加、删除结点的时间复杂度为(  C  )。

    A.O(n)  O(n)     B. O(n)  O(1)       C. O(1)  O(n)        D. O(1) O(1)

    15.线性表( a1,a2,…,an)以链接方式存储时,访问第i位置元素的时间复杂性为( C   )

    A.O(i)     B.O(1)      C.O(n)       D.O(i-1)

    16.非空的循环单链表head的尾结点p满足( A   )。

    A.p.link=head       B.p.link=NIL         C.p=NIL     D.p= head

    17.循环链表H的尾结点P的特点是(  A  )。

        A.P.NEXT=H         B.P.NEXT= H.NEXT        C.P=H      D.P=H.NEXT

    18.在一个以 h 为头的单循环链中,p 指针指向链尾的条件是(A)

     A. p.next=h    B. p.next=NIL  C. p^.next.^next=h   D. p^.data=-1

    二、判断

    1. 链表中的头结点仅起到标识的作用。(  × )

    2. 顺序存储结构的主要缺点是不利于插入或删除操作。(√ )

    3.线性表采用链表存储时,结点和结点内部的存储空间可以是不连续的。(  √  )

    4.顺序存储方式插入和删除时效率太低,因此它不如链式存储方式好。(  × )

    5. 对任何数据结构链式存储结构一定优于顺序存储结构。(× )

     6.顺序存储方式只能用于存储线性结构。(  ×  )

    7.集合与线性表的区别在于是否按关键字排序。( ×  )

    8. 所谓静态链表就是一直不发生变化的链表。( ×  )

    9. 线性表的特点是每个元素都有一个前驱和一个后继。( ×  )

    10. 取线性表的第i个元素的时间同i的大小有关. (  ×  )

    11. 循环链表不是线性表. (  ×  )

    12. 线性表只能用顺序存储结构实现。(  × )

    13. 线性表就是顺序存储的表。(  ×  )

    14.为了很方便的插入和删除数据,可以使用双向链表存放数据。(  √  )

    15. 顺序存储方式的优点是存储密度大,且插入、删除运算效率高。(  ×  )

    16. 链表是采用链式存储结构的线性表,进行插入、删除操作时,在链表中比在顺序存储结构中效率高。 (  √ ) 

     

    三、填空

    1.当线性表的元素总数基本稳定,且很少进行插入和删除操作,但要求以最快的速度存取线性表中的元素时,应采用____顺序___存储结构。

    2.线性表L=(a1,a2,…,an)用数组表示,假定删除表中任一元素的概率相同,则删除一个元素平均需要移动元素的个数是____n-1/2____。

    3.设单链表的结点结构为(data,next),next为指针域,已知指针px指向单链表中data为x的结点,指针py指向data为y的新结点 , 若将结点y插入结点x之后,则需要执行以下语句:___py->next=px->next___; ____px->next=py__;

    4.在一个长度为n的顺序表中第i个元素(1<=i<=n)之前插入一个元素时,需向后移动____n-i+1____个元素。

    5.在单链表中设置头结点的作用是___主要是使插入和删除等操作统一,在第一个元素之前插入元素和删除第一个结点不必另作判断。另外,不论链表是否为空,链表指针不变。_____。

    6.对于一个具有n个结点的单链表,在已知的结点*p后插入一个新结点的时间复杂度为___o(1)_____,在给定值为x的结点后插入一个新结点的时间复杂度为___O(n)_____。

    7.根据线性表的链式存储结构中每一个结点包含的指针个数,将线性链表分成___单链表_____和___多重链表____;而又根据指针的连接方式,链表又可分成____动态链表____和___静态链表_____。

    8. 在双向循环链表中,向p所指的结点之后插入指针f所指的结点,其操作是____f->next=p->next;___、___f->next=p;____、___p->next->prior=f;____、____p->next=f;____。

    10.链接存储的特点是利用____指针____来表示数据元素之间的逻辑关系。

    11.顺序存储结构是通过____物理上相邻____表示元素之间的关系的;链式存储结构是通过_____指针___表示元素之间的关系的。

    12. 对于双向链表,在两个结点之间插入一个新结点需修改的指针共 ___4___个,单链表为____2___个。

    13. 循环单链表的最大优点是:____从任一结点出发都可访问到链表中每一个元素____。

    14. 已知指针p指向单链表L中的某结点,则删除其后继结点的语句是:___q=p->next; p->next=q->next;delete q;_____

    15. 带头结点的双循环链表L中只有一个元素结点的条件是:___ L->next->next==L  或者L->next->prior==L 或者L->prior->next==L或者L->prior->prior==L_____

    16. 在单链表L中,指针p所指结点有后继结点的条件是:__ p->next!=null  

    17.带头结点的双循环链表L为空表的条件是:____ L->next==L &&L->prior==L ____。

    18. 在单链表p结点之后插入s结点的操作是:__ s->next=p->next;p->next=s _____。

     

    四  应用题

    1.线性表有两种存储结构:一是顺序表,二是链表。试问:

    (1)如果有 n个线性表同时并存,并且在处理过程中各表的长度会动态变化,线性表的总数也会自动地改变。在此情况下,应选用哪种存储结构? 为什么?

    答:选链式存储结构,它可动态申请内存空间,不受长度(即表中元素个数)的影响,插入、删除复杂度为O(1)

    (2)若线性表的总数基本稳定,且很少进行插入和删除,但要求以最快的速度存取线性表中的元素,那么应采用哪种存储结构?为什么?

        答:选取顺序结构,顺序表可以随机存取,时间复杂度为O(1)。

     

    2.线性表的顺序存储结构具有三个弱点:其一,在作插入或删除操作时,需移动大量元素;其二,由于难以估计,必须预先分配较大的空间,往往使存储空间不能得到充分利用;其三,表的容量难以扩充。线性表的链式存储结构是否一定都能够克服上述三个弱点,试讨论之。

    答:链式存储结构一般说克服了顺序存储结构的三个弱点。首先,插入、删除不需移动元素,只修改指针,时间复杂度为O(1);其次,不需要预先分配空间,可根据需要动态申请空间;其三,表容量只受可用内存空间的限制。其缺点是因为指针增加了空间开销,当空间不允许时,就不能克服顺序存储的缺点。

     

    3.若较频繁地对一个线性表进行插入和删除操作,该线性表宜采用何种存储结构?为什么?

    答:采用链式存储结构,它根据实际需要申请内存空间,而当不需要时又可将不用结点空间返还给系统。在链式存储结构中插入和删除操作不需要移动元素。

     

    4.线性结构包括___线性表___、______、___队列____和_______。线性表的存储结构分成___顺序存储结构___和____链式存储结构__。

     

    5.线性表(a1,a2,…,an)用顺序映射表示时,ai和ai+1(1<=i<n〉的物理位置相邻吗?链接表示时呢?

    答:顺序映射时,ai与ai+1的物理位置相邻;链表表示时ai与ai+1的物理位置不要求相邻。

     

    6. 说明在线性表的链式存储结构中,头指针与头结点之间的根本区别;头结点与首元结点的关系。

    答:在线性表的链式存储结构中,头指针指链表的指针,若链表有头结点则是链表的头结点的指针,头指针具有标识作用,故常用头指针冠以链表的名字。头结点是为了操作的统一、方便而设立的,放在第一元素结点之前,其数据域一般无意义(当然有些情况下也可存放链表的长度、用做监视哨等等),有头结点后,对在第一元素结点前插入结点和删除第一结点,其操作与对其它结点的操作统一了。而且无论链表是否为空,头指针均不为空。首元结点也就是第一元素结点,它是头结点后边的第一个结点。

     

    7. 在单链表和双向链表中,能否从当前结点出发访问到任何一个结点?

    答:在单链表中不能从当前结点(若当前结点不是第一结点)出发访问到任何一个结点,链表只能从头指针开始,访问到链表中每个结点。在双链表中求前驱和后继都容易,从当前结点向前到第一结点,向后到最后结点,可以访问到任何一个结点。

     

    8. 如何通过改链的方法,把一个单向链表变成一个与原来链接方向相反的单向链表?

    答:链表逆置问题。设该链表带头结点,将头结点摘下,并将其指针域置空。然后从第一元素结点开始,直到最后一个结点为止,依次前插入头结点的后面,则实现了链表的逆置。

     

    展开全文
  • 经典数据结构习题集含标准答案 PAGE PAGE 1 作者 日期 线性表 1....下述哪一条是顺序存储结构的优点A A存储密度大 B插入方便 C删除方便 D可方便地用于各种逻辑结构的存储表示 3.在一个长度为n的顺序表
  • 数据结构习题——第二章 线性表

    万次阅读 多人点赞 2013-09-08 22:40:28
    1.下述哪一条是顺序存储结构的优点?( ) A.存储密度大 B.插入运算方便 C.删除运算方便 D.可方便地用于各种逻辑结构的存储表示 2.下面关于线性表的叙述中,错误的是哪一个?( ) A.线性表采用顺序存储,...

    整理自己学习过程中接触的习题,不断更新中。答案在每个部分后面。

    第一部分:

    第二章 线性表

    一、选择题

    1.下述哪一条是顺序存储结构的优点?( )

    A.存储密度大 B.插入运算方便 C.删除运算方便 D.可方便地用于各种逻辑结构的存储表示

    2.下面关于线性表的叙述中,错误的是哪一个?( )

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

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

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

    D.线性表采用链接存储,便于插入和删除操作。

    3.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则利用( )存储方式最节省时间。

    A.顺序表 B.双链表 C.带头结点的双循环链表D.单循环链表

    4.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用( )存储方式最节省运算时间。

    A.单链表 B.仅有头指针的单循环链表C.双链表 D.仅有尾指针的单循环链表

    5.在一个长度为n的顺序表中删除第i个元素(0<=i<=n)时,需向前移动( )个元素

    A.n-i            B.n-i+l         C.n-i-1         D.i

    6.从一个具有n个结点的单链表中查找其值等于x的结点时,在查找成功的情况下,需平均比较()个元素结点

    A.n/2                B.n                     C.(n+1)/2         D.(n-1)/2

    7.设单链表中指针p指向结点m,若要删除m之后的结点(若存在),则需修改指针的操作为( )

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

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

    8.在一个单链表中,已知q结点是p结点的前趋结点,若在q和p之间插入s结点,则须执行( )

    A.s->next=p->next;  p->next=s

    B.q->next=s;  s->next=p

    C.p->next=s->next;  s->next=p

    D.p->next=s;  s->next=q

    9.线性表的顺序存储结构是一种( )的存储结构。

    A.随机存取         B.顺序存取         C.索引存取         D.散列存取

    二、填空

    1.在线性表的顺序存储中,元素之间的逻辑关系是通过      决定的;在线性表的链接存储中,元素之间的逻辑关系是通过      决定的。

    2.在双向链表中,每个结点含有两个指针域,一个指向       结点,另一个指向       结点。

    3.当对一个线性表经常进行存取操作,而很少进行插入和删除操作时,则采用        存储结构为宜。相反,当经常进行的是插入和删除操作时,则采用        存储结构为宜。

    三、算法设计

    1.设有一个正整数序列组成的有序单链表(按递增次序有序,且允许有相等的整数存在),试编写能实现下列功能的算法(要求用最少的时间和最小的空间)

    ①确定在序列中比正整数x大的数有几个(相同的数只计算一次)

    ②将单链表中比正整数x小的偶数从单链表中删除

    2.设有一个表头指针为h的单链表。试设计一个算法,通过遍历一趟链表,将链表中所有结点的链接方向逆转,如下图所示。要求逆转结果链表的表头指针h指向原链表的最后一个结点。 

     


    3.设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C,其中B表的结点为A表中值小于零的结点,而C表的结点为A表中值大于零的结点(链表A的元素类型为整型,要求B、C表利用A表的结点)。

    4. 假设链表A、B分别表示一个集合,试设计算法以判断集合A是否是集合B的子集,若是,则返回1,否则返回0,并分析算法的时间复杂度。

    5.设有一单循环链表la,其结点有三个域:prior、data与next,其中data为数据域,,next域指向直接后继,prior域应指向直接前驱,但目前空着。试写一算法将此单循环链表改造为双向循环链表。

     


     

     

     

     

     

     

    参 考 答 案

    第二章 线性表

    一.选择题

    1.A

    2.B

    3.A

    4.D

    5.A

    6.C

    7.A

    8.B

    9.A

    二、填空

    1.物理位置相邻 指针

    2.直接前驱  直接后继

    3.顺序  链式

    三、算法设计

    1.①
    int count(Linklist h,int x)
    {
        int num=0;
        Linknode *p;
        p=h->next;
        while(p&&p->data<=x)
            p=p->next;
        while(p)
            if(p->next&&p->data==p->next->data)
                p=p->next;
            else
            {
                num++;
                p=p->next;
            }
        return num;
    }
    
    ②   void delevenl(Linklist h,int x)
    {
        Linknode *p,*r;
        p=h->next;r=h;
        while(p&&p->data<x)
        {
            if(p->data%2==0)
            {
                r->next=p->next;
                free(p);
                p=r->next;
            }
            else
            {
                r=p;
                p=p->next;
            }
        }
    }
    2.
    void Inverse(Linklist &h)
    {
        Linklist p,q;
        p=h; h=null;
        while(p)
        { q=p; p=p->next;
            q->next=h;
            h=q; }
    }
    3.
    void merge(Linklist La,Linklist&Lb,Linklist &Lc)
    {
        Linknode*p;
        Lc=newLnode;
        Lc->next=NULL;
        p=La->next;
        Lb=La;
        Lb->next=NULL;
        while(p)
        {
            La=p->next;
            if(p->data>0)
            {
                p->next=Lc->next;
                Lc->next=p;
            }
            else
            {
                p->next=Lb->next;
                Lb->next=p;
            }
            p=La;
        }
    }
    4.
    int insect(Linklist La,Linklist Lb)
    {
        Linknode*p,*q;
        p=La->next;
        while(p)
        {
            q=Lb->next;
            while(q)
            {
                if(p->data==q->data)
                    break;
                else
                    q=q->next;
            }
            if(!q)
                return0;
            p=p->next;
        }
        return1;
    }
    5.
    void change(Dublist &h)
    {
        DubLnode*p;
        p=h;
        while(p->next!=h)
        {
            p->next->prior=p;
            p=p->next;
        }
        h->prior=p;
    }
    

     

    第二部分:


                                        第2章   线性表

    2.1 选择题

    1.对于线性表最常用的操作是查找指定序号的元素和在末尾插入元素,则选择(  )最节省时间

    A)顺序表                                     B)带头结点的双循环链表

    C)单链表                                     D)带尾结点的单循环链表

    【答案】A

    2.若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新元素的算法时间复杂度为(  )(1≤i≤n+1)。

    A) O(0)               B) O(1)         C) O(n)          D) O(n2)

    【答案】C

    3.双向链表中有两个指针域,prior和next,分别指向前驱及后继,设p指向链表中的一个结点,q指向一待插入结点,现要求在p前插入q,则正确的插入为(  )

    A)  p->prior=q;  q->next=p;  p->prior->next=q;  q->prior=p->prior;

    B)  q->prior=p->prior;  p->prior->next=q;  q->next=p;  p->prior=q->next;

    C)  q->next=p;  p->next=q;  p->prior->next=q;  q->next=p;

    D)  p->prior->next=q;  q->next=p;  q->prior=p->prior;  p->prior=q;

    【答案】D

    4.在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是( )

    A)O(nlog2n)   B) O(1)         C) O(n)         D) O(n2

    【答案】C

    5. 在一个以 h 为头指针的单循环链中,p 指针指向链尾结点的条件是(  )

    A)p->next==NULL                     B) p->next==h

    C)p->next->next==h                    D) p->data==-1

    【答案】B

    6.对于一个具有n个结点的线性表,建立其单链表的时间复杂度是(  )

        A)O(n)      B) O(1)         C)O(nlog2n)         D) O(n2)

    【答案】A

    8.在双向链表存储结构中,删除p所指的结点时须修改指针(  )

    A)p->prior->next=p->next                   p->next->prior=p->prior;

    B)p->prior=p->prior->prior       p->prior->next=p;

    C)p->next->prior=p           p->next=p->next->next

    D)p->next=p->prior->prior                  p->prior=p->next->next;

    【答案】A

    9.线性表采用链式存储时,其元素地址(  )

    A)必须是连续的                                  B)一定是不连续的

    C)部分地址是连续的                           D)连续与否均可

    【答案】D

    2.2 填空题

    1.线性表L=(a1,a2,…,an)用数组表示,假定删除表中任一元素的概率相同,则删除一个元素平均需要移动元素的个数是_____________。

    【答案】(n-1)/2

    2.在单链表中设置头结点的作用是_____________。

    【答案】主要是使插入和删除等操作统一,在第一个元素之前插入元素和删除第一个结点不必另作判断。另外,不论链表是否为空,链表头指针不变。

    3.线性表的顺序存储是通过_____________来反应元素之间的逻辑关系,而链式存储结构是通过_____________来反应元素之间的逻辑关系。

    【答案】(1)数据元素的前后顺序   (2)元素中的指针

    4.当对一个线性表经常进行的是存取操作,而很少进行插入和删除操作时,则采用_____________存储结构最节省时间,相反当经常进行插入和删除操作时,则采用_____________存储结构最节省时间。

    【答案】(1)顺序  (2)链式

    5.对于一个具有n个结点的单链表,在已知的结点*p后插入一个新结点的时间复杂度为_____________,在给定值为x的结点后插入一个新结点的时间复杂度为_____________。

    【答案】(1)O(1)    (2)O(n)

    7. 对于双向链表,在两个结点之间插入一个新结点需修改的指针共_____________个,单链表为_____________个。

    【答案】(1)4  (2)2

    8. 循环单链表的最大优点是_____________。

    【答案】从任一结点出发都可访问到链表中每一个元素。

    9.若要在一个不带头结点的单链表的首结点*p结点之前插入一个*s结点时,可执行下列操作:

            s->next=_____________;

            p->next=s;

            t=p->data;

            p->data= _____________; 

            s->data=_____________;  

    【答案】(1)p->next       (2)s->data      (3) t

    10.某线性表采用顺序存储结构,每个元素占据4个存储单元,首地址为100,则下标为11的(第12个)元素的存储地址为_____________。

    【答案】144

    11.带头结点的双循环链表L中只有一个元素结点的条件是_____________。

    【答案】L->next->next==L

    2.3  判断题

    1.取线性表的第i个元素的时间同i的大小有关(  )

    【答案】×

    2.线性表的特点是每个元素都有一个前驱和一个后继(  )

    【答案】×

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

    【答案】×

    4.线性表采用链表存储时,结点的存储空间可以是不连续的(  )

    【答案】√

    5.链表是采用链式存储结构的线性表,进行插入、删除操作时,在链表中比在顺序存储结构中效率高(  )

    【答案】√

    6.顺序存储方式只能用于存储线性结构(  )

    【答案】×

    【解析】线性结构、树型结构和图状结构均可用顺序存储表示。

    9.顺序存储结构的主要缺点是不利于插入或删除操作(  )

    【答案】√

    10.顺序存储方式插入和删除时效率太低,因此它不如链式存储方式好(  )

    【答案】×

     

    2.4 程序设计题

    1.设顺序表va中的数据元素递增有序。试设计一个算法,将x插入到顺序表的适当位置上,以保持该表的有序性。

    【算法源代码】

    void  Insert_SqList(SqList va,int x)/*把x插入递增有序表va中*/
    { int i;
      if(va.length> MAXSIZE) return;
      for(i=va.length-1;va.elem[i]>x&&i>=0;i--)
             va.elem[i+1]=va.elem[i];
      va.elem[i+1]=x;
      va.length++;
    }/*Insert_SqList*/

    2.设 A=(a1,a2,…,am) 和 B=(b1,b2,…,bn)均为顺序表,试设计一个比较A,B大小的算法(请注意:在算法中,不要破坏原表A和B)。

    【算法分析】比较顺序表A和B,并用返回值表示结果,值为1,表示A>B;值为-1,表示A<B;值为0,表示A=B。

    1)当两个顺序表可以互相比较时,若对应元素不等,则返回值为1或-1;

    2)当两个顺序表可以互相比较的部分完全相同时,若表长也相同,则返回值为0;否则,哪个较长,哪个就较大

    【算法源代码】

    int ListComp(SqList A,SqList B)
    {
      for(i=1;i<=A.length&&i<=B.length;i++)
        if(A.elem[i]!=B.elem[i])
          return A.elem[i]>B.elem[i]?1:-1;
      if(A.length==B.length) return 0;
      return A.length>B.length?1:-1;
    /*当两个顺序表可以互相比较的部分完全相同时,哪个较长,哪个就较大*/
    }/*ListComp */

    3.已知指针 ha和 hb分别指向两个单链表的头结点,并且已知两个链表的长度分别为m和n。试设计一个算法将这两个链表连接在一起(即令其中一个表的首元结点连在另一个表的最后一个结点之后),假设指针hc指向连接后的链表的头结点,并要求算法以尽可能短的时间完成连接运算。

    【算法分析】

    1)单链表ha的头结点作为连接后的链表的头结点,即hc=ha;

    2)查找单链表ha的最后一个结点,由指针p指向,即p->next==NULL;

    3)将单链表hb的首元结点(非头结点)连接在p之后,即p->next=hb->next;

    4)回收单链表hb的头结点空间

    【算法源代码】

    void ListConcat(LinkList ha,LinkList hb,LinkList *hc)
    /*把链表hb接在ha后面形成链表hc*/
    {
      *hc=ha;
      p=ha;/*由指针p指向ha的尾元结点*/
            p=p->next;
      p->next=hb->next;
      free(hb);
    }/*ListConcat */

    4.试设计一个算法,在无头结点的动态单链表上实现线性表操作INSERT(L,i,b),并和在带头结点的动态单链表上实现相同操作的算法进行比较。

    【算法分析】

    1)生成新结点存放元素b,由指针new指向;

    2)将new插入在单链表的第i个元素的位置上:若i==1,new插在链表首部;否则查找第i-1个结点,由指针p指向,然后将new插在p之后。

    【算法源代码】

    void  Insert(LinkList *L,int i,int b)
    { LinkList  new;
      new=(LinkList*)malloc(sizeof(LNode));
      new->data=b; 
      if(i==1)
      {/*插入在链表头部*/
        New->next=*L;
        *L=new;
      }
      else
      { /*插入在第i个元素的位置*/
        p=*L;
        while(--i>1) p=p->next;
        new->next=p->next;p->next=new;
      }
    }/*Insert */

    5.已知线性表中的元素以值递增有序排列,并以单链表作存储结构。试设计一个高效的算法,删除表中所有值大于 mink且小于 maxk的元素(若表中存在这样的元素),同时释放被删结点空间(注意:mink和maxk是给定的两个参变量。它们的值可以和表中的元素相同,也可以不同)。

    【算法分析】

    1)查找最后一个不大于mink的元素结点,由指针p指向;

    2)如果还有比mink更大的元素,查找第一个不小于maxk的元素,由指针q指向;

    3)p->next=q,即删除表中所有值大于 mink且小于 maxk的元素。

    【算法源代码】

    void  Delete_Between(LinkList *L,int mink,int maxk)
    {
      p=*L;
      while(p->next->data<=mink) p=p->next;   /*p是最后一个不大于mink的元素*/
      if(p->next)    /*如果还有比mink更大的元素*/
      {
        q=p->next;
        while(q->data<maxk) q=q->next;  /*q是第一个不小于maxk的元素*/
        p->next=q;
      }
    }/*Delete_Between */

    展开全文
  • 1.下述哪一条是顺序存储结构的优点?( )【北方交通大学 2001 一、4(2分)】 A.存储密度大 B.插入运算方便 C.删除运算方便 D.可方便地用于各种逻辑结构的存储表示 2.下面关于线性表的叙述中,错误的是哪...

    大一下半期数据结构

    数据结构:第2章 线性表

    选择题
    1.下述哪一条是顺序存储结构的优点?( )【北方交通大学 2001 一、4(2分)】
    A.存储密度大 B.插入运算方便
    C.删除运算方便 D.可方便地用于各种逻辑结构的存储表示
    2.下面关于线性表的叙述中,错误的是哪一个?( )【北方交通大学 2001 一、14(2分)】
    A.线性表采用顺序存储,必须占用一片连续的存储单元。
    B.线性表采用顺序存储,便于进行插入和删除操作。
    C.线性表采用链接存储,不必占用一片连续的存储单元。
    D.线性表采用链接存储,便于插入和删除操作。
    3.线性表是具有n个( )的有限序列(n>0)。 【清华大学 1998 一、4(2分)】
    A.表元素 B.字符 C.数据元素 D.数据项 E.信息项

    1.数据:数据是对客观事物的符号表示,在计算机科学中
    是指所有能输入到计算机中并被计算机程序处理的符号的
    总称。
    2.数据元素:数据元素是数据的基本单位,在计算机程序
    中通常作为一个整体进行考虑和处理。一个数据元素可由
    若干个数据项组成。
    3.数据项:数据项是数据的不可分割的最小单位。
    4.数据对象:数据对象是性质相同的数据元素的集合,是
    数据的一个子集。
    5.数据结构:数据结构是相互之间存在一种或多种特定关系
    的数据元素的集合。数据结构包括三方面的内容:数据的
    逻辑结构、数据的存储结构、数据的运算。
    6.数据的逻辑结构是指数据元素之间的逻辑关系,即从逻辑
    关系上描述数据。它与数据的存储无关,是独立于计算机的。
    

    4.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则利用( )存储方式最节省时间。【哈尔滨工业大学 2001 二、1(2分)】
    A.顺序表 B.双链表
    C.带头结点的双循环链表 D.单循环链表
    5.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用( )存储方式最节省运算时间。【南开大学 2000 一、3】
    A.单链表 B.仅有头指针的单循环链表
    C.双链表 D.仅有尾指针的单循环链表
    6.设一个链表最常用的操作是在末尾插入结点和删除尾结点,则选用( )最节省时间。
    A. 单链表 B.单循环链表
    C. 带尾指针的单循环链表 D.带头结点的双循环链表
    【合肥工业大学 2000 一、1(2分)】
    7.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用( )存储方式最节省运算时间。【北京理工大学 2000 一、1(2分)】
    A.单链表 B.双链表
    C.单循环链表 D.带头结点的双循环链表
    8. 静态链表中指针表示的是( ). 【北京理工大学 2001 六、2(2分)】
    A. 内存地址 B.数组下标 C.下一元素地址 D.左、右孩子地址
    9. 链表不具有的特点是( ) 【福州大学 1998 一、8 (2分)】
    A.插入、删除不需要移动元素 B.可随机访问任一元素
    C.不必事先估计存储空间 D.所需空间与线性长度成正比
    10. 下面的叙述不正确的是( )【南京理工大学 1996 一、10(2分)】
    A.线性表在链式存储时,查找第i个元素的时间同i的值成正比
    B. 线性表在链式存储时,查找第i个元素的时间同i的值无关
    C. 线性表在顺序存储时,查找第i个元素的时间同i 的值成正比
    D. 线性表在顺序存储时,查找第i个元素的时间同i的值无关
    12.(1) 静态链表既有顺序存储的优点,又有动态链表的优点。所以,它存取表中第i个元素的时间与i无关。
    (2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了,以后不能增加。
    (3) 静态链表与动态链表在元素的插入、删除上类似,不需做元素的移动。
    以上错误的是( )【南京理工大学 2000 一、3(1.5分)】
    A.(1),(2) B.(1)
    C.(1),(2),(3) D.(2)
    13. 若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新元素的算法的时间复杂度为( )(1<=i<=n+1)。【北京航空航天大学 1999 一、1(2分)】
    A. O(0) B. O(1) C. O(n) D. O(n2)
    14. 对于顺序存储的线性表,访问结点和增加、删除结点的时间复杂度为( )。
    A.O(n) O(n) B. O(n) O(1)
    C. O(1) O(n) D. O(1) O(1)
    15.非空的循环单链表head的尾结点p满足( )。【武汉大学 2000 二、10】
    A.p->link=head B.p->link=NIL
    C.p=NULL D.p= head
    16.在一个以 h 为头的单循环链中,p 指针指向链尾的条件是()【南京理工大学1998 一、15(2分)】
    A. p->next=h B. p->next=NIL
    C. p->next->next=h D. p->data=-1
    17. 线性表的表元存储方式有((1)顺序)和链接两种。试指出下列各表中使用的是何种存储方式:表1是((2)顺序)存储方式;表2是((3)循环链接)存储方式;表3是((4)单项链接)存储方式;表4是((5)双向链接)存储方式。表左的s指向起始表元。
    供选择的答案:
    A.连续 B.单向链接 C.双向链接 D.不连接 E.循环链接
    F.树状 G.网状 H.随机 I.顺序 J.顺序循环
    表一
    在这里插入图片描述
    表二

    在这里插入图片描述
    表三
    在这里插入图片描述
    表四

    在这里插入图片描述
    18为了增加内存空间的利用率,由两个栈共享一片连续的内存空间时,应将两栈的栈底分别设在这片内存空间的两端,这样,当( )时,才表示栈满。
    A.两个栈的栈顶同时到达栈空间的中心点
    B、其中一个栈的栈顶到达栈空间的中心点
    C=、两个栈的栈顶在栈空间的某一位置相遇
    D、两个栈均不空,且一个栈的栈顶到达另一个栈的栈底
    19.假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear,则当前队列中的元素个数为( )
    A(rear-front+m)%m
    B、rear-front+1
    C、(front-rear+m)%m
    D、(rear-front)%m

    判断题
    1. 链表中的头结点仅起到标识的作用。( × )【南京航空航天大学 1997 一、1(1分)】

    头结点并不仅起“标识”作用,并且使操作统一。另外,头结点
    数据域可写入链表长度,或做监视哨。
    

    2. 顺序存储结构的主要缺点是不利于插入或删除操作。( )【南京航空航天大学1997 一、2(1分)】
    3.线性表采用链表存储时,结点和结点内部的存储空间可以是不连续的。( )
    【北京邮电大学 1998 一、2(2分)】
    4.顺序存储方式插入和删除时效率太低,因此它不如链式存储方式好。(× )
    【北京邮电大学 2002 一、2(1分)】
    5. 对任何数据结构链式存储结构一定优于顺序存储结构。( )【南京航空航天大学 1997 一、3(1分)】
    6.顺序存储方式只能用于存储线性结构。( )
    【中科院软件所 1999 六、1-2(2分)】【上海海运学院 1997 一、1(1分)】
    7.集合与线性表的区别在于是否按关键字排序。( )【大连海事大学 2001 一、5 ( 1分)】

    集合中元素无逻辑关系
    

    8. 所谓静态链表就是一直不发生变化的链表。( )【合肥工业大学 2000 二、1(1分)】
    9. 线性表的特点是每个元素都有一个前驱和一个后继。( )【合肥工业大学2001 二、1(1分)】

    非空线性表第一个元素无前驱,最后一个元素无后继。
    

    10. 取线性表的第i个元素的时间同i的大小有关. ( )【南京理工大学 1997 二、9(2分)】
    11. 循环链表不是线性表. ( )【南京理工大学 1998 二、1(2分)】
    12. 线性表只能用顺序存储结构实现。( )【青岛大学 2001 四、2(1分)】
    13. 线性表就是顺序存储的表。( )【青岛大学 2002 一、1(1分)】

    线性表是逻辑结构,可顺序存储,可链式存储。
    

    14.为了很方便的插入和删除数据,可以使用双向链表存放数据。( )
    【上海海运学院 1995 一、1(1分)】 【上海海运学院 1997 一、2(1分)】
    15. 顺序存储方式的优点是存储密度大,且插入、删除运算效率高。( )
    【上海海运学院 1996 一、1(1分)】 【上海海运学院 1999 一、1(1分)】
    16. 链表是采用链式存储结构的线性表,进行插入、删除操作时,在链表中比在顺序存储结构中效率高。 ( ) 【上海海运学院 1998 一、2(1分)】
    17.栈和队列都是限制存取点的线性结构。(
    18.循环队列通常用指针来实现队列的头尾相接。(
    19.栈和队列的存储方式,既可以是顺序方式,又可以是链式方式。(

    填空题

    展开全文
  • 1.下述哪一条是顺序存储结构的优点?( ) A.存储密度大 B.插入运算方便 C.删除运算方便 D.可方便地用于各种逻辑结构的存储表示 2.下面关于线性表的叙述中,错误的是哪一个?( ) A.线性表采用顺序存储,...
  • 2、数据结构习题——第二章 线性表

    千次阅读 2014-06-20 21:42:30
    1.下述哪一条是顺序存储结构的优点?( ) A.存储密度大 B.插入运算方便 C.删除运算方便 D.可方便地用于各种逻辑结构的存储表示 2.下面关于线性表的叙述中,错误的是哪一个?( ) A.线性表采用顺序...
  • 数据结构习题--线性表

    千次阅读 2016-02-28 15:22:25
    1.下述哪一条是顺序存储结构的优点?( )【北方交通大学 2001 一、4(2分)】 A.存储密度大 B.插入运算方便 C.删除运算方便 D.可方便地用于各种逻辑结构的存储表示 2.下面关于线性表的叙述中,错误的...
  • 线性表练习

    2013-04-16 20:33:37
    线性表练习 1.下述哪一条是顺序存储结构的优点?( ) A.存储密度大 B.插入运算方便 C.删除运算方便 D.可方便地用于各种逻辑结构的存储表示
  • 数据结构01

    2011-11-10 13:20:27
    单项选择题(每小题2分)  1. 算法的计算量的大小称为计算的( )。 A.效率 B. 复杂性 C. 现实性 ...D....A....B....C.... 3.下述哪一条是顺序存储结构的优点?( )。 A.存储密度大 B.插入运算方便 ...
  • 数据结构1800试题(第2章)

    千次阅读 2012-04-05 15:57:54
    1.下述哪一条是顺序存储结构的优点?( )【北方交通大学 2001 一、4(2分)】 A.存储密度大 B.插入运算方便 C.删除运算方便 D.可方便地用于各种逻辑结构的存储表示 2.下面关于线性表的叙述中,错误的是...
  • 葵花宝典之数据结构1800T--2

    千次阅读 2012-09-09 09:40:11
    1.下述哪一条是顺序存储结构的优点?( )【北方交通大学 2001 一、4(2分)】 A.存储密度大 B.插入运算方便 C.删除运算方便 D.可方便地用于各种逻辑结构的存储表示 2.下面关于线性表的叙述中,错误的...
  • 6、下述哪一条是顺序存储结构的优点( )?。 A插入运算方便 B可方便地用于各种逻辑结构的存储表示 C存储密度大 D删除运算方便 7、在单链表指针为p的结点之后插入指针为s的结点,正确的操作是( ) 。 A、p->...
  • 线性表--选择题

    2012-07-25 18:55:20
    1.下述哪一条是顺序存储结构的优点?( ) A.存储密度大 B.插入运算方便 C.删除运算方便 D.可方便地用于各种逻辑结构的存储表示 2.下面关于线性表的叙述中,错误的是哪一个?( ) A.线性表采用顺序...
  • 1.下述哪一条是顺序存储结构的优点?( ) A.存储密度大 B.插入运算方便 C.删除运算方便 D.可方便地用于各种逻辑结构的存储表示 2.以下数据结构中,( )是非线性数据结构 A.树 B.字符串 C.队 D.栈 3.若...
  • 考研题目 第二章线性表

    千次阅读 2007-12-02 10:29:00
    下述哪一条是顺序存储结构的优点?( )【北方交通大学2001 一、4(2分)】 A.存储密度大 B.插入运算方便 C.删除运算方便 D.可方便地用于各种逻辑结构的存储表示 2.下面关于线性表的叙述中,错误的是哪一个?...
  • 1.下述哪一条是顺序存储结构的优点?( )(A) A.存储密度大 B插入运算方便 C.删除运算方便 D可方便地用于各种逻辑结构的存储表示 2.下面关于线性表的叙述中,错误的是哪一个?( )(B) A.线性表采用顺序存储,...
  • 第2章 线性表

    千次阅读 2007-07-08 22:08:00
    下述哪一条是顺序存储结构的优点?( )【北方交通大学 2001 一、4(2分)】A.存储密度大 B.插入运算方便 C.删除运算方便 D.可方便地用于各种逻辑结构的存储表示2.下面关于线性表的叙述中,错误的是哪一个...
  • 《数据结构 1800题》

    热门讨论 2012-12-27 16:52:03
    10. 在顺序存储结构中,有时也存储数据结构中元素之间的关系。( )【华南理工大学 2002 、2 (1分)】 11. 顺序存储方式的优点是存储密度大,且插入、删除运算效率高。( )【上海海运学院 1999 、1(1分)】 12....
  • (63) 线性表的顺序存储结构和线性表链式存储结构分别(B) A. 顺序存取存储结构、顺序存取存储结构 B. 随机存取存储结构、顺序存取存储结构 C. 随机存取存储结构、随机存取存储结构 D. 任意存取存储...
  • (32) 顺序存储方法把逻辑上相邻结点存储在物理位置______存储单元中。 答:相邻 (33) Jackson结构化程序设计方法英国M.Jackson提出,它是一种面向______设计方法。 答:数据结构 (34) 数据库设计...

空空如也

空空如也

1 2
收藏数 27
精华内容 10
关键字:

下述哪一条是顺序存储结构的优点