- 1.以下关于数据结构的说法中正确的是____。
A数据结构的逻辑结构于其存储结构
B数据结构的存储结构于该数据结构的逻辑结构
C数据结构的逻辑结构唯一地决定了该数据结构的存储结构
D数据结构仅由其逻辑结构和存储结构决定 - 2.某算法的时间复杂度是O(n2 )，表明该算法的（ ）。
问题规模是n2
问题规模与n2成正比
执行时间等于n2
执行时间与n2成正比 - 3.数据在计算机内存中的表示是指（） 。
数据的存储结构
数据结构
数据的逻辑结构
数据元素之间的关系 - 4.下列代码
-
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;
}
的时间复杂度是：O（N4）
if语句的时间复杂度是O（N4），else语句中的时间复杂度是O（N2），这里一定要注意是N2，N3，而不是二次方三次方。 - 5.链式存储的存储结构所占存储空间（ ）
A.分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 - 6.下面代码段的时间复杂度是()
-
int func ( int n )
{ int i = 0, sum = 0;
while ( sum < n ) sum += ++i;
return i;
}
B.O(n1/2)
-
-
8.下面说法错误的是（ ）。
（1）算法原地工作的含义是指不需要任何额外的辅助空间。
（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2^n)的算法。
（3）所谓最坏时间复杂度是指最坏情况下，估算算法执行时间的一个上界。
（4）同一个算法，实现语言的级别越高，执行效率就越低。
B.(1),(2)
-
简答题
顺序存储结构和链式存储结构的优缺点比较，以及使用情况。
1 优缺点
优点：存储密度大（＝1），存储空间利用率高。缺点：插入或删除元素时不方便。
②链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（<1），存储空间利用率低。
-
判断题
- 算法可以没有输入，但是必须有输出 对（一个算法可以有0个或多个输入，而要有一个或多个输出。）
- Nlog(N2)和NlogN具有相同的增长速度 对
- N2logN和NlogN2 具有相同的增长速度 错
- 在顺序表中取出第i个元素所花费的时间与i成正比。错（非线性关系，因为是顺序表并且知道是第i个，相当于知道了具体位置。所以时间复杂度为O(1)）
-
-
对于顺序存储的长度为N的线性表，访问结点和增加结点的时间复杂度分别对应为O(1)和O(N)。对
-
在具有N个结点的单链表中，访问结点和增加结点的时间复杂度分别对应为O(1)和O(N)。 错
-
在带头结点的非空单链表中，头结点的存储位置由前驱结点指示。错（它是单链表，怎么可能由前驱节点指示呢）
-
.在双向链表中，可以从当前结点出发访问到任何一个结点。对
-
数据结构基本操作的设置准则是，实现应用程序与存储结构的。 对
