第二章–线性表
|
数据结构
|
39

6861 字
|
47 分钟
本文最后更新于26 天前，其中的信息可能已经过时，如有错误请发送邮件到big_fw@foxmail.com

知识点

1.线性表的定义和特点

由n (n≥0)个数据特性相同的元素构成的有限序列称为线性表，(n=0)的时候被称为空表。

对于非空的线性表或线性结构，其特点是：

  • 存在唯一的一个被称作“第一个”的数据元素；
  • 存在唯一的一个被称作“最后一个”的数据元素；
  • 除第一个元素之外，结构中的每个数据元素均只有一个前驱；
  • 除最后一个元素之外，结构中的每个数据元素均只有一个后继。

2.线性表的顺序表示和实现

2.1线性表的顺序表示

线性表的顺序存储又被称为顺序表
顺序存储表示：用一组地址连续的存储单元依次存储线性表的数据元素的方式，具有顺序存储结构的特点（数据间的逻辑关系和物理关系是一致的）

假设线性表 L 存储的起始位置为 LOC(A) ，sizeof(ElemType) 是每个数据元素所占用存储空间的大小，则表 L 所对应的顺序存储如下图：

线性表的顺序存储结构是一种随机存取的存储结构，即通过首地址和元素序号可以在O(1) 时间内找到指定的元素

注意：线性表中的位序是从 1 开始的，而数组中元素的下标是从 0 开始的

//－－－－－ 顺序表的存储结构－－－－－
#define MAXSIZE 100             //顺序表可能达到的最大长度
    typedef struct {
        ElemType *elem;         //存储空间的基地址
        int length;             //当前长度
    } SqList;                   //顺序表的结构类型为SqList

2.2顺序表中基本操作的实现

一、顺序表初始化
①、为顺序表L动态分配一个预定义大小的数组空间，使elem指向这段空间的基地址。
②、将表的当前长度设为0。

    Status InitList(SqList &L) {
        //构造一个空的顺序表 L
        L.elem = new ElemType[MAXSIZE];     //为顺序表分配一个大小为MAXSIZE的数组空间，这是C++语句
        if (!L.elem) exit(OVERFLOW);        //存储分配失败退出
        L.length = O;                       //空表长度为0
        return OK;
    }

二、顺序表取值

①、判断指定的位置序号 i 值是否合理 (1≤i≤L.length), 若不合理，则返回ERROR。
②、若 i 值合理，则将第 i 个数据元素 L.elem[i-1] 赋给参数 e, 通过 e返回第 i 个数据元素的传值。

    Status GetElem(SqList L, int i, ElemType &e) {
        if {
            (i < 1 || i > L.length) return ERROR;  //判断l. 值是否合理，若不合理， 返回ERROR
            e = L.elem[i - 1];                     //elem[i-1] 单元存储第 i 个数据元素
            return OK;
        }

    }

顺序表取值算法的时间复杂度为 ：O(1)

三、顺序表的按值查找

①、从第一个元素起，依次和 e相比较，若找到与 e相等的元素 L.elem[i], 则查找成功，返回该元素的序号 i+l (数组下标从 0 开始)
②、若查遍整个顺序表都没有找到，则查找失败， 返回0

int LocateELem(SqList L, ElemType e) {
        //在顺序表1中查找值为e的数据元素， 返回其序号
        for (i = O; i < L.length; i++) {
            if (L.elem[i)==e){
                return i + l;           //查找成功， 返回序号 i+l
            }
        }
        return O;                       //查找失败， 返回 0           
    }

顺序表按值查找算法的平均时间复杂度为 O(n)

四、顺序表插入元素

在第 i 个位置插入一个元素时，需从最后一个元素即第 n 个元素开始，依次向后移动一个位置，直至第 i 个元素。

  1. 判断插入位置 i 是否合法(i 值的合法范围是 1≤i≤n+ I), 若不合法 则返回 ERROR。
  2. 判断顺序表的存储空间是否已满，若满则返回 ERROR。
  3. 将第n个至第 i 个位置的元素依次向后移动一个位置，空出第 i 个位置 ( i =n+l 时无需移动）。
  4. 将要插入的新元素e放入第i个位置。
  5. 表长加1
Status Listinsert(SqList &L, int i, ElemType e) {
        //在顺序表 L 中第 i 个位置之前插入新的元素 e, i值的合法范围是 1...i...L.length+l
        if ((i < l) || (i > L.length + l)) {
            return ERROR;                       //i值不合法
        }
        if (L.length == MAXSIZE) {
            return ERROR;                       //当前存储空间已满
        }
        for (j = L.length - 1; j >= i - 1; j--) {
            L.elem[j + l] = L.elem[j];                     //插入位置及之后的元素后移
        }
        L.elem[i - l] = e;                                //将新元素e放入第l个位置
        ++L.length;                                       //表长加1
        return OK;
    }

顺序表插入算法的平均时间复杂度为O(n)

五、顺序表删除元素

删除第 i 个元素时需将第 i+ 1 个至第 n 个元素依次向前移动一个位置 (i = n 时无需移动）

  1. 判断删除位置 i 是否合法（合法值为 1 ≤ i ≤n), 若不合法则返回 ERROR。
  2. 将第 i个至第n个的元素依次向前移动一个位置 (i = n时无需移动）
  3. 表长减 1
Status ListDelete(SqList &L, int i) {
        //在顺序表L中删除第J.个元素，J.值的合法范围是 1.;;i.;;L. length
            if ((i < l) || (i > L.length)) {
                return ERROR;                               //i值不合法
            }
            for (j = i; j <= L.length - 1; j++) {
                L.elem[j - 1]=1.elem[j];                    //被删除元素之后的元素前移
            }
            --L.length;                                     //表长减 1
            return OK;
        }

顺序表删除算法的平均时间复杂度为 O(n)

3.线性表的链式表示和实现

链式存储结构的特点：用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的），存放数据元素的结点至少包括两个域（指针域、数据域），也可以包含若干个指针域和数据域。

3.1、单链表的定义和表示

关于带头结点的单链表及不带头节点的单链表

  • 首元结点：是指链表中存储第一个数据元素的结点。
  • 头结点：是在首元素结点之前附设的一个结点，其指针指向首元结点。
  • 头指针：是指向链表中第一个结点的指针。若链表设有头结点，则头指针所指结点为线性表的头结点；若链表不设头结点，则头指针所指结点为该线性表的首元结点。

带头结点：

不带头结点：

  • 带头结点的单链表为空时：L->next==NULL；
  • 不带头结点：不带头结点的单链表为空时：L=NULL;
    //－－－－－ 单链表的存储结构－－－－－
    typedef struct LNode {
        ElemType data;          //结点的数据域
        struct LNode *next;     //结点的指针域
    } LNode, *LinkList;         //LinkList 为指向结构体 LNode 的指针类型

3.2、单链表基本操作的实现

一、单链表的初始化

①、生成新结点作为头结点，用头指针L 指向头结点。
②、头结点的指针域置空。

 Status InitList(LinkList &L) {     //构造一个空的单链表L
        L = new LNode;             //生成新结点作为头结点，用头指针L指向头结点
        L->next = NULL;          //头结点的指针域置空
        return OK;
    }

二、单链表的取值

①、用指针p指向首元结点，用 j 做计数器初值赋为1
②、从首元结点开始依次顺着链域 next 向下访问，只要指向当前结点的指针 p 不为空(NULL), 并且没有到达序号为 i 的结点，则循环执行以下操作：

  • p指向下一个结点；
  • 计数器 j 相应加 1

③、退出循环时， 如果指针p为空， 或者计数器 j 大于 i, 说明指定的序号 i 值不合法（i 大于表长n或 i 小于等于0), 取值失败返回ERROR; 否则取值成功， 此时 j=i 时，p所指的结点就是要找的第 i 个结点，用参数 e 保存当前结点的数据域， 返回OK。

    Status GetElem(LinkList L, int i, ElemType &e) {
        //在带头结点的单链表L中根据序号l.获取元素的值，用e返回L中第l.个数据元素的值
        p = L->next;
        j = 1;                              //初始化，p指向首元结点，计数器］初值赋为1
        while (p && j < i) {                //顺链域向后扫描，直到p为空或p指向第l.个元素
            p = p->next;                    //p指向下一个结点
            ++j;                            //计数器j相应加1
        }

        if (!p || j > i) return ERROR;      // i值不合法 i>n或i≤0
        e = p->data;                        //取第i个结点的数据域
        return OK;
    }

单链表取值算法的平均时间复杂度为 O(n)

三、单链表的按值查找

①、用指针p指向首元结点

②、从首元结点开始依次顺着链域next向下查找， 只要指向当前结点的指针p不为空， 并且p所指结点的数据域不等于给定值e, 则循环执行以下操作： p指向下一个结点 。

③、返回p。若查找成功，p此时即为结点的地址值，若查找失败，p的值即为NULL

    LNode *LocateELem(LinkList L, Elemtype e) {
        //在带头结点的单链表L中查找值为e的元素
        p = L->next;                            //初始化，p指向首元结点
        while (p && p->data != e) {             //顺链域向后扫描，直到p为空或p所指结点的数据域等于e    
            p = p->next;                        //p指向下一个结点
        }
        return p;                               //查找成功返回值为e的结点地址p, 查找失败p为NULL
    }

单链表的按值查找算法的平均时间复杂度为 O(n)

四、单链表的插入

将值为e的新结点插入到表的第 i 个结点的位置上，即插入到结点 a~i-1~与a~i~之间。

①、查找结点 a~i-1~ 并由指针p指向该结点
②、生成一个新结点*s
③、将新结点*s 的数据域置为 e
④、将新结点*s 的指针域指向结点a~i~
⑤、将结点 * p 的指针域指向新结点*s

 Status Listinsert(LinkList &L, int i, ElemType e) {
        //在带头结点的单链表L中第i个位置插入值为e的新结点
        p = L;
        j = O;
        while (p && (j < i - 1)) {
            p = p->next;
            ++j;                                //查找到第i-1个结点，p指向该结点
        }
        if (!p || j > i - 1) return ERROR;      //i>n+1 或者 i≤1

        s = new LNode;                          //生成新结点 *s

        s->data = e;                            //将结点*s的数据域置为e

        s->next = p->next;                      //将结点 *s的指针域指向结点 ai

        p->next = s;                            //将结点*p的指针域指向结点*s

        return OK;
    }

单链表插入算法的时间复杂度为：O(n)

五、单链表的删除

删除单链表的第 i 个结点a~i~

  1. 查找结点a~i-1~ 并由指针p指向该结点
  2. 临时保存待删除结点 a~i~ 的地址在q中 ，以备释放。
  3. 将结点*p的指针域指向 a~i~ 的直接后继结点
  4. 释放结点a~i~的空间
    Status ListDelete(LinkList &L, int i) {
//在带头结点的单链表L中，删除第l个元素
        p = L;
        j = O;
        while ((p->next) && (j < i - 1)) {              //查找第i-1个结点，p指向该结点
            p = p->next;
            ++j;
        }
        if (!(p->next) || (j > i - 1)) return ERROR;    //当i＞n或i＜1时，删除位置不合理
        q = p->next;                                    //临时保存被删结点的地址以备释放
        p->next = q->next;                              //改变删除结点前驱结点的指针域
        delete q;                                       //释放删除结点的空间
        return OK;
    }

单链表删除算法的时间复杂度为： O(n)

六、创建单链表

前插法：始终让新结点在第一的位置，不常用，因为输入顺序和输出顺序是相反的。

void CreateList_H(LinkList &L,int n)
{//逆位序输入n个元素的值，建立带表头节点的单链表L
 L=new LNode;
 L->next=NULL; 　　//先建立一个带头节点的空链表
 for(i=0;i<n;++i)
 {
　　 p=new LNode; //生成新节点*p
　　 cin>>p->data; //输入元素值赋给新节点*p的数据域
　　 p->next=L->next;L->next=p; //将新节点*p插入到头节点之后
 }
}

后插法：尾指针r始终指向单链表的表尾，常用（输入顺序和输出顺序相同）

①、创建一个只有头结点的空链表。
②、尾指针r初始化， 指向头结点。
③、根据创建链表包括的元素个数n, 循环n次执行以下操作

  • 生成一个新结点*p;
  • 输入元素值赋给新结点*p 的数据域；
  • 将新结点p 插入到尾结点r之后；
  • 尾指针r指向新的尾结点*p
void CreateList_R(LinkList &L,int n)
{//正位序输入n个元素的值，建立带表头节点的单链表L
 L=new LNode;
 L->next=NULL; 　　//先建立一个带头节点的空链表
 r=L; 　　//尾指针r指向头节点
 for(i=0;i<n;++i)
 {
　　　p=new LNode; 　　//生成新节点
　　　cin>>p->data; 　　//输入元素值赋给新节点*p的数据域
　　　p->next=NULL; r->next=p; 　　//将新节点*p插入尾节点*r之后
　　　r=p; 　　//r指向新的尾节点*p
 }
}

3.3、循环链表

3.4、双向链表

//- - - - - 双向链表的存储结构- - - - -
typedef struct DuLNode
{
 ElemType data; //数据域
 struct DuLNode *prior; //指向直接前驱
 struct DuLNode *next; //指向直接后继
}DuLNode,*DuLinkList;

双向链表的插入：

Status ListInsert_DuL(DuLinkList &L,int i,ElemType e)
{//在带头节点的双向链表L中第i个位置之前插入元素e
 if(!(p=GetElem_DuL(L,i))) //在L中确定第i个元素的位置指针p
　　　return ERROR; //p为NULL时，第i个元素不存在
 s=new DuLNode; //生成新节点*s
 s->data=e; //将节点*s数据域置为e
 s->prior=p->prior; //将节点*s插入L中，此步对应图2.20①
 p->prior->next=s; //对应图2.20②
 s->next=p; //对应图2.20③
 p->prior=s; //对应图2.20④
 return OK;
}

双向链表的删除

Status ListDelete_DuL(DuLinkList &L,int i)
{//删除带头节点的双向链表L中的第i个元素
 if(!(p=GetElem_DuL(L,i))) //在L中确定第i个元素的位置指针p
　　　return ERROR; //p为NULL时，第i个元素不存在
 p->prior->next=p->next; //修改被删节点的前驱节点的后继指针，对
　　　　　　　　　　　　　　　　　　　 应图2.21①
 p->next->prior=p->prior; //修改被删节点的后继节点的前驱指针，对
　　　　　　　　　　　　　　　　　　 应图2.21②
 delete p; //释放被删节点的空间
 return OK;
}

4.顺序表和链表的比较

习题

顺序表部分

一、单选题

1.对线性表的定义是（  ）

A. 一个有限序列，可以为空 
B. 一个有限序列，不可以为空
C. 一个无限序列，可以为空
D. 一个无限序列，不可以为空

2.有关线性表L=(a1，a2,……an)，下列说法正确的是（ ）。

A. 每个元素都有一个直接前驱和一个直接后继
B. 线性表中至少有一个元素
C. 表中诸元素的排列必须是由小到大或由大到小
D. 除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。

3.在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（ ）。

A. 访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
B. 在第i个结点后插入一个新结点（1≤i≤n）
C. 删除第i个结点（1≤i≤n）
D. 将n个结点从小到大排序

4.顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ ）。

A. 110
B. 108
C. 100
D. 120

5.若长度为n的顺序表在其第i个位置插入一个新元素，需移动的元素个数是（ ）。

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

6.假设删除长度为n的顺序表中的每个元素的概率相同，则删除一个元素平均要移动的元素个数是（ ）。

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

7.设某顺序表中第一个元素的地址是Base，每个结点占m个单元，则第i个结点的地址为（ ）。

A. Base+(i-1)×m
B. Base-i×m
C. Base+(i+1)×m
D. Base+i×m

8.一个长度为n的顺序表的表尾插入一个新元素的时间复杂度为（ ）。

A. o(1)
B. o(n)
C. o(n^2)
D. o(log₂n)

9.在一个长度为n的顺序表中删除第i个元素(1<=i<=n)时，需向前移动（ ）个元素

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

10.向一个有126个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（ ）。

A. 8
B. 63.5
C. 63
D. 7

11.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ ）。

A. o(n) o(n)
B. o(n) o(1)
C. o(1) o(n)
D. 均为o(1)

二、填空题

1.某线性表采用顺序存储结构，每个元素占据4个存储单元，首地址为100，则下标为11的（第12个）元素的存储地址为（ ）。

三、判断题

2.线性表的逻辑结构和存储结构总是一致的（ ）

A. 对
B. 错

3.线性表的特点是每个元素都有一个前驱和一个后继（ ）

A. 对
B. 错

4.取线性表的第i个元素的时间同i的大小有关（ ）

A. 对
B. 错

链表部分

一、单选题

1.线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ ）。

A. 必须是连续的
B. 部分地址必须是连续的
C. 一定是不连续的
D. 连续或不连续都可以

2.已知L是带表头结点的单链表，删除第一个元素结点的语句是（ ）。

A. L = L->next;
B. L-> next = L-> next -> next;
C. L = L;
D. L-> next = L;

3.在单链表中增加一个头结点的目的是（ ）。

A. 使单链表至少有一个结点
B. 标识表结点中首结点的位置
C. 方便运算的实现
D. 说明单链表是链式存储

4.设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（ ）。

A. o(log₂n)
B. o(1)
C. o(n²)
D. o(n)

5.在一个单链表中，若删除p所指结点的后继结点（注：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;

6.链式存储的存储结构所占存储空间（ ）。

A. 分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
B. 只有一部分，存放结点值
C. 只有一部分，存储表示结点间关系的指针
D. 分两部分，一部分存放结点值，另一部分存放结点所占单元数

7.在单链表中，要将s所指结点插入到p所指结点之后，其语句应为（ ）。

A. s->next=p+1; p->next=s;
B. (p).next=s; (s).next=(*p).next;
C. s->next=p->next; p->next=s->next;
D. s->next=p->next; p->next=s;

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

A. n/2
B. n
C. （n+1）/2
D. （n-1）/2 

9.不带头结点的单链表head为空的判定条件是（   ）。 

A. head==NULL 
B. head->next==NULL
C. head->next==head
D. head!=NULL

10.创建一个包括n个结点的有序单链表的时间复杂度是（ ）。

A. O(1)
B. O(n)
C. O(n²)
D. O(nlog₂n)

11.链表不具备的特点是（ ）。

A. 可随机访问任一结点
B. 插入和删除不需要移动元素
C. 不必事先估计存储空间
D. 所需空间与长度成正比

12.在双向链表存储结构中，删除p所指的结点时须修改指针（ ）。

A. p->next->prior=p->prior; p->prior->next=p->next;
B. p->next=p->next->next; p->next->prior=p;
C. p->prior->next=p; p->prior=p->prior->prior;
D. p->prior=p->next->next; p->next=p->prior->prior;

13.以下链表结构中，从当前结点出发能够访问到任一结点的是（  ）。

A. 单向链表和双向链表
B. 双向链表和循环链表 
C. 单向链表和循环链表
D. 单向链表、双向链表和循环链表

14.在双向循环链表中，在p指针所指的结点后插入q所指向的新结点，其修改指针的操作是（ ）。

A. p->next=q; q->prior=p; p->next->prior=q; q->next=q;
B. p->next=q; p->next->prior=q; q->prior=p; q->next=p->next;
C. q->prior=p; q->next=p->next; p->next->prior=q; p->next=q;
D. q->prior=p; q->next=p->next; p->next=q; p->next->prior=q;

15.设带有头结点的单向循环链表的头指针变量为head，则判断其为空链表的条件（ ）。

A. head==0
B. head->next==0
C. head->next==head
D. head!=0

16.下面关于线性表的叙述错误的是（ ）。

A. 线性表采用顺序存储必须占用一片连续的存储空间
B. 线性表采用链式存储不必占用一片连续的存储空间
C. 线性表采用链式存储便于插入和删除操作的实现
D. 线性表采用顺序存储便于插入和删除操作的实现

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

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

18.线性表Ｌ在（ ）情况下适用于使用链式结构实现。

A. 需经常修改Ｌ中的结点值
B. 需不断对Ｌ进行删除插入
C. Ｌ中含有大量的结点
D. Ｌ中结点结构复杂

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

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

20.单链表的存储密度（ ）。

A. 大于1
B. 等于1
C. 小于1
D. 不能确定

21.以下说法错误的是（ ）。

A. 求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低
B. 顺序存储的线性表可以随机存取
C. 由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活
D. 线性表的链式存储结构优于顺序存储结构

二、判断题

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

A. 对
B. 错

2.顺序表的每个结点只能是一个基本类型，而链表的每个结点可以是一个构造类型。

A. 对
B. 错

3.顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好（　　）

A. 对
B. 错

4.线性表的链式存储结构优于顺序存储。

A. 对
B. 错

三、填空题

1.对于双向链表，在两个结点之间插入一个新结点需修改的指针共（ 1 ）个，单链表为（ 2 ）个。

习题解析

顺序表部分

一、单选题

  1. 答案：A
    解析： 线性表的定义是元素个数有限的序列，且允许为空（即不含任何元素）。
  2. 答案：D
    解析： 线性表中，第一个元素无直接前驱，最后一个元素无直接后继。中间每个元素有且仅有一个直接前驱和一个直接后继。
  3. 答案：A
    解析： 顺序表支持随机访问，通过下标直接定位元素及其直接前驱，时间复杂度为O(1)。
  4. 答案：B
    解析： 地址计算公式：首地址 + (序号 – 1) × 元素长度 = 100 + (5-1)×2 = 108。
  5. 答案：C
    解析： 在第i个位置插入，需要将第i个至第n个元素后移，共移动 n – i + 1 个元素。
  6. 答案：A
    解析： 删除第i个元素需移动 n – i 个元素，等概率下平均移动次数为 Σ(n-i)/n = (n-1)/2。
  7. 答案：A
    解析： 第i个元素的地址 = 基地址 + (i – 1) × 每个元素占用的单元数。
  8. 答案：A
    解析： 在表尾插入不需要移动任何元素，时间复杂度为O(1)。
  9. 答案：A
    解析： 删除第i个元素后，需要将第i+1个至第n个元素前移，共移动 n – i 个元素。
  10. 答案：C
    解析： 在顺序表中插入，平均需要移动约一半的元素，即 n/2 = 126/2 = 63。
  11. 答案：C
    解析： 顺序存储支持随机访问（O(1)），但插入和删除需要移动元素（O(n)）。

二、填空题

  1. 答案：144
    解析： 存储地址 = 首地址 + (下标) × 元素大小 = 100 + 11 × 4 = 144。

三、判断题

  1. 答案：错
    解析： 线性表的逻辑结构（元素间的前后关系）与存储结构（顺序、链式）是两个概念，不一定一致。
  2. 答案：错
    解析： 线性表的第一个元素没有前驱，最后一个元素没有后继。
  3. 答案：错
    解析： 时间复杂度取决于存储结构。顺序表随机访问为O(1)，与i无关；单链表需顺序查找，与i有关。

链表部分

一、单选题

  1. 答案：D
    解析： 链式存储的结点在内存中的分布是任意的，不要求连续。
  2. 答案：B
    解析： 在带头结点的单链表中，删除第一个元素结点，只需将头结点的next指针指向原第二个结点。
  3. 答案：C
    解析： 增加头结点可以统一空表和非空表的操作，简化插入、删除等算法的实现。
  4. 答案：D
    解析： 在有序单链表中插入新结点，需要先找到合适的插入位置，平均需要遍历一半结点，时间复杂度为O(n)。
  5. 答案：A
    解析： 要删除p的后继结点，只需将p的next指针指向后继结点的后继结点。
  6. 答案：A
    解析： 链式存储的结点包含数据域（存放值）和指针域（存放关系）。
  7. 答案：D
    解析： 插入操作的正确步骤：先将新结点s的next指向p的后继，再将p的next指向s。
  8. 答案：C
    解析： 在等概率查找成功的情况下，单链表查找的平均比较次数为 (n+1)/2。
  9. 答案：A
    解析： 不带头结点的单链表，头指针head直接指向第一个结点，为空时head为NULL。
  10. 答案：C
    解析： 每插入一个结点，都需要在已有有序链表中找到合适位置，总时间复杂度为O(n²)。
  11. 答案：A
    解析： 链表只能顺序访问，不能像数组一样通过下标直接访问任一结点。
  12. 答案：A
    解析： 删除双向链表中的p结点，需要修改其前驱结点的next指针和后继结点的prior指针。
  13. 答案：B
    解析： 双向链表可向前向后遍历，循环链表可从任意结点出发遍历全表。单向链表不能反向。
  14. 答案：C
    解析： 正确步骤：先设置q的前驱和后继，然后修改原后继的前驱，最后修改p的后继。
  15. 答案：C
    解析： 带头结点的空循环链表，其头结点的next指针指向自身。
  16. 答案：D
    解析： 顺序存储便于访问，但插入和删除需要移动大量元素，效率较低。
  17. 答案：B
    解析： 仅有尾指针的单循环链表，在表尾插入（通过尾指针）和删除表头元素（尾指针->next->next）都很方便。
  18. 答案：B
    解析： 链式存储的最大优点就是插入和删除操作不需要移动数据。
  19. 答案：A
    解析： 顺序表支持按序号随机存取（O(1)），在末尾插入删除也只需O(1)，综合效率最高。
  20. 答案：C
    解析： 存储密度 = 数据域占用的空间 / 整个结点占用的空间。由于结点包含指针域，密度小于1。
  21. 答案：D
    解析： 顺序存储和链式存储各有优缺点，需根据具体应用场景选择，没有绝对的优劣。

二、判断题

  1. 答案：对
    解析： 链表的插入删除只需修改指针，而顺序表需要移动大量元素。
  2. 答案：错
    解析： 顺序表和链表的结点都可以是基本类型或构造类型（结构体等）。
  3. 答案：错
    解析： 顺序存储和链式存储各有适用场景。顺序存储访问快，链式存储插入删除灵活。
  4. 答案：错
    解析： 两种存储结构各有优缺点，不能笼统地说哪个更好。

三、填空题

  1. 答案：4；2
    解析： 双向链表插入需要修改4个指针（新结点的prior和next，前驱结点的next，后继结点的prior）。单链表插入只需修改2个指针（新结点的next，前驱结点的next）。
文末附加内容
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																

							
							
						

																

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
第四章—串

							
							

							
第三章–栈和队列

							
							

							
第一章-绪论

							
							

							
C/C++

							
							

							
第七章–树和二叉树

							
							

							
第五章–数组

							
							

							
第九章–查找

							
							

							
第六章–广义表

							
							

							
第八章–图

							
							

							
第十章–排序