数据结构试题5.doc

数据结构试题库中的习题一、填空1、线性表的顺序存储是用一组_ 连续的空间单元实现数据元素的存储。2、线性表的链式存储是用_ 语句实现空间单元动态分配。3、头结点地址指针为L的循环单链表，空表的判别标志是_ 。4、含有N 个结点的一棵完全二叉树上，叶子结点的最小编号是_ 。5、高度为K的一棵完全二叉树中，结点的总个数至少是_个；至多是 _个。6、图的遍历过程中，选择出发顶点V0的次数，为该图的_的个数。7、图的邻接表存储适用于_ ，_，_ 。8、拓扑排序的功能是检验AOV网络中是否存在。9、在拓扑排序过程中，若图中没有入度为零的结点，则此时_确定在该图中存在回路。10、关键路径的功能是计算_时间；找出 _ 顶点；提供_ 策略。11、图的遍历输出序列_唯一的。12、一个赋权图的最小代价生成树_唯一的。13、仅适用于有向图存储的存储方法是_法。14、义表的头元素可以是_元素，也可以是_元素；其尾元素只能是_ 元素。15、给出二叉树的先根序序列和中根序序列，便能_的确定这棵二叉树。16、先根序序列和中根序序列相同的二叉树是树中每个结点只有_孩子结点的二叉树。17、后根序序列和中根序序列相同的二叉树是树中每个结点只有_孩子结点的二叉树。18、先根序序列、中根序序列和后根序序列均相同的二叉树是_树或者是只有_个结点的二叉树.l19、判定一棵线索二叉树中未知结点P没有左孩子的标志_ 。20、线索二叉树是利用结点中空闲字段来记录_次序的二叉树。21、在一棵中序线索二叉树中已知结点P的左侧插入一个新结点Y后仍然是一棵中序线索二叉树的操作，主要是查找P的_前驱结点22、本书介绍的静态查找方法有 _，_，_ ；其中，_ 需要记录表是顺序存储且按关键字大小有序。23、二叉排序树中删除有左右孩子的结点P时，一般用P的_前驱或_ 后继来带替P的位置。24、含有N 个顶点E条边的无向图中，假设每个顶点和每条边都占用一个存储单元，采用邻接表存储方式，那么，共需要_ 单元。25、在一个图中，若两个顶点是邻接的，那么，这两个顶点之间至少存在_路径。路径长度为 _。26、在一个图中，若两个顶点间存在路径，则这两个顶点 _ 是相邻接。27、在对一个有向图进行拓扑排序结束后，发现输出顶点个数为0，那么，该图一定是一个 图。28、分块查找的索引表中的关键字是_有序的。所以，在索引表中确定给定值所在块时，可以用_查找方式。29、在构造二叉排序树时，若新结点插在左重结点左孩子的左分支上，则称为 _型。用_旋转的方法调整。30、哈希表查找，从原理上讲，查找时间只与被查记录的_有关，而与表的 _无关。31、影响哈希表查找时间的因素有_,_ 。32、哈希表查找的主要缺点是 _ ，解决的办法通常有下列四种其一，_ ；其二，_；其三，_；其四，_。33、在实际工作中选择小于1的目的是为了_冲突。 34、哈希表查找成功的平均查找长度是对所有记录查找成功时总的比较次数与 _的比值。35、哈希表查找不成功的平均查找长度是对所有记录查找不成功时总的比较次数与 _的比值。36、排序时，若待排序记录能一次全部调入内存进行排序的方式，一般称_ 排序。37、平均时间量级为O（）的排序方法有_，_，_。38、希尔排序是属于_ ，但它不是稳定排序。39、磁带文件只能是 _。40、顺序文件分为_文件_文件。它们分别对应于线性表的顺序存储和链式存储。41、一棵M叉的树中，结点的度最多有_种。42、一棵高度为N 的树中，结点的最大 _为N。43、构成森林的每棵子树的根结点是 _关系。45、有序树中每个结点的孩子结点的_是固定的。46、一棵具有N个结点的完全二叉树中，叶子结点的最大_为N。47、磁带文件批处理时，待修改的原文件称为_。所有的修改申请构成一个_ 。这两个文件是有序文件。它们利用的方式形成新 _。48、一棵二叉树中结点的度有 _，_，_，三种。49、哈（霍、赫）夫曼树中结点的度，只有_，_两种。50、从连通图的定义出发，树是一个没有 _的连通图。51、B-树的叶子结点为_结点，它们必须在_层上。52、除根为叶子结点外，根结点至少有 _棵子树。53、M 阶的B 树中，非叶子结点上最多有_个关键字。54、 M 阶的B 树中，非叶子结点上最少有_个关键字。55、N阶B+树中，结点上有_个关键字。56、在B+树上查找记录时，可以，从_开始按索引方式查找也可以从_开始按顺序查找。57、在计算机科学中常用的数据结构有_, _， _ ,_ 。58、栈的操作特点是 先进后出；队列的操作特点是 先进先出。59、线性表的顺序存储，要求每个数据元素都占用 相同的存储单元数。60、线性表的顺序存储可以用顺序查找，也可以用_ 查找。61、线性表的顺序存储的缺点是在任意位置上 插入数据与删除 数据费时间。62、在实际应用中，一般最多建立_ 级索引。63、线性表的顺序存储可以用顺序查找，也可以用_查找。64、线性表的顺序存储的缺点是在任意位置上 插入 数据与 删除 数据费时间。65、线性表的顺序存储是用一组 物理 连续的空间单元实现数据元素的存储。66、编写在内存中生成线性表（a1 a2 a3an ）的算法。(判断表是否满了)67、已知线性表（ a1 a2 a3an ）以顺序的方式存储在内存，编写在表中查找值为X的元素，若存在把它与其直接前驱元素交换，否则把X插到表尾的算法。并计算该算法的时间复杂性.（如果是a1就不交换）（可用while语句做）68、编写把线性表（ a1 a2 a3an ）的顺序完全倒置的算法。并计算该算法的时间复杂性及决定时间复杂性的语句频度。(对称交换)69编写把从线性表（ a1 a2 a3an ）中值为X 的元素开始到的所有元素顺序倒置的算法。70、线性表的链式存储C语言是用 语句实现空间单元动态分配。71、设一线性表的顺序存储，总存储容量为M ，其指针的变化范围为。(0M-1)72、线性表的顺序存储，要求每个数据元素都占用 的存储单元。73、头结点地址指针为L的循环单链表，空表的判别标志是 。74、头结点地址指针为L1的双循环链表，空表的判别标志是 。75、含有N 个结点的一棵完全二叉树上，叶子结点的最小编号是_。76、后根序序列和中根序序列相同的二叉树是树中每个结点只有 左 孩子结点的二叉树。77、先根序序列、中根序序列和后根序序列均相同的二叉树是 空 树或者是只有 一 个结点的二叉树。78、判定一棵线索二叉树中未知结点P没有左孩子的标志是 。79、线索二叉树是利用结点中空闲字段来记录 次序的二叉树。80、高度为K的一棵完全二叉树中，结点的总个数至少是 个；至多是 个。给出二叉树的先根序序列和中根序序列，便能 唯一 的确定这棵二叉树。81、先根序序列和中根序序列相同的二叉树是树中每个结点只有 左 孩子结点的二叉树。82、在一棵中序线索二叉树中已知在结点P的左侧插入一个新结点Y后仍然是一棵中序线索二叉树的操作，主要是查找P的 前驱结点。83、高度为K的一棵完全二叉树中，结点的总个数至少是 个；至多是 个。84、一棵M叉的树中，结点的度最多有 种。85、一棵高度为N 的树中，结点的最大 为N。86、一棵具有N个结点的完全二叉树中，叶子结点的最大_为N。87、构成森林的每棵子树的根结点是 兄弟 关系。88、有序树中每个结点的孩子结点的 是固定的。89、含有N 个结点的一棵完全二叉树上，叶子结点的最小编号是 。二、完成下列各题1、知A为二维数组，A-1 2，-2 3，按顺序存储，基址为999，每个元素都占用4个存储单元，分别计算元素A（-1，-1）按行（列）优先存储的地址号。（写出计算公式）2、知S=“aabbbccaabccaabc”, t =xxyy; m=ASSIGN( m, SUBSTR ( S ,LEN(t);i =INDEX( m,SUBSTR(S,6,LEN(t);求 REPLACE( m, SUBSTR(m,i,LEN(t),t) = ?3、知广义表A= (a),b,(d,(f),c),(e),g,(h),求A的长度与深度；4） 设有abcd，按顺序进入一个栈，试写出所有可能的输出序列。5 ）设有abcde,经过一个栈的处理得到输出序列为cdbea 。假设，用P代表一次进栈操作，Q代表一次退栈操作。要求，写出用PQ序列表示得到上述输出结果的过程。6 ）假设三维数组A，它的各维界偶分别为（4，9），（-1，5）， （-9，-2），基地址为20，每个元素占三个存储单元，试计算元素A6，0，-5的存储位置。7 ）写出head(tail(head(a,b),c,d)和tail(head(tail(a,(b,c,d)各自的运算结果。画出A的图形表示及一种存储结构图；写出用求头、尾元素的方式求出单元素h的过程。8、知一棵二叉树的先根序、中根序序列分别为123456789，243168975，试画出这棵二叉树。9、知一棵完全二叉树的结点个数为20到40之间的素数，求该二叉树的叶子结点个数。10、知一有向图G，用n*n维邻接矩阵表示，据此回答下列问题：1）该图中边的条数为多少？2）任一顶点的V的入度、出度是多少？3）若用邻接表方式存储图G，应构成多少个单链表？11、知一无向图G，用n*n维邻接矩阵表示，据此回答下列问题：1）该图中边的条数为多少？2）任一顶点的V度是多少？3）若用邻接表方式存储图G，应构成多少个单链表？12、假设N 为一棵结点的度只有0和2的二叉树中叶子结点的个数，M 为树中结点的总个数，证明：M = 2*N 1。13、设一棵具有N 个结点的二叉树用链式存储，每个结点都含有左右孩子指针域和数据域，证明：该树中共空闲N + 1个字段。14、知算术表达式为A*（B C）/E+ F*G H/（I + J），用学过的方法把它划成一棵二叉树。然后，再画成按后序遍历的线索二叉树。15、知要传输的数据为字符串“AABBBBAAAACCCDDCC”，试画出哈夫曼树并求出数据中每种符号的哈夫曼编码。16、知A，B，C，D，E为高度为3的一棵三叉树上的结点，也是由这棵三叉树转换成的高度为4的一棵二叉树上的结点，试画出满足上述两条件的所有三叉树和二叉树。17、知关键字集合（60，70，50， 40，30， 55，58）按顺序输入构成一棵平衡二叉排序树，画出中间出现的各不平衡树，并说明属于何种类型；画出最后的平衡二叉排序树。18、判断关键字集合（20，45，60，55，70，90，80，75）是否是堆树，若不是画出按顺序输入构成的树及整理成的堆树。然后再画出输出一个排序结果的树及调整后的堆。19、设某系学生举办运动会，参加同学的学号为（9301，9382，9372，9324，9345，9248，9262，9207，9223，9246，9152，9162，9109，9147，9118）。试画出其块大小为5的分块查找的数据结构图。20、设关键字集合（16，87，54，70，75，26，63，29，32，52，53，78），a = 0、75，设计一种散列函数，将它们进行散列，画出散列表并计算查找成功时的平均查找长度。21、在实际工作中顺序栈有两种，一种是我们讲过的栈顶移动的栈。另一种是栈底移动的栈。但一般都不用第二种方式，请回答为什么？22、设有abcd，按顺序进入一个栈，试写出所有可能的输出序列。23、高度为K的一棵完全二叉树中，结点的总个数最多是多少？最少是多少？24、设一棵满二叉树中，结点的总个数为20 40间的一个素数，问满二叉树中共有多少个叶子结点？25、一棵完全二叉树中结点的总个数是一个偶数，问该完全二叉树中有多少个度为一的结点？26、设一棵完全二叉树中结点i的堂兄弟结点的编号是2i+3 ，问该堂兄弟结点的双亲结点编号是多少？27、知A为二维数组，A-1 2，-2 3，按顺序存储，基址为999每个元素都占用4个存储单元，分别计算元素A（-1，-1）按行（列）优先存储的地址号。（写出计算公式）28、假设三维数组A，它的各维界偶分别为（4，9），（-1，5）， （-9，-2），基地址为20，每个元素占三个存储单元，试计算元素A6，0，-5的存储位置。29、写出head(tail(head(a,b),c,d)和tail(head(tail(a,(b,c,d)各自的运算结果。30、设有abcde,经过一个栈的处理得到输出序列为cdbea 假设，用P代表一次进栈操作，Q代表一次退栈操作。要求，写出用PQ序列表示得到上述输出结果的过程。31、一棵完全二叉树中的某个结点，如果没有左孩子结点，则其一定没有右孩子。这种说法正确吗？32、具有N个结点的一棵完全二叉树中，编号最小的叶子结点的编号是多少？33、知A为二维数组，A-1 2，-2 3，按顺序存储，基址为999每个元素都占用4个存储单元，分别计算元素A（-1，-1）按行（列）优先存储的地址号。（写出计算公式）34、已知下边给出的两棵二叉树是由森林转换成的，现要求画出原森林。35、用迪杰斯特拉算法，求右下图中从顶点V1到其他各顶点的最短路径，要求写出： 无图（1）网的带权邻接矩阵；（2）求最短路径的计算过程。36、利用深度优先搜索的方法编写求无向图中通过给定顶点VK的简单回路的算法。37、利用广度优先搜索思想编写求无向图中从V1顶点到VK顶点之间的最短路径（指边的条数）的算法。38、根据右下图的AOE网络完成各题：（1）求每个顶点的最早、晚时间； 无图（2）写出关键顶点；（3）是否有哪项活动减少时间后能使整个工期缩短。39、假设三维数组A，它的各维界偶分别为（4，9），（-1，5）， （-9，-2），基地址为20，每个元素占三个存储单元，试计算元素A6，0，-5的存储位置。40、写出head(tail(head(a,b),c,d)和tail(head(tail(a,(b,c,d)各自的运算结果。41、已知T为一棵二叉树的根结点，按先序遍历该树的输出序列为ABDFGHCE，按中序遍历该树的输出序列为BFDHGAEC，要求画出这棵二叉树。三.算法1、已知L 为单链表的头结点的地址指针，编写把L从第i个结点处分开形成两个带头结点的单链表的算法。第1个结点为新表结点。2、编写把一个值为X的结点插到表中地址为Y的结点之前的算法。3、已知L 为单链表的头结点的地址指针，数据结点值递增有序。编写把表中从值大于X的结点开始到小于值为Y的结点之间 的所有结点的顺序完全倒置的算法。4、已知L 为单链表的头结点的地址指针，表中结点的值都是正整数，编写把表中值为奇数的所有结点从表中删除并生成一个新的带头结点的单链表的算法。（要求用的时间较少）5、已知L 为单链表的头结点的地址指针，编写把表中值X的结点的直接前驱结点删除的算法。6、已知L为循环单链表的头结点指针，且每个结点都有一个空闲的前驱指针域，要求编写一个算法把该表变为循环双链表。7、已知一个循环单链表，要求编写删除表中地址为Y的结点的直接前驱结点的算法。8、已知L为循环单链表的头结点指针，要求编写把表从地址为Y的结点处分开，形成两个循环单链表的算法。Y作为新表的第一个结点。9、编写把一个循环双链表中已知结点P与其直接前驱结点位置交换的算法。（要求只用一个辅助空间P）10、已知一个循环单链表的尾结点地址P，问在该链表中能否执行首部删除、尾部插入结点的操作？如何实现？11、完成两个栈的设计以及进、退栈的算法。12、完成将迷宫的算法编写成C 语言的程序。13、编写链式栈的进、退栈算法。14、已知L为循环单链表的头结点地址指针，AV为另一单链表的第一个结点地址指针（如图示），要求用最少的时间、用最少的操作完成把L表中的全部结点链接到链表AV中，并写出相应的算法。15、求出子串NG在字符串JIAOTONG中的位置序号。ab图 三个盘子移动ca c b b cL AV16、由下图1知，此时队列中的空间并非全部都被占用（若用循环队列，这些空间可以被重新使用），现在，希望你想另外一种方法，也能使这些空间可以被重新使用。并设计实现进、出队列的算法。17、编写一个计算循环队列中数据元素个数的算法。（图2）18、设有m个连续的存储单元，现分成由一个栈和一个队列使用。栈和队列的容量不知且不相等。要求在任何时刻，只要栈和队列中已存储的元素个数之和小于m，便能满足用户的存放数据的申请。试设计出 FQ.frontQ.rear0 16 3 5 47 2CG D F EQ. frontQ.rear图2图1这种结构并写出进、出栈的算法。19、已知T为一棵二叉树的根结点，设计把树中每个结点的左右孩子结点交换的算法。20、已知T为一棵二叉树的根结点，设计把树中每个单分支结点，用添加数据值为0的新结点变为双分支结点的算法。21、已知T为一棵二叉树的根结点，设计把树中值为X的结点找出，并将它的两个孩子分别作为根生成两棵子树的算法。22、已知T为一棵二叉树的根结点，设计计算该树高度（深度）的算法。23、已知T为一棵二叉树的根结点，树中结点的数据值都是正整数其中只有一个值是寄数，设计找出该结点的算法。24、已知T为一棵二叉树的根结点，设计计算该树中结点总个数的算法。25、已知T为一棵中序线索二叉树的根结点指针，P为树中一个结点的地址，设计把一个新结点X插到结点P左侧（即作为P的左孩子）的算法。26、设计把一个新结点X插到结点P右侧（即作为P的右孩子）的算法。27、若把第一题中的新结点X改成是以X为根的一棵中序线索二叉树，设计把以X为根的一棵中序线索二叉树，插到结点P左侧（或右侧）的算法。四术语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. 树的深度28. 树的度29. 树30. 完全二叉树31. 前缀码32. 哈夫曼编码33. 最优二叉树34. 最小生成树35. 完全有向图36. 完全无向图37. 广度遍历38. 深度遍历39. 生成树40. 生成森林41. 环（简单环）42. 路径43. 极大连通子图44. 连通图45. 拓扑排序46. 关键路径47. 最短路径48. 折半查找49. 索引顺序表50. 二叉排序树51. 平衡因子52. 平衡二叉树53. 平衡旋转54. LR型平衡旋转55. LL型平衡旋转56. RL型平衡旋转57. RR型平衡旋转58. 哈希函数59. 哈希表60. shell排序61. 气泡排序法62. 选择排序63. 快速排序64. 堆排序65. 交换排序66. 插入排序67. 稳定排序68. 不稳定排序69. 内部排序70. 归并排序71. 基数排序72. 外部排序五简答1、什么是数据，数据元素、数据项？何谓主关键字？2、什么是数据结构？什么是存储结构？它们各有多少种形式？3、衡量一个算法性能好坏的标准是什么？5、如果两个算法的平均时间复杂度相同，能否说，这两个算法的实际执行时间一定相等？6、试描述数据结构的概念与程序设计语言中数据类型概念的区别。1、 什么是数据结构？什么是存储结构？它们各有多少种形式？2、 数据结构是如何分类的？举出你所学的六种并分类。3、 衡量一个算法性能好坏的标准是什么？4、 抽象数据类型如何描述，以线性表为例说明。5、 描述以下三个概念的区别：哨兵指针，哨兵结点，首结点（第一个元素结点）。6、 算法与程序的主要区别是什么？7、 如果两个算法的平均时间复杂度相同，能否说，这两个算法的实际执行时间一定相等？（不一定）。8、 线性表、栈、队列的区别与联系。9、 线性表的顺序存储结构与链式存储结构在操作上的特点是什么？10、 线性表与串的区别与联系。11、 静态链表与动态链表的不同点与相同点。12、 简述队列在顺序存储结构上实现的特点。13、 简述二栈共享空间时的数据结构、操作实现过程及优点。14、 链式结构存储串时，每个结点可存放多个字符，当插入和删除子串时操作如何实现？15、 如何用一维数组存储对称矩阵？16、 如何用一维数组存储下三角矩阵？17、 稀疏矩阵有几种存储方式分别叙述。18、 已知二叉树的中序遍历和先序遍历结果，如何确定这棵二叉树？19、 简述哈夫曼算法。20、 树的存储结构有几种？简述之。21、 一棵完全二叉树中的某个结点，如果没有左孩子结点，则其