没有合适的资源?快使用搜索试试~ 我知道了~
首页深入解析软考数据库工程师:CPU与控制器详解
深入解析软考数据库工程师:CPU与控制器详解
4 下载量 75 浏览量
更新于2024-06-18
5
收藏 34.84MB DOCX 举报
本资源是一份针对软考数据库系统工程师的备考笔记,主要涵盖了计算机系统基础知识。首先,章节1.1重点介绍了CPU(中央处理器)的组成,这是理解数据库系统运行的核心组件。 1.1.1运算器是CPU的关键部分,负责执行算术和逻辑运算。它包括算术逻辑单元(ALU),用于处理数据运算;累加寄存器(AC)作为运算时的工作区;数据缓冲寄存器(DR)在内存操作中起到缓冲和中转作用;状态条件寄存器(PSW)保存运算结果的各种状态标志,如进位、溢出、零值、负数等。 1.1.2控制器是CPU的指挥中心,负责程序的自动化执行和异常处理。其组成部分包括指令寄存器(IR)、程序计数器(PC)、地址寄存器(AR)和指令译码器(ID)。这些部件协同工作,确保指令的正确解析和执行流程。 1.1.3寄存器组区分了专用寄存器(如ALU和控制器内的寄存器)和通用寄存器(可由程序员指定用途),通用寄存器数量因处理器不同而变化。 1.1.4数的表示方法提到了原码,其中最高位作为符号位,0代表正数,1代表负数,而0的原码表示形式有[+0]原=00000000和[-0]原=10000000,原码可用于表示定点整数的范围,从-(2n-1-1)到+(2n-1)。 这份笔记对于准备软考数据库系统工程师考试的学生来说,提供了关于硬件基础的重要参考,帮助他们理解计算机硬件如何支持数据库系统的操作,为后续学习数据库设计、优化和管理打下坚实的基础。通过深入学习这部分内容,考生可以掌握计算机系统底层原理,从而更好地应对考试中的理论和实践问题。
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/88650346/bgf.jpg)
需要设置一个头指针指到栈顶。
需要附设指针 top 指示栈顶元素的位置。
(2)链栈:用链表存储栈中的元素。
栈中元素的插入和删除仅在栈顶进行,因此不必设置头节点, 链表的头指针就是栈顶指针。
3.1.3 队列
队列是一种“先进先出”的线性表,队尾入队头出。
●队列的顺序存储(无元素的时候,头尾指向同一个空间 )
(1)顺序队列(头指向第一个元素,尾指向最有一个元素的下一个空间)
(2)循环队列(首尾相连的空间,头指向第一个元素,尾指向最有一个元素的下一个空间)
(Rear-frout+m)%m 计算空间
q.frout=q.rear 说明空间是空
(q.rear+1)% m = q.front 判断是否满
●队列的链式存储(链队列)
为了便于操作,可给链队列添加一个头节点,并令头指针指向头节点。
队列为空的判定条件就是头指针和尾指针的值相同,并且均指向头节点。
3.2 数组与矩阵
3.2.1 数组
●由于数组一般不做插入和删除,且元素个数和元素之间的关系不再发生变动,那么数组适
合采用顺序存储结构。
●数组元素的存储方式及相关计算
二维数组的存储结构可分为以行为主序(按行存储)和以列为主序(按列存储)两种方法。
●设每个数据元素占用 L 个单元,m、n 为数组的行数和列数,那么:
以行为主序优先存储的地址计算公式为:
Loc (a
ij
)=Loc(a
11
)+((i-1) Xn+(j-1)) XL
![](https://csdnimg.cn/release/download_crawler_static/88650346/bg10.jpg)
以列为主序优先存储的地址计算公式为:
Loc (a
ij
)=Loc(a
11
)+((j-1) Xm+(i-1)) XL
3.2.2 矩阵
这里主要讨论一些特殊矩阵的压缩存储的问题。
对多个值相同的元素可以只分配一个存储单元,零元素不分配存储单元。
●下面主要讨论对称矩阵、三对角矩阵、稀疏矩阵。
(1)对称矩阵
若矩阵 A
nxn
中的元素有 a
ij
=a
ji
(1≤i, j≤n) 的特点,则称之为对称矩阵。
●则矩阵 A
nxn
的 n2 个元素可以压缩存储到可以存放 n(n+1)/2 个元素的存储空间中。
●假设以行为主序存储下三角(包括对角线)中的元素,并以一个一维数组 B[n(n+ 1)/2]作为 n
阶对称矩阵 A 中元素的存储空间,则 B[k] (0≤k<n(n+1)/2)与矩阵元素 aij (aji ) 之间存在着一
一对应的关系:
(2)三对角矩阵
●对角矩阵是指矩阵中的非零元素都集中在以主对角线为中心的带状区域中,其余的矩阵元
素都为零。
●下面主要考虑三对角矩阵,即只有主对角线及其左右两边为非零元素。
●若以行为主序将 n 阶三对角矩阵 Anxn 的非零元素存储在一维数组 B[k](0≤k<3n-2) 中,则
元素位置之间的对应关系为:
K=3X(i-L)-L+j-i+1=2i+j-3 (L≤i,j≤n)
(3)稀疏矩阵:
●在一个矩阵中,若非零元素的个数远远少于零元素的个数,且非零元素的分布没有规律,
则称之为稀疏矩阵。
●可以用一个三元组(i, j,a
ij
)唯一确定矩阵中的一个元素。
![](https://csdnimg.cn/release/download_crawler_static/88650346/bg11.jpg)
3.3 树和二叉树
3.3.1 树
●定义:树是 n(n≥0)个节点的有限集合。当 n=0 时称为空树。在任一非空树中,有且仅有一
个称为根的节点:其余节点可分为 m (m≥0)个互不相交的有限集 T1,T2.... Tm,其中每个集合
又都是一棵树,并且称为根节点的子树。
1、双亲、孩子和兄弟:
2、节点的度:一个节点的子树的个数记为该节点的度。
3、叶子节点:也称为终端节点,指度为零的节点。
4、内部节点:度不为零的节点称为分支节点或非终端节点。除根节点之外,分支节点也称为
内部节点。
5、节点的层次:根为第一层,根的孩子在第二层,依此类推。
6、树的高度:一棵树的最大层次数记为树的高度(或深度)
3.3.2 二叉树
●定义:二叉树是 n (n20)个节点的有限集合,它或者是空树(n=0), 或者是由一个根节点及两
棵不相交的、分别称为左子树和右子树的二叉树所组成。
树和二叉树的区别: (1) 二叉树中节点的子树要区分左子树和右子树,即使只有一棵子树,
而树中不用区分。(2) 二叉树中节点的最大度为 2,而树中无限制。
二叉树的性质
1、二叉树第 i (i≥1) 层上至多有 2
i-1
个节点。
2、深度为 k 的二叉树至多有 2
k
-1 个节点(k≥1)。
3、对任何一棵二叉树,若其终端节点数为 n
o
,度为 2 的节点数为 n
2
,则 n
o
=n
2
+1。
满二叉树和完全二叉树
●满二叉树的定义:若深度为 k 的二叉树有 2
k
-1 个节点,则称其为满二叉树。
![](https://csdnimg.cn/release/download_crawler_static/88650346/bg12.jpg)
●完全二叉树:当深度为 k、有 n 个节点的二叉树,当且仅当其每一个节点都与深度为 k 的满
二叉树中编号为 1~n 的节点一一对应时,称之为完全二叉树。
完全二叉树的性质
设深度为 k 的完全二叉树共有 n 个节点,那么可知,除第 k 层外,其余各层都有最多的节点
数。
●具有 n 个节点的完全二叉树的深度为 INT (log
2
n) +1。
●假设有编号为 i 的节点,则有:
(1)若 i=1, 则该节点为根节点,无双亲;若 i>1,则该节点的双亲节点为 INT(i/2)
(2)若 2i≤n,则该节点的左孩子编号为 2i,若 2i>n,无左孩子。
(3)若 2i+ 1≤n,则该节点的右孩子编号为 2i+1,若 2i+1>n, 无右孩子。
二叉树的储存结构
(1)顺序存储
无孩子也要占用一个空间
(2)链式存储
二叉链表:每个元素有三个空间,中间存放数值,左右空间分别存放左右孩子地址域
三叉链表:每个元素有四个空间,第一空间存放左孩子的地址域,第二空间存放数值,第三
空间存放上一节点的地址域,第四空间存放右孩子的地址域。
二叉树的遍历
依据访问根节点次序的不同,可分为前序遍历法、中序遍历法、后序遍历法。
(1)中序遍历法:(左、根、右)
A、中序遍历根的左子树。
B、访问根节点。
C、中序遍历根的右子树。
依此类推。
(2)前序遍历法:先访问根节点(根、左、右)
(3)后序遍历法:后访问根节点(左、右,根)
(4)层序遍历法:按层从上至下、每层从左至右的顺序遍历。
最优二叉树
●最优二叉树又称哈夫曼树,是一类带权路径长度最短的树。
●权:是一个人为的概念,表示计算机对每个节点的访问频率。
●路径长度:是每一个结点到根节点的路径的长度。
●节点的带权路径长度:是指从该节点到根节点之间的路径长度与该节点权的乘积。
●树的带权路径长度为树中所有叶子节点的带权路径长度之和。
●构造最优二叉树的哈夫曼方法:
(1) 根据给定的 n 个权值{W
1
, W
2
, ... w
n
}构成 n 棵二叉树的集合
F={T
1
,T
2
, .. T
n
}, 其中每棵树 T
i
只有一个带权为 w
i
的根节点,其左右
子树均空。
(2)在 F 中选取两棵根节点的权值最小的树作为左右子树,构造一棵新的二叉树,置新构造
二叉树的根节点的权值为其左、右子树根节点的权值之和。
剩余87页未读,继续阅读
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
光头的小蘑菇
- 粉丝: 2
- 资源: 7
上传资源 快速赚钱
我的内容管理 收起
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
会员权益专享
最新资源
- 利用迪杰斯特拉算法的全国交通咨询系统设计与实现
- 全国交通咨询系统C++实现源码解析
- DFT与FFT应用:信号频谱分析实验
- MATLAB图论算法实现:最小费用最大流
- MATLAB常用命令完全指南
- 共创智慧灯杆数据运营公司——抢占5G市场
- 中山农情统计分析系统项目实施与管理策略
- XX省中小学智慧校园建设实施方案
- 中山农情统计分析系统项目实施方案
- MATLAB函数详解:从Text到Size的实用指南
- 考虑速度与加速度限制的工业机器人轨迹规划与实时补偿算法
- Matlab进行统计回归分析:从单因素到双因素方差分析
- 智慧灯杆数据运营公司策划书:抢占5G市场,打造智慧城市新载体
- Photoshop基础与色彩知识:信息时代的PS认证考试全攻略
- Photoshop技能测试:核心概念与操作
- Photoshop试题与答案详解
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)