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

2024年甘肃开放大学数据结构形成性考核参考试题库（含答案）一、单选题1 .在实现某个系统中成员之间的隶属关系时,可以采用（）存储结构Av线性表B、栈C、队列D、树答案：D2 .如下图说是的二叉树按中序线索化,则结点X的右指针和Y的左指针分别指向（）B、，CCxD,ADxC,A答案：C3 .在长度为n的顺序表中，若要删除第i(1WiWn)个元素,则需要向前移动元素的次数为O。Av1Bxn-iC¼n-i+1Dvn-i-1答案：B4 .在定义数组inta10后,需要访问数组中第3个元素,正确的是()。Ax0Bva1C、a2Dva3答案：C5 .在n个结点的线索二叉树中,可用于线索的指针域数目为()。Avn-1BxnC¼n+1Dv2n答案：C6 .下面关于工程计划的AOE网的叙述中，不正确的是0。A、关键活动不按期完成就会影响整个工程的完成时间B、任何一个关键活动提前完成,那么整个工程将会提前完成C、所有的关键活动都提前完成那么整个工程将会提前完成D、某些关键活动若提前完成,那么整个工程将会提前完答案：B7 .任何一棵二又树的叶结点在前序、中序和后序遍历序列中的相对次序()。Av不发生变化B、发生变化C、某些树中发生变化,某些树中不发生变化Dv没有规律,无法确定答案：A8 .向一个队首指针为front、队尾指针为rear的链队列中插入一个S所指结点时,其操作步骤为()。1 、s->next-front;front->next=s;8 、front=front->next;Cxrear->next=s;rear-s;Dxrear=s;s->next=rear;答案：C9 .含n个顶点的连通图中的任意一条简单路径,其长度不可能超过()。Av1B、n/2Cn-1Dxn10 .关键路径是AOE网中()。A、从源点到终点的最长路径B、从源点到终点的最短路径C、最长的回路Dv最短的回路答案：A11 .顺序队列的初始化时,需要将front和rear分别设置为()。A、都是0Bx0和-1C、都是Dv-1和0答案：A12 .某顺序栈sqStack,其成员包含两部分:data10和top,分别代表数据和栈顶,则表示栈中第三个数据元素的是0。AxsqStack.data2B、sqStack.data3CvsqStack.data4D、无法表示答案：A13 .以下说法正确的是0。A、若一个树叶是某二叉树的前序遍历序列中的最后一个结点,则它必是该二又树的后序遍历序列中的最后一个结点。B、若一个树叶是某二叉树的前序遍历序列中的最后一个结点,则它必是该二叉树的中序遍历序列中的最后一个结点。C、若二叉树中，有两个孩子结点的双亲结点在中序遍历序列中，它的后继结点中必然有一个孩子结点。D、若二叉树中，有一个孩子结点的双亲结点在中序遍历序列中，它的后继结点中没有该孩子结点。答案：C14 .图的深度优先遍历类似于二叉树的()遍历，它所用到的数据结构是O。Av前序,栈B、后序,栈C、前序,队列D、后序,队列答案：A15 .用链式存储的栈,在出栈操作之前,需要()。A、判断栈是否满了B、判断栈是否空了C、不需判断D、以上答案都不对答案：B16 .用单链表方式存储的线性表,存储每个结点需要两个域,一个数据域,另一个是()。A、当前结点所在地址域Bx地址域C、空指针域D、空闲域答案：B17 .递归函数调用时,处理参数及返回地址,要用一种称为()的数据结构A、队列B、多维数组C、栈D、线性表答案：C18 .有结构体定义及结构体类型数组如下:StructworkIistintno;charname120;CharSex;PerSOn5;需要给结构体数组中第2个变量的no成员赋值为5,正确的写法是0。A、no-5;B、person,no-5:Cxperson2.no-5;D、person1.no-5.答案：D19 .已知一棵度为3的树有2个度为1的结点,3个度为2的结点,4个度为3的结点。则该树中有()个叶子结点。Av8C、12D、14答案：C20 .若栈采用顺序存储方式存储,现两栈共享空间V口.top口代表第i个栈(i=1,2)栈顶,栈1的底在V0,栈2的底在Vm-1,则栈满的条件是()。Axtop2-top1=0Bxtop1+1=top2Cxtop1+top2-mDxtop1=top2答案：B21 .用顺序存储的方法将完全二叉树中所有结点逐层存放在数组R口,根结点存入R1,结点R口若有左子树,则左子树是结点()。AvR2*i+IBxR2*iC、Ri2DxR2*i-1答案：B22 .分析以下程序段,其时间复杂度为TO=()o1=1；While(i<=n)l=',3*i;<">B、0(n2)Cv0(n3)DxO(log3n)答案：D23 .循环单链表的主要优点是()。A、不再需要头指针了B、已知某个结点的位置后,能够容易找到他的直接前趋C、在进行插入、删除运算时,能更好的保证链表不断开D、从表中的任意结点出发都能扫描到整个链表答案：D24 .一棵树的广义表表示为a(b(c),de(g(h),f,k),则该树的叶子结点个数为OoA、2B、3C、4D、5答案：C25 .设有13个值,用它们组成一棵赫夫曼树,则该赫夫曼树共有()个结点。Av12B、13C、25答案：C26 .顺序栈包含两部分,数组data10和栈顶top,当top值为()表示栈空。Ax0Bx10Cx9D、-1答案：D27 .在一个顺序循环队列中，队尾指向队尾元素的0位置。Av前一个Bv后一个C、当前Dv最后答案：B28 .下列关于最小生成树的叙述中，正确的是()。Av最小生成树不唯一,但是最小生成树各边权值总和唯一Bv所有权值最小的边一定会出现在最小生成树中C、使用Prim算法从不同顶点开始得到的最小的生成树一定相同Dv使用Prim算法和使用Kruskal算法得到的最小生成树总不相同答案：A29 .在一棵树中，每个结点最多有0个前驱结点。Ax0C、2Dv任意多个答案：B30 .一棵二又树前序遍历序列是ABDGCFK,中序序列是DGBAFCK,则它的后序遍历序列是()。A、 CFKDBGB、 GDBFKCAGKCFAGDBDxABCDFKG答案：B31 .在数据结构中,从逻辑上可以把数据结构分成()。A、动态结构和静态结构B、紧凑结构和非紧凑结构C、线性结构和非线性结构Dv内部结构和外部结构答案：C32 .n个顶点的生成树有()条边。A、n-1B、nC、n+1D、2n33 .链队列的在建立时,可以采用()将几个元素链接起来建立单链表A、头插法Bv尾插法C、随机插入法D、需要指定插入位置的方法答案：B34 .有一份电文中共使用5个字符:a、b、Cvd、e,它们的出现频率依次为4、7、5、2、9,对应的赫夫曼树中字符a的赫夫曼编码长度为O。Av1Bv2C、3D、4答案：C35 .栈和队列都是特殊的线性表,其特殊性在于O。A、它们具有一般线性表所没有的逻辑特性Bx它们的存储结构比较特殊C、对他们的使用方法做了限制Dv它们比一般线性表更简单答案：C36 .树中所有结点的度等于所有结点数加()。AxOC、-1Dv2答案：C37 .一棵树的广义表表示为a(b(c),d(e(g(h),f,k),则该树的度为()0A、OBv1C、2D、3答案：D38 .对下面的有向图进行深度优先遍历得到的遍历序列是()oA、 bcfdegB、 abcgfdeCvabcdefgD、abcfgde答案：A39.已知单链表的每个结点包括一个指针域next,它指向该结点的后继结点。现要将指针指向的新结点插入到指针P指向的结点之后,下面的操作序列中正确的A、 q-p->next;p->next-q->next:B、 p->next-q->next:q-p->next:C、 q->next-p->next;p->next-q:Dvp->next-q;q->next-p->next;答案：C40 .栈中元素的进出原则是O。A、先进先出B、后进先出C、栈空则进Dx栈满则出答案：B41 .在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前,则下列情形不可能出现的是()。A、G中有弧B、G中有一条从Vi到Vj的路径C、G中没有弧D、G中有一条从Vj到Vi的路径答案：D42 .栈的插入和删除操作在()进行。A、栈底B、栈顶C、任意位置D、指定中间某位置答案：B43 .用链式存储的栈,在进行出栈和入栈运算时O。A、仅修改头指针B、仅修改尾指针C、头、尾指针都要修改D、头、尾指针可能都要修改答案：A44 .设aI,a2,a3为三个结点;p,10,20代表地址,则如下的链表存储结构称为()。A、单链表B、循环单链表C、双向链表D、循环双向链答案：A45 .某顺序栈saStack,其成员包含两部分:data10和top,分别代表数据和栈顶,初始时top值为7,则表示栈顶数据元素的是()。AxsqStack.data9B、sqStack.topCvsqStack.datasqStack.topDxsqStack.top+1答案：C46 .已知单链表的每个结点包括一人指针域next,它指向该结点的后继结点。在一个单链表中，若删除P所指结点的直接后继结点则执行()。Avp->next-p->next->next;B、p-p->next;p->next-p->next->next;Cxp-p->next->next;答案：A47 .二又树在线索化后,仍然不能有效求解的问题是()。A、在先序线索二叉树中求先序后继B、在中序线索二又树中求中序后继C、在中序线索二叉树中求中序前驱驱D、在后序线索二又树中求后序后继答案：D48 .n个顶点的无向图的接表最多有()个结点。Avn28、 n(n-1)Cxn(n+1)D、n(n-1)2答案：B49 .一棵深度为6的满二又树一共有个()结点。Av31Bx32C、63D、64答案：C50 .在下图中,J结点是()。(DII)(，)/Iej(I)(UQ)A、叶节点B、根结点但不是分支结点Cx根结点也是分支结点D、分支结点但不是根结点答案：A51 .若用一个大小为6的数组来实现循环队列,且当前rear和front的值分别为0和3,当从队列中删除一个元素,再加入两个元素后,rear和front的值分别为OoA、1和5Bx2和4Cx4和2Dx5和