🏷️ 知识点：线性表的链式表示
下列关于线性表的存储结构的描述中，正确的是()。 I. 线性表的顺序存储结构优于其链式存储结构 Ⅱ.链式存储结构比顺序存储结构能更方便地表示各种逻辑结构 Ⅲ.若频繁使用插入和删除结点操作，则顺序存储结构更优于链式存储结构 IV. 顺序存储结构和链式存储结构都可以进行顺序存取
A. I 、Ⅱ 、Ⅲ B.Ⅱ 、IV C.Ⅱ 、Ⅲ D.Ⅲ 、IV
[tag_link]
正确答案：B
对于一个线性表，既要求能进行较快速地插入和删除，又要求存储结构能反映数据之间 的逻辑关系，则应该用()。
A. 顺序存储方式 B. 链式存储方式 C. 散列存储方式 D. 以上均可以
[tag_link]
正确答案：B
链式存储设计时，结点内的存储单元地址()。
A. 一定连续 B. 一定不连续 C. 不一定连续 D. 部分连续，部分不连续
[tag_link]
正确答案：A
下列关于线性表的说法中，正确的是()。 I. 顺序存储方式只能用于存储线性结构 IⅡ . 在一个设有头指针和尾指针的单链表中，删除表尾元素的时间复杂度与表长无关 Ⅲ.带头结点的循环单链表中不存在空指针 IV. 在一个长度为n 的有序单链表中插入一个新结点并仍保持有序的时间复杂度为O(n) V. 若用单链表来表示队列，则应该选用带尾指针的循环链表
A. I、Ⅱ B.I 、Ⅲ 、IV 、V C. IV 、V D.Ⅲ 、IV 、V
[tag_link]
正确答案：
设线性表中有2n 个元素，()在单链表上实现要比在顺序表上实现效率更高。
A. 删除所有值为x 的元素 B. 在最后一个元素的后面插入一个新元素 C. 顺序输出前 k 个元素 D. 交换第i 个元素和第2n-i-1 个元素的值( i=0,…,n-1)
[tag_link]
正确答案：A
在一个单链表中，已知 q 所指结点是 p 所指结点的前驱结点，若在q 和 p 之间插入结点 s, 则执行( )。
A. s->next=p->next;p->next=s; B. p->next=s->next;s->next=p; C. q->next=s;s->next=p; D.p->next=s;s->next=q;
[tag_link]
正确答案：C
给定有n 个元素的一维数组，建立一个有序单链表的最低时间复杂度是()。
A. O(1) B.O(n) C.O(n²) D.O(nlog₂n)
[tag_link]
正确答案：D
将长度为 n 的单链表链接在长度为m 的单链表后面，其算法的时间复杂度采用大0形 式表示应该是()。
A. O(1) B.O(n) C.O(m) D.O(n+m)
[tag_link]
正确答案：C
单链表中，增加一个头结点的目的是()。
A. 使单链表至少有一个结点 B. 标识表结点中首结点的位置 C. 方便运算的实现 D. 说明单链表是线性表的链式存储
[tag_link]
正确答案：C
在一个长度为 n 的带头结点的单链表h 上，设有尾指针 r, 则执行()操作与链表的 表长有关。
A. 删除单链表中的第一个元素 B. 删除单链表中的最后一个元素 C. 在单链表第一个元素前插入一个新元素 D. 在单链表最后一个元素后插入一个新元素
[tag_link]
正确答案：B
对于一个头指针为head 的带头结点的单链表，判定该表为空表的条件是();对于不 带头结点的单链表，判定空表的条件为()。
A. head==NULL B.head->next==NULL C. head->next==head D.head!=NULL
[tag_link]
正确答案：【解答】
在线性表ao,a₁,…,a100 中，删除元素a50需要移动()个元素。
A. 0 B. 50 C. 51 D. 0 或50
[tag_link]
正确答案：D
通过含有n(n>1) 个元素的数组a, 采用头插法建立单链表L, 则 L中的元素次序()。
A. 与数组a 的元素次序相同 B. 与数组a 的元素次序相反 C. 与数组a 的元素次序无关 D. 以上都错误
[tag_link]
正确答案：B
下面关于线性表的一些说法中，正确的是()。
A. 对一个设有头指针和尾指针的单链表执行删除最后一个元素的操作与链表长度无关 B. 线性表中每个元素都有一个直接前驱和一个直接后继 C. 为了方便插入和删除数据，可以使用双链表存放数据 D. 取线性表第i 个元素的时间与i 的大小有关
[tag_link]
正确答案：C
在双链表中向 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;q->prior->next=q;q->next=p; D. p->prior->next=q;q->next=p;q->prior=p->prior;p->prior=q;
[tag_link]
正确答案：D
在双链表存储结构中，删除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;
[tag_link]
正确答案：A
在如下图所示的双链表中，已知指针p 指向结点 A, 若要在结点A 和 C 之间插入指针q 所指的结点B, 则依次执行的语句序列可以是()。 ①q->next=p->next;②q->prior=p;③p->next=q; ④p->next->prior=q; A.①②④③ B.④③②① C.③④①②
[tag_link]
正确答案：A
在双链表的两个结点之间插入一个新结点，需要修改()个指针域。
A. 1 B.3 C.4 D.2
[tag_link]
正确答案：【解答】
在长度为n 的有序单链表中插入一个新结点，并仍然保持有序的时间复杂度是()。 A.O(1) B.O(n) C.O(n²) D.O(nlog₂n)
[tag_link]
正确答案：【解答】
与单链表相比，双链表的优点之一是()。
A. 插入、删除操作更方便 B. 可以进行随机访问 C. 可以省略表头指针或表尾指针 D. 访问前后相邻结点更灵活
[tag_link]
正确答案：D
对于一个带头结点的循环单链表L, 判断该表为空表的条件是()。
A. 头结点的指针域为空 B.L 的值为NULL C. 头结点的指针域与L 的值相等 D. 头结点的指针域与L的地址相等
[tag_link]
正确答案：C
对于一个带头结点的循环双链表L, 判断该表为空表的条件是()。
A. L->prior==L&&L->next==NULL B.L->prior==NULL&&L->next==NULL C. L->prior==NULL&&L->next==L D.L->prior==L&&L->next==L
[tag_link]
正确答案：
一个链表最常用的操作是在末尾插入结点和删除结点，则选用()最节省时间。
A. 带头结点的循环双链表 B. 循环单链表 C. 带尾指针的循环单链表 D. 单链表
[tag_link]
正确答案：A
设对n(n>1) 个元素的线性表的运算只有4种：删除第一个元素；删除最后一个元素； 在第一个元素之前插入新元素；在最后一个元素之后插入新元素，则最好使用()。
A. 只有尾结点指针没有头结点指针的循环单链表 B. 只有尾结点指针没有头结点指针的非循环双链表 C. 只有头结点指针没有尾结点指针的循环双链表 D. 既有头结点指针又有尾结点指针的循环单链表
[tag_link]
正确答案：C
有两个长度为n 的循环单链表，若要求两个循环单链表头尾相接的时间复杂度为O(1), 则对应两个循环单链表各设置一个指针，分别指向()。
A. 各自的头结点 B. 各自的尾结点 C. 各自的首结点 D. 一个表的头结点，另一个表的尾结点
[tag_link]
正确答案：B
有一个长度为 n 的循环单链表，若从表中删除首元结点的时间复杂度达到 O(n), 则此 时采用的循环单链表的结构可能是()。
A. 只有表头指针，没有头结点 B. 只有表尾指针，没有头结点 C. 只有表尾指针，带头结点 D. 只有表头指针，带头结点
[tag_link]
正确答案：A
某线性表用带头结点的循环单链表存储，头指针为 head, 当 head->next->next== hea d 成立时，线性表的长度可能是()。
A. 0 B.1 C. 2 D. 可能为0或1
[tag_link]
正确答案：D
有两个长度都为n 的双链表，若以h₁为头指针的双链表是非循环的，以 h₂ 为头指针的 双链表是循环的，则下列叙述中正确的是()。
A. 对于双链表h₁, 删除首结点的时间复杂度是O(n) B. 对于双链表h₂, 删除首结点的时间复杂度是 O(n) C. 对于双链表h₁, 删除尾结点的时间复杂度是 O(1) D. 对于双链表h₂, 删除尾结点的时间复杂度是 O(1)
[tag_link]
正确答案：D
一个链表最常用的操作是在最后一个元素后插入一个元素和删除第一个元素，则选用() 最节省时间。
A. 不带头结点的循环单链表 B . 双链表 C. 单链表 D. 不带头结点且有尾指针的循环单链表
[tag_link]
正确答案：D
需要分配较大连续空间，插入和删除不需要移动元素的线性表，其存储结构为()。
A. 单链表 B. 静态链表 C. 顺序表 D. 双链表
[tag_link]
正确答案：B
下列关于静态链表的说法中，正确的是()。 I. 静态链表兼具顺序表和单链表的优点，因此存取表中第 i 个元素的时间与i 无关 II. 静态链表能容纳的最大元素个数在表定义时就确定了，以后不能增加 Ⅲ.静态链表与动态链表在元素的插入、删除上类似，不需要移动元素 IV. 相比动态链表，静态链表可能浪费较多的存储空间 prevdatanext32.【2016统考真题】已知一个带有表头结点的循环双链表L,结点结构为 prev data next 其中prev 和 next 分别是指向其直接前驱和直接后继结点的指针。现要删除指针 p 所 指的结点，正确的语句序列是()。
A. I 、Ⅱ 、Ⅲ B.Ⅱ 、Ⅲ 、IV C. I 、Ⅲ 、IV D.I 、Ⅱ 、IV A. p->next->prev=p-> prev;p- >prev->next=p->prev ;free (p); B.p->next->prev=p->next ;p->prev->next=p->next; free(p); C. p->next->prev=p->next ;p- >prev->next=p->prev ;free(p); D. p->next- >prev=p- >prev ;p-> prev->next=p->next; free(p);
[tag_link]
正确答案：B
在带头结点的单链表L 中，删除所有值为x 的结点，并释放其空间，假设值为x 的结点 不唯一，试编写算法以实现上述操作。
[tag_link]
B
试编写在带头结点的单链表L 中删除一个最小值结点的高效算法(假设该结点唯一)。
[tag_link]
B
试编写算法将带头结点的单链表就地逆置，所谓“就地”是指辅助空间复杂度为0(1)。
[tag_link]
A
设在一个带表头结点的单链表中，所有结点的元素值无序，试编写一个函数，删除表中 所有处于给定的两个值(作为函数参数给出)之间的元素(若存在)。
[tag_link]
给定两个单链表，试分析找出两个链表的公共结点的思想(不用写代码)。
[tag_link]
A
设 C={a,b₁,a₂,b₂,…,ambn} 为线性表，采用带头结点的单链表存放，设计一个就地算 法，将其拆分为两个线性表，使得A={a₁,a₂,…,a n},B={bn…,b₂,b₁}。
[tag_link]
C
在一个递增有序的单链表中，存在重复的元素。设计算法删除重复的元素，例如(7,10, 10,21,30,42,42,42,51,70)将变为(7,10,21,30,42,51,70)。
[tag_link]
D
设 A 和 B 是两个单链表(带头结点),其中元素递增有序。设计一个算法从A 和 B中 的公共元素产生单链表C, 要求不破坏A 、B的结点。
[tag_link]
C
已知两个链表A 和 B 分别表示两个集合，其元素递增排列。编制函数，求A 与 B 的交 集，并存放于A 链表中。
[tag_link]
C
两个整数序列A=a1,a2,a₃,…,am 和 B=b₁,b₂,b₃,…,b 已经存入两个单链表中，设计一 个算法，判断序列B 是否是序列A的连续子序列。
[tag_link]
B
设计一个算法用于判断带头结点的循环双链表是否对称。
[tag_link]
【解答】
有两个循环单链表，链表头指针分别为 h₁ 和 h₂, 编写一个函数将链表h₂ 链接到链表 h₁ 之后，要求链接后的链表仍保持循环链表形式。
[tag_link]
D
设有一个带头结点的非循环双链表L, 其每个结点中除有 pre 、data 和 next 域外， 还有一个访问频度域 freq, 其值均初始化为零。每当在链表中进行一次 Locate(L,x) 运算时，令值为 x 的结点中 freq 域的值增1,并使此链表中的结点保持按访问频度递 减的顺序排列，且最近访问的结点排在频度相同的结点之前，以便使频繁访问的结点总 是靠近表头。试编写符合上述要求的Locate(L,x) 函数，返回找到结点的地址，类型 为指针型。
[tag_link]
B
设将n(n>1) 个整数存放到不带头结点的单链表L 中，设计算法将L 中保存的序列循环 右移k(0<k<n) 个位置。例如，若k=1, 则将链表{0,1,2,3}变为{3,0,1,2}。要求： 1)给出算法的基本设计思想。 2)根据设计思想，采用C 或 C++语言描述算法，关键之处给出注释。 3)说明你所设计算法的时间复杂度和空间复杂度。
[tag_link]
C
单链表有环，是指单链表的最后一个结点的指针指向了链表中的某个结点(通常单链表 的最后一个结点的指针域是空的)。试编写算法判断单链表是否存在环。 1)给出算法的基本设计思想。 2)根据设计思想，采用C 或 C++语言描述算法，关键之处给出注释。 3)说明你所设计算法的时间复杂度和空间复杂度。
[tag_link]
D
设有一个长度 n(n 为偶数)的不带头结点的单链表，且结点值都大于0,设计算法求这 个单链表的最大孪生和。孪生和定义为一个结点值与其孪生结点值之和，对于第i 个结 点(从0开始),其孪生结点为第n-i-1 个结点。要求： 1)给出算法的基本设计思想。 2)根据设计思想，采用C 或 C++ 语言描述算法，关键之处给出注释。 3)说明你的算法的时间复杂度和空间复杂度。
[tag_link]
A