《2017年复旦大学基础医学院754生物医工综合之数据结构考研导师圈点必考题汇编.doc》由会员分享，可在线阅读，更多相关《2017年复旦大学基础医学院754生物医工综合之数据结构考研导师圈点必考题汇编.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年复旦大学基础医学院754生物医工综合之数据结构考研导师圈点必考题汇编目录 2017年复旦大学基础医学院754生物医工综合之数据结构考研导师圈点必考题汇编（一）. 2 2017年复旦大学基础医学院754生物医工综合之数据结构考研导师圈点必考题汇编（二）. 18 2017年复旦大学基础医学院754生物医工综合之数据结构考研导师圈点必考题汇编（三）. 32 2017年复旦大学基础医学院754生物医工综合之数据结构考研导师圈点必考题汇编（四）. 47 2017年复旦大学基础医学院754生物医工综合之数据结构考研导师圈点必考题汇编（五）. 60一、填空题1 属于不稳定排序的有_。【答案】希尔排
2、序、简单选择排序、快速排序、堆排序等2 表达式【答案】的后缀表达式是_。 3 棵深度为k 的平衡二叉树， 其每个非终端结点的平衡因子均为0，则该树共有_个结点。【答案】树。故结点个数为4 【答案】5 5 假定有k 个关键字互为同义词，若用线性探测再哈希法把这k 个关键字存入哈希表中，至少要进行_次探测。【答案】 【解析】当该关键字发生冲突时，用线性探测不会遇到别的关键字冲突，这个时候需要探测 的次数最小。总次数为 6 试利用下列栈和串的基本操作完成下述填空题。initstack （S ） 置S 为空找； push （S , X ） 元素X 入找； pop （S ） 出栈操作； gettop （
3、S ） 返回栈顶元素； sempty （S ） 判找空函数； 置串 判串 返回联接为空串；是否相等的函数； 之后的串；length （st ） 返回串st 的长度； =_【解析】每个非终端结点都是0表示该平衡二叉树没有高度落差。也就是说它是一棵满二叉sub （S , i , 1） 返回S 中第i 个字符；empty （st ） 判串空函数 若给定的表达式的前缀式pre 正确，本过程求得和它相应的表达式exp 并返回true , 否则exp 为空串，并返回false 。已知原表达式中不包含括弧，opset 为运算符的集合。） 注意：毎个空格只填一个语句。 【答案】（1）（2）（3）（4）（5）（
4、6）（7）exp （8）（9）exp （10）（11）（12）取栈顶操作符 操作符取出后，出栈将pre 的最后一个字符（操作数）加入到中缀式exp 的最后若ch 是操作数且栈非空，则形成部分中缀表达式栈S 初始化为空栈 串exp 初始化为空串 判取出字符是否是操作符如ch 是运算符，则入操作符栈s 判栈8是否为空若读出ch 是操作数且栈为空，则按出错处理 7 如果按关键码值递増的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为_。【答案】 【解析】如果关键码是排好序的，构建二叉排序树就会形成一个单支树，它的查找效率和顺序查找效率一样为 8 空格串是指_，其长度等
5、于_。【答案】由空格字符（9 在哈希函数值32）所组成的字符串；空格个数 中，P 值最好取_。【答案】小于等于表长的最大素数或不包含小于20的质因子的合数【解析】在使用除留余数法时，对除数P 的选择很重要。若P 选的不好，容易产生同义词。一般情况下，可以选P 为质数或不包含小于20的质因素的合数。 10检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按_检索。也可以按_检索；按_检索又可以有_检索和_检索。【答案】关键字；记录号；记录号；顺序；直接11假定查找有序表【答案】37/12【解析】折半查找时每个的次数如表所示：表 平均查找次数为 12己知有序表为（12，18，24，35，47，50，62，83，90，115，134）当用二分法查找90时，需_次查找成功，查找47时_成功，查找100时，需_次才能确定不成功。【答案】2；4；3【解析】二分法查找元素次数列表 查找100是找到115就停止了。 中每个元素的概率相等，则进行折半查找时的平均查找长度为_二、选择题13将线性表的数据元素进行扩充，允许带结构的线性表是（ ）。A. 串 B. 树 C. 广义表 D. 栈 【答案】C考研试题
