数据结构题库

______________________________________________________________________________________________________________判断题一.绪论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-10ΧΧΧΧ∨11-15∨ΧΧΧ∨16-20ΧΧ∨∨∨21-25∨∨∨∨∨26-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-5∨ΧΧ∨∨6-10∨∨Χ∨Χ11-15∨∨Χ∨∨16-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、X22、∨四．串1、确定串Ｔ在串Ｓ中首次出现的位置的操作称为串的模式匹配。（）2、如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。（）3、一个任意串是其自身的子串。（）1、∨2、Χ3、∨五．数组和广义表1、多维数组是向量的推广。（）2、用相邻矩阵表示图所用的存储空间大小与图的边数成正比。（3、除插入和删除操作外，数组的主要操作还有存取、修改、检索和排序等。（）4、稀疏矩阵中0元素的分布有规律，因此可以采用三元组方法进行压缩存储。（）5.如果采用如下方式定义一维字符数组：constintmaxSize=30;chara[maxSize];则这种数组在程序执行过程中不能扩充。7.数组是一种静态的存储空间分配，就是说，在程序设计时必须预先定义数组的数据类型和存储空间大小，由编译程序在编译时进行分配。8.多维数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。9.使用三元组表示稀疏矩阵中的非零元素能节省存储空间。10.用字符数组存储长度为n的字符串，数组长度至少为n+1。1-5ΧΧΧΧ∨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+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-10Χ∨Χ∨Χ11-15ΧΧΧ∨∨16-20ΧΧΧ∨Χ21-25Χ∨Χ∨∨26-30∨ΧΧΧ∨31∨七．图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-5ΧΧΧ∨∨6-10∨∨Χ∨∨11-15Χ∨∨∨∨16-20Χ∨Χ∨Χ21-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->nextp->next=s____________。12、线性表的链式存储结构地址空间可以__不连续_______，而向量存储必须是地址空间_____连续______。13.线性表是由n（n≥0）个____数据元素_____组成的有限序列。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!=Null8、前驱，后继重题9、删除p的后继结点10、后继11、s->next=p->next;p->next=s12、不连续，连续13.数据元素14.链式（或链接）15.删除16.指针域17.分配18.不一定19.前驱20.表头指针21.删除22.前趋结点和后继结点23.链接指针24.存储25.p->llink三．栈和队列1、栈结构允许进行删除操作的一端为___栈顶__________。2、在栈的顺序实现中，栈顶指针top，栈为空条件___top=-1___________。3、对于单链表形式的队列，其空队列的F指针和R指针都等于_____头结点的指针_____________。?4、若数组s[0..n-1]为两个栈s1和s2的共用存储空间，仅当s[0..n-1]全满时，各栈才不能进行栈操作，则为这两个栈分配空间的最佳 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 是：s1和s2的栈顶指针的初值分别为__s[0]s[n-1]_______。5、允许在线性表的一端插入,另一端进行删除操作的线性表称为_队列______。插入的一端为__队尾____,删除的一端为__队头____。6、设数组A[m]为循环队列Q的存储空间，font为头指针，rear为尾指针，判定Q为空队列的条件____Q->font==Q->rear________________。7、对于顺序存储的队列，存储空间大小为n，头指针为F，尾指针为R。若在逻辑上看一个环，则队列中元素的个数为__(_R-F)%n________。8、已知循环队列的存储空间为数组data[21]，且头指针和尾指针分别为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==-13、头节点的指针4、s[0]，s[n-1]5、队列，队尾队头6、Q->font=Q->rear7、(R-F)%n8、179.后出先进10.先进先出11.栈顶指针12.队头（或队首）13.栈顶指针14.top==MaxSize-115.top==016.队尾17.p->link=top18.119.一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.doc\0”，则该字符串S的长度为_____16____。1、子串，主串2、Index(S,T,pos)3、D4、O(n)5、16.16五．数组和广义表1、已知一顺序存储的线性表，每个结点占用k个单元，若第一个结点的地址为DA1，则第i个结点的地址为___DA1+(i-1)*k___________。2、设一行优先顺序存储的数组A[5][6]，A[0][0]的地址为1100，且每个元素占2个存储单元，则A[2][3]的地址为__1130___________。3、设有二维数组A[9][19]，其每个元素占两个字节，第一个元素的存储地址为100，若按行优先顺序存储，则元素A[6,6]的存储地址为____340__________，按列优顺序存储，元素A[6,6]的存储地址为_____220_________。/*100+(6*9+6)*2*/4、假设以行为优先存储的三维数组A[5][6][7]，A[0][0][0]的地址为1100，每个元素占两个存储单元，则A[4][3][2]的地址为__1482_____。/*1100+{(4*6+3)*7+2}*2*/4、设二维数组A[m][n]按列优先存储，每个元素占1个存储单元，元素A00的存储地址loc(A00)，则Aij的存储地址loc(Aij)=_loc(A00)+j*_m+i__________________。6、稀疏矩阵一般采用_三元组_________方法进行压缩存储。7、稀疏矩阵可用_三元组________进行压缩存储，存储时需存储非零元的__行号______、____列号____、__值______。8、若矩阵中所有非零元素都集中在以主对角线为中心的带状区域中，区域外的值全为0，则称为_____三对角矩阵_____。9、若一个n阶矩阵A中的元素满足：Aij=Aji(0<=I,j<=n-1)则称A为___对称_________矩阵；若主对角线上方(或下方)的所有元素均为零时，称该矩阵为___（上）下三角矩阵___________。10、对于上三角形和下三角形矩阵，分别以按行存储和按列存储原则进行压缩存储到数组M[k]中，若矩阵中非0元素为Aij，则k对应为__i*(i-1)/2+j-1(i>=j)____和_j*(j-1)/2+i-1(i<j)_________。11、设有一上三角形矩阵A[5][5]按行压缩存储到数组B中，B[0]的地址为100，每个元素占2个单元，则A[3][2]地址为_____108_______。/*{3*(3-1)/2+2-1}*2=8*/12.一维数组所占用的空间是连续的。但数组元素不一定顺序存取，通常是按元素的____下标_____存取的。13.在程序运行过程中不能扩充的数组是_静态_________分配的数组。这种数组在声明它时必须指定它的大小。14.在程序运行过程中可以扩充的数组是_____动态_____分配的数组。这种数组在声明它时需要使用数组指针。？15.二维数组是一种非线性结构，其中的每一个数组元素最多有_________个直接前驱（或直接后继）。16.若设一个n(n的矩阵A的开始存储地址LOC(0,0)及元素所占存储单元数d已知，按行存储时其任意一个矩阵元素a[i][j]的存储地址为_LOC(0,0)+（i*n+j）d________。17.对称矩阵的行数与列数__相等_______且以主对角线为对称轴，aij=aji，因此只存储它的上三角部分或下三角部分即可。18.将一个n阶对称矩阵的上三角部分或下三角部分压缩存放于一个一维数组中，则一维数组需要存储__n*(n+1)/2_______个矩阵元素。19.将一个n阶对称矩阵A的上三角部分按行压缩存放于一个一维数组B中，A[0][0]存放于B[0]中，则A[I][J]在I≤J时将存放于数组B的_________位置。20.利用三元组表存放稀疏矩阵中的非零元素，则在三元组表中每个三元组元素对应一个非零元素的行号、列号和___值______。1、DA1+(i-1)*k2、1100+（6*2+3）*2=11303、100+（19*6+6）*2=340，100+（9*6+……）*2=2204、14825、loc（a00）+(j*m+i)*16、三元组7、三元组，行号，列号，值8、三对角矩阵9、上（下）三角矩阵10、i*（i-1）/2+j-1(i≥j)，j*(j-1)/2+i-1(i<j)11、10812.下标（或顺序号）13.静态14.动态15.两个16.LOC(0,0)+(i*n+j)*d17.相等18.n(n+1)/219.2n-I-1)*I/2+J20.值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，322、d23、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、在序列(2,5,8,11,15,16,22,24,27,35,50)中采用折半查找(二分查找)方法查找元素24，需要进行_____4_________次元素之间的比较。/*16、27、22、24*/21、设有10个值，构成哈夫曼树，则该哈夫曼树共有___19___个结点。/*10个值就是10个叶子结点；没有1度的结点*/22、从树中一个结点到另一个结点之间的分支构成这两个结点之间的_____路径_______。23.对于一棵具有n个结点的树，该树中所有结点的度数之和为_n-1_____。/*每一个结点对应一个棍就是一度（除根节点外）*/24.一棵树的广义表表示为a(b(c,d(e,f),g(h)),i(j,k(x,y)))，结点k的所有祖先的结点数为__2______个。25.一棵树的广义表表示为a(b(c,d(e,f),g(h)),i(j,k(x,y)))，结点f的层数为_____3____。假定树根结点的层数为0。26.假定一棵三叉树（即度为3的树）的结点个数为50，则它的最小高度为__4______。假定树根结点的深度为0。27.在一棵高度为3的四叉树中，最多含有___255_____个结点，假定树根结点的高度为0。28.在一棵三叉树中，度为3的结点数有2个，度为2的结点数有1个，度为1的结点数为2个，那么度为0的结点数有____6____个。29.一棵高度为5的完全二叉树中，最多包含有____63____个结点。假定树根结点的高度为0。/*2*2*2*2*2*2-1*/30.假定一棵树的广义表表示为A(B(C,D(E,F,G),H(I,J)))，则该树的高度为___3_____。假定树根结点的高度为0。31.在一棵二叉树中，假定双分支结点数为5个，单分支结点数为6个，则叶子结点数为____6____个。/*n0=n2+n1*/32.假定一棵二叉树的结点数为18，则它的最小高度为___3_____。假定树根结点的高度为0。1、前驱，路径2、叶子，终端，兄弟3、3；3；e,h,I,j,g；C；A,F；A；F,g4、线索5、56、k，2k-17、n1+n28、509、排序10、711、38412、102413、714、1115、1（0）16、3117、3，14，1518、2k-1，2k-119、中序20、421、1922、路径23.n-124.225.326.427.8528.629.6330.331.632.4七．图1、对于一个图G，若边集合E（G）为无向边的集合，则称该图为____无向图________。2、对于一个图G，若边集合E（G）为有向边的集合，则称该图为_____有向图_______。3、对于有向图，顶点的度分为入度和出度，以该顶点为终点的边数目叫__入度______；以该顶点为起点的边数目叫___岀度______。4、一个无向图采用邻接矩阵存储方法，其邻接矩阵一定是一个___对称矩阵___________。5、有一个n个顶点的有向完全图的弧数____2n_________。6、在无向图中，若从顶点A到顶点B存在__路径_______，则称A与B之间是连通的。7、在一个无向图中，所有顶点的度数之和等于所有边数的_______2____倍。8、一个连通图的生成树是该图的_____极小______连通子图。若这个连通图有n个顶点,则它的生成树有___n*（n-1）______条边。9、无向图的邻接矩阵是一个_______对称______矩阵。10、如果从一无向图的任意顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是_____连通的_______。11、若采用邻接表的存储结构，则图的广度优先搜索类似于二叉树的_____层次_______遍历。12、若图的邻接矩阵是对称矩阵，则该图一定是_______无向图_________。13、从如图所示的临接矩阵可以看出，该图共有__3____个顶点。如果是有向图，该图共有__4____条弧；如果是无向图，则共有_____3___条边。14、如果从一个顶点出发又回到该顶点，则此路径叫做_环/回路__________。15、一个具有个n顶点的无向图中，要连通全部顶点至少需要__n-1______条边。16.n(n﹥0)个顶点的连通无向图各顶点的度之和最少为_2（_n-1）_______。17.用邻接矩阵存储图，占用的存储空间与图中的___顶点_____数有关。18.设图G=(V,E)，V={V0,V1,V2,V3},E={(V0,V1),(V0,V2),(V0,V3),(V1,V3)}，则从顶点V0开始的图G的不同深度优先序列有____4____种。19.设图G=(V,E)，V={1,2,3,4},E={<1,2>,<1,3>,<2,4>,<3,4>}，从顶点1出发，对图G进行广度优先搜索的序列有__2______种。20.n(n﹥0)个顶点的无向图中顶点的度的最大值为__n-1_______。21.在重连通图中每个顶点的度至少为________。22.n个顶点的连通无向图的生成树含有___n-1______条边。23.11个顶点的连通网络N有10条边，其中权值为1,2,3,4,5的边各2条，则网络N的最小生成树各边的权值之和为____30_____。/*2*（1+2+3+4+5）=30*/24.在使用Kruskal算法构造连通网络的最小生成树时，只有当一条候选边的两个端点不在同一个___连通分量_____上，才会被加入到生成树中。25.一般来说,深度优先生成树的高度比广度优先生成树的高度要____高____。26.求解带权连通图最小生成树的Prim算法使用图的___邻接矩阵_____作为存储结构。？27.设图的顶点数为n，则求解最短路径的Dijkstra算法的时间复杂度为_O(n2)_______。1、无向图2、有向图3、入度，出度4、对称矩阵5、n(n-1)6、路径7、28、极小（最小），n-19、对称10、连通11、层次12、无向图13、3，4，314、环/回路15、n-116.2(n-1)17.顶点18.419.220.n-121.222.n-123.3024.连通分量25.高26.邻接矩阵27.O(n2)八．查找1、若待散列的序列为(18,25,63,50,42,32,9)，散列函数为H(key)=keyMOD9，与18发生冲突的元素有________2_____个。/*18、63*/2、关键字自身作为哈希函数，即H（k）=k，也可自身加上一个常数作为哈希函数，即H(k)=k+C这种构造哈希函数的方式叫___直接定址法_________。3、折半搜索只适合用于_____有序表______________。4、结点关键字转换为该结点存储单元地址的函数H称为_____哈希函数________或叫_____散列表_____。5、在索引查找中，首先查找___索引表_____，然后查找相应的__子表_______，整个索引查找的平均查找长度等于查找索引表的平均长度与查找相应子表的平均查找长度的___和____。6.链表只适用于顺序查找。7.在一棵高度为h的理想平衡二叉树中，最少含有__2h______个结点。假定树根结点的高度为0。8.在一棵高度为h的理想平衡二叉树中，最多含有_2h+1_-1______个结点。假定树根结点的高度为0。9.若将一棵树A(B(C,D,E),F(G(H),I))按照左子女-右兄弟表示法转换为二叉树，该二叉树中度为2的结点的个数为____2____个。10.将一棵树按照左子女-右兄弟表示法转换成对应的二叉树，则该二叉树中树根结点肯定没有__右______子女。11.以顺序搜索方法从长度为n的顺序表或单链表中搜索一个元素的渐进时间复杂度为__O(n)______。？12.对长度为n的搜索表进行搜索时，假定搜索第i个元素的概率为pi,搜索长度（即在搜索过程中依次同有关元素比较的总次数）为ci，则在搜索成功情况下的平均搜索长度的计算公式为_______。13.假定一个顺序表的长度为40，并假定顺序搜索每个元素的概率都相同，则在搜索成功情况下的平均搜索长度为__20.5______。/*等差数列求和Sn=na1+n(n-1)d/2*/14.从有序表(12,18,30,43,56,78,82,95)中折半搜索元素56时，其搜索长度为___3_____。？15.假定对长度n=50的有序表进行折半搜索，则对应的判定树中最底下一层的结点数为______个。16.从一棵二叉搜索树中搜索一个元素时，若给定值大于根结点的值，则需要向_右子树_______继续搜索。17.向一棵二叉搜索树中插入一个元素时，若元素的值小于根结点的值，则应把它插入到根结点的_____左子树___上。18.根据n个元素建立一棵二叉搜索树的渐进时间复杂度大致为____O(nlog2n)_________。19.在一棵AVL树中，每个结点的左子树高度与右子树高度之差的绝对值不超过__1______。20.根据一组记录(56,42,50,64,48)依次插入结点生成一棵AVL树时，当插入到值为___50____的结点时需要进行旋转调整。21.根据一组记录(56,74,63,64,48)依次插入结点生成一棵AVL树时，当插入到值为63的结点时需要进行______先右后左双翻转__________调整。22.根据一组记录(56,42,38,64,48)依次插入结点生成一棵AVL树时，当插入到值为38的结点时需要进行___向右单翻转_________调整。23.根据一组记录(56,42,73,50,64,48,22)依次插入结点生成一棵AVL树时，当插入到值为___48____的结点时才出现不平衡，需要进行旋转调整。24.在索引表中，若一个索引项对应数据对象表中的一个表项，则称此索引为稠密索引，若对应数据对象表中的若干表项，则称此索引为___稀疏_____索引。25.假定对长度n=100的线性表进行索引顺序搜索，并假定每个子表的长度均为，则进行索引顺序搜索的时间复杂度为_0(10)______。26.假定对长度n=100的线性表进行索引顺序搜索，并假定每个子表的长度均为，则进行索引顺序搜索的平均搜索长度为________。/*5.5+5.5=11*/27.若对长度n=10000的线性表进行二级索引存储，每级索引表中的索引项是下一级20个表项的索引，则一级索引表的长度为____500____。29.假定要对长度n=100的线性表进行散列存储，并采用开散列法处理冲突，则对于长度m=20的散列表，每个散列地址的同义词子表（单链表）的长度平均为___5_____。/*100/20*/30.在线性表的散列存储中，装载因子(又称为装载系数，若用m表示散列表的长度，n表示待散列存储的元素的个数，则(等于_____n/m___。31.对于包含n个关键码的m阶B树，其最小高度为____(logm(n+1)(________。32.已知一棵3阶B树中含有50个关键码，则该树的最小高度为___4_____。33.已知一棵3阶B树中含有50个关键码，则该树的最大高度为___5_____。34.在一棵m阶B树上，每个非根结点的关键码数最少为________个。35.在一棵m阶B树上，每个非根结点的子树最少为___(m/2(_____棵。36.在一棵m阶B树上，每个非根结点的关键码数最多为________个。37.在对m阶B树插入元素的过程中，每向一个结点插入一个关键码后，若该结点的关键码个数等于________个，则必须把它分裂为2个结点。38.在从m阶B树删除关键码的过程中，当从一个结点中删除掉一个关键码后，所含关键码个数等于(m/2(-2个，并且它的左、右兄弟结点中的关键码个数均等于________，则必须进行结点合并。39.在一棵具有n个结点的AVL树上进行插入或删除元素的渐进时间复杂度大致为_________。1、22、直接定址法3、有序表4、哈希函数，散列函数5、索引表，子表，和6.顺序7.2h8.2h+1-19.210.右11.O(n)12.13.20.514.315.1916.右子树17.左子树18.O(nlog2n)19.120.5021.先右后左双旋转22.右单旋转23.6424.稀疏25.O(Eq\r(n))26.1127.50028.2529.530.n/m31.(logm(n+1)(32.433.534.(m/2(-135.(m/2(36.m-137.m38.(m/2(-139.O(log2n)九．排序1、在进行直接插入排序时,其数据比较次数与数据的初始排列____有____关；而在进行直接选择排序时，其数据比较次数与数据的初始排列______无____关。2、每一趟排序时从排好序的元素中挑出一个值最小的元素与这些未排小序的元素的第一个元素交换位置，这种排序方法成为______选择_______排序法。3、给定序列{100,86,48,73,35,39,42,57,66,21},按堆结构的定义,则它一定____大顶_____堆。4、从未排序序列中选择一个元素，该元素将当前参加排序的那些元素分成前后两个部分，前一部分中所有元素都小于等于所选元素，后一部分中所有元素都大于或等于所选元素，而此时所选元素处在排序的最终位置。这种排序法称为______快速_______排序法。5.在一个堆的顺序存储中，若一个元素的下标为i(0≤i≤n-1)，则它的左子女元素的下标为__2i+1____。6.在一个堆的顺序存储中，若一个元素的下标为i(0≤i≤n-1)，则它的右子女元素的下标为__2i+2______。7.在一个最小堆中，堆顶结点的值是所有结点中的__最小的______。8.在一个最大堆中，堆顶结点的值是所有结点中的_最大的_______。9.第i(i=1,2,…,n-1)趟从参加排序的序列中取出第i个元素，把它插入到由第0个至第i-1个元素组成的有序表中适当的位置，此种排序方法叫做_____直接插入_____排序。10.第i(i=0,1,...,n-2)趟从参加排序的序列中第i个至第n-1个元素中挑选出一个最小元素，把它交换到第i个位置，此种排序方法叫做____直接选择_____排序。11.每次直接或通过基准元素间接比较两个元素，若出现逆序排列就交换它们的位置，这种排序方法叫做___交换_______排序。12.每次使两个相邻的有序表合并成一个有序表，这种排序方法叫做___二路归并______排序。13.在直接选择排序中，记录比较次数的时间复杂度为__O(n2)______。14.在直接选择排序中，记录移动次数的时间复杂度为__________。？15.在堆排序中，对n个记录建立初始堆需要调用__________次调整算法。16.在堆排序中，如果n个对象的初始堆已经建好，那么到排序结束，还需要从堆顶结点出发调用___n-1______次调整算法。17.在堆排序中，对任意一个分支结点进行调整运算的时间复杂度为____O(log2n)________。18.对n个数据对象进行堆排序，总的时间复杂度为____O(nO(nlog2n))__________。19.给定一组数据对象的关键码为{46,79,56,38,40,84}，则利用堆排序方法建立的初始堆（最大堆）为_84,79,56,38,46,40______________。20.快速排序在平均情况下的时间复杂度为___________。21.快速排序在最坏情况下的时间复杂度为____________。22.快速排序在平均情况下的空间复杂度为____________。?23.快速排序在最坏情况下的空间复杂度为___O(nlog2n)_________。24给定一组数据对象的关键码为{46，79，56，38，40，84}，对其进行一趟快速排序处理，得到的右子表中有___3_____个对象。25.在对n个数据对象的二路归并排序中，每趟归并的时间复杂度为O(n)____________。26.在对n个数据对象进行的二路归并排序中，整个归并过程的时间复杂度为__O(nlog2n)_________。27.在索引表中，每个索引项至少包含有__关键码________域和地址域这两项。28.假定一个线性表为{12,23,74,55,63,40,82,36}，若按key%3条件进行划分，使得同一余数的元素成为一个子表，则包含74的子表长度为___3_____。29.假定一个线性表为(”abcd”,”baabd”,”bcef”,”cfg”,”ahij”,”bkwte”,”ccdt”,”aayb”)，若按照字符串的第一个字母进行划分，使得同一个字母被划分在一个子表中，则得到的以a为第一个字母的子表长度为_____3___。1、有，无2、选择3、大根堆4、快速5.2i+16.2i+27.最小值8.最大值9.直接插入10.直接选择11.交换12.二路归并3.O(n2)14.O(n)15.n/216.n-117.O(log2n)18.O(nlog2n)19.84，79，56，38，40，4620.O(nlog2n)21.O(n2)22.O(log2n)23.O(n)24.325.O(n)26.O(nlog2n)27.关键码28.229.3三、选择题：一．绪论（）1.数据结构通常是研究数据的及它们之间的联系。A存储和逻辑结构B存储和抽象C理想和抽象D理想与逻辑（）2.计算机识别、存储和加工处理的对象被统称为_________A．数据B.数据元素C.数据结构D.数据类型（）3．若需要利用形参直接访问实参，则应把形参变量说明为____参数。A.指针B.引用C.值D.变量（）4.算法指的是________A.计算机程序B.解决问题的计算方法C.排序算法D.解决问题的有限运算序列（）5.若需要利用形参直接访问实参，则应把形参变量说明为________参数。A指针B引用C值D常量（）6．下面算法的时间复杂度为＿＿。intf（intn）{if（n＝＝0）return1；else  return  n＊f（n-1）；}A．O(1)B．O(n)　C．O(n²)　D．O(n!)（）7.数据结构是一门研究非数值计算的程序设计问题中计算机的（　①　）以及它们之间的（　②　）和运算的学科　　①Ａ、操作对象　Ｂ、计算方法　Ｃ、逻辑存储　Ｄ、数据映象②Ａ、结构　　　Ｂ、关系　　　Ｃ、运算　　　Ｄ、算法（）8.数据结构被形式地定义为(K，R)，其中K是（　①　）的有限集合，R是K上（　②　）的有限集合①Ａ、算法　Ｂ、数据元素　Ｃ、数据操作　Ｄ、逻辑结韵②Ａ、操作　Ｂ、映象　　　Ｃ、存储　　　Ｄ、关系（）9.在数据结构中，从逻辑上可以把数据结构分为________Ａ、动态结构和静态结构　　Ｂ、紧凑结构和非紧凑结构Ｃ、线性结构和非线性结构　Ｄ、内部结构和外部结构（）10.线性表的顺序存储结构是一种_________的存储结构，线性表的链式存储结构是一种________的存储结构Ａ、随机存取　　Ｂ、顺序存取　　Ｃ、索引存取　　Ｄ、HASH存取（）11.算法分析的目的是（　①　），算法分析的两个主要方面是（　②　）①Ａ、找出数据结构的合理性Ｃ、分析算法的效率以求改进　　　Ｂ、研究算法中的输入和输出的关系Ｄ、分析算法的易懂性和文档性②Ａ、空间复杂性和时间复杂性Ｃ、可读性和文档性Ｂ、正确性和简明性Ｄ、数据复杂性和程序复杂性（）12.计算机算法指的是（　①　），它必具备输入、输出和（　②　）等五个特性①Ａ、计算方法　Ｂ、排序方法　Ｃ、解决莱一问题的有限运算序列　Ｄ、调度方法②Ａ、可执行性、可移植性和可扩充性Ｃ、确定性、有穷性和稳定性Ｂ、可执行性、确定性和有穷性Ｄ、易谩性、稳定性和安全性（）13.对于两个函数，若函数名相同，但只是____________不同则不是重载函数。A、参数类型B、参数个数C、函数类型D、函数变量（）14.若需要利用形参直接访问实参，则应把形参变量说明为________参数A、指针B、引用C、值D、函数（）15.下面程序段的时间复杂度为____________。for(inti=0;i<m;i++)for(intj=0;j<n;j++)A[i][j]=i*j;A、O(m2)B、O(n2)C、O(m*n)D、O(m+n)（）16.执行下面程序段时，执行S语句的次数为____________。/*n*i*/for(inti=1;i<=n;i++)for(intj=1;j<=i;j++)S;A、n2B、n2/2C、n(n+1)D、n(n+1)/2（）17.下面算法的时间复杂度为____________。intf(unsignedintn){if(n==0||n==1)return1;elsereturnn*f(n-1);}A、O(1)B、O(n)C、O(n2)D、O(n!)1-5AAADA6-BDADACBA11-CACBCAC16-17DB二．线性表（）1.设单链表中结点的结构为　　typedefstructnode{file://链表结点定义　　ElemTypedata；file://数据　　structnode*Link；file://结点后继指针　　}ListNode；　　已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行下列哪一个操作______。A.s->link=p；p->link=s；　　B.s->link=p->link；p->link=s；C.s->link=p->link；p=s；D.p->link=s；s->link=p；（）2.设单链表中结点的结构为typedefstructnode{file://链表结点定义ElemTypedata；file://数据structnode*Link；file://结点后继指针}ListNode；非空的循环单链表first的尾结点（由p所指向）满足：______A.p->link==NULL；　　B.p==NULL；C.p->link==first；　　D.p==first；（）3.在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是________A．O（1）B.O（n）C.O(nlogn)D.O(n2)（）4.在长度为n的顺序存储的线性表中，删除第i个元素（1≤i≤n）时，需要从前向后依次前移____个元素。A、n-iB、n-i+1C、n-i-1D、i（）5．在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行____。A.q一>next=p一>next；p一>next=q；C.q一>next=p一>next；p一>next=q；B.p一>next=q一>next；q=p；D.p一>next=q一>next；q一>next=p；（）6.线性表采用链式存储时，结点的存储地址________A.必须是不连续的B.连续与否均可C.必须是连续的D.和头结点的存储地址相连续（）7.将长充为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为________A.O（1）B.O（n）C.O（m）D.O（m+n）（）8.设单链表中结点的结构为（data,link）。已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作________A.s->link=p->link;p->link=s;B.p->link=s;s->link=q;C.p->link=s->link;s->link=p;D.q->link=s;s->link=p;（）9.线性链表不具有的特点是________。A.随机访问B.不必事先估计所需存储空间大小C.插入与删除时不必移动元素D.所需空间与线性表长度成正比（）10.线性表若采用链表存储结构时，要求内存中可用存储单元的地址________Ａ、必须是连续的　　　Ｂ、部分地址必须是连续的Ｃ、一定是不连续的　　Ｄ、连续不连续都可以（）11．在一个长度为n的顺序存储线性表中，向第i个元素(1≤i≤n+1)之前插入一个新元素时，需要从后向前依次后移个元素。A、n-iB、n-i+1C、n-i-1D、i（）12．在一个长度为n的顺序存储线性表中，删除第i个元素(1≤i≤n+1)时，需要从前向后依次前移_____个元素。A、n-iB、n-i+1C、n-i-1D、i（）13.在一个长度为n的线性表中顺序查找值为x的元素时，查找时的平均查找长度（即x同元素的平均比较次数，假定查找每个元素的概率都相等）为_____。A、nB、n/2C、(n+1)/2D、(n-1)/2（）14．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行_____。A、HL=p;p->next=HL;C、p->next=HL;p=HL;B、p->next=HL;HL=p;D、p->next=HL->next;HL->next=p;（）15．在一个单链表HL中，若要在指针q所指的结点的后面插入一个由指针p所指的结点，则执行_____。A、q->next=p->next;p->next=q;C、q->next=p->next;p->next=q;B、p->next=q->next;q=p;D、p->next=q->next;q->next=p;（）16．在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行_____。A、p=q->next;p->next=q->next;B、p=q->next;q->next=p->next;C、p=q->next;q->next=p;D、q->next=q->next->next;q->next=q1-5BCBAD6-10BCDAD11-15BADDD16B三．栈和队列（）1.在堆栈中存取数据的原则是。A先进先出B后进先出C先进后出D随意进出（）2.由两个栈共享一个向量空间的好处是______。A减少存取时间,降低下溢发生的机率B节省存储空间,降低上溢发生的机率C减少存取时间,降低上溢发生的机率D节省存储空间,降低下溢发生的机率（）3.设长度为n的链队列用单循环链表表示，若只设头指针，则入队操作的时间复杂度为_______。A.O(1)B.O(log2n)C.O(n)D.O(n2)（）4．队和栈的主要区别是________A.逻辑结构不同B.存储结构不同C.所包含的运算个数不同D.限定插入和删除的位置不同（）5．链栈与顺序栈相比，比较明显的优点是________A.插入操作更加方便B.删除操作更加方便C.不会出现下溢的情况D.不会出现上溢的情况（）6.假定一个顺序队列的队首和队尾指针分别为f和r，则判断队空的条件为____。A、f+1==rB、r+1==fC、f==0D、f==r（）7．在一个顺序队列中，队首指针指向队首元素的____位置。A.前一个B.后一个C.当前D.最后一个（）8.由两个栈共享一个向量空间的好处是：________A.减少存取时间，降低下溢发生的机率B.节省存储空间，降低上溢发生的机率C.减少存取时间，降低上溢发生的机率D.节省存储空间，降低下溢发生的机率（）9.设数组Data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为________A.front=front+1B.front=(front+1)%(m-1)C.front=(front-1)%mD.front=(front+1)%m（）10.链式栈与顺序栈相比，一个比较明显的优点是________。A.插入操作更加方便B.通常不会出现栈满的情况C.不会出现栈空的情况D.删除操作更加方便（）11．若让元素1,2,3依次进栈，则出栈次序不可能出现________种情况。A.3,2,1B.2,1,3C.3,1,2D.1,3,2（）12.假定一个顺序队列的队首和队尾指针分别为front和rear，存放该队列的数组长度为N，则判断队空的条件为________。A．（front+1）%N==rear      C．front==0B．（rear+1）%N==front  D．front==rear（）13．栈的插入和删除操作在＿＿＿进行．(Ａ)．栈顶　(Ｂ)．栈底(Ｃ)．任意位置(Ｄ).指定位置?（）14.在一个顺序循环队列中，队首指针指向队首元素的________位置。A.后两个B.后一个C.当前D.前一个（）15.在以下的叙述中，正确的是__________Ａ、线性表的线性存储结构优于链表存储结构Ｃ、栈的操作方式是先进先出Ｂ、二维数组是它的每个数据元素为一个线性表的线性表Ｄ、队列的操作方式是先进后出（）16．栈的插入与删除操作在_____进行。A、栈顶B、栈底C、任意位置D、指定位置（）17．当利用大小为N的一维数组顺序存储一个栈时，假定用top==N表示栈空，则向这个栈插入一个元素时，首先应执行_____语句修改top指针。A、top++B、top--C、top=0D、top（）18．若让元素1，2，3依次进栈，则出栈次序不可能出现_____种情况。A、3，2，1B、2，1，3C、3，1，2D、1，3，2（）19．在一个循环顺序队列中，队首指针指向队首元素的_____位置。A、前一个B、后一个C、当前D、后面（）20．当利用大小为N的一维数组顺序存储一个循环队列时，该队列的最大长度为_____。A、N-2B、N-1C、ND、N+1（）21．从一个循环顺序队列删除元素时，首先需要_____。A、前移一位队首指针B、后移一位队首指针C、取出队首指针所指位置上的元素D、取出队尾指针所指位置上的元素（）22．假定一个循环顺序队列的队首和队尾指针分别为f和r，则判断队空的条件是_____。A、f+1==rB、r+1==fC、f==0D、f==r（）23．假定一个链队的队首和队尾指针分别为front和rear，则判断队空的条件是_____。A、front==rearB、front!=NULLC、rear!=NULLD、front==NULL栈和队列1—5CBCDD6—10DABDB11—15CDADB16—20ABCAB21—23BDA四．串（）1．在目标串T[0…n-1]=”xwxxyxy”中，对模式串p[0…m-1]=”xy”进行子串定位操作的结果_______A.0B.2C.3D.5（）2.如下陈述中正确的是________A.串是一种特殊的线性表B.串的长度必须大于零C.串中元素只能是字母D.空串就是空白串（）3.若目标串的长充为n，模式串的长度为[n/3]，则执行模式匹配算法时，在最坏情况下的时间复杂度是________A.O（1）B.O（n）C.O（n2）D.O（n3）串1—3CAB五．数组和广义表（）1．二维数组A按行顺序存储，其中每个元素占1个存储单元。若A[1][1]的存储地址为420，A[3][3]的存储地址为446，则A[5][5]的存储地址为_______A.470B.471C.472D.473（）2．在稀疏矩阵的十字链接存储中，每个列单链表中的结点都具有相同的_____。Ａ．行号Ｂ．列号Ｃ．元素值Ｄ．地址（）3.一个数组元素A[i]与________的表示等价。A、*(A+i)B、A+iC、*A+iD、&A+i（）4.在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相同的________。A、行号B、列号C、元素值D、地址数组1—4CAAA广义表（）1．已知广义表的表头为A，表尾为(B,C)，则此广义表为________A.（A,(B,C)）B.（A,B,C）C.(A,B,C)D.((A,B,C))（）2.设一个广义表中结点的个数为n，则求广义表深度算法的时间复杂度为____。A、O(1)B、O(n)C、O(n2)D、O(log2n)（）3.一个非空广义表的表头________A.不可能是子表B.只能是子表C.只能是原子D.可以是子表或原子（）4.设一个广义表中结点的个数为n，则求广义表深度算法的时间复杂度为_______。A、O(1)B、O(n)C、O(n2)D、O(log2n)广义表1—4BDDB六．树（）1.将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子的编号为______。A.98B.99C.50D.48()2.对于如图所示二叉树采用中根遍历，正确的遍历序列应为()A.ABCDEF                    B.ABECDFC.CDFBEA                    D.CBDAEF（）3.某二叉树的前序和后序序列正好相反，则该二叉树一定是_____的二叉树A空或者只有一个结点B高度等于其结点数C任一结点无左孩子D任一结点无右孩子（）4．二叉树中第5层上的结点个数最多为________A.8B.15C.16D.32（）5.由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为________。A、24B、48C、72D、55（）6.一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为________A.4B.5C.6D.7树1—6ADBCDC七．图（）1.在含有n个项点有e条边的无向图的邻接矩阵中，零元素的个数为________。A.eB.2eC.n2-eD.n2-2e（）2.图的深度优先遍历类似于二叉树的_______。A.先序遍历B.中序遍历C.后序遍历D.层次遍历（）3.一个无向连连通图的生成树是含有该连通图的全部项点的_______。A.极小连通子图B.极小子图C.极大连通子图D.极大子图（）4．如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是_______A.有向完全图B.连通图C.强连通图D.有向无环图（）5．下面关于图的存储的叙述中，哪一个是正确的。________A．用相邻矩阵法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关B．用相邻矩阵法存储图,占用的存储空间数只与图中边数有关,而与结点个数无关C．用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关D．用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关（）6.输入序列为（A,B,C,D），不可能得到的输出序列是______.A.(A,B,C,D)B.(D,C,B,A)C.(A,C,D,B)D.(C,A,B,D)图1--5DAADA6D八．查找（）1.设有100个元素，用折半查找法进行查找时，最大比较次数是_____。A.25B.50C.10D.7（）2.设散列表长m=14,散列函数H（K）=K％11，已知表中已有4个结点：r(15)=4;r(38)=5;r(61)=6;r(84)=7，其他地址为空，如用二次探测再散列处理冲突，关键字为49的结点地址是________。A8B3C5D9（）3．对于哈希函数H(key)=key%13，被称为同义词的关键字是_______A．35和41B.23和39C.15和44D.25和51（）4．对包含N个元素的散列表进行检索，平均检索长度________A、为o(log2N)B、为o(N)C、不直接依赖于ND、上述三者都不是（）5．向二叉搜索树中插入一个元素时，其时间复杂度大致力____。AO（1）BO（1og2n）CO（n）DO（nlog2n）（）6.从二叉搜索树中查找一个元素时，其时间复杂度大致为________。A、O(n)B、O(1)C、O(log2n)D、O(n2)（）7.根据n个元素建立一棵二叉搜索树时，其时间复杂度大致为________。A、O(n)B、O(log2n)C、O(n2)D、O(nlog2n)（）8.适于对动态查找表进行高效率查找的组织结构是________A.有序表B.分块有序表C.二叉排序树D.线性链表查找1—5DDDCB6—8CDC九．排序（）1.快速排序在_____情况下最易发挥其长处。A.被排序数据中含有多个相同排序码B.被排序数据已基本有序C.被排序数据完全无序D.被排序数据中最大值和最小值相差悬殊（）2.堆的形状是一棵_______。A.二叉排序树B.满二叉树C.完全二叉树D.平衡二叉树（）3.一个序列中有10000个元素，若只想得到其中前10个最小元素，最好采用_______方法A.快速排序B.堆排序C.插入排序D.二路归并排序（）4．对n个关键字的序列进行快速排序，平均情况下的空间复杂度为_______A.O（1）B.O（logn）C.O（n）D.O（nlogn）（）5.向堆中插入一个元素的时间复杂度为________。A、O(log2n)B、O(n)C、O(1)D、O(nlog2n)（）6.从堆中删除一个元素的时间复杂以为____。A、O(1)B、O(log2n)C、O(n)D、O(nlog2n)（）7.从堆中删除一个元素的时间复杂度为________。A、O(1)B、O(n)C、O(log2n)D、O(nlog2n)（）8.用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况是如下________：20，15，21，25，47，27，68，35，8415，20，21，25，35，27，47，68，8415，20，21，25，27，35，47，68，84则所采用的排序方法是________A.选择排序B.希尔排序C.归并排序D.快速排序排序1—5CCBDA6—8BCD应用题：1、栈和队列都是特殊线性表，其特殊性是什么？2、设有一顺序队列sq，容量为5，初始状态sq.front=sq.rear=0，划出作完下列操作的队列及其头尾指针变化状态，若不能入队，简述理由后停止。1）d,e,b入队。2）d,e出队。3）i,j入队。4）b出队。5）n,o,p入队。3、设有一个顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素的出栈顺序为s2,s3,s4,s6,s5,s1，则顺序栈的容量至少应为多少？4、将两个栈存入数组V[1..m]中应如何安排最好?这时栈空、栈满的条件是什么?5、已知稀疏矩阵如下：请写出该稀疏矩阵三元组表示。6、广义表A=（a,b,(c,d),(e,(f,g))）,求其长度，及深度。7、请画出下面广义表相应的加入表头结点的单链表表示，D(A(x,y,L(a,b))，B(z,A(x,y,L(a,b))))。8、一棵具有n个结点的理想平衡二叉树（即除离根最远的最底层外其他各层都是满的，最底层有若干结点）有多少层？若设根结点在第0层，则树的高度h如何用n来表示（注意n可能为0）？　9、设二叉树后根遍历为BAC，画出所有可能的二叉树。10、假设一棵二叉树的层序序列是ABCDEFGHIJ和中序序列是DBGEHJACIF,请画出该树。11、有一个完全二叉树按层次顺序存放在一维数组中，如下所示：请指出结点P的父结点，左子女，右子女。12、给出下列二叉树的先序序列。13、已知某非空二叉树采用顺序存储结构，树中结点的数据信息依次存放在一个一维数组中，即ABC□DFE□□G□□H□□，该二叉树的中序遍历序列为：14、设一棵二叉树的前序序列为1,2,3,4,5,6,7,8,9,其中序序列为2,3,1,5,4,7,8,6,9,试画出该二叉树。15、已知一组元素为（46，25，78，62，12，37，70，29），试画出按元素排列次序插入生成的一棵二叉树。16、由于元素插入的次序不同，所构成的二叉排序树也有不同的状态，请画出一棵含有1，2，3，4，5，6六个结点且以1为根，深度为4的二叉排序树。17、什么是线索二叉树？为什么要线索化？18、有n个顶点的有向连通图最多有多少条边?最少有多少条边？19、下图中给出由7个顶点组成的无向图。从顶点1出发，对它进行深度优先遍历得到的顶点序列是：进行广度优先遍历得到的顶点序列是：20、什么是连通图的生成树？21、什么是哈夫曼（Huffman）树？22、已知结点a,b,c,d及其权值写出哈夫曼树的构造过程。abcd752423、已知图G={V,E}V={a,b,c,d,e}E={(a,b),(b,d),(c,d),(d,e),(e,a),(a,c)}画出图G，画出图G的邻接表。24、考虑下图：1）从顶点A出发，求它的深度优先生成树。2）从顶点E出发，求它的广度优先生成树。3）根据普里姆（Prim）算法，求它的最小生成树。 25、设有关键码序列（Q，H，C，Y，Q，A，M，S，R，D，F，X），要按照关键码值递增的次序进行排序。若采用初始步长为4的Shell排序法，则一趟扫描的结果是：若采用以第一个元素为分界元素的快速排序法，则一趟扫描的结果是：26、一个对象序列的排序码为{46，79，56，38，40，84}，采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为：27、用二分法对一个长度为10的有序表进行查找，填写查找每个元素需要的比较次数。下标：0123456789比较次数：28、若对序列(49,38,27,13,97,76,50,65)采用泡排序法(按照值的大小从小到大)进行排序，请分别在下表中写出每一趟排序的结果。原始序列4938271397765065第1趟的结果第2趟的结果第3趟的结果第4趟的结果29、给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程：1）归并排序每归并一次 书 关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf 写一个次序。2）快速排序每划分一次书写一个次序。3）堆排序先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。30、给出一组关键字T=（12，2，16，30，8，28，4，10，20，6，18）。写出用下列算法从小到大排序时第一趟结束时的序列：1）希尔排序（第一趟排序的增量为5）2）快速排序(选第一个记录为枢轴(分隔))3）链式基数排序（基数为10）31、若杂凑表的地址范围为[0:9]，杂凑函数为H(key)=(key2+2)MOD9，并且采用链地址方法处理冲突，请画出元素7,4,5,3,6,2,8,9,1依次插入该杂凑表以后，该杂凑表的状态。32、已知二叉树采用二叉链表存储结构，链结点的构造为lchild|data|rchild，根结点的指针为T。下面是利用中序遍历的方法统计二叉树中度为1的结点的个数的算法，算法中设置了一顺序存储结构的堆栈STACK[1:M]，栈顶指针为top，请在算法的空缺处填入适当内容，使之能正常工作。33、设有一个顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素的出栈顺序为s2,s3,s4,s6,s5,s1，则顺序栈的容量至少应为多少？34、设有一个关键码的输入序列{55,31,11,37,46,73,63,02,07},　　(1)从空树开始构造平衡二叉搜索树,画出每加入一个新结点时二叉树的形态。若发生不平衡,指明需做的平衡旋转的类型及平衡旋转的结果。　　(2)计算该平衡二叉搜索树在等概率下的查找成功的平均查找长度。35、关键码的输入序列{55,31,11,37,46,73,63,02,07}请计算在二分法查找、二叉排序树两种的情况下等概率下查找成功的平均查找长度。36、广义表A=（a,b,(c,d),(e,(f,g))）,计算下面式子的值Head(Tail(Head(Tail(Tail(A)))))37、下图是用邻接表存储的图，画出此图，并写出从C点开始按深度优先、广度优先遍历该图的结果。38、用序列（46，88，45，39，70，58，101，10，66，34）建立一个排序二叉树，画出该树，并求在等概率情况下查找成功的平均查找长度。39、判断下列序列是否为堆，如果不是请调整为堆，如果是请判断是什么类型的堆（101，88，46，70，34，39，45，58，66，10）40、假设一棵二叉树的层序序列是ABCDEFGHIJ和中序序列是DBGEHJACIF,请画出该树。41、找出所有满足下列条件的二叉树a)它们在先序遍历和中序遍历时,得到的结点访问序列相同；b)它们在后序遍历和中序遍历时,得到的结点访问序列相同；c)它们在先序遍历和后序遍历时,得到的结点访问序列相同。42、已知L是无表头结点的单链表,其中P结点既不是首元结点,也不是尾元结点。a)在P结点后插入S结点的语句序列是______b)在P结点前插入S结点的语句序列是______c)在表首插入S结点的语句序列是______d)在表尾插入S结点的语句序列是______(1)P->next=S;(2)P->next=P->next->.next;(3)P->next=S->next;(4)S->next=P->next;(5)S->next=L;(6)S->next=NIL;(7)Q=P;(8)WHILEP->next<>QP=P->next;(9)WHILEP->next!=NULLP=P->next;(10)P=Q;(11)P=L;(12)L=S;(13)L=P;43、已知树T的先序遍历序列为ABCDEFGHIJKL，后序遍历序列为CBEFDJIKLHGA，请画出树T。44、对关键字序列（72，87，61，23，94，16，5，58）进行堆排序、快速排序、直接选择排序，使之关键字递增有序，请写出每个排序的前三趟结果。45、请画出广义表D的图形表示D=(D,(a,b),((a,b),c),())46、若一二叉树有2度结点100个，则其叶结点有多少个？该二叉树可以有多少个1度顶点？47、对于单链表、单循环链表和双向链表，如果仅仅知道一个指向链表中某结点的指针p，能否将p所指结点的数据元素与其确实存在的直接前驱交换?请对每一种链表作出判断，若可以，写出程序段；否则说明理由。单链表和单循环链表的结点结构为 data next双向链表的结点结构为 prior data next(1)单链表(2)单循环链表(3)双向链表48、已知散列函数为H(key)=key%7，散列表长度为7(散列地址空间为0..6)，待散列序列为：(25，48，32，50，68)。要求：(1)根据以上条件构造一散列表，并用线性探测法解决有关地址冲突；(2)若要用该散列表查找元素68，给出所需的比较次数。49、已知一组键值序列为(38，64，73，52，40，37，56，43)，试采用快速排序法对该组序列作升序排序，并给出每一趟的排序结果。50、已知某二叉树的顺序存储结构如图所示，试画出该二叉树。51、设有一个关键码的输入序列{  55,  31,  11,  37,  46,  73,  63,  02,  07  }  (1)从空树开始构造平衡二叉搜索树,  画出每加入一个新结点时二叉树的形态。若发生不平衡,指明需做的平衡旋转的类型及平衡旋转的结果。(2)计算该平衡二叉搜索树在等概率下的查找成功的平均查找长度和查找不成功的平均查找长度。52、求下列广义表运算的结果：1)HEAD(p,h,w);2)TAIL(b,k,p,h);3)HEAD((a,b),(c,d));4)TAIL(a,b),(c,d);5)HEAD（TAIL（（(a,b),(c,d)）））6)TAIL（HEAD((a,b),(c,d))）53、画出下列广义表的图形表示：1)D（A（）），B（e），C（a,L(b,c,d)）2)J1(J2,(J1,a,J3(J1)),J3(J1))54、完成下列要求：1）请画出下列广义表的存储结构（(((a),b)),(((),(d)),(e,f))）2）请写出下面链表表示的广义表55、一棵二叉树如图：1)写出对此树进行中序、先序、后续遍历时得到的结点序列。2)画出树的后序线索二叉树。56、将下列森林转化为二叉树。57、已知一个图如下所示，写出其临接矩阵，并从顶点a出发按深度优先搜索、按广度优先搜索，则可以得到所有顶点序列为什么？58、试问在直接插入排序、希尔排序、快速排序、归并排序、二分法排序、直接选择排序中，哪些排序是稳定的？哪些是不稳定的，哪个排序平均比较次数最少？哪个排序要求内存容量最多？59、哈希表中使用哈希函数H（key）=3*key%11,并采用开放定址法处理冲突，随机探测再散列的下一地址公式为：d1=H(key)di=(di-1+7*key)%11（I=2,3…..）试在0到10的散列地址空间中对关键字序列（22，41，53，46，30，13，01，67）画出Hash表示意图，并求在等概率情况下查找成功的平均查找长度。60、什么是内部排序？什么是排序方法的稳定性？说出你所学过的三个稳定算法，一个不稳定算法。61、何为队列上溢？一般用什么方法解决，简述之。62、载入下图所示的有权图G，回答下列问题：1）给出从结点v1出发按深度优先搜索遍历图所得的结点序列；2）给出图的拓扑序列；3）给出从结点v1到结点v8的最短路径和关键路径。63、对于下图，请给出1）对应的邻接矩阵，并给出A,B,C三个顶点的入度和出度；2）邻接表表示和逆邻接表表示；3）求其连同分量；64、对于下图的树，分别用孩子链表和孩子兄弟链表法画出存储结构。65、对于下图的树，请分别用中序、先序的方法写出其遍历结果。66、已知一个表{jan,feb,mar,apr,may,june,july,aug,sep}1)使按表中元素的次序依次插入一棵初始为空的二叉排序树，画出表中元素构成的二叉排序树。2)求初等概率情况下查找july的查找长度。67、数组a[1..10,-2..6,2..8]以行优先的顺序存储，设第一个元素的首地址为100，每个元素占3个存储长度的存储空间，则元素A[5,1,8]的存储地址为多少？68、设有一组关键字（17，13，153，29，35，21）需插入到表长为12的表中，请回答下列问题：1）自己设计一个合理的散列函数2）用自己设计的函数将上述关键字插入到散列表中，画出其结构；并指出用线性探测法解决冲突构造散列表的装填因子为多少？71、请画出下列二叉树的中序线索化前趋链树，后序线索化后继链树。72、将下列结点按输入顺序构造一棵二叉平衡树。{As，Bx，Ca，Dww，Ae，Cf，Edd，Fap，Goi，Fab，Hre}73、试在如图所示线索化的二叉树中，查找指定结点E的后继结点、C的前驱结点，并说明找到结果的原因。74、什么是数据结构？75、试比较线性表的顺序存储结构和链式存储结构的优缺点。76、有一组关键字{14，15，30，28，5，10}，分别画出冒泡排序、快速排序过程的图示。77、具有3个节点的树和具有3个节点的二叉树它们的所有不同形态有哪些？78、内存中一片连续空间（不妨假设地址从1到m），提供给两个栈S1和S2使用，怎样分配这部分存储空间，使得对任一个栈，仅当这部分空间全满时才发生上溢。79、给出数组intA[3…8，2…6]；当它在内存中按行存放和按列存放时，分别写出数组元素A[i,j]的地址计算公式（设每个元素占两个存储单元）。80、已知一组键值序列为(38，64，73，52，40，37，56，43)，试采用快速排序法对该组序列作升序排序，并给出每一趟的排序结果。81、如图所示的二叉树完成中序遍历、后续遍历、先序遍历，并画出后序线索化的二叉树。82、将下图转换为二叉树，对转换后的二叉树进行先根、中根、后根遍历。83、有一组数值14、21、32、15、28，画出哈夫曼树的生成过程及最后结果。84、有n个顶点的有向连通图最多有多少条边?最少有多少条边？85、对关键字序列（72，87，61，23，94，16，5，58）进行堆排序、快速排序、直接选择排序，使之关键字递增有序，请写出每个排序的前三趟结果。86、已知图G={V,E}V={a,b,c,d,e}E={(a,b),(b,d),(c,d),(d,e),(e,a),(a,c)}画出图G，画出图G的邻接表。87、设一个有向图为G=(V,E),其中V={v1,v2,v3,v4}，E={<v2,v1>,<v2,v3>,<v4,v1>,<v1,v4>,<v4,v2>},画出该有向图，并求出每个结点的入度和出度，画出相应的邻接矩阵、邻接表和逆邻接表。88、请给出下图的邻接矩阵和邻接表。89、请画出下图中的极大连通子图。90、对于如下图请画出其用prim和kruskal两种不同算法生成最小生成树的各条边的并入顺序。画出最小生成树。并写出广度优先和深度优先的结点遍历顺序。91、什么是静态查找，什么是动态查找，什么叫平均查找长度。92、用序列（46，88，45，39，70，58，101，10，66，34）建立一个二叉排序树，画出该树，并求在等概率情况下查找成功的平均查找长度。93、已知一个线性表（38，25，74，63，52，48），假定采用h(k)=k%7计算散列地址进行散列存储，若引用线性探测的开放地址法解决冲突，则在该散列表上进行检索的平均检索长度为多少，若利用连地址法处理冲突，则在该散列表上进行检索的平均查找长度为多少？设地址空间为9。请画出算列表。94、已知长度为12的表：（Jan,Fed,Mar,Apr,May,Jun,Aug,Sep,Oct,Nov,Dec）按表中元素的顺序，依次插入一棵初始为空的二叉排序树，画出插完之后的二叉排序树，并求其在等概率情况下，查找成功的平均查找长度。95、有散列函数为h(k)=k%11,如果用二次探测在散列的方式解决冲突，49应放入哪？01234567891011121396、用增量序列{8、4、2、1}对下列关键字进行希尔排序，用图表示排序过程。{56、37、59、41、98、47、94、50、63、52、42、54、60、72、86、90}五、程序题四、程序题1、已知二叉树用下面的顺序结构存储，写出中序遍历该二叉树的算法。 left data right2、下列算法为删除单链表中值为X的算法，将程序填完整  voiddel(structnode*head) {q=head;p=q->next;while(()&&()){q=p;_________;}if(p==null)printf(“error”);else{______________;free(p);printf(“success!”);}}3、以下函数中，h是带头结点的双向循环链表的头指针，（1）写出下列程序的功能。（2）当链表中结点数分别为1和6（不包括头结点）时，请写出程序中while循环体的执行次数。Intfox(structnode*h){structnodep,q;intj=1;p=h->next;q=h->prior;while(p!=q&&p->prior!=q){if(p->data==q->data){p=p->next;q=q->prior;j++;}elsej=0;}return(j);}4、写出按后序序列遍历中序线索树的算法.5、写出计算树深度的算法。6、写出计算树叶子结点的算法。7、写出计算字符串长度的算法。8、试写出以带头结点单链表为存储结构实现简单选择排序的算法9、阅读下列算法，并回答下列问题：（1）该算法完成什么功能？（2）算法中R[n+1]的作用是什么？voidsort(elemtyper[],intn){intk,i;for(k=n-1;k>=1;k--)if(r[k]>r[k+1]){r[n+1]=r[k];for(i=k+1;r[i]<r[n+1];i++)r[i-1]=r[i];r[i-1]=r[n+1];}}10、试编写一算法，以完成在带头结点单链表L中第i个位置前插入元素X的操作。11.二叉树是由所有度数不大于2的结点构成的一种特定树，若某结点度为2，则该结点有左右两个孩子，请编写算法计算一二叉树所有度数为2的结点个数。12、试设计一个算法在中序线索化的树中，求指定结点P在后序遍历序列中的前驱结点，要求用非递归算法。13、若X和Y是两个单链表存储的串，设计一个算法，找出X中第一个不在Y中出现的字符。14、试设计一个算法在中序线索化的树中，求指定结点P在后序遍历序列中的前驱结点，要求用非递归算法。15、设计一个算法，删去串中第I个字符开始的J个字符，说明算法所用的存储结构，并估计算法的执行时间。16、设有单链表中存放着N个字符，试设计算法判断字符串是否中心对称关系，例如：XYZZYX，XYZYX都算是中心对称的字符串。要求用尽可能少的时间完成判断(提示：将一半字符先依次进栈)。提示:我们设H为指向链表头结点的指针,单链表每个结点包括两个域:分别是date,next分别代表数据域和指针域,s为定义的栈。17、设计一个算法将任意输入的N个数，按输入的顺序(或逆序)链接成一个单链表。18、试设计一个算法，求单链表中数据值为X0的元素的地址。19、试编一个程序，将两个字符串s1和s2进行比较，若s1>s2则输出一个正数；若s1=s2，则输出0；若s1<s2，则输出一个负数。不能用strcmp函数。20、写出在中序线索二叉树中结点*p的右子树中插入一个结点*s的算法。21、给定一棵用链表表示的二叉树，其根指针为t，试写出从根开始，按层次遍历二叉树的算法，同层的节点按从左到有的次序访问。22、完成在二叉排序树中查找结点的程序Bitreptr*bstsearch(t,k)Bitreptr*k;Keytypek;{if(t==null)returnnull;elsewhile(t!=null){if(t->key==k)_________;if(t->key>k)______________;else____________________;}}23、编写一个算法交换单链表中P所指向的位置和其后续位置上的两个结点，HEAD指向该链表的表头，P指向该链表中的某一结点。24、已知两个链表A和B，其元素值递增排列。写出编程将A和B合并成一个递减有序（相同值只保留一个）的链表C的思想，并要求利用原表结点。（*）25、下列算法完成在一个带头单链表中第i个结点前插入一个结点算法，请将空余处填上。Voidinserti(structnode*head){p=head->next;k=0;while(p!=null)&&(k<_______){________;k++;}ifp!=null{printf(“pleaseinputtox”);scanf(“%d”,&x);q=(structnode*)malloc(sizeof(structnode));q->data=x;_________;_________;}elseprintf(“notfoundithnode”);}26、写出下列算法的功能：voidweizhi(structnode*head){p=head->next；head->next=null;while(p!=null){q=p->next;p->next=head->next;head->next=p;p=q;}}27、建立一个带头结点、有10个结点的单链表，请将下列算法填完整。voidcreat(){structnode*head,*p,*s;inti,x;head=(structnode*)malloc(sizeof(structnode));head->next=null;p=head;for(i=1;i<=10;i++){s=(structnode*)malloc(sizeof(structnode));printf(“请输入数据值”)；scanf(“%d”,&x);s->data=x;s->next=p->next;_______;_______;}}28、试编写一个求指定结点在二叉排序树中的层数。29、对于一个有序表，请设计一个算法使得其插入一个结点后仍为有序表，并将其逆序输出。30、用直接插入排序的方法，将一个无序的链表排列成一个按降序排列的有序链表。31、试设计一个多项式相加的算法。32、试设计一个求在表中，相同元素出现最多值的算法。33、有一个带头结点的单链表，写出在值为x结点前插入m个结点的算法。（假设x存在，m个结点由键盘输入）。34、将下列程序填完整，并输出程序的功能：voidsearchbinary(elemtypea[],intn,intk){intlow=0,high=n-1,mid,find=0;while(find==0)&&(low<=high){mid=______________;if(k==a[mid]){find=1;printf(“findk!”);}else{if(k<a[mid])high=mid-1;else_____________;}}if(find==0)printf(“notfindk!”);}35、分析下列算法，说出算法的功能：voidinsstr(charstring1,charstring2,inti){intn,m,j;n=strlen(string1);m=strlen(string2);if(i<0||i>n–1)printf(“error!”);else{for(j=n;j>=i-1;j--)string1[j+m]=string1[j];for(j=0,j<m,j++)string1[i+j-1]=string2[j];}}36、下列算法实现了在主串从第i个位置起删除长为j的子串，请将程序填完整。voiddelstr(charstring,inti,intj){if(i>strlen(string))printf(“error!”);else{k=i-1;while(string[k+j]!=‘\o’){____________;k++;}string[k]=‘\0’;}}37、说出下列程序段完成了什么功能？Voiddelete(inta[n],inti){if(i<0)||(i>=n)printf(“error”);else{for(j=i-1;j<n;j--)a[j]=a[j+1];n=n-1;}}38、在有头结点head单链表p指针结点后插入值为x的结点，请将下列算法填完整；voidinsert(structnode*head,elemtypex){structnode*s,*p*q;q=head->next;while(q!=p)q=q->next;ifq==nullprintf(“notfind”);else{s=(structnode*)malloc(sizeof(structnode));s->data=x;_______________；_______________；}}39、说出下列算发的功能：voidweizhi(linkqueue*q){structqueuenode*p;ifq.front==q.rearprintf(“thequeueisempty”);else{p=q->front->next;q->front->next=p->nextreturn(p->data);free(p);}}40、编写一个交换单链表中p指针所指结点和其后这两个结点的算法。41、写出在二叉排序树中插入一指定结点一个结点的算法。42、完成计算二叉树叶子结点的算法。voidmidtravel(structtreenode*bt){structtreenode*p,*a[n];inttop=-1,true=1,j=0;while(true){p=bt;while(p!=null){top++;a[top]=p;p=________}if(top!=-1){p=a[top];top--;printf(“%c”,p->data);if(p->left==null)&&________________________;p=p->right;}elsetrue=0;}printf(“%d”,j)}43、完成二叉树按层遍历的算法。voidleveltravel(structtreenode*bt){structtreenode*p,*a[n];intrear=front=-1;p=bt;rear=__________;a[rear]=p;while(rear!=front){front=___________;p=a[front];printf(“%c”,p->data);if(p->left!=null){rear=(rear+1)%na[rear]=_________;}if(p->right!=null){rear=(rear+1)%n;a[rear]=_________;}}}44、给定一棵用链表表示的二叉树，其根指针为t，试写出从根开始，按层次遍历二叉树的算法，同层的节点按从左到有的次序访问。45、写出在中序线索二叉树中结点*p的右子树中插入一个结点*s的算法。46、试设计一个算法在中序线索化的树中，求指定结点P的前驱结点，要求用非递归算法。47、完成下列程序,并说出该算法所完成的功能。voidweizhisort(structnoder[n],intn){intlow,high,mid,j,i;for(i=2;i<=n;i++){r[0]=r[i];low=__________;high=_________;while(low<=high){mid=(low+high)/2;if(r[0].key<r[mid].key)_______________;elselow=mid+1;}for(j=i-1;j>=l;j--)r[j+1]=r[j];r[low]=r[0];}}48、完成程序，并说出程序的功能Bitreptr*bstsearch(t,k)Bitreptr*k;Keytypek;{if(t==null)returnnull;elsewhile(t!=null){if(t->key==k)_________;if(t->key>k)______________;else____________________;}}49、完成下列程序，并说出该算法的功能。voidweizhitravel(structtreenode*bt){structtreenode*p,*a[n];inttrue=1,top=-1;while(true){while(p!=null)//只要p不空全部压栈//{printf(“%c”,p->data);______________;a[top]=p;_________;}if(top!=-1){p=a[top];p=p->right;top--;}elsetrue=0;}}完成的功能：___________________50、写出在二叉排序树中查找值为x的算法。51、试写出以带头结点单链表为存储结构实现简单选择排序的算法。52、阅读下列算法，并回答下列问题：该算法完成什么功能？算法中R[n+1]的作用是什么？voidsort(elemtyper[],intn){intk,i;for(k=n-1;k>=1;k--)if(r[k]>r[k+1]){r[n+1]=r[k];for(i=k+1;r[i]<r[n+1];i++)r[i-1]=r[i];r[i-1]=r[n+1];}}53、说出下列算法的运行结果:structnode{elemtypedata;structnode*next;}voidweizhi(structnode*head,structnode*q){structnode*p,*r;p=head->nextwhile(p->next!=q)&&(p->next!=null)p=p->next;if(p->next!=null){r=p->next;q->next=r;p->next=r->next;r->next=p;}}算法完成的结果是:_______________________54、设编写一计算字符串长度的算法。55、写一算法将一单链表逆置。要求操作在原链表上进行。56、编写算法在一个非减有序线性表中，插入一个值x的元素，使插入的线性表仍为非减有序表。WelcomeToDownload!!!欢迎您的下载，资料仅供参考！�EMBEDWord.Picture.8���02 3 35AAACBDEF�EMBEDPBrush���FEDCBA�EMBEDPBrush����EMBEDPBrush����EMBEDPBrush����EMBEDPBrush����EMBEDPBrush����EMBEDPBrush����EMBEDPBrush����EMBEDPBrush���AaAAAAABCDEFGHBCDEFGHACBDEFABCDEFGJabedcf14563214325612123310657842015386184�EMBEDPBrush���qsyvvccvcccpheadPAGE精品资料_1181453174.doc�EMBEDEquation.3���CBA_1086942774.unknown_1065590370.unknown_1031224588.unknown