《2017年北方民族大学计算机技术833C语言程序设计与数据结构之数据结构考研强化模拟题.doc》由会员分享，可在线阅读，更多相关《2017年北方民族大学计算机技术833C语言程序设计与数据结构之数据结构考研强化模拟题.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年北方民族大学计算机技术833C语言程序设计与数据结构之数据结构考研强化模拟题一、填空题1 二进制地址为011011110000，大小为【答案】011011110100；011011100000011011110000是块的起始地址，【解析】大小分别为式如下： 当大小为4时，起始地址为 2 试利用下列栈和串的基本操作完成下述填空题。initstack （S ） 置S 为空找； push （S , X ） 元素X 入找； pop （S ） 出栈操作； gettop （S ） 返回栈顶元素； sempty （S ） 判找空函数； 置串 判串 返回联接empty （st ） 判串空函数 若给
2、定的表达式的前缀式pre 正确，本过程求得和它相应的表达式exp 并返回true , 否则exp 为空串，并返回false 。已知原表达式中不包含括弧，opset 为运算符的集合。） 第 2 页，共 39 页和块的伙伴地址分别为：_ 和其伙伴块的起始地址计算公当大小为16时，起始地址为：为空串；是否相等的函数； 之后的串；length （st ） 返回串st 的长度； sub （S , i , 1） 返回S 中第i 个字符； 注意：毎个空格只填一个语句。 【答案】（1）（2）（3）（4）（5）（6）（7）exp （8）（9）exp （10）（11）（12）取栈顶操作符 操作符取出后，出栈将pr
3、e 的最后一个字符（操作数）加入到中缀式exp 的最后表示，两栈顶指针为则若ch 是操作数且栈非空，则形成部分中缀表达式栈S 初始化为空栈 串exp 初始化为空串 判取出字符是否是操作符如ch 是运算符，则入操作符栈s 判栈8是否为空若读出ch 是操作数且栈为空，则按出错处理 3 当两个栈共享一存储区时，栈利用一维数组当栈1空时，【答案】为_，栈2空时， 为_，栈满时为_。【解析】共享栈的栈底在共享存储区的两端，当栈满时栈顶相邻。 4 如下的算法分别是后序线索二叉树求给定结点node 的前驱结点与后继结点的算法，请在算法，其空格处填上正确的语句。设线索二叉树的结点数据结构为（lflag ，lc
4、ft ，data ，right ，rflag ）中：lflag=0，lcft 指向其左孩子，lflag=1，left 指向其前驱：rflag=0，right 指向其右孩子，rflag=1，right 指向其后继。Prior （node , x ） if（node !=null）If （ （1） ） *x=node-right；else * x-node-left;next （bt , node, x ）/*bt是二叉树的树根*/ （2） ;第 3 页，共 39 页 if （node-rflag）（3）; else do t=*x；;while （*x=node ）; *x=t; 【答案】nod
5、c-rflag=O; *x=ht; *x=nodc-right; prior （t , X ）5 顺序栈用【答案】存储数据，栈顶指针是top ，则值为x 的元素入栈的操作是_。 【解析】先判断栈是否满，如果不满，元素入栈。否则返回溢出信息。6 n 个顶点的有向图用邻接矩阵array 表示，下面是其拓扑排序算法，试补充完整。注：（1）图的顶点号从0开始计；（2）indegree 是有n 个分量的一维数组，放顶点的入度， （3）函数crein 用于记算顶点入度；（4）有三个函数push （data ）, pop（ ）, check（ ）其含义为数据data 入浅，出栈和测试栈是否空（不空返回1, 否则0）。 ） . 【答案】0; j; i; 0; indegreei=0; vexi; k=l; indegreei=0【解析】有向图用邻接矩阵表示时，顶点i 的入度等于第i 列的所有元素之和。拓扑排序过程：首先将入度 为0的顶点全部进栈。然后弹出栈顶结点，并将与弹出的顶点相连的其它顶点的入度 减一，然后判断这些顶点的 入度是否为零，如果为零，继续进栈，重复这些操作，完成拓扑排序。 ；（“图有回路”） 第 4 页，共 39 页 一、填空题考研试题
