资源描述
第 页（共 3 页）1青 岛 科 技 大 学二一六年硕士研究生入学考试试题考试科目：数据结构注意事项：1本试卷共三道大题（共计 23 个小题） ，满分 150 分；2本卷属试题卷，答题另有答题卷，答案一律写在答题卷上，写在该试题卷上或草纸上均无效。要注意试卷清洁，不要在试卷上涂划；3必须用蓝、黑钢笔或签字笔答题，其它均无效。 一、选择题(每个 2 分，共 30 分)1、在长度为 n 的顺序表的第 i(1i n+1)个位置上删除一个元素，移动元素的个数为( ) 。A. i-1 B .n-i+1 C. i D. n-i 2、以下哪一个术语与数据的逻辑结构无关？（ ）A哈希表 B. 栈 C. 二叉树 D. 线性表3、下面程序段的时间复杂度为_。 for(int i=0; i=1）的满三叉树中，结点总数为（ ） 。 A. 3k B. 3k-1 C . （3 k-1）/3 D. （3 k-1）/28、AVL 树是一种平衡的二叉排序树，树中任一结点的( ) 。A. 左、右子树高度差的绝对值不超过 1 B. 左、右子树的高度均相同C. 左子树的高度均大于右子树的高度 D. 左子树的高度均小于右子树的高度 第 页（共 3 页）29、若一个栈的输入序列为 1,2,3,n，输出序列的第一个元素是 i，则第 j 个输出元素是（ ） 。A. i-j-1 B. 不确定的 C. j-i+1 D. i-j10、适用于折半查找的表的存储方式及元素排列要求为( ) 。A链接方式存储，元素无序 B链接方式存储，元素有序C顺序方式存储，元素无序 D顺序方式存储，元素有序11、设哈希表长为 14，哈希函数是 H(key)=key%11,表中已有数据的关键字为 15，38，61，84共四个，现要将关键字为 49 的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是( )。A9 B3 C5 D 812、设单链表中指针 p 指向结点 m，若要删除 m 之后的结点（若存在） ，则需修改指针的操作为（ ） 。Ap=p-next Bp-next=p-next-next Cp=p-next-next Dp-next=p13、对序列15，9，7，8，20 ，-1 ，4进行排序，进行一趟后数据的排列变为4，9，-1，8，20，7，15；则采用的是（ ）排序。A. 选择 B. 快速 C. 冒泡 D. 希尔14、关键路径是事件结点网络中的（ ） 。A从源点到汇点的最长路径 B从源点到汇点的最短路径C最长的回路 D最短的回路15、在含有 n 个结点的二叉树中有（ ）个分支。A. n B. n-1 C. n+1 D.（n+1）/2二、应用题（60 分）1 （12 分）回答下列问题：1 什么是数据结构？2 对于数据结构一般包含哪三个方面的讨论？3 在编制管理通讯录的程序时，通讯录数据采用什么样的数据结构合适？4 对于第问，存储结构采用什么样的结构合适？为什么？2 （12 分）数组 A 中，每个元素 Ai,j的长度均为 32 个二进位 ,行下标从-1 到 9，列下标从 1 到11，从首地址 S 开始连续存放主存储器中，主存储器字长为 16 位。求： 存放该数组所需多少单元？ 存放数组第 4 列所有元素至少需多少单元？ 数组按行存放时，元素 A7,4的起始地址是多少？ 数组按列存放时，元素 A4,7的起始地址是多少？ 3 （12 分）设一棵二叉树的先序序列： A B D F C E G H ，中序序列： B F D A G E H C画出这棵二叉树。画出这棵二叉树的后序线索树。将这棵二叉树转换成对应的树（或森林） 。第 页（共 3 页）34 （12 分）请阅读下列算法，回答问题。for ( i=2; i=L.length; +i ) if (L.ri.key L.ri-1.key) L.r0 = L.ri; / 复制为监视哨for ( j=i-1; L.r0.key L.rj.key; - j )L.rj+1 = L.rj; / 记录后移L.rj+1 = L.r0; 这是什么类型的排序算法？； 该排序算法稳定吗？ 该排序算法的时间复杂度与关键字的初始排列顺序有没有关系？ 假定设待排序的关键字序列为12 ，2，16，30，28，10，16*，20，6，18，请写出使用该排序方法，每趟排序结束后关键字序列的状态。5.（12 分）假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题： 画出描述折半查找过程的判定树； 若查找元素 54，需依次与哪些元素比较？ 若查找元素 90，需依次与哪些元素比较？ 假定每个元素的查找概率相等，求查找成功时的平均查找长度。三、算法设计题（60 分）1.（20 分）将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中不允许有重复的数据。（1）描述算法的基本设计思想；（2）用类 C 的语言描述该算法，关键之处给出简要注释。2.（20 分）以 二 叉 链 表 作 为 二 叉 树 的 存 储 结 构 ， 编写以下算法：（1）判别两棵树是否相等；（2）交换二叉树每个结点的左孩子和右孩子。3.（20 分）（1）试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点 vi 到顶点 vj 的路径（ij） 。（2）采用邻接表存储结构，编写一个算法，判别无向图中任意给定的两个顶点之间是否存在一条长度为为 k 的简单路径。
展开阅读全文