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