《2017年北京语言大学软件工程825数据结构与程序设计[专业硕士]考研强化模拟题.doc》由会员分享，可在线阅读，更多相关《2017年北京语言大学软件工程825数据结构与程序设计[专业硕士]考研强化模拟题.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年北京语言大学软件工程825数据结构与程序设计专业硕士考研强化模拟题目录 2017年北京语言大学软件工程825数据结构与程序设计专业硕士考研强化模拟题（一） . 2 2017年北京语言大学软件工程825数据结构与程序设计专业硕士考研强化模拟题（二） . 13 2017年北京语言大学软件工程825数据结构与程序设计专业硕士考研强化模拟题（三） . 22 2017年北京语言大学软件工程825数据结构与程序设计专业硕士考研强化模拟题（四） . 31 2017年北京语言大学软件工程825数据结构与程序设计专业硕士考研强化模拟题（五） . 41第 1 页，共 52 页一、填空题1 有五个数据依次
2、入栈：1，2, 3, 4, 5。在各种出栈的序列中，以3, 4先出栈的序列有_。（3在4之前出栈）【答案】3个【解析】以3, 4先出栈的序列有34521、34215、34251共3个。 2 二叉树的前序序列和中序序列相同的条件是_。【答案】空树或任何结点至多只有右子树的二叉树【解析】前序遍历的顺序为根左右，中序遍历的顺序为左根右，因此若中序遍历和前序遍历序列相同，则任何结点都没有左子树。 3 试利用下列栈和串的基本操作完成下述填空题。initstack （S ） 置S 为空找； push （S , X ） 元素X 入找； pop （S ） 出栈操作； gettop （S ） 返回栈顶元素； s
3、empty （S ） 判找空函数； 置串 判串 返回联接empty （st ） 判串空函数 若给定的表达式的前缀式pre 正确，本过程求得和它相应的表达式exp 并返回true , 否则exp 为空串，并返回false 。已知原表达式中不包含括弧，opset 为运算符的集合。） 第 2 页，共 52 页为空串；是否相等的函数； 之后的串；length （st ） 返回串st 的长度； sub （S , i , 1） 返回S 中第i 个字符； 注意：毎个空格只填一个语句。 【答案】（1）（2）（3）（4）（5）（6）（7）exp （8）（9）exp （10）（11）（12）取栈顶操作符 操作符取
4、出后，出栈将pre 的最后一个字符（操作数）加入到中缀式exp 的最后表示，两栈顶指针为则若ch 是操作数且栈非空，则形成部分中缀表达式栈S 初始化为空栈 串exp 初始化为空串 判取出字符是否是操作符如ch 是运算符，则入操作符栈s 判栈8是否为空若读出ch 是操作数且栈为空，则按出错处理 4 当两个栈共享一存储区时，栈利用一维数组当栈1空时，【答案】为_，栈2空时， 为_，栈满时为_。【解析】共享栈的栈底在共享存储区的两端，当栈满时栈顶相邻。5 高度为h 的堆中，最多有_元素，最少有_个元素。【答案】 当最后一层只有 【解析】当这个堆构成的是满二叉树时，元素的个数最多，元素个数为一个元素时
5、，此时堆的元素个数最少，元素个数为 第 3 页，共 52 页 6 从用户的观点看，文件的逻辑结构通常可以区分为两类：一类是如NdBASE 中数据库文件那样的文件组织结构，称为_文件:另一种是诸如用各种文字处理软件编辑成的文本文件，称为_文件。从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即_，_和_。B+树适用于组织_的索引结构，m阶个关键码。【答案】数据库；文本；顺序组织；随机组织；链组织；随机组织；7 已知二维数组为1000的连续存储区域时，【答案】1196【解析】设元素的行标为i ，列标为j 。则它的存储位置为：8 设为哈夫曼树的叶结点数日，则该哈夫曼树共有_个结点。【
6、答案】 【解析】哈夫曼树只有度为0和2的节点。 9=_【答案】5 10假定查找有序表【答案】37/12【解析】折半查找时每个的次数如表所示：表 平均查找次数为 11串是一种特殊的线性表，其特殊性表现在_; 串的两种最基本的存储方式是_、_; 两个串相等的充分必要条件是_。【答案】其数据元素都是字符；顺序存储；链式存储；串的长度相等且两串中对应位置的字符也相等 12中每个元素的概率相等，则进行折半查找时的平均查找长度为_ 树每个结点至多有_个儿子，除根结点外每个结点至少有_个儿子，根结点至少有_个儿子，有k 个儿子的结点必有_中每个元素占4个单元，在按行优先方式将其存储到起始地址的地址是：_。已 求REPLACE （S ，V , m ）=_。知【答案】 第 4 页，共 52 页考研试题
