数据结构填空题

一、填空题数据结构的存储结构包括顺序、(链接)、索引和散列等四种。设关键字序列｛7,12,26,30,47,58,66,70,82,90｝,当用折半查找方法查找时,所需比较的次数为3次的关键字分别是(7265882)。假定一个线性表为｛12,23,74,55,63,40,82,36｝，若按key%3条件进行划分,使得同一余数的元素成为一个子表,则包含74的子表长度为(2)。和折半查找相比,顺序查找的优点是除了不要求表中数据元素有序之外,对(存储)结构也无特殊要求。设双向循环链表每个结点结构为(data,llink,rlink),则结点*p的前驱结点的地址为(p->llink)。n个顶点的连通无向图的生成树含有(n-1)条边。在一个最大堆中,堆顶结点的值是所有结点中的(最大值)。假定对长度n=50的有序表进行折半查找，则对应的判定树中最底下一层的结点数为(19)个。对于带头结点的链栈top,取栈顶元素的操作是(*y=top->next->data)。假定一棵二叉树的结点个数为50,则它的最小高度为(5)。假定树根结点的深度为0。二维数组是一种非线性结构,其中的每一个数组元素最多有(2)个直接前驱(或直接后继)。在堆排序中,对任意一个分支结点进行调整运算的时间复杂度为(O(log2n))。队列的删除操作在(队头(或队首))进行。设图G=(V,E),V={1,2,3,4},E={<1,2>,<1,3>,〈2,4>,〈3,4>},从顶点1出发，对图G进行广度优先搜索的序列有(2)种。向一棵二叉排序树中插入一个元素时,若元素的值小于根结点的值,则应把它插入到根结点的(左子树)上。快速排序在平均情况下的时间复杂度为(O(nlog2n))。由关键字序列{42,97,75,23,68,34}建成的最大堆是(97,68,75,23,42,34)。对于关键字序列(12,13,11,18,60,15,7,18,25,100)进行初始建堆,必须从关键字为(60)的结点开始。从有序表(12,18,30,43,56,78,82,95)中折半查找元素56时,其查找长度为(3)。设有二叉树根结点的层次为0,一棵高度为h的满二叉树中的叶子结点个数是(2h)。在一个最小堆中,堆顶结点的值是所有结点中的(最小值)。在长度为n的顺序表中删除一个元素时，等概率情况下的平均移动元素的次数是((n-1)/2)。由关键字序列（57,24,76,63,18,31,15）生成的一棵二叉排序树,其等查找概率情况下查找成功的平均查找长度为（18/7）数据结构包括逻辑结构、（存储结构）和数据的运算三个方面。在一棵m阶B树上，每个非根结点的关键字数最多为（m-1）个。在双向链表中,每个结点除了数据域外,还有两个指针域,它们分别指向（前趋结点和后继结点）。一般来说，深度优先生成树的高度比广度优先生成树的高度要（高）。递归工作栈起到两个作用，其一是将递归调用时的实际参数和返回地址传递给下一层递归;其二是保存本层的形式参数和（局部变量）。在一个堆的顺序存储中,若一个元素的下标为i（OWiWn-1），则它的右子女元素的下标为（2i+2）。数据结构的逻辑结构包括线性结构和（非线性）结构两大类。队列是具有（先进先出）特性的线性表。基本数据类型是计算机已经实现了的（数据结构）。n个顶点且含有环路的无向连通图中，至少含有（n）条边。若设L是指向带表头的单链表，语句L->link=L->link->link的作用是（删除）单链表中的第一个结点。已知8个数据元素为(34,76,45,18,26,54,92,65),按照依次插入结点的方法生成一棵二叉排序树后,最后两层上的结点总数为(2)。大小为M的顺序存储的循环队列sq队满的条件为((sq.rear+l)%M==sq.front)。若设顺序栈的最大容量为MaxSize,top==-l表示栈空，则判断栈满的条件是(top==MaxSize-1)。假定一个顺序表的长度为40,并假定顺序查找每个元素的概率都相同,则在查找成功情况下的平均搜索长度为(20.5)。设有程序段为for(i=1;i<10;i++)for(j=1;j<=i;j++){p=i*j;printf(“%4d\n”,p);}则执行p=i*j的次数为(45)。一棵高度为5的完全二叉树中,最多包含有(63)个结点。假定树根结点的高度为0。第i(i=1,2,…，n-1)趟从参加排序的序列中取出第i个元素，把它插入到由第0个至第i-1个元素组成的有序表中适当的位置，此种排序方法叫做(直接插入)排序。设栈S和队列Q的初始状态为空，元素A,B,C,D,E,和F依次通过栈S,且一个元素出栈后即进入队列Q,若6个元素出队列的顺序是B,D,C,F,E,A,则栈S的容量至少是(3)。45.在对m阶B树插入元素的过程中，每向一个结点插入一个关键字后,若该结点的关键字个数等于(m)个,则必须把它分裂为2个结点。栈是一种限定在表的一端进行插入和删除的线性表,又被称为(后出先进)表。在无向图G的邻接矩阵表示中，第j列中非零元的个数等于该顶点的(度)。在一个链式队列中,若队头指针与队尾指针的值相同,则表示该队列至多有(1)个结点。假定一棵二叉树的结点数为18,则它的最小高度为(4)。假定树根结点的高度为0。在单链表中,除了表头结点外,任意结点的存储位置由其直接(前驱)结点的指针域的值所指示。由分别带权为9,6,2,5,7的五个叶子结点构造的哈夫曼树的带权路径长度为(65)。对长度为20的有序表进行二分查找的判定树的高度为(5)。快速排序在平均情况下的空间复杂度为(O(log2n))。队列是一种限定在表的一端插入,在另一端删除的线性表,它又被称为(先进先出)表。当用长度为MaxSize的数组顺序存储一个栈时，若用top==MaxSize表示栈空，则表示栈满的条件为(top==0)。若进栈序列为a,b,c，且进栈和出栈可以穿插进行，则可能出现(5)个不同的出栈序列。若设一个n的矩阵A的开始存储地址LOC(0,0)及元素所占存储单元数d已知，按行存储时其任意一个矩阵元素a[i][j]的存储地址为(L0C(0,0)+(i*n+j)*d)。如果n个顶点的图是一个环，则它有(n)棵生成树。设有程序段为:for(i=1;i<=10;i++)for(j=1;j<=i;j++)p=i*j;则执行p=i*j的次数为(45)。在单链表中某P结点后插入S结点的操作是(s->next二p->next;p->next=s;)。以顺序查找方法从长度为n的顺序表或单链表中查找一个元素的渐进时间复杂度为(O(n))。在直接选择排序中，记录比较次数的时间复杂度为(O(n2))。栈下溢是指在(栈空)时进行出栈操作。在单链表设置表头结点的作用是插入和删除表中第一个元素时不必对（表头指针）进行特殊处理。一维数组所占用的空间是连续的。但数组元素不一定顺序存取,通常是按元素的（下标（或顺序号））存取的。利用三元组表存放稀疏矩阵中的非零元素,则在三元组表中每个三元组元素对应一个非零元素的行号、列号和（值）。克鲁斯卡尔算法适用于求（边稀疏）的网的最小生成树。用链表表示线性表,表中元素之间的逻辑关系是通过链表中结点的（指针）来实现的。将一棵树按照左孩子-右兄弟表示法转换成对应的二叉树,则该二叉树中树根结点肯定没有（右）孩子。由带权为9,6,2,5,7的五个叶子结点构造的哈夫曼树,其根结点的权值为（29）。11个顶点的连通网络N有10条边，其中权值为1,2,3,4,5的边各2条,则网络N的最小生成树各边的权值之和（30）线性表是由n（n±0）个（数据元素）组成的有限序列。给定一组数据元素的关键字为{46,79,56,38,40,84},对其进行一趟快速排序处理,得到的右子表中有（3）个元素。将一个n阶对称矩阵的上三角部分或下三角部分压缩存放于一个一维数组中，则一维数组需要存储（n（n+1）/2）个矩阵元素。对于一棵具有n个结点的树，该树中所有结点的度数之和为(n-1)。在使用Kruskal算法构造连通网络的最小生成树时，只有当一条候选边的两个端点不在同一个(连通量)上，才会被加入到生成树中。设序列｛25，36，40，45，48，56，60，68，72，85｝，当用折半查找方法查找36时，所需比较的次数为(2)。哈希查找是通过(哈希函数)来确定记录的存储地址的。对n个数据对象进行堆排序，总的时间复杂度为(O(nlog2n))。在线性表的散列存储中，装载因子又称为装载系数，若用m表示散列表的长度,n表示待散列存储的元素的个数，则等于(n/m)。设图的顶点数为n,则求解最短路径的Dijkstra算法的时间复杂度为(O(n2))。已知一棵3阶B树中含有50个关键字,则该树的最大高度为(5)。从一棵二叉排序树中查找一个元素时，若给定值大于根结点的值，则需要向(右子树)继续查找。链接存储表示的结点存储空间一般在程序的运行过程中进行动态地(分配)和释放。线性表的链接存储只能通过(链接指针)顺序访问。直接插入排序在初始有序时，进行(n-1)次关键字比较。每次直接或通过基准元素间接比较两个元素,若出现逆序排列就交换它们的位置,这种排序方法叫做（交换）排序。单链表中逻辑上相邻的结点而在物理位置上（不一定）相邻。链表只适用于（顺序）查找。在堆排序中，如果n个对象的初始堆已经建好，那么到排序结束，还需要从堆顶结点出发调用（n-1）次调整算法。向一个顺序栈插入一个元素时，首先使（栈顶指针）后移一个位置，然后把待插入元素写入到这个位置上。在带表头结点的单链表中删除某一指定结点，必须找到该结点的（前一个）结点。在一棵高度为3的四叉树中，最多含有（85）个结点，假定树根结点的高度为0。在含有3个结点a,b,c的二叉树中，前根序列为abc且后根序列为cba的二叉树有（4）棵。设图G=（V,E）,V={VO,VI,V2,V3},E={（VO,VI）,（VO,V2）,（VO,V3）,（V1,V3）}，则从顶点VO开始的图G的不同深度优先序列有（4）种。在一般情况下用直接插入排序、选择排序和冒泡排序的过程中,所需记录交换次数最少的是（选择排序）。在链表的结点中,数据元素所占的存储量和整个结点所占的存储量之比称作（存储密度）°1OO.用邻接矩阵存储图，占用的存储空间与图中的（顶点）数有关。对称矩阵的行数与列数(相等)且以主对角线为对称轴,aij=aji,因此只存储它的上三角部分或下三角部分即可。在直接选择排序中,记录移动次数的时间复杂度为(O(n))。对关键字序列(15,18,11,13,19,16,12,17,10,8)进行增量为5的一趟希尔排序的结果为((15,12,11,10,8,16,18,17,13,19))。已知完全二叉树有200个结点,则整个二叉树有(1)个度为1的结点。普里姆算法适用于求(边稠密)的网的最小生成树。在一个堆的顺序存储中,若一个元素的下标为i(OWiWn-1),则它的左孩子元素的下标为(2i+1)。若用邻接矩阵表示有向图,则顶点i的入度等于矩阵中(所对应列中的非零元素个数)o108.链队列lq为空的条件为(Lq->rear==lq.front)。109.长度为11的有序表进行折半查找时,在等查找概率情况下查找成功的平均查找长度为(3)o110.第i(i=0,1,...,n-2)趟从参加排序的序列中第i个至第n-1个元素中挑选出一个最小元素,把它交换到第i个位置，此种排序方法叫做(直接选择)排序。快速排序在最坏情况下的时间复杂度为(O(n2))。由关键字序列｛36,96,84,18,52,27｝建成的最小堆是((18,36,27,96,52,84))。深度为10的完全二叉树,至少有(512)个结点。在一棵二叉树中,假定双分支结点数为5个,单分支结点数为6个,则叶子结点数为(6)个。向一个栈顶指针为top的链式栈中插入一个新结点*p时,应执行(p->next二top)和top=p操作。假设用<x,y>表示树的边(其中x是y的双亲)，已知一棵树的边集为{<b,d>,<a,b>,<c,g>,<c,f>,<c,h>,<a,c>},该树的度是(3)。设待排序的表为(42,55,12,47,94,06,18,63),利用快速排序方法对其进行排序,经第一趟排序后,表的状态为((18,06,12,42,94,47,55,63))。估算算法时间复杂度时考虑的问题规模通常是指算法求解问题的(输入量)。在一棵三叉树中,度为3的结点数有2个,度为2的结点数有1个,度为1的结点数为2个,那么度为0的结点数有(6)个。n(n>0)个顶点的连通无向图各顶点的度之和最少为(2(n-1))。对n个元素的序列进行冒泡排序时，(初始数据有序)情况下比较次数最少，比较次数为(n-1)。已知一棵3阶B树中含有50个关键字,则该树的最小高度为(4)。仅允许在表的同一端进行插入和删除运算的线性表被称为(栈)。链表与顺序表、索引表、散列表等都是数据逻辑结构的(存储)表示。如果一个对象部分地包含自己,或自己定义自己,则称这个对象是(递归)的对象。127.在有向图的邻接表表示中,每个顶点邻接表中所含的结点数等于该顶点的（出度）。128.给定一组数据对象的关键码为{46,79,56,38,40,84},则利用堆排序方法建立的初始堆（最大堆）为（{84,79,56,38,40,46}）。设关键字序列（17,8,13,25,24,16,3,19,1）,用希尔排序法按升序排序,用初始增量4进行一趟排序后的结果是（1,8,3,19,17,16,13,25,24）。设循环队列用数组A[m]表示，队头、队尾指针分别是front和rear,则判定队满的条件为（（rear+1）%M==front）。求解带权连通图最小生成树的Prim算法使用图的（邻接矩阵）作为存储结构。在堆排序中，对n个记录建立初始堆需要调用（n/2）次调整算法。已知一棵二叉树的先根序列为ABDFCE,中根序列为DFBACE,则后根序列为（FDBECA）。用折半查找法查找一个线性表中的元素时,此线性表必须是（有序的）。在有向图的邻接矩阵表示中，第j列元素之和等于第j个顶点的（入度）。在链表中进行插入和（删除）操作的效率比在顺序存储结构中进行相同操作的效率高。137.算法的一个特性是（有穷性）