数据结构与算法--第二章习题

发布时间:2024年01月24日

数据结构与算法--PTA第二章习题

一、判断

  1. For a sequentially stored linear list of length?N, the time complexities for query and insertion are?O(1)?and?O(N), respectively. T
  2. If the most commonly used operations are to visit a random position and to insert and delete the last element in a linear list, then sequential storage works the fastest. T
  3. In a singly linked list of?N?nodes, the time complexities for query and insertion are?O(1)?and?O(N), respectively. F
  4. If a linear list is represented by a linked list, the addresses of the elements in the memory must be consecutive. F
  5. 将N个数据按照从小到大顺序组织存放在一个单向链表中。如果采用二分查找,那么查找的平均时间复杂度是O(logN)。 F

二、单选

  1. 对于顺序存储的长度为N的线性表,访问结点和增加结点的时间复杂度为:B

    A.O(1),?O(1)

    B.O(1),?O(N)

    C.O(N),?O(1)

    D.O(N),?O(N)

  2. 链表不具有的特点是:B

    A.插入、删除不需要移动元素

    B.方便随机访问任一元素

    C.不必事先估计存储空间

    D.所需空间与线性长度成正比

  3. 线性表L在什么情况下适用于使用链式结构实现? A

    A.需不断对L进行删除插入

    B.需经常修改L中的结点值

    C.L中含有大量的结点

    D.L中结点结构复杂

  4. 线性表若采用链式存储结构时,要求内存中可用存储单元的地址 B

    A.必须是连续的

    B.连续或不连续都可以

    C.部分地址必须是连续的

    D.一定是不连续的

  5. 在N个结点的顺序表中,算法的时间复杂度为O(1)的操作是: A

    A.访问第i个结点(1≤i≤N)和求第i个结点的直接前驱(2≤i≤N)

    B.在第i个结点后插入一个新结点(1≤i≤N)

    C.删除第i个结点(1≤i≤N)

    D.将N个结点从小到大排序

  6. 将线性表La和Lb头尾连接,要求时间复杂度为O(1),且占用辅助空间尽量小。应该使用哪种结构?C

    A.单链表

    B.单循环链表

    C.带尾指针的单循环链表

    D.带头结点的双循环链表

  7. 采用多项式的非零项链式存储表示法,如果两个多项式的非零项分别为N1?和N2?个,最高项指数分别为M1?和M2?,则实现两个多项式相加的时间复杂度是:A

    A.O(N1?+N2?)

    B.O(M1?+M2?)

    C.O(N1?×N2?)

    D.O(M1?×M2?)

  8. In a singly linked list, if the node pointed by?p?is not the last node, then to insert a node pointed by?s?after?p, we must do: C

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

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

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

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

  9. For a non-empty singly linked circular list, with?h?and?p?pointing to its head and tail nodes, respectively, the TRUE statement is: A

    A.p->next == h

    B.p->next == NULL

    C.p == NULL

    D.p == h

  10. The following table shows how a linked list is stored in memory space with the head node?c:

    Now?f?is stored at?1014H?and is inserted into the linked list between?a?and?e. Then the "Link"

    fields of?a,?e, and?f?are __, respectively. D

    A.1010H,?1014H,?1004H

    B.1010H,?1004H,?1014H

    C.1014H,?1010H,?1004H

    D.1014H,?1004H,?1010H

文章来源:https://blog.csdn.net/hcjdhsjs/article/details/135822409
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。