发布时间 : 星期四 文章河北工业大学-考研资料-数据结构--习题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树中,结点的带权路径长度是指由 到 之间