数据结构题库.doc

_判断题一.绪论1、程序是用计算机语言表述的算法。（ ）2、算法一定要有输入和输出。（ ）3、算法分析的目的旨在分析算法的效率以求改进算法。（ ）4、数据的存储结构不仅有顺序存储结构和链式存储结构，还有索引结构与散列结构。（ ）5、程序就是算法，但算法不一定是程序。（ ）6、程序越短，程序运行的时间就越少。（ ）7. 数据元素是数据的最小单位。( )8. 数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。( )9. 算法和程序原则上没有区别，在讨论数据结构时二者是通用的。( )10. 数据的逻辑结构与数据元素本身的内容和形式无关。( )11. 算法和程序都应具有下面一些特征：有输入，有输出，确定性，有穷性，有效性。( )12. 只有用面向对象的计算机语言才能描述数据结构算法。( )13. 插入与删除操作是数据结构中最基本的两种操作，因此这两种操作在数组中也经常被使用。( )14. 在使用后缀表示实现计算器类时用到一个栈的实例, 它的作用是暂存运算器对象。( )15. 每种数据结构都应具备三种基本运算：插入、删除和搜索。( )16. 数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面。( )1、 2、 3、 4、 5、 6、 7、 8、 9、 10、 11、 12、 13、 14、 15、 16、二线性表1、线性表的逻辑顺序与物理顺序总是一致的。( )2、线性表的顺序存储表示优于链式存储表示。( )3、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。( )4、二维数组是其数组元素为线性表的线性表。( )5、假定有两个用单链有序表表示的集合，则这两个集合的交运算可得到一个新的集合单链表，其长度小于等于参加运算的任意一个集合单链表的长度。( )6、假定有两个用单链有序表表示的集合，则这两个集合的差运算可得到一个新的集合单链表，其长度小于参加运算的任意一个集合单链表的长度。( )7、线性表中的每个结点最多只有一个前驱和一个后继。（ ）8、线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。（ ）9、单链表从任何一个结点出发，都能访问到所有结点 （ ）10、线性表的顺序存储结构是通过数据元素的存储地址直接反映数据元素的逻辑关系。（ ）11、用一组地址连续的存储单元存放的元素一定构成线性表。（ ）12、非空线性表中任意一个数据元素都有且仅有一个直接后继元素。（ ）13、若频繁地对线性表进行插入和删除操作，该线性表采用顺序存储结构更合适。（ ）14、若线性表采用顺序存储结构，每个数据元素占用4个存储单元，第12个数据元素的存储地址为15、则第1个数据元素的存储地址是101。（ ）16、若长度为n的线性表采用顺序存储结构，删除表的第i个元素之前需要移动表中n-i+1个元素。（ ）17、符号p-next出现在表达式中表示p所指的那个结点的内容。（ ）18、要将指针p移到它所指的结点的下一个结点是执行语句p=p-next。（ ）19、线性链表中各个链结点之间的地址不一定要连续。（ ）20、线性表只能采用顺序存储结构或者链式存储结构。（ ）21、线性表的链式存储结构是通过指针来间接反映数据元素之间逻辑关系的。（ ）22、已知指针P指向链表L中的某结点，执行语句P=P-next不会删除该链表中的结点。（ ）23、在非空线性链表中由p所指的结点后面插入一个由q所指的结点的过程是依次执行语句：q-next=p-next;p-next=q。（ ）24、非空双向循环链表中由q所指的结点后面插入一个由p指的结点的动作依次为：p-prior=q, p-next=q-next,q-next=p,q-prior-next=p。（ ）25、删除非空链式存储结构的堆栈(设栈顶指针为top)的一个元素的过程是依次执行:p=top,top= p-next,free (p)。( )26. 在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻。( )27. 顺序表和一维数组一样，都可以按下标随机（或直接）访问。( )28. 线性表若采用链式存储表示时，其存储结点的地址可连续也可不连续。( )29. 线性表若采用链式存储表示, 在删除时不需要移动元素。( )30. 在对双向循环链表做删除一个结点操作时，应先将被删除结点的前驱结点和后继结点链接好再执行删除结点操作。( )1-5 6-1011-1516-2021-2526-30三栈和队列、栈和队列逻辑上都是线性表。（ ） 、堆栈在数据中的存储原则是先进先出。（ ）3、队列在数据中的存储原则是后进先出。（ ）4、堆栈、队列和数组的逻辑结构都是线性表结构。（ ）5、若某堆栈的输入序列为1,2,3,4，则4,3,1,2不可能是堆栈的输出序列之一。（ ）6、不管堆栈采用何种存储结构，只要堆栈不空，可以任意删除一个元素。（ ）7、在链队列中，即使不设置尾指针也能进行入队操作。（ ）8、采用循环链表作为存储结构的队列就是循环队列。（ ）9、堆栈是一种插入和删除操作在表的一端进行的线性表。（ ）10、队列是一种可以在表头和表尾都能进行插入和删除操作的线性表。（ ）11. 每次从队列中取出的是具有最高优先权的元素, 这种队列就是优先级队列。( )12. 链式栈与顺序栈相比, 一个明显的优点是通常不会出现栈满的情况。( )13. 在一个顺序存储的循环队列中, 队头指针指向队头元素的后一个位置。( )14. 栈和队列都是顺序存取的线性表, 但它们对存取位置的限制不同。( )15. 在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。( )16. 若让元素1,2,3依次进栈，则出栈次序1,3,2是不可能出现的情况。( )?17. 在用单链表表示的链式队列Q中，队头指针为Q-front，队尾指针为Q-rear，则队空条件为Q-front = Q-rear。( )1-56-1011-1516-17递归 18. 递归定义的数据结构通常用递归算法来实现对它的操作。( )19. 递归的算法简单、易懂、容易编写，而且执行效率也高。( )20. 递归调用算法与相同功能的非递归算法相比，主要问题在于重复计算太多，而且调用本身需要分配额外的空间和传递数据和控制，所以时间与空间开销通常都比较大。（ ）21. 递归方法和递推方法本质上是一回事，例如求n! 时既可用递推的方法，也可用递归的方法。( )22. 将f = 1 + 1/2 + 1/3+ + 1/n转化为递归函数时，递归部分为f (n) = f (n-1) + 1/n，递归结束条件为f (1) = 1。（ ） 18、 19、 20、 21、X 22、四串1、确定串在串中首次出现的位置的操作称为串的模式匹配。（ ）2、如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。（ ）3、一个任意串是其自身的子串。（ ）1、 2、 3、五数组和广义表1、多维数组是向量的推广。（ ）2、用相邻矩阵表示图所用的存储空间大小与图的边数成正比。（ 3、除插入和删除操作外，数组的主要操作还有存取、修改、检索和排序等。（ ）4、稀疏矩阵中0元素的分布有规律，因此可以采用三元组方法进行压缩存储。（ ）5. 如果采用如下方式定义一维字符数组： const int maxSize = 30; char amaxSize; 则这种数组在程序执行过程中不能扩充。7. 数组是一种静态的存储空间分配，就是说，在程序设计时必须预先定义数组的数据类型和存储空间大小，由编译程序在编译时进行分配。 8. 多维数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。9. 使用三元组表示稀疏矩阵中的非零元素能节省存储空间。10. 用字符数组存储长度为n的字符串，数组长度至少为n+1。1-56-1011、一个广义表的深度是指该广义表展开后所含括号的层数。（）12. 一个广义表的表头总是一个广义表。( )13. 一个广义表的表尾总是一个表。( )14. 一个广义表 ( (a), ( (b), c), ( ( (d) ) ) ) 的长度为3，深度为4。( )15. 一个广义表 ( (a), ( (b), c), ( ( (d) ) ) ) 的表尾是（ ( (b), c), ( ( (d) ) )）。( 129 )11、 12、 13、 14、 15、六树1、一般树和二叉树的结点数目都可以为0。 （ ）2、在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。（ ）3、折半搜索只适用与有序表，包括有序的顺序表和有序的链表。（ ）4、哈夫曼树一定是满二叉树。（ ）5、给定一组权值，可以唯一构造出一棵哈夫曼树。（ ）6、深度为h的非空二叉树的第i层最多有2i-1 个结点。（ ）7、满二叉树也是完全二叉树。（ ）8、已知一棵二叉树的前序序列和后序序列可以唯一地构造出该二叉树。（ ）9、非空二叉排序树的任意一棵子树也是二叉排序树。（ ）10、对一棵二叉排序树进行前序遍历一定可以得到一个按值有序的序列。（ ）11、设与一棵树T所对应的二叉树为BT，则与T中的叶子结点所对应的BT中的结点也一定是叶子结点。（ ）12、哈夫曼树一定是完全二叉树。（ ）13、由一棵二叉树的前序序列和后序序列可以唯一确定它。（ ）14、在完全二叉树中,若某结点元左孩子,则它必是叶结点。（ ）15、树的带权路径长度最小的二叉树中必定没有度为1的结点。（ ）16、二叉树可以用0度2的有序树来表示。（ ）17、一组权值，可以唯一构造出一棵哈夫曼树。( ) 18、将一棵树转换成二叉树后，根结点没有左子树；（ ）19、用树的前序遍历和中序遍历可以导出树的后序遍历；（ ）20. 二叉树是一棵无序树。( )21. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和后序遍历，则具有相同的结果。( )22. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的结果。( )23. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和中根遍历，则具有相同的结果。( )24. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和按层遍历，则具有相同的结果。( )25. 在树的存储中，若使每个结点带有指向双亲结点的指针，这为在算法中寻找双亲结点带来方便。( )26. 对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O(n)。( )27. 对于一棵具有n个结点，其高度为h的任何二叉树，进行任一种次序遍历的时间复杂度均为O(h)。( )28. 对于一棵具有n个结点的任何二叉树，进行前序、中序或后序的任一种次序遍历的空间复杂度为O(log2n)。( )29. 在一棵具有n个结点的线索二叉树中，每个结点的指针域可能指向子女结点，也可能作为线索，使之指向某一种遍历次序的前驱或后继结点，所有结点中作为线索使用的指针域共有n个。( )30. 线索二叉树中的每个结点通常包含有5个数据成员。( )31.已知一棵树的前序遍历和后序遍历序列能唯一地确定这棵树。（ ）1-5 6-1011-15 16-2021-25 26-3031七图 1、若图G的最小生成树不唯一，则G的边数一定多于n-1，并且权值最小的边有多条（其中n为G的顶点数）。（）2、带权连通图中某一顶点到图中另一定点的最短路径不一定唯一。（ ）3、在n个结点的无向图中,若边数等于n-1,则该图必是连通图。（ ）4、若一个有向图的邻接矩阵中,对角线以下元素均为0,则该图的拓扑有序序列必定存在。（）5、对于有向图，顶点的度分为入度和出度，入度是以该顶点为终点的入边数目；出度是以该顶点为起点的出边数目，该顶点的度等于其入度和出度之和。（ ）6、无向图的邻接矩阵是对称的有向图的邻接矩阵是不对称的。（ ）7、具有n个顶点的连通图的生成树具有n-1条边（）8.用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。( )9. 邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。( )10. 邻接矩阵适用于稠密图（边数接近于顶点数的平方），邻接表适用于稀疏图（边数远小于顶点数的平方）。( )11. 存储无向图的邻接矩阵是对称的，因此可以只存储邻接矩阵的下（上）三角部分。( )12. 强连通分量是有向图中的极大强连通子图。( )13. 对任何用顶点表示活动的网络（AOV网）进行拓扑排序的结果都是唯一的。( )14. 有回路的有向图不能完成拓扑排序。( )15. 在AOE网络中一定只有一条关键路径。( )16. 用边表示活动的网络（AOE网）的关键路径是指从源点到终点的路径长度最长的路径。( )17. 对于AOE网络，加速任一关键活动就能使整个工程提前完成。()18. 对于AOE网络，任一关键活动延迟将导致整个工程延迟完成。( )19. 在AOE网络中，可能同时存在几条关键路径，称所有关键路径都需通过的有向边为桥。如果加速这样的桥上的关键活动就能使整个工程提前完成。( )20. 对一个连通图进行一次深度优先搜索可以遍访图中的所有顶点。( )21. 图中各个顶点的编号是人为的，不是它本身固有的，因此可以根据需要进行改变。( )22. 如果无向图中每个顶点的度都大于等于2，则该图中必有回路。( )23. 如果有向图中各个顶点的度都大于2，则该图中必有回路。()24. 图的深度优先搜索是一种典型的回溯搜索的例子，可以通过递归算法求解。( )25. 图的广度优先搜索算法通常采用非递归算法求解。( )26. 对一个有向图进行拓扑排序，一定可以将图的所有顶点按其关键码大小排列到一个拓扑有序的序列中。( )1、 2、 3、 4、5、6、 7、 8、 9、 10、 11、 12、 13、 14、15、 16、17、 18、 19、20、 21、 22、 23、 24、 25、 26、 八查找 1、散列表的查找效率主要取决于所选择的散列函数与处理冲突的方法。（ ）2、折半查找方法可以用于按值有序的线性链表的查找。（ ）3、哈希的查找无需进行关键字的比较。（）4、一个好的哈希函数应使函数值均匀的分布在存储空间的有效地址范围内，以尽可能减少冲突。（ ）5、在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不与表的个数有关，而与每一块中的元素个数有关。（ ）6. 在顺序表中进行顺序搜索时，若各元素的搜索概率不等，则各元素应按照搜索概率的降序排列存放，则可得到最小的平均搜索长度。( )7. 进行折半搜索的表必须是顺序存储的有序表。( )8. 能够在链接存储的有序表上进行折半搜索，其时间复杂度与在顺序存储的有序表上相同。( )9. 折半搜索所对应的判定树，既是一棵二叉搜索树，又是一棵理想平衡二叉树。( )10. 对于同一组关键码互不相同的记录，若生成二叉搜索树时插入记录的次序不同则得到不同形态的二叉搜索树。( )11. 对于同一组记录，生成二叉搜索树的形态与插入记录的次序无关。( )12. 对于两棵具有相同记录集合而具有不同形态的二叉搜索树，按中序遍历得到的结点序列是相同的。( )13. 在二叉搜索树中，若各结点的搜索概率不等，使得搜索概率越大的结点离树根越近，则得到的是最优二叉搜索树。( )14. 在二叉搜索树中，若各结点的搜索概率不等，使得搜索概率越小的结点离树根越近，则得到的是最优二叉搜索树。( )15. 装载因子是散列表的一个重要参数，它反映了散列表的装满程度。( )16. 在用散列表存储关键码集合时，可以用双散列法寻找下一个空位置。在设计再散列函数时，要求计算出的值与表的大小m 互质。( )17. 一棵3 阶B树是平衡的3 路搜索树，反之，一棵平衡的3 路搜索树是3 阶B树。( )18. 闭散列法通常比开散列法时间效率更高。( )?19. 一棵 m 阶 B 树中每个结点最多有 m-1 个关键码，最少有 m/2-1个关键码。( )20. 在索引顺序结构上实施分块搜索，在等概率情况下，其平均搜索长度不仅与子表个数有关，而且与每一个子表中的对象个数有关。( )21. 在索引顺序结构的搜索中，对索引表既可以采取顺序搜索，也可以采用折半搜索。( )22. 在散列法中采取开散列（链地址）法来解决冲突时, 其装载因子的取值一定在(0,1)之间。( )23. AVL树（平衡二叉搜索树）的所有叶结点不一定在同一层次上，同样，平衡m路搜索树的叶结点也不一定在同一层次上。( )？24. 在一棵B-树中，所有叶结点都处在同一层上，所有叶结点中空指针数等于所有关键码的总数加1。( )？25. 向一棵B-树插入关键码的过程中，若最终引起树根结点的分裂，则新树比原树的高度减少1。( )26. 从一棵B-树删除关键码的过程中，若最终引起树根结点的合并，则新树比原树的高度增加1。( )27.折半搜索只适用与有序表，包括有序的顺序表和有序的链表。（ ）1、 2、 3、 4、 5、 6、 7、 8、 9、 10、 11、 12、 13、 14、 15、 16、 17、 18、 19、 20、 21、 22、 23、 24、 25、 26、 27、九排序 1、删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。（ ）2、快速排序是排序算法中最快的一种。（ ）3、直接选择排序是一种不稳定的排序方法。（ ）4、对一个堆按层次遍历，不一定能得到一个有序序列。（ ）5、只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。（ ）6、希尔排序在效率上较直接插入排序有较大的改进。但是不稳定的。（ ）7、在平均情况下，快速排序法最快，堆积排序法最节省空间。（ ）8、快速排序法是一种稳定性排序法。（ ）9、序列初始为逆序时，冒泡排序法所进行的元素之间的比较次数最多。（ ）10、给出不同的输入序列建造二叉排序树，一定得到不同的二叉排序树。（ ）11、由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间多。（ ）12、101，88，46，70，34，39，45，58，66，10）是堆；（ ）13、排序是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。（ ）14. 当向一个最小堆插入一个具有最小值的元素时，该元素需要逐层向上调整，直到被调整到堆顶位置为止。15. 当从一个最小堆中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。16. 对具有n个结点的堆进行插入一个元素运算的时间复杂度为O(n)。17. 直接选择排序是一种稳定的排序方法。18. 若将一批杂乱无章的数据按堆结构组织起来, 则堆中数据必然按从小到大的顺序线性排列。19. 当输入序列已经基本有序时，起泡排序需要比较关键码的次数，比快速排序还要少。20. 在任何情况下，快速排序需要进行关键码比较的次数都是O(nlog2n)。21. 若用m 个初始归并段参加 k 路平衡归并排序，则归并趟数应为log2m。22. 堆排序是一种稳定的排序算法。23. 任何基于排序码比较的算法，对n个数据对象进行排序时，最坏情况下的时间复杂度都不会大于O(nlog2n)。1-56-1011-1516-2021-23二、填空题：一绪论1、数据结构课程讨论的主要内容是数据的逻辑结构、存储结构和_运算_。2、数据结构算法中，通常用时间复杂度和_空间复杂度_两种方法衡量其效率。3、一个算法一该具有_有穷_,确定_,_可行_,_输入_和_输出_这五种特性。4. 数据是_信息_的载体，它能够被计算机程序识别、存储和加工处理。5. 数据结构包括逻辑结构、_存储结构_和数据的运算三个方面。6. 数据结构的逻辑结构包括线性结构和_非线性_结构两大类。7. 数据结构的存储结构包括顺序、_链接_、索引和散列等四种。8. 基本数据类型是计算机已经实现了的_数据结构_。9. 抽象数据类型的特点是_数据封装_、信息隐蔽、使用与实现分离。10. 算法的一个特性是_有穷性_，即算法必须执行有限步就结束。1.运算 2 空间复杂度 3 有穷性 确定性 可行性 输入 输出 4 信息 5 存储结构 6 非线性7. 链接 8. 数据结构 9. 数据封装 10. 有穷性 二线性表1、若频繁地对线性表进行插入与删除操作，该线性表应采用_链表_存储结构。2、在非空线性表中除第一个元素外，集合中每个数据元素只有一个_直接前驱_；除最后一个元素之外，集合中每个数据元素均只有一个_直接后继_。3、线性表中的每个结点最多有_1个直接_前驱和_一个直接_后继。4、_循环_链表从任何一个结点出发，都能访问到所有结点。5、链式存储结构中的结点包含_数据_域，_指针_域。6、在双向链表中，每个结点含有两个指针域，一个指向_前驱_结点，另一个指向_后继_结点。7、某带头结点的单链表的头指针head，判定该单链表非空的条件_head-next!=NULL_。8、在双向链表中，每个结点含有两个指针域，一个指向_前驱_结点，另一个指向_后继_结点。9、已知指针p指向单链表中某个结点，则语句p-next=p-next-next的作用_删除p 的后继结点_。10、已知在结点个数大于1的单循环链表中，指针p指向某个结点，则下列程序段结束时，指针q指向*p的_前驱_结点。q=p;while(q-next!=p) q=q-next;11、若要在单链表结点*P后插入一结点*S，执行的语句_s-next=p-next p-next=s_。12、线性表的链式存储结构地址空间可以_不连续_，而向量存储必须是地址空间_连续_。13. 线性表是由n（n0）个_数据元素_组成的有限序列。14. 链表是一种采用 链式 存储结构存储的线性表。15. 在链表中进行插入和 删除 操作的效率比在顺序存储结构中进行相同操作的效率高。16. 链表对于数据元素的插入和删除不需要移动结点，只需要改变相应结点的_指针_的值。17. 链接存储表示的结点存储空间一般在程序的运行过程中进行动态地分配_和释放。18. 单链表中逻辑上相邻的结点而在物理位置上_不一定_相邻。19. 在单链表中, 除了表头结点外, 任意结点的存储位置由其直接_前驱_结点的指针域的值所指示。20. 在单链表设置表头结点的作用是插入和删除表中第一个元素时不必对_表头指针_进行特殊处理。21. 若设L是指向带表头的单链表, 语句 L-link=L-link-link的作用是_删除_单链表中的第一个结点。22. 在双向链表中, 每个结点除了数据域外, 还有两个指针域, 它们分别指向_前驱结点和后继结点_。23. 线性表的链接存储只能通过_链接指针_顺序访问。24. 链表与顺序表、索引表、散列表等都是数据逻辑结构的_存储_表示。25. 设双向循环链表每个结点结构为(data,llink,rlink),则结点*p的前驱结点的地址为_p-llink_。1、链表 2、直接前驱，直接后继 3、1个直接，1个直接 4、循环 5、指针，数据 6、前驱，后继 7、head-next!=Null 8、前驱，后继 重题 9、删除p 的后继结点 10、后继 11、s-next=p-next;p-next=s 12、不连续，连续 13. 数据元素 14. 链式（或链接） 15. 删除 16. 指针域 17. 分配 18. 不一定 19. 前驱 20. 表头指针 21. 删除22. 前趋结点和后继结点23. 链接指针 24. 存储 25. p-llink三栈和队列1、栈结构允许进行删除操作的一端为_栈顶_。2、在栈的顺序实现中，栈顶指针top，栈为空条件_top=-1_。3、对于单链表形式的队列，其空队列的F指针和R指针都等于_头结点的指针_。?4、若数组s0.n-1为两个栈s1和s2的共用存储空间，仅当s0.n-1全满时，各栈才不能进行栈操作，则为这两个栈分配空间的最佳方案是：s1和s2的栈顶指针的初值分别为_s0sn-1_。5、允许在线性表的一端插入,另一端进行删除操作的线性表称为_队列_。插入的一端为_队尾_,删除的一端为_队头_。6、设数组Am为循环队列Q的存储空间，font为头指针，rear为尾指针，判定Q为空队列的条件_Q-font=Q-rear_。7、对于顺序存储的队列，存储空间大小为n，头指针为F，尾指针为R。若在逻辑上看一个环，则队列中元素的个数为_(_R-F)%n_。8、已知循环队列的存储空间为数组data21，且头指针和尾指针分别为8和3，则该队列的当前长度_17_。9. 栈是一种限定在表的一端进行插入和删除的线性表，又被称为_先进后出_表。10. 队列是一种限定在表的一端插入，在另一端删除的线性表，它又被称为_先进先出_表。11. 向一个链式栈插入一个新结点时，首先把栈顶指针的值赋给新结点的指针域，然后把新结点的存储位置赋给_ _。12. 队列的删除操作在_进行。13. 向一个顺序栈插入一个元素时，首先使_后移一个位置，然后把待插入元素写入到这个位置上。14. 若设顺序栈的最大容量为MaxSize，top=-1表示栈空，则判断栈满的条件是_ _。15. 当用长度为MaxSize的数组顺序存储一个栈时，若用top = MaxSize表示栈空，则表示栈满的条件为_top=0_。16. 向一个循环队列中插入元素时，需要首先移动_队尾_指针，然后再向所指位置写入新元素。17. 向一个栈顶指针为top的链式栈中插入一个新结点*p时，应执行_p-link=top _和top=p操作。18. 在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列至多有_1_个结点。19. 在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列至多有_个结点。1、栈顶2、 top=-1 3、 头节点的指针 4、s0，sn-1 5、队列，队尾队头6、Q-font=Q-rear 7、(R-F)%n 8、17 9. 后出先进 10. 先进先出 11. 栈顶指针 12. 队头（或队首）13. 栈顶指针 14. top=MaxSize-1 15. top = 0 16. 队尾17. p-link=top 18. 1 19. 一20. 如果一个对象部分地包含自己，或自己定义自己，则称这个对象是_递归_的对象。21. 如果一个过程直接或间接地调用自己，则称这个过程是一个_递归_的过程。22. 递归工作栈起到两个作用，其一是将递归调用时的实际参数和返回地址传递给下一层递归；其二是保存本层的形式参数和_局部变量_。23. 函数内部的局部变量是在进入函数过程后才分配存储空间，在函数过程执行结束后就_释放_局部变量所占用的存储空间。24. 迷宫问题是一个回溯控制的问题，最好使用_递归_的方法来解决。20. 递归 21. 递归 22.局部变量 23. 释放 24. 递归四串1、一个串的任意个连续的字符组成的子序列称为该串的_子串_，包含该子串的串称为_主串_。2、求串T在主串S中首次出现的位置的操作是_Index(S,T,pos)_。3、在初始为空的队列中插入元素A,B,C,D以后，紧接着作了两次删除操作，此时的队尾元素是_D_。4、在长度为n的循环队列中，删除其节点为x的时间复杂度为_ O(n)_。5、已知广义表L为空，其深度为_1_。6. 若设串S = “documentHash.doc0”，则该字符串S的长度为_16_。 1、子串，主串 2、Index(S,T,pos) 3、D 4、O(n) 5、1 6. 16 五数组和广义表1、已知一顺序存储的线性表，每个结点占用k个单元，若第一个结点的地址为DA1，则第i个结点的地址为_DA1+(i-1)*k_。2、设一行优先顺序存储的数组A56，A00的地址为1100，且每个元素占2个存储单元，则A23的地址为_1130_。3、设有二维数组A919，其每个元素占两个字节，第一个元素的存储地址为100，若按行优先顺序存储，则元素A6,6的存储地址为_340_，按列优顺序存储，元素A6,6的存储地址为_220_。/*100+(6*9+6)*2*/4、假设以行为优先存储的三维数组A567，A000的地址为1100，每个元素占两个存储单元，则A432的地址为_1482_。/*1100+(4*6+3)*7+2*2*/4、设二维数组Amn按列优先存储，每个元素占1个存储单元，元素A00的存储地址loc(A00)，则Aij的存储地址loc(Aij)=_loc(A00)+j*_m+i_。6、稀疏矩阵一般采用_三元组_方法进行压缩存储。7、稀疏矩阵可用_三元组_进行压缩存储，存储时需存储非零元的_行号_、_列号_、_值_。8、若矩阵中所有非零元素都集中在以主对角线为中心的带状区域中，区域外的值全为0，则称为_三对角矩阵_。9、若一个n 阶矩阵A中的元素满足：Aij=Aji (0=I ,j=j)_和_j*(j-1)/2+i-1(ij)_。11、设有一上三角形矩阵A55按行压缩存储到数组B中，B0的地址为100，每个元素占2个单元，则A32地址为_108_。/*3*(3-1)/2+2-1*2=8*/12. 一维数组所占用的空间是连续的。但数组元素不一定顺序存取，通常是按元素的_下标_存取的。13. 在程序运行过程中不能扩充的数组是_静态_分配的数组。这种数组在声明它时必须指定它的大小。14. 在程序运行过程中可以扩充的数组是_动态_分配的数组。这种数组在声明它时需要使用数组指针。？15. 二维数组是一种非线性结构，其中的每一个数组元素最多有_个直接前驱（或直接后继）。16. 若设一个nn的矩阵A的开始存储地址LOC(0, 0) 及元素所占存储单元数d已知，按行存储时其任意一个矩阵元素aij的存储地址为_ LOC(0, 0)+（i*n+ j ）d_。17. 对称矩阵的行数与列数_相等_且以主对角线为对称轴，aij = aji，因此只存储它的上三角部分或下三角部分即可。18. 将一个n阶对称矩阵的上三角部分或下三角部分压缩存放于一个一维数组中，则一维数组需要存储_n*(n+1)/2_个矩阵元素。19. 将一个n阶对称矩阵A的上三角部分按行压缩存放于一个一维数组B中，A00存放于B0中，则AIJ在IJ时将存放于数组B的_ _位置。20. 利用三元组表存放稀疏矩阵中的非零元素，则在三元组表中每个三元组元素对应一个非零元素的行号、列号和_值_。1、DA1+(i-1)*k 2、1100+（6*2+3）*2=1130 3、100+（19*6+6）*2=340，100+（9*6+）*2=220 4、14825、loc（a00）+(j*m+i)*1 6、三元组 7、三元组，行号，列号，值8、三对角矩阵9、上（下）三角矩阵 10、i*（i-1）/2+j-1 (ij) ，j*(j-1)/2+i-1 (ij) 11、10812. 下标（或顺序号）13. 静态 14. 动态 15. 两个 16.LOC(0,0)+(i*n+j)*d 17. 相等18. n(n+1)/2 19.2n-I-1)*I/2+J 20. 值 21、广义表（A,(a,b),d,e,(i,j),k)）,则广义表的长度为_5_，深度为_3_。22、已知广义表A=(a,b,c),(d,e,f),则运算head(head (tail（A）)=_ _ d _。23、已知广义表ls =(a,(b,c,d),e),运用head和tail函数取出ls中的原子b的运算是head(head(tail(s)_。24. 非空广义表的除第一个元素外其他元素组成的表称为广义表的_表尾_。25. 广义表A ( (a, b, c), (d, e, f ) ) 的表尾为_25. ( (d, e, f ) ) _。26. 广义表是一种递归的数据结构，子表结点则指示下一层广义表的_表头结点_。27. 广义表的深度定义为广义表括号的_层数_。21、5，3 22、d 23、head(head(tail(s) 24. 表尾 25. ( (d, e, f ) ) 26. 表头结点 27. 层数 六树1、在树结构里，有且仅有一个结点没有前驱，称为根。非根结点有且仅有一个_前驱_,且存在一条从根到该结点的_路径_。2、度数为0的结点，即没有子树的结点叫作_叶子_结点或_终端_结点。同一个结点的儿子结点之间互称为_兄弟_结点。 3、假定一棵树的广义表为A(B(e),C(F(h,i,j),g),D),则该树的度为_3_，树的深度为_4_，终端结点为_ehijgD_，单分支结点为B，双分支结点个数为 _1_，三分支结点为_A_F_，C结点的双亲结点是_A_，孩子结点是_F,g_。4、完全二叉树、满二叉树、线索二叉树和二叉排序树这四个名词术语中，与数据的存储结构有关系的是_线索_。5、有三个结点的二叉树，最多有_5_种形状。6、高度为k的二叉树具有的结点数目，最少为_k_,最多为_2k-1_。/*高度？深度？*/7、对任何一棵二叉树，若n0，n1，n2分别是度为0，1，2的结点的个数，则n0=_ n2+1_。8、在含100个结点的完全二叉树，叶子结点的个数为_50_。9、将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列叫_排序_。10、若一棵满二叉树含有121个结点，则该树的深度为_7_。11、一个具有767个结点的完全二叉树，其叶子结点个数为_384_。12、深度为90的满二叉树，第11层有_1024_个结点。13、有100个结点的完全二叉树，深度为_7_。14、设一棵二叉树中度为2的结点10个，则该树的叶子个数为_11_。/*n0=n2+1*/?15、含有3个2度结点和4个叶结点的二叉树可含_个1度结点。16、一棵具有层满二叉树中节点总数为_31_。17、一棵含有16个结点的完全二叉树，对他按层编号，对于编号为7的结点，他的双亲结点及左右结点编号为_3_、_14_、_15_。18、深度为k(设根的层数为1)的完全二叉树至少有_个结点, 至多有_个结点。19、若要对某二叉排序树进行遍历，保证输出所有结点的值序列按增序排列，应对该二叉排序树采用_中序_遍历法。20、在序