2017年北邮803数据结构考研真题及解析

"这是一份2017年北京邮电大学803数据结构考研真题，包含选择题和填空题，涉及数据结构的基础概念和算法分析。" 在数据结构的学习中，时间复杂度是衡量算法效率的重要指标。问题规模通常与时间复杂度直接相关，因为它决定了算法执行的基本操作次数。例如，在排序或查找算法中，问题规模通常指输入数据的数量。选择题第一题指出，A.问题规模是与算法时间复杂度有关的因素，而B.计算机硬件性能、C.编译程序质量和D.程序设计语言则不是直接影响时间复杂度的主要因素。 链表是一种常用的数据结构，用于存储动态集合。在第二题中，如果用单链表存储两个有序表并进行归并，最佳情况下每次比较即可确定一个元素的位置，因此最少的比较次数为n次，即B.n。归并排序的比较次数通常与待排序元素的数量有关，而不是元素本身的值。 队列是一种先进先出（FIFO）的数据结构，通常用于实现缓冲区。在第三题中，如果队列用单循环链表存储，插入和删除操作通常在链表头部和尾部进行，所以它们的时间复杂度都是O(1)，即A.O(1)、O(1)。 数组的存储空间计算涉及元素数量、数组维度以及每个元素的大小。第四题中，三维数组A[1..15][0..9][-3..6]的总存储空间为15 * 10 * 10 * 5 = 7500个存储单元，因此答案是D.7500。 树是一种非线性数据结构，高度代表了从根节点到最远叶子节点的最长路径。第五题中，一棵具有n个结点的树，高度最小为1（完全二叉树），最大为n（退化成链表的树）。 树的存储方式多种多样，如孩子链表表示法、双亲表示法、孩子兄弟表示法等，但不包括C.按层次的顺序存储表示法，因为按层次顺序存储通常指的是队列或广度优先搜索。 强连通图是指图中任意两个顶点都互相可达的有向图。第六题提到，具有n个顶点的强连通图，边数最多是n(n-1)，因为每个顶点都可以指向其他n-1个顶点，故答案是C.n(n-1)。 在图的性质中，第七题提到强连通图的边数最多是n(n-1)，而第八题中，正确的是C.连通分量是无向图中的极小连通子图，其他选项描述的性质并不总是成立。 查找算法中，第九题提到折半查找（二分查找）通常比顺序查找比较次数少，因为在有序表中，折半查找每次可以缩小一半的搜索范围。 排序算法的稳定性是指排序过程中相等元素的相对位置保持不变。第十题中，B.希尔排序的实质是多次利用直接插入排序，希尔排序是一种不稳定的排序算法，而A选项描述的是算法的渐进时间复杂度，不是稳定性。 这些题目覆盖了数据结构的基础知识，包括时间复杂度、链表操作、数组存储、树的性质、图的理论以及排序和查找算法，这些都是学习数据结构时必须掌握的核心概念。