数据结构概论 01 刷题

第一节

选择题

1.d

线性结构：所有数据元素之间存在一对一的关系。

2.c

3.a c*错

4.a

5.c

6.b

7.c

8.a

算法特性和算法分析不一样

9.c

10.b

填空题

1 数据结构包括数据逻辑结构、数据存储结构和数据运算。

2 线性结构和非线性结构

3.不知道 *

4.没有 没有

5.头 1 子 n个 前驱 1 后驱 任意多个 错-

6.超纲了-忘记了 任意多个

7顺序存储、链式存储、索引存储和哈希存储。

8 时间复杂度 空间复杂度

9规模为n

10 额外内存空间

简答题

运算描述是从抽象层面对数据结构的操作定义。它是算法设计时的理论框架，侧重于说明在该数据结构上可以进行哪些操作，以及这些操作的输入、输出和效果。运算描述强调操作的功能而不是具体实现

运算实现是运算描述的具体实现方式，涉及到算法如何在特定的数据结构中执行操作。它需要考虑到算法的时间复杂度、空间复杂度和具体的编程语言实现。运算实现是通过具体的编程代码来完成的

1.不知道

2.省掉1000log2N

3.n2

4.不知道

3.4次

5.头炸了

6.头炸了

…..对于这种计算后续针对训练一下

第2节

选择题

1.a

2.b c没看见随机存取

3.a

4.b

5.c

6.d

7.c

8.b

9.a

10.c *

11.c

12 a

13.a c *B 不知道

14 d 是循环单链表

15 d

16 d

17 a

18 c

19 a

20b

填空题

初始化linkList()

o1

*o1 看错字了

不知道 2/n

下标 指针域 物理存储位置 链域的指针

前驱节点 0 1

7 8 省

9 on

10 l->next==head –看错了

简答题

2不知道

3便于算法设计

4. 2 4

5 4

回去找答案

栈和队列

1.a

2.D

1.进栈后立即出栈在进栈 A a b c d

2.顺序出栈 b

3. a b c 1.bc 2.b 3.bd 4.b

   弹栈 a c d b

4. a b c d a b c->出错

3.c

4.c *D 我就说我看不懂ai *

5.a

6.d

7.a

方便出栈-栈顶必须在数组尾部-

8.b A忘记了 *

9.A D 我感觉答案有问题 *

10 B 看错了以为是栈 A

11 C

12 A D

考察队列的逻辑结构 忘记了

13 b

单队列 遵循先进先出

双端队列就有五线可能

14 a

不知道

15

16

17

18

循环队列 回去学习

19 b

20 b

填空题

栈顶 栈底、

n/

立即出栈

c d b a e cd be a

data[top]=x;/ top++.data[top]=x

data[top]=0;top–

top到底指针栈顶-还是栈顶上面+1

// 假设栈大小为 n，数组 data 用于存储栈元素，top 为栈顶指针
void push(int[] data, int n, int x, int top) {
    if (top < n) {
        data[top] = x;  // 将元素 x 放入栈顶
        top++;          // 栈顶指针加 1
    } else {
        System.out.println("栈满，无法进栈");
    }
}

int pop(int[] data, int top) {
    if (top > 0) {
        top--;            // 栈顶指针减 1
        int x = data[top]; // 取出栈顶元素
        return x;         // 返回出栈的元素
    } else {
        System.out.println("栈空，无法出栈");
        return -1;        // 表示栈为空时的错误返回值
    }
}

队列

8

9

10

不知道，没学过循环队列

栈-先进后出-只允许一端操作

队列-先进先出 一端添加-一端删除

一般设置在数组的开端-这是为了栈顶在数组末端方便删除数据，而不需要移动数组

1

没学过

顺序队列使用数组作为存储结构，当进行元素的入队和出队操作时，数组的起始位置是固定的。随着出队操作的进行，数组的前面部分空间被释放，但由于队首指针只向后移动，不会将元素搬移到数组的前端，这就导致了所谓的“假溢出”现象——即数组的后端已经满了，但前端还有空余位置。这时我们无法再进行入队操作，虽然数组并没有真正被填满，但由于指针的原因，无法有效利用这些空余的空间。

ps:循环队列

还要算法表示的结构

在栈的操作中，top 通常指的是 栈顶指针，而不是栈顶元素。它表示栈顶元素在数组中的位置。在大多数实现中，top 指向的是下一个可以存放元素的位置（即当前栈顶元素的下一个位置）。例如：

• 如果 top = 0，说明栈是空的，栈中还没有元素。
• 如果 top = n（n 是栈的大小），则说明栈已经满了。

因此，top - 1 通常是栈顶元素在数组中的位置。

总结：

• 栈顶指针：top 表示下一个可以存放元素的位置。
• 栈顶元素：data[top - 1] 表示栈顶的实际元素。

串

选择题

1.d

2.d

3. a b d-我觉得题目可以改成不是

4.b

5.b

填空题

1含有零个字符的串，由一个或多个空格组成的串

2删除 3位置的2个字符–abcdg abefg

这种题就有歧义 这个3的位置是对于数组还是对于我们心中3的位置

3 o n

4.指针域为空 s->ne==null;

5. on

数组

1.b

2.c

3.c

a[11] a[12] a[13] a[14] a[15] a[16] a[17] a[18]

8*3=24+5=29

4 c

计公式

5.c

计公式

6.A

7. b

8.b

考察矩阵从0开始i+1

9.c

10

11d

12 a

13 c

14 b

不知道

15d

不知道

学习对此矩阵稀疏矩阵的一些知识–学习广义表

树和二叉树

选择题

1 c

2. a 2 a 3 c

3.c

**4.a

梯子坏了，看不了笔记

5.c(计算错了)

6.d

7.b

8.c

满二叉树

9.d

• 满二叉树的计算

10 d

完全二叉树考察

11 b

• 完全二叉树考察

h=10

2 10-1/2

512/2=256错误

12 b

13 c 不会

中序和后序序列确定二叉树

14 d

15 d

• 无法理解

只能确定根节点

16 b

17

18

19

ps:崩溃了休息

填空题

​ 3

n-3

5

31 32

分支节点- 度大于0的节点 63-1-32=63-33=30+1

5.350

6. 500 499 1

7.2 i-1次方

8

2 h-1 2h -1 2h-1

9

a的左递归节点 根的右节点的最右下节点

10

34

图

选择题

1. c

2. b

3.c

4.c

5.b d

6.d

7.a

8.c

9.a

10.c

11.b

12 b

13 a

14 d

15 d

16 a

17 d

18 c

19 b

20 c

21

22

填空题

1.n-1

2. 邻接矩阵 邻接表
3. n-1 9
4. 2(n-1)
5. n2
6. n+e
7. n2 n+e
8. n2 n+e

9

10

11 -极小连通子图

12 n2 nlog2n kruskal prim