《数据结构》试题库中的习题

《数据结构》试题库中的习题一、填空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、编写在内存中生成线性表（a1a2a3…an）的算法。(判断表是否满了)67、已知线性表（a1a2a3…an）以顺序的方式存储在内存，编写在表中查找值为X的元素，若存在把它与其直接前驱元素交换，否则把X插到表尾的算法。并计算该算法的时间复杂性.（如果是a1就不交换）（可用while语句做）68、编写把线性表（a1a2a3…an）的顺序完全倒置的算法。并计算该算法的时间复杂性及决定时间复杂性的语句频度。(对称交换)69编写把从线性表（a1a2a3…an）中值为X的元素开始到的所有元素顺序倒置的算法。70、线性表的链式存储C语言是用语句实现空间单元动态分配。71、设一线性表的顺序存储，总存储容量为M，其指针的变化范围为——。(0~M-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[-12，-23]，按顺序存储，基址为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，每个元素占三个存储单元，试计算元素A[6，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个结点