计算机复习材料补充-面向信息技术类专业数据结构基础知识

1、数据结构基础知识整*1、数据：是信息的载体，能够被计算机识别* 2数据结构基础知识整*1、数据：是信息的载体，能够被计算机识别* 2。* 3* 4* 5* 6*7* 8*9、算法的时间复杂度T(n)：是该算法的时间耗费，它是该算法所求解问题规模n趋向*10和平均时间复杂度：由于算法中语句的频度不仅与问题规模n有关，还与输* 11、数据的运算：指对数据施加的操作。数据的运算是定义在数据的逻辑结构上的* 12、线性表：由n(n0)个结点组成的有限序列。其逻辑特征反映了结点间一对一的*13、顺序表：顺* 14、单链表：每个结点有两个域：一个值域data；另一个指针域next，用来指向该* 15、双链

2、表：每个结点中增加了一个prior，用来指向该点的直接前趋结点。它是双*16、循环链表：是一种首尾相接的链表。单循环链表形成一个* 15、双链表：每个结点中增加了一个prior，用来指向该点的直接前趋结点。它是双*16、循环链表：是一种首尾相接的链表。单循环链表形成一个next链环，而双循环链*17密度为1，而链表密度小于1*18（stack* 19、LIFO表：即后进先出表，修改操作按后进先出的原则进行。譬如栈就是一种*20、顺序栈：采用顺结构的栈，称为顺序栈*21* 22队列只允许在一端进（queue*23、FIFO表：即先进先出表。譬如队列就是一种FIFO*24* 25、循环队列：为克服

3、顺序队列中假上溢现象，将向量空间想象为一个首尾相接的圆环这种向量称为循环向量在其中的队列称为循环队列*26、链队列：采用链*an28、空白串：由一个或多个空格组成的串称为空白串*29、空串：长度为零的串称为空串，它不包括任何字符*30、顺序串：串的顺*31、链式串：串的链32、模式匹配：子串的定位运算又称为串的模式匹配*33、对称矩阵：元素满足aij=aji（0i,jn）的矩阵*34、三角矩阵：主对角线以上或以下的元素（不包括对角线）均为常数的*34、三角矩阵：主对角线以上或以下的元素（不包括对角线）均为常数的矩阵*35、带状矩阵：所有非零元素均集中在以主对角线为中心的带状区域的矩阵*36、稀

4、疏矩阵：非零元素远远少于矩阵元素的矩阵* 37、广义表：有n个元素a1,a2an组成的有限序列，其中n可以是原子或一个广义表* 38、三元组表：若线性表顺*39*40排序：假设给定含有n（R1,R2,Rn）的文件，其相应的关键字（K1，K2，,Kn）,则排序是确定一个排列（P(1),P(2),P(n)Kp(2)Kp(n)p(n)* 41、稳定排序：假设在待排序的文件中，存在两个或两个以上* 42排序若排序算法所需的辅助空间并不依赖于问题的规模n，即辅助空间为* 43、堆：n个关键字序列K1，K2，,Kn，称为堆，当且仅当序列满足如下性质K2i，且KiK2i1或KiK2i，且KiK2i1*44、

5、查找：即给定一个值K，在含有n个结点的表中找出关键字等于给定值K* 45、动态查找表：若在查找的同时对表做修改操作（和删除，则相应的表称* 46、静态查找表：若在查找的同时不对表做修改操作（和删除*47*48*50、散列函数：在关键字和表地址之间建立的对应关系h*51。*52* 53、装填因子：设m和n分别表示表长和表中填入的结点数，则将=n/m* 1*50、散列函数：在关键字和表地址之间建立的对应关系h*51。*52* 53、装填因子：设m和n分别表示表长和表中填入的结点数，则将=n/m* 1、索引、散列。 2*3、一个算法的效率可分为时间和空间效率。 4*5。 6*7、按顺8、线性表中结点

6、的集合是有限的，结点间的关系是一对一的* 9、在n个结点的顺序表中(删除)一个结点需平均移动n/2（(n-1)/2）个（删除）位置i* 10任意一结点的时间复杂度均为O(1)，因此，顺序表也称为随机* 11、在民个结点的单链表中要删除已知结点*p，需找到它的直接前趋结点的地址，其*12、在双链有中要删除已知结点*p，其时间复杂度为O(1)* 13、在单链表中要在已知结点*p一新结点，仍需找到*p的直接前趋结点的址，其时间复杂度为O(n)；而在双链表中，完成同样操作其时间复杂庶O(1)能遍历链表。 15、在栈中存取数据遵从后进先出的原则，队列中则是先进先出。* 16、栈结构中，允*17、在有n个

7、元素的栈中，进栈和退栈操作的复杂度为O(1)和O(1)*18、设长度为n的链队列用单循环链表示，若只设头指针，则入队和出队操作的时间复杂度分别为O(n)和 O(1)；若只设尾指针，则O(1) 和O(1)。* 19、通常在程序中使用串可*17、在有n个元素的栈中，进栈和退栈操作的复杂度为O(1)和O(1)*18、设长度为n的链队列用单循环链表示，若只设头指针，则入队和出队操作的时间复杂度分别为O(n)和 O(1)；若只设尾指针，则O(1) 和O(1)。* 19、通常在程序中使用串可分为串变量和串常量；而串式串。 20* 21、成功匹配的起始位置称为有效位移， 所有匹配不成功称为无效位移；Naiv

8、estrMatch返回的是第1个有效位移*22、串的朴素匹配算法 的情况下需要比较字符的总次数为(n-m+1)m,n为主串长* 23、 对于数组 Anm， 其元素aij按行优先与列优先的地址之差为(i-1)(n-1)-(j-1)(m-1).(两的LOC(a11)相同*24、特殊矩阵是指非零或零元素分布有一定规律的矩阵。 25数组方式顺序和链式。 26* 27、任何一个非空广义表的表头是表中第一个元素，它可以是原子*28、表的长度是指广义表元素的个数，表的深度是指广义表展开后扩号的层数。 29树中结点的最大层次称为树的深度（高度*30、若有一棵二叉排序树，则按照中序遍历顺序将产生一个有序序列。

9、31结构，遍历图有深度优先（DFT）和广度优先（BFT）等方法*34、有向图G，其第i行的所有和等于顶点i的出度。 35果n个顶点的图是一个环，则它有n个生成树O(n2（O(n+e)* 38、图的逆邻接39、已知一个图的邻接矩阵表示，删所有从第i个顶点出发的边的方法是将邻接矩阵的第i行全置0* 40n个顶点e条边的图用邻接矩（邻接（O(n+e)*41、图的BFS生成树的树高比DFSO(n2)（O(elog2e)*43、稀疏（稠密）图G的最小生成树，最好用Kruskal（Prim*41、图的BFS生成树的树高比DFSO(n2)（O(elog2e)*43、稀疏（稠密）图G的最小生成树，最好用Kru

10、skal（Prim）* 45、用Dijkstra算法求某一顶点到其余各顶点间最短路径是按路径长度递增的次序* 46、拓扑排序算法是通过重复选择具有0个前趋顶点的过程来完成的。 47*48、对n个顶点e条边的图进行拓扑排序，算法的时间复杂度为O(n+e)*49*50* 51、在堆、快速和归并排序中，只考* 52、大多数排序算法都有两个基本操作：比较两上关键字的大小和改变指*53、散列地址。 54* 57、m阶B-树具有k个子树的非叶子结点含有k1个关键字。 58、m阶B-*59、中序遍历二叉树排序树的结点就可以得到排好序的结点序列。 60。在B树地*62、在各种查找方法中，平均查找长度与结点个数

11、n*64中，装填因子*65、假设在有序线生表a20上进行二分查找，则比较一次查找的结点数为1*62、在各种查找方法中，平均查找长度与结点个数n*64中，装填因子*65、假设在有序线生表a20上进行二分查找，则比较一次查找的结点数为1；比较两*66的数据项，称为主关键字，否则称为次关键字。 67*68、文件有四种常用的组织：顺序、索引、散列和多关键字文件。 *70、衡量文件操作质量的重要标志是检索功能的多少和速度的快慢。 71* 72、在索引非顺序文件中采用动态索引时，为减* 73、在索引文件中，评价外存索引表的查找性能*74、常用的索引顺序文件有ISAM（索引顺序存取法）和VSAM（存取方法*

12、 75、ISAM*76、VSAM是一种索引顺序文件的组织方式，采用B+*77* 78、在双链表中*79、对于一棵满二叉树，若有m个叶子，则结点数为2m-1；若满二叉树的结点数为n，* 80、森林的后序遍历序列正是相应二叉树的中序遍历序列，森林的先序遍历序列正是*点若81、在一棵具有n个结点的完全二叉树中，从树根起，自上而下、自左至右地给所有为1*点若81、在一棵具有n个结点的完全二叉树中，从树根起，自上而下、自左至右地给所有为1。为i的结点，有左孩子，那么其右孩子为为i的结点，有父结点，那么其父结为i/2* 82、采用折半查找法进行查找的数据文件应为有序表和顺结构。 83* 84、在有n个结点

13、的二叉链表中，空指针域有n+1*85*86、在含胡n个结点的二叉排序树上查找某结点时，其平均查找长度ASL的范围估计是*87密度为1，而链表密度小于*88、在上三角矩阵中，它的下三角（不包括对角线）中的元素均为常数C中的重复元素C可个空间，其余的元素正好有n(n+1)/2个*1 *2*答：顺*3*4、简述算法复杂度（效率分析）* * 空间，也是总是规模*3*4、简述算法复杂度（效率分析）* * 空间，也是总是规模n的函数，同样用渐近空间复*5* *6 （ *7 其另一端的头指针是rearnextnext(表结点)。这将给操作带来很多方便*8*9、在顺序栈中简述进栈、退栈操作的过程*指针先加*9

14、、在顺序栈中简述进栈、退栈操作的过程*指针先加1，再送值到栈顶指针指向处。退栈时，先从栈顶指针指向处取值，栈顶指针再*10、在队列中简述入队、出队操作的过程（用“少和一个元素空间”的方法 * 在队列不空时，可执行出队操作，此时先从队头指针指向处取值，队头指针再加1（取模*11*队列结构主要应用在需要“排除”的事件中，例如OS*12*13 *的相对次序（特别是相同排序码的元素）*14*第i*89.排序前每一个位置上的排序码43现在位于第5个位置上* 15、在快速排序算法中，能否用队列代替栈来保存子文件首* 的地址（下标的地址（下标* 这才能地该子文件进行快速排序（排序过程又可能出现新的子文件*1

15、6、设有5000个无序的元素，希望用最快速度挑选出其中前10排序、堆排序、归并排序、基数排序和 素，然后对堆进行调整，保证堆顶的元素总是余下元素中最大的（或最小*根据题意，只要选取前10* 17、将十进制的关键字用二进制表示，对基数排序所需的计算时间和附设空间分别有* 答：因为基数排序所需的计算时间不仅与文件的大小n*把n分放到各个人列中并重新收集起来所需的时间为O(n)，因此一遍排序所需时间复杂度为O(n+r)*若每个关键字有d位，则总共要d遍排序，所以基数排序的时间复杂度为O(d(n+r)。由于关键字的位数d直接与基数r以及最大关键字的值有关因此不同的r和关键字将需要* 18、有n个不同的

16、英文单词，它们的长度相等，均为m，若n50，m5，试问什么排 * 19、试述顺序查找法 * 19、试述顺序查找法、折半查找法和分块查找法对被查找的表中元素的要求，并求其*答：顺序查找法：表中元素可以任意存放。查找成功的平均查找长度为 * 20的地址空间的长度为1000，如果散列函数只是简单地抽取键字中间的3位作为散列函数* 21、假定有n个关键字，它们具有相同的散列函数值，用线性探测方法把这n* 答：由于线性探测的查找次数主要取决于装填因子* 则在此情况下连续装入n个具有相同的散列函数值的关键字所需的总探测次数为n=n(n+1)/2* 22、已知一个含有100表设计方案，要求它在等概率情况下查找成功的平均查找长度不超过*小，表中数越小或表越长* 的可能性就越小，查找效率也越高；反之，的可能性就越大，查找时间也越长* 若采用二次探测再散列，这样在等概率情况下查找成功的平均查找长度为Sn-1/(1-)，根据题目要求有-1/(1-)3，即-的可能性就越大，查找时间也越长* 若采用二次探测再散列，这样在等概率情况下查找成功的平均查找长度为Sn-1/(1-)，根据题目要求有-1/(1-)3，即-(1-* 可求得0.8.因为0.8，表中含有1