二、线性表复习题

╰+哭是因爲堅強的太久メ 2024-03-16 13:02 62阅读 0赞

#### 练习题2、线性表 ####

*   *  1.线性表定义
     *  2.顺序表
     *  3.链表

### 1.线性表定义 ###

> 线性表定义：线性表是具有相同数据类型的n(n>0)个数据元素的有限序列，其中n为表长，当n=0时线性表是一个空表。

1.以下（）是一个线性表  
A 由n个实数组成的集合 B 由100个字符组成的序列  
C 所有整数组成的序列 D 邻接表

选B，线性表定义的要求为：相同数据类型、有限序列。A没有前驱后继关系，C不是有限的，D属于存储结构，线性表是一种逻辑结构。

### 2.顺序表 ###

> 概念：用一组地址连续的存储单元依次存储线性表的数据元素，这种存储结构的线性表称为顺序表。  
> 特点：逻辑上相邻的数据元素，物理次序也是相邻的。  
> 时间复杂度：线性表的顺序存储结果在**读**数据是的时间复杂度是O(1)，插入、删除操作的时间复杂度是O(n)。按值查找是O(n)，按位查找是O(1)。

1.设线性表有n个元素,以下操作中, 在顺序表上实现比在链表上实现效率更高。（AEG）  
**A、输出第i(1≤i≤n)个元素值**  
B、交换第1个元素与第2个元素的值  
C、顺序输出这n个元素的值  
D、输出与给定值x相等的元素在线性表中的序号  
**E、在最后一个元素的后面插入一个新元素**  
F、顺序输出前k个元素  
**G、交换第i个元素和第n-i+1个元素的值(i=1,2,…,n)**  
H.删除指定位置元素的后一个元素  
I.删除所有值为x的元素

分析：C、F一样，H、I单链表效率高，BD有疑问

2.若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间  
**A.顺序表**

3.用数组表示线性表的优点是（）。  
**B.便于随机存取**

4.顺序存储表示中数据元素之间的逻辑关系是由（ ）表示的。  
**C.存储位置**

5.线性表L=（a1, a2 ,……，an ）用一维数组表示，假定删除线性表中任一元素的概率相同（都为1/n），则删除一个元素平均需要移动元素的个数是（）。  
**A.(n-1)/2**

如果删除第一个元素，后面的元素都向前移动，需要移动n-1个元素；如果删除第二个元素，后面的元素都向前移动，需要移动n-2个元素；…；如果删除第n-1个元素，后面的元素都向前移动，需要移动1个元素；如果删除第n个元素，后面没有元素需要移动。1/n\*(n-1+n-2+n-3+…0)= (n-1)/2

6.顺序表的插入算法中，当n个空间已满时，可再申请增加分配m个空间，若申请失败，则说明系统没有（）可分配的存储空间  
**D n+m个连续**

### 3.链表 ###

> 单链表方式有一个数据域和一个指针域  
> 双链表方式有一个数据域和两个指针域  
> 静态链表需要分配较大的连续空间，插入和删除不需要移动元素。  
> 双向链表（double linked list）是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。所以在双向链表中的结点都有两个指针域，一个指向直接后继，另一个指向直接前驱。

1.在带头结点的非空单链表中，头结点的存储位置由前驱结点指示。  
**错**

2.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ）  
**B.head->next = null**

3.静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。  
**对**

4.在循环链表中，将头指针改设为尾指针（rear）后，其头结点和尾结点的存储位置分别是（ )  
**B.rear->next和rear**

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

**B.仅有尾指针的单循环链表**

6.对于一个具有N个结点的单链表，在给定值为x的结点后插入一个新结点的时间复杂度为  
**C.O(N)**

7.对于一个具有N个结点的单链表，在给定值为x的结点后插入一个新结点的时间复杂度为  
**C.O(N)**

8.在双向循环链表结点p之后插入s的语句是  
**D.s->prior=p; s->next=p->next; p->next->prior=s; p->next=s;**

9.将两个结点数都为N且都从小到大有序的单向链表合并成一个从小到大有序的单向链表，那么可能的最少比较次数是：  
**B.N**

10.对于一非空的循环单链表，h和p分别指向链表的头、尾结点，则有：  
**A.p->next=h**

11.在双向链表存储结构中，删除p所指的结点，相应语句为：  
**A.p->prior->next=p->next; p->next->prior=p->prior;**

12.设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( D )最节省时间。  
A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 **D.带头结点的双循环链表**

13.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ D ）存储方式最节省运算时间。  
A．单链表 B．双链表 C．单循环链表 **D．带头结点的双循环链表**

14.在n个结点的单链表中要**删除已知结点\*p**/**在已知结点\*p之前插入一个新结点**,需找到其（前驱）结点的地址（填两个字） ,其时间复杂度为（O(n)）

15.循环链表的合并代码  
![在这里插入图片描述][c948e668f3d248ac91cdf437d41a2aec.png]

//第一步：保存A的头结点
    p = rearA->next;	
    //第二步：将本是指向B表的第一个节点（不是头结点）赋值给rearA->next
    rearA->next = rearB->next->next;
    //第三步：将原A表的头结点赋值给rearB->next
    rearB->next=p;
    //释放p
    free(p);

16.若用单链表来表示队列，则应该选用带尾指针的循环链表。  
**对**  
  
17.给定有n个元素的一维数组，建立一个有序单链表的最低时间复杂度是  
**D.O(nlog n)**

18.将长度为n的单链表链接在长度为m的单链表后面，其算法的时间复杂度采用大O形式表示应该是  
**A.O(1)**

19.已知头指针h指向一个带头结点的非空单循环链表，结点结构为

其中next是指向直接后继结点的指针，p是尾指针，q是临时指针。现要删除该链表的第一个元素，正确的语句序列是( D )。

A、h-> next= h-> next -> next;q= h-> next; free(q);  
B、q=h-> next;h-> next= h-> next -> next; free(q);  
C、q=h-> next; h-> next=q -> next; if(p != q)p = h; free(q);  
**D、q=h-> next; h-> next=q -> next; if(p == q)p= h; free(q);**

需要考虑特殊情况，若待删结点是链表的尾结点，即循环单链表中只有一个元素(p 和q指向同一个结点)的情况

20.设有两个长度为n的单链表（带头结点），结点类型相同，若以h1为头结点指针的链表是非循环的，以h2为头结点指针的链表是循环的，则（B）。  
A、对于两个链表来说，删除开始结点的操作，其时间复杂度分别为O(1)和O(n)。  
**B、对于两个链表来说，删除重点结点的操作，其时间复杂度都是O(n)。**  
C、循环链表要比非循环链表占用更多的内存空间。  
D、h1和h2是不同类型的变量。

两个链表占用内存空间相同，不要误以为循环链表比非循环链表多一个指向头结点的指针，其实非循环链表也有这个指针，只是它没有指向头结点而已。

循环链表和非循环链表其实创建的过程以及思路几乎完全一样，唯一不同的是，**非循环链表的尾结点指向空（NULL），而循环链表的尾指针指向的是链表的开头**。通过将单链表的尾结点指向头结点的链表称之为循环单链表（Circular linkedlist）

参考：[PTA 数据结构 第二章课后作业][PTA _]

[c948e668f3d248ac91cdf437d41a2aec.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/d3880ee49cf64572ac8434b1c18a5b9c.png
[PTA _]: https://blog.csdn.net/hongjian_314/article/details/118102882?spm=1001.2101.3001.6650.3&utm_medium=distribute.pc_relevant.none-task-blog-2~default~CTRLIST~Rate-3-118102882-blog-107481397.235%5Ev38%5Epc_relevant_anti_t3&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2~default~CTRLIST~Rate-3-118102882-blog-107481397.235%5Ev38%5Epc_relevant_anti_t3&utm_relevant_index=4