南京信息工程大学《数据结构与算法》2021-2022学年期末试卷

自觉遵守考场纪律如考试作弊此答卷无效密自觉遵守考场纪律如考试作弊此答卷无效密封线第1页，共3页南京信息工程大学

《数据结构与算法》2021-2022学年期末试卷院(系)_______班级_______学号_______姓名_______题号一二三总分得分一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、在一个具有n个节点的带权有向图中，若存在负权边，以下哪种最短路径算法可能不适用？A.迪杰斯特拉算法B.贝尔曼-福特算法C.弗洛伊德算法D.以上都适用2、已知一个带权有向图G=(V,E)，顶点集合V={1,2,3,4,5}，边集合E={(1,2,5),(1,3,3),(2,4,2),(3,4,6),(3,5,4),(4,5,1)}，采用迪杰斯特拉（Dijkstra）算法求从顶点1到顶点5的最短路径，经过的中间顶点依次为？（）A.2,4B.3,4C.2,3D.3,53、在一个用数组实现的循环队列中，若队头指针front=5，队尾指针rear=2，队列容量为10，则队列中的元素个数是多少？A.7B.6C.5D.44、在数据结构中，对于一个具有n个元素的有序数组，使用二分查找算法查找一个特定元素，其平均时间复杂度为（）A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)5、对于一个具有n个元素的哈希表，若采用链地址法处理冲突，以下关于查找操作的平均时间复杂度的描述，哪一项是正确的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)6、在一个顺序存储的循环队列中，队头指针front和队尾指针rear都指向同一个位置时，队列的状态可能是？（）A.队满B.队空C.既不满也不空D.以上都有可能7、对于一个具有n个元素的冒泡排序，在最坏情况下，需要进行多少次比较操作？（）A.n(n-1)/2B.nC.n+1D.n-18、以下哪种数据结构可以方便地实现字典操作（添加、删除、查找），且平均时间复杂度较低？A.数组B.链表C.二叉搜索树D.哈希表9、对于一个具有n个顶点和e条边的无向连通图，其生成树中边的条数为（）。A.nB.n-1C.eD.e-110、在一个具有n个元素的循环链表中，查找第i个元素（1<=i<=n），平均需要遍历的节点个数约为？A.n/2B.nC.2nD.n/411、设有一个广义表L=((a,b),c,(d,e))，其表头和表尾分别为？（）A.(a,b)和(c,(d,e))B.(a,b)和(c,d,e)C.((a,b))和(c,(d,e))D.((a,b))和(c,d,e)12、在数据结构中，块状链表结合了链表和数组的优点，以下关于块状链表的特点，描述不正确的是（）A.适合频繁的插入和删除操作B.可以提高随机访问的效率C.每个块内部是有序的D.空间复杂度比普通链表低13、对于一个采用顺序存储结构的完全二叉树，若已知根节点在数组中的位置为1，则其第i个节点的左孩子节点在数组中的位置为？A.2iB.2i+1C.i*2D.i*2-114、对于一个具有n个元素的双向循环链表，若要删除第i个节点（1<=i<=n），平均需要修改多少个指针？（）A.2B.3C.4D.515、对于一个具有n个节点的带权有向图，使用迪杰斯特拉算法求最短路径，其时间复杂度为？A.O(n)B.O(nlogn)C.O(n^2)D.O(n^3)16、在一个m行n列的二维数组中，按列优先存储时，元素aij的存储地址为？（）A.LOC(a11)+[(j-1)*m+(i-1)]*dB.LOC(a11)+[(i-1)*m+(j-1)]*dC.LOC(a11)+[(j-1)*n+(i-1)]*dD.LOC(a11)+[(i-1)*n+(j-1)]*d17、在二叉树中，判断两棵二叉树是否完全相同，以下方法不正确的是（）A.同时进行先序遍历，比较节点值B.同时进行中序遍历，比较节点值C.同时进行后序遍历，比较节点值D.比较两棵树的节点数量18、以下哪种数据结构常用于实现图的存储？A.邻接矩阵和邻接表B.二叉树和链表C.栈和队列D.数组和哈希表19、若一个链表的每个节点只包含数据域和指针域，且指针域只指向其后继节点，这种链表称为：A.单向链表B.双向链表C.循环链表D.静态链表20、已知一棵二叉树的先序遍历序列为ABCDEFG，中序遍历序列为CBAEDFG，则其后序遍历序列为？（）A.CBEFDAGB.CBEFDGAC.CBFEDGAD.CBFEGDA二、简答题（本大题共4个小题，共40分)1、（本题10分）在数据结构中，阐述如何使用线段树解决区间查询和更新问题，给出算法步骤和实现代码，并分析其性能优势。2、（本题10分）比较冒泡排序和堆排序在时间复杂度上的优劣。3、（本题10分）详细阐述在具有n个顶点的图中，如何使用迪杰斯特拉（Dijkstra）算法求解每对顶点之间的最短路径，并分析其时间复杂度。4、（本题10分）阐述如何在一个循环队列中实现元素的入队和出队操作，给出算法步骤和实现代码，并分析其时间复杂度和空间复杂