发布时间 : 星期六 文章数据结构习题集更新完毕开始阅读b1f4ef3b16fc700aba68fc0d
case ?,? (2) break；
default：p=new BinTreeNode； (3) p->leftChild=NULL； p->rightChfild=NULL； if(BT==NULL) (4) else if(k==1) top(s)->leftChild=p； else top(8)->rightChild=p； } (5) } }|
七、下面是一个用C编写的快速排序算法。为了避免最坏情况，取基准记录pivot采用从left，right和mid=? (1eft+right)/2?中取中间值，并交换到right位置的办法。数组a存放待排序的一组记录，数据类型为Type，left和right是待排序子区间的最左端点和最右端点。
Void quicksort(Type a&#, int lefl，int right) { Type temp； if(left { Type pivot=medlian3(a,left，right)； int i=left，j=right-1; for( ； ；) { while(i { temp=a[i]；a[j]=a[i]；a[i]=temp； i++；j--； } else break； } if(s[i]>pivot) { temp=a[i]；a[i]=a[right]；a[right]=temp；} quicksort(a,left，i-1)； //递归排序左子区间 quicksort(a，i+1，right)；//递归排序右子区间 } } 25 (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