第 1 页 共 4 页 昆明理工大学 2021 年硕士研究生招生入学考试试题 (A卷 ) 考试科目代码： 877 考试科目名称 ： 数据结构与算法分析 考生答题须知 1 所有题目（包括填空、选择、图表等类型题目）答题答案必须做在考点发给的答题纸上，做在本试题册上无效。 请考生务必在答题纸上写清题号。 2 评卷时不 评阅本试题册，答题如有做在本试题册上而影响成绩的，后果由考生自己负责。 3 答题时一律使用蓝、黑色墨水笔或圆珠笔作答（画图可用铅笔），用其它笔答题不给分。 4 答题时不准使用涂改液等具有明显标记的涂改用品。 一、单项选择题（每小题 3分，共 60 分 ） 1.以下数据结构中哪一个是非线性结构？ ( ) A. 队列 B. 栈 C. 线性表 D. 二叉树 2从逻辑关系来看，数据元素的直接前驱为 0个或 1个的数据结构只能是（ ） A线性结构 B.树形结构 C.线性结构和树型结构 D.线性结构和图状结构 3数据的四种基本存储结构是指（ ） A.顺序存储结构、索引存储结构、直接存储结构、倒排存储结构 B顺序存储结构、索引存储结构、链式存储结构、散列存储结构 C顺序存储结构、非顺序存储结构、指针存储结构、树型存储结构 D.顺序存储结构、链式存储结构、树型存储结构、图型存储结构 4下面程序的时间复杂为 （ ） s=0; for（ i=1； i=n； i+） t=1； for(j=1； j=i； j+) t=t*j； s=s+t； A. O(n) B.O(n2) C. O(n3) D. O(n4) 5. 链式存储结构的最大优点是（ ）。 A.便于随机存取 B.存储密度高 C.需 要 预分配空间 D.便于进行插入和删除操作 6. 假设在顺序表 a0,a1, ,an 1中，每一个数据元素所占的存储单元的数目为 4，且 a0的存储 地址为 100，则数据元素 a7的存储地址是（ ）。 A 106 B. 107 C.124 D.128 7. 在链表中 若 经常要删除表中最后一个结点或在最后一个结点之后插入一个新结点，则宜采用 （ ）存储方式。 A. 顺序表 B. 用头指针标识的循环单链表 C. 用尾指针标识的循环单链表 D. 双向链表 第 2 页 共 4 页 昆明理工大学 2021 年硕士研究生招生入学考试试题 8若已知一个栈的进栈序列是 1， 2， 3， n，其输出序列为 p1， p2， p3， .， pn，若 p1 3， 则 p2( )。 A 可能是 2 B 一定是 2 C 可能是 1 D 一定是 1 9. 用链表方式存储的队列，在进行删除运算时（ ）。 A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改 10.循环队列的队满条件为 ( ) A. (sq.rear+1) % maxsize =(sq.front+1) % maxsize; B. (sq.front+1) % maxsize =sq.rear C. (sq.rear+1) % maxsize =sq.front D.sq.rear =sq.front 11. 数组 A0.5,0.6的每个元素占五个字节，将其按列优先次序存储在起始地址为 1000 的内 存单元中，则元素 A5， 5的地址是 ( )。 A. 1175 B. 1180 C. 1205 D. 1210 12. AN， N是对称矩阵，将下三角（包括对角线）矩阵以行序存储到一维数组 TN(N+1)/2中， 则对任一上三角元素 aij对应 Tk的下标 k是（ ）。 A. i(i-1)/2+j B. j(j-1)/2+i C. i(j-i)/2+1 D. j(i-1)/2+1 13若一棵二叉树具有 10 个度为 2 的结点， 5个度为 1的结点，则度为 0的结点个数是（ ） A 9 B 11 C 15 D不确定 14二叉树的第 k 层上最多含有结点数为（ ） A 2k B 2k-1-1 C 2k-1 D 2k -1 15.设有无向图 G=（ V， E）和 G =（ V,E ） ,如 G 为 G的生成树，则下面不正确的说法是（ ） A G 为 G的子图 B G 为 G的连通分量 C G 为 G的极小连通子图且 V =V D G 是 G的无环子图 16下面哪一方法可以判断出一个有向图是否有环（回路）： A深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径 17比较次数与排序的初始状态无关的排序方法是 ( )。 A直接插入排序 B起泡排序 C快速排序 D直接选择排序 18对一组数据（ 84， 47， 25， 15， 21）排序，数据的排列次序在排序的过程中的变化为 1 84 47 25 15 21 2 15 47 25 84 21 3 15 21 25 84 47 4 15 21 25 47 84 则采用的排序是 ( )。 A. 选择 B. 冒泡 C. 快速 D. 插入 19适用于折半查找的表的存储方式及元素排列要求为 ( ) A链接方式存储，元素无序 B链接方式存储，元素有序 C顺序方式存储，元素无序 D顺序方式存储，元素有序 第 3 页 共 4 页 B A C E D F 昆明理工大学 2021年硕士研究生招生入学考试试题 20下图所示的 4 棵二叉树 ,( )是平衡二叉树。 A B C D 二、简答题（每小题 10分，共 70 分） 1. 简 述分治法的基本思想和动态规划 法所运用的最优化原理 。 2分别给出下图所示二叉树的前序、中序和后序遍历结果。 3将下列由二棵树组成的森林转换为二叉树。 4 已知一个无向图如下图所示，要求用 Prime算法生成最小 生成 树（假设以为起点，试画出 构造过程）。 5. 设有一组关键字 9,01,23,14,55,20,84,27，采用哈希函数： H（ key） =key mod 7 ，表长为 10，用开放地址法的二次探测再散列方法 Hi=(H(key)+di) mod 10(di=12,-12,22, -22,) 解决冲 突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。 散列地址 0 1 2 3 4 5 6 7 8 9 关键字 1 2 6 5 4 3 20 10 11 6 6 18 10 14 5 9 A B E C D F 第 4 页 共 4 页 昆明理工大学 2021年硕士研究生招生入学考试试题 6. 输入一个正整数序列（ 53,17,12,66,58,70,87,25），请按次序构造一棵二叉排序树。 7对于给定的一组键值： 66， 42， 63， 15， 90， 35，分别画出应用直接插入排序进行排序中各 趟的结果。 三、综合题（ 20分） 输入一个整数 n,写出计算 1+2+3+ +n 的递归算法并分析算法的时间复杂度 ，写非递归算法不 给分 。