Relax1000 数据结构 · 第1章 绪论 · 题目¶
第1章 绪论¶
本章 26 题；题目册印刷页 2–6。
Q1¶
以下关于数据结构的说法中，正确的是（ ）。
- A．数据的逻辑结构独立于其存储结构
- B．数据的存储结构独立于其逻辑结构
- C．数据的逻辑结构唯一决定其存储结构
- D．数据结构仅由其逻辑结构和存储结构决定
Q2¶
设有如下遗产继承规则：丈夫和妻子可以互相继承遗产，子女可以继承父亲和母亲的遗产，子女间不能相互继承，则表示该遗产继承关系最合适的数据结构应该是（ ）
- A．树
- B．图
- C．线性表
- D．集合
Q3¶
下列关于数据结构的说法，正确的有（ ）
I．数据项是数据的基本单位
II．抽象数据结构可以定义一个完整的数据结构
III．循环队列属于数据结构中的物理结构
IV．线索二叉树属于数据结构中的物理结构
- A．II、III、IV
- B．I、II、IV
- C．I、III
- D．全部正确
Q4¶
下列关于数据、数据元素、数据项的说法正确的是（ ）
- A．数据具有同一特点
- B．数据元素对应数据项的类型要一致
- C．每个数据元素都一样
- D．数据元素所包含的数据项的个数可以不相等
Q5¶
某算法的时间复杂度为 〔公式/符号见原页版面片段〕2，表明该算法的（ ）。
- A．问题规模是〔公式/符号见原页版面片段〕2
- B．执行时间等于〔公式/符号见原页版面片段〕2
- C．执行时间与〔公式/符号见原页版面片段〕2成正比
- D．问题规模与〔公式/符号见原页版面片段〕2成正比
原页版面片段（用于核对图表、公式、矩阵或代码）
审计旁注（非原文）：作废
题干只给出 O(n²)，表示渐近上界，不能推出执行时间必与 n² 成正比；四个选项都不严格。王道回源：result.md [block: b_17_5]。
[已降级 · 2026-09-01 逐题复核] 原判“作废”过重。王道第18页同题同选项，标准答案就是 C。只需记“严格说 O 只是上界”，正常作答。
Q6¶
下列逻辑结构属于线性结构的是（ ）
- A．树
- B．图
- C．集合
- D．队列
Q7¶
下列不属于物理结构的是（ ）
- A．顺序表
- B．单链表
- C．散列表
- D．有序表
Q8¶
数据结构和数据类型的形式定义分别为：Data-Structure=(D，R) Data-Type=(D，R，P)试选择 D、R、P 的确切含义是（ ）
- A．数据，数据元素，存储结构
- B．数据元素，数据关系，基本操作
- C．数据对象，存储结构，基本操作
- D．数据对象，数据关系，基本操作
原页版面片段（用于核对图表、公式、矩阵或代码）
Q9¶
下列代码的时间复杂度是（ ）int x=90, y=100; while(y>0){ if(x>100){ x=x-10; y--; } else x++; }
- A．〔公式/符号见原页版面片段〕
- B．〔公式/符号见原页版面片段〕2
- C．〔公式/符号见原页版面片段〕3
- D．〔公式/符号见原页版面片段〕 1
原页版面片段（用于核对图表、公式、矩阵或代码）
Q10¶
下列代码的时间复杂度是（ ）for (int i = 1; i <= n; i ++ ) { for (int j = 1; j <= n; j ++ ) { k = 1; while (k <= n) k *= 5; } }
- A．〔公式/符号见原页版面片段〕2
- B．〔公式/符号见原页版面片段〕3
- C．〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕
- D．〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕
原页版面片段（用于核对图表、公式、矩阵或代码）
Q11¶
下列代码的时间复杂度是（ ）int cnt = 1, sum = 0; while(sum <= n){ sum += cnt; cnt ++ ; }
- A．〔公式/符号见原页版面片段〕
- B．〔公式/符号见原页版面片段〕2
- C．〔公式/符号见原页版面片段〕
- D．〔公式/符号见原页版面片段〕 1
原页版面片段（用于核对图表、公式、矩阵或代码）
Q12¶
假定 n>2，计算机执行下面的语句时，语句 S 的执行次数为（ ）。for (i = 1; i < n - 1; i ++ ) for (j = n; j >= i; j --) S；
- A．n(n-1)
- B．(n+3)(n-2)/2
- C．(n+2)(n-1)/2
- D．n(n-1)/2
原页版面片段（用于核对图表、公式、矩阵或代码）
Q13¶
以下程序的时间复杂度是（ ）for (int i = 1; i <= n; i ++ ) { for (int j = i; j <= n; j ++ ){ count ++ ; } }
- A．〔公式/符号见原页版面片段〕
- B．〔公式/符号见原页版面片段〕2
- C．〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕
- D．〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕
原页版面片段（用于核对图表、公式、矩阵或代码）
Q14¶
下列代码的时间复杂度是（ ）for(i=1;i<=n;i++) for(j=1;j<=n;j++){ c[i][j]=0; for(k=1;k<=n;k++) c[i][j]=c[i][j]+a[i][k]*b[k][j]; }
- A．〔公式/符号见原页版面片段〕
- B．〔公式/符号见原页版面片段〕2
- C．〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕
- D．〔公式/符号见原页版面片段〕3
原页版面片段（用于核对图表、公式、矩阵或代码）
Q15¶
下列代码的时间复杂度为（ ）for (int i = 1; i <= n; i += 2 ) for (int j = 1; j <= n; j *= 2) for (int k = 1; k <= j; k ++ ）count ++ ；
- A．〔公式/符号见原页版面片段〕2 〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕
- B．〔公式/符号见原页版面片段〕2
- C．〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕
- D．〔公式/符号见原页版面片段〕3
原页版面片段（用于核对图表、公式、矩阵或代码）
Q16¶
以下代码的时间复杂度为（ ）void F(int n) { int sum = 0; for (int i = 1; i <= n; i ++ ) { for (int j = 0; j < n; j += i) { sum += j; } } }
- A．〔公式/符号见原页版面片段〕2
- B．〔公式/符号见原页版面片段〕 3 2
- C．〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕
- D．〔公式/符号见原页版面片段〕3
原页版面片段（用于核对图表、公式、矩阵或代码）
Q17¶
下面程序的时间复杂度是（ ）void func(int n){ int i, j, k; int count = 0; for (int i = 1; i <= n; i *= 2){ for (int j = 1; j <= i; j ++ ){ for (k = 1; k <= j; k ++ ){ count ++ ; } } } }
- A．〔公式/符号见原页版面片段〕3
- B．〔公式/符号见原页版面片段〕2
- C．〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕
- D．〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕
原页版面片段（用于核对图表、公式、矩阵或代码）
Q18¶
对于下列求 Fibonacci 数的算法，其时间复杂度为（ ）int Fibonacci(int n) { if(n == 1 || n==2) return 1; return Fibonacci(n-1) + Fibonacci(n-2); }
- A．O(n)
- B．O(n²)
- C．〔公式/符号见原页版面片段〕
- D．指数复杂度
原页版面片段（用于核对图表、公式、矩阵或代码）
Q19¶
以下是经典汉诺塔问题的伪代码，在调用 hanoi(n, 'A', 'C', 'B');时，时间复杂度是（ ）。void hanoi(int n, char from_rod, char to_rod, char aux_rod) { if (n == 1) {只有一个盘子时，直接移动到目标柱子return; } hanoi(n-1, from_rod, aux_rod, to_rod);将最大的盘子（第 n 个）从起始柱子移动到目标柱子hanoi(n-1, aux_rod, to_rod, from_rod); }
- A．〔公式/符号见原页版面片段〕 2〔公式/符号见原页版面片段〕
- B．〔公式/符号见原页版面片段〕
- C．〔公式/符号见原页版面片段〕2
- D．〔公式/符号见原页版面片段〕
原页版面片段（用于核对图表、公式、矩阵或代码）
Q20¶
设二叉树共有 n 个结点，下列程序段的时间复杂度是（ ）。int maxFunc(TreeNode root) { if (root == NULL) return 0; return max(maxFunc(root->left), maxFunc(root->right)) + 1; }
- A．〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕
- B．〔公式/符号见原页版面片段〕
- C．〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕
- D．〔公式/符号见原页版面片段〕 2〔公式/符号见原页版面片段〕
原页版面片段（用于核对图表、公式、矩阵或代码）
Q21¶
下列代码的时间复杂度是（ ）int func(int n) { if (n == 1) return 1; return func(n - 1) * n; }
- A．〔公式/符号见原页版面片段〕2
- B．〔公式/符号见原页版面片段〕
- C．〔公式/符号见原页版面片段〕 2〔公式/符号见原页版面片段〕
- D．〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕
原页版面片段（用于核对图表、公式、矩阵或代码）
Q22¶
下列递归表达式的复杂度是多少（ ）〔公式/符号见原页版面片段〕 = 3〔公式/符号见原页版面片段〕 4 + 〔公式/符号见原页版面片段〕2
- A．O(〔公式/符号见原页版面片段〕2)
- B．O(2〔公式/符号见原页版面片段〕)
- C．O (〔公式/符号见原页版面片段〕)
- D．O(〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕)
原页版面片段（用于核对图表、公式、矩阵或代码）
Q23¶
下列递归代码的时间复杂度为（ ）void process(int n) { if (n <= 1) return; int sum = 0; for (int i = 0; i < n; ++i) sum += i; printf("%d\n", sum); for (int i = 0; i < 2; ++i) process(n / 2); }
- A．〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕
- B．〔公式/符号见原页版面片段〕2
- C．〔公式/符号见原页版面片段〕2 〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕
- D．〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕
原页版面片段（用于核对图表、公式、矩阵或代码）
Q24¶
以下代码在最坏情况下的时间复杂度为（ ）for(k=n-1;k>=1;--k) for(t=1;t
- A．O(〔公式/符号见原页版面片段〕)
- B．O(〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕)
- C．O(〔公式/符号见原页版面片段〕3)
- D．O(〔公式/符号见原页版面片段〕2)
原页版面片段（用于核对图表、公式、矩阵或代码）
Q25¶
下列程序段的空间复杂度是（ ）。int func(int m,int n){ if(m==n) return 1; else{ int mid=(m+n)/2; return func(m,mid)+func(mid+1,n); } }
- A．〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕
- B．〔公式/符号见原页版面片段〕
- C．〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕
- D．〔公式/符号见原页版面片段〕 2〔公式/符号见原页版面片段〕
原页版面片段（用于核对图表、公式、矩阵或代码）
Q26¶
若某算法的空间复杂度为 O(1)，则表示该算法（ ）。
- A．不需要任何辅助空间
- B．所需辅助空间大小与问题规模 n 无关
- C．不需要任何空间
- D．所需空间大小与问题规模 n 无关
原页版面片段（用于核对图表、公式、矩阵或代码）
