9-12章数据结构作业答案第九章查找选择题1、对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( A )A．（n+1）/2 B. n/2 C. n D. [（1+n）*n ]/22. 下面关于二分查找的叙述正确的是 ( D )A. 表必须有序，表可以顺序方式存储，也可以链表方式存储B. 表必须有序且表中数据必须是整型，实型或字符型C. 表必须有序，而且只能从小到大排列D. 表必须有序，且表只能以顺序方式存储3. 二叉查找树的查找效率与二叉树的( （1）C)有关, 在 (（2)C ）时其查找效率最低(1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置(2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。
4. 若采用链地址法构造散列表，散列函数为H（key）=key MOD 17，则需 (（1）A) 个链表。
这些链的链首指针构成一个指针数组，数组的下标范围为 (（2）C) （1） A．17 B. 13 C. 16 D. 任意（2） A．0至17 B. 1至17 C. 0至16 D. 1至16判断题1．Hash表的平均查找长度与处理冲突的方法无关。
(错)2. 若散列表的负载因子α<1，则可避免碰撞的产生。
（错）3. 就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。
（错）填空题1. 在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为 4 .算法应用题1. 设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：H（key）=key mod 7 ，表长为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10解决冲突。
要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。
2. 已知散列表的地址空间为A[0..11]，散列函数H（k）=k mod 11，采用线性探测法处理冲突。
计算机学科专业基础综合数据结构-内部排序(总分80,考试时间90分钟)一、单项选择题1. 对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15)；则采用的是____排序。
A. 选择B. 快速C. 希尔D. 冒泡2. 下列4个序列中，哪一个是堆____。
A. 75，65，30，15，25，45，20，10B. 75，65，45，10，30，25，20，15C. 75，45，65，30，15，25，20，10D. 75，45，65，10，25，30，20，153. 一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为____。
A. (38，40，46，56，79，84)B. (40，38，46，79，56，84)C. (40，38，46，56，79，84)D. (40，38，46，84，56，79)4. 数据序列(8，9，10，4，5，6，20，1，2)只能是下列排序算法中____的两趟排序后的结果。
A. 选择排序B. 冒泡排序C. 插入排序D. 堆排序5. 对一组数据(84，47，25，15，21)排序，数据的排列次序在排序的过程中的变化为____。
(1)84 47 25 15 21 (2)1 5 47 25 84 21(3)15 21 25 84 47 (4)1 5 21 25 47 84则采用的排序是____。
A. 选择B. 冒泡C. 快速D. 插入6. 若用冒泡排序对关键字序列{18，16，14，12，10，8}，进行从小到大的排序，所需进行的关键字比较总次数是____。
A. 10B. 15C. 21D. 347. 设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为____。
第1章绪论一、选择题1. 算法的计算量的大小称为计算的（）。
A．效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（）A．问题的规模 B. 待处理数据的初态 C. A和B3. 下面说法错误的是（）(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1) B.(1),(2) C.(1),(4) D.(3)4. 以下数据结构中，哪一个是线性结构（）A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串5. 在下面的程序段中，对x的赋值语句的频度为（）for (int i=1; i<=n; i++)for (int j=1; i<=n;j++)x+=1;A．2n B．n C．n2D．log2n二、判断题1. 数据元素是数据的最小单位。
( )2. 算法的优劣与算法描述语言无关，但与所用计算机有关。
( )3. 数据的物理结构是指数据在计算机内的实际存储形式。
( )4. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
( )5. 数据结构的抽象操作的定义与具体实现有关。
( )三、填空1．数据的物理结构包括的表示和的表示2. 数据结构中的逻辑结构有（1），（2），（3），__（4）_四种。
3. 一个数据结构在计算机中称为存储结构4. 数据结构中评价算法的两个重要指标是5. 一个算法具有5个特性: （1）、（2）、（3），有零个或多个输入、有一个或多个输出。
6. 已知如下程序段, 语句1执行的频度为（1）；语句2执行的频度为（2）；for (int i=n; i>=1; i--) {x = x+1; //语句1for (int j = n; j>=1; j--)y = y+1; //语句2}7. 下面程序段中带下划线的语句的执行次数的渐进时间复杂度为int i=1; while (i<n) i = i*2;四、应用题1. 解释和比较以下各组概念（1）抽象数据类型及数据类型（2）数据结构、逻辑结构、存储结构（3）抽象数据类型（4）算法的时间复杂性（5）算法（6）频度2. 若有100个学生，每个学生有学号，姓名，平均成绩，采用什么样的数据结构最方便，写出这些结构？3. 有实现同一功能的两个算法A1和A2，其中A1的时间复杂度为Tl=O(2n)，A2的时间复杂度为T2=O(n2)，仅就时间复杂度而言，请具体分析这两个算法哪一个好.4. 下列算法对一n位二进制数加1，假如无溢出，该算法的最坏时间复杂性是什么？并分析它的平均时间复杂性。
