数据结构、栈和队列、循环队列、树状结构
- 一. 数据结构
-
- 1. 数据结构
- 2. 练习
- 二. 栈和队列
-
- 1. 进栈出栈
- 2. 入队出队
- 3. 练习
- 三. 循环队列
-
- 1. 循环队列
- 2. 练习
- 四. 树状结构
-
- 1. 树
- 2. 树的相关计算
- 3. 练习
一. 数据结构
1. 数据结构
数据结构是指互相有关联的数据元素的集合，它包含两个元素，即“数据”和“结构”
所谓“结构”，就是关系
设数据元素集合为{1,2,3,4,5,6,7}，下列关系为线性结构的是
1,2； 3,4； 2,3； 4,5； 6,7； 5,6； 每一块，前面为前件，后面为后件。 每一个元素有且仅有一个前件，有且仅有一个后件。 
换下顺序变成
1,2； 2,3； 3,4； 4,5； 5,6； 6,7； 该成为线性结构
2. 练习
设数据集合为D={1, 2, 3, 4, 5}。下列数据结构 B=(D, R)中为非线性结构的是 (A) R={ (5, 4), (4, 3), (3, 2), (2, 1) } (B) R={ (1, 2), (2, 3), (3, 4), (4, 5) } (C ) R={ (2, 5), (5, 4), (3, 1), (4, 3) } (D) R={ (1, 2), (2, 3), (4, 3), (3, 5) }
设数据集合为D={1, 2, 3, 4, 5}。则满足下列关系R的数据结构中为线性结构的是 (A) R={ (1, 3), (2, 4), (3, 5), (1, 2) } (B) R={ (1, 3), (4, 1), (3, 2), (5, 4) } ( C) R={ (1, 2), (3, 2), (5, 1), (4, 5) } (D) R={ (1, 2), (2, 4), (4, 5), (2, 3) } 
答案：1. D 2. B
二. 栈和队列
1. 进栈出栈
栈底封死，从栈顶进入 出栈：先进的后出 
栈顶指针指向d
2. 入队出队
-先进先出，后进后出 
3. 练习
设有一个栈与一个队列的初始状态均为空。现有一个序列 A,B,C,D,E,F,G,H。先分别将序列中的前 4 个元素依次入栈，后 4 个元素依次入队，然后分别将栈中的元素依次退栈，再将队列中的元素依次退队。最后得到的序列为 (A) A,B,C,D,E,F,G,H (B) A,B,C,D,H,G,F,E (C ) D,C,B,A,E,F,G,H (D) D,C,B,A,H,G,F,E 
设有栈S和队列Q，初始状态均为空。首先依次将A,B,C,D,E,F入栈，然后从栈中退出三个元素依次入队，再将X,Y,Z入栈后，将栈中所有元素退出并依次入队，最后将队列中所有元素退出，则退队元素的顺序为 (A) DEFXYZABC (B) FEDXYZCBA (C ) DEFZYXABC (D) FEDZYXCBA
答案：1.C 2.D
三. 循环队列
1. 循环队列
进 
循环 
通过对头指针和队尾指针的位置计算数据块的个数 第二种：对位-对头 5-8=-3说明有三个空着 ， 总位数-空位数 8-3=5有五个数据元素 
2. 练习
初始状态：front=rear → 队满或者队空
提示：front=rear表示栈为空或者栈为满
循环队列的存储空间为 Q(1:60)，初始状态为空。经过一系列正常的入队与退队操作后，front=24，rear=25。循环队列中的元素个数为 (A) 60 (B) 59 (C ) 2 (D) 1 rear – front = 25 – 24 = 1
循环队列的存储空间为 Q(1:50)，初始状态为空。经过一系列正常的入队与退队操作后，front=25，rear=24。循环队列中的元素个数为 (A) 49 (B) 25 (C ) 50 (D) 1 rear – front = 24 – 25 = -1；-1 + 50 = 49
答案：1.C 2.D 3.A
四. 树状结构
1. 树
树是一种简单的非线性结构。在树这种数据结构中，所有数据元素之间的关系具有明显的层次特性。
2. 树的相关计算
【结点计算方法】 
方法1：每个度对应的个数之和 2 + 1 + 1 + 6 = 10
方法2：度×相应个数再加1 3×2 + 2×1 + 1×1 + 0×6 + 1 = 10
通常让两个方法相等，解得相关的参数。
| 3 | 2 |
| 2 | 1 |
| 1 | 1 |
| 0 | 6 |
| 节点总数 | 10 |
3. 练习
树的度为3说明最大度为3
解：9 + 0 + 5 + X = 3×9 + 2×0 + 1×5 + 0×X + 1； X = 19
| 3 | 9 |
| 2 | 0 |
| 1 | 5 |
| 0 | X |
解：X + 3 + 1 + 6 = 3×X + 2×3 + 1×1 + 0×6 + 1； X = 1
| 3 | X |
| 2 | 3 |
| 1 | 1 |
| 0 | 6 |
答案：1.B 2.D
