第一章 绪论

1.数据元素在计算机存储器内表示时，物理相对位置和逻辑相对位置相同并且是连续的，称之为（b ）。

A.逻辑结构

B.顺序存储结构

C.链式存储结构

D.以上都不对

---

2.以下数据结构中，（ a）是非线性结构

A.树

B.字符串

C.队列

D.栈、

1.线性结构是一个有序数据元素的集合。 其中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。

2.非线性结构中各个数据元素不再保持在一个线性序列中，每个数据元素可能与零个或者多个其他数据元素发生联系。
3.常用的线性结构有：线性表，栈，队列，双队列，数组，串。
? 常见的非线性结构有：多维数组，广义表，树(二叉树等)，图。

3.当输入规模为n时，下列算法渐进复杂性中最低的是（a）

A.5n

B.n^2

C.2n^2

D.n!

假设为10,则a=50 b=100 c=200 d=3628800，通过比较，可知a最小

4.算法的特性：一个算法必须满足有穷性、确定性、▁▁可行性▁▁▁、输入和输出等五个重要特性。

5.T(n)表示当输入规模为n时的算法效率，以下算法中效率最优的是(c )。

A.T(n)=T(n-1)+1,T(1)=1

B.T(n)=2n2

C.T(n)=T(n/2)+1,T(1)=1

D.T(n)=3nlog2?n

6设?0≤i,k<n，下面这段代码的时间复杂度是(a)

if (i>k) {
    for (j=i; j<n; j++)
        a[j] = a[j-k]+1;
}
else {
    for (j=i; j>0; j--)
        a[j] = a[k-j]+2;
}

A.O(n)

B.Θ(kn)

C.Ω(n)

D.Θ(nlogn)

即分为，[0,k][k,n]两个区间，两个区间相合并即为【0，n】,则0(n)