北京邮电大学数据结构期末考试试卷（含详细答案）

北京邮电大学数据结构期末考试试卷（含详细答案）适用专业：计算机类、电子信息类相关专业考试时长：120分钟满分：100分考试说明：闭卷考试，严禁携带资料，所有答案写在答题纸上，试卷作答无效一、单项选择题（共15题，每题2分，共30分）1.下列关于算法特性的描述，错误的是（）A.有穷性：算法必须在有限步骤、有限时间内结束B.确定性：每一步操作都有唯一确定的含义C.可行性：操作均可通过基本运算实现D.输入性：算法必须至少有一个输入2.在长度为n的顺序表中删除第i个元素（1≤i≤n），需要移动的元素个数为（）A.n-iB.n-i+1C.iD.n3.带头结点的单链表为空的判定条件是（）A.head==NULLB.head->next==NULLC.head->next==headD.任意条件均可4.栈和队列的共同特点是（）A.都是先进先出B.都是先进后出C.只允许在端点处插入和删除元素D.没有共同点5.若一个栈的输入序列为1,2,3,4，不可能得到的输出序列是（）A.4,3,2,1B.2,1,4,3C.3,1,2,4D.1,2,3,46.串“ababc”的next数组值（经典KMP算法）为（）A.0,1,1,2,3B.0,1,2,1,2C.1,2,1,2,3D.0,0,1,2,17.深度为k的完全二叉树，最多包含的结点个数为（）A.2^kB.2^k-1C.2^(k-1)D.2^(k-1)-18.已知二叉树后序遍历序列为FDEBGCA，中序遍历序列为FDBEACG，则前序遍历序列为（）A.ABDFECGB.ABDEFCGC.ABDFEGCD.ADBFECG9.下列存储结构中，可用于存储稀疏图的是（）A.邻接矩阵B.邻接表C.顺序表D.哈希表10.具有n个顶点的连通无向图，至少包含的边数为（）A.n-1B.nC.n+1D.n(n-1)/211.对序列{28,16,32,12,22,1,36}进行从小到大冒泡排序，第一趟排序后的结果是（）A.16,28,12,22,1,32,36B.16,12,22,1,28,32,36C.1,12,16,22,28,32,36D.28,32,36,16,22,12,112.下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(nlogn)的是（）A.快速排序B.归并排序C.冒泡排序D.直接插入排序13.哈希查找中，若采用线性探测法解决冲突，可能出现的问题是（）A.堆积现象B.溢出现象C.查找失败D.哈希函数失效14.平衡二叉树的平衡因子的取值范围是（）A.[-1,0,1]B.[0,1,2]C.[-2,-1,0]D.任意整数15.下列数据结构中，属于非线性结构的是（）A.顺序表B.栈C.二叉树D.队列二、填空题（共10空，每空2分，共20分）1.数据结构的三要素是________、________、数据的运算。2.循环队列中，判断队列满的条件（少用一个存储空间）是________。3.二叉树的第i层最多有________个结点（i≥1）。4.有向图的邻接矩阵中，第i行非零元素的个数表示顶点i的________。5.拓扑排序适用于________结构的图。6.堆排序的时间复杂度为________，空间复杂度为________。7.二分查找的前提是________。8.线索二叉树的作用是________。三、简答题（共3题，每题6分，共18分）1.简述顺序存储结构和链式存储结构的优缺点及适用场景。2.简述快速排序的基本思想，并说明其最好、最坏、平均时间复杂度。3.简述Prim算法和Kruskal算法求解最小生成树的核心区别及适用场景。四、算法应用题（共2题，每题8分，共16分）1.已知一组关键字序列：{10,22,31,15,68,72,45}，哈希表长度为11，哈希函数为H(key)=key%11，采用线性探测法解决冲突，构造哈希表，并计算成功查找的平均查找长度。2.给定二叉树的中序序列：DBEAFC，后序序列：DEBFCA，画出该二叉树的树形结构，并写出前序遍历序列。五、编程算法题（共1题，16分）编写C语言算法，实现带头结点单链表的逆置。要求：（1）写出算法设计思路；（4分）（2）写出完整可运行的核心代码；（10分）（3）分析算法的时间复杂度和空间复杂度。（2分）详细参考答案及解析一、单项选择题答案及解析1.D解析：算法可以零个输入，例如固定输出常量的算法，其余三项均为算法必备特性。2.A解析：删除第i个元素，后方n-i个元素依次向前移动一位。3.B解析：带头结点单链表，头结点后继为空则链表无数据结点。C为循环单链表空表条件。4.C解析：栈仅允许栈端操作，队列仅允许队头队尾操作，均为端点受限操作。5.C解析：输入1234，3先出栈则1、2必在栈中，后续只能2先出，无法出现3,1,2的序列。6.A解析：串ababc的next数组：下标1-5对应值0,1,1,2,3，符合KMP经典求解规则。7.B解析：深度为k的满二叉树结点数最多，为2^k-1，完全二叉树结点数不超过满二叉树。8.A解析：由中序、后序序列还原二叉树，根节点为A，逐层划分左右子树，最终前序序列为ABDFECG。9.B解析：稀疏图边数少，邻接表仅存储有效边，节省空间；邻接矩阵空间固定，适合稠密图。10.A解析：n个顶点连通无向图的最小结构为生成树，边数为n-1。11.A解析：冒泡排序第一趟从前往后两两比较，将最大值36冒泡至末尾，得到序列16,28,12,22,1,32,36。12.B解析：归并排序无论数据初始有序与否，时间复杂度恒为O(nlogn)；快速排序最坏为O(n²)。13.A解析：线性探测法会导致冲突元素连续聚集，产生堆积现象，降低查找效率。14.A解析：平衡二叉树任意结点左右子树高度差绝对值不超过1，平衡因子取值-1、0、1。15.C解析：线性结构包含顺序表、栈、队列，树、图属于非线性结构。二、填空题答案1.逻辑结构、存储结构2.(rear+1)%maxsize==front3.2^(i-1)4.出度5.有向无环图（DAG）6.O(nlogn)、O(1)7.有序的顺序存储结构8.避免遍历递归/栈操作，提升二叉树遍历效率，快速查找结点前驱后继三、简答题参考答案1.顺序存储与链式存储对比顺序存储：优点是存储空间连续、随机访问效率高、无需额外指针开销；缺点是插入删除需移动大量元素，空间固定易溢出或浪费。适用于数据元素个数固定、频繁查找、极少增删的场景，如数组、静态表。链式存储：优点是动态分配空间，插入删除仅修改指针，无需移动元素；缺点是仅支持顺序访问，每个结点存在指针开销。适用于数据个数动态变化、频繁增删、查找操作少的场景，如链表、树、图。2.快速排序核心思想与复杂度基本思想：分治思想。选取一个基准元素，将待排序序列划分为左右两个子序列，左侧元素均小于基准，右侧元素均大于基准，再递归对两个子序列进行排序，直至整个序列有序。复杂度：最好时间复杂度O(nlogn)（基准划分均匀）；最坏时间复杂度O(n²)（序列已有序/逆序，划分极度不均）；平均时间复杂度O(nlogn)；空间复杂度O(logn)（递归栈开销）。3.Prim与Kruskal算法区别核心区别：Prim算法以顶点为核心，从单个顶点出发，每次选取连接生成树内外的最小权值边，逐步扩展生成树；Kruskal算法以边为核心，将所有边按权值排序，依次选取不构成环的最小权值边，直至覆盖所有顶点。适用场景：Prim算法适合稠密图（顶点少、边多）；Kruskal算法适合稀疏图（顶点多、边少）。四、算法应用题答案1.哈希表构造及平均查找长度计算哈希函数H(key)=key%11，表长11，线性探测解决冲突各关键字哈希值计算：10%11=10、22%11=0、31%11=9、15%11=4、68%11=2、72%11=6、45%11=1无冲突，哈希表存储结构（下标0-10）：0:22、1:45、2:68、3:空、4:15、5:空、6:72、7:空、8:空、9:31、10:10成功查找次数：每个元素均一次查找成功平均查找长度ASL=(1+1+1+1+1+1+1)/7=12.二叉树还原与遍历序列推导过程：后序最后一个元素A为根节点；中序划分得左子树DBE、右子树FC。左子树后序DEB，中序DBE，得B为左子树根，D为左孩子、E为右孩子；右子树后序FC，中序FC，得C为右孩子、F为C左孩子。前序遍历序列：ABDECF（树形结构：根A，左孩子B、右孩子C；B左D、右E；C左F）五、编程算法题答案（1）算法设计思路采用三指针迭代法逆置单链表。定义前驱结点、当前结点、后继结点三个指针，遍历链表，逐个反转当前结点的指向，将当前结点的next指针指向前驱结点，遍历结束后修改头结点后继，完成链表整体逆置。该方法无需递归，无额外空间开销，效率较高。（2）核心C语言代码c

#include<stdio.h>

#include<stdlib.h>

//定义单链表结点结构

typedefstructLNode{

intdata;

structLNode*next;

}LNode,*LinkList;

//链表逆置函数

voidReverseList(LinkListhead){

//空表或单结点无需逆置

if(head==NULL||head->next==NULL)return;

LNode*pre=NULL;//前驱结点

LNode*cur=head->next;//当前结点

LNode*nex=NULL;//后继结点

while(cur!=NULL){

nex=cur->next;//保存后继结点

cur->next=pre;//反转指针

pre=cur;//前驱后移

cur=nex;//当前结点后移

}

head->next=pre;//头结点指向新的首结点

}

//尾插法创建链表（测试用）

voidCreateList(LinkListhead,intarr[],intn){

LNode*tail=head;

for(inti=0;i<n;i++){

LNode*p=(LNode*)malloc(sizeof(LNode));

p->data=arr[i];

p->next=NULL;

tail->next=p;

tail=p;

}

}

//遍历输出链表（测试用）

voidPrintList(LinkListhead){

LNode*p=head->next;

while(p!=NULL){

printf("%d",p->data);

p=p->next;

}

printf("\n");

}

intmain(){

LinkListhead=(LNode*)malloc(sizeof(LNode));

head->next=NULL;

intarr[]={1,2,3,4,5};

intn=sizeof(arr)/sizeof(arr[0]);