数据结构习题整理

一、单项选择题

数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的（）和运算的科学。
- A. 约束
- B. 算法
- C. 关系
- D. 操作
答案：C
数据结构研究的内容不包括（）。
- A. 逻辑结构
- B. 存储结构
- C. 操作和运算
- D. 有穷性和健壮性
答案：D

错题分析：有穷性、健壮性是算法的特性，并非数据结构的研究内容。
以下属于逻辑结构的是（）。
- A. 顺序表
- B. 哈希表
- C. 有序表
- D. 单链表
答案：C
以下与数据的存储结构无关的术语是（）。
- A. 循环队列
- B. 链表
- C. 哈希表
- D. 栈
答案：D

错题分析：栈是逻辑结构（描述元素的线性关系），而循环队列（顺序存储的队列）、链表（链式存储）、哈希表（散列存储）均与存储结构直接相关。
以下哪一种术语与数据的存储结构有关（）。
- A. 栈
- B. 队列
- C. 散列表
- D. 线性表
答案：C
以下哪种结构是逻辑结构，而与存储和运算无关（）。
- A. 顺序表
- B. 散列表
- C. 线性表
- D. 单链表
答案：C
下列与数据元素有关的叙述中，哪一个是不正确的（）。
- A. 数据元素是数据的基本单位，即数据集合中的个体
- B. 数据元素是有独立含义的数据最小单位
- C. 数据元素又称结点
- D. 数据元素又称作记录
答案：B

错题分析：数据项是数据的最小单位，数据元素是数据的"基本单位"（可由多个数据项组成）。
以下说法正确的是（）。
- A. 数据元素是数据的最小单位
- B. 数据项是数据的基本单位
- C. 数据结构是带有结构的各数据项的集合
- D. 一些表面上很不相同的数据可以有相同的逻辑结构
答案：D
下列关于数据的逻辑结构的叙述中，哪一个是正确的（）。
- A. 数据的逻辑结构是数据间关系的描述
- B. 数据的逻辑结构反映了数据在计算机中的存储方式
答案：A
线性表采用链式存储结构时，要求内存中可用存储单元的地址（）。
- A. 必须是连续的
- B. 部分地址必须是连续的
- C. 一定是不连续的
- D. 连续不连续都可以
答案：D
以下关于链式存储结构的叙述中哪一条是不正确的（）。
- A. 结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构
- B. 逻辑上相邻的结点物理上不必邻接
- C. 可以通过计算直接确定第 $i$ 个结点的存储地址
- D. 插入、删除运算操作方便，不必移动结点
答案：C

错题分析：链式存储通过指针遍历访问结点，无法直接通过计算得到第 $i$ 个结点的地址（顺序存储可直接计算）。
以下关于顺序存储结构的叙述中哪一条是不正确的（）。
- A. 存储密度大
- B. 逻辑上相邻的结点物理上不必邻接
- C. 可以通过计算直接确定第 $i$ 个结点的存储地址
- D. 插入、删除运算操作不方便
答案：B

错题分析：顺序存储的核心是"逻辑相邻则物理必相邻"；链式存储才是"逻辑相邻但物理不必相邻"。
线性结构的顺序存储结构是一种（）的存储结构。
- A. 随机存取
- B. 顺序存取
- C. 索引存取
- D. 散列存取
答案：A
线性表的链式存储结构是一种（）的存储结构。
- A. 随机存取
- B. 顺序存取
- C. 索引存取
- D. 散列存取
答案：B
计算机算法指的是（）。
- A. 计算方法
- B. 排序方法
- C. 解决问题的有限运算序列
- D. 调度方法
答案：C
计算机算法必须具备输入、输出和（）等5个特性。
- A. 可行性、可移植性和可扩充性
- B. 可行性、确定性和有穷性
- C. 确定性、有穷性和稳定性
- D. 易读性、稳定性和安全性
答案：B
算法分析的主要内容是（）。
- A. 正确性
- B. 可读性和稳定性
- C. 简单性
- D. 空间复杂性和时间复杂性
答案：D
算法分析的目的是（）。
- A. 找出数据结构的合理性
- B. 研究算法中的输入和输出的关系
- C. 分析算法的效率以求改进
- D. 分析算法的易懂性和文档性
答案：C
关于算法的时间复杂度，下列说法错误的是（）。
- A. 算法中语句执行的最大次数作为算法的时间复杂度
- B. 一个算法的执行时间等于其所有语句执行时间的量度
- C. 任一语句的执行时间为该语句执行一次所需的时间与执行次数的乘积
- D. 一般认为，随问题规模 $n$ 的增大，算法执行时间的增长速度较快的算法最优
答案：D

错题分析：执行时间增长越快的算法，效率越低，并非"最优"。
算法时间复杂度 $T(n)$ 按数量级大小顺序正确的为（）。
- A. $O(n \log n) > O(\log n)$
- B. $O(n^2) < O(n \log n)$
- C. $O(\log n) > O(n)$
- D. $O(2^n) < O(n^3)$
答案：A
下列各式中，按增长率由小至大的顺序正确排列的是（）。
- A. $\sqrt{n}, n!, 2^n, n^{1/2}$
- B. $n^{1/2}, 2^n, n!, 2^{20}$
- C. $2^{20}, \log n, n^{1/2}, n!$
- D. $\log n, 2^n, n^3, n!$
答案：C

二、填空题

数据结构是一门研究非数值计算的程序设计问题中计算机的（操作对象）以及它们之间的（关系）和（运算）等的学科。
数据结构的形式定义为：数据结构是一个二元组 $Data_Structure = (D, S)$ ，其中：D是（数据元素）的有限集，S是D上（关系）的有限集。
数据结构包括数据的（逻辑结构）、数据的（存储结构）和数据的（运算）这三个方面的内容。
数据结构按逻辑结构可分为两大类，它们分别是（线性结构）和（非线性结构）。
数据的逻辑结构包括集合、（线性结构）、（树形结构）、（图形结构）四种类型，树形结构和图形结构合称为（非线性结构）。
数据的存储结构包括（顺序存储结构）和（链式存储结构）两种类型。
线性结构中元素之间存在（一对一）关系，树形结构中元素之间存在（一对多）关系，图形结构中元素之间存在（多对多）关系。
数据的基本单位是（数据元素），在计算机中通常作为一个（整体）来进行处理。
数据的最小单位是（数据项）。
在线性结构中，第一个结点（无）前驱结点，其余每个结点有且只有（一）个前驱结点；最后一个结点（无）后继结点，其余每个结点有且只有（一）个后继结点。
在树形结构中，树根结点没有（前驱）结点，其余每个结点有且只有（一）个前驱结点；叶子结点没有（后继）结点，其余每个结点的后继结点数可以（多个）。
在图形结构中，每个结点的前驱结点数和后继结点数可以（任意个）。
数据的运算最常用的有5种，它们分别是（插入）、（删除）、（查找）、（排序）、（修改）。
算法效率的度量主要采用（时间复杂度）和（空间复杂度）来衡量。
算法的时间复杂度取决于问题的（规模）和待处理数据的初态。
语句++x的频度为（ $\frac{(n-2)(n-1)}{2}$ ）。

for(i=2; i<=n; i++)
    for(j=2; j<=i-1; j++)
        ++x; a[i][j] = x;

分析下面程序段的时间复杂度：

i = s = 0;
while (i < n)
{i++; s += i;}

答案： $O(n)$

三、算法时间复杂度分析题

程序段：

if(i>3) j++;
else i++;

时间复杂度： $O(1)$ （注：原笔记标红可能误判，此段为常数操作）

程序段：

i=0; k=0;
do{
    k = k + 10 * i;
    i++;
}while(i<n);

时间复杂度： $O(n)$

程序段：

x=90; y=100;
while(y>0)
    if(x>100) {x = x - 10; y--;}
    else x++;

时间复杂度： $O(1)$ 错题分析：x、y为常数，循环次数有限，属于常数时间。

程序段：

s=0;
for(i=0; i<t; i++)
    for(j=0; j<n; j++)
        s += B[i][j];

时间复杂度： $O(nt)$ 错题分析：原笔记写 $O(n^2)$ 错误，两层循环次数为 $t \times n$ ，故为 $O(nt)$ 。

程序段：

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

时间复杂度： $O(n^2)$

程序段：

for(i=0; i<n; i++)
    for(j=0; j<m; j++)
        A[i][j] = 0;

时间复杂度： $O(nm)$

程序段：

for(i=0; i<10; i++)
    for(j=0; j<10; j++)
        A[i][j] = 0;

时间复杂度： $O(1)$ （循环次数固定，为常数时间）

程序段：

i=1;
while(i<=n)
    i = i * 2;

时间复杂度： $O(\log_2 n)$

程序段：

int count = 1;
while (count < n)
    count = count * 3;

时间复杂度： $O(\log_3 n)$ （可归为 $O(\log n)$ ）

程序段：

y=1;
while(y*y <= n)
    y++;

时间复杂度： $O(\sqrt{n})$

程序段：

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

时间复杂度： $O(n^2)$

程序段：

x=n; y=0; // n>1
while(x >= (y+1)*(y+1))
    y++;

时间复杂度： $O(\sqrt{n})$

程序段：

i=2;
while((i%n)!=0 && i*i < sqrt(n)) i++;

时间复杂度： $O(\sqrt{n})$

递归函数：

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

时间复杂度： $O(n)$ 错题分析：递归调用n次，每次操作为常数时间，故复杂度为 $O(n)$ ；原笔记写 $O(1)$ 错误。

错题分析总结

概念混淆：如"数据元素 vs 数据项"（第7题）、“算法特性 vs 数据结构研究内容”（第2题）。
存储与逻辑结构区分：如"栈的逻辑结构属性"（第4题）、“链式/顺序存储的地址特性”（第11、12题）。
时间复杂度分析：如递归次数计算（fact函数）、嵌套循环次数乘积（第4、14题）、常数时间与非常数时间的边界（固定次数循环为 $O(1)$ ）。
增长率比较：对不同复杂度（如 $O(n^2)$ 、 $O(n \log n)$ ）的增长速度理解有误（第19、20题）。

需重点加强逻辑/存储结构的定义边界、算法与数据结构的范畴划分、时间复杂度的"循环/递归次数+操作代价"分析方法。