第三章 查找与排序
一、选择题
1. 对采用折半查找法进行查找操作的查找表，要求按【 】方式进行存储。
A．顺序存储 B．链式存储
C．顺序存储且结点按关键字有序 D．链式存储且结点按关键字有序
2. 设有序表的关键字序列为(1，4，6，10，18，35，42，53，67，71，78，84，92，99)，当用折半查找法查找键值为35的结点时，经【 】次比较后查找成功。
A．2 B．3 C．4 D．6 3. 分块查找的时间性能【 】。
A．低于折半查找
B．高于顺序查找而低于折半查找 C．高于顺序查找
D．低于顺序查找而高于折半查找
4. 设哈希函数为H(key)=key％7，一组关键字为(37，21，9，20，30，19，46)，哈希表T的地址空间为0..6，用线性探测法解决冲突，依次将这组关键字插入T中，得到的哈希表为【 】。 A． 0 1 2 3 4 5 6 21 20 37 9 46 30 19 B． 0 1 2 3 4 5 6 21 46 37 9 30 19 20 C． 0 1 2 3 4 5 6 21 19 9 37 30 46 20 D．0 1 2 3 4 5 6 20 37 30 21 46 19 9
5. 设有一个用线性探测法解决冲突得到的哈希表：
0 1 2 3 4 5 6 7 8 9 10 13 25 80 16 17 6 14
哈希函数为H(key)=key％11，若要查找元素14，探测的次数是【 】。 A．3 B．6 C．7 D．9
6. 在哈希函数H(key)=key％m中，一般来讲，m应取【 】。
A．奇数 B．偶数 C．素数 D．充分大的数 7. 以下说法错误的是【 】。
A．哈希法存储的基本思想是由关键字的值决定数据的存储地址 B．哈希表的结点中只包含数据元素自身的信息，不包含任何指针 C．哈希表的基本思想与顺序查找、对分查找和分块查找都不同
D．哈希表的查找效率主要取决于哈希表造表时选取的哈希函数和处理冲突的方法
8. 在关键字随机分布的情况下，用二叉排序树的方法进行查找，其平均查找长度与【 】查找方法量级相当。
A．分块 B．顺序 C．折半 D．散列
9. 在具有n个结点的二叉排序树中查找一个元素时，最坏情况下的时间复杂度为【 】。
2
A．O(n) B．O(1) C．O(log2n) D．O(n) 10. 哈希表的平均查找长度( )。
A．与处理冲突的方法有关而与表的长度无关
11
B．与处理冲突的方法无关而与表的长度有关 C．与处理冲突的方法有关且与表的长度有关 D．与处理冲突的方法无关且与表的长度无关
11. 有数据(49,32,40,6,45,12,56)，从空二叉树开始依次插入数据形成二叉排序树，若希望高度最小，则应选择下列【 】输入序列。
A．45，12，49，6，40，56，32 B．40，12，6，32，49，45，56 C．6，12，32，40，45，49，56 D．32，12，6，40，45，56，49
12. 在一棵深度为h的具有n个元素的二叉排序树中，查找所有元素的最长查找长度为【 】。 A．n B．log2n C．(h+1)／2 D．h
13. 【 】方法是从未排序序列中依次取出元素与已经排序序列中的元素进行比较，将其放人已经排序序列的正确位置上。
A．双向冒泡排序 B．插入排序 C．冒泡排序 D．选择排序
14. 【 】方法是从未排序序列中挑选元素，并将其依次放入已经排序序列的一端。 A．双向冒泡排序 B．插入排序 C．冒泡排序 D．选择排序
二、填空题
1．索引顺序表上的查找分两个阶段：一、______________；二、____________。该查找方法称为________查找。
2．二叉排序树是一种特殊的、增加了限制条件的二叉树，其限制条件是任一结点的键值___于其左孩子(及其子孙)的键值且____于其右孩子(及其子孙)的键值。
3．中序遍历一棵二叉排序树所得到的结点访问序列是键值的_____序列。
4．二叉排序树上的查找长度不仅与______有关，也与二叉排序树的________有关。
5．折半查找方法仅适用于这样的表：表中的记录必须______，其存储结构必须是_______。 6．按照排序过程涉及的存储设备的不同，排序可分为________排序和________排序。 7．请填空完成顺序查找算法程序：在线性表v中查找值为k的元素 struct sqlist {
int elem[MAXSIZE]; int last; };
int seqsearch (struct sqlist v, int k) { int i;
for(i=1;i<=v.last;i++) if(______________) return i; /*查找成功，返回被查元素在表中相对位置*/ return 0; /*查找失败，返回0*/ }
8．请填空完成改进型的顺序查找算法程序：在线性表v中查找值为k的元素 struct sqlist {
int elem[MAXSIZE]; int last; };
int seqsearch (struct sqlist v, int k) { int i;
12
v.elem[0]=k; _____________
while(_____________) i--;
return i; /*返回被查元素在表中相对位置，0为失败，其他为成功*/ }
9. 请填空完成对分查找算法程序：在线性表v中查找值为x的元素 struct sqlist {
int elem[MAXSIZE]; int last; };
int search (struct sqlist v, int x ) { int low, high, mid; low = 1; high = v.last; while (_____________)
{ mid = ( low + high )/2; //中间位置元素下标 if (_____________)
return mid; //返回被查元素在表中相对位置 if (_____________)
high=mid - 1; //取前半部分 else
_____________ //取后半部分 }
return (-1); //查找失败，返回-1 }
10. 请填空完成选择排序算法程序：在具有n个元素的线性表R按关键字进行排序struct record {
int key;
int otheritem; };
void selectsort(struct record R[],int n)
{ /*注意待排记录放在R[1]到R[n]中*/ int i,j,k; struct record temp; for(i=1;i 13 三、判断题 1．分块查找方法的平均查找长度低于顺序查找，高于折半查找。 2．在任一二叉排序树上查找某个结点的查找时间都小于用顺序查找法查找同样结点的线性表的查找时间。 3．虽然关键字序列的顺序不一样，但依次生成的二叉排序树却是一样的。 四、简答应用题 1. 将关键字序列{26,25,3,38, 6,7,12,24}依次填入长度为n=12的线性哈希表中，哈希码为i=INT(k / 4) + 1，并指出各关键字元素在插入过程中的冲突次数。 2. 依次输入以下元素序列：12,6,3,20,18,34,6，请按照输入的顺序构造一棵二叉排序树，并计算出要在这棵二叉排序树中查找18，需要比较多少次？ 3. 有如下序列：12,6,20,18,34,10，请分别写出用冒泡法、选择法、插入法对该序列进行排序的过程，并作出适当的标示。 14 第四章 资源管理技术 一、选择题 1．操作系统是计算机系统的一种【 】。 A．应用软件 B．系统软件 c．通用软件 D．工具软件 2．允许多个用户以交互方式使用计算机的操作系统是【 】。 A．分时操作系统 B．批处理单道系统 C．实时操作系统 D．批处理多道系统 3．下列系统中【 】是实时系统。 A．计算机图像处理系统 B．办公自动化系统 C．化学反应堆控制系统 D．计算机辅助设计系统 4． 操作系统是一种系统软件，它【 】。 A．控制程序的执行 B．管理计算机系统的资源 C．方便用户使用计算机 D．管理计算机系统的资源和控制程序的执行 5． 实时操作系统对可靠性和安全性要求极高，它【 】。 A．十分注重系统资源的利用率 B．不强调响应速度 C．不强求系统资源的利用率 D．不必向用户反馈信息 6． 【 】为用户分配主存空间，保护主存中的程序和数据不被破坏，提高主存空间的利用率。 A．处理器管理 B．存储管理 C．文件管理 D．作业管理 7． 财务管理软件是一种专用程序,它属于【 】 A．系统软件 B．应用软件 C．接口软件 D．支援软件 8． 在多道程序设计技术的计算机系统中，中央处理器【 】。 A．只能被一个程序占用 B．可以被多个程序同时占用 C．可以被多个程序交替占用 D．可以被操作系统和另一个程序同时占用 二、填空题 1．计算机是由硬件系统和_______系统组成。 2．使计算机系统使用方便和______是操作系统的两个主要设计目标。 3．批处理操作系统、____________和实时操作系统是基本的操作系统。 4．用户要求计算机系统中进行处理的一个计算机问题称为________。 5．在多道操作系统控制下，允许多个作业同时装入________，使中央处理器轮流地执行各个作业。 6．批处理操作系统提高了计算机系统的_________，但在作业执行时用户不能直接干预作业的执行。 7．在分时系统中，每个终端用户每次可以使用一个由_______规定的CPU时间。 8．分时系统具有同时性、独立性、及时性和________等特点。 9．若干个进程均因互相等待对方所占有的资源而无限地等待，使计算机系统无法继续正常运行的现象，称之为________。 10．当多个进程需要对系统中的同一个数据块进行操作时，进程之间常用的通信方式有两种：当多个进程共享数据块或其他排他性使用的资源时，不能同时进入存取或使用，这种称为_________；进程之间为了合作完成一个任务，而需要互相等待和互相交换信息的相互制约关系称为_________。 三、简答题 1．计算机系统的资源包括哪些? 2．为计算机设计操作系统要达到什么目的?设计时应考虑哪些目标? 3．简述操作系统的五大功能。 15 百度搜索“70edu”或“70教育网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，70教育网，提供经典综合文库2024现代科技学院《软件技术基础》练习题+答案(3)在线全文阅读。
相关推荐：
