(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