资源简介：北京工业大学数据结构1995年考研真题硕士研究生入学考试试题    

        下载流程： 考研真题 点击“考研试卷””下载; 考博真题 点击“考博试卷库” 下载

 

北京工业大学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的结点，则什么也不打印。例如

 

说明：本站提供的《北京工业大学数据结构1995年考研真题硕士研究生入学考试试题 》源自权威渠道，为历年考过（被使用过）的真题试卷，除标注有“回忆版”字样的试题外，其余均为原版扫描，权威可靠；回忆版试题由当年参加全国硕士、博士研究生入学考试考生回忆，内容完整。