​

 ​编辑

软考中级(软件设计师)——数据结构与算法(上午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渐进表示法。

算法基础及常见的算法(★★★★★)

 深度优先·广度有限

图的遍历

​编辑

​