【PTA】《数据结构与算法》线性结构复习题

<>总复习题

<>1、判断题

1-1 通过对堆栈S操作：Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S),
Pop(S)。输出的序列为：123。 (1分)
F

1-2 若一个栈的输入序列为1，2，3，…， N N N，输出序列的第一个元素是 i，则第 j个输出元素是 j − i − 1。 (1分)
F

1-3 若一个栈的输入序列为{1, 2, 3, 4, 5}，则不可能得到{3, 4, 1, 2, 5}这样的出栈序列。 (1分)
T

1-4 栈顶元素和栈底元素有可能是同一个元素。 (1分)
T

1-5 在具有N个结点的单链表中，访问结点和增加结点的时间复杂度分别对应为 O ( 1 )和 O ( N )。 (1分)
F

1-6 线性表L如果需要频繁地进行不同下标元素的插入、删除操作，此时选择顺序存储结构更好。 (1分)
F

1-7 In a singly linked list of N nodes, the time complexities for query and
insertion are O ( 1 ) and O ( N ) ,respectively. (1分)
（翻译：在单链表的N个节点中，查询和插入的时间复杂度分别为 O ( 1 )和 O ( n ) 。）
F

1-8 If N numbers are stored in a singly linked list in increasing order, then
the average time complexity for binary search is O(logN) O(logN). (1分)
（翻译：如果N个数按递增顺序存储在单链表中，则二分查找的平均时间复杂度为O(logN)。1-10）
F
解析
：链表不可以用二分查找法。根据链表的存储特性，查找链表中的数据时只能采用从头到尾的顺序来检索。而利用数组存储的数据进行二分查找的平均时间复杂度为O(logN)。

1-9 若用链表来表示一个线性表，则表中元素的地址一定是连续的。 (1分)
F

1-10 将 N 个数据按照从小到大顺序组织存放在一个单向链表中。如果采用二分查找，那么查找的平均时间复杂度是 O(logN)。(1分)
F

1-11 将长度分别为m,n的两个单链表合并为一个单链表的时间复杂度为 O(m+n)。 (1分)
F

1-12 在单链表中，要访问某个结点，只要知道该结点的指针即可。因此，单链表是一种随机存取结构。 (1分)
F

1-13 链表 - 存储结构
链表中逻辑上相邻的元素，其物理位置也一定相邻。 (1分)
F

1-14 链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。 (1分)
T

1-15 算法分析的两个主要方面是时间复杂度和空间复杂度的分析。 (1分)
T

1-16 对于某些算法，随着问题规模的扩大，所花的时间不一定单调增加。 (1分)
T

1-17 线性表的插入、删除总是伴随着大量数据的移动。 (1分)
F

1-18 算法可以没有输入，但是必须有输出。 (1分)
T

<>2、单选题

2-1 若元素a、b、c、d、e、f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈工作，则不可能得到的出栈序列是？(2分)
A. b c a e f d
B. c b d a e f
C. d c e b f a
D. a f e d c b

2-2 有六个元素以6、5、4、3、2、1的顺序进栈，问哪个不是合法的出栈序列？ (2分)
A. 2 3 4 1 5 6
B. 3 4 6 5 2 1
C. 5 4 3 6 1 2
D. 4 5 3 1 2 6

2-3 若一个栈的入栈序列为1、2、3、…、 N，输出序列的第一个元素是 i，则第 j 个输出元素是： (2分)
A. i − j − 1
B. i − j
C. j − i − 1
D. 无法确定

2-4 将5个字母ooops按此顺序入栈，则有多少种不同的出栈顺序可以仍然得到ooops？ (2分)
A. 1
B. 3
C. 5
D. 6

2-5 设一个堆栈的入栈顺序是1、2、3、4、5。若第一个出栈的元素是4，则最后一个出栈的元素必定是： (2分)
A. 1
B. 3
C. 5
D. 1或者5

2-6 给定一个堆栈的入栈序列为{ 1, 2,··· , n }，出栈序列为{p1,p2,⋅⋅⋅,pn}。如果p2=n，则存在多少种不同的出栈序列？(2分)
A. 1
B. 2
==C. n − 1 ==
D. n

2-7 以下不是栈的基本运算的是( )。 (2分)
A. 删除栈顶元素
B. 删除栈底元素
C. 判断栈是否为空
D. 将栈置为空栈

2-8 一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但单从运行时间来看， 通常递归过程比非递归过程（ ）。(2分)
A. 较快
B. 较慢
C. 相同
D. 无法确定

2-9 设顺序栈的栈顶指针（int 类型）指向栈顶元素位置，则判断一个栈ST（最多元素为MaxSize）为栈满的条件是（）。(2分)
A. ST.top != -1
B. ST.top ==-1
C. ST.top !==MaxSize - 1
D. ST.top == MaxSize - 1

2-10 假设一个栈的输入序列是1，2，3，4，则不可能得到的输出序列是（ ）。 (2分)
A. 1,2,3,4
B. 4,1,2,3
C. 4,3,2,1
D. 1,3,4,2

2-11 设一个堆栈的入栈顺序是1、2、3、4、5。若第一个出栈的元素是4，则最后一个出栈的元素必定是____。 (2分)
A. 1
B. 3
C. 5
D. 1或者5

2-12
为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是？(2分)
A. 堆栈
B. 队列
C. 树
D. 图

2-13 某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。若元素a、b、c、d、e依次入此队列后再进行出队操作，则不可能得到的出队序列是：(2分)
A. b a c d e
B. d b a c e
C. e c b a d
D. d b c a e

2-14 现有队列 Q 与栈 S，初始时 Q 中的元素依次是{ 1, 2, 3, 4, 5, 6 }（1在队头），S 为空。若允许下列3种操作：
（1）出队并输出出队元素；（2）出队并将出队元素入栈；（3）出栈并输出出栈元素，则不能得到的输出序列是：(2分)
A. 1, 2, 5, 6, 4, 3
B. 2, 3, 4, 5, 6, 1
C. 3, 4, 5, 6, 1, 2
D. 6, 5, 4, 3, 2, 1

2-15 设一数列的顺序为1，2，3，4，5，6，通过队列操作可以得到（ ）的输出序列。 (2分)
A. 3,2,5,6,4,1
B. 1,2,3,4,5,6
C. 6,5,4,3,2,1
D. 4,5,3,2,6,1

2-16 关于栈和队列的下列说法正确的是（） (2分)
A. 栈的插入操作是在栈顶进行，插入时需将栈内所有元素后移；
B. 栈是后进先出的结构，出栈时除了栈顶元素，其余元素无需移动；
C. 循环队列的出队操作删除的是队头元素，采用循环队列存储时，其余队列元素均需要移动；
D. 链队列的入队操作在表尾进行，操作时间与队列长度成正比

2-17 设栈S和队列Q的初始状态均为空，元素a、b、c、d、e、f、g依次进入栈S。若每个元素出栈后立即进入队列
Q，且7个元素出队的顺序是b、d、c、f、e、a、g，则栈S的容量至少是：
(2分)
A. 1
B. 2
C. 3
D. 4

2-18 设栈S和队列Q的初始状态均为空，元素{1, 2, 3, 4, 5, 6, 7}依次进入栈S。若每个元素出栈后立即进入队列Q，
且7个元素出队的顺序是{2, 5, 6, 4, 7, 3, 1}，则栈S的容量至少是：
(2分)
A. 1
B. 2
C. 3
D. 4

2-19 下列属于线性数据结构的是( )。 (2分)
A. 队列
B. 树
C. 图
D. 二叉树

2-20 队列的“先进先出”特性是指（　）。
Ⅰ.最后插入队列中的元素总是最后被删除
Ⅱ.当同时进行插入、删除操作时，总是插入操作优先
Ⅲ.每当有删除操作时，总要先做一次插入操作
Ⅳ.每次从队列中删除的总是最早插入的元素
(2分)
A. Ⅰ
B. Ⅰ、Ⅳ
C. Ⅱ、Ⅲ
D. Ⅳ

2-21 一个队列的入队序列是1，2，3，4，则队列的输出序列是( ) 。 (2分)
A. 4，3，2，1
B. 1，2，3，4
C. 1，4，3，2
D. 3，2，4，1

2-22 已知初始为空的队列 Q 的一端仅能进行入队操作，另外一端既能进行入队操作又能进行出队操作。若 Q 的入
队序列是 1、2、3、4、5，则不能得到的出队序列是：
(2分)
A. 5、4、3、1、2
B. 5、3、1、2、4
C. 4、2、1、3、5
D. 4、1、3、2、5

2-23 栈和队列的共同点是( ) (2分)
A. 都是先进后出
B. 都是后进先出
C. 只允许在端点处插入和删除元素
D. 没有共同点

2-24 已知队列(13，2，11，34，4l，77，5，7，18，26，15)，第一个进入队列的元素是13，则第五个出队列的
元素是( )。
(2分)
A. 41
B. 5
C. 77
D. 13

2-25 线性表若采用链式存储结构时，要求内存中可用存储单元的地址 (2分)
A. 必须是连续的
B. 连续或不连续都可以
C. 部分地址必须是连续的
D. 一定是不连续的

2-26 在具有 N个结点的单链表中，实现下列哪个操作，其算法的时间复杂度是 O(N)？ (2分)
A. 在地址为 p的结点之后插入一个结点
B. 删除开始结点
C. 遍历链表和求链表的第 i 个结点
D. 删除地址为 p 的结点的后继结点

2-27 线性表L在什么情况下适用于使用链式结构实现？ (2分)
A. 需不断对L进行删除插入
B. 需经常修改L中的结点值
C. L中含有大量的结点
D. L中结点结构复杂

2-28 链表不具有的特点是： (2分)
A. 插入、删除不需要移动元素
B. 方便随机访问任一元素
C. 不必事先估计存储空间
D. 所需空间与线性长度成正比

2-29 The following table shows how a linked list is stored in memory space
with the head node c :

（翻译：下表显示了链表如何与头部节点c一起存储在内存空间中：）

1014H
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.

（翻译：现在 f 存储在1014H，并插入到a和e之间的链表中。然后，a、e和f的“Link”字段分别为__。）
A. 1010H , 1014H , 1004H
B. 1010H , 1004H , 1014H
C. 1014H , 1010H , 1004H
D. 1014H , 1004H , 1010H

2-30 在单链表中，要删除某一指定结点，必须先找到该结点的（）。 (2分)
A. 直接前驱
B. 自身位置
C. 直接后继
D. 直接后继的后继

2-31 以下关于链式存储结构的叙述中，（）是不正确的。 (2分)
A. 结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构
B. 逻辑上相邻的结点物理上不必邻接
C. 可以通过计算直接确定第i个结点的存储地址
D. 插入、删除运算操作方便，不必移动结点

2-32 对于一个具有 N 个结点的单链表，在给定值为 的结点后插入一个新结点的时间复杂度为 (2分)
A. O ( 1 )
B. O ( N / 2 )
==C. O ( N ) ==
D. O O(N^2)

2-33 带头结点的单链表h为空的判定条件是： (2分)
A. h == NULL;
B. h->next == NULL;
C. h->next == h;
D. h != NULL;

2-34 链表 - 存储密度
链表的存储密度 ▁▁▁▁▁ 。
(2分)
A. 大于 1
B. 等于 1
C. 小于 1
D. 不能确定

2-35 在数据结构中，从逻辑上可以把数据结构分成（）。 (2分)
A. 动态结构和静态结构
B. 紧凑结构和非紧凑结构
C. 线性结构和非线性结构
D. 内部结构和外部结构

<>2.1绪论

<>1、判断题

1、算法分析的两个主要方面是时间复杂度和空间复杂度的分析。 T

2、在任何情况下，时间复杂度为O(n^2) 的算法比时间复杂度为O(n*logn)的算法所花费的时间都长。 F

3、O(n^2)，O(1+2+···+n) 对应的算法时间复杂度相同。 T

4、对于某些算法，随着问题规模的扩大，所花的时间不一定单调增加。 T

5、算法可以没有输入，但是必须有输出。 T

6、数据项是数据的最小单位。 T

7、数据元素是数据的最小单位。 F 基本单位

8、数据结构概念包括数据之间的逻辑结构、数据在计算机中的存储方式和数据的运算三个方面。 T

9、数据元素可以由类型互不相同的数据项构成。T

数据元素是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数据元素也称为元素、记录等。数据元素用于完整地描述一个对象。

10、算法的优劣与算法描述语言无关，但与所用计算机有关。 F

<>2、选择题

1、给定N×N的二维数组A，则在不改变数组的前提下，查找最大元素的时间复杂度是：
A O(N^2)
B O(NlogN)
C O(N)
D (N2logN)

2、以下数据结构中，（ ）是非线性数据结构。
A 树
B 字符串
C 队列
D 栈

3、下面程序段的时间复杂度是（）。
x=90; y=100; while(y>0) if(x>100) { x=x-10; y--; } else x++;
A O(1)
B O(N)
C O(N^{2})
D O(log_{2}N)

循环次数是常量，所以是常量级的时间复杂度。

4、下面代码段的时间复杂度是（）。
for ( i=0; i<n; i++ ) for ( j=0; j<m; j++ ) a[i][j]=0;
A O(1)
B O(mn)
C O(m^{2})
D O(n^{2})

5、下面代码段的时间复杂度是（）。
s=0; for ( i=0; i<n; i++ ) for( j=0; j<n; j++ ) s+=B[i][j]; sum=s;
A O(1)
B O(log2​n)
C O(n)
D O(n^{2})

6、数据的（）包括集合、线性结构、树形结构和图形结构四种基本类型。
A 存储结构
B 逻辑结构
C 基本运算
D 算法描述

7、下面的程序段违反了算法的（）原则。
void sam() { int n=2; while (n%2==0) n+=2; printf(“%d”,n); }
A 有穷性
B 确定性
C 可行性
D 健壮性

8、下列关于数据的逻辑结构的叙述中，（）是正确的。
A 数据的逻辑结构是数据元素间关系的描述
B 数据的逻辑结构反映了数据在计算机中的存储方式
C 数据的逻辑结构分为顺序结构和链式结构
D 数据的逻辑结构分为静态结构和动态结构

9、在数据结构中，从逻辑上可以把数据结构分成（）。
A 动态结构和静态结构
B 紧凑结构和非紧凑结构
C 线性结构和非线性结构
D 内部结构和外部结构

10、计算机算法必须具备输入、输出和（）等五个特性。
A 可行性、可移植性和可扩充性
B 可行性、确定性和有穷性
C 确定性、有穷性和稳定性
D 易读性、稳定性和安全性

11、在数据结构中，与所使用的计算机无关的数据结构是（）。
A 逻辑结构
B 存储结构
C 逻辑结构和存储结构
D 物理结构

12、下面程序的时间复杂度为（）。
for(i = 0; i < m; i++) for(j = 0; j < t; j++) c[i][j] = 0; for(i = 0; i < m;
i++) for(j = 0; j < t; j++) for(k = 0; k < n; k++) c[i][j] = c[i][j]+a[i][k] *
b[k][j];
A O(m × n × t)
B O(m + n + t)
C O(m + n × t)
D O(m × t + n)

13、下列程序段的时间复杂度为（）。
i = 1; k = 0; n = 100; do{ k = k + 10 * i; i = i++; }while(i != n)
A O(1)
B O(n)
C O(i)
D O(i × n)

14、算法分析的目的是（ ）。
A 找出数据结构的合理性
B 研究算法中的输入和输出的关系
C 分析算法的效率以求改进
D 分析算法的可读性和简明性

15、算法的时间复杂度与（ ）有关。
A 问题规模
B 计算机硬件的运行速度
C 源程序的长度
D 编译后执行程序的质量

16、某算法的时间复杂度是O(n^2)，表明该算法的（ ）。
A 问题规模是n^{2}
B 问题规模与n^{2}成正比
C 执行时间等于n^{2}
D 执行时间与n^{2}成正比

17、下列代码的时间复杂度是：
if ( A > B ) { for ( i=0; i<N*N/100; i++ ) for ( j=N*N; j>i; j-- ) A += B; }
else { for ( i=0; i<N*2; i++ ) for ( j=N*3; j>i; j-- ) A += B; }
A O(N^{3})
B O(N^{4})
C O(N^{5})
D O(N^6)

18、Choose the time complexity of the following code:
x=0; for(i=0;i<n;i++) for(j=0;j<i*i;j++) x++;
A O(N^2)
B O(N^{3})
C O(N^2 * logN)
D O(N^3 * logN)

19、下列代码的时间复杂度是：
for(i=0; i<n; i++) for(j=i; j>0; j/=2) printf(“%d\n”, j);
A O(N×i)
B O(N)
C O(N^2)
D O(NlogN)

20、要判断一个整数N（>10）是否素数，我们需要检查3到\sqrt{N}之间是否存在奇数可以整除N。则这个算法的时间复杂度是：
A O(N/2)
B O(\sqrt{N})
C O(\sqrt{N}logN)
D O(0.5logN)

<>2.2顺序表

<>1、判断题

1、数据的逻辑结构是指数据的各数据项之间的逻辑关系。 F

数据的逻辑结构是指数据的各数据元素之间的逻辑关系。

2、顺序表中逻辑上相邻的元素，其物理位置也一定相邻。 == T==

3、顺序表是一种随机存取的存储结构。 T

4、链表中逻辑上相邻的元素，其物理位置也一定相邻。 F

5、顺序存储设计时，存储单元的地址一定连续。 T

6、在N个结点的顺序表中访问第i（1<=i<=N）个结点和求第i（2<=i<=N）个结点直接前驱的算法时间复杂度均为O(1)。 T

7、线性表采用链式存储结构时，各个数据元素的存储单元地址一定是不连续的。 F

8、线性表L如果需要频繁地进行不同下标元素的插入、删除操作，此时选择顺序存储结构更好。 F

9、非空线性表可以有多个开始结点。 F

10、非空线性表中每个结点都有一个前驱结点。 F

11、非空线性表除终端结点外，每个结点都有唯一的后继结点。 T

12、非空线性表中每个结点都有一个后继结点。== F==

13、对于顺序存储的长度为N的线性表，访问结点和增加结点的时间复杂度分别对应为O(1)和O(N)。 T

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

15、对于顺序存储的长度为N的线性表，删除第一个元素和插入最后一个元素的时间复杂度分别对应为O(1)和O(N)。 F

16、在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。 T

17、顺序存储方式只能用于存储线性结构。 F

18、顺序存储的线性表可以随机存取。 T

19、顺序存储结构的主要缺点是不利于插入或删除操作。 T

20、在顺序表中逻辑上相邻的元素，其对应的物理位置也是相邻的。 T

<>2、选择题

1、对于顺序存储的长度为N的线性表，访问结点和增加结点的时间复杂度为：
A O(1),O(1)
B O(1),O(N)
C O(N),O(1)
D O(N),O(N)

2、在N个结点的顺序表中，算法的时间复杂度为O(1)的操作是：
A 访问第i个结点（1≤i≤N）和求第i个结点的直接前驱（2≤i≤N）
B 在第i个结点后插入一个新结点（1≤i≤N）
C 删除第i个结点（1≤i≤N）
D 将N个结点从小到大排序

3、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用哪种存储方式最节省时间？
A 双链表
B 单循环链表
C 带头结点的双循环链表
D 顺序表

4、顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ ）。
A 100
B 105
C 108
D 110

100+2*4=108

5、用数组表示线性表的优点是（）。
A 便于插入和删除操作
B 便于随机存取
C 可以动态地分配存储空间
D 不需要占用一片相邻的存储空间

6、若长度为n的线性表采用顺序结构，在第i个数据元素之前插入一个元素，需要它依次向后移动（）个元素。
A n-i
B n-i+1
C n-i-1
D i

在第i个之前插入，i后边有n-i个，再加上第i个本身，就是n-i+1

7、顺序存储表示中数据元素之间的逻辑关系是由（ ）表示的。
A 指针
B 逻辑顺序
C 存储位置
D 问题上下文

顺序存储结构是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系的。

8、在以下有关顺序表的叙述中正确的是（ ）。
A 顺序表的优点是存储密度高，且插入与删除运算的时间效率高
B 集合与顺序表的区别在于集合中的元素不能相等
C 线性表就是顺序存储的表
D 取顺序表第i个元素的时间与i的大小有关

9、阅读下列程序，其功能是（）。
typedef struct { ElemType *list; int size; intMaxSize; }SeqList; void
fun1(SeqList&L) { inti, j; ElemType temp; for (i=0, j= L.sise-1; i<j; i++, j--)
{ temp=L.list[i]; L.list[i]=L.list[j]; L.list[j]=temp; } }
A 将顺序表原地逆置
B 将链表原地逆置
C 将顺序表首尾元素对换
D 将链表首尾元素对换

10、已知线性表中的元素以值递增有序排列，阅读下列程序，该算法的功能是（）。
typedef struct { ElemType *list; int size; intMaxSize; }SeqList; void
fun3(SeqList&L, ElemType min, ElemType max){ inti=0, j, k, d;
while(i<L.size&&L.list[i]<=min) i++; j = i; while (j<L.size&&L.list[j]<max)
j++; d = j-i; if ( d==0) return; for (k=j; k<L.size; k++) L.list[k-d] =
L.list[k]; size = L.size - d; }
A 删除顺序表中所有值小于min或大于max的元素
B 将顺序表中值大于min且小于max的元素向前移动
C 将顺序表中值大于max的元素向前移动min个位置
D 删除顺序表中所有值大于min且小于max的元素

***11、已知A、B和C为3个元素递增有序的顺序表，且同一个表中元素值各不相同，下列算法对A做如下操作：删除那些既在表B又在表C中出现的元素。请将该算法补充完整。
typedef struct { ElemType *list; int size; intMaxSize; }SeqList; void
deletesame(SeqList&A, SeqList B, SeqList C) { inti=0, j=0, k=0, m; ElemType
same; while (i<A.size&& j<B.size&& k<C.size) { if (C.list[k] <B.list[j]) k++;
else if (C.list[k] >B.list[j]) j++; else { same=B.list[j]; while
(i<A.size&&A.list[i]<same) i++; if (i<A.size&&A.list[i]==same) { m=i+1; while
(m<A.size) { ________________ } A.size--; j++;k++; } } } }
A A.list[m]=A.list[m-1]; m++;
B A.list[m-1]=A.list[m]; m++;
C A.list[m++]=A.list[k++];
D A.list[m++]=A.list[j++];

12、在包含 n个数据元素的顺序表中，▁▁▁▁▁ 的时间复杂度为 O(1)。
A 访问第 i 个数据元素
B 在第 i(1≤i≤n) 个结点后插入一个新结点
C 删除第 i(1≤i≤n) 个结点
D 将 n 个元素按升序排序

13、在一个长度为n的顺序表中，删除第i个元素(1≤i≤n)时需要移动（ ）个元素。
A n-i
B n-i+1
C n-i-1
D i

14、将两个各有n个元素的递增有序顺序表归并成一个有序顺序表，其最少的比较次数是( )
A n
B 2n-1
C 2n
D n-1

15、等概率情况下，在表长为n的顺序表中插入一个元素所需移动的元素平均个数为（ ）
A (n-1)/2
B n/2
C (n+1)/2
D n-i

从头插入到在尾部插入，需要移动n个到0个共n+1种情况，n*(n+1)/2(n+1)=n/2

16、（ ）结构中的结点最多只有一个前驱和一个后继。
A 二叉树
B 图
C 线性表
D 以上都不是

17、线性表L=(a1​，a2​，…，an​)，下列说法正确的是（ ）
A 每个元素都有一个直接前驱和一个直接后继
B 表中至少有一个元素
C 表中元素需有序
D 除第一个和最后一个元素外，其他元素都有且仅有一个直接前驱和一个直接后继

18、在n个数据元素的顺序表中，算法时间复杂度为O(1)的操作是（ ） (1) 访问第i个结点（1≤i≤n） (2) 求第i个结点的直接前驱（2≤i≤n）
(3) 求第i个结点的直接后继（1≤i≤n-1） (4) 在第i个结点后插入一个新结点（1≤i≤n） (5) 删除第i个结点（1≤i≤n） (6) 排序
A (1)(2)(3)(4)(5)
B (1)(2)(3)
C (4)(5)
D (6)

19、线性表(a1​，a2​，…，an​)以顺序存储结构存储时，访问第i位置元素的时间复杂度为（ ）
A O(1)
B O(n)
C O(i)
D O(i-1)

20、顺序表中第1个元素的存储地址是2000，每个元素的长度为4，则第5个元素的地址是（ ）
A 2020
B 2016
C 2024
D 2012

2000+4*4=2016

• « 上一篇：linux文件查看和文件查找
• » 下一篇：什么是C#？与常见的基本数据类型