|
友情提示：本站提供全国400多所高等院校招收硕士、博士研究生入学考试历年考研真题、考博真题、答案，部分学校更新至2012年，2013年；均提供收费下载。 下载流程： 考研真题 点击“考研试卷””下载; 考博真题 点击“考博试卷库” 下载
北京工业大学1995 年硕士研究生入学考试试题
考试科目：数据结构
一．（共30分，每小题6分）
（1） 输入一组关键字49，38，65，97，76，13，27，38，44，82，35，50，画出由此
而生成的二叉排序树。如果对每一个关键字的查找概率相等，求其平均查找长度ASL。
（2） 对如图（上图）所示的有向图，画出相应的邻接表结构。
(3) 画出广义表（e, (a), ((b,c),d)） 的存贮表示。
(4 ) 如下一组关键字表 25，67，18，24，38，64，55，22，15，48 判断其是否为堆，若不是堆，请调
整为一个堆，写出调整的过程。
(5) 已知下列关键字和它们对应的哈希函数值
key Teas sate east seta eats eats seat
H(key) 4 6 1 4 7 6 5
试构造长度为8的哈希表，用线性探测再散列解决冲突，并求出装填因子α 和平均
查找长度ASL。
二．（16分）如果进栈用“1”表示，退栈用“0”表示，则一串由0和1组成的字符串就表示了某栈的动
态执行情况，例如“1011”代表进栈、退栈、进栈、进栈。设栈空间大小为M，字符串长为N且由一
维数组存放，用算法判断是否会有上溢（OVERFLOW）
和下溢（UNDERFLOW）发生。
三．（15分，统考生） 用循环链表作线性表（a1,a2,….am）和（b1,b2,….bn）的存贮结构，头指针分别为
hm和hn 。设计算法，把两个线性表合并成形如（a1,b1,a2,b2,a3,…..）的线性表，要求不开辟新的动态
空间，利用原来循环链表的结点完成和并操作，结构仍为循环链表，头指针为 HEAD。分析算法的时
间复杂度。
四．（16分，单考生） 设计算法，利用二分查找的思想，在有序表中查插入一个元素X，
使表的有序性不变。分析算法的时间复杂度。
五．（18 分，统考生）若一棵二叉树中没有数据域值先相同的结点，设计算法打印数据域值为 X 的所有
祖先结点的数据域。如果根结点的数据域值为X或不存在数据域值为X的结点，则什么也不打印。例如
免责声明：本文系转载自网络，如有侵犯，请联系我们立即删除，另：本文仅代表作者个人观点，与本网站无关。其原创性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺，请读者仅作参考，并请自行核实相关内容。
|
文章搜索
您现在的位置： 
