2015年山东青岛大学数据结构考研真题.doc

发布时间：2023-11-14 发布人：admin 分类：说明书资料大小：0.11M 资料格式：doc 举报版权申诉

第1页 / 共5页

第2页 / 共5页

第3页 / 共5页

第4页 / 共5页

第5页 / 共5页

文本预览

2015 年山东青岛大学数据结构考研真题一、单项选择题（本大题共 10 道小题，每小题 2 分，共 20 分） 1．数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象，以及它们之间的（）和运算的学科。 A．逻辑存储 B．关系 C．算法 D．数据映像 2．下列函数中渐近时间复杂度 T(n)最小的是（）。 A．T(n)=-10n-5000n2 B．T(n)=300000n2-60n C．T(n)=10000000 D．T(n)=-1000*2log2n-100n 3．在计算机的存储器中表示时，物理地址和逻辑地址相同并且是连续的，称之为（）。 A．逻辑结构 B．物理结构 C．顺序存储结构 D．链式存储结构 4．有六个元素｛6，5，4，3，2，1｝，依次顺序进栈，下列哪一个不是正确的出栈序列？（）。 A．543612 B.453216 C.346521 D.234156 5．循环队列存储在数组 Q[MAX]中，则入队列时的操作为（）。 A．rear=rear+1 B．rear=(rear+1)MOD(MAX-1) C．rear=(rear+1)MODMAX D．rear=(rear+1)MOD(MAX+1) 6．若一棵二叉树具有 8 个度为 2 的结点，4 个度为 1 的结点，则度为 0 的结点个数是（）。 A．8 B．9 C．12 D．13 7．用顺序存储的方法将完全二叉树中所有结点逐层存放在数组 R[1..n]中，结点 R[i]若有双亲结点，则双亲结点是（）。 A．R[i/2] B．R[2i] C．R[2i+1] D．R[2i-1] 8．下列哪一种图的邻接矩阵是对称矩阵？（）。

A．AOV 网 B．AOE 网 C．有向图 D．无向图 9．对线性表进行二分查找时，要求线性表必须（） A．以顺序方式存储 B．以顺序方式存储，且数据元素有序 C．以链接方式存储 D．以链式方式存储，且数据元素有序 10．内部排序方法的稳定性是指（）。 A．该排序算法不允许有相同的关键字记录 B．该排序算法允许有相同的关键字记录 C．平均时间为 O（nlogn）的排序方法 D．以上都不对二、简答题（本大题共 6 道小题，每题 5 分，共 30 分） 1．描述以下 3 个概念的区别：头指针、头结点、第一个结点（首结点）。 2．简述栈和队列的特点。 3．列出先序遍历能得到 ABC 序列的所有不同的二叉树。 4．简要说明深度优先搜索法(DFS)和广度优先搜索法（BFS）的不同之处。 5．如果有一组关键字，以不同的次序输入后建立起来的二叉排序树是否相同？当中序遍历这些二叉排序树时，其遍历的结果是否相同？为什么？ 6．简要说明 Shell（希尔）排序的基本思想。三、综合应用题（本大题共 4 道小题，其中第 1 题、第 2 题和第 4 题每题 12 分，第 3 题 14 分，共 50 分） 1．根据下图所示的二叉树，回答以下问题： (1)写出前序序列、中序序列和后序序列。 (2)画出该二叉树的中序线索二叉树。 (3)画出该二叉树对应的森林。 2．对给定的下图，求解下列问题： (1)写出该图的邻接表。 (2)写出全部拓扑排序。

3．设哈希（Hash）函数为：H（key）=keyMODl4，其中 key 为关键字（整数），MOD 为取模运算。用线性探测再散列法处理冲突，在地址范围为 0～14 的散列区中，试用关键字序列{19， 27，26，28，29，40，64，21，15，12）构造一个哈希表，回答下列各题： (1)画出该哈希表的存储结构图。 (2)若查找关键字 40，必须依次与表中哪些关键字比较大小？ (3)假设每个关键字的查找概率相同，试求查找成功的平均查找长度。 4．设记录的关键字集合 key={49，38，66，90，75，10，20}。 (1)写出快速排序第一趟和第二趟之后的状态。 (2)把关键字集合 key 调整成堆顶元素取最小值的堆。四、算法分析题（本大题共 3 道小题，每题 10 分，共 30 分） 1．下面的算法是对单链表进行的插入算法，请在空白处填入正确的语句。 2．阅读下面的代码，试说明算法的功能。

3．对于给定的二叉排序树 T，对于给出的正整数 x，下面算法实现了将 data 域之值小于等于 x 的结点全部删除掉。请在空白处填入正确的语句。

五、算法设计题（本大题共 2 道小题，每题 10 分，共 20 分） 1．已知一个带头结点的单链表 L，试编写算法：清空单链表。StatusClearList(LinkListL) {//初始条件：线性表 L 已存在。操作结果：将 L 重置为空表 2．设二叉树用二叉链表表示，设计算法，求二叉树的度为 2 的结点数。

分享到：

赞收藏

资料库

2015年山东青岛大学数据结构考研真题.doc

相关推荐

考研

热门标签

最新资料