概念抽象数据类型数据对象、数据关系、基本操作集数据结构三要素逻辑结构、存储结构、数据运算逻辑结构类型集合结构、线性结构、树状结构、网状结构两种存储结构顺序存储和链式存储第一章1.可用抽象数据类型定义一个完整的数据结构2.有序表属于逻辑结构3.数据逻辑结构独立于存储结构4.不仅存储数据元素而且存储数据间的关系5.一个算法是问题求解步骤的描述6.算法特性有穷性、确定性、可行性、输入、输出、7.循环时间复杂度总结没层都是,将每层循环变量相乘。每层不是对于外层循环每一个i值求出内层遍历数并求和。第二章线性表线性表中除了开始元素每个元素只有唯一前驱元素1.存取方式指读写方式随机存取2.线性表快速插入与删除又存储反应逻辑关系应该采用链式存储结构3.链式存储结构内单元地址一定连续4.单链表增长头节点方便运算的实现5.线性表为了方便删除与存储数据可以使用双链表存储数据6.双链表访问前后节点更加灵活7.判断链表为空即头节点指针域为空8.末尾插入与删除结点先用带头节点的双循环链表最节省时间9.不用太大空间插入与删除不用移动大量元素采用静态链表。链表算法头插法、尾插法、逆置法、归并法、双指针法。顺序表归并排序、二分查找10.数组排序最小时间复杂度nlog2n建立单链表的时间复杂度时间复杂度排序常数《对数《线性函数《线性*对数《幂函数《指数函数《阶乘《幂值函数顺序存储优点存储密度大顺序表与一维数据均可随机存取线性表是顺序存储结构的一种顺序表存储空间与存储顺序无关静态链表用数组表示算法设计题1.写书数据结构定义类型2.正确的算法思想3.伪代码写出第三章栈、队列、数组1.栈与队列有逻辑结构、线性结构2.栈与队列都是限制点存取的线性结构3.删除栈底元素不是栈的基本操作但可调用基本操作实现4.5.与顺序栈相比链栈优势是动态分配存储空间通常不会出现满栈情况6.n个元素进出栈顺序排列有c 2n n/(n1)7.采用共栈好处节省存储空间降低上溢的可能8.上溢指满了还写下溢指空了还读9.与顺序队列相比链式队列不能根据收尾指针来计算队列的大小1.最适合做队列的是带队首和队尾指针的非循环单链表2.队头没在链表链头3.链式存储队列删除时候头尾指针可能都要修改4.栈的应用包括递归、表达式求值、括号匹配5.FIFD页面替换算法用到了队列括号匹配、表达式求值、递归用栈6.一个问题的非递归算法通常效率高效7.执行函数时局部变量一般用栈结构进行存储注意在函数嵌套时候栈头尾指针在建设好函数栈时候又往上去建设内层函数的栈8.图的广度优先搜索图要使用队列作为辅助存储空间9.在递归中系统为每一层返回点局部变量、传入实参等开辟递归工作栈来存储10.特殊矩阵采用压缩存储节省存储空间11.稀疏矩阵采用压缩存储缺点主要是丧失随机读取的特点12.适合用于压缩存储稀疏矩阵两种存储结构是三元组和十字链表第四章串13.设两个字符串s1和s2,求s2在s1中出现的位置称为模式匹配14.KMP算法特点在模式匹配时主串中的指针不会变小15.主串长n字串长为m简单模式匹配算法的时间复杂度为nm,KMP算法的复杂度nm)16.KMP中主串i与字串j不匹配时主串i不变i与next[j]比较即jnext[j];17.KMP中主串指针i与子串j不匹配时主串i不回曙第五章树与二叉树二叉树、二叉树遍历、线索二叉树、哈夫曼树1.树适合用来表示元素之间具有分支层次关系2.一棵树有n个基点所有结点的度数之和为n-13.树的路径长度是从树更根到每个节点的路径长度总和4.对于n个结点度为4的树来书树高度最多为n-35.度为4高h的树至少有h3个结点6.完全二叉树中结点没有左孩子则必是叶结点7.二叉树为空则意味着二叉树没有结点8.完全二叉树中最后一个分支结点序号为[n/2]取小9.完全二叉树叶结点比非叶结点多一或者相同10.三种遍历都先遍历左子树再遍历右子树11.二叉树前中后序中所有叶节点先后顺序完全相同12.先序与后序不能唯一确定一棵二叉树13.二叉树中序与后序相同则为空或者无右子树14.释放占用的存储空间使用后续遍历最合适15.引入线索二叉树是为了快速查找结点的前驱或者后驱速度16.线索二叉树是一种物理结构17.n个结点的线索二叉树线索数为n118.后序线索树遍历需要栈的支持19.先序与后序相反则高度等于结点数20.n个结点哈夫曼树中非也叶结点总是n-121.n个叶结点哈夫曼树最高是n22.并查集是一种双索引表示法存储的树第六章图图的存储及基本操作邻接矩阵、邻结表、邻结多重表、十字链表、深度优先、广度优先搜索、最短路径1.路径的定义由顶点与相邻顶点序偶构成的边所形成的序列1.n个顶点n条边无向图成环2.从无向图任意顶点出发的深度优先搜索访问所有顶点该图为连通图3.无向图的联通分量指无向图中极大联通子图4.有向完全图是强联通有向图5.n个若为联通无向图边数至少为n-1,若强连通图边数至少为n6.n个顶点的图是一个环则有n生成树7.n个顶点e条边的森林由n-e棵树8.图邻接矩阵主对角元素为0改图一定是完全图9一个图的邻接矩阵表示不唯一邻接表示不唯一10.用邻接矩阵法存储图所用空间大小与图的顶点数与边数有关11.邻接表有奇数个边表结点则图为有向图12.n个顶点e条边邻接表复杂度是ne13.求有向图结点的度必须遍历整个邻接表14.邻接多重表是无向图存储结构15.十字链表是有向图存储结构16.广度优先算法中当各边权值相等时广度优先算法可以解决就单源最短路径问题。17.函数中调用DFS次数正好等于连通分量数18.用邻接表存储的深度优先遍历赛诺菲类似树的先序遍历。19.判断图中是否存在回路除拓扑排序外还有可利用深度优先遍历算法20.图的广度生成树高比深度优先生成树高小或想等21.任一无向连通图最小生成树有一棵或多个22.无向连通图中没有树值相同边则最小生成树唯一。23.最小生成唯一图边数大于n-11.图最短路径一定是简单路径2.DIijkstra 求单元最短路径不允许边权值为负3.Floyd最短路径允许边权值为负但不允许负边回路4.深度拓扑关键路径可判断一个有向图是否有环5.强连通同不能进行拓扑排序6.无向图的邻接矩阵是对称矩阵7.最小生成的树的代价唯一8.关键路径是源点到江点最长路径9.呢嗯求到顶点到各点最短路径是图广度优先第七章查找顺序查找、分块查找、折半查找、树形查找、二叉搜索树、平衡二叉树、红黑树1.顺序查找适合存储结构为顺序存储结构或者链式存储结构的线性表2.折半查找对应判定树是一棵平衡二叉树3.表长为n有序表折半查找树高log2(n1)4.折半查找元素大约要log2n次比较5.逐点插入法构造二叉排序树先后插入关键字有序二叉排序树深度最大。6.按中序遍历二叉树序列是有序序列7.二叉树中查找的效率与二叉树深度有关8.二叉排序树存储中关键字最大值结点右指针一定为空9.二叉排序树理想深度log2(n1)10.二叉平衡树中可发生两次旋转的操作的操作是添加、删除结点。11.红黑树任意结点左右子树高度之比不超过212.若红黑树任意结点、左右子树高度之比不超过213.M阶树根结点至多有M棵树叶结点再同一层次根结点数据有序。1.m阶b树每个结点至多m-1个关键字2.n个关键字m阶b树应有n1)个结点3.b树不同于b树特点是能支持顺序查找4.关系数据库系统中索引适合使用b树5.只能 再顺序存储上查找的的是折半查找6.散列查找适合关键字集合与地址集合之间存在对应关系7.散列表中删除元素不能简单的删除元素8.在开放定址法中散列到同一地址引起的堆积由于同义词与非同义词之间发生冲突9.散列采用平方探测法处理冲突时不易产生聚集10.k个同义词采用线性探测法填入散列表至少进行k(k1)/2次探测11.n个元素散列表查找平均查找长度为o112.采用开放定址法解决冲突散列查找发生聚集原因主要是冲突解决方法不当13.散列查找关键字值一定同义词14.提高散列查找效率可设计散列函数或避免堆积现象15.受堆现象直接影响的是平均查找长度16.拓扑排序不属于内部排序算法17.排序算法的稳定性指相同元素的顺序相对位置不变18.基本有序提前直接插入排序算法效率最高19.直接插入排序在最后一趟开始前元素不在最终位置20.希尔排序属于插入排序21.折半插入时间复杂度为N222.希尔排序不稳定直接插入排序稳定1.希尔排序组内排序采用直接插入排序2.快速排序在数据基数基本有序条件下不利3.平均而言最好的内部排序算法是快速排序4.为实现快排使用顺序存储5.从未排序记录中选择最小关键字记录加入末尾的算法是简单选择排序6.简单选择排序比较与移动的次数为n2和n17.比较次数与初始状态无关是简单选择排序8.到任意结点路径有序的是堆9.基数排序不需要进行关键字比较10.二路归并数量级为log2n11.归并排序附加存储空间最大12.移动次数与初始状态无关的是基数排序13.二路归并将两个有序表合并为一个有序表14.排序稳定应该优选直接插入15.稳定且log2n的是归并排序16.辅助空间堆排序《快速排序《归并排序17.n-1)趟排序算法是简单与直接插入排序18.查找效率最低的平衡二叉树19.排序与原状态有关的是冒泡排序20.总比较次数一定是折半插入与简单选择21.10TB问价采用归并排序22.m个归并段建k阶归并树中不补充段则度为k结点树是m/k23.最佳归并树外部排序中作用是设计m路归并排序的优化方案24.k路归并败者树关键字最小记录时间为logk25.置换选择排序用于生成外部排序初始归并段26.多路平衡归并作用减少归并趟数27.败者树是完全二叉树28.空间复杂度归并n快排最坏n。时间复杂度为nlon2n的有快排、堆排、归并超标量流水线多条流水线控制部件不属于数据通路串行传输有PCI RS USB SATA硬件处理过程中处于关中断中断服务程序中处于开中断终端程序服务过程保护现场----开中断--------执行中断服务程序-------关中断--------恢复现场----关中断------返回现场保 开 执 关 恢 开 回试卷错题1.构造哈夫曼树查看哈夫曼编码。左小右大左低右高左0右1权重大的编码短权重小的编码长前缀特性任何编码不是其他编码的前缀。2.建成大根堆从序列末尾开始往前遍历与兄弟比较大的往上提直到根节点往下调换。3.IEEE754单精度浮点数格式符号 阶码 尾数1 8 23 移码范围1-254偏置值1271.0*2-126-------2-2-23*21274.机器数右移逻辑移位左移右移空位都补0所有数字都移算数移位符号位不参与移位右移空位补符号位。左移空位补0.5.判断进位、借位、与溢出位最高位进位与符号位进位不同时才产生溢出借位用真值判断。R1-1R2-16,R1R2则不借位不进位。R1与R2同号相减不溢出。6.树T转化位二叉树BT:左孩子右兄弟T的后根BT的中序。tree binary tree3.哈夫曼编码只有度为0与2的结点4.平衡二叉树左右子树之差不超过一8.散列表HT:线性探查平均查找长度9.KMP算法next数组10.外存12路归并只有度为0与度为12结点11.快速排序注意边界元素12.森林树F与对应的二叉树T:森林先根遍历对应二叉树先序森林后根对应后序5.二叉排序树关键字输入序列中不会调整6.DFS深度优先搜索算法先递归后输出逆拓扑有序序列7.Kruskal算法按权值递增顺序依次选取n-1条边保证n-1边构成回路9.大根堆可看为完全二叉树采用一维数组存储要求根节点值大于左右孩子结点值并不要求左右孩子有序10.B树4阶最多4-13个关键字插入关键字n/2不断进行分裂11.直接插入排序比较后移后插入简单选择排序比较后直接交换。1.链表删除于插入带头结点链表头指针一个地址大小4字节头结点一个地址4字节一个整型数字4字节第一个结点一个地址4字节一个数据4n字节2.僧林F与二叉树T转换方式为左孩子右兄弟3.哈夫曼树带权路径长度WPL为叶结点X深度6平衡二叉树LLR,RRL,LRLR,RLRL.转换方式左左右右右左左右左右右左右左。7.有向图拓扑有序序列从图中选择无入边的结点输出该结点并删除该结点的所有出边至全部结点输出。从图中选择无入边的结点输出该结点并删除该结点的所有出边至全部结点输出。8.Dijkstra算法数组dist[ ],到其他点有边则初始权值无边则初始无穷大。每次从剩下的顶点中选出dist[t]最小的顶点t将t加入s集合进行更新数组到所有顶点都加入集合。9.B树n阶B树分支最多n,结点元素最多n-1.11.插入大根堆H元素插入大根堆H插入后动态调整。9.B树B树每个结点关键字二分支减一B树没饿过结点关键字二分支数B树总叶节点数总关键字数110.基数排序、桶排序升序桶内按队列桶间按从小到大。降序桶内按队列桶间按从小到大。2.栈可根据入栈顺序判断出栈顺序是否合法。5.哈夫曼编码集、定长编码集。6.无向图G(V,E):E是图边数V是图顶点数。Vetex顶点edge边8.5阶B树除根节点外关键字数K要满足2K4,删除一个节点后从前后结点补不够从左右兄弟结点借不够借则与左右兄弟组合为新结点9.散列哈希查找装填因子越大元素越满冲突越高平均查找长度越大。11.直接插入排序与快排比较情况 数量 空间 稳定性直接 基本有序 较少 1 稳定快排 基本无序 较多 log2n 不稳定12.无向图连通图从任意顶点都有路径到大任意点完全图从任意点有边到达任何点。最少边数 最多边数无向图非连通 0 (m-1)(n-2)/2无向图连通 n-1 n(n-1)/2非强连图 0 n-1)(n-2)1强连通图 n n(n-1)7.AOV网与AOE网AOVvetex顶点顶点表示活动边表示先后顺序边无权值周末求拓扑序列。AOEedge边边表示活动表事件活动有持续时间边有权值用来求关键路径。14.排序插入排序(直接排序、折半插入、希尔排序 交换排序冒泡排序快速排序。4.哈夫曼编码加权平均长度为编码长度*频次/频次和6.普里姆算法与克鲁斯卡尔算法用于解决最小生成树9.线性探测再散列法中为解决删除操作位置依赖性问题可以使用删除标记来表示一个位置上关键字已经被删除。10.算法稳定性快排的枢轴元素交换跨度太大。堆排建堆与调整中交换大希尔跨度大。11.b树b树关键字总数1叶结点总数10.折半查找。折半查找判定树是一棵特殊的平衡二叉树每个结点的两个子树结点数绝对值之差不超过1。不稳定排序包括希尔排序、简单选择、堆、快排2.栈中表达式的转换二叉树先序遍历对应前缀表达式。中序遍历对应中缀表达式。后序遍历对应后序表达式。构造二叉树。4.无向图G(V,E)邻接多重表左为顶点V右为边6.KMP算法数组next[1]无脑写0next[2]无脑写1KMP优化nextval,nextval[1]无脑写0不同则写next不变同则传递。7.无向图的概念无向完全图连通图。8.m阶B树与B树的特点B树叶节点由指针相连6.完全二叉树第六层有叶节点则树为6层或者7层。7.调整根堆插至末尾从头到尾遍历调整8.几大排序算法3.线索二叉树定义先对二叉树进行先中后序排列。一、结点无前驱与左子树则左链域为空。二、无右子树则右链域指向后继点b。三、无左子树左链域指向前驱点d。1.进退栈不能连续三次进退栈等价于不能三个挨着。2.两端入队一端出新元素与原来元素挨着左挨着或者右挨着。4.平衡二叉树左左右右右左左右左右右左右左5.树中度度只算孩子数总结点N1祖先Ni(所有孩子6.哈夫曼树为带权路径长度最小二叉树哈夫曼树中没有度为1的结点。9.折半查找n个元素关键字比较次数最多log2n1往下取整或者log2(n1)上取整10.快排快排递归次数与元素初始排列有关划分后分区平衡则递归次数少递归类似二叉树深度log(n1)8.图的概念首结点与尾结点相同的路径称为回路序列中结点不重复的路径称为简单路径。邻接矩阵空间n2邻接表ne)。存在回路的有向图不存在拓扑序列。9.Hash表查找效率取决于散列函数、处理冲突方法、装填因子。表中记录数于表长之比处理冲突方法拉链法不存在聚集现象。线性探测法易引起聚集现象。3.二叉树遍历前序序列与后序序列不能唯一确定一棵二叉树但可以确定二叉树中结点的祖先关系。两结点前序xy,后序yx时x为y祖先。4.平衡二叉树非叶结点平衡因子为1.则cNC(N-1)C(N-2)18.最小生成树代价唯一。普利姆最小生成树最小时的生成树不一定唯一。只有当各边权值不同prim算法与krskal算法得到的最小生成树相同。5.广度优先遍历邻接表结构顶点表、边表有向图为出边表借助队列。每个顶点入队一次顶点表遍历On。访问每条边出边表遍历Oe。6.有向图的邻接矩阵任意有向图邻接矩阵中对角线以下元素为零则存在拓扑序列可能不唯一。10.排序简单选择排序每次选择未排序中的最小元素插入排序子序列。希尔排序子表排序局部有序。堆排大根结点与表尾交换最终确定位置11.排序折半插入与直接插入都是把元素插在前面有序子表。直接插入采用顺序查找折半插入采用折半查找。1.链表两顺序链表合并最差时间复杂度未Onm)O(max(n,m))5.线索二叉树6.二叉排序树二叉排序树删除结点后又插入若为叶结点则前后相同非叶节点不完全相同。7.邻接矩阵求顶点的度邻接矩阵非对称则为有向图度为出度与入度之和对应行加对应列。8.广度优先遍历入队查找。10.n阶B树定义3.平衡二叉树中平衡因子为0的分支结点包含根4.三叉树T带权路路径长度最小。n叉树叶结点n0-1)%(3-1)u10.m阶b树定义根结点最少含一个关键字其他结点最少关键字个数【m/2]-114.机器码运算左移、右移、相加高两位进位相同则不溢出15.海明码检验校验位K位数据位n位则海明码纠正错位妈祖2k次》nk119.接口标准usb是外部设备总线标准设备总线用于设备与设备控制器之间。pci\agp\pcie为系统局部总线标准连接主存、视频。20.RAID可靠性对磁盘镜像处理与奇偶校验条带化基数将IO负载分储多磁盘。提高IO并行能力。21.中断io与DMA:中断io申请CPU时间发生在指令结束之后一个数据传送由软件控制。DMA方式基本单元数据块DMA申请总线使用权仅传送前后端需CPU干预传送过程与控制器控制完成的。3.出入队指针end1指向对头元素则出队是先读数后end1再加1end2指向尾元素后一个位置入队操作是先存数后end加一。4.线索二叉树线索二叉树左指针指向前驱右指针指向后继。5.森林与树森林F中叶节点数等于二叉树T中左孩子指针为空的结点个数。6.4阶B树15个关键字则结点树最多是根结点最少含一个关键字非根结点最少含【4/2]-11个关键字。1.递归函数调用先进后出栈先调用mian()函数然后调用S(1)函数故main()函数压底。2.出栈序列以a\b\c\d入栈出栈序列右C2n n/(n1)种9.排序基数排序元素移动次数有关键字初始排列次序有关直接插入排序、冒泡、快排移动都与初始序列有关。11.希尔排序首先元素分割为若干子序列后分别进行直插排序后缩减增量至基本有序再对全体元素进行一次直插排序2.栈容量3.由嵌套深度最深嵌套为6.图各顶点度均大于或者等于2的无向图必有回路7.分块查找n个元素每块元素根号n均分8.B树n个关键字构成的b树种类有9.二次探查通过二次函数来决定下一个检查位置。10.二叉树分支结点非叶结点。链式二叉树根保存的是最后计算的运算符6.图Dijkrstra:单源最短路径。Floyd:多源最短路径。BFS:适用于无权图。8.M阶b树m4.根为1到3.非根为m/2取上-116.指令集体系结构ISA:控制方式。指令格式机器村种类数量位数寻址方式。17.RISC:RISC指令定长简单易采用流水线提高指令执行吞吐量。RISC架构采用load/store架构控制逻辑采用硬链接非微程序控制。18.CPI与Cache缺失率cache缺失会导致额外内存访问时延。从而增加访存指令如load/store执行的平均时钟周期数。20总线带宽总线频率*总线带宽。每周期传送4次总线工作频率1333MHZ总线款段64位。带宽64b*1333M21.DMA设备键盘针式打印机数据传输量少痛殴工厂不需使用DMA同步处理大量网络数据传输速率高位减少 CPU再传输资源中大量被占用网卡与固态硬盘适合采用DMA技术。1.prim最小生成树prim算法时间复杂度位O|n|2,不依赖于|e|适用于边稠密图每次选择一个点加入。2.kruskal算法时间复杂度O|E|log2E适用于边稠密图每次选择一条最短边。最小生成树不唯一但权值唯一。各边权值不同时tree唯一。最短路径带权图Dijkstra:单源最短路径O|N|2. Floyd:点对点最短路径O|N|3.Floyd允许图中有负边但不允许包含负权值边组成的回路。BFS算法O|n|2或O|n||e|,无权图最短。3.B树与B树M阶B树除根结点以外非叶结点至少有m/2向上取整课子树。B树多叉平衡排序树。B树字节数关键个数相等。2.所有叶结点包含全部关键字及指向相应记录的指针且叶结点中将关键字按大小顺序排列。相邻叶结点按大小顺序相互连接起来。B树非根结点关键字范围m/2nmB树m/2-1nm-1 根1nm-1一、线性表应用二、数组应用三、栈的应用四、队列应用五、树与二叉树应用哈夫曼树与哈夫曼编码、并查集及其应用六、图的基本应用最小生成树、最短路径、拓扑排序、关键路径七、查找算法分析及应用散列表、顺序查找、折半查找、散列表八、排序算法及应用选择排序、堆排序、外部排序一、画图作答画数据结构状态示意图二、代码作答写数据结构、基本操作代码三、文字简答手算分析算法运行、数据结构算法选择、算法性质分析、文字描述算法思想、数据结构性质推演直接插入排序原理同插牌一样。顺序发定位插入位置直接插入排序。二分法定位插入位置二分插入排序。缩小增量多变插入排序希尔排序。一、顺序表先判断能否用快排求解。快排擅长将乱序数组排成有序归并二路归并擅长将有序数组合并为一个数组。二、链表不支持随机访问。基本功遍历、插入、删除。头插法原地逆置。尾插法保持原序。三、二叉树无时空效率要哦求。求树高、树宽、以及WPL四、图。定义邻接矩阵、邻接表图的遍历深度优先、广度优先搜索图应用(DFS,BFS.管堵优先求最短路径拓扑排序。