2026秋国家开放大学《大数据与数据结构》（课程ID：05479）形考任务1-4参考答案

国家开放大学《大数据与数据结构》形考任务1—4参考答案适用：2026年秋季学期·国开学习网在线形考按2026年秋季学期最新网络题库逐题匹配，覆盖数据结构基础、线性表、栈与队列、树与二叉树、图、查找、排序以及Hadoop/Spark大数据技术，单项选择题均含完整选项，题号用阿拉伯数字顺序编排。⚠️平台抽题时选项顺序可能随机打乱，请按题干关键字定位题目，核对选项内容后再作答；算法题的答案不唯一，只要思路与复杂度正确即可得分。形考任务一大数据概述·数据结构基本概念·算法与复杂度·线性表一、单项选择题1.下列不属于大数据主要特征的是（）A.数据体量大（Volume）B.处理速度快（Velocity）C.数据类型多样（Variety）D.数据必须完全结构化答案：D2.数据结构中，数据元素之间的逻辑关系称为（）A.逻辑结构B.存储结构C.物理结构D.数据运算答案：A3.下列数据结构中属于线性结构的是（）A.树B.图C.队列D.集合答案：C4.数据的存储结构是逻辑结构在计算机中的表示，下列不属于存储结构的是（）A.顺序存储B.链式存储C.索引存储D.树形存储答案：D5.在长度为n的顺序表中，等概率情况下插入一个元素平均需要移动的元素个数为（）A.n/2B.(n−1)/2C.nD.(n+1)/2答案：A6.在长度为n的顺序表中，等概率情况下删除一个元素平均需要移动的元素个数为（）A.n/2B.(n−1)/2C.(n+1)/2D.n−1答案：B7.单链表中访问第i个结点的时间复杂度为（）A.O(1)B.O(log₂n)C.O(n)D.O(n²)答案：C8.已知指针p指向单链表中某结点，要在p所指结点之后插入s所指结点，正确的语句是（）A.s->next=p;p->next=s;B.s->next=p->next;p->next=s;C.p->next=s;s->next=p;D.p->next=s->next;s->next=p;答案：B9.单链表设置头结点的主要作用是（）A.节省存储空间B.使空表与非空表的插入、删除操作得到统一，简化边界处理C.加快查找速度D.便于实现随机存取答案：B10.与顺序存储相比，链式存储的主要优点是（）A.可随机存取B.存储密度高C.插入和删除不必移动大量元素D.不需要额外指针空间答案：C11.下列不属于算法基本特性的是（）A.有穷性B.确定性C.可行性D.可移植性答案：D12.下列时间复杂度中最小的是（）A.O(n)B.O(nlog₂n)C.O(log₂n)D.O(n²)答案：C二、判断题1.数据的存储结构是数据的逻辑结构在计算机存储器中的表示。（）A.正确B.错误答案：A2.线性表采用顺序存储时，所有元素必须占用一片连续的存储空间。（）A.正确B.错误答案：A3.单链表可以随机存取表中任一元素。（）A.正确B.错误答案：B4.算法的时间复杂度与运行算法的计算机速度直接相关。（）A.正确B.错误答案：B5.在循环链表中，从表中任一结点出发都能遍历整个链表。（）A.正确B.错误答案：A6.数据项是数据不可分割的最小单位，一个数据元素可由若干数据项组成。（）A.正确B.错误答案：A7.空间复杂度是指算法在执行过程中除输入数据外所需的辅助存储空间大小。（）A.正确B.错误答案：A8.线性表采用链式存储时，各结点的存储单元必须连续。（）A.正确B.错误答案：B9.抽象数据类型包括数据对象、数据关系以及定义在该数据对象上的一组基本操作。（）A.正确B.错误答案：A10.顺序表进行插入操作时，若插入位置在表尾，则不需要移动任何元素。（）A.正确B.错误答案：A三、计算与算法题1.一个长度为n=10的顺序表，在等概率情况下插入一个元素，平均需要移动多少个元素？删除一个元素平均又需移动多少个？答案：插入：可插入位置共n+1=11个，在第i个位置插入需移动n−i+1个元素，移动总数=n+(n−1)+…+1+0=n(n+1)/2，平均值=[n(n+1)/2]/(n+1)=n/2=10/2=5个。删除：可删除位置共n=10个，删除第i个元素需移动n−i个元素，移动总数=(n−1)+(n−2)+…+0=n(n−1)/2，平均值=[n(n−1)/2]/n=(n−1)/2=9/2=4.5个。2.分析下列程序段的时间复杂度。i=1;

while(i<=n)

i=i*3;答案：设循环执行k次，则3^k≤n，即k≤log₃n，故执行次数约为⌊log₃n⌋+1。时间复杂度T(n)=O(log₃n)=O(log₂n)，只与问题规模n的对数有关。3.写出将带头结点的单链表就地逆置的算法。答案：思路：从原链表依次摘下结点，用头插法重新插入到头结点之后，只需O(1)辅助空间。voidReverse(LinkListL){

LNode*p=L->next,*q;//p指向第一个数据结点

L->next=NULL;//头结点与后续结点断开

while(p!=NULL){

q=p->next;//暂存后继

p->next=L->next;//头插

L->next=p;

p=q;

}

}时间复杂度O(n)，空间复杂度O(1)。4.写出在顺序表中删除值最小的元素（假设唯一）的算法，并用表尾元素填补被删位置。答案：boolDelMin(SqList&L,ElemType&e){

if(L.length==0)returnfalse;

intpos=0;

for(inti=1;i<L.length;i++)

if(L.data[i]<L.data[pos])pos=i;//找最小值下标

e=L.data[pos];//保存被删元素

L.data[pos]=L.data[L.length-1];//表尾元素填补

L.length--;

returntrue;

}时间复杂度O(n)，空间复杂度O(1)。注意：若最小值恰在表尾，填补操作等价于直接删除，逻辑仍然成立。

形考任务二栈与队列·串与数组·树与二叉树一、单项选择题1.栈的操作特点是（）A.先进先出B.后进先出C.随机存取D.按关键字存取答案：B2.若入栈序列为1、2、3、4，则下列不可能的出栈序列是（）A.1、2、3、4B.4、3、2、1C.4、3、1、2D.2、3、4、1答案：C3.队列的操作特点是（）A.后进先出B.先进先出C.只能在中间插入D.两端都可删除答案：B4.设循环队列的最大容量为m，采用"少用一个存储单元"的方式区分队空与队满，则队满的条件是（）A.front==rearB.(rear+1)%m==frontC.rear==m−1D.front==0答案：B5.循环队列中元素个数的计算公式是（）A.rear−frontB.front−rearC.(rear−front+m)%mD.(front−rear+m)%m答案：C6.下列应用中，不宜采用栈的是（）A.表达式求值B.括号匹配检查C.函数递归调用D.操作系统作业调度排队答案：D7.一棵二叉树第i层（根为第1层）最多有（）个结点A.2iB.2^iC.2^(i−1)D.2^i−1答案：C8.深度为k的二叉树最多有（）个结点A.2^kB.2^k−1C.2^(k−1)D.2k−1答案：B9.具有n个结点的二叉树中，空指针域的个数为（）A.n−1B.nC.n+1D.2n答案：C10.已知一棵二叉树的先序序列和中序序列，可以（）A.唯一确定这棵二叉树B.不能确定C.只能确定根结点D.可确定两棵不同的树答案：A11.在哈夫曼树中，其带权路径长度（WPL）（）A.最大B.最小C.与树的形态无关D.等于各结点权值之和答案：B12.具有n个结点的完全二叉树，其叶子结点数为（）A.n/2B.⌈n/2⌉C.⌊n/2⌋−1D.n−1答案：B二、判断题1.栈和队列都是操作受限的线性表。（）A.正确B.错误答案：A2.二叉树中每个结点最多有两棵子树，且子树有左右之分，次序不能颠倒。（）A.正确B.错误答案：A3.完全二叉树中一定不存在度为1的结点。（）A.正确B.错误答案：B4.满二叉树一定是完全二叉树，反之不成立。（）A.正确B.错误答案：A5.已知一棵二叉树的先序序列和后序序列，即可唯一确定这棵树。（）A.正确B.错误答案：B6.哈夫曼树中不存在度为1的结点。（）A.正确B.错误答案：A7.队列的插入只能在队尾进行，删除只能在队头进行。（）A.正确B.错误答案：A8.串是一种特殊的线性表，其数据元素只能是字符。（）A.正确B.错误答案：A9.稀疏矩阵采用三元组顺序表压缩存储后，仍可按行、列下标随机存取任一元素。（）A.正确B.错误答案：B10.二叉树的先序遍历、中序遍历、后序遍历中，叶子结点的相对次序保持不变。（）A.正确B.错误答案：A三、计算与算法题1.一棵完全二叉树共有1000个结点，求其叶子结点数、度为1的结点数和度为2的结点数。答案：设n₀、n₁、n₂分别为度为0、1、2的结点数：①n₀+n₁+n₂=1000；②由二叉树性质n₀=n₂+1，即n₂=n₀−1。代入得2n₀−1+n₁=1000。完全二叉树中度为1的结点数n₁只能取0或1，n=1000为偶数，故n₁=1。则n₀=(1000+1−1)/2=500，n₂=500−1=499。校验：500+1+499=1000✓。2.已知权值集合{5,7,2,3,6,8}，构造哈夫曼树并求其带权路径长度WPL。答案：每次取两个最小权值合并，合并过程为：①2+3=5，余{5,5,6,7,8}；②5+5=10，余{6,7,8,10}；③6+7=13，余{8,10,13}；④8+10=18，余{13,18}；⑤13+18=31（根）。WPL等于所有非叶结点权值之和：WPL=5+10+13+18+31=77。（权值总和为31，平均码长为77/31≈2.48位。）3.已知一棵二叉树的先序序列为ABDECFG，中序序列为DBEAFGC，求其后序序列。答案：先序首字符A为根；在中序中A左侧DBE为左子树、右侧FGC为右子树。左子树：先序BDE、中序DBE→根B，D为左孩子，E为右孩子。右子树：先序CFG、中序FGC→根C，F为左孩子，G为右孩子。故二叉树为：A（左B（左D，右E），右C（左F，右G））。后序（左—右—根）序列为DEBFGCA。4.设循环队列的最大容量m=50，当前front=15、rear=8（采用"少用一个单元"的判满方式），求队列中元素个数，并判断此时队空还是队满。答案：元素个数=(rear−front+m)%m=(8−15+50)%50=43%50=43个。队空条件front==rear不成立；队满条件(rear+1)%m==front，即9≠15不成立，故队列既非空也非满，处于有43个元素的状态（还可再存入6个元素即达m−1=49的上限）。

形考任务三图·查找一、单项选择题1.用邻接矩阵存储具有n个顶点的无向图，所需存储空间为（）A.O(n)B.O(n²)C.O(n+e)D.O(e)答案：B2.具有n个顶点的无向连通图，其边数至少为（）A.nB.n−1C.n+1D.n(n−1)/2答案：B3.采用邻接表存储有向图时，顶点v的出度等于（）A.第v个单链表的长度B.各单链表中出现v的次数C.顶点总数D.边总数答案：A4.图的深度优先遍历（DFS）通常借助（）实现A.队列B.栈（或递归）C.优先队列D.哈希表答案：B5.具有n个顶点、e条边的图采用邻接表存储，其深度优先遍历的时间复杂度为（）A.O(n)B.O(e)C.O(n+e)D.O(n²)答案：C6.关于最小生成树算法，下列说法正确的是（）A.Prim算法更适合稀疏图B.Kruskal算法更适合稠密图C.Prim算法时间复杂度与边数无关，适合稠密图D.两种算法得到的最小生成树一定相同答案：C7.Dijkstra算法用于求单源最短路径，其不适用的情况是（）A.无向图B.有向图C.存在负权边的图D.稠密图答案：C8.能够进行拓扑排序的图必须是（）A.无向连通图B.有向无环图C.有向完全图D.带权连通图答案：B9.折半查找要求线性表必须（）A.采用链式存储且有序B.采用顺序存储且按关键字有序C.采用顺序存储，是否有序无要求D.是二叉排序树答案：B10.对二叉排序树进行（）遍历，可得到按关键字递增的有序序列A.先序B.中序C.后序D.层次答案：B11.在哈希查找中，装填因子α越大，则（）A.冲突可能性越小B.冲突可能性越大，平均查找长度越长C.与冲突无关D.查找效率一定提高答案：B12.具有n个结点的二叉排序树，其查找的最坏时间复杂度为（）A.O(1)B.O(log₂n)C.O(n)D.O(nlog₂n)答案：C二、判断题1.用邻接矩阵存储无向图时，矩阵一定是对称矩阵。（）A.正确B.错误答案：A2.用邻接矩阵存储有向图时，矩阵一定是对称矩阵。（）A.正确B.错误答案：B3.对无权图进行广度优先遍历，可以求得从源点到各顶点的最短路径（边数最少）。（）A.正确B.错误答案：A4.Prim算法更适合稀疏图，Kruskal算法更适合稠密图。（）A.正确B.错误答案：B5.一个连通图的生成树包含n−1条边，且不包含回路。（）A.正确B.错误答案：A6.对一个有向无环图，其拓扑排序序列是唯一的。（）A.正确B.错误答案：B7.折半查找既可用于顺序表，也可直接用于单链表。（）A.正确B.错误答案：B8.哈希表中装填因子越大，平均查找长度越小。（）A.正确B.错误答案：B9.在二叉排序树中插入新结点时，新结点一定成为叶子结点。（）A.正确B.错误答案：A10.AOE网中的关键路径是源点到汇点路径长度最长的那条路径。（）A.正确B.错误答案：A三、计算与算法题1.无向图G有6个顶点、9条边，分别用邻接矩阵和邻接表存储，求各自的空间需求和遍历的时间复杂度。答案：邻接矩阵：需6×6=36个存储单元，空间复杂度O(n²)=O(36)；DFS/BFS需检查矩阵的每一行，时间复杂度O(n²)=O(36)。邻接表：顶点表6个，边结点2e=18个（无向图每条边存两次），空间复杂度O(n+e)=O(24)；DFS/BFS时间复杂度O(n+e)=O(24)。结论：稠密图用邻接矩阵、稀疏图用邻接表更省空间与时间。2.已知带权无向图的边集为(A,B,6)、(A,C,1)、(A,D,5)、(B,C,5)、(B,E,3)、(C,D,5)、(C,E,6)、(C,F,4)、(D,F,2)、(E,F,6)，用Kruskal算法求最小生成树及其权值。答案：按权值从小到大排序：AC(1)、DF(2)、BE(3)、CF(4)、AB(5)、CD(5)、AD(5)、BC(6)、CE(6)、EF(6)。①选AC(1)，不构成回路；②选DF(2)；③选BE(3)；④选CF(4)，连接{A,C}与{D,F}；⑤选AB(5)，连接{B,E}；此时6个顶点已连通，共5条边，停止。最小生成树边集：{AC,DF,BE,CF,AB}，权值W=1+2+3+4+5=15。3.对有序表{5,13,19,21,37,56,64,75,80,88,92}进行折半查找，求查找关键字64时的比较过程与比较次数。答案：n=11，下标1~11。第1次：low=1，high=11，mid=6，元素56<64，令low=7；第2次：low=7，high=11，mid=9，元素80>64，令high=8；第3次：low=7，high=8，mid=7，元素64=64，查找成功。共比较3次，对应判定树中64位于第3层。折半查找最多比较⌈log₂(n+1)⌉=⌈log₂12⌉=4次。4.设哈希表长为13，哈希函数H(k)=kmod13，用线性探测法处理冲突，依次插入关键字25、37、52、43、84、99、120、15，画出哈希表并求查找成功的平均查找长度。答案：依次计算与放置（下标0~12）：25%13=12→位置12（1次）；37%13=11→11（1次）；52%13=0→0（1次）；43%13=4→4（1次）；84%13=6→6（1次）；99%13=8→8（1次）；120%13=3→3（1次）；15%13=2→2（1次）。本题8个关键字均未发生冲突，每个元素的查找长度均为1，故ASL成功=(1×8)/8=1。说明：若题目给出的关键字使H(k)相同（如再插入38，38%13=12已被占，则探测0位已被占、1位空，查找长度变为3），此时按"各元素查找长度之和÷元素个数"重新计算即可。

形考任务四排序·大数据处理技术一、单项选择题1.下列排序算法中，属于不稳定排序的是（）A.直接插入排序B.冒泡排序C.快速排序D.归并排序答案：C2.快速排序在（）情况下时间复杂度退化为O(n²)A.待排序列随机排列B.待排序列已基本有序且以第一个元素为基准C.待排序列元素较少D.待排序列元素互不相同答案：B3.对n个元素进行冒泡排序，最多需要比较的次数为（）A.n−1B.n(n−1)/2C.n²D.nlog₂n答案：B4.下列排序算法中，空间复杂度为O(1)的是（）A.归并排序B.快速排序（递归栈不计时的就地划分）C.堆排序D.基数排序答案：C5.归并排序的空间复杂度为（）A.O(1)B.O(log₂n)C.O(n)D.O(n²)答案：C6.一趟排序结束后不一定能确定某个元素最终位置的排序方法是（）A.冒泡排序B.快速排序C.简单选择排序D.直接插入排序答案：D7.若待排序列已按关键字有序，则下列排序算法中效率最高的是（）A.直接插入排序B.快速排序C.简单选择排序D.堆排序答案：A8.大顶堆中任一非叶结点的关键字与其孩子结点的关系是（）A.大于等于其孩子结点B.小于等于其孩子结点C.等于其左孩子D.无固定关系答案：A9.排序算法的"稳定性"是指（）A.排序过程不改变元素个数B.关键字相同的元素排序后相对次序保持不变C.排序结果唯一D.排序时间固定答案：B10.Hadoop分布式计算平台的两个核心组件是（）A.MySQL与TomcatB.HDFS与MapReduceC.Kafka与FlumeD.Hive与HBase答案：B11.Hadoop2.x/3.x中HDFS的默认数据块大小为（）A.64MBB.128MBC.256MBD.1GB答案：B12.关于Spark，下列说法正确的是（）A.基于磁盘计算，适合迭代运算B.基于内存计算，核心抽象是RDDC.不支持流处理D.不能运行在YARN上答案：B二、判断题1.快速排序是一种不稳定的排序算法。（）A.正确B.错误答案：A2.归并排序是原地排序，不需要额外的存储空间。（）A.正确B.错误答案：B3.堆排序在最坏情况下的时间复杂度仍为O(nlog₂n)。（）A.正确B.错误答案：A4.简单选择排序的比较次数与待排序列的初始状态无关。（）A.正确B.错误答案：A5.基数排序属于比较类排序，通过两两比较确定元素次序。（）A.正确B.错误答案：B6.HDFS适合存储海量小文件，且小文件不会影响NameNode的性能。（）A.正确B.错误答案：B7.MapReduce中Shuffle阶段的主要作用是将Map输出按key进行分区、排序和分组后交给Reduce。（）A.正确B.错误答案：A8.Spark的RDD是只读的、可分区的分布式数据集，支持血统（Lineage）容错。（）A.正确B.错误答案：A9.所有NoSQL数据库都不支持事务。（）A.正确B.错误答案：B10.大数据的计算模式主要包括批处理与流处理两类。（）A.正确B.错误答案：A三、计算与算法题1.对序列{49,38,65,97,76,13,27,49}进行快速排序，写出以第一个元素为基准的一趟划分结果。答案：取基准pivot=49，设i从左、j从右向中间扫描：j从右找小于49的元素为27，与i位交换；i从左找大于49的元素为65，与j位交换；继续扫描，j停在13，i与j相遇于13处，基准49归位到第4个位置。一趟划分结果为：27,38,13,[49],76,97,65,49即基准49左侧{27,38,13}均小于49，右侧{76,97,65,49}均大于等于49，基准已到达最终位置，后续对左右两个子区间递归处理。2.将序列{49,38,65,97,76,13,27,49}建成大顶堆，写出建堆结果，并说明调整过程。答案：按层序存入数组a[1..8]，从最后一个非叶结点i=⌊8/2⌋=4开始向前筛选：i=4（97）：孩子为a[8]=49，97>49，不调整；i=3（65）：孩子13、27，均小于65，不调整；i=2（38）：孩子97、76，与较大者97交换→{49,97,65,38,76,13,27,49}，38下沉到位置4后与孩子49比较，再交换→{49,97,65,49,76,13,27,38}；i=1（49）：孩子97、65，与97交换→{97,49,65,49,76,13,27,38}，49下沉到位置2后与孩子49、76比较，与76交换→{97,76,65,49,49,13,27,38}。得到大顶堆：97,76,65,49,49,13,27,38（堆顶97为最大值，满足任一结点不小于其孩子）。3.对序列{49,38,65,97,76,13,27,49}进行二路归并排序，写出前两趟的结果。答案：初始：49|38|65|97|76|13|27|49（8个长度为1的有序段）第一趟（两两归并，段长2）：[38,49][65,97][13,76][27,49]第二趟（段长4）：[38,49,65,97][13,27,49,76]第三趟（段长8）：[13,27,38,49,49,65,76,97]，排序完成。归并排序时间