数据结构错题收录（一）

1、以下属于逻辑结构的是（）

• A：顺序表
• B：哈希表
• C：有序表
• D：单链表

解析

顺序表、哈希表和单链表是三种不同的数据结构，既描述逻辑结构，又描述存储结构和数据运算。而有序表是指关键字有序的线性表，仅描述元素之间的逻辑关系，它既可以链式存储，又可以顺序存储，故属于逻辑结构。

答案：C

2、链式存储设计时，结点内的存储单元地址（）。

• A：一定连续
• B：一定不连续
• C：不一定连续
• D：部分连续，部分不连续

解析

链式存储设计时，各个不同结点的存储空间可以不连续，但结点内的存储单元地址必须连续。

答案：A

3、对于两种不同的数据结构，逻辑结构或物理结构一定不相同吗？

数据的运算也是数据结构的一个重要方面。
对于两种不同的数据结构，它们的逻辑结构和物理结构完全有可能相同。比如二叉树和二叉排序树，二叉排序树可以采用二叉树的逻辑表示和存储方式，前者通常用于表示层次关系，而后者通常用于排序和查找。虽然它们的运算都有建立树、插入结点、删除结点和查找结点等功能，但对于二叉树和二叉排序树，这些运算的定义是不同的，以查找结点为例，二叉树的时间复杂度为O(n)，而二叉排序树的时间复杂度为O()。

4、试举一例，说明对相同的逻辑结构，同一种运算在不同的存储方式下实现时，其运算效率不同。

线性表既可以用顺序存储方式实现，又可以用链式存储方式实现。在顺序存储方式下，在线性表中插入和删除元素，平均要移动近一半的元素，时间复杂度为O(n)；而在链式存储方式下，插入和删除的时间复杂度都是O(1)。

5、下面关于倒排文件的说法中正确的是____。

• A：倒排文件是对主关键字建立索引
• B：倒排文件是对次关键字建立索引
• C：倒排文件的优点是维护简单
• D：采用倒排文件是为了节省存储空间

解析

倒排文件：用记录的非主属性（也叫副键）来查找记录而组织的文件叫倒排文件，即次索引。倒排文件中包括了所有副键值，并列出了与之有关的所有记录主键值，主要用于复杂查询。倒排文件的优点是检索记录较快。特别是对某些询问，不用读取记录，就可得到解答。

答案：B

6、下列术语中，____与数据的存储结构无关。

• A：循环队列
• B：堆栈
• C：散列表
• D：单链表

解析

数据的存储结构有顺序存储、链式存储、索引存储和散列存储。栈是一种抽象数据类型，可采用顺序存储或链式存储，是一种逻辑结构。散列表和单链表表示几种数据结构，既描述逻辑结构，又描述存储结构。

答案：B

7、下面程序的时间复杂度为____。

for (i = 1, s= 0 ; i < n ; i++)
{
    t = 1 ;
    for(j =1 ; j<=i;j++)
    {
        t=t*j;
    }
    s=s+t;
}

• A：O(n)
• B：O()
• C：O()
• D：O()

解析

分析代码：内层循环执行i次，外层循环执行n次，i从1取到n。
得知执行最内层循环语句总次数为，即O()。

答案：B

8、下面算法的时间复杂度是____。

Void fun(int n)
{
    int i = 0,s = 0;
    while(s<n)
    {
        ++i;
        s=s+i;
    }
}

• A：O(n)
• B：O()
• C：O()
• D：O()

解析

最底层的代码为s=s+i，s到达n的过程刚好是1+2+3+4....+m这样累加起来的，根据等差队列之和的公式，(1+m)*m=2n，故m约等于根号n，所以此题选C。

答案：C

9、下面算法的空间复杂度为_____。

float aver(float a[n])
{
    int j;
    for(j=n;j>0;j--)
        printf("%8.2f",a[j]);
}

• A：O(1)
• B：O()
• C：O(n)
• D：O()

解析

函数体定义中出现数组，数组在初始化时需要分配空间，此时空间复杂度为O(n)，所以选C。

答案：C

10、已知程序如下所示，程序运行时使用栈来保存调用过程的信息，自栈底到栈顶保存的信息依次对应的是____。

int S(int n){
    return (n<=0)?0:S(n-1)+n;
}

void main(){
    cout<<S(1);
}

• A ：main()->S(1)->S(0)
• B：S(0)->S(1)->main()
• C：main()->S(0)->S(1)
• D：S(1)->S(0)->main()

解析

程序都是从main函数开始的，进入main函数后执行S(1)，之后递归执行S(0)。

答案：A

学海无涯苦作舟