王道计算机数据结构考研——绪论

题目

数据结构的基本概念

一、单项选择题

可以用（）定义一个完整的数据结构。

A. 数据元素
B. 数据对象
C. 数据关系
D. 抽象数据类型
答案：D。抽象数据类型（ADT）描述了数据的逻辑结构和抽象运算，通常用（数据对象，数据关系，基本操作集）这样的三元组来表示，从而构成一个完整的数据结构定义

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

A. 树
B. 字符串
C. 队列
D. 栈
答案：A。树和图是典型的非线性数据结构，其他选项都属于线性数据结构。

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

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

以下与数据的存储结构无关的术语是（）。

A. 循环队列
B. 链表
C. 队列
D. 抽象数据类型
答案：D。数据的存储结构有顺序存储、链式存储、索引存储和散列存储。循环队列（易错点）是用顺序表表示的队列，是一种数据结构。栈是一种抽象数据类型，可采用顺序存储或链式存储，只表示逻辑结构。

以下关于数据结构的说法中，正确的是（）。

A. 数据的逻辑结构独立于其存储结构
B. 数据的存储结构独立于其逻辑结构
C. 数据的逻辑结构唯一决定其存储结构
D. 数据结构仅由其逻辑结构和存储结构决定
答案：A。数据的逻辑结构是从面向实际问题的角度出发的，只采用抽象表达方式，独立于存储结构，数据的存储方式有多种不同的选择；而数据的存储结构是逻辑结构在计算机上的映射，它不能独立于逻辑结构而存在。数据结构包括三个要素，缺一不可。

在存储数据时，通常不仅要存储各数据元素的值，而且要存储（）。

A. 数据的操作方法
B. 数据元素的类型
C. 数据元素之间的关系
D. 数据的存取方法
答案：C。在存储数据时，不仅要存储数据元素的值，而且要存储数据元素之间的关系。

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

A. 一定连续
B. 一定不连续
C. 不一定连续
D. 部分连续，部分不连续
答案：A。链式存储设计时，各个不同结点的存储空间可以不连续，但结点内的存储单元地址必须连续

二、综合应用题

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

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

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

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

算法和算法评价

一、单项选择题

一个算法应该是（）。

A. 程序
B. 问题求解步骤的描述
C. 要满足五个基本特性
D. A 和 C
答案：B。本题是中山大学考研真题，题目本身没有问题，考查的是算法的定义。程序不一定满足有穷性, 如死循环、操作系统等，而算法必须有穷。算法代表对问题求解步骤的描述，而程序则是算法在计算机上的特定实现。不少读者认为C也对，它只是算法的必要条件，不能成为算法的定义。

某算法的时间复杂度为 $O(n^2)$，表明该算法的（）。

A. 问题规模是 $n^2$
B. 执行时间等于 $n^2$
C. 执行时间与 $n^2$ 成正比
D. 问题规模与 $n^2$ 成正比
答案：时间复杂度为$O(n^2)$,说明算法的时间复杂度$T(n)$满足$T(n) \leq cn^2$ (c为比例常数)，即$T(n)=O(n^2)$ 。时间复杂度$T(n)$是问题规模$n$的函数，其问题规模仍然是$n$而不是$n^2$。

以下算法的时间复杂度为（）。

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

A. $O(n)$
B. $O(n^2)$
C. $O(nlog_2n)$
D. $O(log_2n)$
答案：D。找出基本运算i=i*2,设执行次数为$t$，则$2^t \leq n$即$t \leq log_2n$，因此时间复杂度$T(n)=O(log_2n)$
- 更直观的方法：计算基本运算i=i*2的执行次数(每执行一次i乘2),其中判断条件可理解为$2^t=n$，即$t=log_2n$，则$T(n)=O(log_2n)$ (注意,本方法可灵活运用到第4题和第8题。)

有以下算法，其时间复杂度为（）。

void fun(int n){ 
  int i = 0;
  while (i * i * i <= n)
    i++;
}

A. $O(n)$
B. $O(nlogn)$
C. $O(\sqrt[3]{n})$
D. $O(\sqrt{n})$
答案：C。基本运算为i++,设执行次数为$t$，有$t \times t \times t \leq n$，即$t^3 \leq n$，故有$t \leq \sqrt[3]{n}$，则$T(n)=O(\sqrt[3]{n})$。

程序段如下，其时间复杂度是（）。

for (int i = n - 1; i > 1; i--) {
  for (int j = 1; j < i; j++) {
    if (A[j] > A[j + 1]) {
      // 交换 A[j] 和 A[j + 1]
    }
  }
}

A. $O(n)$
B. $O(nlogn)$
C. $O(n^3)$
D. $O(n^2)$
答案：D。这是冒泡排序的算法代码，考查最坏情况下的元素交换次数(若觉得理解困难可在学完第8 第1章绪论009 章后再回顾)。当所有相邻元素都为逆序时，则最后一行的语句每次都会执行。此时： \[ T(n)=\sum\limits_{i=2}^{n-1} \sum\limits_{j=1}^{i-1}1=\sum\limits_{i=2}^{n-1}i-1=(n-2)(n-1)/2=O(n^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。 m++语句的执行次数为： \[ \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{2*i}1=\sum\limits_{i=1}^{n}2i=2\sum\limits_{i=1}^{n}i=n(n+1) \]

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

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

A. $O(log_2n)$
B. $O(n)$
C. $O(nlog_2n)$
D. $O(n^2)$
答案：基本运算(执行频率最高的语句)为x=2*x,每执行一次x乘2,设执行次数为t,则有$2^{t+1}< n/2$，所以$t < log_2(n/2)-1=log_2n-2$ ，得到$T(n)=O(log_2n)$。

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

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

A. $O(log_2n)$
B. $O(n)$
C. $O(nlog_2n)$
D. $O(n^2)$
答案：B。本题是求阶乘$n!$的递归代码，即$n \times (n-1) \times···\times 1$。每次递归调用时fact()的参数减1，递归出口为fact (1)，一共执行$n$次递归调用fact ()，故$T(n)=O(n)$。

已知两个长度分别为 m 和 n 的升序链表，若将它们合并为长度为 m + n 的一个降序链表，则最坏情况下的时间复杂度是（）。

A. $O(n)$
B. $O(mn)$
C. $O(min(m, n))$
D. $O(max(m,n))$
答案：D。两个升序链表合并，两两比较表中元素，每比较一次，确定一个元素的链接位置(取较小元素，头插法)。当一个链表比较结束后，将另一个链表的剩余元素插入即可。最坏的情况是两个链表中的元素依次进行比较，因为$2max(m, n)\geq m + n$,所以时间复杂度为$O(max(n,m))$。

下列程序段的时间复杂度是（）。

int count = 0;
for (int k = 1; k < n; k *= 2) {
  for (int j = 1; j <= n; j++) {
    count++;
  }
}

A. $O(log_2n)$
B. $O(n)$
C. $O(n log_2n)$
D. $O(n^2)$
答案：C。内层循环条件与外层循环的变量无关，各自独立，每执行一次j自增1,每次内层循环都执行$n$次。外层循环条件$k \leq n$，增量定义为k*=2，可知循环次数$t$，满足$k = 2^t \leq n$，即$t \leq log_2n$。即内层循环的时间复杂度为$O(n)$，外层循环的时间复杂度为$O(log_2n)$。对于嵌套循环，根据乘法规则可知，该段程序的时间复杂度$T(n) = T_1(n)-T_2(n) = O(n)\times O(log_2n)=O(nlog_2n)$。

下列函数的时间复杂度是（）。

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

A. $O(logn)$
B. $O() $
C. $O(n)$
D. $O(n log n)$
答案：B。基本运算sum+=++i，它等价于++i; sum=sum+i,每执行一次i自增1。i=l时sum=0 + l； i=2 时 sum=0+l+2； i=3 时 sum=0+1+2+3,以此类推得出 sum=0+1+2+3+......+i= (1 + i) * i / 2, 可知循环次数t满足(1+t)*t/2<n，因此时间复杂度为$O(\sqrt{n})$。

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

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

A. $O(log n) $
B. $O(\sqrt{n})$
C. $O(n) $
D. $O(n^2)$
答案：B。假设第$k$次循环终止，则第$k$次执行时，$(x + 1)^2>n$，$x$的初始值为0，第$k$次判断时，$x = k-1$, 即$k^2>n$，$ k>$,因此该程序段的时间复杂度为$O()$。因此选B。

下列程序段的时间复杂度是（）。

int sum = 0;
for (int i = 1; i < n; i *= 2) {
  for (int j = 0; j < i; j++) {
    sum++;
  }
}

A. $O(log n) $
B. $O(n) $
C. $O(n log n)$
D. $O(n^2)$
当外层循环的变量i取不同值时，内层循环就执行多少次，因此总循环次数为i的所有取值之和。假设外层循环共执行$k$次，当$i=1,2,4,8,···2^{k-1}(2^{k-1}< n <2^k)$时，内层循环执行$i$次，因此总循环次数$T=1+2+4+8+···+2^{k-1}=2^k-1$ ，即$n<T<2n$，时间复杂度为$O(n)$。

二、综合应用题

一个算法所需时间由下述递归方程表示，试求出该算法的时间复杂度的级别(或阶)。

\[ T(n)=\left\{ \begin{aligned} &1, & & n = 1 \\ &2T(n/2), & & n > 1 \\ \end{aligned} \right. \]

式中，$n$是问题的规模，为简单起见，设$n$是2的整数次幂。

答案：时间复杂度为$O(nlog_2n)$。设$n=2^k(k \geq 0)$，根据题目所给定义有$T(2^k)=2T(2^{k-1})+2^k=2^2T(2^{k-2})+2\times2^k$，由此可得一般递推公式$T(2^k)=2^iT(2^{k-1})+i \times 2^k$，进而得$T(2^k)=2^kT(2^0)+k \times 2^k= (k+1)2^k$，即$T(n)=2^{log_2n}+log_2n \times n=n(log_2n+1)$，也就是$O(nlog_2n)$

分析以下各程序段，求出算法的时间复杂度。

//1
i=1; k=0;
while(i<n-1)
{
    k=k+10*i;
    i++;
}

//2
y=0;
while((y+1)*(y+1)<=n)
{
    y=y+1;
}

//3
for(i=1;i<=n;i++)
    for(j=1;j<=i;j++)
        for(k=1;k<=j;k++)
            x++;

//4
for(i=0;i<n;i++)
    for(j=0;j<m;j++)
        a[i][j]=0;

答案：

基本语句k=k+10*i共执行了 n-2次，所以$T(n)=O(n)$。
设循环体共执行$t$次，每循环一次，循环变量y加1，最终$t=y$，故$t \leq n^2$，得到$T(n)=O(\sqrt{n})$。
基本语句x++的执行次数为$T(n)=O(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{i}\sum\limits_{k=1}^{j}1)=O(n^3/6)=O(n^3)$。
内循环执行m次，外循环执行n次，根据乘法原理，共执行了$m \times n$，故$T(m,n)=O(m \times n)$。