《2017年上海海事大学文理学院828数据结构及程序设计之数据结构考研冲刺密押题.doc》由会员分享，可在线阅读，更多相关《2017年上海海事大学文理学院828数据结构及程序设计之数据结构考研冲刺密押题.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年上海海事大学文理学院828数据结构及程序设计之数据结构考研冲刺密押题目录 2017年上海海事大学文理学院828数据结构及程序设计之数据结构考研冲刺密押题（一）. 2 2017年上海海事大学文理学院828数据结构及程序设计之数据结构考研冲刺密押题（二）. 16 2017年上海海事大学文理学院828数据结构及程序设计之数据结构考研冲刺密押题（三）. 27 2017年上海海事大学文理学院828数据结构及程序设计之数据结构考研冲刺密押题（四）. 39 2017年上海海事大学文理学院828数据结构及程序设计之数据结构考研冲刺密押题（五）. 51第 1 页，共 61 页一、填空题1 VSAM 系
2、统是由_、_、_构成的。【答案】索引集；顺序集；数据集2 在一棵m阶的个数是_。【答案】 最少 【解析】m阶树除根结点和叶子结点外，结点中关键字个数最多是3 试利用下列栈和串的基本操作完成下述填空题。initstack （S ） 置S 为空找； push （S , X ） 元素X 入找； pop （S ） 出栈操作； gettop （S ） 返回栈顶元素； sempty （S ） 判找空函数； 置串 判串 返回联接empty （st ） 判串空函数 若给定的表达式的前缀式pre 正确，本过程求得和它相应的表达式exp 并返回true , 否则exp 为空串，并返回false 。已知原表达式中不
3、包含括弧，opset 为运算符的集合。） 第 2 页，共 61 页树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是_；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字为空串；是否相等的函数； 之后的串；length （st ） 返回串st 的长度； sub （S , i , 1） 返回S 中第i 个字符； 注意：毎个空格只填一个语句。 【答案】（1）（2）（3）（4）（5）（6）（7）exp （8）（9）exp （10）（11）（12）取栈顶操作符 操作符取出后，出栈将pre 的最后一个字符（操作数）加入到中缀式exp 的最后.若ch 是操作数
4、且栈非空，则形成部分中缀表达式栈S 初始化为空栈 串exp 初始化为空串 判取出字符是否是操作符如ch 是运算符，则入操作符栈s 判栈8是否为空若读出ch 是操作数且栈为空，则按出错处理 4每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是中序序列是前庁序列是_。【答案】 ，则它的后庁序列是_。设上述二叉树是由某棵树转换而成，则该树的【解析】树的抑序序列对应二叉树的前序序列. 该二叉树转换成森林吋含三棵树. 其第一棵树的前序是。5 下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。 第 3 页，共 61 页 【答案】 【解析】快速排序（quicksort ）的基
5、本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 6 一个算法具有5个特性：_、_、_、有零个或多个输入、有一个或多个输出。【答案】有穷性；确定性；可行性7 在进行入栈运算时应先判别栈是否_:在进行出栈运算时应先判别栈是否_:当栈中元素为n 个，进行入栈运算时发生上溢，则说明该栈的最大容量为_。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_分别设在内存空间的两端，这样只有当_时才产生溢出。【答案】满；空；n ; 栈底；两栈顶指针相邻（即值之差的绝对值为1） 8 设有一个10阶对称矩阵A 采用压缩存储方式（以行为主序存储：【答案】33【解析】设存储的元素的行标为i ，列标为j 。若的地址为将代入得33。 9 应用prim 算法求解连通网络的最小生成树问题。 则（1）针对如图所示的连通网络，试按如下格式给出在构造最小生成树过程中顺序选出的各条边。第 4 页，共 61 页 ，）则 的地址为_。若则的地址为考研试题
