2024年吉林开放大学《数据结构》形成性考核参考试题库（含答案）.docx

2024年吉林开放大学数据结构形成性考核参考试题库(含答案)一、单选题1.对图从顶点a出发进行广度优先遍历,则0是不可能得到的遍历序列。A、 bcdefgB、 acdbfgeCxabdcegfDxadcbgef答案：D2 .栈和队列的共同点是()。A¼都是先进先出B、都是先进后出C、只允许在端点处插入和删除元素D、没有共同点答案：C3 .在AOE网中()关键路径。A、一定只有一条B、可能只有一条C、不可能只有一条D、以上答案都不对答案：B4 .一棵树的广义表表示为a(b(c),de(g（三）),frk),则该树的叶子结点个数为()oA、2Bv3Cx4D、5答案：C5 .n个顶点的无向图的接表最多有()个结点。A、n2Bxn(n-1)Cxn(n+1)Dvn(n-1)2答案：B6 .在一棵深度为k的完全二叉树中，所含结点个数至少()。A、2K(2的K次方)B、2k+1(2的K次方+1)G2k-1(不选C)Dx2k-1(2的K次方7)答案：D7 .顺序队列的初始化时,需要将front和rear分别设置为()。B、O和-1C、都是-1Dv-1和0答案：A8 .在C语言中，有一种适用于不同数据类型构成的数据的结构称为()。A、结构体B、数组C、变量D、常量答案：A9 .用链式存储的栈,在进行出栈和入栈运算时()。A、仅修改头指针B、仅修改尾指针C、头、尾指针都要修改D、头、尾指针可能都要修改答案：A10 .设无向图G中有五个顶点,各顶点的度分别为2、4、3、1、2,则G中边数为()。A、4B、5C、6D、无法确定11 .表示一个有100个顶点JOoO条边的非带权有向图的邻接矩阵有()个大于零矩阵元素A、100B、 1000C、 100x100-1000D、 1000x2答案：B12 .双向链表中有两个指针域，Iink和rink分别指向前趋及后,设p指向链表中的一个结点,现要求删去P所指结点,则正确的删除是()(链中结点数大于2,P不是第一个结点)oAvp->IIink->rIink-p->Ilink;p->rIink->IIink-p->rlink;free(p);B、free(p);p->IIink->rIink-p->Ilink;p->rIink->IIink-p->rlink;Cxp->IIink->rIink-p->Ilink;free(p);p->rIink->IIink-p->rlink;Dv以上A,B,C都不对答案：D13 .两类存储结构为()。A、线性结构和非线性结构Bx逻辑结构和非逻辑结构C、顺序结构和链式结构Dv逻辑结构和物理结构14 .有个结构体及其变量定义如下:Structdateintyear;intmonth:intday;birthday;此时要调用变量中的year,正确的书写格式是0。AxyearB、irthday.yearC、date.yearDxstruct.year答案：B15 .循环单链表的主要优点是()。Av不再需要头指针了Bx已知某个结点的位置后,能够容易找到他的直接前趋C、在进行插入、删除运算时,能更好的保证链表不断开Dx从表中的任意结点出发都能扫描到整个链表答案：D16 .图的深度优先遍历类似于二叉树的()遍历，它所用到的数据结构是0。Av前序,栈B、后序,栈C、前序,队列D、后序,队列答案：A17 .在一棵树中，每个结点最多有0个前驱结点。Ax0C、2Dv任意多个答案：B18 .为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,只有当()时,才产生上溢A、两个栈的栈顶同时到达栈空间的中心点B、其中一个栈的栈顶到达栈空间的中心点C、两个栈的栈顶在栈空间的某一位置相遇D、两个栈均不空,且一个栈的栈顶到达另一个栈的栈底答案：C19 .线性表的顺序存储结构是一种()的存取结构。A、随机存取B、顺序存取C、索引存取DxHaSh存取答案：A20 .已知单链表的每个结点包括一个指针域next,它指向该结点的后继结点。在一个单链表中，已知q指结点是P所指结点的直接前驱结点,若在q和P之间插入S结点,则执行()。Axs->next-p->next;p->next-s;B、 p->next-s->next;s->next-p:C、 q->next-s;s->next-p;D、 p->next-s;s->next-q;答案：C21.无向图6="巳)，其中7=匕,丁5&6,竹£二(1母)，(2,6),仁0),1),日)，七节,(f,d)(e.d),对该图进行深度优先遍历,得到的顶点序列正确的是()。Ax,b,e,c,d,fBxA,c,f,e,b,dCxA,e,b,c,f,dDxA,e,d,f,c,b答案：D22 .对于顺序存储的栈和队列,进行插入和删除的算法的时间复杂度为()。A、0(1)B、0(n)Cv0(n2)Dv无法确定答案：A23 .对有n个顶点、e条边且使用邻接表存储的有向图进行广度优先遍历,其算法的时间复杂度是()。Ax0(n)Bx0(e)Cx0(n+e)DvO(nXe)24 .下图中的树转换成二又树后,B结点的孩子结点有()oA、仅有EBvC和DC、E和CDvE和F答案：C25 .下面关于线性表的叙述中,错误的是()。A、线性表采用顺序存储必须占用一片连续的存储单元B、线性表采用顺序存储便于进行插入和删除操作C、线性表采用链式存储不必占用一片连续的存储单元D、线性表采用链式存储便于进行插入和删除操作答案：B26 .设aI,a2,a3为三个结点;p,10,20代表地址,则如下的链表存储结构称为()。A、单链表B、循环单链表C、双向链表D、循环双向链答案：A27 .递归函数调用时,处理参数及返回地址,要用一种称为()的数据结构A、队列B、多维数组C、栈D、线性表答案：C28 .某顺序栈sqStack,其成员包含两部分:data10和top,分别代表数据和栈顶,则表示栈中第三个数据元素的是0。AxsqStack.data2B、sqStack.data3CvsqStack.data4D、无法表示答案：A29 .设深度为k的二叉树上只有度为0和度为2的结点,则这棵树所含的结点数至少为()。A、k+1Bv2k-1C、2kD、2k+130.在下图中,树的深度为()Av1Bv2C、3Dx4答案：D31.已知单链表的每个结点包括一个指针域next,它指向该结点的后继结点。带头结点的单链表1.为空的条件是()A、 1.i=NU1.1.Bv1.=NU1.1.C、1.-Xext=NU1.1.Dx1.->next-1.答案：C32 .栈中元素的进出原则是()。A、先进先出B、后进先出Cv栈空则进D、栈满则出答案：B33 .对下面的有向图进行深度优先遍历得到的遍历序列是()oAvbcfdegB、 abcgfdeC、 abcdefgD、 abcfgde答案：A34 .用链式存储的栈,在进栈操作之前,需要()。A、判断栈是否满了B、判断栈是否空了C、不需判断D、以上答案都不对答案：C35 .下面关于工程计划的AOE网的叙述中，不正确的是()。A、关键活动不按期完成就会影响整个工程的完成时间B、任何一个关键活动提前完成,那么整个工程将会提前完成C、所有的关键活动都提前完成.那么整个工程将会提前完成D、某些关键活动若提前完成,那么整个工程将会提前完答案：B36 .在一棵具有35个结点的完全二叉树中,该树的深度为()。A、5Bv6C、7Dv8答案：B37 .在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前,则下列情形不可能出现的是()。AvG中有弧B、G中有一条从Vi到Vj的路径C、G中没有弧DvG中有一条从Vj到Vi的路径答案：D38 .某无向图的邻接矩阵如图所示,可以看出该图共有()个顶点。OlOI101010Ax1B、3C、6D、9答案：B39 .以下说法错误的是()。A、存在这样的二叉树,对它采用任何次序遍历其结点访问序列均相同B、普通二叉树只能用链式存储结构存储C、由树转换成二叉树,其根结点的右子树总是空的D、二叉树只有一棵子树的情况下也要明确指出该子树是左子树还是右子树答案：B40 .栈通常采用的两种存储结构是0。Av顺序存储结构和链式存储结构B、散列方式和索引方式C、链式存储结构和数组D、线性存储结构和非线性存储结构答案：A41 .在一棵二叉树的二叉链表中，空指针域等于所有非空指针域相加()。A、-1B、0C、1D、2答案：D42 .用邻接表存储图所用的空间大小0。A、与图的顶点数和边数都有关B、只与图的边数有关C、只与图的顶点数有关D、与边数的平方有关答案：A43 .后缀表达式“45*32+-”的值为()。Av21Bv17C、15Dv5答案：C44 .在长度为n的顺序表中第i(1WiWn)个位置上插入一个元素时,为留出插入位置所需移动元素的次数为()。Avn-iB、iCn-i+1Dvn-i-1答案：C45 .表示一个有100个顶点JOOO条边的无向图的邻接矩阵有()个非零矩阵元素。A、100B、1000C、9000Dv1000x2答案：D46 .某图的邻接矩阵如图所示,若G为无向图,则G中共有()条边。O1OIlOl010b4Av1Bv2C、3Dv4答案：B47 .最大容量为maxsize的循环队列，队尾指针是rear,队头是front,初始时均为0且采用损失一个空间的原则,则队满条件为()。Av(rear+1)%maxsize-(front+1)%maxsizeBx(front+1)%maxsize-rearCx(rear+1)%maxsize-frontD、rear-front答案：C48 .设有13个值,用它们组成一棵赫夫曼树,则该赫夫曼树共有()个结点。Av12B、13C、25Dv2649 .用链式存储的栈,在出栈操作之前,需要OoA、判断栈是否满了B、判断栈是否空了C、不需判断D、以上答案都不对答案：B50 .用链表表示线性表的优点是()。A、便于随机存取B、占用的存储空间较顺序表少C、便于进行插入和删除操作D、元素的物理顺序与逻辑顺序相同答案：C51 .对于顺序循环队列,以下说法正确的是()。A、无法判断队列是否为空B、无法判断队列是否为满C、队列不可能满D、以上说法都不对答案：D52 .分析以下程序段,其时间复杂度为TO=()o1=1；While(i<=n)l=',3*i;<">Av0(n)B、0(n2)CvO(n3)DvO(log3n)答案：D