内容发布更新时间 : 2024/11/14 15:11:07星期一 下面是文章的全部内容请认真阅读。
(1)用C或Pascal实现三者取中子程序median3(a,left,right)；(5分)
(2)改写quicksoft算法，不用栈消去第二个递归调用quicksort(a，j+1，right)；(5分) (3)继续改写quicksort算法，用栈消去剩下的递归调用。(5分)
上海交通大学2001年数据结构及程序设计试题
注意：程序设计请采用C语言，程序应有注解及说明。回答问题简洁、清晰全面。不得采用类C之类的语言写程序。
一、参见下图，该有向图是AOE网络。该图上已标出了源点及汇点，并给出了活动(边)的权值。
请求出该AOE网络的关键路径，以及事件(结点)的最早发生时间及最迟发生时间。(本题8分)
二、已知某二叉树的每个结点，要么其左、右子树皆为空，要么其左、右子树皆不空。又知该二叉树的前序序列为(即先根次序)：J、F、D、B、A、C、E、H、X、I、K；后序序列为(即后根次序)：A、C、B、E、D、X、I、H、F、K、Jo请给出该二叉树的中序序列(即中根次序)，并画出相应的二叉树树形。(本题8分) 三、回答下列问题：(本题10分)
1)具有N个结点且互不相似的二叉树的总数是多少? 2)具有N个结点且不同形态的树的总数是多少?
3)对二叉树而言，如果它的叶子结点总数为N0，度为2的结点的总为N2，则N0和N2之间的关系如何?
4)二叉树是否是结点的度最多为2的树?请说明理由。
5)具有n片叶子的哈夫曼树(即赫夫曼树)中，结点总数为多少？
四、在外部分类时，为了减少读、写的次数，可以采用k路平衡归并的最佳归并树模式。当初始归并段的总数不足时，可以增加长度为零的“虚段”。请问增加的“虚段”的数目为多少?请推导之。设初始归并段的总数为m。(本题8分)
五、对平衡的排序二叉树进行删除结点的操作，必须保证删除之后平衡树中的每个结点的平衡因子是+1，-1，0三种情况之一，且该树仍然是排序二叉树。现假定删除操作是在p结点的左子树上进行的，且该左子树原高为h-l，现变为h-2。因此，必须从p的左子树沿着到根的方向回溯调整结点的平衡因子，并进行树形的调整。设p是调整时遇到的第一个平衡
26
因子力图由-1变成-2的最年轻的“前辈”结点。我们知道，以p为根的子树经调整后，高度有可能减少1。试用图形把调整前及调整后的相关结点的平衡因子、树形表示出来；仅仅针对调整后子树的高度减少1的情况即可。注意，罗列出所有可能的情况。上图可供参考。(本题10分)
六、某算法由下述方程表示。请求出该算法的时间复杂性的级别(以大O形式表示)。注意n>7求解问题的规模，设n是3的正整数幂。(本题8分)
七、如右图所示，该二叉树是某棵有序树变换成的相对应的二叉树。试给出原来的有序树的形状。并回答以下问题：
1)原有序树是度为多少的树? 2)原有序树的叶子结点有哪几个?
3)是否所有的二叉树都可以找到相对应的有序树?必须满足什么条件?(本题5分)
八、在排序二叉树上进行查找操作时，设对树中的每个结点查找概率相同。设由n个结点构成的序列生成的排序二叉树是“随机”的。试求出在成功查找的情况下，平均查找长度是多少?为了简单起见，最后得到的递推式可不予求解。(本题8分)
九、设从键盘每次输入两个字符。如A、B，则表示存在着一条由数据场之值为字符A的结点到数据场之值为字符B的结点的有向边。依此输入这些
有向边，直至出现字符!为止。试设计一个程序，生成该有向图的邻接表及逆邻接表。必须交待所用的结构、变量、加以适当注解。(本题20分) ·
十、设二叉树中结点的数据场之值为一字符。采用二叉链表的方式存储该二叉树中的所有结点，设p为指向树根结点的指针。设计一个程序在该二叉树中寻找数据场之值为key(key为一变量，变量内容为一字符)的那个结点的所有祖先。设二叉树中结点数据场之值互不重复。(本题15分)
注意：有些书上将二叉树的二叉链表存储形式称之为标准存储形式。
1 如果n=1 5T(n/3)+n 如果n>1
Tn= 南开大学2001年数据结构试题
一、选择题(每小题3分，共21分)
在下列各题中，每题之后均有若干个备选答案，请选出所有正确的答案，填人“ ”处。答案请写在答题纸上。
1．任何一个无向连通图的最小生成树 。 ①只有一棵 ②有一棵或多棵
27
③一定有多棵 ④可能不存在
2．已知一棵非空二叉树的 ，则能够惟一确定这棵二叉树。 ①先序遍历序列和后序遍历序列 ②先序遍历序列和中序遍历序列 ③先序遍历序列 ④中序遍历序列 ，
3．使用指针实现二叉树时，如果结点的个数为n，则非空的指针域个数为 。 ①n-1 ②2n-1 ③n+1 ④2n+1
4．设队列存储于一个一维数组中，数组下标范围是1-n，头尾指针分别为f和r，f指向第一个元素的前一个位置，r指向队列中的最后一个元素，则队列中元素个数为 。 ①r-f ②r-f+1 ③(r-f+1)mod n ④(r-f+n)mod n 5．任意一个AOE网络的关键路径 。
①一定有多条 ②只有一条 ③可能不只一条 ④可能不存在 ． 6．下列排序算法中，在每一趟都能选出一个元素放到其最终位置上的是 。
①插入排序 ②希尔排序 ③快速排序 ④堆排序 7．任意一个有向图的拓扑排序序列 。
①一定有多种 ②只有一种 ③可能不存在 ④以上都不对
二、(7分)已知散列表地址空间为0-8，哈希函数为H(k)=kmod7，采用线性探测再散列法解决冲突。将下面关键字数据依次填入该散列表中，同时将查找每个关键字所需的比较次数m填入下表中，并求等概率下的平均查找长度。
关键字值：100，20，21，35，3，78，99，45
0 1 2 3 4 5 6 7 8 A
m 100 20 21 35 3 78 99 45
三、(12分)回答下列问题： (1)(3分)什么叫基数排序?
(2)(3分)什么是AVL树中的平衡因子，它有什么特点?
(3)(6分)n个元素的序列{k1,k2,…kn}满足什么条件才能称之为堆?简述对它进行堆排序的过程。
四、(10分)顺序给出以下关键字：63、23、31、26、7、91、53、15、72、52、49、68，构造3阶B-树。要求从空树开始，每插入一个关键字，画出一个树形。 五、(6分)设有向无环图G如下图所示： 试写出图G的六种不同的拓扑排序序列。
28
六、(10分)设二叉树以二叉链表表示，各结点的结构如下所示：
left data subsum right 其中left、right分别为指向该结点左、右孩子的指针，data为存储关键字值的整数域，subsum中存储以该结点为根的子树中所有关键字值之和。试使用C或C++语言设计算法，计算所给树T中所有结点的subsum值。
七、(12分)给出一个带表头的单链表L，L的每个结点中存放一个整数。现给定一个阈值K，将L分成两个子表L1和L2，其中L1中存放L中所有关键字值大于等于是的结点，L2中存放L中所有关键字值小于K的结点。试编程实现这个过程。要求，使用C或C++语言实现算法，L1和L2仍占用L的存储空间。
八、(10分)设有一维整数数组A，试使用C或C++语言设计算法，将A中所有的奇数排在所有偶数之前。要求，时间复杂度尽可能地少，结果仍放在A原来的存储空间。 九、(12分)简述哈夫曼编码的构造过程。
华东理工大学2001年数据结构与程序设计试题
一、单选题(10分)
1．若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用——存储方式最节省运算时间。
A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表
2．若在线性表中采用折半查找法查找元素，该线性表应该 。 A．元素按值有序 B．采用顺序存储结构 C．元素按值有序，且采用顺序存储结构 D．元素按值有序，且采用链式存储结构
3．对于给定的结点序列abcdef，规定进栈只能从序列的左端开始。通过栈的操作，能得到的序列为 。
A．abcfed B．cabfed C．abcfde D．cbafde
4．已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为 。
29
A．-A+B*C/DE B．-A+B*CD/E
C．-+*ABC/DE D．-+A*BC/DE
5．如果n1和n2是二叉树T中两个不同结点，n2为n1的后代，那么按遍历二叉树T
时，结点n2一定比结点n1先被访问。
A．前序 B．中序 C．后序 D．层次序 6．具有65个结点的完全二叉树其深度为 。(根的层次号为1) A．8 B．7 C．6 D．5
7．已知二叉树的前序遍历序列是abdgcefh，中序遍历序列是dgbaechf，它的后序遍历序列是 。
A．bdgcefha B. gdbecfha C．bdgechfa D．gdbehfca
8．对于前序遍历和后序遍历结果相同的二叉树为 。 A．一般二叉树 B．只有根结点的二叉树 C．根结点无左孩子的二叉树 D．根结点无右孩子的二叉树
9．对于前序遍历与中序遍历结果相同的二叉树为 。 A．根结点无左孩子的二叉树 B．根结点无右孩子的二叉树 C．所有结点只有左子树的二叉树 D．所有结点只有右子树的二叉树
10．在有n个叶子的哈夫曼树中，其结点总数为 。 A．不确定 B．2n C．2n+1 D．2n-1 二、是非题(10分)
1．顺序存储方式只能用于存储线性结构。 2．消除递归不一定需要使用栈。
3．将一棵树转换成相应的二叉树后，根结点没有右子树。
4．完全二叉树可以采用顺序存储结构实现，存储非完全二叉树则不能。
5．在前序遍历二叉树的序列中，任何结点的子树的所有结点都是直接跟在该结点之后。 6．邻接表法只能用于有向图的存储，而邻接矩阵法对于有向图和无向图的存储都适用。 7．在一个有向图的邻接表中，如果某个顶点的链表为空，则该顶点的度一定为零。 8．二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值，小于其右孩子的值。
9．最佳二叉排序树的任何子树都是最佳二叉排序树。
10．对两棵具有相同关键字集合的而形状不同的二叉排序树，按中序遍历它们得到的序列的顺序是一样的。 三、问答题
(应届生限做2，3，4，5题；在职生任选做四题；共40分)
30