CS408/Data-Structrue/0-summary-ex.md

概述习题

数据结构

例题 以下关于数据结构的说法中，正确的是()。

$A.$数据的逻辑结构独立于其存储结构

$B.$数据的存储结构独立于其逻辑结构

$C.$数据的逻辑结构唯一决定其存储结构

$D.$数据结构仅由其逻辑结构和存储结构决定

解：$A$。数据的逻辑结构是从面向实际问题的角度出发的，只采用抽象表达方式，独立于存储结构；而数据的存储结构是逻辑结构在计算机上的映射，它不能独立于逻辑结构而存在；数据结构包括三个要素，缺一不可。

例题 在存储数据时，通常不仅要存储各数据元素的值，而且要存储()。

$A.$数据的操作方法

$B.$数据元素的类型

$C.$数据元素之间的关系

$D.$数据的存取方法

解：$C$。在存储数据时，不仅要存储数据元素的值，而且要存储数据元素之间的关系。

例题 链式存储设计时，结点内的存储单元地址()。

$A.$一定连续

$B.$一定不连续

$C.$不一定连续

$D.$部分连续，部分不连续

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

算法

算法概念

例题 一个算法应该是()。

$A.$程序

$B.$问题求解步骤的描述

$C.$要满足五个基本特性

$D.A$和C

解：$B$。$A$算法不是程序，且$C$是算法的特性，其不能作为算法的定义。

效率度量

一般一个循环就是一个$n$，嵌套的两个循环就是$n^2$。如果实在不能计算出来就直接代入值计算。

首先设执行次数为$t$，然后根据基本运算（执行频率最高的语句，一般是最后一句）来计算$t$次计算后的结果，代入循环条件反推出$n$，然后来看复杂度。

例题 以下算法的时间复杂度为()。

void fun (int n) {
    int i=1;
    while(i<=n)
        i=i*2;
}

A.O(n)

B.O(n^2)

C.O(n\log_2n)

D.O(\log_2n)

解：$D$。根据基本运算：i=i*2，令执行次数为$t$，所以假如在执行中，即满足$i\leqslant n$，则$t$次时运算结果为$2^t$，从而$2^t\leqslant n$，解得$t\leqslant\log_2n$，所以时间复杂度为$O(\log_2n)$。

或者简单一点来看，默认一个循环，循环条件为一个简单的小于$n$，则时间复杂的为$O(n)$，而循环中对$n$进行计算，使$n$按照$2^n$的速度增长，所以最后时间复杂度就变成了$O(\log_2n)$。

例题 设$n$是描述问题规模的非负整数，下面的程序片段的时间复杂度是()。

void fun (int n) {
    x=2;
    while(x<n/2);
    x=2*x;
}

A.O(\log_2n)

B.O(n)

c.O(n\log_2n)

D.O(n^2)

解：$A$。基本运算为x=2*x，每执行一次就乘$2$，令执行次数为$t$，则第$t$运算结果为$2^{t+1}<n/2$，解得$t<\log_2(n/2)-1=\log_2n-2$，所以时间复杂度为$O(\log_2n)$。

例题 求整数$n$（$n\geqslant0$）的阶乘的算法如下，其时间复杂度是()。

int fact (int n) {
    if (n<=1) return 1;
    return n*fact(n-1);
}

A.O(\log_2n)

B.O(n)

c.O(n\log_2n)

D.O(n^2)

解：$B$。这显然是一个计算阶乘的程序。计算结果为$n\times(n-1)\times\cdots\times1$，一共计算$n$次，所以时间复杂度为$O(n)$。

例题 下列函数的时间复杂度是()。

int func(int n) {
    int i = 0, sum = 0;
    while(sum < n) sum += ++i;
    return i;
}

A.O(\log n)

B.O(n^{\frac{1}{2}})

C.O(n)

D.O(n\log n)

解：$B$。首先把sum += ++i;拆开，这是两个程序语句：++i;sum += i;，即先$i$自加，再$sum+i$。基本运算不能直接推出，所以使用归纳法，$i=1$，$sum=0+1;$，$i=2$，$sum=0+1+2;$，令执行次数为$t$，从而得到$sum=0+1+\cdots+t=(1+t)t/2$，所以$t+t^2<2n$，所以时间复杂度为$O(n^\frac{1}{2})$。

例题 以下算法中最后一个语句的执行次数为()。

int m=0, i, j;
for(i = 1; i <= n ; i++)
    for(j = 1; j <= 2*i; j++)
        m++;

A.n(n+1)

B.n

c.n+1

D.n^2

解：$A$。根据两次循环可以根据计算法则：$=\sum\limits_{i=1}^n\sum\limits_{j=1}^{2i}1=\sum\limits_{i=1}^n2i=2\sum\limits_{i=1}^ni=2(1+\cdots+n)=2\times(n+1)n\div2=(n+1)n$。

例题 下面说法中，错误的是()。

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

Ⅱ.在相同规模$n$下，复杂度为$O(n)$的算法在时间上总是优于复杂度为$O(2^n)$的算法

Ⅲ.所谓时间复杂度，是指最坏情况下估算算法执行时间的一个上界

Ⅳ.同一个算法，实现语言的级别越高，执行效率越低

$A.$Ⅰ

$B.$Ⅰ，Ⅱ

$C.$Ⅰ，Ⅳ

$D.$Ⅰ

解：$A$。Ⅰ是定义，指的是耗费空间是常数级而不是不用。Ⅱ考察复杂度的定义，时间复杂度是渐进时间复杂度，不能直接赋值或利用函数图像去说必然优于。Ⅲ是对的，时间复杂度总是考虑最坏情况以保证运行时间不会比其更长。Ⅳ而言是书上所给，一般而言是对的。

例题 设$n$是描述问题规模的非负整数，下列程序段的时间复杂度是()。

int fun(int n) {
    x = 0;
    while (n>=(x+1)*(x+1))
        x=x+1;
}

A.O(\log n)

B.O(n^\frac{1}{2})

C.O(n)

D.O(n^2)

解：$A$。令执行次数为$t$，基本运算是$t+1$，然后第$t$次$x+1=t$，所以根据判断条件$t^2>n$，所以解得$t>\sqrt{n}$，所以$O(n^\frac{1}{2})$。 2^k 例题 一个算法所需时间由下述递归方程表示，试求出该算法的时间复杂度的级别（或阶)。

T(n)=\left\{\begin{array}{lc} 1, & n=1 \\ 2T(n/2)+n , & n>1 \end{array}\right. 式中，$n$是问题的规模，为简单起见，设$n$是$2$的整数次幂。

解：设$n$是$2$的整数次幂，所以设$n=2^k$，当执行$k$次时，$n=1$跳出循环。当$n>1$时，$T(2^k)=2T(2^{k-1})+2^k$，又$T(2^{k-1})=2T(2^{k-2})+2^{k-1}$，所以$T(2^k)=4T(2^{k-2})+2\times2^k$，根据递推式规律所以得到$T(2^k)=2^iT(2^{k-i})+i\times2^k$，即$T(2^k)=2^kT(1)+k\times2^k=2^k+k\times2^k=(k+1)\times2^k$，即$T(n)=(\log_2n+1)\times n$，即$O(n\log_2n)$。