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

装订线装订线PAGE2第1页，共3页南京信息工程大学

《数据结构Ⅲ》2021-2022学年期末试卷院(系)_______班级_______学号_______姓名_______题号一二三总分得分批阅人一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、设有一个链栈，栈顶指针为top，若要在栈顶插入一个新元素，则需要执行的操作是（）。A.s->next=top;top=s;B.top->next=s;top=s;C.s->next=top->next;top->next=s;D.top=s;s->next=NULL;2、在一个具有n个顶点和m条边的无向图中，若采用邻接表存储，则存储空间复杂度主要取决于？A.nB.mC.n+mD.n^23、在一个具有n个元素的最小堆中，删除堆顶元素后，为了恢复堆的性质，需要进行的调整操作的时间复杂度为（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)4、二叉树的性质和遍历方式可以用于解决很多实际问题，以下关于它们的应用的说法中，错误的是？（）A.二叉搜索树可以用于实现高效的查找、插入和删除操作。B.平衡二叉树可以用于解决二叉搜索树的不平衡问题，提高查找效率。C.二叉树的遍历方式可以用于实现二叉树的复制、遍历和序列化等操作。D.二叉树的性质和遍历方式只适用于理论研究，在实际应用中没有实际价值。5、若要从一个具有n个元素的有序单链表中删除所有值重复的元素，使得链表中每个元素的值都不同，最优的算法时间复杂度是？（）A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)6、对于单链表，若要访问链表中的第i个元素，必须从链表的头指针开始依次遍历，平均时间复杂度为O(n)。那么如果要在链表的末尾添加一个新元素，时间复杂度是多少？（）A.O(1)B.O(n)C.O(logn)D.O(nlogn)7、在一个具有n个元素的有序数组中，使用二分查找查找一个不存在的元素，其时间复杂度为：A.O(logn)B.O(n)C.O(nlogn)D.O(n^2)8、在一个具有n个顶点的有向完全图中，边的数量为：A.n(n-1)/2B.n(n-1)C.n^2D.2n(n-1)9、以下哪种排序算法的空间复杂度最低？A.归并排序B.快速排序C.冒泡排序D.插入排序10、以下哪种数据结构能够在O(1)的时间复杂度内实现元素的随机访问？（）A.链表B.队列C.栈D.数组11、在一个用邻接矩阵存储的无向图中，若要删除一条边，需要修改矩阵中的几个元素？A.1个B.2个C.3个D.4个12、哈希表的冲突解决方法有多种，以下关于它们的说法中，错误的是？（）A.开放定址法是一种常用的冲突解决方法，它通过在哈希表中寻找下一个空闲位置来解决冲突。B.链地址法是另一种常用的冲突解决方法，它将冲突的元素存储在链表中。C.再哈希法是通过使用不同的哈希函数来解决冲突。D.哈希表的冲突解决方法只有开放定址法和链地址法两种。13、若要对一个具有n个元素的数组进行归并排序，需要额外的辅助空间大小为？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)14、图是一种复杂的数据结构。在有向图中，顶点的入度是指指向该顶点的边的数量。若要计算一个有向图中所有顶点的入度，哪种算法较为合适？A.深度优先搜索B.广度优先搜索C.拓扑排序D.以上都可以15、对于一个栈，进行入栈和出栈操作时，以下哪种情况会导致栈溢出？A.入栈元素过多B.出栈元素过多C.连续进行入栈操作且存储空间已满D.连续进行出栈操作且栈为空16、在一个链式存储的线性表中，若要删除第i个元素（1<=i<=n），需要找到其前驱节点的时间复杂度为？（）A.O(1)B.O(n)C.O(logn)D.O(nlogn)17、已知一个有序表为{11,22,33,44,55,66,77,88,99}，使用折半查找法查找值为77的元素，需要比较的次数是（）。A.1B.2C.3D.418、以下哪种数据结构常用于实现优先级队列？A.链表B.队列C.栈D.堆19、对于一个满二叉树，若其高度为h，则其节点总数为多少？（）A.2^h-1B.2^(h-1)C.2^hD.2^(h+1)-120、在一个具有n个顶点和e条边的无向图中，使用克鲁斯卡尔（Kruskal）算法生成最小生成树。以下关于该算法的时间复杂度的描述，哪一项是正确的？A.O(nlogn)B.O(eloge)C.O(elogn)D.O(n^2)二、简答题（本大题共4个小题，共40分)1、（本题10分）对于一个用邻接表存储的有向图，详细阐述如何进行深度优先遍历和广度优先遍历，给出两种遍历算法的步骤和实现代码框架。2、（本题10分）详细说明如何在一个有序链表中删除重复元素，只保留一个，给出算法步骤和实现代码，并分析其时间复杂度。3、（本题10分）详细说明在插入排序中，对于近乎有序的数组，其性能表现为何较好。4、（本题10分）解释如何在一个链表中实现插入排序的优化，给出算法步骤和实现代码，并分析其性能改进。三、设计题