数据结构题.docx
- 文档编号:4593609
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:12
- 大小:142.97KB
数据结构题.docx
《数据结构题.docx》由会员分享,可在线阅读,更多相关《数据结构题.docx(12页珍藏版)》请在冰点文库上搜索。
数据结构题
排序
1.快速排序、希尔排序、选择排序、堆排序不稳定(快些选一堆)
2.冒泡排序、插入排序、归并排序、基数排序稳定
3.一趟冒泡排序,是将“大的”字母沉底(如果前面的大于后面的就交换,知道碰到比它大的,之后用那个比它大的继续比--最大的放在最后)
4.选择排序时间复杂度最差
5.选择排序(最大最小),堆排序(最大最小),冒泡排序(最大最小),快速排序(一个数左边都是小于等于它,右边都大于等于它)一趟都能确定一个元素的位置,直接插入排序不行,插入排序在每趟排序后能确定前面的若干元素是有序的,2路归并排序,第一趟排序结束都可以得到若干个有序子序列
6.拓扑排序运算只能用于有向无环图
7.归并排序中,归并的趟数是(O(logn))
8.堆排序平均执行的时间复杂度和需要附加的存储空间复杂度分别是(O(Nlog2N)和O
(1))
9.只有100MB的内存,需要对1GB的数据进行排序,最合适的算法归并排序
10.对于基本有序的序列,按照冒泡排序方式最快
11.两分法插入排序所需比较次数与待排序记录的初始排列状态无关
12.快速排序:
基准元素和末尾比,小于末尾不动,否则交换,接着和第一个比同理,一趟后找到位置,第二趟是左边和右边同时用同样的方法进行比较,又有两个确定位置。
13.数据表A中每个元素距其最终位置不远,为节省时间排序,应采用插入排序
14.外排中使用置换选择排序的目的,是为了增加初始归并段的长度
15.对n个数字进行排序,期中两两不同的数字的个数为k,n远远大于k,而n的取值区间长度超过了内存的大小,时间复杂度最小可以是O(n)
16.按当前词所在的顺序排序表示要稳定
17.只有快速排序,基数排序,二路归并排序,需要空间(会计归)logn,
18.归并排序和堆排序最坏为O(nlogn),基数排序为O(d(r+n)),其它为O(n^2)
19.插入排序为从第二个开始依次和它前面比它大的交换,希尔排序是步长依次减少的插入排序,基数是0-9个桶,依次把个位相同的放入桶,倒出,再把十位相同的倒入,倒出,以此类推最后就有序了。
计数排序是几个有范围的桶,桶内排好序然后倒出来。
快速排序是和最后一位比,第二位,以此类推。
20.优化过后的冒泡排序算法关键字比较的次数与记录的初始排列次序也有关
21.叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左子树的值、小于等于其右子树的值,注意不是仅仅是孩子而是整颗子树。
22.拓扑排序:
由一个集合上的一个偏序来得到集合上的一个全序。
所以只能用在有向图中,且如果有向图存在环的话也无法得到图的所有节点,所以拓扑排序只能用在有向无环图中-AOV网。
个数就是符合前驱就行。
23.快速排序比较快的,先找中间的在开头的,之后代入看看吧
24.如果待排序序列中两个数据元素具有相同的值,在排序前后它们的相互位置发生颠倒,则称该排序算法是不稳定的
25.几乎有序时,快排的时间复杂度退化到O(n*n)最慢,无序时,快排才比较省时间O(n*logn)
26.记的插入排序第n趟是n+1个数有序
27.前面有序用插入排序,比较次数少
28.在外部排序时,利用选择树方法在能容纳m个记录的内存缓冲区中产生的初始归并段的平均长度为2m个记录
29.内排序:
我们常用的选择、交换、插入、归并、基数排序都属于内排序,只用在内存读一次原始数据即可完成排序。
30.外部排序:
指的是大文件的排序,即待排序的记录存储在外存储器上,待排序的文件无法一次装入内存,需要在内存和外部存储器之间进行多次数据交换,以达到排序整个文件的目的。
外部排序最常用的算法是多路归并排序,即将原文件分解成多个能够一次性装入内存的部分,分别把每一部分调入内存完成排序。
然后,对已经排序的子文件进行多路归并排序。
31.采用递归方式对顺序表进行快速排序,递归次数与每次划分后得到的分区的处理顺序无关
32.堆是具有以下性质的完全二叉树:
每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆。
33.堆排序:
按数组顺序构造完全二叉树,之后从最后一个非叶子节点n/2向下取整,开始调整结构,看是大顶堆还是小顶堆,每次调整要是倒置下面不对了就继续调整,从左往右,从下往上依次调整。
一次完了后将顶和最后一个元素交换位置,接着对其前n-1进行同样操作。
34.若将顺序存储更换为链式存储,则希尔排序、堆排序算法的时间效率会降低
35.计数排序的空间复杂度为O(k),计数排序的时间复杂度为O(n+k)
36.选择排序元素比较次数与元素的初始排列无关,希尔、归并、插入都有关
37.排序趟数与序列的原始状态有关的排序方法是优化的起泡和快速
38.堆排序适用于个数较多的情况,当深度为k时,最多比较2(k-1)
39.冒泡排序最多比较n(n-1)/2次
40.希尔排序平均时间复杂度为O(n^1.3)
41.2路插入需要n个辅助空间
42.二叉排序树比折半查找快
43.归并,基数排序是外部排序其它为内部排序
44.
查找
1.能用二分法进行查找的是顺序存储的有序线性表
2.在长度为n的顺序线性表中顺序查找值为x的元素时,查找成功时的平均查找长度为(n+1)/2
3.只要数据元素保持有序,则查找时就可以采用折半查找方法(错),其存储必须是顺序存储,链式不行
4.一个文件包含了200个记录,若采用分块查找法,每块长度为4,则平均查找长度为:
(50+1)/2+(4+1)/2=28分为50份找到哪个块,然后加上块内顺序查找的时间
5.有序表中有1000个元素,用二分查找查找元素X最多需要比较(log(1000)向上取整)次
6.判断是否有环的方法包括:
深度优先遍历(DFS),拓扑排序
7.二分查找,查找成功与查找不成功,最坏的情况下,都需要比较[logn]+1(向下取整),或者[log(n+1)](向上取整)
8.图的BFS生成树的树高小于等于比DFS生成树的树高
9.在有序列表中通过二分查找的复杂度(平均查找长度)一定是O(log2n)
10.对于有序列表的排序最快的是插入排序
11.记的计算的时候二分查找它的左右是中间值的前或后要加减1的,不能直接按中间值再算中间值
12.二元查找树的任何结点的左右子树都是二元查找树(就是左边大右边小的一种构造结构)
13.长度为12的无重复有序表,按折半查找法进行查找,查找成功所需的平均比较的次数为37/12。
这个就是构造出树来,计算(1*1+2*2+4*3+5*4)/12就是根为1次,之后每层加一完了除以个数
14.由先序遍历,后续遍历,中序遍历其中两个求后一个,可以先确定根和左右子树,接着对左右子树进行同样操作即可画出全图
15.ASL平均查找长度,等于每个数查找的次数和除以个数,例如哈希和树都可以这样计算
16.链地址法就是哈希之后冲突了就放到链里
17.大数求log记得拆分法估算
18.在一个有8个int数据的数组中,随机给出数组的数据,找出最大和第二大元素一定需要进行9次比较。
即两两比较7次得出最大的,之后把和最大的比较过的元素组织起来再比一次。
19.单词查找树(Trie树),是一种树形结构,是一种哈希树的变种。
典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。
它的优点是:
利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希表高。
20.红黑树和avl树都属于自平衡二叉树;两者查找、插入、删除的时间复杂度相同;包含n个内部结点的红黑树的高度是o(logn);TreeMap是一个红黑树的实现,能保证插入的值保证排序
21.当采用分快查找时,数据的组织方式为数据分成若干块,每块内数据不必有序,但块间必须有序,每块内最大(或最小)的数据组成索引块
22.SelectionSort选择排序,每迭代一次就确定一个元素的位置
23.顺序,分块,折半,哈希
24.给定一个整数sum,从有N个有序元素的数组中寻找元素a,b,使得a+b的结果最接近sum,最快的平均时间复杂度是O(n)
25.折半代码记得循环x<=y,m-1,m+1这3条易错点
26.深度优先搜索要借助栈;广度优先搜索要借助队列;
27.朴素匹配算法时间复杂度O((N-P+1)*P)KMP匹配算法时间复杂度为O(N+P)
28.分块找出,块间有序,块内无须,平均查找长度(b+1)/2+(s+1)/2,用折半找块则平均查找长度近似为log(n/s+1)+s/2
29.二叉排序树,左子树上的值小于根节点,右子树上所有点的值均大于它的根节点。
中序遍历为有序
30.平衡二叉树(AVL),深度为logn
31.折半查找长度为n的表的判定树是唯一的,含有n个节点的二叉排序树是不唯一的。
32.B-树,所有的叶子节点都在同一层
33.B+树
树和二叉树
1.树的深度,高度就是有几层
2.树的度为所有节点中最大的孩子个数,单个节点的度为孩子个数,如叶子节点的度为0。
3.二叉树的第i层至多有2^(i-1)个节点
4.深度为k的二叉树至多有2^k-1个节点
5.具有n个节点的完全二叉树深度为log2n取整+1
6.对于任何一颗二叉树,若其终端节点数为n0,度为2的节点数为n2,则n0=n2+1
7.一颗完全二叉树的节点按层次编号
a.如果i=1,则节点i是二叉树的根
b.如果2i>n,则节点i无左孩子,否则左孩子为2i
c.如果2i+1>n,则节点i无右孩子,否则右孩子为2i+·1
8.k叉树的非空链域为(k-1)n+1
9.遍历
先(根)序遍历(根左右):
ABDHEICFJKG
中(根)序遍历(左根右):
DHBEIAJFKCG
后(根)序遍历(左右根):
HDIEBJKFGCA
10.二叉树用来存储操作数,计算。
其中叶子节点存储数据,非叶子节点存储操作
11.路径长度指节点之间的分支数目,树的路径长度为根节点到每个节点的路径长度和,完全二叉树是路径长度最小的二叉树,但不唯一
12.哈夫曼树,让两个权重最小的节点组合,之后依次添加权重小的节点。
有n个节点则共有2n-1个,其中辅助空间为n-1个
13.哈夫曼编码就是组成哈夫曼树之后,左边为1,右边为0写在分支上,每个叶子也就是元素的表示为从根到叶子的分子顺序排序。
是一种变长编码,可以使得发送的数据长度最少。
14.把一棵树转换成二叉树后,这棵二叉树是唯一的。
15.3个节点可以构造5种不同的二叉树。
n个节点构成的二叉树个数为C(2n,n)/n+1
16.一个具有1025个节点的二叉树高度为11-1025
17.利用二叉链表树存储树,则根节点的右指针为空(孩子兄弟,它没兄弟)
18.用二叉链表表示有n个节点的二叉树时,值为空的指针域的个数为n+1(每个节点都有一个前驱,加上根没有前驱的1个)
19.设森林F对应的二叉树为B,它有m个节点,B的根为p,p的右子树节点个数为n,则森铃F的第一颗树的节点个数为m-n。
(森林变二叉树,首先把每个树变成左孩子右兄弟,之后把它们合起来,所以根节点的右子树就是除第一颗外的所有节点)
20.树中分支数=n-1=度与节点数相乘节点数=每个度的节点相加
21.完全二叉树叶子节点数:
总节点数=n0+n1+n2n0=n2+1n1为0或1则可计算出n0的值了
22.一颗二叉树的高为h,节点度为0或2,则这颗二叉树最少有2h-1个
23.前缀编码:
任何一个编码都不是其他任何编码的前缀(最左子串)
24.线索二叉树是一种逻辑和存储结构
25.引入二叉线索树的目的是加快查找节点的前驱和后继的速度
26.n个节点的线索二叉树上含有的线索数为n+1个
27.若X是二叉中序线索树中一个有左孩子的节点,且X不为根,则X的前驱为X的左左子树中的最右节点
28.先序等于后序则它高度等于节点数或空
29.已知一颗二叉树的线序和后续不能唯一确定树的形状
30.满二叉树一定是完全二叉树,完全二叉树不一定是满二叉树。
31.哈夫曼树没有度为1的节点
32.
栈和队列
1.栈:
后进先出
2.栈和队列是受限的线性表
3.栈顶等于栈底时栈为空
4.共享栈,两个栈的栈底一个在数组开头一个在结尾,就可以共享中间的空间了
5.栈用来倒叙,如进制转换,除一个数余数,倒置。
括号等对称符号判断,递归
6.队列:
先进先出
7.循环队列判满:
设置标志位或牺牲一个位置,当尾的下一个尾头时满。
避免假溢出
8.循环队列位置:
数组Q[n],f为队头,r为队尾,元素个数小于n,队列中元素个数公式为(n+r-f)%n
9.循环队列添加一个元素则其位置为:
存储在A[0...m]r=(r+1)%(m+1)
10.多维数组中的元素不是线性的也不是树形的
11.顺序存储的队列删除一个元素时,首先将后移一位队首指针
12.对于任意非空二叉树,要设计其后序遍历的非递归算法而不是用堆栈,最合适的是采用三叉链表
13.
图
1.邻接矩阵存储图,一个数组存点,一个数组存关系。
无向图可以压缩到一半,有向图不可以,无权的存01,有权的存具体数字
2.邻接表,一个数组,里面存链表,后面连接连接点对应的位置(下标)。
对于有向图,只存出来连接的点。
3.n个顶点,e条边的无向图,若采用邻接表作为存储结构,则需要n个表头节点和2e个表节点,而邻接矩阵需要n(n-1)/2的空间。
稀疏图O(nlogn)用邻接表省空间
4.消除递归用循环加栈
5.最小生成树,克鲁斯卡尔时间复杂度eloge,使用邻接表,边。
普里姆算法O(n^2),使用邻接矩阵,表
6.关键路径:
最长路径,考最早最晚时间
7.最短路径:
迪杰斯特拉,弗洛伊德算法O(n^3)如果求一个点到指定一个点的话是O(n^2)
8.n个点的有向图,最多有n(n-1)条边。
无向图中最多有n(n-1)/2条边
9.生成树的边数,n个点,n-1条边。
n个点的连通无向图最少有n-1条边
10.n个点的强连通图,最少有n条边
11.邻接表深度优先遍历和二叉树的先序遍历相似,广度优先类似于按层序遍历
12.n个顶点,e条边,采用邻接表存储,需要表头大小为n,2e个边节点
13.
数组与特殊矩阵
1.稀疏矩阵压缩存储,三元组,(行,列,值)
2.数组A中每个元素3字节,i为1-8,j为1-10,则A[5,8]的地址,按行存储为(4*10+7)*3,按列存储时为(7*8+4)*3
3.
线性表
1.插入一个元素平均移动位置为n/2,有n+1个位置
2.删除一个位置有n个位置,平均移动(n-1)/2
3.线性表只有一个头一个尾,除它们外元素的前驱和后驱只有一个元素
4.顺序表优点:
存储简单,缺点:
插入删除需要大量移动,需要占据连续空间造成空间碎片
5.链表优点:
插入删除简单不需要大量数据移动,缺点:
只能顺序访问不能随机访问
6.顺序表,第一个元素存储地址100,元素长度2,第5个元素的位置:
100+2*(5-1)=108
7.二维数组的第一维可以省略(表示倍数)机器根据后面赋值可自动计算,第二维不能省略(表示长度)doublea[][3]={1.0};
8.静态链表中的指针表示下一个元素在数组中的位置
9.从表中任一节点出发能扫描所有元素:
顺序表,双链表,循环链表
10.线性表有链式和顺序存储两种
11.
数据结构基本概念与算法评价
1.数据元素是数据结构的基本单位
2.数据项结构中的最小单位,一个数据元素可以由一个和多个数据项构成
3.数据结构是带”结构“的数据元素的集合,结构指元素之间的关系
4.数据结构分为逻辑结构和物理结构
5.逻辑结构有:
线性结构、树形结构、图状结构、集合结构
6.数据结构分为线性和非线性两种
7.算法:
有穷性、确定性、可行性、有0个或多个输入,有一个或多个输出
8.设计算法考虑:
正确性,可读性,健壮性,效率和低存储
9.算法的数据存储:
输入数据所占空间,程序本身所占空间,辅助变量所占空间
10.数据结构在计算机内存中的表示是指数据的存储结构
11.算法的时间复杂度取决于:
问题的规模,待处理的数据状态,算法的优化程度
12.
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构
![提示](https://static.bingdoc.com/images/bang_tan.gif)