北京工业大学1995-2007年数据结构试题.pdfVIP

北京工业大学 硕士研究生入学考试初试专业课资料 计算机专业考研 数据结构历年真题（1995-2007 ） 资料包括： 1995-2007 年计算机考研《数据结构》部分，缺2002 年和2008 年。 含2001 年和2004 年的答案。 欢迎分享王道上没有的试题和资料！予人玫瑰 手有余香！ 王道论坛友情分享，请勿用于商业用途！ 王道论坛（ ）友情分享！ 予人玫瑰 手有余香！ 北京工业大学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 的 结点，则什么也不打印。例如下图所示的二叉数，则打印结点序列为A 、C、E 。 王道论坛（ ）友情分享！ 予人玫瑰 手有余香！ 六．（18 分，单考生） 再二叉排序树的结构中，有些数据元素值可能是相同的 ，设计一个 算法实现 按递增有序打印结点的数据域，要求相同的数据元素 仅输出一个，算法还应能 报出最后被滤掉，而未输出的数据元素个数，对如图所示的二叉排序树，输出为：10，12， 13，15，18，21，27，35，42 ．滤掉3 个元素。 七、（20 分）某个任务的数据 模型可以抽相象为给定的K 个集和：S1，S2、、、、，Sk 。其中 S1(1 〈I 〈K 〉中的元素个数不定。在处理数据过程中将会涉及到元素的查找和新元素的 插入两种操作，查找和插入时用一个二元组（I，X ）来规定一个元素，I 是集和的序号， X 是元素值。设计一种恰当的数据结构来贮存这K 个集和的元素，并能高效的实现所要 求的查找和插入操作。 （1） 借助Pascal 的数据类型来构造和描述你所选定的数据结构，并且说明选择的理由； （2 ） 若一组数据模型为S1={10.2, 1.7, 4.8, 16.2 }, S2={1.7, 8.4, 0.5 }, S3={4.8, 4.2, 3.6, 2.7, 5.1, 3.9 }, 待插入的元素二元组为(2, 11.2 )和(1, 5.3 ), 按你的设计思想画出插入