基本信息

---

下载

文档摘要

---

计算机基础知识测评（练习版）试卷含答案

1.下列对顺序存储的有序表（长度为n）实现给定操作的算法中，平均时间复杂度为O(1)的是（）。

A.查找包含指定值元素的算法

B.插入包含指定值元素的算法

C.删除第i（1≤i≤n）个元素的算法

D.获取第i（1≤i≤n）个元素的算法(正确答案)

答案解析：线性表的顺序存储结构是随机存取结构，获取第i个元素时，可通过公式LOC(ai)=LOC(a1)+(i?1)×L直接计算地址，时间复杂度为O(1)。而查找、插入、删除操作均需遍历或移动元素，平均时间复杂度高于O(1)。

2.若采用三元组表存储结构存储稀疏矩阵M，则除三元组表外，下列数据中