2017年军事医学科学院生物工程研究所836计算机应用之数据结构考研强化模拟题
● 摘要
目录
2017年军事医学科学院生物工程研究所836计算机应用之数据结构考研强化模拟题（一） ... 2 2017年军事医学科学院生物工程研究所836计算机应用之数据结构考研强化模拟题（二） ... 9 2017年军事医学科学院生物工程研究所836计算机应用之数据结构考研强化模拟题（三） . 15 2017年军事医学科学院生物工程研究所836计算机应用之数据结构考研强化模拟题（四） . 23 2017年军事医学科学院生物工程研究所836计算机应用之数据结构考研强化模拟题（五） . 29
第 1 页，共 34 页
一、填空题
1． 有向图G=（V ，E ）, 其中V （G ）=[0, 1，2，3，4, 5}, 用
【答案】50; 4
2． 完善算法：求KMP 算法.next 数组。
END ； 【答案】
3． 试利用下列栈和串的基本操作完成下述填空题。
initstack （S ） 置S 为空找； push （S , X ） 元素X 入找； pop （S ） 出栈操作； gettop （S ） 返回栈顶元素； sempty （S ） 判找空函数；
置串 判串 返回联接
empty （st ） 判串空函数
{若给定的表达式的前缀式pre 正确，本过程求得和它相应的表达式exp 并返回true , 否则exp 为空串，并返回false 。已知原表达式中不包含括弧，opset 为运算符的集合。）
第 2 页，共 34 页
为空串；
是否相等的函数；
之后的串；
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 是操作数且栈非空，则形成部分中缀表达式
栈S 初始化为空栈 串exp 初始化为空串 判取出字符是否是操作符
如ch 是运算符，则入操作符栈s 判栈8是否为空
若读出ch 是操作数且栈为空，则按出错处理
4． 对于一个具有n 个结点的单链表，在已知的结点半p 后插入一个新结点的时间. 复杂度为_____，在给定值为x 的结点后插入一个新结点的时间复杂度为_____。
【答案】
【解析】第一种情况只需直接修改指针的指向。第二种情况必须从头结点遍历找到x 的结点。
5． VSAM 系统是由_____、_____、_____构成的。
【答案】索引集；顺序集；数据集
6． 索引顺序文件既可以顺序存取，也可以_____存取。
【答案】随机
第 3 页，共 34 页
7． 顺序存储结构是通过_____表示元素之间的关系的；链式存储结构是通过_____表示元素之间的关系的。
【答案】物理上相邻；指针
【解析】顺序存储结构是通过物理位置表示元素之间的关系的，链式存储结构通过指针表示元素之间的关系。
8． 下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n
个顶点
用相邻矩阵A 表示，边的权全是正数。请在下列划线处填上正确叙述。
（1）若
是边，则
的值等于_____，若
不是边，则
的值是一个比任
何边的权，矩阵的对角线元素全为0。
（2）构造最小生成树过程中，若顶点Vi 已包括进生成树，就把相邻矩阵的对角线元素A （i , i ）置成若
【答案】（1） 9．
【答案】5
10．在一棵m 阶的个数是_____。
【答案】
则
【解析】m 阶树除根结点和叶子结点外，结点中关键字个数最多是最少
11．当两个栈共享一存储区时，栈利用一维数组表示，两栈顶指针为当栈1空时，
【答案】
为_____，栈2空时
，
为_____，栈满时为_____。
树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的
已包括进生成树，就把矩阵元素A （i ，j ）置成。 边上的权值；都大的数；（2）1; 负值；（3）为负；边
=_____
（3）算法结束时，相邻矩阵中的元素指出最小生成树的
关键字的个数是_____；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字
【解析】共享栈的栈底在共享存储区的两端，当栈满时栈顶相邻。
12．已知一循环队列的存储空间为其中队头和队尾指针分别为front 和rear , 则此循环队列判满的条件是（ ）
【答案】
13．阅读下列程序，指出其功能，并写出空格处应填上的语句。
第 4 页，共 34 页
相关内容
相关标签