下载文档原格式
第九章查找一、选择题1•若查找每个记录的概率均等，则在具有n 个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL 为()。
A ．(n-1)/2B.n/2C.(n+1)/2D.n 2. 下面关于二分查找的叙述正确的是()A. 表必须有序，表可以顺序方式存储，也可以链表方式存储C.表必须有序，而且只能从小到大排列B. 表必须有序且表中数据必须是整型，实型或字符型D.表必须有序，且表只 能以顺序方式存储3. 用二分(对半)查找表的元素的速度比用顺序法() A. 必然快B.必然慢C.相等D.不能确定4. 具有12个关键字的有序表，折半查找的平均查找长度()A.3.1B.4C.2.5D.55．当采用分块查找时，数据的组织方式为()A. 数据分成若干块，每块内数据有序B. 数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块C. 数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块D. 数据分成若干块，每块(除最后一块外)中数据个数需相同6. 二叉查找树的查找效率与二叉树的((1))有关,在((2))时其查找效率最低(1) ：A.高度B.结点的多少C.树型D.结点的位置(2) :A.结点太多B.完全二叉树C.呈单枝树D.结点太复杂。
7. 对大小均为n 的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找失败,它们的平均查找长度是((1)),对于查找成功,他们的平均查找长度是((2))供选择的答案:A.相同的B.不同的9．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是()A ．(100，80，90，60，120，110，130)B.(100，120，110，130，80，60，90) C. (100，60，80，90，120，110，130)D.(100，80，60，90，120，130，110)10. 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A 的左孩子的平衡因子为0右孩子的平衡因子为1，则应作()型调整以使其平衡。
习题九排序一、单项选择题1．下列内部排序算法中：A．快速排序 B.直接插入排序C. 二路归并排序D.简单选择排序E. 起泡排序F.堆排序（1）其比较次数与序列初态无关的算法是（）（2）不稳定的排序算法是（）（3）在初始序列已基本有序（除去n 个元素中的某 k 个元素后即呈有序， k<<n）的情况下，排序效率最高的算法是（）（4）排序的平均时间复杂度为O(n?logn)的算法是（）为 O(n?n) 的算法是（）2．比较次数与排序的初始状态无关的排序方法是( )。
A．直接插入排序B．起泡排序C．快速排序D．简单选择排序3．对一组数据（ 84， 47， 25， 15， 21）排序，数据的排列次序在排序的过程中的变化为（1） 84 47 25 15 21（2） 15 47 25 84 21（3） 15 21 25 84 47（4） 15 21 25 47 84则采用的排序是 ()。
A. 选择B.冒泡C.快速D.插入4．下列排序算法中 ( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。
A. 选择B.冒泡C.归并D.堆5．一组记录的关键码为（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)6．下列排序算法中，在待排序数据已有序时，花费时间反而最多的是()排序。
A．冒泡 B. 希尔C. 快速D. 堆7.就平均性能而言，目前最好的内排序方法是() 排序法。
A. 冒泡B.希尔插入C.交换D.快速8.下列排序算法中，占用辅助空间最多的是：()A. 归并排序B.快速排序C.希尔排序D.堆排序9.若用冒泡排序方法对序列 {10,14,26,29,41,52}从大到小排序，需进行（）次比较。
第一章绪论一，选择题1．组成数据的根本单位是〔〕A．数据项B．数据类型C．数据元素D．数据变量2．数据结构是研究数据的〔〕以及它们之间的相互关系。
A．理想结构，物理结构B．理想结构，抽象结构C．物理结构，逻辑结构D．抽象结构，逻辑结构3．算法分析的两个主要方面是〔〕A．正确性和简单性B．可读性和文档性C．数据复杂性和程序复杂性D．时间复杂度和空间复杂度4．算法分析的目的是〔〕。
A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改良D．分析算法的易懂性和文档性5. 算法的时间复杂度取决于〔〕A．问题的规模 B. 待处理数据的初态 C. A和B Ｄ．以上都不是6．一个算法应该是〔〕。
A．程序 B．问题求解步骤的描述 C．要满足五个根本特性 D．A和C.7. 下面关于算法说法错误的选项是〔〕A．算法最终必须由计算机程序实现C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的8．从逻辑上可以把数据结构分为〔〕两大类。
A．动态结构、静态结构 B．顺序结构、链式结构C．线性结构、非线性结构 D．初等结构、构造型结构9．程序段 for ( i=n-1;i>=1;i--)for (j=1j<=i;j++)if( A[j]>A[j+1])A[j]与A[j+1]对换；其中 n为正整数，那么最后一行的语句频度在最坏情况下是〔〕A．O〔n〕B．O(nlogn) C.．O(n3) D．O(n2)10．连续存储设计时，存储单元的地址〔〕。
A．一定连续 B．一定不连续 C．不一定连续 D．局部连续，局部不连续二，判断题1．数据结构的抽象操作的定义与具体实现有关。
( )2．数据结构是数据对象与对象中数据元素之间关系的集合。
3．在顺序存储结构中，有时也存储数据结构中元素之间的关系。
( )4．数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用的需要建立的。
5．算法和程序原那么上没有区别，在讨论数据结构是两者是通用的。
数据结构（C语言版）9-12章练习答案清华大学出版社9-12章数据结构作业答案第九章查找选择题1、对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( A )A．（n+1）/2 B. n/2 C. n D. [（1+n）*n ]/2 2. 下面关于二分查找的叙述正确的是 ( 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 mod7 ，表长为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10解决冲突。
要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。
第9章 查找教材中练习题及参考答案1. 设有5个数据do 、for 、if 、repeat 、while ，它们排在一个有序表中，其查找概率分别是p 1=0.2，p 2=0.15，p 3=0.1，p 4=0.03，p 5=0.01。
而查找它们之间不存在数据的概率分别为q 0=0.2，q 1=0.15，q 2=0.1，q 3=0.03，q 4=0.02，q 5=0.01，该有序表如下：（1）试画出对该有序表分别采用顺序查找和折半查找时的判定树。
（2）分别计算顺序查找的查找成功和不成功的平均查找长度。
（3）分别计算折半查找的查找成功和不成功的平均查找长度。
答：（1）对该有序表分别采用顺序查找和折半查找时的判定树分别如图9.2和9.3所示。
（2）对于顺序查找，成功查找到第i 个元素需要i 次比较，不成功查找需要比较的次数为对应外部结点的层次减1：ASL 成功=(1p 1+2p 2+3p 3+4p 4+5p 5)=0.97。
ASL 不成功=(1q 0+2q 1+3q 2+4q 3+5q 4+5q 5)=1.07。
（3）对于折半查找，成功查找需要比较的次数为对应内部结点的层次，不成功查找需要比较的次数为对应外部结点的层次减1：ASL 成功=(1p 3+2(p 1+p 4)+3(p 2+p 5))=1.04。
ASL 不成功=(2q 0 q 5图9.3 有序表上折半查找的判定树2. 对于A [0..10]有序表，在等概率的情况下，求采用折半查找法时成功和不成功的平均查找长度。
对于有序表（12，18，24，35，47，50，62，83，90，115，134），当用折半查找法查找 90时，需进行多少次查找可确定成功；查找47时需进行多少次查找可确定成功；查找100时，需进行多少次查找才能确定不成功。
答：对于A [0..10]有序表构造的判定树如图9.4（a ）所示。
因此有：ASL 成功=1144342211⨯+⨯+⨯+⨯=3ASL 不成功=124834⨯+⨯=3.67 对于题中给定的有序表构造的判定树如图9.4（b ）所示。
第9章 查找答案一、填空题1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。
2. 线性有序表（a 1，a 2，a 3，…，a 256)是从小到大排列的，对一个给定的值k ，用二分法检索表中与k 相等的元素，在查找不成功的情况下，最多需要检索 9 次。
设有100个结点，用二分法查找时，最大比较次数是 7 。
3. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ；平均查找长度为 3.7 。
解：显然，平均查找长度＝O （log 2n ）<5次（25）。
但具体是多少次，则不应当按照公式)1(log 12++=n nn ASL 来计算（即（21×log 221）/20＝4.6次并不正确！）。
因为这是在假设n ＝2m-1的情况下推导出来的公式。
应当用穷举法罗列：全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL ＝74/20=3.7 ！！！4．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 28，6，12，20 比较大小。
5. 在各种查找方法中，平均查找长度与结点个数n 无关的查找方法是 散列查找 。
6. 散列法存储的基本思想是由 关键字的值 决定数据的存储地址。
7. 有一个表长为m 的散列表，初始状态为空，现将n （n<m ）个不同的关键码插入到散列表中，解决冲突的方法是用线性探测法。
如果这n 个关键码的散列地址都相同，则探测的总次数是 n(n-1)/2=（ 1＋2＋…＋n-1） 。
(而任一元素查找次数 ≤n-1)二、单项选择题（ B ）1．在表长为ｎ的链表中进行线性查找，它的平均查找长度为Ａ. ＡＳＬ＝ｎ; Ｂ. ＡＳＬ＝（ｎ＋１）／２;Ｃ. ＡＳＬ＝n ＋１; Ｄ. ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１（ A ）2. 折半查找有序表（4，6，10，12，20，30，50，70，88，100）。
清华大学课程讲义-数据结构答案第9章9-1 什么是内排序? 什么是外排序? 什么排序方法是稳定的? 什么排序方法是不稳定的? 【解答】9-2 设待排序的关键码序列为{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18}, 试分别写出使用以下排序方法每趟排序后的结果。
并说明做了多少次关键码比较。
(1) 直接插入排序(2) 希尔排序(增量为5,2,1) (3) 起泡排序(4) 快速排序(5) 直接选择排序(6) 锦标赛排序(7) 堆排序(8) 二路归并排序(9) 基数排序【解答】9-3 在起泡排序过程中，什么情况下关键码会朝向与排序相反的方向移动，试举例说明。
在快速排序过程中有这种现象吗？【解答】如果在待排序序列的后面的若干关键码比前面的关键码小，则在起泡排序的过程中，关键码可能向与最终它应移向的位置相反的方向移动。
例如，57 40 38 11 13 34 48 75 6 19 9 7 如9向相反方向移动6 57 40 38 11 13 34 48 75 7 19 9 如19向相反方向移动6 7 57 40 38 11 13 34 48 75 9 19 如9向最终方向移动6 7 9 57 40 38 11 13 34 48 75 19 如13向相反方向移动6 7 9 11 57 40 38 13 19 34 48 75 如13向最终方向移动6 7 9 11 13 57 40 38 19 34 48 75 如34向相反方向移动6 7 9 11 13 19 57 40 38 34 48 756 7 9 11 13 19 34 57 40 38 48 756 7 9 11 13 19 349-4 试修改起泡排序算法，在正反两个方向交替进行扫描，即第一趟把关键码最大的对象放到序列的最后，第二趟把关键码最小的对象放到序列的最前面。
如此反复进行。
【解答】template <class Type> void dataList<Type> :: shake_Sort ( ) {//奇数趟对表Vector从前向后, 比较相邻的关键码, 遇到逆序即交换, 直到把参加比较关键码序列//中最大的关键码移到序列尾部。
第九章 查找一、填空题1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。
2. 线性有序表（a 1，a 2，a 3，…，a 256)是从小到大排列的，对一个给定的值k ，用二分法检索表中与k 相等的元素，在查找不成功的情况下，最多需要检索 8 次。
设有100个结点，用二分法查找时，最大比较次数是 7 。
3. 假设在有序线性表a[1..20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ,其下标从小到大依次是1,3,6,8,11,13,16,19______，平均查找长度为 3.7 。
解：显然，平均查找长度＝O （log 2n ）<5次（25）。
但具体是多少次，则不应当按照公式)1(log 12++=n nn ASL 来计算（即（21×log 221）/20＝4.6次并不正确！）。
因为这是在假设n ＝2m -1的情况下推导出来的公式。
应当用穷举法罗列：全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL ＝74/20=3.7 ！！！ 4．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 28，6，12，20 比较大小。
5. 在各种查找方法中，平均查找长度与结点个数n 无关的查找方法是 散列查找 。
6. 散列法存储的基本思想是由 关键字的值 决定数据的存储地址。
7. 有一个表长为m 的散列表，初始状态为空，现将n （n<m ）个不同的关键码插入到散列表中，解决冲突的方法是用线性探测法。
如果这n 个关键码的散列地址都相同，则探测的总次数是 n(n-1)/2=（ 1＋2＋…＋n-1） 。
(而任一元素查找次数 ≤n-1)8、设一哈希表表长M 为100 ，用除留余数法构造哈希函数，即H （K ）=K MOD P （P<=M ）, 为使函数具有较好性能，P 应选（ 97 ）9、在各种查找方法中，平均查找长度与结点个数无关的是哈希查找法 10、对线性表进行二分查找时，要求线性表必须以 顺序 方式存储，且结点按关键字有序排列。
目录基础练习题及答案 (1)第一章绪论 (1)第二章线性表 (3)第三章栈和队列 (7)第四-五章串和数组 (12)第六章树和二叉树 (16)第七章图 (24)第八章查找 (30)第九章排序 (33)数据结构实验指导 (34)实验一线性表的应用 (34)实验二栈和队列的应用 (39)实验三串的应用 (47)实验四数组 (48)实验五二叉树的应用 (51)实验六图的应用 (55)实验七查找 (56)实验八排序 (61)配套题集算法答案 (64)第一章绪论 (64)第二章线性表 (67)第三章栈与队列 (79)第四章串 (89)第五章数组和广义表 (101)第六章树和二叉树 (114)第七章图 (133)第八章动态存储管理 (148)第九章查找 (152)第十章内部排序 (163)基础练习题及答案第一章绪论一、填空题1. 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。
2. 数据结构被形式地定义为（D, R），其中D是数据元素的有限集合，R是D上的关系有限集合。
3. 数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。
4. 数据结构按逻辑结构可分为两大类，它们分别是线性结构和非线性结构。
5. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。
6．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有 1个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有1个后续结点。
7. 在树形结构中，树根结点没有前驱结点，其余每个结点有且只有 1 个前驱结点；叶子结点没有后续结点，其余每个结点的后续结点数可以任意多个。
8. 在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。
9．数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、索引和散列。
10. 数据的运算最常用的有5种，它们分别是插入、删除、修改、查找、排序。
一、判断题（第一章绪论）1.数据元素是数据的最小单元。
答案：错误2.一个数据结构是由一个逻辑结构和这个逻辑结构上的基本运算集构成的整体。
答案：错误3.数据的存储结构是数据元素之间的逻辑关系和逻辑结构在计算机存储器内的映像。
答案：正确4.数据的逻辑结构是描述元素之间的逻辑关系，它是依赖于计算机的。
答案：错误5.用语句频度来表示算法的时间复杂度的最大好处是可以独立于计算机的软硬件，分析算法的时间答案：正确（第二章线性表）6.取顺序存储线性表的第i个元素的时间同i的大小有关。
答案：错误7.线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。
答案：正确8.线性链表的每一个节点都恰好包含一个指针域。
答案：错误9.顺序存储方式的优点的存储密度大，插入和删除效率不如练市存储方式好。
答案：正确10.插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用。
答案：错误（第三章栈）11.栈是一种对进栈和出栈作了限制的线性表。
答案：错误12.在C（或C++）语言中设顺序栈的长度为MAXLEN，则top=MAXLEN表示栈满。
答案：错误13.链栈与顺序栈相比，其特点之一是通常不会出现满栈的情况。
答案：正确14.空栈就是所有元素都为0上的栈。
答案：错误15.将十进制数转换为二进制数是栈的典型应用之一。
答案：正确（第四章队列）16.队列式限制在两端进行操作的线性表。
答案：正确17.判断顺序队列为空的标准是头指针和尾指针都指向同一结点。
答案：错误18.在循环链列队中无溢出现像。
答案：错误19.在循环队列中，若尾指针rear大于头指针front，则元素个数为rear-front。
答案：正确20.顺序队列和循环队列关于队满和队空的判断条件是一样的。
答案：错误（第五章串）21.串是n个字母的有限序列。
答案：错误22.串的堆分配存储是一种动态存储结构。
答案：正确23.串的长度是指串中不同字符的个数。
《数据结构》第九章习题参考答案一、判断题（在正确说法的题后括号中打“√”，错误说法的题后括号中打“×”）1、快速排序是一种稳定的排序方法。
（×）2、在任何情况下，归并排序都比简单插入排序快。
（×）3、当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素。
（√）4、内排序要求数据一定要以顺序方式存储。
（×）5、直接选择排序算法在最好情况下的时间复杂度为O（n）。
( ×)6、快速排序总比简单排序快。
( ×)二、单项选择题1．在已知待排序文件已基本有序的前提下，效率最高的排序方法是（A）。
A．直接插入排序B．直接选择排序C．快速排序D．归并排序2．下列排序方法中，哪一个是稳定的排序方法？（B）A．直接选择排序B．折半插入排序C．希尔排序D．快速排序3、比较次数与排序的初始状态无关的排序方法是( B)。
A．直接插入排序B．起泡排序（时间复杂度O（n2））C．快速排序D．简单选择排序4、对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47 （4）15 21 25 47 84 则采用的排序是( A)。
A. 选择B. 冒泡C. 快速D. 插入5、快速排序方法在（D）情况下最不利于发挥其长处。
A. 要排序的数据量太大B. 要排序的数据中含有多个相同值C. 要排序的数据个数为奇数D. 要排序的数据已基本有序6、用某种排序方法对线性表{25，84，21，47，15，27，68，35，20}进行排序，各趟排序结束时的结果为：（基准）20，21，15，25，84，27，68，35，47（25）15，20，21，25，47，27，68，35，84（左20右47）15，20，21，25，35，27，47，68，84（左35右68）15，20，21，25，27，35，47，68，84 ；则采用的排序方法为（C）。
第9章查找一、选择题1．若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为（）。
A．（n-1）／2B．n／2C．（n+1）／2D．n【答案】C【解析】最快查找一次成功，最慢查找n次成功。
平均查找次数为（1+2+3+…+n）/n，那么ASL=(n+1)/2。
2．在一个有N个元素的有序单链表中查找具有给定关键字的结点，平均情况下的时间复杂性为（）。
A．O（1）B．O（N）C．O（N2）D．O（NlogN）【答案】B【解析】二分查找的时间复杂度为O(logn)。
在一个用N个元素的有序单链表中查找具有给定关键字的结点，因为查找是从头结点开始的，需要使用指针顺序往下查找，因此时间复杂度为0（N）。
3．对线性表进行折半查找时，要求线性表必须（）。
A．以顺序方式存储B．以顺序方式存储，且数据元素有序C．以链接方式存储D．以链接方式存储，且数据元素有序【答案】B【解析】二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。
因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
折半查找方法适用于对以顺序方式存储的有序表的查找，查找效率较高。
4．下列二叉排序树中查找效率最高的是（）。
A．平衡二叉树B．二叉查找树C．没有左子树的二叉排序树D．没有右子树的二叉排序树【答案】A【解析】平衡二叉树的左子树和右子树的深度之差的绝对值不超过1。
这就保证了二叉树的深度是log2n级别的。
二叉查找树或者是一颗空数；或者是具有下列性质的二叉树：①若左子树不空，则左子树上所有结点的值均小于它的根结点的值；②若右子树不空，则右子树上所有结点的值均大于它的根结点的值；③左、右子树也分别为二叉排序树。
B、C、D 三项均不能保证左子树和右子树的深度之差的绝对值不超过1，甚至很大，因此查找效率低。
5．当在一个有序的顺序存储表上查找一个数据时，既可用折半查找，也可用顺序查找，但前者比后者的查找速度（）。
第1章绪论一、判断题1.数据的逻辑结构与数据元素本身的内容和形式无关。
（√）2.一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。
（√）3.数据元素是数据的最小单位。
（×）4.数据的逻辑结构和数据的存储结构是相同的。
（×）5.程序和算法原则上没有区别，所以在讨论数据结构时可以通用。
（×）6.从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。
（√）7.数据的存储结构是数据的逻辑结构的存储映象。
（√）8.数据的物理结构是指数据在计算机内实际的存储形式。
（√）9.数据的逻辑结构是依赖于计算机的。
（×）10.算法是对解题方法和步骤的描述。
（√）二、填空题1.数据有逻辑结构和存储结构两种结构。
2.数据逻辑结构除了集合以外，还包括线性结构、树形结构和图形结构。
3.数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。
4.树形结构和图形结构合称为非线性结构。
5.在树形结构中，除了树根结点以外，其余每个结点只有1个前驱结点。
6.在图形结构中，每个结点的前驱结点数和后继结点数可以任意多个。
7.数据的存储结构又叫物理结构。
8.数据的存储结构形式包括顺序存储、链式存储、索引存储和散列存储。
9.线性结构中的元素之间存在一对一的关系。
10.树形结构中的元素之间存在一对多的关系。
11.图形结构的元素之间存在多对多的关系。
12.数据结构主要研究数据的逻辑结构、存储结构和算法（或运算） 3个方面的内容。
13.数据结构被定义为（D，R），其中D是数据的有限集合，R是D上的关系有限集合。
14.算法是一个有穷指令的集合。
15.算法效率的度量可以分为事先估算法和事后统计法。
16.一个算法的时间复杂度是算法输入规模的函数。
17.算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题规模的n的函数。
18.若一个算法中的语句频度之和为T(n)=6n+3nlog2n,则算法的时间复杂度为O（ nlog2n）。
第一章绪论一、选择题1.数据结构是一门研究非数值计算的程序设计问题中计算机的1以及它们之间的2和运算等的学科。
1 A.数据元素 B.计算方法 C.逻辑存储 D.数据映像2 A.结构 B.关系 C.运算 D.算法2.数据结构被形式地定义为(K, R)，其中K是1的有限集，R是K上的2有限集。
1 A.算法 B.数据元素 C.数据操作 D.逻辑结构2 A.操作 B.映像 C.存储 D.关系3.在数据结构中，从逻辑上可以把数据结构分成。
A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构4.线性结构的顺序存储结构是一种1的存储结构，线性表的链式存储结构是一种2的存储结构。
A.随机存取 B.顺序存取 C.索引存取 D.散列存取5.算法分析的目的是1，算法分析的两个主要方面其一是指2，其二是指正确性和简单性。
1 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性2 A.空间复杂度和时间复杂度 B.研究算法中的输入和输出的关系C.可读性和文档性D.数据复杂性和程序复杂性k6.计算机算法指的是1，它必须具备输入、输出和2等5个特性。
1 A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法2 A.可执行性、可移植性和可扩充性 B.可行性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、稳定性和安全性7.线性表的逻辑顺序与存储顺序总是一致的，这种说法。
A.正确 B.不正确8线性表若采用链式存储结构时，要求内存中可用存储单元的地址。
A.必须连续的B.部分地址必须连续的C.一定是不续的D连续不连续都可以9.以下的叙述中，正确的是。
A.线性表的存储结构优于链式存储结构 B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出10.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法。
第九章 查找一、填空题1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。
2. 线性有序表（a 1，a 2，a 3，…，a 256)是从小到大排列的，对一个给定的值k ，用二分法检索表中与k 相等的元素，在查找不成功的情况下，最多需要检索 8 次。
设有100个结点，用二分法查找时，最大比较次数是 7 。
3. 假设在有序线性表a[1..20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ,其下标从小到大依次是1,3,6,8,11,13,16,19______，平均查找长度为 3.7 。
解：显然，平均查找长度＝O （log 2n ）<5次（25）。
但具体是多少次，则不应当按照公式)1(log 12++=n n n ASL 来计算（即（21×log 221）/20＝4.6次并不正确！）。
因为这是在假设n ＝2m -1的情况下推导出来的公式。
应当用穷举法罗列：全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL ＝74/20=3.7 ！！！4．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 28，6，12，20 比较大小。
5. 在各种查找方法中，平均查找长度与结点个数n 无关的查找方法是 散列查找 。
6. 散列法存储的基本思想是由 关键字的值 决定数据的存储地址。
7. 有一个表长为m 的散列表，初始状态为空，现将n （n<m ）个不同的关键码插入到散列表中，解决冲突的方法是用线性探测法。
如果这n 个关键码的散列地址都相同，则探测的总次数是 n(n-1)/2=（ 1＋2＋…＋n-1） 。
(而任一元素查找次数 ≤n-1)8、设一哈希表表长M 为100 ，用除留余数法构造哈希函数，即H （K ）=K MOD P （P<=M ）, 为使函数具有较好性能，P 应选（ 97 ）9、在各种查找方法中，平均查找长度与结点个数无关的是哈希查找法10、对线性表进行二分查找时，要求线性表必须以 顺序 方式存储，且结点按关键字有序排列。
