数据结构导论填空题目汇总.docx

《数据结构导论填空题目汇总.docx》由会员分享，可在线阅读，更多相关《数据结构导论填空题目汇总.docx（12页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、20040116以下程序段的时间简单性量级是 0(n*i)ofor (i=l;in; i+)for (j=l; j top + sq - datasq - top=x19链队列实际上是一个同时带有头指针和尾指针的单链表，尾指针指向该单链表的队尾结点 O20设有k个结点在用哈夫曼算法构造哈夫曼树的过程中假设第i次合并时已找到权最小的结点 x和权次小的结点v用Tx.wt表示结点x的权值Tx.wt=m, Ty.wt=n那么合并成新的二叉 树后给新根结点的权值赋值的语句为 m+n o21在以下树中结点H的祖先为 F o22顶点数为n、边数为n(n-l)/2的无向图称为无向完全图。任何两点之间都有的边的

2、无向图称为无向完全图；边数(n(n-l)/2)任何两点之间都有弧的有向图称为有向完全图；弧数(n*(n-l)23动态查找表在开散列表上通常采纳线性探测法和链地址法 来解决冲突问题。24对于有10个元素的有序表采纳二分查找需要比拟3次方可找到其对应的键值那么该元素在 有序表中的位置可能是1,3,6,9 o25查找表的规律结构与线性结构、树型结构等相比根本区分在于数据元素之间无规律关系 O27在排序方法中依次将每个纪录插入到一个有序的子序列中去即在第i(i”)遍整理时 r92,皿已经是排好挨次的子序列取出第i个元素门在已排好序的子序列里为找到一个 合适的位置并把它插到该位置上。这种排序方法被称为直

3、接插入排序 O28快速排序法在待排序数据已基本有序 的状况下最不利于发挥其特长。20041016 .从数据结构的观点，数据通常可分为三个层次，即：数据、数据元素和数据项 o18 .对挨次表执行插入操作，其插入算法的平均时间简单性为 0(n)。19 .在具有n个单元、且采纳挨次存储的循环队列中，队满时共有 n-1 个元素。20 .假设front和rear分别表示循环队列Q的头指针和尾指针，m0表示该队列的最大容量，那么 循环队列为空的条件是Q front二二Q rear。18 .从一个长度为n的挨次表中删除第i个元素(iWign)时，需向前移动n-i一个元素。19 .在单链表中，插入一个新结点需

4、修改_2 个指针。20 .在队列结构中，允许插入的一端称为队尾 o.稀疏矩阵采纳的压缩存储方法是三元组表o21 .向一个栈顶指针为top的链栈中插入一个新结点*p时,应执行p-next=t叩和 top=p 操作。22 .有m个叶结点的哈夫曼树所具有的结点数为_2m-l。23 .在一棵具有n个结点的完全二叉树中，从树根起，自上而下、自左至右地给全部结点编 号。设根结点编号为lo假设编号为i的结点有右孩子，那么其右孩子的编号为2i+lo.在一棵树中，根结点没有前驱结点。24 . 一个具有n个顶点的有向完全图的弧数是_n(n-l)。25 . n个顶点的无向图G用邻接矩阵A n n存储，其中第i列的全

5、部元素之和等于顶 点V的一度 O.选择排序的平均时间简单度为_0(n的平方)o20220116 .以下程序段的时间简单度为O(log2n)oi=l; while (il)的满二叉树中共有2n次方-1 个结点。22 .在无向图中，假如从顶点v到顶点/有路径，那么称v和4是连通的 o.无向完全图G采纳 邻接矩阵 存储结构较省空间。23 .在挨次查找、二分查找、索引查找和散列查找四种查找方法中，平均查找长度与元素个数没有关系的查找方法是散列查找 o.快速排序最好状况下的时间简单度为 O(nlog2n)2022-一10.以下程序段的时间简单度为_O(n的平方)ofor(i=l;i=n;i+)for(j

6、=l;jnext=head。18 .队列又称为先进先出 的线性表。19 .挨次栈被定义为结构类型，含有两个域：data和top,那么对栈*sq进行初始化的操作是_sqtop=0 o20 .对于任何一棵二叉树T,假如其终端结点数为n0,度为2的结点数为n2,那么n2=_n0-l o21 .一棵具有n个结点的二叉树，采纳二叉链表存储，那么二叉链表中指向孩子结点的指针有 _n-1 个。22 .假设连通图G的顶点个数为n,那么图G的生成树的边数为n-1。23 .一个具有n个顶点的无向图的边数最多为n(n-l)/2。24 .中根遍历二叉排序树所得到的结点访问序列是键值的递增 序列。27眉泡排序的平均时间

7、简单度为0(n2)o.将序列60, 20, 23, 68, 94, 70, 73建成堆，那么只需把20与 60 相互交换。2022-01.数据的不行分割的最小标识单位是数据项,它通常不具有完整确定的实际意义， 或不被当作一个整体对待。16 .运算分为加工型运算和引用型运算，读取操作是引用类型运算。17 .带有头结点的单向循环链表L (L为头指针)中，指针p所指结点为尾结点的条件是_pnext=L o.在双链表中，前趋指针和后继指针分别为prior和next。假设使指针p往后移动两个结点, 那么需执行语句 *p=p-next-next。18 .元素Si，S2，S3，S4，S5，S6依次进入挨次栈

8、S,假如6个元素的退栈挨次为S2，S3, S4， S6，S5，S1，那么挨次栈的容量至少为 3_o.稀疏矩阵一般采纳的压缩存储方法是三元组表示法o19 .在一棵树中，根结点没有双亲。20 .一棵具有n个结点的完全二叉树中，从树根起，自上而下、自左至右给全部结点编号。 设根结点编号为1，假设编号为i的结点有父结点，那么其父结点的编号为_i/2 (取下整 数)o.二叉树的二叉链表存储结构中推断指针p所指结点为叶子结点的条件是 (p-lchild=null) &( p-rchild=null)。21 ,边稀疏的无向图采纳邻接表存储较省空间。22 .除第一个顶点和最终一个顶点相同外，其余顶点不重复的回

9、路，称为简洁回路o.二分查找算法的时间简单度是O(n*log2n)。23 .要将序列51, 18, 23, 68, 94, 70, 73建成堆，那么只需把18与_51 相互交换。2022-10.下面算法程序段的时间简单度为_0(n的3次方)。for (i=l; i=n; i+)for (j=l; j=n; j+)for (k=l;knext=_p-next-next。17 .在带有头结点的单链表head中首结点的指针为_head-next。18 .在栈结构中允许插入和删除的一端称为栈顶o.C程序中将对称矩阵Ann的下三角元素压缩存储到n(n+l)/2个元素的一维数组M中设 aijij存放在数组

10、Mk中那么k的值用i,j表示为_(i+l)*i/2+j。19 .具有64个结点的完全二叉树的深度为7o.某二叉树的先序遍历序列为AJKLMNO中序遍历序列为JLKANMO那么根结点A的右子树中 的结点个数为3o一011.三个顶点Vi,V2,V3的图的邻接矩阵为101那么该图中顶点V2的出度为_2 o000.除第一个顶点和最终一个顶点相同外其余顶点不重复的回路称为_简洁回路或简洁环20 .在挨次查找、二分查找、散列查找和索引挨次查找四种查找方法中平均查找长度与元素 个数没有关系的查找方法是散列查找.堆排序算法的时间简单度为_O(n*logn2(n)。21 .假如要将序列建成堆那么只需把60与18

11、 相互交换。2022-01.下面算法程序段的时间简单度为0(n2平方)ofor(i=l;i=n;i+)for(j=l;jnext=q;p=q;p-next = NULL。18,向一个长度为100的挨薇市第50个元素之前插入一个元素时,需向后移动的元素个数 为 51 o.一个带头结点的链栈LS,现将一个新结点入栈，指向该结点的指针为P，入栈操作为 p-next=LS-next 和ls-next=p。22 .队列操作的原那么更二先进先出。21,含有n个顶点的连通图中的任意一条简洁路径，其最大长度为n-1 o.在一棵度为3的树中，度为3的结点数为1个，度为2的结点数为2个，度为1的结点 数为3个，那

12、么度为0的结点数为 6 个。正确答案：C解析：设这棵树中叶子结点数为n0,度数为1的结点数为nl,度数为2的结点数为n2,度数为3的结 点数为总结点数为m那么nO-ltn2tn3(l)设树的总入度为由于在树中除了根结点外，其 余每一个结点都有唯一的一个分支进入，那么树的总结点数为n=m+l(2)又由于树中这m个进入分支分 别由非叶子结点射出，其中度数为1的结点射出L度数为2的结点射出2,度数为3的结点射出3。 而且射出分支总数与总的进入分支数相等，即2n2+3n3(3)由式(1)、(2)、(3)可以得到 nO=n2+2n3+l=l+2X 2+1=6 o.某二叉树的中序遍历序列为BACDEFGH

13、,后序遍历序列为BCAEDGHF,那么根结点F的左子 树上共有5 个结点。24,设有向图G的邻接矩阵为A,假如是图中的一条弧,那么A i j的值为1。 25.一个有序表A含有15个数据元素，且第一个元素的下标为1,按二分查找算法查找元素 A 14,所比拟的元素下标依次是_8,12,14。二分查找算法是从low=l开头的。Hgih二有序表长度1+15/2=8(814),9+15/2=12(12prior=p_t-next=p-next p-next-prior=tp-next=to18.在带有头结点的循环链表中头指针为head推断指针p所指结点为首结点的条件是p=head-next。19元素的进

14、栈次序为123n出栈的第一个元素是n那么第k个出栈的元素是n-k+1。20在栈结构中允许插入和删除的一端称为 栈顶 o21 100个结点的二叉树采纳三叉链表存储时空指针域NULL有 102 个。100个结点的二叉树用三叉链表存储共有101+ 1 = 102个空指针域1代表双亲指针，只有根没有双亲101：每个结点有两个孩子域，因此一共100*2= 100个指针域，但100个结点 中间的连接边肯定是100-1=99个，所以空的指针域有200-99=101,也就是n 个结点有n+1个空的指针域这样加上双亲域，n个结点的三叉链表共有n+2个空指针域101是二叉树的空指针域，而三叉树比二叉树每个节点多了

15、父指针。此种存储跟 节点是没有父节点的。所以二叉树的空指针域+1(跟节点父指针为空)=三叉树空 节点.某二叉树的先序遍历序列为ABKLMNO中序遍历序列为BLKANMO那么该二叉树中结点A的右孩子为结点M o一个二叉树的最少结点个数为 0 o24图中第一个顶点和最终一个顶点相同的路径称为回路。除第一个顶点和最终一个顶点相同外其余顶点不重复的回路称为简洁回路或简洁环 O25设查找表有n个数据元素那么二分查找算法的平均查找长度为(n+1)/n*log2(n+l)-l o26用键值通过散列函数猎取存储位置的这种存储方式构造的存储结构称为 散列值27假设在线性表中采纳二分查找法查找元素那么该线性表必需

16、按值有序并且采纳挨次 存储结构。28堆分为最小堆和最大堆假设键值序列k,k2,kn满意Ji(i = i,2,.J-|)那么这n个键k；2值序列kih,kJ是 最小堆(或最大堆)2022416 .数据的基本单位是数据元素 o17双向循环链表中，在p所指结点的后面插入一个新结点*3需要修改四个指针，分别为 t-prior=P； t-next=p-next； p-next-prior=t； p-next=t；。18 .在带有头结点的循环链表中，尾指针为rear,推断指针P所指结点为首结点的条件是 rear-next-next。19 .假设线性表中最常用的操作是求表长和读表元素，那么挨次表和链表这两种

17、存储方式中，较 节约时间的是一挨次表 o.不含任何数据元素的栈称为空栈 o20 .稀疏矩阵一般采纳的压缩存储方法是三元组表示法 o22.100个结点的二叉树采纳二叉链表存储时，用来指向左、右孩子结点的指针域有 99 个。23 .完全二叉树的第5层有5个结点，那么整个完全二叉树有 20 个结点。24 .n个顶点的有向图G用邻接矩阵AL.n, Ln存储，其第i列的全部元素之和等于顶点Vi的 入度 O25 .具有10个顶点的有向完全图的弧数为 90o.要完全避开散列所产生的“积累，现象，通常采纳公共溢出区解决冲突。26 .在长度为n的带有岗哨的挨次表中进行挨次查找，查找不胜利时，与关键字的比拟次数

18、为N+l_o,归并排庠算法的时间简单度是 O(NLOG2N)。21二维数组A10H20采纳按行为主序的存储方式，每个元素占4个存储单元，假设A0的存储地址为300,那么的地址为 1056 o22 .树的遍历主要有先根遍历、后根遍历和中根遍历 三种。23 .深度为k的完全二叉树至少有 2(k次方)-1 个结点。24 .假设图的邻接矩阵是一个对称矩阵，那么该图肯定是一个 无向图 o.对于具有n个元素的数据序列，采纳二叉排序树查找，其平均查找长度为log2 (n+l)-lo布完全避开散列所产生的积累现象,通常采纳公共溢出区 法。28.在最好的状况下，对于具有n个元素的有序序列，假设采纳冒泡排序，所需

19、的比拟次数为 n-1 次。200501.数据结构中的算法，通常采纳最坏时间简单度和一平均时间简单度 两种方法衡量其效率。17 .推断带头结点head的单链表为空的条件是 head-next=null。18 .假设挨次表每个元素长度均为5,其中第一个元素的存储地址为30,那么第6个元素的储地 址为 55_( 30+5*(6-1)o.假设front和rear分别表示循环队列Q的头指针和尾指针，m0表示该队列的最大容量，那么 推断循环队列为满的条件是(sq.rear+1 )%maxsize=sq.front。19 .对于挨次存储结构的二维数组，通常采纳 行序优先存储和列序优先存储 两种存放方式存储数

20、据元素。20 .假设某二叉树的先根遍历序列为CEDBA,中根遍历序列为DEBAC,那么其后根遍历序列为 DABEC o.具有n个结点的完全二叉树，其深度为log2n+1。21 .图主要采纳邻接矩阵和邻接表 两种存储结构存放。22 .索引挨次查找通常分两个阶段进行，首先采纳挨次查找法或二分法确定所要查找的块，然后再用 挨次查找 法在块中找到详细的元素值。23 .二叉排序树是一种特别的有序表，假设要保证输出序列其键值完全按递增排列，那么应对二 叉排序树采纳 中根遍历 法遍历。28 .在各种内部排序中，占用存储空间较大的排序通常是一并归 排序。200510.时间简单性描述量级中，假设某算法到达指数量

21、级，那么该算法通常是不行计算的。17 .对挨次表执行删除操作，其删除算法的平均时间简单性为(n-1 )/2 o.假设head表示循环链表的头指针，t表示尾结点，那么头指针head与尾结点t之间的关系可 表示为 t-next=head。18 .我们通常把队列中允许删除的一端称为队头 o.二维数组A 5 6采纳按列为主序的存储方式，每个元素占3个存储单元，假设A0 0的存储地址是100,那么A 4 3的存储地址是 157 0以行为主序存储的首地址=数组的在内存中的基地址+ i *列数*每个元素占单元数+ j *每 个元素占单元数假设二维数组ALLULL2.U2以列为主序存储，每个元素占用d个存储单

22、元，那么元素Aij 的存储位置相对于数组空间首地址的偏移量为(J-L2)x(Ul-LI+l)+I-Ll)xd19 .树在数据结构中常采纳孩子链表表示法、孩子兄弟链表和双亲表示法三种存 储结构表示。20 .假设某二叉树中度为1的结点数为4,度为2的结点数为6,那么该树叶子结点数为 7.对于n个顶点的生成树，其边的个数为_n-1。21 .对于具有n个元素的数据序列，假设采纳二分查找法，当n的值较大时其平均查找长度为 一log2 (n+l) -1 o.解决散列所引起冲突的方案中，建立公共溢出区 法是介于开散列表与闭散列表之间的一种方法。28.排序通常可分为内部排序和外部排序，其中内部排序是指排序的整

23、个过程中，数据全部存放在计算机的内存 中。200601.数据表示和 数据处理 是程序设计者所要考虑的两项基本任务。16 .一个算法通常可从正确性、易读性、健壮性和时空性 等四个方面评价、分析。17 .对长度为n的挨次表执行删除操作，其删除算法在最坏状况下的时间简单性为 0(n).我们通常把队列中允许插入的一端称为 队尾。20 .二维数组在机器级的详细实现，通常均采纳 挨次和二叉链表 存储结构。21 .深度为k的满二叉树其叶子结点个数共有 2(k次方).1 个。22 .二叉树通常采纳挨次储存结构和链式储存结构 两种存储结构表示。23 .假设一个完全无向图具有n条边，那么该图的顶点个数为 o.查找

24、表的规律组织结构实际上是 集合 结构。24 .对于具有n个元素的数据序列，采纳挨次查找法，其平均查找长度为 (n+l)/2 o28.对于具有n个元素的有序序列，假设采纳冒泡排序，最多需要进行 n-1 趟起泡。2006-一10.在数据结构中，数据的规律结构分为集合、_线性结构、树形结构和图状结构等 四类。16 .通常从正确性、易读性、健壮性 和时空性等4个方面评价算法(包括程序)的质量。18,挨次表的存储密度为1,而链表的存储密度为小于1 o.对于栈只能在栈顶插入和删除元素。19 .在循环队列中，存储空间为0n-l,设队头指针front指向队头元素前一个空闲元素，队 尾指针指向队尾元素，那么队满

25、标志为front=（rear+l）%n,队空标志为front= rear.三个结点可构成_5 种不同形态的二叉树。共有5种，如以下图所示.对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为2n个，其中n-1 个用于链接孩子结点。（n+1个空闲节点）.有向图G用邻接矩阵A ln, ln存储，其第i列的全部元素之和等于顶点W的度O.对二叉排序树进行中序一遍历，可得到排好序的递增结点序列。20 .采纳折半查找方法进行查找的数据序列应为有序表 且挨次存储结构 o.在插入和选择排序中，假设初始数据基本正序，那么选用插入;假设初始数据基本反 序，那么选用选择 o基本正序时用插入排

26、序，由于这时的关键字比拟次数和纪录移动次数都很少基本反序用选择排序，此时两者的关键字比拟次数差不多，选择排序的纪录移动27 .快速排序最好状况下的时间简单度为_O（nlog2n次方）,最坏状况下的时间简单度 为_0（n2平方）o20070116 .在数据结构中，各个结点按规律关系相互缠绕，任意两个结点可以邻接的结构称为 图结构一O.每个存储结点只含一个数据元素，全部存储结点连续存放。此外增设一个索引表，索引 表中的索引指示各存储结点的存储位置或位置区间端点。按这种方式组织起来的存储结 构称为索引存储方式O17 .在挨次表上读表元算法的时间简单度为_0（n）o.双链表中前驱指针为prior,后继

27、指针为next,在指针P所指结点前插入指针S所指的 结点，需执行以下语句：Snext=P;Sprior=Pprior;Pprior=S;.设数组A 0.8 0.8的起始元素位置为a,每个元素占2 L个存储单元，按行序为 主序存储。假设元素A i j的存储位置为a+66L,那么元素A j i的存储位置为_a+114Lo.有4个结点且深度为4的二叉树的形态共有4种。18 .某二叉树的先根遍历序列为IJKLMNO,中根遍历序列为JLK1NMO,那么该二叉树中根 结点的右孩子是M o.第一个顶点和最终一个顶点相同的路径称为回路或者环，除第一个顶点和最终一个顶点 外，其余顶点都不重复的回路，称为简洁回路

28、或简洁环o19 . 一个具有10个顶点的完全无向图中有45 条边。26 .二分查找的时间简单度为O（log2n次方）o.二路归并排序算法的时间简单度为_O（nlog2n次方）。2007-一10.设有指针head指向不带表头结点的单链表用next表示结点的一个链域指针p指向与链 表中结点同类型的一个新结点。现要将指针p指向的结点插入表中使之成为第一个结点那么所 需的操作为p玲next=head 和17 .单链表中规律上相邻的两个元素在物理位置上 未必 相邻。18 .在一个长度为n的数组中删除第i个元素litl-rl=s-rl； 和s-rl-tl=s-tl;.对稀疏矩阵进行压缩麴的目的是节约储存空

29、间。18 .在一个具有n个结点的单链表中查找值为m的某结点，假设查找胜利，那么需平均比拟的结 点数为 n+1/2 o.深度为15的满二叉树上，第11层有 1024 个结点。5.深度为15的满二叉树上，第11层有2024个结点。在深度为7的满二叉树中,度为2的结点个数为.这里的度为2 的结点个数是什么意思？在深度为7的满二叉树中，度为2的结点个数为.这里的度为2的结点个数是什么意思？片冈美夕数学 2014-11-29优质解答度为2的节点就是该节点既有左子树,又有右子树深度为7的满二叉树总共的节点数为2人7-1 = 127;又因为是满二叉树,所以只有度为2的和度为0的节点，叶子节点的数目为：2人(

30、7-1)= 64,所以有度为2的结点做为二127-64 = 63个.21 .对一棵有100个结点的完全二叉树按层编号，那么编号为49的结点，它的左孩子的编号为98 oi的左孩子是2i,右孩子是2i+l.所以49的右孩子编号为98+1.22 .一个具有4个顶点的无向完全图有 6 条边。n(n-l)/2.一个有向图G中假设有孤、和,那么在图G的拓扑序列中，顶点M和Vk的相对位置为 VNj,Vk o.在一棵二叉排序树上按 中序 遍历得到的结点序列是一个有序序列。23 .实现二分查找的存储结构仅限于挨次存储结构，且其中元素排列必需是 有序表的。27 .在插入排序和选择排序中，假设原始纪录已基本有序，那

31、么较适合选用 插入排序.对n个元素的序列进行冒泡排序时，最多需进行n-1 趟。202210.在任何问题中，数据元素都不是孤立的，它们之间总存在某种关系，通常称这种关系为 图状结构 O16 .存储结点之间通常有四种基本存储方式，即挨次存储方式、索引存储方式、链式存储 方式 和散列存储方式。17 .在一个长度为n的挨次表中第i个元素(Bi)之前插入一个元素时，需向后移动 n-i+1 个元素。18 .对一棵深度为10的满二叉树按层编号，那么编号为51的结点，它的双亲结点编号为25 o.用S表示入栈操作，X表示出栈操作，假设元素入栈挨次为1234,为了得到1342的出栈挨 次，相应的S和X操作串为SX

32、SSXSXX o20 .具有n个叶子结点的哈夫曼树，其结点总数为 2n.l。21 .一棵具有n个结点的树,全部非终端结点的度均为k,那么该树中叶子结点个数为。 一棵具有n个结点的树，全部非终端结点的度均为k,那么此二叉树为K叉树，这棵树只右度 为K和度为。的结点，设度为K的结点数为a,度为。的结点数为b,那么n=a+b。又设二叉 树的全局部支为m,那么m=k*a,同样可以得到n=m+1。综上可以得到 b=(n-l)*(k-l)/k-lo.在无向图G的邻接矩阵A中，假设A i j等于0,那么A j i等于0。25 .某二叉树的后根遍历序列为abd,中根遍历序列为adb,那么它的先根遍历序列为 d

33、ab o.先在全部的纪录中选出键值最小的纪录，将它与第一个纪录交换；然后在其余的纪录中 再选出最小的纪录与其次个纪录交换，依此类推，直至全部纪录排序完成。这种排序方法 称为直接选择排序 o26 .对含有n个结点e条边的无向连通图，采用prim算法生成最小生成树的时间简单度为 O(n2 次方)o.对n个元素进行冒泡排序时，最少的比拟次数为_n-l。202201.在数据结构中，数据的存储结构有挨次存储方式、链式存储方式、索引存储方式 和散列存储方式等四种。16 .作为一个算法输入的数据所含数据元素的数目，或与此数目有关的其他参数，称为算 法的输入规模和问题的规模 o.在双链表中，存储一个结点有三个

34、域，一个是数据域，另两个是指针域，分别指向 直接前驱 和一直接后继 o17 .在有n个元素的链队列中，入队和出队操作的时间简单度分别为_0(1)和_0(n)o18 .在栈结构中，允许插入的一端称为栈顶；在队列结构中，允许插入的一端称 为 队尾o.在循环队列中，存储空间为。n-l。设队头指针front指向队头元素前一个空闲元素，队 尾指针指向队尾元素，那么其队空标志为rear=front ,队满标志为 _(rear+1 )%maxsize=front。19 .深度为k的二叉树至多有_2k次方-1 个结点，最少有 2(k次方-1)个结点。20 .设有一稠密图G,那么G采纳 邻接矩阵 存储结构较省空

35、间。设有一稀疏图G,那么G采纳 邻接表 存储结构较省空间。21 .在一个具有n个结点的单链表中查找其值等于x的结点时，在查找胜利的状况下，需平 均比拟(n+1)/2 个元素结点。22 .假定对线性表R 0.59进行分块检索，共分为10块，每块长度等于6。假设检索索引表 和块均用挨次检索的方法，那么检索每一个元素的平均检索长度为9 o.在插入排序、冒泡排序、快速排序、归并排序等排序算法中，占用帮助空间最多的是 一 归并排序 o27 .冒泡排序最好的时间简单度为 0 (n) ，平均时间简单度为_ 0 (n的平方) ,是一种稳定的排序算法。202210.以下程序段的时间简单度为 0(n)o i=0s

36、=0 whileKn i+ s=s+i)16 .数据的规律结构被分为集合结构、线性结构、树形结构和图状结构4种。17 .线性表中所含结点的个数称为表长。18 .向一个栈顶指针为top的链栈中插入一个新结点*p时应执行topnext_=p 和top=p操作。19 .设一个挨次栈S元素s1s2s3s4s5s6依次进栈假如6个元素的退栈挨次为s2s3s4s6s5sl那么挨次 栈的容量至少为3 o.假设满二叉树的结点数为n那么其高度为log2(n)J +1。20 .在一棵具有n个结点的完全二叉树中从树根起自上而下、从左到右地给全部结点编号。 假设编号为i的结点有父结点那么其父结点的编号为i/2o.深度

37、为k的二叉树结点数最多有 2k次方-1 个。21 .某二叉树的后根遍历为ABKCBPM那么该二叉树的根为 M。22 .在一个具有n个顶点的无向图中顶点的度最大可达n-1。23 .有向图G的邻接矩阵为A假如图中存在弧VW，那么Aij的值为1 o.挨次查找算法的平均查找长度为n+1/2 o24 .二路归并排序的平均时间简单度为Sk数2。20220116,以下程序段的时间简单度为 0（n3次方）ofor（i=l； i=n； i+）for（j=l； j=n； j+）for（k=l； k=n； k+）s = i+j+k；17 .在数据结构中，各个结点按规律关系相互缠绕，任意两个结点可以邻接的结构称为 图

38、状结构。18 .在单链表中，存储每个结点有两个域，一个是数据域，另一个是指针域，指针域指向该 结点直接后继 的。19 .在栈结构中，允许插入的一端称为 栈顶。20 .从一个长度为n的挨次表中删除第i个元素（1W）时，需向前移动 n-i 个元素。21 .一个栈的输入序列是1, 2, 3, n,输出序列的第一个元素是n,那么第i个输出元素为 n-i+1 o.循环队列被定义为结构类型，含有三个域：data、front和rear,那么循环队列sq为空的条 件 是 sq.front=sq.rea r。22 .一个10阶对称矩阵A,采纳行优先挨次压缩存储上三角元素，aoo为第一个元素，其存储 地址为0,每个元素占有1个存储地址空间，那么a45的地址为 19 o.对于一棵满二叉树，假设有m个叶子，那么树中结点数为 2m-l。23 .含有n个顶点和n-1条边的连通图G采纳邻接表 存储结构较省空间。24 .在图中，第一个顶点和最终一个顶点相同的路径称为 简洁回路或简洁环 o.动态查找中两个元素X, Y存入同一个散列表时，X、Y键值相同，那么这种状况称为冲突 o.堆排序需 一 个纪录大小的帮助存储空间。202210.以下程序段的时间简单度为_0（根号n）oi=0； s=0；while （sn）i+;s = s+i；）.数据的存储结构被分为挨次存储结构、链式存储结构、散列存储结构和索引存 储结构4种。