第 2 章 线性表
1.选择题
(1)顺序表中第一个元素的存储地址是 100,每个元素的长度为 2,则第 5 个元素的地址是
( )。
A.110 B.108 C.100 D.120
答案:B
解释:顺序表中的数据连续存储,所以第 5 个元素的地址为:100+2*4=108。
(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 个结点从小到大排序
答案:A
解释:在顺序表中插入一个结点的时间复杂度都是 O(n
2
),排序的时间复杂度为 O(n
2
)或 O(nlog
2
n)。
顺序表是一种随机存取结构,访问第 i 个结点和求第 i 个结点的直接前驱都可以直接通过数组的
下标直接定位,时间复杂度是 O(1)。
(3) 向一个有 127 个元素的顺序表中插入一个新元素并保持原来顺序不变,平均要移动 的元
素个数为( )。
A.8 B.63.5 C.63 D.7
答案:B
解释:平均要移动的元素个数为:n/2。
(4)链接存储的存储结构所占存储空间( )。
A.分两部分,一部分存放结点值,另一部分存放表示结点间关系的指针
B.只有一部分,存放结点值
C.只有一部分,存储表示结点间关系的指针
D.分两部分,一部分存放结点值,另一部分存放结点所占单元数
答案:A
(5)线性表若采用链式存储结构时,要求内存中可用存储单元的地址( )。
A.必须是连续的 B.部分地址必须是连续的
C.一定是不连续的 D.连续或不连续都可以
答案:D
(6)线性表L在( )情况下适用于使用链式结构实现。
A.需经常修改L中的结点值 B.需不断对L进行删除插入
C.L中含有大量的结点 D.L中结点结构复杂
答案:B
解释:链表最大的优点在于插入和删除时不需要移动数据,直接修改指针即可。
(7)单链表的存储密度( )。
A.大于 1 B.等于 1 C.小于 1 D.不能确定
答案:C
评论0