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

发布时间：2022-09-16 发布人：admin 分类：说明书资料大小：0.03M 资料格式：doc 举报版权申诉

第1页 / 共4页

第2页 / 共4页

第3页 / 共4页

第4页 / 共4页

文本预览

2016 年山东青岛科技大学数据结构考研真题一、选择题(每个 2 分，共 30 分) 1、在长度为 n 的顺序表的第 i(1≤i≤n+1)个位置上删除一个元素，移动元素的个数为( ) 。 A. i-1 B .n-i+1 C. I D. D.n-i 2、以下哪一个术语与数据的逻辑结构无关？（） A．哈希表 B. 栈 C. 二叉树 D.线性表 3、下面程序段的时间复杂度为____________。 for(int i=0; i=1）的满三叉树中，结点总数为（）。 A. 3k B.3k-1 C .（3k-1）/3 D.（3k-1）/2

8、AVL 树是一种平衡的二叉排序树，树中任一结点的( ) 。 A. 左、右子树高度差的绝对值不超过 1 B. 左、右子树的高度均相同 C. 左子树的高度均大于右子树的高度 D. 左子树的高度均小于右子树的高度 9、若一个栈的输入序列为 1,2,3,…,n，输出序列的第一个元素是 i，则第 j 个输出元素是（）。 A. i-j-1 B. 不确定的 C. j-i+1 D. i-j 10、适用于折半查找的表的存储方式及元素排列要求为() 。 A．链接方式存储，元素无序 B．链接方式存储，元素有序 C．顺序方式存储，元素无序 D．顺序方式存储，元素有序 11、设哈希表长为 14，哈希函数是 H(key)=key%11,表中已有数据的关键字为 15，38，61， 84 共四个，现要将关键字为 49 的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是()。 A．9 B．3 C．5 D． 8 12、设单链表中指针 p 指向结点 m，若要删除 m 之后的结点（若存在），则需修改指针的操作为（）。 A．p=p->next B．p->next=p->next->next C．p=p->next->next D．p->next=p 13、对序列{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 分）回答下列问题： ①什么是数据结构？ ②对于数据结构一般包含哪三个方面的讨论？ ③在编制管理通讯录的程序时，通讯录数据采用什么样的数据结构合适？ ④对于第③问，存储结构采用什么样的结构合适？为什么？ 2．（12 分）数组 A 中，每个元素 A[i,j]的长度均为 32 个二进位,行下标从-1 到 9，列下标从 1 到 11，从首地址 S 开始连续存放主存储器中，主存储器字长为 16 位。求： ① 存放该数组所需多少单元？ ② 存放数组第 4 列所有元素至少需多少单元？ ③ 数组按行存放时，元素 A[7,4]的起始地址是多少？ ④ 数组按列存放时，元素 A[4,7]的起始地址是多少？ 3．（12 分）设一棵二叉树的先序序列： A B D F C E G H ，中序序列： B F D A G E H C ①画出这棵二叉树。 ②画出这棵二叉树的后序线索树。 ③将这棵二叉树转换成对应的树（或森林）。 4．（12 分）请阅读下列算法，回答问题。 for ( i=2; i<=L.length; ++i ) if (L.r[i].key < L.r[i-1].key) { L.r[0] = L.r[i];// 复制为监视哨 for ( j=i-1; L.r[0].key < L.r[j].key;-- j ) L.r[j+1] = L.r[j];// 记录后移 L.r[j+1] = L.r[0]; } ① 这是什么类型的排序算法？； ② 该排序算法稳定吗？ ③ 该排序算法的时间复杂度与关键字的初始排列顺序有没有关系？ ④ 假定设待排序的关键字序列为{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 的路径（i≠j）。（2）采用邻接表存储结构，编写一个算法，判别无向图中任意给定的两个顶点之间是否存在一条长度为为 k 的简单路径。

分享到：

赞收藏

资料库

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

相关推荐

考研

热门标签

最新资料