2018年辽宁工程技术大学项目管理(专业学位)935数据结构考研基础五套测试题
● 摘要
目录
2018年辽宁工程技术大学项目管理（专业学位）935数据结构考研基础五套测试题（一） .... 2 2018年辽宁工程技术大学项目管理（专业学位）935数据结构考研基础五套测试题（二） .. 12 2018年辽宁工程技术大学项目管理（专业学位）935数据结构考研基础五套测试题（三） .. 23 2018年辽宁工程技术大学项目管理（专业学位）935数据结构考研基础五套测试题（四） .. 34 2018年辽宁工程技术大学项目管理（专业学位）935数据结构考研基础五套测试题（五） .. 44
一、填空题
1． 数据结构是研讨数据的_____和_____以及它们之间的相互关系，并对与这种结构定义相应的_____, 设计出相应的_____。
【答案】逻辑结构；物理结构；操作(运算) ；算法
2． 在n 个顶点的非空无向图中，最多有_____个连通分量。
【答案】n
【解析】当n 个顶点之间没有边，都是孤立的顶点时，有n 个连通分量。
3． 外排序的基本操作过程是_____和_____。
【答案】生成有序归并段(顺串) ；归并
4． VSAM(虚拟存储存取方法) 文件的优点是:动态地_____，不需要文件进行_____，并能较快地_____进行查找。
【答案】分配和释放存储空间；重组；对插入的记录
5． 对于给定的元素，可以构造出的逻辑结构有_____，_____，_____，_____四种。
【答案】集合；线性结构；树形结构；图状结构(网状结构)
6． 对于一个具有n 个结点的单链表，在已知的结点半p 后插入一个新结点的时间. 复杂度为_____，在给定值为x 的结点后插入一个新结点的时间复杂度为_____。
【答案】O(1)；O(n)
【解析】第一种情况只需直接修改指针的指向。第二种情况必须从头结点遍历找到x 的结点。
7． 假定有k 个关键字互为同义词，若用线性探测再哈希法把这k 个关键字存入哈希表中，至少要进行_____次探测。
【答案】
【解析】当该关键字发生冲突时，用线性探测不会遇到别的关键字冲突，这个时候需要探测的次数最小。总次数为。
8． 设正文串长度为n ，模式串长度为m ，则串匹配的KMP 算法的时间复杂度为_____。
【答案】O(m＋n)
9． 栈是_____的线性表，其运算遵循_____的原则。
【答案】操作受限(或限定仅在表尾进行插入和删除操作) ；后进先出
10．如下的算法分别是后序线索二叉树求给定结点node 的前驱结点与后继结点的算法，
请在算法空格处填上正确的语句。 设线索二叉树的结点数据结构为其中:
left 指向其左孩子，
【答案】
left 指向其前驱；，
right 指向其后继。
，
right 指向其右孩子，，
，
二、算法设计题
11．试为二叉树写出一个建立三叉链表的算法，并在此三叉链表中删去每一个元素值为x 的结点，以及以它为根的子树，且释放相应存储空间。二叉树的三叉链表的描述为:
{二叉树根结点的指针}
【答案】算法如下:
生成三叉链表的二叉树(题目给出PASCAL 定义，下面用类C 语言书写
)
是二叉树结点指针的一维数组，容量足够大
一维数组最后元素的下标
元素或虚结点
根结点
双亲结点和子女结点用指针链上
结束
12．给定一个整数数组求出b 中最长平台的长度。
【答案】算法如下:
b 中连续的相等元素构成的子序列称为平台。试设计算法，
//求具有N 个元素的整型数组b 中最长平台的长度。
//局部最长平台
//新平台起点
(“最长平台长度
13．假设以双亲表示法作树的存储结构，写出双亲表示的类型说明，并编写求给定的树的深度的算法(注:已知树中的结点数) 。
【答案】算法如下:
求以双亲表示法作为存储结构的树的深度
深度加1, 并取新的双亲
最大深度更新
返回树的深度
’结束Depth
在b 数组中起始下标为
”，1，
k)
相关内容
相关标签