软考中级(软件设计师)——数据结构与算法(上午10分题)(下午15分)
目录
软考中级(软件设计师)——数据结构与算法(上午10分题)(下午15分)
数组与矩阵(★★)
稀疏矩阵
线性表(★★★★★)
链表的基本操作
队列与栈
广义表(★★)
二叉树遍历
反向构造二叉树
哈夫曼树
图(★★)
完全图
拓扑排序
时间复杂度与空间复杂度(★★★★★)
深度优先·广度有限
数组与矩阵(★★)
数组的下标从0开始。
一维数组a[n]：a[i]的存储地址为: a i*len
二维数组a[m][n]：
a[i][j]的存储地址(按行存储)为: a (i*n j)*len a[i][j]的存储地址(按列存储)为: a (j*m i)*len
例题：
已知5行5列的二维数组a中的各元素占两个字节,求元素a[2][3]按按行优先存储的存储地址?
需要使用：a (i*n j)*len，其中len是两个字节，故而是2，带入公式可得：
a (2*5 3)*2=a 26
稀疏矩阵
线性表(★★★★★)
顺序表：一维数组
链表：单链表、循环链表、双向链表。
链表的基本操作
单链表删除结点 单链表插入结点 双向链表删除结点 双向链表插入结点
顺序存储与链式存储对比图：
队列与栈
队：先进先出
栈：先进后出
广义表(★★)
1、广义表是n个表元素组成的有限序列,是线性表的推广。
2、通常用递归的形式进行定义,记做: LSO (aO, a1.. an),
3、基本运算:取表头head(Ls)和取表尾tail(Ls)。
4、若有:LS1=(a, (b,c)，(d,e) )
5、head(LS1)= a
6、tail(LS1)=((b,c) , (d,e))
7、例1，有广义表LS1=(a, (b,c)，(d,e) )，则其长度为?深度为?
8、例2，有广义表LS1=(a, (b,c)，(d,e) ) ,要将其中的b字母取出，操作就为?
例题1答案:长度为3 ,深度为2。 例题2答案: head(head(tail(Ll)))。
树与二叉树(★★★★★)
结点的度 树的度 叶子结点 分支结点 内部结点 父结点 子结点 兄弟结点 层次(也叫树的深度)
满二叉树、完全二叉树、非完全二叉树，三类。
二叉树遍历
前序遍历·根左右 中序遍历·左根右 后序遍历·左右根 层次遍历·从上-下，从左-右。
层次遍历：1-2-3-4-5-6-7-8 前序遍历：1-2-4-5-7-8-3-6 中序遍历：4-2-7-8-5-1-3-6 后序遍历：4-8-7-5-2-6-3-1（缺节点的自行补充）
反向构造二叉树
结果：
哈夫曼树
权就是边使用的频次。
图(★★)
完全图
图的存储-邻接矩阵
拓扑排序
图的最小生成树
时间复杂度与空间复杂度(★★★★★)
时间复杂度：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。
空间复杂度：是对一个算法在运行过程中临时占用存储空间大小的量度 。
空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。
算法基础及常见的算法(★★★★★)
深度优先·广度有限
图的遍历
