(4)每次把待排序的区间划分为左、右两个子区间,其中左区间中元素的键值均小于等于基准元素的键值,右区间中元素的键值均大于等于基准元素的键值。
(5)当两个元素比较出现反序(即逆序)时就相互交换位置。
2.在对一组记录（4,38,96,23,15,72,60,45,83）进行直接插入排序时,当把第7个记录60插入到有序表时,为寻找插入位置需比较________次。
3.在利用快速排序方法对一组记录(54,38,96,23,15,72,60,45,83)进行快速排序时,递归调用而使用的栈的所能达到的最大深度为________,共需递归调用的次数为________,其中第二次递归调用是对________一组记录进行快速排序。
4.在堆排序,快速排序和归并排序中,若只从存储空间考虑,则应首先选取________方法,其次选取________方法,最后选取________方法:若只从排序结果的稳定性考虑,则应选取________方法:若只从平均情况下排序最快考虑,则应选取________方法:若只从最坏情况下排序最快并且要节省内存考虑,则应选取________方法。
5.在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中,排序是不稳定的有________。
6.在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中,平均比较次数最少的排序是________需要内存容量最多的是________。
7.在堆排序和快速排序中,若原始记录接近正序或反序,则选用________若原始记录无序则最好选用________。
8.在插入和选择排序中,若初始数据基本正序,则选用________若初始数据基本反序,则选用________。
9.对n个元素的序列进行起泡排序时,最少的比较次数是________。 10.两个序列如下：
L1＝{25，57，48，37，92，86，12，33} L2＝{25，37，33，12，48，57，86，92}
用冒泡排序方法分别对序列L1和L2进行排序，交换次序较少的是序列________。 四、算法设计
1.有一种简单的排序算法,叫做计数排序。这种排序算法对一个待排序的表(用数组表示)进行排序,并将排序结果存放到另一个新的表中。必须注意的是,表中所有待排序的关键字互不相同,计数排序算法针对表中的每个记录,扫描待排序的表一趟,统计表中有多少个记录的关键字比该记录的关键字小。假设对某一个记录,统计出数值为c,那么这个记录在新的有序表中的合适的存放位置即为c。 (1)给出适用于计数排序的数据表定义。 (2)编写实现计数排序的算法。
(3)对于有n个记录的表,比较次数是多少?
(4)与直接选择排序相比,这种方法是否更好?为什么? 解: (1) typedef struct {
ElemType data; KeyType key; }listtype;
(2) void countsort(listtype a[],listtype b[],int n) {
int i1,j,count;
for(i1=0;i1 count=0; 19 for(j=0;j if(a[j].key (3) 对于有n个记录的表，关键字比较的次数是n2. (4)直接选择排序比这种计数排序好，因为直接选择排序的比较次数为n*(n-1)/2，且可在原地进行排序（稳定排序），而计数排序为不稳定排序，需要辅助空间多，为O(n). 2.修改冒泡排序法以实现双向冒泡排序。即第一次把最大记录放到表尾，第二次将最小记录放到表头，如此反复进行，直至排序结束。试编写此算法。 第九章 查 找 一、判断题 1.用二分查找法对一个顺序表进行查找，这个顺序表可以是按各键值排好序的，也可以是没有按键值排好序的。（ ） 2.哈希表的查找不用进行关键字的比较。（ ） 3.哈希表的定义函数H（key）=key%p(p<=m)这种方法是直接定址法。（ ） 4.装填因子α的值越大，就越不容易发生冲突。( ) 5.选择hash函数的标准为：随机性好、均匀性好和尽量避免冲突。( ) 二、填空题 1.顺序查找法的平均查找长度为________，二分查找法的平均查找长度为________，分块查找法(以顺序查找确定块)的平均查找长度为________，分块查找法(以二分查找确定块〉的平均查找长度为________，哈希表查找法采用链接法处理冲突时的平均查找长度为________。 2.在各种查找方法中,平均查找长度与结点个数n无关的查法方法是________。 3.二分查找的存储结构仅限于________,且是________。 4.在分块查找方法中,首先查找________,然后再查找相应的________。 5.长度为255的表,采用分块查找法,每块的最佳长度是________。 6.在散列函数H(key)=key%p中,p应取________。 7.假设在有序线性表A[1..20]上进行二分查找,则比较一次查找成功的结点数为________,则比较二次查找成功的结点数为________,则比较三次查找成功的结点数为________,则比较四次查找成功的结点数为________,则比较五次查找成功的结点数为________,平均查找长度为________。 8.对于长度为n的线性表,若进行顺序查找,则时间复杂度为________，若采用二分法查找,则时间复杂度为________。 9.己知一个有序表为(12,18,20,25,29,32,40,62,83,90,95,98),当二分查找值为29和90的元素时,分别需要________次和________次比较才能查找成功；若采用顺序查找时,分别需要________次和________次比较才能查找成功。 三、选择题 1.顺序查找法适合于存储结构为（ ）的线性表。 A．散列存储 B．顺序存储或链接存储 C．压缩存储 D．索引存储 2.对线性表进行二分查找时,要求线性表必须（ ）。 A．以顺序方式存储 B．以链接方式存储 C．以顺序方式存储,且结点按关键字有序排序 D．以链接方式存储,且结点按关键字有序排序 3.采用顺序查找方法查找长度为n的线性表时,每个元素的平均查找长度为（ ）。 A．n B．n/2 C．(n+1)/2 D．(n-1)/2 4.采用二分查找方法查找长度为n的线性表时,每个元素的平均查找长度为（ ）。 A．O(n2) B．O(log2n) C．O(n) D．O(log2n) 20 5.二分查找和二叉排序树的时间性能（ ）。 A．相同 B．不相同 C．无法比较 6.有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当二分查找值为82的结点时,（ ）次比较后查找成功。 A．1 B．2 C．4 D．8 7.设哈希表长m=14,哈希函数H(key)=key。表中已有4个结点: addr(15)=4 addr(38)=5 addr(61)=6 addr(84)=7其余地址为空，如用二次探测再散列处理冲突,关键字为49的结点的地址是（ ）。 A．8 B．3 C．5 D．9 8.有一个长度为12的有序表,按二分查找法对该表进行查找,在表内各元素等概率情况下查找成功所需的平均比较次数为（ ）。 A．35/12 B．37/12 C．39/12 D．43/12 9.采用分块查找时,若线性表中共有625个元素,查找每个元素的概率相同,假设采用顺序查找来确定结点所在的块时,每块应分（ ）个结点最佳。 A．10 B．25 C．6 D．625 10.如果要求一个线性表既能较快地查找,又能适应动态变化的要求,可以采用（ ）查找方法。 A．分块 B．顺序 C．二分 D．散列 11.设有一个长度为100的已排好序的表，用二分查找进行查找，若查找不成功，至少比较（ ）次。 A．9 B．8 C．7 D．6 四、问答题 1.已知一个线性表为(38,25,74,63,52,48),假定采用H(k)=k%7计算散列地址进行散列存储,试分别求出利用线性探测的开放定址法处理冲突和利用链接法处理冲突,在该散列表上进行查找的平均查找长度。 2.己知线性表的元素为(87,25,310,8,27,132,68,95,187,123,70,63,47),散列函数为h(k)=k,采用链接法处理冲突。设计出这种链表结构,并求该表平均查找长度。 3.假定一个待散列存储的线性表为(32,75,63,48，94,25,36,18,70),散列地址空间为[0...10],若采用除留余数法构造散列函数和线性探查法处理冲突,试给出它们对应的散列表,并求出在等概率情况下的平均查找长度。 4.试用连线把右边是四种线性表的存储结构与左边对应的操作的特点连接起来。 (A）散列表 (1）查找和存取速度快,但插入和删除速度慢。 (B)顺序有序表 (2）查找、插入和删除速度快,但不能进行顺序存取。 (C)顺序表 (3）插入、删除和顺序存取速度快,但查找速度慢。 (D)链接表 (4)查找、插入和删除速度慢,但顺序存取和随机存取第i个元素速度快。 五、应用题 设闭散列表容量为7，给定表（30，36，47，52，34），散列函数H（K）＝k mod 6，采用线性探测解决冲突，要求： （1）构造此散列表(散列地址为0~6)。 （2）求查找34需要进行比较的次数。 六、算法设计 哈希表的删除 hashtable del_hashtable (hashtable &hash, keytype K) {t=h(k); 21 if ( hash[t]= = null) return (\else if (hash[t]= =K) hash[t]=hash[t]->next; else { found=0; q=hash[t]; p=hash[t]->next; while ((!found)&&(p<> null)) if ( p->key= =K) {found=1; q->next=p->next; } else{q=p; p=p->next;} if(!found) return (\} return(hash); } 第十章 文 件 1.常见的文件组织方式有哪几种?各有何特点? 文件上的操作有哪几种? 如何评价文件组织的效率? 2.索引文件、散列文件和多关键字文件适合存放在磁带上吗?为什么? 3.设有一个职工文件，其记录格式为(职工号、姓名、性别、职务、年龄、工资)。其中职工号为关键字，并设该文件有如下五个记录： 地址 职工号 姓名 性别 职务 年龄 工资 A 39 张恒珊 男 程序员 25 3270 B 50 王莉 女 分析员 31 5685 C 10 季迎宾 男 程序员 28 3575 D 75 丁达芬 女 操作员 18 1650 E 27 赵军 男 分析员 33 6280 (1)若该记录为顺序文件，请写出文件的存储结构； (2)若该文件为索引顺序文件，请写出索引表； (3)若该文件为倒排序文件，请写出关于性别的倒排表和关于职务的倒排表。 4.在上题所述的文件中，对下列检索写出检索条件的表达式，并写出结果记录的职工号。 (1)男性职工 (2)工资超过平均工资的职工； (3)职务为程序员和分析员的职工； (4)年龄超过25岁的男性程序员或分析员； 5.B+树和B-树的主要差异是什么？ 6.编写计算二叉树中叶节点个数的递归函数（14分）。 数据结构模拟试题（自测一） 考试时间：2小时 一、单项选择题（每个2分， 共24分） 1.若语句S的执行时间为O（1），那么下列程序段的时间复杂度为（ ）。 for(i=0; i 22 A．O(n) B．O(n*n) C．O(nlogn) D．O(n*i) 2. 已知一堆栈的进栈序列为：1234，则下列哪个序列为不可能的出栈序列（ ）。 A．1234 B．4321 C．2143 D．4123 3. 深度为5的二叉树至多有（ ）个结点. A．16 B．32 C．31 D．10 4. 堆(HEAP)是一种（ ）。 A．二叉树 B．线性表 C．图 D．算法 5. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？（ ）。 A．1和5 B．2和4 C．4和2 D．5和1 6. 下列哪种排序算法的平均时间复杂度为O（nlogn）（ ）。 A．简单选择排序 B．简单插入排序 C．冒泡排序 D．归并排序 7. 用冒泡排序（交换排序）算法对(12 37 42 19 27 35 56 44 10)数据进行从小到大排序。在将最大的数“沉”到最后时，数据的顺序是（ ）。 A．12 37 42 19 27 35 44 10 56 B．12 37 42 19 27 35 10 44 56 C．12 37 19 27 35 42 44 10 56 D．10 12 19 27 35 37 42 44 56 8. 下列哪种排序算法更适合于外部排序（ ）。 A．选择排序 B．插入排序 C．冒泡排序 D．归并排序 9. 数据结构中的DIJKSTRA方法是用来求（ ）。 A．关键路径 B．最短路径 C．拓扑排序 D．字符串匹配 10. 对下列二叉树进行后序遍历，其遍历结果为（ ）。 a b c d e f g A．gfedcba B．dbegfca C．bdecgfa D．dbaecgf 11.稀疏矩阵（SPARSE MATRIX）一般的压缩存储方法有以下两种（ ）。 A．二维数组和三维数组 B．三元组（TRIPES）和哈希表（HASH TABLE） C．三元组（TRIPES）和十字链表（cross linked） D．哈希表和十字链表 12. 在待排序的元素基本有序的前提下，效率最高的排序方法是（ ）。 A．简单插入排序 B．简单选择排序 C．快速排序 D．归并排序 二、填空题（共16分） 1.、栈和队列都是________线性表。（2分） 2.、下三角形矩阵按行存储的下标计算公式为________(2分)，三对角矩阵按行存储的计算公式为________。（2分） 3.、（4分）在简单插入排序、希尔排序、简单选择排序、快速排序、堆排序、归并排序和基数排序中，排序是不稳定的有：________。 4.、（2分）请举例输出树形结构的两种存储方法________。 5.、（4分）按满二叉数的概念可推广出满K叉数的概念。若对满K叉树的节点逐层编号（从1开始，同层中从左到右），则编号为i的节点的父节点编号是________，编号为i的节点的第j个儿子的编号是________。 三、应用题（共34分） 1.、请对右图有向图（共10分）： 23