【考研数据结构】习题（一）

文章预览

基础知识习题

选择题

1. 算法的时间量大小称为算法的（）

A、效率 B、复杂性 </span> C、现实性 D、难度

解析：

算法中的基本操作的重复执行次数就是算法的计算量。

2. 算法的时间复杂度取决于（）

A、问题的规模 B、待处理数据的初态 <span style="color:red"> C、A和B </span>

解析：

算法的时间复杂度就是基本操作的执行次数，显然，问题规模越大，基本操作次数也就越多，但是，也跟待处理数据的初态有关，比如说：两个数字相乘，一个数为0时，和两个数都不为零的数相乘的情况下快。

3. 计算机算法是指（1），它必须具备（2）这三个特性

（1）A、计算方法 B、排序方法

​ C、解决问题的步骤和序列 D、调度方法

（2）A、可执行性、可移植性、可扩充性 B、可执行性、确定性、有穷性

​ C、确定性、有穷性、稳定性 D、易读性、稳定性、安全性

4. 一个算法应该是（）

A、程序 B、问题求解步骤描述 C、满足5个基本特征 D、A和C

5. 下面关于算法说法正确的是（）

A、算法最终必须由计算机程序实现

B、为解决某问题的算法同为该问题编写的程序含义是相同的

C、算法的可行性是指指令不能有二义性

D、以上几个都是错误的

解析：

A：计算机仅仅时算法实现的一种手段，手工也可以实现；

B：算法可以理解为由基本运算以及规定的运算顺序所构成的完整解题步骤；程序则是为实现特定目标或者这解决特定问题而用计算机语言编写出来的命令集合。

6.下面说法错误的是（）

（1）算法原地工作的含义是指不需要任何额外的辅助空间

（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2 ⁿ )的算法

（3）所谓的时间复杂度是指最坏的情况下，估算算法执行时间的上界

（4）同一个算法，实现语言的级别越高，执行效率就越低

A、（1） B、（1），（2） C、（1），（4） D、（3）

解析：

（1）：算法原地工作是指所需要的额外辅助空间时常数

（4）：太绝对，还需要参考编译环境等因素

7.从逻辑上可以把数据结构分为（）两大类

A、动态结构、静态结构 B、顺序结构、链式结构

**C、线性结构、非线性结构 ** D、初等结构、构造型结构

8.下述（）与数据结构的存储结构无关

A、栈 B、双向链表 C、散列表 D、线索树 E、循环队列

解析：

栈：逻辑结构

9.在下面程序中，对x赋值语句的频度为（）

for(i=0;i<n;++i)
    for(j=0;j<n;++j)
        ++x;

A、O（2n） B、O（n） C、O（n ² ） D、（log ₂ n）

10.程序段

for(i=n-1;i>=1;--i)
    for(j=1;j<=i;++j)
        if(a[j]>a[j+1])
            a[j]和a[j+1]对换

其中，n为正整数，则最后一个语句频度在最坏情况下是（）

A、O(n) B、O(nlog ₂ n) C、O(n ³ ) D、O(n ² )

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

**A、树 ** B、队 C、栈

12.连续存储设计时，存储单元的地址（）

A、一定连续 B、一定不连续 C、不一定连续 D、部分连续部分不连续

解析：

顺序存储结构要开辟一片连续的空间

13.以下属于逻辑结构的是（）

A、顺序表 B、散列表 **C、有序表 ** D、单链表

解析：

有序表指出:表中的数据是根据一定逻辑顺序排列的

综合应用

如下函数mergesort()的时间复杂度为多少？假设函数调用调用被写成mergesort(1,n)，函数merge()的时间复杂度为O(n)

void mergesort(int i,int j)
{
    int m;
    if(i != j)
    {
        m = (i+j)/2;
        margesort(i,m);
        margesort(m+1,j);
        marge(i,j,m);//此函数的时间复杂度为O(n)
    }
}

分析：

显然，数据规模为n，基本操作在函数marge()；marge()的时间复杂度为O(n)，因此我们可以假设marge()中的执行次数为cn,函数mergesort()的基本操作次数设为:f(n)，则：

由代码可以得知，当n为1时，f(1)=c

所以，当n=2 ^k (k=log ₂ n)时，f(n)=cn+cnlog ₂ n

因此，时间复杂度为

T(n)=O(n log ₂ n) *

………………………………