2018年辽宁工程技术大学项目管理(专业学位)935数据结构考研仿真模拟五套题
● 摘要
目录
2018年辽宁工程技术大学项目管理（专业学位）935数据结构考研仿真模拟五套题（一） .... 2 2018年辽宁工程技术大学项目管理（专业学位）935数据结构考研仿真模拟五套题（二） .. 12 2018年辽宁工程技术大学项目管理（专业学位）935数据结构考研仿真模拟五套题（三） .. 21 2018年辽宁工程技术大学项目管理（专业学位）935数据结构考研仿真模拟五套题（四） .. 35 2018年辽宁工程技术大学项目管理（专业学位）935数据结构考研仿真模拟五套题（五） .. 44
第 1 页，共 53 页
一、填空题
1． 索引顺序文件既可以顺序存取，也可以 _____存取。
【答案】随机
2． 组成串的数据元素只能是_____。
【答案】字符
3． 对于一个具有n 个结点的二叉树，当它为一棵_____二叉树时具有最小高度, 当它为一棵_____时，具有最大高度。
【答案】完全；只有一个叶结点的二叉树
4． 抽象数据类型的定义仅取决于它的一组_____，而与_____无关，即不论其内部结构如何变化，只要它的_____不变，都不影响其外部使用。
【答案】逻辑特性；在计算机内部如何表示和实现；数学特性
5． 在顺序存储的二叉树中，编号为i 和j 的两个结点处在同一层的条件是_____。
【答案】要加“虚结点”。
设编号为i 和j 的结点在顺序存储中的下标为s 和t , 则结点i 和j 在同一层上的条件是
。
6． 有五个数据依次入找:1，2，3，4，5。在各种出栈的序列中，以3，4先出栈的序列有_____。(3在4之前出栈)
【答案】3个
【解析】以3，4先出栈的序列有34521、34215、34251共3个。
7． 假定有k 个关键字互为同义词，若用线性探测再哈希法把这k 个关键字存入哈希表中，至少要进行_____次探测。
【答案】的次数最小。总次数为
。
第 2 页，共 53 页
【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，
【解析】当该关键字发生冲突时，用线性探测不会遇到别的关键字冲突，这个时候需要探测
8． 对n 个记录的表
【答案】n (n－1) /2
进行简单选择排序，所需进行的关键字间的比较次数为_____。
【解析】第一次需要n －1次比较，第i 此需要n －i 此比较，所以共需要。
9． 关键码序列(Q，H ，C ，Y ，Q ，A ，M ，S ，R ，D ，F ，X) ，要按照关键码值递增的次序进行排序，若采用初始步长为4的希尔排序法，则一趟扫描的结果是_____; 若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是_____。
【答案】(Q，A ，C ，S ，Q ，D ，F ，X ，R ，H ，M ，Y) ; (F，H ，C ，D ，a ，A ，M ，Q ，R ，S ，Y ，X)
【解析】希尔排序的基本思想是:先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
快速排序(quick sort) 的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
10．如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为_____。
【答案】序查找效率一样为
。
【解析】如果关键码是排好序的，构建二叉排序树就会形成一个单支树，它的查找效率和顺
二、算法设计题
11．设有两个栈S 1，S 2都采用顺序栈方式，并且共享一个存储区的操作算法。
【答案】找的定乂:
两栈共享顺序存储空间所能达到的最多元素数
//假设元素类型为整型
； //栈空间
//top为两个栈顶指针
//S是如上定义的结构类型变量，为全局变量
(1)入栈操作:
//入栈操作。i 为栈号，i ＝〇表示左栈Sl ，i ＝l 表示右栈s2，x 是入栈元素。入栈成功返回1，
第 3 页，共 53 页
为了尽量利用
空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计S 1，S 2有关入栈和出找
否则返回
(2)出栈操作
//出栈算法。i 代表栈号，i ＝0时为s1栈，i ＝l 时为s2栈。出栈成功返回出栈元素，否则返﹣
1
//算法结束
12．已知两个线性表A , B 均以带头结点的单链表作存储结构，且表中元素按值递增有序排列。设计算法求出A 与B 的交集C ，要求C 另开辟存储空间。，并同样以元素值的递增有序的单链表形式存储。
【答案】算法如下:
//线性表A 和B 以带头结点的单链表作为存储结构。本算法求A 和B 的交集C , C 另辟空间
//pa、pb 是两链表的工作指针
//监视哨
//pa指针后移
//pb指针后移
//处理交集元素
//删除重复元素
//交集元素并入结果表
//置结果链表尾
第 4 页，共 53 页
相关内容
相关标签