下载文档原格式
1、静态查找表和动态查找表的区别是( )。
A.所包含的数据元素的类型不同B.施加其上的操作不同C.它们的逻辑结构相同D.以上都不对正确答案：B解析：B、若在查找的同时对表做修改操作(如插入和删除)，则相应的查找表称之为动态查找表。
若在查找中不涉及表的修改操作，则相应的查找表称之为静态查找表。
2、顺序查找法适合于存储结构为( )的线性表。
A.索引存储B.压缩存储C.顺序存储或者链式存储D.哈希存储正确答案：C解析：C、顺序查找可以从前向后或者从后向前挨次查找，既适合于顺序存储结构也适合于链式存储结构。
3、采用顺序查找方法查找长度为n 的顺序表时，在等概率时成功查找的平均查找长度为( )。
A.(n-1)/2B.nC.n/2D.(n+1)/2正确答案：D解析：D、顺序查找时，元素ai 需i 次比较，成功查找的平均查找长度=(1+2+ …+n)/n=(n+1)/2。
4、采用顺序查找方法查找长度为n 的顺序表时，在等概率时不成功查找的平均查找长度为( )。
A.(n-1)/2B.nC.n/2D.(n+1)/2正确答案：B解析：B、当查找的元素不在线性表中时，均需要n 次元素之间的比较。
5、适合于折半查找的数据组织方式是( )。
A.以链表存储的有序线性表B.以顺序表存储的有序线性表C.以链表存储的线性表D.以顺序表存储的线性表正确答案：B解析：B、折半查找的数据必须是有序的。
此外，折半查找中需要确定查找区间，这要求存储结构最好具有随机存取特性，而顺序表满足这个特性。
6、采用折半查找方法查找长度为n 的线性表，当n 很大时，在等概率时不成功查找的平均查找长度为( )。
n)A. O(nlog2B. O(n2)C. O(n)n)D. O(log2正确答案：D解析：D、采用折半查找时，若n 很大，对应的判定树可以看成是一棵满二叉树，失败节点(外部节点)集中在最下一层，落在每一个失败节点时比较的次都均为log n。
27、设有100 个元素的有序表，采用折半查找方法，在等概率时成功时最大的比较次数是( )。
实验五查找的应用一、实验目的：1、掌握各种查找方法及适用场合，并能在解决实际问题时灵活应用。
2、增强上机编程调试能力。
二、问题描述1.分别利用顺序查找和折半查找方法完成查找。
有序表（3,4,5,7,24,30,42,54,63,72,87,95）输入示例：请输入查找元素：52输出示例：顺序查找：第一次比较元素95第二次比较元素87 ……..查找成功，i=**/查找失败折半查找：第一次比较元素30第二次比较元素63 …..2.利用序列（12,7,17,11,16,2,13,9,21,4）建立二叉排序树，并完成指定元素的查询。
输入输出示例同题1的要求。
三、数据结构设计（选用的数据逻辑结构和存储结构实现形式说明）（1）逻辑结构设计顺序查找和折半查找采用线性表的结构，二叉排序树的查找则是建立一棵二叉树，采用的非线性逻辑结构。
（2）存储结构设计采用顺序存储的结构，开辟一块空间用于存放元素。
（3）存储结构形式说明分别建立查找关键字，顺序表数据和二叉树数据的结构体进行存储数据四、算法设计（1）算法列表（说明各个函数的名称，作用，完成什么操作）序号 名称 函数表示符 操作说明1 顺序查找 Search_Seq 在顺序表中顺序查找关键字的数据元素2 折半查找 Search_Bin 在顺序表中折半查找关键字的数据元素3 初始化 Init 对顺序表进行初始化，并输入元素4 树初始化 CreateBST 创建一棵二叉排序树5 插入 InsertBST 将输入元素插入到二叉排序树中6 查找 SearchBST在根指针所指二叉排序树中递归查找关键字数据元素 （2）各函数间调用关系（画出函数之间调用关系）typedef struct { ElemType *R; int length;}SSTable;typedef struct BSTNode{Elem data; //结点数据域 BSTNode *lchild,*rchild; //左右孩子指针}BSTNode,*BSTree; typedef struct Elem{ int key; }Elem;typedef struct {int key;//关键字域}ElemType;（3）算法描述int Search_Seq(SSTable ST, int key){//在顺序表ST中顺序查找其关键字等于key的数据元素。
数据结构上机实验五实验内容:查找表和内部排序的基本算法实验要求:1) 基本操作要作为函数被调用，做到模块化.2) 基本上实现每个实验题目的要求.分组要求：可单独完成，也可两人一组。
实验目的:1)熟悉C/C++基本编程,培养动手能力.2)通过实验,加深对查找算法的理解.评分标准：1) 只完成第一和第二题，根据情况得4，5-分；2）完成前3题，根据情况得5，6分；3）在2）基础上，选做四）中题目，根据情况得6，7分。
题目:一)顺序表与有序表的查找(1)建立一个顺序表，利用教材9.1.1的顺序查找算法进行查找；(2)建立一个有序表，利用折半法进行查找；(3)试将把(2)中的折半法改用递归算法实现；二)二叉排序树的一些基本操作(1)利用二叉链表的存储形式，从键盘输入建立一棵二叉排序树；(2)对（1）中建立的二叉排序树进行中序遍历并打印；(3)编写算法，判断一棵二叉树是否为二叉排序树。
(4)在（1）建立的二叉排序树中，查找一个树中不存在的关键字后并插入，之后打印该树；三)排序（1）插入排序——已知序列{17，18，60，40，7，32，73，65，85}建立一个顺序表，采用插入排序算法的实现升序排序，打印排序结果；（2）交换排序——已知序列{503，87，512，61，908，170，897，275，652，462}(1)建立一个顺序表，采用冒泡排序法实现升序排序，并打印每趟排序结果；(2)建立一个顺序表，采用快速排序法实现升序排序，并打印每趟排序结果，与(1)做比较；（3）选择排序——已知序列{42，13，24，91，23，16，05，88}利用简单选择排序，实现上述序列的降序排序；四）选作题（1）试构造一个算法，从键盘输入一组关键字，按哈希函数H(key) = key MOD 13和链地址法处理冲突构来造哈希表,能对关键字进行查找并显示。
如(19,14,23,1,68,20,84,27,55,11,10,79,33).(2)已知序列{503，87，512，61，908，170，897，275，652，462}，采用基数排序法对其作升序排序，打印每一趟的结果。
数据结构的排序与查找算法数据结构是计算机科学中一门重要的基础课程，它研究了数据的组织、存储和管理方式。
对于大规模数据的处理，排序和查找算法是数据结构中的两个核心问题。
本文将介绍常见的排序和查找算法，包括其原理、实现方法以及应用场景。
一、排序算法排序算法是将一组无序的数据按照特定的规则进行排列的过程。
常见的排序算法包括冒泡排序、插入排序、选择排序、快速排序、归并排序等。
1. 冒泡排序冒泡排序是一种简单的排序算法，它重复地遍历要排序的数列，每次比较相邻的两个元素，如果顺序错误就交换它们，直到没有再需要交换的元素为止。
2. 插入排序插入排序是一种简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序的数据，在已排序序列中从后向前扫描，找到相应位置插入。
3. 选择排序选择排序是一种简单直观的排序算法，它的工作原理是每次从待排序的数据中选择最小（或最大）的一个元素，与待排序数据的第一个元素交换，直到所有待排序数据排序完成。
4. 快速排序快速排序是一种分治的排序算法，它使用了递归的思想。
快速排序首先选择一个基准元素，将小于基准的元素放在左边，大于基准的元素放在右边，然后对左右两个子序列进行递归排序。
5. 归并排序归并排序是一种分治的排序算法，它的核心思想是将待排序序列拆分成若干个子序列，分别对子序列进行排序，最后将排好序的子序列合并成最终的排序结果。
二、查找算法查找算法是在一组数据中寻找特定元素的过程。
常见的查找算法包括线性查找、二分查找、哈希查找等。
1. 线性查找线性查找是一种简单直观的查找算法，它从数据的起始位置开始，依次比较每个元素，直到找到目标元素或遍历完整个数据。
2. 二分查找二分查找是一种高效的查找算法，它要求待查找的数据必须是有序的。
二分查找从有序数据的中间元素开始比较，根据比较结果可以确定目标元素在左半部分还是右半部分，然后递归地在相应半部分继续查找，直到找到目标元素或确定不存在。
3. 哈希查找哈希查找是一种利用哈希表进行查找的算法，它通过将关键字映射到哈希表中的位置，将查找的时间复杂度降低到常数级。
哈尔滨工业大学(深圳)数据结构实验报告查找与排序学院: 计算机科学与技术一、问题分析此题是一道排序问题，排序的方法有很多种，此题我用的是堆排序，这是一种不稳定排序，但时间复杂度较低，比较快。
计算机首先需要把文件中的数据读入内存中，用动态数组存储数据，然后建立数据结构，然后建立堆，比较子节点和父节点大小，降序排列，之后互换头结点与尾节点，再递归重复即可。
查找的话，依次查找对比即可。
二、详细设计2.1 设计思想将股票的代码，交易日期，及开盘价等信息分别用不同的动态数组存储起来。
因为要根据交易量的降序进行排序所以应将交易量的信息另外用一个float型的数组保存起来便于比较。
排序：使用一个下标数组用来模拟交易量的堆排序，将下标数组进行降序排序。
再根据下标数组里的值将股票信息保存在新的文件中。
查看：因为录入文件时是先把股票的代码相同的信息存入数组的。
所以查找时比较股票的代码，找到该代码后比较交易日期。
最后输出交易量。
2.2 存储结构及操作(1) 存储结构（一般为自定义的数据类型，比如单链表，栈等。
）vector<string> a;//股票代码vector<string> b;//股票交易日期vector<string> c;//股票开盘价_最高价_最低价_收盘价vector<float> d;//将交易量转换为float用于比较不过有的会被舍去vector<string> e;//交易量的原始数据用于输出到排序的文件中(2)涉及的操作（一般为自定义函数，可不写过程，但要注明该函数的含义。
）read_file() 将文件信息分别保存在上述存储结构中HeapAdjust(vector<long>& x,long s,long n) 小顶堆的调整函数HeapSort() 用堆排序进行交易量的降序排序并存储在指定文件中serach() 查找某交易日期某股票的交易量2.3 程序整体流程开始 A读入文件，存入数组 B排序 C查找 D结束 E2.堆排序示意图（由于堆排序描述时需要具体数据，所以只弄到示意图）三、用户手册1>将股票文件先存入指定文件夹中，根据提示输入文件名字按回车即可2>先在指定文件夹新建你要保存的文件后将文件的名字输入3>根据提示输入股票代码及交易日期，以空格隔开。
数据结构复习--排序和查找现在正在学习查找和排序，为了节省时间提⾼效率，就正好边学习边整理知识点吧！知识点⼀：⼆分查找/折半查找1.⼆分查找的判定树（选择题）下列⼆叉树中，可能成为折半查找判定树（不含外部结点）的是： (4分)1.2.3.4.注：折半查找判定树是⼀棵⼆叉排序树，它的中序遍历结果是⼀个升序序列，可以在选项中的树上依次填上相应的元素。
虽然折半查找可以上取整也可以下取整但是⼀个查找判定树只能有⼀种取整⽅式。
如果升序序列是偶数个，那么终点应该偏左多右少。
在2选项中，由根节点左⼦树4个节点⽽右⼦树5个节点可以确定⽤的是向下取整策略，但是它的左⼦节点在左⼦树种对应的终点左边2个，右边个，明显是上取整策略，策略没有统⼀，所以是错的。
其他的选项类似分析。
2.⼆分查找法/折半查找法已知⼀个长度为16的顺序表L，其元素按关键字有序排列。
若采⽤⼆分查找法查找⼀个L中不存在的元素，则关键字的⽐较次数最多是： (2分)1. 72. 63. 54. 4 注：⼀次找到最边界的那⼀个树的情况下有最多次数 这个题中结点数16是个偶数：第⼀次（0+15）/2 7 第⼆次（8+15）/2 11第三次（12+15）/2 14 第四次（14+15）/2 14 第五次（15+15）/2 15（下取整的就向右计算求最多次数）第⼀次（0+15）/2 8 第⼆次（0+7）/2 4 第三次（0+3）/2 2 第四次（0+1)/2 0第五次（0+0）/2 0（下取整的话就向左求最多次数）若结点数是奇数15：第⼀次（0+14）/2 7 第⼆次（ 0+6）/2 3 第三次（0+2）/2 1第四次（0+0）/2 0第⼀次（0+14）/2 7 第⼆次（8+14）/2 11 第三次（12+14）/2 13第四次（14+14）/2 0这时候向左或者向右都是OK的（因为得到的数都是能够被2整除的）但是划重点了折半查找⼀个有序表中不存在的元素，若向下取整，则要最多⽐较[log2n]+1次，若向上取整，则要最多⽐较[log2(n+1)],其实就是求树的深度.（这⼀块⾃⼰的说法可能不够准确，希望⼤家看到有问题的可以指出来）结合实际，我们⽤[log2n]+1来算更简单并且计算[log2n]要取整数，因为可能会存在不是满⼆叉树的情况。
数据结构查找与排序练习题答案一、选择题1.对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( ) A．（N+1）/2 B. N/2 C. N D. [（1+N）*N ]/22.适用于折半查找的表的存储方式及元素排列要求为( )A．链接方式存储，元素无序 B．链接方式存储，元素有序C．顺序方式存储，元素无序D．顺序方式存储，元素有序3.当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( )A．必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减4．有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为（）。
A．35/12 B.37/12 C.39/12 D.43/125.折半查找的时间复杂性为（）A. O（n2）B. O（n）C. O（nlogn）D. O（logn）6.对有18个元素的有序表作折半查找，则查找A[3]的比较序列的下标为（）A.1，2，3B.9，5，2，3C.9，5，3D.9，4，2，37.设有序表的关键字序列为{1，4，6，10，18，35，42，53，67，71，78，84，92，99}，当用二分查找法查找健值为84的结点时，经（）次比较后查找成功。
A.2B. 3C. 4D.128.用n个键值构造一棵二叉排序树，最低高度为（）A.n/2B.、nC.lognD.logn+19．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( ) 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.设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=key% 13,散列地址为1的链中有（）个记录。
西北工业大学《数据结构》实验报告实验题目：排序与查找班号：09040802 学号：2008302360 姓名：崔昌浩完成时间：2011.1.12查找和排序一.需求分析1.对以下4种常用的查找算法进行比较：顺序查找、折半查找、索引查找、二叉排序树查找。
2.对以下6种常用的内部排序算法进行比较：起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。
3．待查找或排序的表长不小于5000；其中的数据要用伪随机数产生程序产生；至少要用5 组不同的输入数据作比较；比较的指标为有关键字参加的比较次数或关键字的移动次数（关键字交换计为3 次移动）。
4．要考虑并统计一些特殊情况下（如完全正序、完全逆序）情况下的关键字比较次数或移动次数；要考虑对于随机数据执行某种算法（如折半查找、索引查找、二叉排序树查找）时需要的额外计算。
二.概要设计1.各种查找排序的概念如下:①.直接排序算法描述：经过i-1遍处理后，L[1..i-1]己排好序。
第i遍处理仅将L[i]插入L[1..i-1]的适当位置，使得L[1..i]又是排好序的序列。
要达到这个目的，我们可以用顺序比较的方法。
首先比较L[i]和L[i-1]，如果L[i-1]≤ L[i]，则L[1..i]已排好序，第i遍处理就结束了；否则交换L[i]与L[i-1]的位置，继续比较L[i-1]和L[i-2]，直到找到某一个位置j(1≤j≤i-1)，使得L[j] ≤L [j+1]时为止。
②.冒泡排序算法描述：核心思想是扫描数据清单，寻找出现乱序的两个相邻的项目。
当找到这两个项目后，交换项目的位置然后继续扫描。
重复上面的操作直到所有的项目都按顺序排好。
③.快速排序算法描述：首先检查数据列表中的数据数，如果小于两个，则直接退出程序。
如果有超过两个以上的数据，就选择一个分割点将数据分成两个部分，小于分割点的数据放在一组，其余的放在另一组，然后分别对两组数据排序。
通常分割点的数据是随机选取的。
数据结构图,查找,内排序的练习及答案数据结构课后练习习题要求：此次练习不要求上交，只是帮助⼤家掌握知识点，便于复习。
第⼋章图⼀．单项选择题（20分）1. 带权有向图G ⽤邻接矩阵A 存储，则Vi 的⼊度等于A 中___D______A. 第i ⾏⾮∞的元素只和B. 第i 列⾮∞的元素之和C. 第i ⾏⾮∞且⾮0的元素之和D. 第i 列⾮∞且⾮0的元素个数2. ⽆向图的邻接矩阵是⼀个___A____A. 对称矩阵B. 零矩阵C. 上三⾓阵D. 对⾓矩阵3. 在⼀个⽆向图中，所有顶点的度之和等于边数的__C____倍A. 1/2B. 1C. 2D. 44. ⼀个有n 个顶点的⽆向图最多有___C____条边。
A. nB. n(n-1)C. n(n-1)/2D.2n5. 对于⼀个具有n 个顶点的⽆向图，若采⽤邻接矩阵表⽰，则该矩阵⼤⼩是__D_____A. nB. 2)1(?nC. n-1D. 2n6. ⼀个有向图G 的邻接表存储如右图所⽰，现按深度优先搜索遍历，从V1出发，所得到的顶点序列是___B_____。
A. 1，2，3，4，5B. 1，2，3，5，4C. 1，2，4，5，3D. 1，2，5，3，47. 对右图所⽰的⽆向图，从顶点V1开始进⾏深度优先遍历，可得到顶点访问序列__A______（提⽰：可先画出邻居表图再遍历）A. 1 2 4 3 5 7 6B. 1 2 4 3 5 6 7C. 1 2 4 5 6 3 7D. 1 2 3 4 5 6 78. 如果从⽆向图的任⼀顶点出发进⾏⼀次深度优先搜索即可访问所有顶点，则该图⼀定是__B_____A. 完全图B. 连通图C.有回路D. ⼀棵树9. 任何⼀个⽆向连通图___B___最⼩⽣成树（提⽰：注意最⼩⽣成树的定义，此题易错）A. 只有⼀棵B. ⼀棵或多棵C. ⼀定有多棵D.可能不存在11. 若图的邻接矩阵中主对⾓线上的元素全是0，其余元素全是1，则可以断定该图⼀定是_D_____。
上机报告四
一、上机目的
1、掌握顺序查找、折半查找的基本思想和算法实现，了解怎样对各种查找方法进行时间性能（平均查找长度）分析。
2、掌握各种排序方法的基本思想、排序过程、算法实现，实现冒泡排序算法。
二、上机内容
1、设计一组随机数据，对线性表进行顺序查找，计算平均查找速度。
2、设计一组有序数据，对线性表进行折半查找，计算平均查找速度。
3、以关键字序列（265，301，751，129，937，863，742，694，76，438）作为输入数据，
采用冒泡排序进行排序。
三.原理：
对于有序和无序列表，顺序搜索是 O(n)。
在最坏的情况下，有序列表的二分查找是 O(log^n )。
哈希表可以提供恒定时间搜索。
冒泡排序，选择排序和插入排序是 O(n^2 )算法。
shell排序通过排序增量子列表来改进插入排序。
它落在 O(n) 和 O(n^2 ) 之间。
归并排序是 O(nlog^n ），但是合并过程需要额外的空间。
快速排序是 O(nlog^n ），但如果分割点不在列表中间附近，可能会降级到O(n^2 ) 。
它不需要额外的空间。
四.核心代码
（1）插入排序
def insert(ls):
for i in range(len(ls)-1):
print('\033[036m',i,ls,'\033[0m')
min_=ls[i]
index=i
for j in range(i+1,len(ls)):
if ls[j]<min_:
min_=ls[j]
index=j
ls.insert(i,min_)
del ls[index+1]
return ls
a=[0,11,22,33,44,55,66,77,88,99]
random.shuffle(a)
print(insert(a))
冒泡排序
def bubble(ls):
go_on=1
for i in range(len(ls)-1):
print('\033[036m',i,ls,'\033[0m')
go_on=0
for j in range(len(ls)-1,i,-1):
if ls[j]<ls[j-1]:
ls[j-1],ls[j]=ls[j],ls[j-1]
go_on=1
if not go_on:
break
return ls
a=[0,11,22,33,44,55,66,77,88,99]
random.shuffle(a)
print(bubble(a))
查找算法
（2）顺序查找
def sequential(ls,value):
for i in range(len(ls)):
print('\033[036m',i,ls[i],'\033[0m') # show steps
if ls[i]==value:
return i
l=[0,11,22,33,44,55,66,77,88,99]
print(l)
for i in range(9):
v=int(input('look up number').strip())
print(sequential(l,v))
（3）二分查找
def binary(ls,value):
head,tail=0,len(ls)-1
mid=(head+tail)//2
while head<=tail:
if ls[mid]==value:
return mid
elif value<ls[mid]:
print('\033[036m',mid,ls[mid],'\033[0m') # show steps tail=mid-1
mid=(head+tail)//2
elif ls[mid]<value:
print('\033[036m',mid,ls[mid],'\033[0m') # show steps head=mid+1
mid=(head+tail)//2
l=[0,11,22,33,44,55,66,77,88,99]
print(l)
for i in range(9):
v=int(input('look up number').strip())
print(binary(l,v))
结果分析：顺序查找
二分查找：。
