《河海大学1998年数据结构考研试题》由会员分享，可在线阅读，更多相关《河海大学1998年数据结构考研试题（1页珍藏版）》请在金锄头文库上搜索。
1、河海大学 1998 年数据结构考研试题一、名词解释：（每题 3 分，共 15 分） A、数据类型 B、时间复杂度 C、静态链表 D、循环队列 E、拓扑排序 二、给出下列结构的存储描述（每题 3 分，共 15 分） A、广义表（给出一种） B、双向循环链表 C、邻接表 D、串 三、利用两个栈 s1，s2 模拟一个队列时如何用栈的运算 （push，pop，top，sempty）来实现下列队列的运算 enq（入队） ， deq（出队） ，qempty（测队空） ，试写出算法。 （每个算法 4 分共 12 分） 。 四、顺序检索时间为 O(n)，折半检索时间为 O(log2n)，hash 方法为 O(
2、1)， 为什么有高效的检索算法，而分辨率的方法不被放弃。 （8 分） 五、给出折半查找的递归算法，并给出算法时间复杂度分析。 （5 分） 六、给出以十字链表作存储结构，建立图的算法，输入（i，j，v）其中 i，j 为顶点号，v 为权值。 （10 分） 七、写出在中序线索二叉树里，找指定结点在后序下的前驱结点的算法。 （10 分） 八、分别以不同存储结构实现线性表就地逆转的算法，即在原表的存储空 间内将线性表（a1，a2，an）逆转为（an，an- 1，a2，a1） 。 A、以一维数组作存储结构； B、一单链表作存储结构。 （10 分） 九、证明：如果给了一个二叉树结点的先序序列和中序序列，则此二叉树 即可构造出来，如果给了先序序列和后序序列行吗？给了后序序列和 中序序列呢？如果不行请举反例。 （10 分）
