资源描述：
《c,考研,试题哈工大2000参考答案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、参考答案一、1・抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。即不论其内部结构如何变化，只要它的数学特性不变，都不影响外部使用。抽象数据类型和数据类型实质上是一个概念。另外，抽象数据类型的范畴更广，它不再局限于各处理器己定义并实现的数据类型，还包括用户在设计软件系统吋自己定义的数据类型。2・一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n),算法的时间量度记作T(n)=O(f(n))它表示随问题规模n的增大，算法执行时间的增长率和
2、f(n)的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。3・散列法是一种重要的存储方法，也是一种重要的查找方法。由于记录在存储结构屮的相对位置是随机的，所以在查找时都要通过一系列的关键字的比较才能确定被查记录在结构屮的位置。也就是说，这类查找都是以关键字的比较为基础的，而散列法则不同，它通过一个函数(称为散列函数)，该函数以记录的关键字为自变量，函数值即为记录的存储地址。这样就把记录逐--存放到以相应函数值为地址的存储单元中，这样得到的符号表就成为散列表。当要查找时，须用同个散列函数计算得到待查记录的存储地址，然后到相应的存储单元里去
3、获得有关信息。4・为了提高查找速度，可以采用索引的方法组织文件。通常在主文件之外，再建立一张指示关键字与其物理记录之间一一对应关系的表，这张表就称为索引表。由索引表和主文件一起构成的文件称为索引文件。二、1・不管单链表是否为空表，头指针均不空，并使得对单链表的操作在各种情况下统一。2・n-13・某种遍历序列的直接前驱结点，某种遍历序列的直接后继结点4・双亲表示法、孩子表示法、孩子兄弟表示法5・插入排序、交换排序、选择排序、归并排序、基数排序三、l・J2・X3・J4・X5・y四、堆是一种排序方法，其定义为：对于n个关键字序列{k1,k2,…，k
4、n},当且仅当满足下列关系吋称其为堆：厂■丄iWk2iki$k2i或kiWk2i+lkik2i+l二叉查找树是一种查找方法，其定义为：二叉排序又称二叉查找树，它或者是一棵空树，或者是具有如下性质的二叉树：(1)若它的左子树非空，则左子树上所有结点的值均小于根结点的值；(2)若它的右子树非空，则右子树上所有结点的值均大于或等于根结点的值;(3)左、右子树本身就是二棵二叉排序树。五、快速排序是对冒泡排序的一种改进。快速排序的基本思想：通过一趟排序将待排的记录分割为独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分继
5、续进行排序，以达到整个序列有序。一趟快速排序的具体作法是：附设两个指针low和high,它们的初值分别指向文件的第一个记录和最后一个记录，设枢轴记录（通常是第一个记录）的关键字为pivotkey,则首先从high所指位置起向前搜索，找到第一个关键字小于pivotkey的记录并与枢轴记录互相交换，然后从low所指位置起向后搜索，找到第一个关键字大于piotkey的记录并与枢轴记录互相交换，重复这两步直至1ow=high为止。六、所对应的二叉树如图10.3所示。七、可得到序列｛b,e,c,e,b,g,a｝和｛c,d,b,e,f,a,g｝八、由中根
6、和后根所确定的二叉树如图10.4所示。cAD图10.4二叉树前根序列和后根序列不能唯一确定一棵二叉树。因为根据中极序列，结合前根或后根序列可以把二叉树区分岀左右子树来。而前根序列和后根序列访问左右子树是顺序连在一起的，故无法区分出左右子树来，那么也就无法确定一棵二叉树了。九、使用Prim算法构造量小生成树的过程如图10.5所示。prim算法构造最小生成树的过程使用Kruskal算法构造最小牛成树的过程如图10.6所示。J:2:6图610.6用kruskal算法构造最小生成树的过程十、对于二叉排序树，按照“右中左”的次序顺序递归遍历，即可得到由
7、大到小的序列。PROCEDUREtravel(bt:bitrce);BEGINIF(btONIL)THENBEGINtravel(btlrchiId);write(bt：data);travel(btllchild)ENDEXD;十一、非递归算法。根据完全二叉树的定义可知，对完全二叉树按照从上到下，从左到右的次序遍历应满足：(1)若某结点没有孩子，则一定无右孩子；(2)若某结点缺(左或右)孩子，则其所有后继一定无孩子。反之，可采用按层次遍历二叉树的方法依次对每个结点进行判断。为此增加一个标志以表示所有已扫描过的结点均有左右孩子，将局部判断结果
8、存入DM(初值是true)中，CM表示整个二叉树是否是完全二叉树，BJ表示到目前为止所有结点均有左右孩子。FUNCT10NCCM(T:bitree):boolean
