没有合适的资源?快使用搜索试试~ 我知道了~
希赛软件设计师归纳2006版和2012版
2星 需积分: 9 5 下载量 132 浏览量
2018-07-25
11:40:37
上传
评论
收藏 63.64MB DOC 举报
温馨提示
本文件为希赛2006版软件设计师和2012版软件设计师的视频上午卷知识点归纳起来总结,以文字和截图形式展示,望能帮助考生通过软件设计师考试
资源推荐
资源详情
资源评论
软件设计师上午
一、数据结构
1.数组与矩阵
数组:存储同类型数据数据元素集合。数组是线性表,因为数组一开始定义的时候就需要
定义最大能存储多少个数据。数组分:一维数组(a[1],a[2]…),二维数组(a[0][0],a[0][1]
…),
数组存储:不同数组之间能转,例如二维数组转一维数组,有按行存储(优先按行顺序存
储,例如:a[0][0]=b[0],a[0][1]=b[1],a[0][2]=b[2]….),有按列存储(优先按列顺序存储,
例如:a[0][0]=b[0],a[1][0]=b[1],a[2][0]=b[2]….),
数组存储地址:
(二维数组存储位置,1.必须要看清楚首地址是不是 a[0][0],有些题目首地址不是从 00 开始
的,假如题目没有说明首地址,就从 00 开始计算,假如题目说明按照说明的计算;2.必须
看清楚题目是按行存储还是按列存储,题目一般会明示,没明示的就按行的;3.看清楚一
个数组占多少字符,这个是 len 的数值;4.个人建议做这些可以按照题目画数组,然后直接
得出结果。)
答案:(i(2)*n(5)+j(3))*len(2)=26
稀疏矩阵:矩阵,类似于二维数组的东西,假如矩阵中非零元素的个数远远小于矩阵元素
的总数,并且非零元素的分布没有规律,则称该矩阵为稀疏矩阵。
特殊矩阵:如果非零元素的分布存在规律(如上三角矩阵、下三角矩阵、对称矩阵),则
称该矩阵为特殊矩阵。
答案:这些题目,将数据带进去就知道结果,带进去最好是一些很特殊的值,,例如 A[0]
[0],得出选 A
(特殊矩阵:1.一个存储空间占用一个字符;2.所需空间数为: n(n+1)/2。)
2.数据结构
2.1.线性表
线性表:是一个有序数据元素的集合,例如:线性表,栈,队列,双队列,数组,串
非线性表:一个无序数据元素集合,例如:二维数组,多维数组,广义表,树,二叉树,图
线性表:线性结构是一个有序数据元素的集合,线性表一般分 2 中存储结构:顺序表(计
算机内存中以数组的形式保存的线性表,连续存放在内存空间的表。)和链表(物理存储
单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实
现的,不连续存放在内存的空间表,以链作为指向而形成线性结构。其中链表又有:单链
表,循环链表,双向链表)。
单链表操作:删除:将要删除的数据的最后一个指针域复制,然后放到要删除节点的前一
个节点的指针域粘贴。增加:将增加指针的前一个指针域复制,然后放到要增加节点的最
后一个节点的指针域粘贴,然后将增加指针的前一个指针域指向增加节点的第一个数据。
双链表操作:删除:将要删除的数据的最后一个指针域指向要删除的后一个指针的指针域,
然后将删除的后一个指针的指针域指向要删除的数据的前一个指针域。增加:将要增加的
前一个指针域指向增加的指针域,然后增加指针域指向要添加的后一个指针域,后一个指
针域,然后又指向前一个指针域,增加指针域指向前一个指针。
栈:先进后出,其中注意是:假设:0,1,2,3 进栈,出来结果有可能是:0,1,2,3,也有可能是:
0 进去了 0 出来,1 进去了 1 出来,。。变成 0,1,2,3
队列:先进先出,其中注意是:它包含了循环队列,他的特点是:头指针和尾指针相等代
表空队列,尾指针+1 等于头指针代表满队列,队列最后一个一定不存数据。尾指针不是指
向队伍实际队尾位置,都是实际位置+1
上题注意点:1.队尾实际位置,也就是队尾指针位置的前一个位置;2.mod 求余,知道 m
就是队伍元素个数,length 也是元素个数,所以 a,d 不对,然后要弄成为(rear+1)MOD m
才对,所以 C
链表和顺序表性能对比:
PS:什么是密度:线性表要了一个空间,里卖弄全部放数据,所以密度是 1,但是链表是
要了很多个空间,每个空间放一个数据,所以是小于 1。
什么是读运算:要知道 a[5]的数值,然后线性表就是起始位置+5,但是链表就要读下去,
所以链表比较复杂
为什么插入删除为链表为 1:因为链表增加删除其实就是对添加元素或者删除前后元素操
作,所以是 1,但是线性表就要操作很多数据
3.广义表
广义表(又称列表)是一种非线性的数据结构,是线性表的一种推广。
LS=(a,(b,c),d),其中 LS 是广义表名字,a 是数据元素(又称为原子),a,(b,c),d 是表的元素,
(b,c)是子表。广义表元素个数是长度(最外层包含元素个数),当长度为 0 代表表为空,
递归定义重数是深度(原子深度是 0,空表深度是 1)
答案:长度是 3,深度 2.
4.树与二叉树
4.1 树概念
树:是包含 n(n>0)个结点的有穷集
结点的度:一个结点含有的子树的个数称为该结点的度树的度: 一棵树中,最大的结点的度
称为树的度
叶子结点:又叫终端结点,度为 0 的结点称为叶结点
分支结点:又叫非终端结点,度不为 0 的结点
内部结点:度不为 0 的结点,且结点不是根结点
父结点:又叫双亲结点,若一个结点含有子结点,则这个结点称为其子结点的父结点
子结点:又叫孩子结点,一个结点含有的子树的根结点称为该结点的子结点
兄弟结点:具有相同父结点的结点互称为兄弟结点
层次:从根开始定义起,根为第 1 层,根的子结点为第 2 层,以此类推
一棵树总结点数是:所有度数+1,所以上题上面的总结点数是:2*3+2+1=9,所以 0 个结
点的就是 9-2-1=6
4.2.二叉树
二叉树:二叉树是每个结点最多有两个子树的树结构
二叉树和树的区别:二叉树不是特殊的树;树的任何一个结点有多个子结点,但是二叉树
结点只能有 2 个;树中子结点是无序的,但是二叉树是有序的,分为左子结点和右子结点;
二叉树是特殊的存储结构。
二叉树分为:满二叉树(完整的二叉树);完全二叉树(假设有 n 层,n-1 层是完全二叉树,
但是最后一层是一个从左至右连续顺序排列的二叉树)
4.3.遍历
树与二叉树遍历
前序遍历:先访问根结点,然后访问根结点的最左孩子,假如最左孩子有结点就继续找孩
剩余63页未读,继续阅读
资源评论
- MrStub2019-09-18版本太久了
hurrytttt
- 粉丝: 6
- 资源: 14
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功