《2017年北京林业大学信息学院839数据结构[专业硕士]考研导师圈点必考题汇编.doc》由会员分享，可在线阅读，更多相关《2017年北京林业大学信息学院839数据结构[专业硕士]考研导师圈点必考题汇编.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年北京林业大学信息学院839数据结构专业硕士考研导师圈点必考题汇编一、填空题1 索引顺序文件既可以顺序存取，也可以_存取。【答案】随机2 线性表【答案】（n 1）/2【解析】删除第一个元素需要移动n i 次，以此类推，删除最后一个元素需要移动0次。平 均次数为 3 如下的算法分别是后序线索二叉树求给定结点node 的前驱结点与后继结点的算法，请在算法，其空格处填上正确的语句。设线索二叉树的结点数据结构为（lflag ，lcft ，data ，right ，rflag ）中：lflag=0，lcft 指向其左孩子，lflag=1，left 指向其前驱：rflag=0，right 指向其右
2、孩子，rflag=1，right 指向其后继。Prior （node , x ） if（node !=null）If （ （1） ） *x=node-right；else * x-node-left;next （bt , node, x ）/*bt是二叉树的树根*/ （2） ; if （node-rflag）（3）; else do t=*x；;while （*x=node ）; *x=t; 【答案】nodc-rflag=O; *x=ht; *x=nodc-right; prior （t , X ）4 试利用下列栈和串的基本操作完成下述填空题。initstack （S ） 置S 为空找； pu
3、sh （S , X ） 元素X 入找； pop （S ） 出栈操作； gettop （S ） 返回栈顶元素；第 2 页，共 54 页用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_。sempty （S ） 判找空函数； 置串 判串 返回联接empty （st ） 判串空函数 若给定的表达式的前缀式pre 正确，本过程求得和它相应的表达式exp 并返回true , 否则exp 为空串，并返回false 。已知原表达式中不包含括弧，opset 为运算符的集合。） 注意：毎个空格只填一个语句。 【答案】（1）（2）（3）（4）（5）（6）（7）exp （8）（9）
4、exp （10）（11）取栈顶操作符 操作符取出后，出栈第 3 页，共 54 页为空串；是否相等的函数； 之后的串；length （st ） 返回串st 的长度； sub （S , i , 1） 返回S 中第i 个字符；栈S 初始化为空栈 串exp 初始化为空串 判取出字符是否是操作符如ch 是运算符，则入操作符栈s 判栈8是否为空若读出ch 是操作数且栈为空，则按出错处理若ch 是操作数且栈非空，则形成部分中缀表达式（12）将pre 的最后一个字符（操作数）加入到中缀式exp 的最后 5 文件可按其记录的类型不同而分成两类，即_和_文件。【答案】操作系统文件；数据库 6 在n 个顶点的非空无
5、向图中，最多有_个连通分量。【答案】n【解析】当n 个顶点之间没有边，都是孤立的顶点时，有n 个连通分量。7 在一棵m阶树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是_；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是_。【答案】 【解析】m阶树除根结点和叶子结点外，结点中关键字个数最多是最少 8 执行顺序查找时，存储方式可以是_，折半查找时，要求线性表_，分块查找时要求线性表_，而哈希表的查找，要求线性表的存储方式是_。【答案】顺序存储或链式存储；顺序存储且有序；块内顺序存储，块间有序；散列存储9 设二维数组A 的行和列的下标范围分
6、别为【答案】 当其值为和每个元素占2个单元，按行优先顺处的元素为_。序存储，第一个元素的存储起始位置为b ，则存储位置为【解析】令这个元素的行标为i ，列标为j 。则它的存储位置是时，则i=2，j=3。10G 是一个非连通无向图，共有28条边，则该图至少有_个顶点。【答案】9【解析】求该非连通无向图的最少顶点数，则该图为一个孤立的顶点和一个完全连通图。11对于双向链表，在两个结点之间插入一个新结点需修改的指针共_个，单链表为_个。【答案】4; 2 12如某二叉树有20个叶结点，有30个结点仅有一个孩子，则该二叉树的总结点数为_。【答案】69【解析】二叉树叶结点数为20, 则度为2的结点数为19, 所以总的结点数为20+19+30=69。二、选择题第 4 页，共 54 页一、填空题考研试题
