|
北京工业大学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的结点，则什么也不打印。例如
，更多更新年份持续更新，请在本站的考博信息网|www.kaoboinfo.com中的“考研试卷库”学校栏目中查询下载。
|
您现在的位置： 
