《数据结构》-数据结构试卷第一章.docx

《数据结构》期末复****题及参考答案- 第1章绪论
一、选择题
1、算法的时间复杂度取决于( )
B. 待处理数据的初态 C. A和B
2、计算机算法指的是(1),它必须具备(2) 这三个特性。
(1) B. 排序方法 C. 解决问题的步骤序列 D. 调度方法
(2) 、可移植性、可扩充性 B. 可执行性、确定性、有穷性
C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性
3、一个算法应该是( )。
.
4、以下的算法时间复杂度中,算法速度最快的是( )。
A. O(N) B. O(Nlog2N) C. O(N2) D. O(2N)
5、下面说法错误的是( )
(1)算法原地工作的含义是指不需要任何额外的辅助空间
(2)在相同的规模n下,复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法
(3)所谓时间复杂度是指最坏情况下,估算算法执行时间的一个上界
(4)同一个算法,实现语言的级别越高,执行效率就越低
A.(1) B.(1),(2) C.(1),(4) D.(3)
6、从逻辑上可以把数据结构分为( )两大类。
、静态结构 、链式结构
、非线性结构 、构造型结构
7、下面程序的时间复杂度为( )
for(i=0;i<m;i++)
for(j=0;j<n;j++) A[i][j]=i*j;
(A) O(M2) (B) O(N2) (C) O(M*N) (D) O(M+N)
8、如下程序算法的时间复杂度是( )。
void link (int arr[N])
{ int i, j, k;
for (i=0; i<N-1; i++)
for (j=i+1; j<N; j++)
if (arr[i] > arr[j]) { k = arr[i]; arr[i] = arr[j]; arr[j] = k;}
}
A. O(N) B. O(N2) C. O(log2N) D. O(2N)
9、以下数据结构中,(     )是非线性数据结构。 
                           
10、连续存储设计时,存储单元的地址(    )。
       ,部分不连续
二、填空题
1、数据的物理结构包括数据元素的表示和数据元素间关系的表示。
2、根据数据元素之间的逻辑关系,一般可以构造出四种逻辑结构分别是:集合、线性结构、树形结构、图状或网状结构。
3、数据的逻辑结构是指数据的组织形式,即数据元素之间逻辑关系的总体。而逻辑关系是指数据元素之间的关联方式或称“邻接关系”。
4、一个数据结构在计算机中表示(又称映像) 称为存储结构。
5、如果一个算法的时间复杂度是(N3+4N2log2N+3N)/N,那么用数量级表示的时间复杂度应该是O( N2 )。
6、抽象数据类型的定义仅取决于它的一组逻辑特性_, 而与在计算机内部如何表示和实现无关,即不论其内部结构如何变化,只要它的数学特性不变,都不影响其外部使用