查找和排序的实现
实验:查找和排序的实现
1.实验目的
1）掌握折半查找,顺序查找和黄金比例查找的方法；
2）掌握直接插入排序，折半插入排序和快速排序的方法。
2. 实验内容：
(1)建立顺序表;
(2）实现以下算法：
输入要查询的值，经过顺序查找和折半查找还有黄金比例查找，找出该元素的位置。
顺序表经过直接插入排序，折半插入排序和快速排序后输出。
3.设计思想
1．(非递减序列)顺序查找：从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若相等，则查找成功。
2．(非递减序列)折半查找：以处于区间中间位置记录的关键字和给定值比较，若相等则成功，如不等，则缩小范围，直至新的区间中间位置记录的关键字等于给定值或区间大小小于零时为止
3.(非递减序列)黄金比例查找：以处于区间黄金比例处（0.618）位置记录的关键字和给定值比较，注意，不能直接用mid=(low+high)*0.618，这样mid会溢出，应该改为mid=(high-low)*0.618+low。
4.直接插入排序：每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。它是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序属于稳定的排序，最坏时间复杂性为O(n^2)，空间复杂度为O(1)。
5.折半插入排序：是对插入排序算法的一种改进，由于排序算法过程中，就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。[
6.快速排序：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
4.代码实现
#include
#include
#define LIST_INIT_SIZE 100
#define LISTNCREMENT 10
typedef struct SqList
{
int *elem;
int length;
int listsize;
}SqList;
void InitList_Sq(SqList &L)//数据结构初始化，构造空的表{
L.elem=(int *)malloc(LIST_INIT_SIZE *sizeof(int));
if(!L.elem) exit(1);
L.length=0;
L.listsize=LIST_INIT_SIZE;
}
void Creat(SqList &L)//建立顺序表
{
int n;
cout<<"请输入存储的个数:";
cin>>n;
cout<<"请按非递减顺序输入元素:" < for(int i=1;i<=n;i++) cin>>L.elem[i]; L.length=n; } int search_Seq(SqList L,int key,int &d){//顺序查找 L.elem[0]=key; int i; d=d+1; for(i=L.length;key!=L.elem[i];--i) d=d+1; return i; } int halfserch(SqList L,int key2,int &k){ L.elem[0]=key2; int low=1; int high; int mid; high=L.length; k=0; while(low<=high){ mid=(low+high)/2; k=k+1; if(key2==L.elem[mid]) return mid; else if (key2<=L.elem[mid]) high=mid-1; else low=mid+1; } return 0; } int Newserch(SqList L,int key,int &d){ L.elem[0]=key; int low=1; int high; int mid; high=L.length; d=0; while(low<=high){ mid=(high-low)*0.618+low; d=d+1; if(key==L.elem[mid]) return mid; else if (key<=L.elem[mid]) high=mid-1; else low=mid+1; } return 0; } void main() { SqList L; cout<<"创建顺序表"< InitList_Sq(L); Creat(L); int a,b,c,d,e; d=0; cout<<"请输入要查询的值:"< cin>>a; c=search_Seq(L,a,d); cout<<"做顺序查找的执行次数为："< cout<<"经过顺序查找，您查询的元素位置是："< cout<<"做折半查找的执行次数为："< cout<<"经过折半查找，您查询的元素位置是："< e=Newserch(L,a,d); cout<<"做折半查找的执行次数为："< cout<<"经过0.618查找，您查询的元素位置是："< } 5.运行与测试 第一组： 第二组： 数据结构课后练习 习题要求： 此次练习不要求上交，只是帮助大家掌握知识点，便于复习。 第八章 图 一．单项选择题（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/2 B. 1 C. 2 D. 4 4. 一个有n 个顶点的无向图最多有___C____条边。 A. n B. n(n-1) C. n(n-1)/2 D.2n 5. 对于一个具有n 个顶点的无向图，若采用邻接矩阵表示，则该矩阵大小是__D_____ A. n B. 2)1(?n C. n-1 D. 2 n 6. 一个有向图G 的邻接表存储如右图所示，现按深 度优先搜索遍历，从V1出发，所得到的顶点序 列是___B_____。 A. 1，2，3，4，5 B. 1，2，3，5，4 C. 1，2，4，5，3 D. 1，2，5，3，4 7. 对右图所示的无向图，从顶点V1开始进行深度 优先遍历，可得到顶点访问序列__A______ （提示：可先画出邻居表图再遍历） A. 1 2 4 3 5 7 6 B. 1 2 4 3 5 6 7 C. 1 2 4 5 6 3 7 D. 1 2 3 4 5 6 7 8. 如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是__B_____ A. 完全图 B. 连通图 C.有回路 D. 一棵树 9. 任何一个无向连通图___B___最小生成树（提示：注意最小生成树的定义，此题易错） A. 只有一棵 B. 一棵或多棵 C. 一定有多棵 D.可能不存在 11. 若图的邻接矩阵中主对角线上的元素全是0，其余元素全是1，则可以断定该图一定是_D_____。 A. 无向图 B. 不是带权图 C. 有向图 D. 完全图 二．填空题 1. 有n 个结点的无向图最多有__n(n-1)/2___条边。 实验七查找、排序的应用 一、实验目的 1、本实验可以使学生更进一步巩固各种查找和排序的基本知识。 2、学会比较各种排序与查找算法的优劣。 3、学会针对所给问题选用最适合的算法。 4、掌握利用常用的排序与选择算法的思想来解决一般问题的方法和技巧。 二、实验内容 [问题描述] 对学生的基本信息进行管理。 [基本要求] 设计一个学生信息管理系统，学生对象至少要包含：学号、姓名、性别、成绩1、成绩2、总成绩等信息。要求实现以下功能：1．总成绩要求自动计算； 2．查询：分别给定学生学号、姓名、性别，能够查找到学生的基本信息（要求至少用两种查找算法实现）； 3．排序：分别按学生的学号、成绩1、成绩2、总成绩进行排序（要求至少用两种排序算法实现）。 [测试数据] 由学生依据软件工程的测试技术自己确定。 三、实验前的准备工作 1、掌握哈希表的定义，哈希函数的构造方法。 2、掌握一些常用的查找方法。 1、掌握几种常用的排序方法。 2、掌握直接排序方法。 四、实验报告要求 1、实验报告要按照实验报告格式规范书写。 2、实验上要写出多批测试数据的运行结果。 3、结合运行结果，对程序进行分析。 五、算法设计 a、折半查找 设表长为n，low、high和mid分别指向待查元素所在区间的下界、上界和中点,key为给定值。初始时，令low=1,high=n,mid=(low+high)/2，让key与mid指向的记录比较， 若key==r[mid].key，查找成功 若key 三大财务报表的关系分析 摘要：会计报表是会计核算过程的最后结果，也是会计核算工作的总结。会计报表主要包括资产负债表、利润表和现金流量表。资产负债表反应企业报表日财务状况，损益表反应企业会计期间的盈利情况，现金流量表反应企业会计期间的经营、投资、筹资现金流情况。三张报表在编制上相对单独存在，而在财务分析时却相互依存、相互影响。这三张报表所提供的信息为使用者决策和管理提供总括性的资料信息。在市场经济条件下，与企业有经济利害关系的有关方面通常要利用企业的会计信息对企业的财务状况进行分析。会计报表所提供的会计信息资源是会计报表使用者不可缺少的信息来源，是进行有效经济决策的重要依据。 关键词：会计报表；分析；关系；研究;现金动态流向；资本结构。 一、三大报表的概念和包含的内涵 会计报表是根据账簿记录和其他日常核算资料，以一定的指标体系，综合反映企业一定时期财务状况、经营成果和现金流量的一种书写文件。会计报表是会计核算过程的最后结果，也是会计核算工作的总结。会计报表主要包括资产负债表、利润表和现金流量表。这三张报表所提供的信息为使用者决策和管理提供总括性的资料信息。在市场经济条件下，与企业有经济利害关系的有关方面通常要利用企业的会计信息对企业的财务状况进行分析。会计报表所提供的会计信息资源是会计报表使用者不可缺少的信息来源，是进行有效经济决策的重要依据，满足了国家宏观经济管理的要求，满足了投资者决策的需要，满足了企业内部管理的需要，资产负债表是总括地反映会计主体在特定日期（如年末、季末、月末）财务状况的报表；资产负债表的雏形产生于古意大利，随着商业的发展，商贾们对商业融资的需求日益加强。高利贷放贷者出于对贷款本金安全性的考虑，开始关注商贾们的自有资产状况，资产负债表于是孕育而生；利润表它是总括反映企业在某一会计期间（如年度、季度、月份）内经营及其分配（或弥补）情况的一种会计报表；随着近代商业竞争不断加剧，商业社会对企业的信息披露要求越来越高，静态的、局限于时点的会计报表——资产负债表已无法满足信息披露的要 习题九排序 一、单项选择题 1．下列内部排序算法中： A．快速排序 B.直接插入排序 C. 二路归并排序 D.简单选择排序 E. 起泡排序 F.堆排序 （1）其比较次数与序列初态无关的算法是（） （2）不稳定的排序算法是（） （3）在初始序列已基本有序（除去n 个元素中的某 k 个元素后即呈有序， k< 本科学生综合性实验报告 （封面） 项目组长＿郑慧乐＿＿＿学号＿0174280＿＿＿＿ 成员郑慧乐 专业＿物联网＿＿＿班级＿173＿＿＿ 实验项目名称＿＿＿＿＿实验五查找与排序 指导教师及职称＿＿＿黄淑英＿＿＿＿＿＿＿开课学期2018 至＿2019 学年＿第一＿学期上课时间2018 年12 月 3 日 学生实验报告 一、实验目的及要求： 1、目的 1．进一步掌握有序顺序表的折半查找算法。 2．进一步巩固排序的算法，编写对20个及以上的无序数据进行希尔排序和快 速排序的实现程序。 2、内容及要求 1.建立一20个及以上数据的有序顺序表，表中可以仅存放记录的关键字，实现对该有序的折半查找算法，测试数据应充分考虑查找成功和查找不成功两种情况。 2.建立一20个及以上数据的无序顺序表，表中可以仅存放记录的关键字，实现对该无序表进行希尔排序，给出每一趟希尔排序的结果。 3.建立一20个及以上数据的无序顺序表，表中可以仅存放记录的关键字，实现对该无序表进行快速排序，给出每一趟快速排序的结果。 二、仪器用具： DevC++ 三、实验方法与步骤: #include KeyType key; InfoType otherinfo; }RedType; typedef struct { RedType R[MAXSIZE + 1]; int length; }SqList; int Search_Bin (SqList ST, KeyType key) { KeyType low, high, mid; low = 1; high = ST.length; while (low <= high) { mid = (low + high) / 2; if (key == ST.R[mid].key) return mid; else if (key < ST.R[mid].key) high = mid - 1; else low = mid + 1; } return OK; } 实验四：查找与排序 【实验目的】 1.掌握顺序查找算法的实现。 2.掌握折半查找算法的实现。 【实验内容】 1.编写顺序查找程序，对以下数据查找37所在的位置。 5，13，19，21，37，56，64，75，80，88，92 2.编写折半查找程序，对以下数据查找37所在的位置。 5，13，19，21，37，56，64，75，80，88，92 【实验步骤】 1.打开VC++。 2.建立工程：点File->New，选Project标签，在列表中选Win32 Console Application，再在右边的框里为工程起好名字，选好路径，点OK->finish。 至此工程建立完毕。 3.创建源文件或头文件：点File->New，选File标签，在列表里选C++ Source File。给文件起好名字，选好路径，点OK。至此一个源文件就被添加到了你刚创建的工程之中。 4．写好代码 5．编译－＞链接－＞调试 #include "stdio.h" #include "malloc.h" #define OVERFLOW -1 #define OK 1 #define MAXNUM 100 typedef int Elemtype; typedef int Status; typedef struct { Elemtype *elem; int length; }SSTable; Status InitList(SSTable &ST ) { int i,n; ST.elem = (Elemtype*) malloc (MAXNUM*sizeof (Elemtype)); if (!ST.elem) return(OVERFLOW); printf("输入元素个数和各元素的值:"); scanf("%d\n",&n); for(i=1;i<=n;i++) { scanf("%d",&ST.elem[i]); } ST.length = n; return OK; } int Seq_Search(SSTable ST,Elemtype key) { int i; ST.elem[0]=key; for(i=ST.length;ST.elem[i]!=key;--i); return i; } int BinarySearch(SSTable ST,Elemtype key) { int low,high,mid; low=1; high=ST.length; 多选： A: 5.按照用以比较的指标数据的形式不同，比较分析法可分为（全部） A.绝对数指标的比较 B.构成指数的比较C相对数指标的比较 D.动态指数的比较 E.平均数指标的比较 C: 3.财务报表分析的基本资料包括：（全部） A.资产负债表 B.利润表 C.现金流量表 D.所有者权益变动表 E.报表附注 27．长期偿债能力分析对于不同的报表信息使用者有着重要意义，对此理解正确的是（全部） A.管理者通过长期偿债能力分析有利于优化资 本结构 B.管理者通过长期偿债能力分析有利于降低财 务风险 C.股东通过长期偿债能力分析可以判断企业投 资的安全性 D.股东通过长期偿债能力分析可以判断企业投 资的盈利性 E.债权人通过长期偿债能力分析可以判断债权 的安全程度 54.财务报表分析报告的撰写步骤包括（ ABCD ） A.收集整理资料 B.撰写初稿 C.修改定 稿 D.报送或发表 E.收集反馈，再次报送或发表 55.财务报表分析报告的主要撰写方法中问题引导法的优点包括（ BD ） A.报告内容完整 B.重点突出 C.条理清晰 D.格式新颖 E.逻辑性较强 D: 7.对应收账款的分析应从以下几个方面进行 （ ABC ） A.应收账款的规模 B.应收账款的质量 C. 坏账准备政策的影响 22.短期偿债能力的评价方法有（ ABE ） A.评价流动负债和流动资产的数量关系 B.评 价资产的流动性 C.评价负债的流动性 D.比较一年内产生的债务和产生的现金流出 E.比较一年内产生的债务和产生的现金流入 26.对应收账款周转率正确计算有较大影响的因素 有：（ ABCE ） A.季节性经营的企业使用这个指标时不能反映 实际情况 B.大量使用分期付款结算方式 C.大量的销售为现销 D.企业提高应 收账款回收效率 E. 年末销售大幅度上升或下降 40.对净资产收益率进行深入分析评价，可以使用 的方法包括（ CDE ） A.杜邦分析法 B.财务杠杆分析法 C.因 素分析法 D.趋势分析法 E.同业比较分析法 42.杜邦分析法是一个多层次的财务比率分解体 系。对此理解正确的是（全部） A.运用杜邦分析法进行综合分析，就是在每一个 层次上进行财务比率的比较和分析 B. 在分解体系下，各项财务比率可在每个层次 上与本企业历史或同业财务比率比较 C.在分解体系下，通过与历史比较可以识别变动 的趋势，通过与同业比较可以识别存在的差距 D. 在分解体系下，历史比较与同业比较会逐级 向下，覆盖企业经营活动的各个环节 1 *******大学 《数据结构与算法分析》课程设计 题目：数据结构上机试题 学生姓名： 学号： 专业：信息管理与信息系统 班级： 指导教师： 2014年04月 目录 一、顺序表的操作 (2) 【插入操作原理】 (2) 【删除操作原理】 (2) 【NO.1代码】 (3) 【运行截图演示】 (7) 二、单链表的操作 (10) 【创建操作原理】 (10) 【插入操作原理】 (10) 【删除操作原理】 (10) 【NO.2代码】 (11) 【运行截图演示】 (20) 三、顺序栈的操作 (25) 【数值转换原理】 (25) 【NO.3代码】 (26) 【运行截图演示】 (30) 四、查找算法 (32) 【顺序查找原理】 (32) 【折半查找原理】 (32) 【NO.4代码】 (33) 【运行截图演示】 (38) 五、排序算法 (40) 【直接插入排序原理】 (40) 【快速排序原理】 (40) 【NO.5代码】 (41) 【运行截图演示】 (46) 一、顺序表的操作 （1）插入元素操作：将新元素x 插入到顺序表a 中第i 个位置； （2）删除元素操作：删除顺序表a 中第i 个元素。 【插入操作原理】 线性表的插入操作是指在线性表的第i-1个数据元素和第i 个数据元素之间插入一个新的数据元素，就是要是长度为n 的线性表： ()11,,,,,i i n a a a a -………… 变成长度为n+1的线性表： ()11,,,,,,i i n a a b a a -………… 数据元素1i a -和i a 之间的逻辑关系发生了变化。 （其【插入原理】在课本P23的算法2.3有解释） 【删除操作原理】 反之，线性表的删除操作是使长度为n 的线性表： ()111,,,,,,i i i n a a a a a -+………… 变成长度为n-1的线性表： ()111,,,,,i i n a a a a -+………… 数据元素1i a -、i a 和1i a +之间的逻辑关系发生变化，为了在存储结构上放映这个变化，同样需要移动元素。 （其【删除原理】在课本P24的算法2.4有解释） 作业5. 查找、排序 非编程作业参考答案： 1．设有关键字序列{25，40，33，47，12，66，72，87，94，22，5，58}，散 列表长12，散列函数为h(key)=key%11，用线性探查再散列、链地址法处理冲突，请分别画出散列表，并计算在等概率情况下的查找成功的平均查找长度。 线性探查再散列处理冲突： 链地址法处理冲突： 查找时比较1次能够成功的有：25、40、33、12、72、87 比较2次能够成功的有：47 比较3次能够成功的有：66、94 比较5次能够成功的有：5 比较6次能够成功的有：22 比较9次能够成功的有：58 查找成功的ASL=(1*6+2+3*2+5+6+9)/12≈2.83 查找成功的ASL=(1*7+2*3+3*2)/12≈1.58 2．已知待排序序列为{50，86，72，41，45，93，57，46}，请写出按下列排序方法进行升序排序时的第一趟排序结果： ①冒泡排序； ②二路归并排序； ③以第一个元素为枢轴的快速排序； ④堆排序初建堆序列； ⑤取d1=4时的希尔排序； ⑥简单选择排序。 冒泡排序： 50，72，41，45，86，57，46，93 二路归并排序：50，86，41，72，45，93，46，57 快速排序： 46，45，41，50，72，93，57，86 初建堆： 41，45，57，46，50，93，72，86 希尔排序： 45，86，57，41，50，93，72，46 简单选择排序：41，86，72，50，45，93，57，46 3．设计一种方法，以少于2n-3次的比较在顺序存储的n(n>=2)个数中同时找出最大和最小值。 方法1：从n个数中找出最大值放在下标为0的位置——(n-1)次比较； 再在剩余的n-1个数中找到最小值——(n-2)次比较； 总比较次数为2n-3。 方法2：将n个数两两比较，比较的过程中将小的数放在前面，大的数放在后面——(0.5n)次比较； 之后在偶数下标的数中找到最小值（下标从0开始）——(0.5n-1) 次比较； 在奇数下标的数中找到最大值——(0.5n-1)次比较； 总比较次数为1.5n-2，当n>=2时小于2n-3。 实验六、七：查找、排序算法的应用 班级 10511 学号 20103051114 姓名高卫娜 一、实验目的 1 掌握查找的不同方法，并能用高级语言实现查找算法。 2 熟练掌握顺序表和有序表的顺序查找和二分查找方法。 3 掌握排序的不同方法，并能用高级语言实现排序算法。 4 熟练掌握顺序表的选择排序、冒泡排序和直接插入排序算法的实现。 二、实验内容 1 创建给定的顺序表。表中共包含八条学生信息，信息如下： 学号姓名班级C++ 数据结构 1 王立03511 85 76 2 张秋03511 78 88 3 刘丽03511 90 79 4 王通03511 7 5 86 5 赵阳03511 60 71 6 李艳03511 58 68 7 钱娜03511 95 89 8 孙胜03511 45 60 2 使用顺序查找方法，从查找表中查找姓名为赵阳和王夏的学生。如果查找成功，则显示该生的相关信息；如果查找不成功，则给出相应的提示信息。 3 使用二分查找方法，从查找表中查找学号为7和12的学生。如果查找成功，则显示该生的相关信息；如果查找不成功，则给出相应的提示信息。（注意：创建静态查找表时必须按学号的从小到大排列！） 4 使用直接插入排序方法，对学生信息中的姓名进行排序。输出排序前和排序后的学生信息表，验证排序结果。 5 使用直接选择排序方法，对学生信息中的C成绩进行排序。输出排序前和排序后的学生信息表，验证排序结果。 6 使用冒泡排序方法，对学生信息中的数据结构成绩进行排序。输出排序前和排序后的学生信息表，验证排序结果。 7 编写一个主函数，将上面函数连在一起，构成一个完整程序。 8 将实验源程序调试并运行。 三、实验结果 源程序代码为： #include 河南工业大学实验报告 课程名称数据结构实验项目实验三查找和排序(二)——排序院系信息学院计科系专业班级计科1203 姓名张伟龙学号 201216010313 指导老师范艳峰日期 2013.6.5 批改日期成绩 一实验目的 掌握希尔排序、快速排序、堆排序的算法实现。 二实验内容及要求 实验内容：1．实现希尔排序。 2．实现快速排序。 3. 实现堆排序。 （三选一） 实验要求：1. 根据所选题目，用C语言编写程序源代码。 2. 源程序必须编译调试成功，独立完成。 三实验过程及运行结果 选择第三题： Source Code： #include int rchild=2*i+1; //i的右孩子节点序号 int max=i; //临时变量 if(i<=size/2) //如果i是叶节点就不用进行调整 { if(lchild<=size&&a[lchild]>a[max]) { max=lchild; } if(rchild<=size&&a[rchild]>a[max]) { max=rchild; } if(max!=i) { swap(a[i],a[max]); HeapAdjust(a,max,size); //避免调整之后以max为父节点的子树不是堆 } } } void BuildHeap(int *a,int size) //建立堆 { int i; for(i=size/2;i>=1;i--) //非叶节点最大序号值为size/2 { HeapAdjust(a,i,size); } } 数据结构查找排序经典试题 一、填空 1、针对有n条记录的顺序表做顺序查找，假定各记录的查找机会均等，则平均查找长度 ASL=_______。 2、在二叉平衡树中，平衡因子hl-hr的所有可能取值有____________。 3、在排序操作中，待排序的记录有n条，若采用直接插入排序法，则需进行 _________趟的 插入才能完成排序。 4、在排序操作中，待排序的记录有n条，若采用冒泡排序法，则至多需进行_________趟的 排序。 5、直接插入排序算法的时间复杂度为________________。 6、按（）遍历二叉排序树，可以得到按值递增的关键字序列，在下图 所示的二叉排序树中，查找关键字85的过程中，需和85进行比较的关键字序列为（）。 50 95 20 55 70 10 30 85 二、判断 1、平衡二叉树中子树的深度不能大于1。（） 2、快速排序法是稳定的排序方法。（） 3、任何一种排序方法都必须根据关键字值比较的结果来将记录从一个地方移动到另一个地 方。（） 4、冒泡排序法是稳定的排序方法。（） 5、折半插入排序法是稳定的排序方法。（） 三、选择 1、在排序操作中，待排序的记录有n条，若采用直接插入排序法，则需进行_________趟的 插入才能完成排序。 A、n B、(n-1)/2 C、n+1 D、n-1 2、采用顺序查找法查找长度为n的线性表时，平均查找长度为（） A、n B、(n-1)/2 C、n/2 D、(n+1)/2 3、用折半查找法在{11,33,55,77,99,110,155,166,233}中查找155需要进行（）次比较。 A、1 B、2 C、3 D、4 4、请指出在顺序表(2,5,7,10,14,15,18,23,35,41,52)中，用折半查找法查找12需做（）次比较。 A、5 B、4 C、3 D、2 5、如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒， 第二轮排序和查找算法综合1 行政班：教学班：姓名：学号： 根据课本上的排序算法和查找算法回答1-6题： 1．【加试题】有一个数组，采用冒泡排序，第一遍排序后的结果为：4，10，5，32，6，7，9，17，24那么该数组的原始顺序不可能 ．．．的是（） A．10，5，32，6，7，9，17，24，4 B．10，5，32，6，7，9，4，17，24 C．10，5，32，4，6，7，9，17，24 D．4，10，5，32，17，9，24，6，7 2.【加试题】对下列数据序列进行冒泡升序排序，排序效率最低的序列（） A.31，29，24，20，15，10 B.10，15，20，24，29，31 C.29，10，31，15，20，24 D.24，29，31，20，15，10 3．【加试题2】数组变量d（1）到d（8）的值依次为87、76、69、66、56、45、37、23，用“对分查找”找到“69”的过程中，依次被访问到的数据是（） A．69 B．66、69 C．66、76、69 D．56、66、76、69 4.【加试题2】用对分查找法和顺序查找法在数字序列“1,2,3,5,8,13,21,34，55”中查找数字13,两种方法都能访问到的数字是（） A.3 B.5 C.8 D.34 5.【加试题2】在有序单词序列“bike，cake，data，easy，feel，great，hive，mark,sweet”中，用对分查找算法找到“easy”过程中，依次被访问到的数据为（） A.feel, data, easy B.great, data, easy C.bike, cake, dada，easy D.feel,cake,data,easy 6.【加试题2】下列有关查找的说法，正确的是（） A．进行对分查找时，被查找的数据必须已按升序排列 B．进行对分查找时，如果查找的数据不存在，则无需输出结果 C．在新华字典中查找某个汉字，最适合使用顺序查找 D．对规模为n的数据进行顺序查找，平均查找次数是21 n 7. 【加试题】实现某排序算法的部分VB程序如下：数组元素a(1)到a(5)的数据依次为“38，70，53，57，30”。经过下列程序“加工”后数组元素a(1)到a(5)的数据应该是（） For i = 1 To 1 For j = 5 To i + 1 Step -1 If a(j) > a(j - 1) Then t = a(j) a(j) = a(j - 1) a(j - 1) = t End If Next j Next i 命题：杜宗飞 A.70，57，38，53，30 B.30, 38，70，53，57 C.70，38，57，53，30 D.30, 38，57，53，70 8.【加试题】有如下程序段： For i = 1 To 2 计算机科学与技术系实验报告 专业名称计算机科学与技术 课程名称数据结构与算法 项目名称实验八顺序表的排序实验 班级 学号 1 姓名 同组人员 实验日期 实验八顺序表的排序实验 实验题目：为希尔排序设计建表函数和主函数，要求输出每一趟排序的结果， 并通过运行来验证 1.问题分析 本程序要求为希尔排序设计建表函数和主函数，要求输出每一趟排序的结果，并通过运行来验证 完成该实验需要以下4个子任务： ○1定义一个顺序表的存储结构 ○2建立顺序表 ○3定义ShellSort()函数对顺序表L按增量序列di[0]-di[n-1]进行希尔排序○4定义ShellInsert()函数对顺序表L做一趟希尔插入排序 ○5在主函数中调用函数完成操作 测试数据设计如下： 49 52 65 97 35 13 27 50 2.概要设计 为了实现上述程序功能，需要：○1定义一个顺序表的结构○2建立一个顺序表输 入表的长度，再输入表中的元素○3定义ShellSort()ShellInsert()函数实现简单顺序查找算法，在ShellSort()函数调用ShellInsert()函数实现排序。 返回L○4在主函数中调用函数实现操作 本程序包含3个函数： 1.主函数:main() 2.建顺序表：SqLset() 3.希尔排序:ShellSort() 4.ShellInsert()函数 各函数关系如下： Sqlset() Main () ShellSort() ShellInsert() 3、详细设计 实现概要设计中定义的所有的数据类型，对每个操作给出了算法和代码，主程序和模块都需要代码。 （1）顺序表 #define maxlen 50 typedef struct{ //定义顺序表 int r[maxlen]; int last; }Seqlist; Sequenlist *L; (2)建立一个顺序表,输入表的长度，再输入表中的元素 void SqLset(Seqlist *L){ //输入表的长度，再输入表中的元素int i; L->last=-1; printf("请输入表长:"); scanf("%d",&i); if(i>0){ printf("请输入表中元素:\n"); for(L->last=1;L->last<=i;L->last++) scanf("%d",&L->r[L->last]); } } (3）定义ShellSort()函数对顺序表L按增量序列di[0]-di[n-1]进行希尔排序Seqlist *ShellSort(Seqlist *L,int di[],int n){ int i,j; for(i=0;i<=n-1;i++){ ShellInsert(L,di[i]); printf("第%d趟希尔排序，增量为%d，排序之后的结果\n",i+1,di[i]); for(int j=1;j 《编程实训》 实验报告书 专业：计算机科学与技术 班级：151班 学号： 姓名： 指导教师： 日期：2016年6月30日 目录 一、需求分析 (3) 1.任务要求 (3) 2.软件功能分析 (3) 3.数据准备 (3) 二、概要设计 (3) 1.功能模块图 (4) 2.模块间调用关系 (4) 3.主程序模块 (5) 4.抽象数据类型描述 (5) 三、详细设计 (6) 1.存储结构定义 (6) 2.各功能模块的详细设计 (7) 四、实现和调试 (7) 1.主要的算法 (7) 2.主要问题及解决 (8) 3.测试执行及结果 (8) 五、改进 (9) 六、附录 (9) 1.查找源程序 (9) 2.排序源程序 (9) 目录 1 需求分析 1.1 任务要求 对于从键盘随机输入的一个序列的数据，存入计算机内，给出各种查找算法的实现； 以及各种排序算法的实现。 1.2 软件功能分析 任意输入n个正整数，该程序可以实现各类查找及排序的功能并将结果输出。 1.3 数据准备 任意输入了5个正整数如下： 12 23 45 56 78 2 概要设计（如果2，3合并可以省略2.4） 2.1 功能模块图（注：含功能说明） 2.2 模块间调用关系 2.3 主程序模块 2.4 抽象数据类型描述 存储结构：数据结构在计算机中的表示（也称映像）叫做物理结构。又称为存储结构。数据类型（data type）是一个“值”的集合和定义在此集合上的一组操作的总称。 3 详细设计 3.1 存储结构定义 查找： typedef int ElemType ; //顺序存储结构 typedef struct { ElemType *elem; //数据元素存储空间基址，建表时按实际长度分配，号单元留空 int length; //表的长度 在会计上有三大财务报表，分别是：资产负债表、损益表、现金流量表，资产负债表反应企业报表日财务状况，损益表反应企业会计期间的盈利情况，现金流量表反应企业会计期间的经营、投资、筹资现金流情况。三张报表在编制上相对单独存在，而在财务分析时却相互依存、相互影响。在实际的使用中一定要把它们综合起来看，对表间的各种财务数据的关系要辩证的看。如净利润大增而经营性现金流量反而减少，那这个业绩增长的质量就不可靠了，很可能是“突击销售”的结果，又比如负债水平与财务费用不匹配，有可能这些负债是预收账款，该类负债不增加费用反正增加利润，这样的负债多些放在银行吃利息也不见得是坏事。 三张报表以一个三维立体式展现一家公司的财务状况，多角度对同一经济实体的资产质量和经营业绩作报告，从三大报表的时间属性上看，损益表、现金流量表属于期间报表，反应的是某一段时期内企业的经营业绩，资产负债表是期末报表，反应的是报表制作时企业的资产状况。从相互作用上看一个经营期间损益表、现金流量表改变资产负债表结构，但长期而言，资产质量对企业盈利能力起到决定性作用，这又是资产负债表决定损益表、现金流量表。 从某种意义上讲，资产负债表系静态报表，而损益表、现金流量表系动态报表，表现为在一段时期内如何改变资产负债表，有点像资产负债表提供一个平台，损益表、现金流量表在上面长袖善舞。也许从这点上看在分析企业财务状况的时候应该以资产负债表为根本，可我个人并非太看重企业资产结构，更愿意把损益表即利润表作为分析的根本出发点，它更好的反应了在一个期间之内企业的经营成果，高质量的资产就是通过盈利水平体现价值的。当然，同期间前后两份资产负债表也可以大致反应企业的经营状况，但总的来说还是比较迟钝和间接的。现金流量表对不同行业的表现大相径庭，如港口、高速公路、医药等这些行业一般都有较充足的现金流，可对银行、房地产、制造业而言现金流一般都是较为紧张也算常态。 如何看资产负债表？ 资产负债表最主要的是看企业的资产负债情况，即资产的配置和权益负债的组成，资产＝所有者权益+负债，报表从等号双边两个角度分别反应企业资产存在组成明细，一方面是资产的配置情况，另一方面是股东权益与负债的比例和组成明细，在报表中分左右两列记录，如公式般报表左右一定要相等，在会计上这是最主要、最根本的表内勾稽关系，很多其它会计勾稽关系都在此基础上建立起来的。 资产可分为流动资产和非流动资产，故上面等式可变成：流动资产+非流动资产＝所有者权益+负债，又可进一步分解成：流动资产+长期投资+固定资产+无形资产＝所有者权益+流动负债+非流动负债，双边一定是均等关系，这是会计的基本原则。总的方面正常情况下流动 第九章查找 单项选择题 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(nlog2n) C. O(n) D. O (logn) 5.二分查找和二叉排序树的时间性能。 A. 相同 B. 不相同 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%11。表中有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. 散列 填空题 1.顺序查找法的平均查找长度为；二分查找法的平均查找长度为；分块查找法（以顺序查找确定块）的平均查找长度为；分块查找法（以二分查找确定块）的平均查找长度为；哈希表查找法采用链接法处理冲突时的平均查找长度为。 2.在各种查找方法中，平均查找长度与结点个数n无关的查找方法是。 3.二分查找的存储结构仅限于，且是。 4.在分块查找方法中，首先查找，然后再查找相应的。 5.长度为255的表，采用分块查找法，每块的最佳长度是。 6.在散列函数H(key)=key%p中，p应取。 7.假设在有序线性表A[1..20]上进行二分查找，则比较一次查找成功的结点数为，则 山东师范大学 实验报告 课程：数据结构班级：2016级通信2班实验序号： 1 姓名：韩明达 学号: 201611030230 实验日期：9.17 题目: 顺序表的建立和运算 一、实验目的和要求 （1）熟悉C语言的上机环境，进一步掌握C语言的结构特点。 （2）掌握线性表的顺序存储结构的定义及基本运算 二、实验环境 Windows10，Visual Studio 2017 三、实验内容及实施 实验内容 1、建立一个顺序表，输入n个元素并输出； 2、查找线性表中的最大元素并输出； 3、在线性表的第i个元素前插入一个正整数x； 4、删除线性表中的第j个元素； 5、将线性表中的元素按升序排列； 【程序流程图】 【程序】 #include 【一】需求分析 课程题目是排序算法的实现，课程设计一共要设计八种排序算法。这八种算法共包括：堆排序，归并排序，希尔排序，冒泡排序，快速排序，基数排序，折半插入排序，直接插入排序。 为了运行时的方便，将八种排序方法进行编号，其中1为堆排序，2为归并排序，3为希尔排序，4为冒泡排序，5为快速排序，6为基数排序，7为折半插入排序8为直接插入排序。 【二】概要设计 1.堆排序 ⑴算法思想：堆排序只需要一个记录大小的辅助空间，每个待排序的记录仅占有一个存储空间。将序列所存储的元素A[N]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的元素均不大于(或不小于)其左右孩子(若存在)结点的元素。算法的平均时间复杂度为O(N log N)。 ⑵程序实现及核心代码的注释： for(j=2*i+1; j<=m; j=j*2+1) { if(j temp=su[i]; su[i]=su[0]; su[0]=temp; head(0,i-1); } cout<<"排序之后的数组为："<数据结构图,查找,内排序的练习及答案
(完整word版)查找、排序的应用 实验报告
三大财务报表的关系分析3
数据结构第九章排序习题与答案
实验五 查找与排序
查找与排序实验报告
财务报表分析期末考试题-全部排序
《数据结构与算法分析》课程设计：顺序表、单链表、顺序栈、查找、排序算法
作业5查找排序 参考答案
实验6 查找和排序 (2)(1)
河南工业大学实验报告——查找和排序(排序)——张伟龙
数据结构查找排序经典试题
2018年浙江省选考信息技术查找与排序强化习题一答案
实验八 顺序表的排序实验报告
查找排序实验报告
(财务管理)三大财务报表的作用
第9章 查找练习题及答案
顺序表的建立及其基本操作技巧
各种排序实验报告