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

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

第1页 / 共4页

第2页 / 共4页

第3页 / 共4页

第4页 / 共4页

文本预览

2016 年山东青岛大学数据结构考研真题一、单项选择题（本大题共 10 道小题，每小题 2 分，共 20 分） 1．一个算法具有（）等特点。 A．快速性 B．至少有一个输入量 C．确定性 D．健壮性 2．下列函数中渐近时间复杂度 T(n)最小的是（）。 A．T(n)= B．T(n)= C．T(n)= D．T(n)= 3．在计算机的存储器中表示时，物理地址和逻辑地址相同并且是连续的，称之为（）。 A．逻辑结构 B．顺序存储结构 C．链式存储结构 D．以上都对 4．若让元素 1，2，3，4，5 依次进栈，则出栈次序不可能出现在（）种情况。 A．5，4，3，2，1 B．2，1，5，4，3 C．4，3，1，2，5 D．2，3，5，4，1 5．设栈 S 用顺序存储结构表示，则栈 S 为空的条件是（）。 A．S.top-S.base!=0 B．S.top-S.base==0 C．S.top-S.base!=n D．S.top-S.base==n 6．一棵完全二叉树上有 1001 个结点，其中叶子结点的个数是（）。 A．500 B．501 C．250 D．251 7．任何一棵二叉树的叶子结点在先序、中序和后序遍历中的相对次序（）。 A．不发生改变 B．发生改变 C．不能确定 D．以上都不对

8．用邻接表表示图进行广度优先遍历时，通常借助（）来实现算法。 A．栈 B.队列 C.树 D．图 9．折半查找法和二叉排序树的时间性能（）。 A．与处理数据量有关 B．相同 C．不相同 D．不确定 10．对 n 个不同的关键字由小到大进行冒泡排序，在下列（）情况下比较的次数最多。 A．从小到大排列好的 B．从大到小排列好的 C．元素无序 D．元素基本有序二、简答题（本大题共 6 道小题，每题 5 分，共 30 分） 1．一般情况下，线性表可以采用哪几种存储结构？请分别叙述每一种存储结构的构造原理与特点。 2．内存中一片连续空间（不妨假设地址从 0 到 m-1）提供给两个栈 S1 与 S2 使用，怎样分配这部分存储空间，使得对任一个栈仅当这部分空间全满时才发生上溢。 3．简述遍历二叉树的含义及常见的方法。 4．简要说明图的邻接表的构成。 5．简述二叉排序树的插入算法思想（步骤）。 6．简要说明快速排序的基本思想。三、综合应用题（本大题共 5 道小题，每题 10 分，共 50 分） 1．给定二叉树的先序遍历序列和后序遍历序列，能否重构该二叉树？若能，试证明之，否则给出反例。 2．有 4 个顶点 A、B、C、D 的无向连通图。按广度优先和深度优先搜索遍历结果都为 A、B、 C、D，画出所有可能的结构图。 3．设有一组关键字{17，13，14，153，29，35}需插入到表长为 12 的 Hash 表中，请回答以下问题： (1)设计一个适合该 Hash 表的 Hash 函数； (2)使用你所设计的 Hash 函数将上述关键字插入到 Hash 表中，画出其结构（使用线性探测法解决冲突）。 4．某整型数组 A 的 10 个元素值依次为：{6、2、9、7、3、8、4、5、0、10}，用下列各排序方法，将 A 中元素由小到大排序。 (1)取第一个元素 6 作为枢轴，试写出快速排序第一趟排序的结果。 (2)用堆排序（用大根堆，即堆顶元素取最大值），试写出将第一个选出的数据放在 A 的最后位置上，将 A 调整成堆后的 A 中结果。 5．已知信息为“OPQRPQRQPRPOQP”，请按此信息构造哈夫曼树，求出每个字符的最优编码。四、算法分析题（本大题共 3 道小题，每题 10 分，共 30 分） 1．下面的算法是对在顺序线性表 L 的第 i 个元素之前插入新的元素 e，请在空白处填入正确的语句。

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

五、算法设计题（本大题共 2 道小题，每题 10 分，共 20 分） 1．将一带头结点的单链表 head 逆置。要求：逆置在原链表进行，不允许构造一个链表。 voidLink_Reverse(LinkList&head) { 2．设二叉树用二叉链表表示，设计算法，求二叉树的高度。

分享到：

赞收藏

资料库

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

相关推荐

考研

热门标签

最新资料