数据结构题库.doc

1、精品文档判断题一. 绪论1、程序是用计算机语言表述的算法。（）2、算法一定要有输入和输出。（）3、算法分析的目的旨在分析算法的效率以求改进算法。（）4、数据的存储结构不仅有顺序存储结构和链式存储结构，还有索引结构与散列结构。（）5、程序就是算法，但算法不一定是程序。（）6、程序越短，程序运行的时间就越少。（）7.数据元素是数据的最小单位。( )8.数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。( )9.算法和程序原则上没有区别，在讨论数据结构时二者是通用的。( )10.数据的逻辑结构与数据元素本身的内容和形式无关。( )11.算法和程序都应具有下面一些特征：有输入，有输

2、出，确定性，有穷性，有效性。( )12.只有用面向对象的计算机语言才能描述数据结构算法。( )13. 插入与删除操作是数据结构中最基本的两种操作，因此这两种操作在数组中也经常被使用。( )14.在使用后缀表示实现计算器类时用到一个栈的实例,它的作用是暂存运算器对象。( )15.每种数据结构都应具备三种基本运算：插入、删除和搜索。( )16. 数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面。()1、2 、3、4、5、6 、7 、8 、9 、10 、11 、12 、 13、14、15 、 16 、。1 欢迎下载精品文档二线性表1、线性表的逻辑顺序与物理顺序总是一致

3、的。()2、线性表的顺序存储表示优于链式存储表示。()3、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。()4、二维数组是其数组元素为线性表的线性表。()5、假定有两个用单链有序表表示的集合，则这两个集合的交运算可得到一个新的集合单链表，其长度小于等于参加运算的任意一个集合单链表的长度。()6、假定有两个用单链有序表表示的集合，则这两个集合的差运算可得到一个新的集合单链表，其长度小于参加运算的任意一个集合单链表的长度。()7、线性表中的每个结点最多只有一个前驱和一个后继。（）8、线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。（）9、单链表从任何

4、一个结点出发，都能访问到所有结点（）10、线性表的顺序存储结构是通过数据元素的存储地址直接反映数据元素的逻辑关系。（）11、用一组地址连续的存储单元存放的元素一定构成线性表。（）12、非空线性表中任意一个数据元素都有且仅有一个直接后继元素。（）13、若频繁地对线性表进行插入和删除操作，该线性表采用顺序存储结构更合适。（）14、若线性表采用顺序存储结构，每个数据元素占用4 个存储单元，第12 个数据元素的存储地址为 15、则第 1 个数据元素的存储地址是101 。（）16、若长度为n 的线性表采用顺序存储结构，删除表的第i 个元素之前需要移动表中n-i+1个元素。（）17、符号 p-next出现

5、在表达式中表示p 所指的那个结点的内容。（）18、要将指针p 移到它所指的结点的下一个结点是执行语句p=p-next 。（）。2 欢迎下载精品文档19、线性链表中各个链结点之间的地址不一定要连续。（）20、线性表只能采用顺序存储结构或者链式存储结构。（）21、线性表的链式存储结构是通过指针来间接反映数据元素之间逻辑关系的。（）22、已知指针P 指向链表L 中的某结点，执行语句P=P- next 不会删除该链表中的结点。（）23、在非空线性链表中由p 所指的结点后面插入一个由q 所指的结点的过程是依次执行语句：q-next=p-next;p-next=q。（）24、非空双向循环链表中由q 所指的

6、结点后面插入一个由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. 线性表若采用链式存储表示, 在删除时不

7、需要移动元素。( )30. 在对双向循环链表做删除一个结点操作时， 应先将被删除结点的前驱结点和后继结点链接好再执行删除结点操作。 ( )1-5 6-10 11-15 16-20 21-25 。3 欢迎下载精品文档26-30 三栈和队列、栈和队列逻辑上都是线性表。（）、堆栈在数据中的存储原则是先进先出。（）3、队列在数据中的存储原则是后进先出。（）4、堆栈、队列和数组的逻辑结构都是线性表结构。（）5、若某堆栈的输入序列为1,2,3,4，则 4,3,1,2 不可能是堆栈的输出序列之一。（）6、不管堆栈采用何种存储结构，只要堆栈不空，可以任意删除一个元素。（）7、在链队列中，即使不设置尾指针也能进

8、行入队操作。（）8、采用循环链表作为存储结构的队列就是循环队列。（）9、堆栈是一种插入和删除操作在表的一端进行的线性表。（）10、队列是一种可以在表头和表尾都能进行插入和删除操作的线性表。（）11.每次从队列中取出的是具有最高优先权的元素, 这种队列就是优先级队列。()12.链式栈与顺序栈相比, 一个明显的优点是通常不会出现栈满的情况。( )13.在一个顺序存储的循环队列中, 队头指针指向队头元素的后一个位置。()14.栈和队列都是顺序存取的线性表,但它们对存取位置的限制不同。()15.在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。( )16. 若让元素 1,2,3

9、依次进栈，则出栈次序 1,3,2 是不可能出现的情况。 ( )?17.在用单链表表示的链式队列Q中，队头指针为Q-front，队尾指针为Q-rear ，则队空条件为 Q-front = Q-rear。 ()1-5 6-10 。4 欢迎下载精品文档11-15 16-17 递归18.递归定义的数据结构通常用递归算法来实现对它的操作。( )19.递归的算法简单、易懂、容易编写，而且执行效率也高。( )20.递归调用算法与相同功能的非递归算法相比，主要问题在于重复计算太多，而且调用本身需要分配额外的空间和传递数据和控制，所以时间与空间开销通常都比较大。（）21.递归方法和递推方法本质上是一回事，例如求

10、 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、除插入和删除操作外，数组的主要操作还有存取、修改、检

11、索和排序等。（）4、稀疏矩阵中0 元素的分布有规律，因此可以采用三元组方法进行压缩存储。（）。5 欢迎下载精品文档5. 如果采用如下方式定义一维字符数组：const int maxSize = 30;char amaxSize;则这种数组在程序执行过程中不能扩充。7. 数组是一种静态的存储空间分配，就是说，在程序设计时必须预先定义数组的数据类型和存储空间大小，由编译程序在编译时进行分配。8. 多维数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。9. 使用三元组表示稀疏矩阵中的非零元素能节省存储空间。10. 用字符数组存储长度为 n 的字符串，数组长度至少为n+1。1-5

12、6-10 11、一个广义表的深度是指该广义表展开后所含括号的层数。（）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

13、+1 。（）3、折半搜索只适用与有序表，包括有序的顺序表和有序的链表。（）。6 欢迎下载精品文档4、哈夫曼树一定是满二叉树。（）5、给定一组权值，可以唯一构造出一棵哈夫曼树。（）6、深度为h 的非空二叉树的第i 层最多有2i-1个结点。（）7、满二叉树也是完全二叉树。（）8、已知一棵二叉树的前序序列和后序序列可以唯一地构造出该二叉树。（）9、非空二叉排序树的任意一棵子树也是二叉排序树。（）10、对一棵二叉排序树进行前序遍历一定可以得到一个按值有序的序列。（）11、设与一棵树T 所对应的二叉树为BT，则与 T 中的叶子结点所对应的BT 中的结点也一定是叶子结点。（）12、哈夫曼树一定是完全二叉树

14、。（）13、由一棵二叉树的前序序列和后序序列可以唯一确定它。（）14、在完全二叉树中, 若某结点元左孩子, 则它必是叶结点。 （）15、树的带权路径长度最小的二叉树中必定没有度为1 的结点。（）16、二叉树可以用0度 2 的有序树来表示。 （）17、一组权值，可以唯一构造出一棵哈夫曼树。()18、将一棵树转换成二叉树后，根结点没有左子树；（）19、用树的前序遍历和中序遍历可以导出树的后序遍历；（）20. 二叉树是一棵无序树。 ( )21. 在一棵二叉树中， 假定每个结点只有左子女， 没有右子女， 对它分别进行前序遍历和后序遍历，则具有相同的结果。 ( )22. 在一棵二叉树中， 假定每个结点只

15、有左子女， 没有右子女， 对它分别进行中序遍历和后序遍历，则具有相同的结果。 ( )。7 欢迎下载精品文档23. 在一棵二叉树中， 假定每个结点只有左子女， 没有右子女， 对它分别进行前序遍历和中根遍历，则具有相同的结果。 ( )24. 在一棵二叉树中， 假定每个结点只有左子女， 没有右子女， 对它分别进行前序遍历和按层遍历，则具有相同的结果。 ( )25. 在树的存储中， 若使每个结点带有指向双亲结点的指针， 这为在算法中寻找双亲结点带来方便。( )26.对于一棵具有n 个结点，其高度为h 的二叉树，进行任一种次序遍历的时间复杂度为O(n) 。()27. 对于一棵具有 n 个结点， 其高度为

16、 h 的任何二叉树， 进行任一种次序遍历的时间复杂度均为O(h) 。 ()28. 对于一棵具有 n 个结点的任何二叉树， 进行前序、 中序或后序的任一种次序遍历的空间复杂度为 O(log 2 n) 。 ()29.在一棵具有n 个结点的线索二叉树中，每个结点的指针域可能指向子女结点，也可能作为线索，使之指向某一种遍历次序的前驱或后继结点，所有结点中作为线索使用的指针域共有n 个。()30. 线索二叉树中的每个结点通常包含有5 个数据成员。 ()31. 已知一棵树的前序遍历和后序遍历序列能唯一地确定这棵树。（）1-5 6-1011-15 16-2021-25 26-3031七图。8 欢迎下载精品文

17、档1、若图G 的最小生成树不唯一，则G 的边数一定多于n-1 ，并且权值最小的边有多条（其中n为 G 的顶点数）。（）2、带权连通图中某一顶点到图中另一定点的最短路径不一定唯一。（）3、在 n 个结点的无向图中, 若边数等于n-1, 则该图必是连通图。（）4、若一个有向图的邻接矩阵中, 对角线以下元素均为0, 则该图的拓扑有序序列必定存在。（）5、对于有向图，顶点的度分为入度和出度，入度是以该顶点为终点的入边数目；出度是以该顶点为起点的出边数目，该顶点的度等于其入度和出度之和。（）6、无向图的邻接矩阵是对称的有向图的邻接矩阵是不对称的。（）7、具有 n 个顶点的连通图的生成树具有n-1 条边（

18、）8. 用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。()9.邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。()10.邻接矩阵适用于稠密图（边数接近于顶点数的平方），邻接表适用于稀疏图（边数远小于顶点数的平方） 。 ( )11.存储无向图的邻接矩阵是对称的，因此可以只存储邻接矩阵的下（上）三角部分。( )12.强连通分量是有向图中的极大强连通子图。( )13.对任何用顶点表示活动的网络（AOV网）进行拓扑排序的结果都是唯一的。( )14.有回路的有向图不能完成拓扑排序。()15.在 AOE网络中一定只有一条

19、关键路径。( )16.用边表示活动的网络（ AOE网）的关键路径是指从源点到终点的路径长度最长的路径。( )17.对于 AOE网络，加速任一关键活动就能使整个工程提前完成。()18.对于 AOE网络，任一关键活动延迟将导致整个工程延迟完成。( )。9 欢迎下载精品文档19.在 AOE网络中， 可能同时存在几条关键路径，称所有关键路径都需通过的有向边为桥。如果加速这样的桥上的关键活动就能使整个工程提前完成。()20.对一个连通图进行一次深度优先搜索可以遍访图中的所有顶点。()21.图中各个顶点的编号是人为的，不是它本身固有的，因此可以根据需要进行改变。( )22. 如果无向图中每个顶点的度都大于

20、等于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、散列表的查找效率主要取决于所选择的散列函数与处理冲突

21、的方法。（）2、折半查找方法可以用于按值有序的线性链表的查找。（）3、哈希的查找无需进行关键字的比较。（）4、一个好的哈希函数应使函数值均匀的分布在存储空间的有效地址范围内，以尽可能减少冲突。（）5、在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不与表的个数有关，而与每一块中的元素个数有关。（）6. 在顺序表中进行顺序搜索时，若各元素的搜索概率不等，则各元素应按照搜索概率的降序排。10 欢迎下载精品文档列存放，则可得到最小的平均搜索长度。()7.进行折半搜索的表必须是顺序存储的有序表。( )8.能够在链接存储的有序表上进行折半搜索，其时间复杂度与在顺序存储的有序表上相同。( )

22、9.折半搜索所对应的判定树，既是一棵二叉搜索树，又是一棵理想平衡二叉树。( )10.对于同一组关键码互不相同的记录，若生成二叉搜索树时插入记录的次序不同则得到不同形态的二叉搜索树。( )11.对于同一组记录，生成二叉搜索树的形态与插入记录的次序无关。( )12.对于两棵具有相同记录集合而具有不同形态的二叉搜索树，按中序遍历得到的结点序列是相同的。()13.在二叉搜索树中，若各结点的搜索概率不等，使得搜索概率越大的结点离树根越近，则得到的是最优二叉搜索树。( )14.在二叉搜索树中，若各结点的搜索概率不等，使得搜索概率越小的结点离树根越近，则得到的是最优二叉搜索树。()15.装载因子是散列表的一

23、个重要参数，它反映了散列表的装满程度。()16. 在用散列表存储关键码集合时，可以用双散列法寻找下一个空位置。在设计再散列函数时，要求计算出的值与表的大小m 互质。 ( )17.一棵 3 阶 B 树是平衡的3 路搜索树，反之，一棵平衡的3 路搜索树是3 阶 B 树。 ( )18.闭散列法通常比开散列法时间效率更高。()?19.一棵 m 阶 B树中每个结点最多有m-1个关键码，最少有m/2 -1 个关键码。( )20. 在索引顺序结构上实施分块搜索，在等概率情况下，其平均搜索长度不仅与子表个数有关，而且与每一个子表中的对象个数有关。( )21. 在索引顺序结构的搜索中，对索引表既可以采取顺序搜索

24、，也可以采用折半搜索。( )。11 欢迎下载精品文档22.在散列法中采取开散列（链地址）法来解决冲突时,其装载因子的取值一定在(0,1)之间。( )23. AVL 树（平衡二叉搜索树）的所有叶结点不一定在同一层次上，同样，平衡m路搜索树的叶结点也不一定在同一层次上。( )？ 24. 在一棵 B- 树中，所有叶结点都处在同一层上，所有叶结点中空指针数等于所有关键码的总数加 1。( )？ 25. 向一棵 B- 树插入关键码的过程中，若最终引起树根结点的分裂，则新树比原树的高度减少1。( )26.从一棵 B- 树删除关键码的过程中，若最终引起树根结点的合并，则新树比原树的高度增加1。( )27. 折

25、半搜索只适用与有序表，包括有序的顺序表和有序的链表。（）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、在平均情况下，快速排序法最快，堆

26、积排序法最节省空间。（）。12 欢迎下载精品文档8、快速排序法是一种稳定性排序法。（）9、序列初始为逆序时，冒泡排序法所进行的元素之间的比较次数最多。（）10、给出不同的输入序列建造二叉排序树，一定得到不同的二叉排序树。（）11、由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间多。（）12、 101， 88， 46， 70， 34， 39， 45， 58， 66， 10）是堆；（）13、排序是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。（）14.当向一个最小堆插入一个具有最小值的元素时，该元素需要逐层

27、向上调整，直到被调整到堆顶位置为止。15.当从一个最小堆中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。16.对具有 n 个结点的堆进行插入一个元素运算的时间复杂度为O(n) 。17. 直接选择排序是一种稳定的排序方法。18. 若将一批杂乱无章的数据按堆结构组织起来, 则堆中数据必然按从小到大的顺序线性排列。19. 当输入序列已经基本有序时，起泡排序需要比较关键码的次数，比快速排序还要少。20.在任何情况下，快速排序需要进行关键码比较的次数都是O(nlog 2n) 。21.若用 m 个初始归并段参加 k 路平衡归并排序，则归并趟数应为log

28、 2m 。22. 堆排序是一种稳定的排序算法。23.任何基于排序码比较的算法，对 n 个数据对象进行排序时，最坏情况下的时间复杂度都不会大于 O(nlog 2n) 。1-5 。13 欢迎下载精品文档6-10 11-15 16-20 21-23 二、填空题：一绪论1、数据结构课程讨论的主要内容是数据的逻辑结构、存储结构和_运算 _ 。2、数据结构算法中，通常用时间复杂度和_ 空间复杂度 _ 两种方法衡量其效率。3、一个算法一该具有_有穷 _, 确定 _,_ 可行 _,_ 输入 _和 _输出 _ 这五种特性。4. 数据是 _信息 _ 的载体，它能够被计算机程序识别、存储和加工处理。5. 数据结构包

29、括逻辑结构、 _ 存储结构 _和数据的运算三个方面。6.数据结构的逻辑结构包括线性结构和_非线性 _ 结构两大类。7.数据结构的存储结构包括顺序、_链接 _、索引和散列等四种。8.基本数据类型是计算机已经实现了的_ 数据结构 _。9. 抽象数据类型的特点是 _数据封装 _ 、信息隐蔽、使用与实现分离。10. 算法的一个特性是 _有穷性 _，即算法必须执行有限步就结束。1. 运算2空间复杂度3有穷性确定性可行性输入输出4信息5存储结构6 非线性7.链接8.数据结构9.数据封装10.有穷性二线性表1、若频繁地对线性表进行插入与删除操作，该线性表应采用_链表 _ 存储结构。2、在非空线性表中除第一个

30、元素外，集合中每个数据元素只有一个_直接前驱 _；除最后一。14 欢迎下载精品文档个元素之外，集合中每个数据元素均只有一个_直接后继 _。3、线性表中的每个结点最多有_1 个直接 _前驱和 _ 一个直接 _ 后继。4、 _循环 _链表从任何一个结点出发，都能访问到所有结点。5、链式存储结构中的结点包含_数据 _ 域， _ 指针 _ 域。6、在双向链表中， 每个结点含有两个指针域，一个指向 _前驱 _结点，另一个指向 _后继 _结点。7 、 某 带 头 结 点 的 单 链 表 的 头 指针head ， 判 定 该 单 链 表 非 空 的 条 件_head-next!=NULL_。8、在双向链表中

31、，每个结点含有两个指针域，一个指向 _前驱 _结点，另一个指向_后继 _结点。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-nextp-next=s_。12、线性表的链式存储结构地址空间可以_不连续 _ ，而向量存储必须是地

32、址空间_连续 _。13.线性表是由n（ n 0）个 _数据元素 _组成的有限序列。15 欢迎下载精品文档14.链表是一种采用链式存储结构存储的线性表。15.在链表中进行插入和删除操作的效率比在顺序存储结构中进行相同操作的效率高。16.链表对于数据元素的插入和删除不需要移动结点，只需要改变相应结点的_ 指针 _的值。17.链接存储表示的结点存储空间一般在程序的运行过程中进行动态地分配_ 和释放。18.单链表中逻辑上相邻的结点而在物理位置上_不一定 _相邻。19.在单链表中 ,除了表头结点外,任意结点的存储位置由其直接_前驱 _结点的指针域的值所指示。20.在单链表设置表头结点的作用是插入和删除表

33、中第一个元素时不必对_表头指针 _ 进行特殊处理。21.若设 L 是指向带表头的单链表,语句 L-link=L-link-link的作用是 _删除 _单链表中的第一个结点。22. 在双向链表中 , 每个结点除了数据域外 , 还有两个指针域 , 它们分别指向 _ 前驱结点和后继结点 _ 。23. 线性表的链接存储只能通过_链接指针 _顺序访问。24.链表与顺序表、索引表、散列表等都是数据逻辑结构的_存储 _表示。25.设双向循环链表每个结点结构为(data,llink,rlink),则结点 *p的前驱结点的地址为_p-llink_。1、链表2、直接前驱， 直接后继3、1 个直接， 1 个直接4、

34、循环5、指针，数据6、前驱，后继7、 head-next!=Null8、前驱，后继重题9、删除 p 的后继结点10、后继11 、s-next=p-next;p-next=s12、不连续，连续13.数据元素14.。16 欢迎下载精品文档链式（或链接）15.删除16.指针域17.分配18.不一定19.前驱20.表头指针21.删除22. 前趋结点和后继结点23.链接指针24.存储25. p-llink三栈和队列1、栈结构允许进行删除操作的一端为_ 栈顶 _ 。2、在栈的顺序实现中，栈顶指针top ，栈为空条件 _top=-1_。3、对于单链表形式的队列，其空队列的F 指针和 R指针都等于_头结点的指

35、针_ 。?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)%

36、n_ 。8、已知循环队列的存储空间为数组data21，且头指针和尾指针分别为8 和 3，则该队列的当前长度 _17_ 。9.栈是一种限定在表的一端进行插入和删除的线性表，又被称为_ 先进后出 _ 表。10.队列是一种限定在表的一端插入，在另一端删除的线性表，它又被称为_ 先进先出 _表。11.向一个链式栈插入一个新结点时，首先把栈顶指针的值赋给新结点的指针域，然后把新结点。17 欢迎下载精品文档的存储位置赋给_ _ 。12. 队列的删除操作在 _ 进行。13. 向一个顺序栈插入一个元素时，首先使 _后移一个位置，然后把待插入元素写入到这个位置上。14.若 设 顺 序 栈 的 最 大 容 量 为

37、 MaxSize ， top=-1表示栈空，则判断栈满的条件是 _ 。15.当用长度为 MaxSize 的数组顺序存储一个栈时，若用top = MaxSize 表示栈空，则表示栈满的条件为 _top=0_ 。16.向一个循环队列中插入元素时，需要首先移动 _队尾 _ 指针，然后再向所指位置写入新元素。17.向一个栈顶指针为top 的链式栈中插入一个新结点*p 时，应执行_p-link=top _和top=p 操作。18.在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列至多有_1_ 个结点。19. 在一个链式队列中， 若队头指针与队尾指针的值相同， 则表示该队列至多有 _ 个结点。1

38、、栈顶2、 top=-13、头节点的指针4、 s0， sn-15、队列，队尾队头6、 Q-font=Q-rear7、 (R-F)%n8、 179.后出先进10. 先进先出11.栈顶指针12.队头（或队首）13.栈顶指针14. top=MaxSize-115. top = 016.队尾17.p-link=top18. 1 19.一20.如果一个对象部分地包含自己，或自己定义自己，则称这个对象是_递归 _的对象。21.如果一个过程直接或间接地调用自己，则称这个过程是一个_递归 _的过程。18 欢迎下载精品文档22. 递归工作栈起到两个作用，其一是将递归调用时的实际参数和返回地址传递给下一层递归；其

39、二是保存本层的形式参数和_局部变量 _ 。23.函数内部的局部变量是在进入函数过程后才分配存储空间，在函数过程执行结束后就_释放 _局部变量所占用的存储空间。24.迷宫问题是一个回溯控制的问题，最好使用_递归 _ 的方法来解决。20.递归21.递归22.局部变量23.释放24.递归四串1、一个串的任意个连续的字符组成的子序列称为该串的_子串 _，包含该子串的串称为_主串 _。2、求串 T 在主串S 中首次出现的位置的操作是_Index(S,T,pos)_。3、在初始为空的队列中插入元素A,B,C,D 以后，紧接着作了两次删除操作，此时的队尾元素是_D_。4、在长度为n 的循环队列中，删除其节点

40、为x 的时间复杂度为_ O(n) _ 。5、已知广义表L 为空，其深度为_1_ 。6.若设串 S =“ documentHash.doc0” ，则该字符串S 的长度为 _16_ 。1 、子串，主串2 、 Index(S,T,pos) 3、 D4 、 O(n)5、 16. 16五数组和广义表1、已知一顺序存储的线性表，每个结点占用k 个单元，若第一个结点的地址为DA1，则第i个结点的地址为_DA1+(i-1)*k_。2、设一行优先顺序存储的数组A56， A00的地址为1100，且每个元素占2 个存储单元，则 A23的地址为 _1130_ 。19 欢迎下载精品文档3、设有二维数组A919，其每个元素占两个字节，第