算法与数据结构实验报告第九章查找

数据结构课件

第九章 查找

一、 选择题

1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。

A． (n-1)/2 B. n/2 C. (n+1)/2 D. n 2. 下面关于二分查找的叙述正确的是 ( )

A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 C. 表必须有序，而且只能从小到大排列

B. 表必须有序且表中数据必须是整型，实型或字符型 D. 表必须有序，且表只能以顺序方式存储

3. 用二分（对半）查找表的元素的速度比用顺序法( )

A．必然快 B. 必然慢 C. 相等 D. 不能确定 4. 具有12个关键字的有序表，折半查找的平均查找长度（ ） A. 3.1 B. 4 C. 2.5 D. 5 5．当采用分块查找时，数据的组织方式为 ( )

A．数据分成若干块，每块内数据有序

B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块

C. 数据分成若干块，

第九章 查找

一、填空题

1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 。

2. 线性有序表（a1，a2，a3，?，a256)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索 次。设有100个结点，用二分法查找时，最大比较次数是 。

3. 假设在有序线性表a[1..20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 ,其下标从小到大依次是 ____，平均查找长度为 。

4．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 比较大小。

5. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是 。 6. 散列法存储的基本思想是由 决定数据的存储地址。

7. 有一个表长为m的散列表，初始状态为空，现将n（n

8、设一哈希表表长M为100 ，用除留余数法构造哈希函数，即H

第九章 查找 习题及答案

一、基础知识题

1.对含有n个互不相同元素的集合，同时找最大元和最小元至少需进行多少次比较?

2.若对具有n个元素的有序的顺序表和无序的顺序表分别进行顺序查找，试在下述两种情况下分别讨论两者在等概率时的平均查找长度：(1)查找不成功，即表中无关键字等于给定值K的记录；(2)查找成功，即表中有关键字等于给定值K的记录。

3.画出对长度为18的有序的顺序表进行二分查找的判定树，并指出在等概率时查找成功的平均查找长度，以及查找失败时所需的最多的关键字比较次数。 答：如图：

4.为什么有序的单链表不能进行折半查找?

5.设有序表为(a,b,c,e,f,g,i,j,k,p,q),请分别画出对给定值b,g和n进行折半查找的过程。

6.将(for, case, while, class, protected, virtual,

public, private, do, template, const ,if,

int)中的关键字依次插入初态为空的二叉排序树中，请画出所得到的树T。然后画出删去for之后的二叉排序树T',若再将for

插入T'中得到的二叉排序树T''是否与T相同?最后给出T\的先序、中序和后序序列。

答：二

1. 用二分（对半）查找表的元素的速度比用顺序法( )

A． 必然快 B. 必然慢 C. 相等 D. 不能确定

2. 具有12个关键字的有序表，折半查找的平均查找长度（ ） A. 3.1 B. 4 C. 2.5 D. 5

3．如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用( )查找法。

A. 分块查找 B. 顺序查找 C. 折半查找 D. 基于属性

4．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( ) 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)

5. 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( ) 型调整以使其平衡。

A. LL

第九章 查 找

一，选择

1. 对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( )

A．（N+1）/2 B． N/2 C．N D． [（1+N）*N ]/2 2. 对线性表进行二分查找时，要求线性表必须（ ）

A.以顺序方式存储 B.以顺序方式存储,且数据元素有序 C.以链接方式存储 D.以链接方式存储,且数据元素有序

3. 散列函数有一个共同的性质，即函数值应当以( )取其值域的每个值。

A. 最大概率 B. 最小概率 C. 平均概率 D. 同等概率 4. 具有12个关键字的有序表，折半查找的平均查找长度（ ） A. 3.1 B. 4 C. 2.5 D. 5

5. 设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地

址法构造散列表，散列函数为H（key）=key MOD 13,散列地址为1的链中有（ ）个记录。

A．1 B. 2 C. 3 D. 4

数据结构课程（本科）第九章试题

一、单项选择题

1. 若待排序对象序列在排序前已按其排序码递增顺序排列，则采用（ ）方法比较次数最少。

A. 直接插入排序 B. 快速排序 C. 归并排序 D. 直接选择排序

2. 如果只想得到1024个元素组成的序列中的前5个最小元素，那么用（ ）方法最快。 A. 起泡排序 B. 快速排序 C. 直接选择排序 D. 堆排序

3. 对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，

直到子序列为空或只剩一个元素为止。这样的排序方法是（ ）。

A. 直接选择排序 B. 直接插入排序 C. 快速排序 D. 起泡排序

4. 对5个不同的数据元素进行直接插入排序，最多需要进行（ ）次比较？

A. 8 B. 10 C. 15 D. 25

5. 如果输入序列是已经排好顺序的，则下列算法中（ ）算法最快结束？

A. 起泡排序 B. 直接插入排序 C. 直接选择排序 D. 快速排序

6. 如果输入序列是已经排好顺序的，则下列算法中（

数据结构与算法

实 验 报 告

编制教师 袁宇丽 审定 何文孝

（适用于计算机科学学院2012级本科学生）

专业: 班级: 级 班 学号:________________________ 姓名:________________________ 2013至2014学年第二学期

计算机科学学院

实验名称：线性表的应用 指导教师： 余文春 实验日期：2014年 月 日 实验地点：北503 成绩： 实验目的：

1、 掌握线性表及其顺序存储与链式存储结构的概念。 2、 掌握两种存储方式的基本运算、实现方法和技术。 3、 灵活应用线性表进行程序设计，解决实际问题。 实验内容：

约瑟夫(Joseph)问题的一种描述是：编号为1，2，?，n的n个人按顺时针方向围坐一圈，一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，从他在顺时针方向上的下一个人开始重新从1报数，同样报到m的人出列，如此下去，直至所有人全部出列为止。利用循环链表为存储结构模拟此过程

金陵科技学院实验报告

学 生 实 验 报 告 册

课程名称：算法与数据结构

金陵科技学院实验报告

实验项目名称： 顺序表 实验学时： 2 同组学生姓名： 实验地点： 工科楼A205 实验日期： 2013年10月16日 实验成绩： 批改教师： 批改时间：

金陵科技学院实验报告

实验1 顺序表

一、实验目的和要求

掌握顺序表的定位、插入、删除等操作。

二、实验仪器和设备

Turbo C 2.0

三、实验内容与过程（含程序清单及流程图）

1、必做题

（1） 编写程序建立一个顺序表，并逐个输出顺序表中所有数据元素的值。

编写主函数测试结果。

（2） 编写顺序表定位操作子函数，在顺序表中查找是否存在数据元素x。

如果存在，返回顺序表中和x值相等的第1个数据元素的序号（序号从0开始编号）；如果不存在，返回－1。编写主函数测试结果。 （3） 在递增有序的顺序表中插入一个新结点x，保持顺序表的有序性。

解题思路：首先查找插入的位置，再移位，最后进行插入操作；从第一个元素

数据结构实验报告

题目： 线性表 班级：网络工程1401班 学号： 1408020106 指导教师： 高峰 日期： 2016/7/6

实验一：线性表

一：实验要求

掌握数据结构中线性表的基本概念。

熟练掌握线性表的基本操作：创建、插入、删除、查找、输出、求长度及合并并运算在顺序存储结构撒谎能够的实验。 熟练掌握链表的各种操作和应用。

二．实验内容

1. 编程实现在顺序存储的有序表中插入一个元素（数据类型为整型）。

2. 编程实现把顺序表中从i个元素开始的k个元素删除（数据类型为整型）。

三：实验过程及步骤

源代码：

#include #include

#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct{ int * elem; int length; int listsize; }SqList; //SqList sq;

void InitList_Sq(SqList *sq) //初始化列表 {

sq->elem=(int *)malloc(LIST_IN

云南师范大学信息学院

实 验 报 告

学号: 姓名: 班级： 课程名称:大型数据库管理系统 实验名称: Transact-SQL程序结构 实验性质:①综合性实验 ②设计性实验 ③验证性实验 试验时间: 试验地点: 本试验所用的设备:SQL Server2005、计算机一台 实验目的： 1. 理解视图的概念 2. 掌握创建视图、加密视图的方法 3. 掌握试图待检查项和不带检查项的区别 4. 掌握视图更新的概念和方法 实验内容及过程: (1) 针对员工表创建一个视图, 取员工表的前4个属性，要求带WITH ENCRYPTION。使用sp_helptext和在syscomments表中分别观察定义的文本。最后利用定义的视图进行查询。 代码如下： use xmgl1 GO if exists (select table_name from information_schema.views where table_name ='员工表_视图') drop view 员工表_视图 go create view 员工表_视图 with encryption as select 员工号,姓名,性别,出生年月 from 员