发布时间 : 星期四 文章河北工业大学-考研资料-数据结构--习题1答案更新完毕开始阅读a6c1900116fc700abb68fcfa
法查找值为82的数据元素时，查找成功的比较次数是 。 A、2 B、4 C、11 D、3
B
9.25 int Search_Sq(SSTable ST,int key)
//在有序表上顺序查找的算法,监视哨设在高下标端 {
ST.elem[ST.length+1].key=key; for(i=1;ST.elem[i].key>key;i++);
if(i>ST.length||ST.elem[i].key 分析:本算法查找成功情况下的平均查找长度为ST.length/2,不成功情况下为ST.length. 9.26 typedef struct { ElemType *elem; //数据元素存储空间基址，建表时按实际长度分配，0号单元留空。 Int Length; //表的长度 }SSTable int Search_Bin (SSTable ST,int key,int low,int high) //折半查找的递归算法 { if(low>high) return 0; //查找不到时返回0 mid=(low+high)/2; if(ST.elem[mid].key==key) return mid; else if(ST.elem[mid].key>key) return Search_Bin (ST,key,low,mid-1); else return Search_Bin (ST,key,mid+1,high); } }//Search_Bin 10章 一、填充题 1、按排序操作中所涉及的存储器的不同，可以把排序分成 和 两大类。 内部排序 外部排序 2、主关键字是可以 地标识一个数据元素的关键字。 唯一 3、希尔排序是属于插入排序的一种类型，它又被称为 排序。 缩小增量 4、次关键字是用以标识 数据元素的关键字。 多个 5、按关键字与排序结果的关系，可以把排序方法分成 和 两类。 稳定排序 非稳定排序 6、在直接插入排序、希尔排序、直接选择排序、堆排序、快速排序和基数排序中，需要内存量最大的是 。 基数排序 7、在堆排序和快速排序中，如果数据元素的原始序列接近正序或反序，则选用 最好，如果数据元素的原始序列无序，则最好选用 。 堆排序 快速排序 8、对于由n个数据元素构成的序列实施冒泡排序时，最少的比较次数是 。冒泡排序的结束条件是 。 n-1 刚做完的一趟排序没有交换元素 9、对于由n个数据元素构成的序列实施冒泡排序时，数据元素的最少交换次数是 ，此情况说明该数据元素序列是 。 0 已按排序要求有序的 二、单选题（每题2分，共24分） 1、如果采用直接选择排序法来排序一个长度为5，且已按相反顺序排序的数组，共需的比较次数是 。 A、1 B、15 C、8 D、10 D 2、有一组随机数25，84，21，47，15，27，68，35，20，现在采用某种算法对它们进行排序，具体过程如下： （1） 25 84 21 47 15 27 68 35 20 （2） 20 15 21 25 47 27 68 35 84 （3） 15 20 21 25 35 27 47 68 84 （4） 15 20 21 25 27 35 47 68 84 请根据以上情况，判断所用的排序方法是 。 A、直接选择排序 B、快速排序 C、冒泡排序 D、Shall 排序 B 3、在所有学过的排序方法中，关键字比较次数与记录的初始排列次序无关的是 。 A、冒泡排序 B、直接选择排序 C、直接插入排序 D、Shell排序 B 4、设有1000个无序的数据元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用的排序方法是 。 A、冒泡排序 B、基数排序 C、堆排序 D、快速排序 C 5、在待排元素序列基本有序的前提下，下面给出的几种排序方法效率最高的 是 。 A、直接插入排序 B、直接选择排序 C、归并排序 D、快速排序 A 6、现有一待排序列为49，38，65，97，76，13，27，50，如果以第一个数据元素49为支撑元素，在经过一趟快速排序后的结果序列是 。 A、27，38，65，97，76，13，49，50 B、27，38，49，97，76，13，65，50 C、27，38，13，49，76，97，65，50 D、27，38，13，97，76，49，65，50 C 7、在下面给出的几种排序方法中，从未排序之序列中依次取出元素与已经排好的序列（开始为空）中的元素进行比较以确定其在已排序列中的位置的排序方法是 。 A、冒泡排序 B、希尔排序 C、快速排序 D、直接插入排序 D 8、在下面给出的几种排序方法中，从未排序之序列中挑选元素，并将其依次放入已经排好的序列（开始为空）的一端的排序方法是 。 A、冒泡排序 B、希尔排序 C、直接选择排序 D、直接插入排序 C 9、在下面给出的几种排序方法中，要求辅存空间最大的排序方法是 。 A、快速排序 B、归并排序 C、直接选择排序 D、直接插入排序 B 10、下面哪一种情况不利于发挥快速排序的优势 。 A、待排序的数据量很大 B、待排序的数据相同率高 C、待排序的数据中有的数值很大 D、待排序的数据基本有序 D 11、下面哪一种情况不利于发挥堆排序的优势 。 A、待排序的数据量很大 B、待排序的数据量小 C、待排序的数据中有的数值很大 D、待排序的数据相同率高 B 12、下面哪一种情况不利于发挥基数排序的优势 。 A、待排序的数据量很大 B、待排序的数据基本有序 C、待排序的数据中有的数值很大 D、待排序的数据相同率高 C 13、在下面给出的几种排序方法中，要求辅存空间最小的排序方法是 。 A、堆排序 B、基数排序 C、快速排序 D、归并排序 A 一、 填空题 1. 不相交的树的聚集称之为 森林 。 2. 从概念上讲，树与二叉树是两种不同的数据结构，将树转化为二叉树的基本目的是_树可采用孩子-兄弟链表（二叉链表）做存储结构，目的是利用二叉树的已有算法解决树的有关问题。 3. 深度为k的完全二叉树至少有2 k-1个结点。至多有2 k-1个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是2 k-2+1。 4. 在一棵二叉树中，度为零的结点的个数为n 0，度为2的结点的个数为 n 2，则有n0= n2+1。 i-15. 一棵二叉树的第i（i≥1）层最多有2 个结点；一棵有n（n>0） 个结点的满二叉树共有（n+1）/2个叶子和（n-1） /2个非终端结点。 6. 现有按中序遍历二叉树的结果为abc，问有5种不同形态的二叉树可以得到这一遍历结果。 7. 哈夫曼树 是带权路径最小的二叉树。 8. 前缀编码是指任一个字符的编码都 不是 另一个字符编码的前缀的一种编码方法，是设计不等长编码的前提。 9. 以给定的数据集合{4，5，6，7，10，12，18}为结点权值构造的Huffman树的加权路径长度是 165 。 10. 树被定义为连通而不具有 回路 的（无向）图。 11. 若一棵根树的每个结点最多只有 两个 孩子，且孩子又有 左、右 之分，次序不能颠倒，则称此根树为 二叉树 。 12. 高度为k，且有 个结点的二叉树称为 二叉树。 2k-1 满 13. 带权路径长度最小的二叉树称为最优二叉树，它又被称为 树。 Huffman 14. 在一棵根树中，树根是 为零的结点，而 为零的结点是 结点。 入度 出度 树叶 15. Huffman树中，结点的带权路径长度是指由 到 之间