第 1页，共 5 页青岛大学 2017年硕士研究生入学考试试题科目代码： 910 科目名称：数据结构（共 5 页）请考生写明题号，将答案全部答在答题纸上，答在试卷上无效一、单项选择题（本大题共10 道小题，每小题2 分，共 20 分）1．计算机算法指的是（）。A．计算方法B. 排序方法C. 解决问题的步骤序列D. 存储结构2．链表不具有的特点是（） 。A．插入、删除不需要移动元素B．可随机访问任一元素C．不必事先估计存储空间D．所需空间与线性长度成正比3．连续存储设计时，存储单元的地址（） 。A．一定连续B．一定不连续C．不一定连续D．部分连续，部分不连续4．一个递归算法必须包括（） 。A. 递归部分B. 终止条件和递归部分C. 迭代部分D. 终止条件和迭代部分5．栈和队列的共同点是（） 。A. 都是先进先出B. 都是先进后出C. 只允许在端点处插入和删除元素D. 没有共同点6．任何一棵二叉树的叶子结点在先序、中序和后序遍历中的相对次序（）。A．不发生改变B．发生改变C．不能确定D．以上都不对7．由带权为 {8 ，2，5，7}的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（）。A．23B．37C．46D 438．若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（）图。A．非连通B．连通C．强连通D．有向9．适用于折半查找的表的存储方式及元素排列要求为（）。A．链接方式存储，元素无序B．链接方式存储，元素有序第 2页，共 5 页C．顺序方式存储，元素无序D．顺序方式存储，元素有序10．对 n 个关键字作快速排序，在最坏情况下，算法的时间复杂度是（）。A．O(n)B．O(n2)C．O(nlog2n)D．O(n3)二、简答题（本大题共6 道小题，每题5 分，共 30 分）1．如果有n 个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？为什么？2．有 5 个元素，其入栈次序为： A，B，C，D，E，在各种可能的出栈次序中，以元素 C，D 最先出栈（即C 第一个且D 第二个出栈）的次序有哪几个？3．简述树与二叉树的转化方法。试举一个例子说明。4．简要说明图的各种遍历方法。5．简述顺序查找和折半查找的优缺点。6．简要说明归并排序的基本思想。三、综合应用题（本大题共4 道小题，每题12 分，共 48 分）1．已知一棵二叉树的中序遍历序列为BCAFEC ，后序遍历序列为CBECFA，试画出该二叉树，并给出该二叉树的先序序列。2...
