2013数据结构作业5-查找排序-参考答案

数据结构与算法上机作业第五章查找一、选择题1、若构造一棵具有n个结点的二叉排序树，在最坏情况下，其高度不超过 B 。

A. n/2B. nC. (n+1)/2D. n+12、分别以下列序列构造二叉排序数（二叉查找树），与用其他3个序列所构造的结果不同的是 C ：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)3、不可能生成下图所示的二叉排序树的关键字的序列是 A 。

A. 4 5 3 1 2B. 4 2 5 3 1C. 4 5 2 1 3D. 4 2 3 1 54、在二叉平衡树中插入一个结点造成了不平衡，设最低的不平衡点为A，并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1，则应作 C 型调整使其平衡。

A. LLB. LRC. RLD. RR5、一棵高度为k的二叉平衡树，其每个非叶结点的平衡因子均为0，则该树共有 C 个结点。

A. 2k-1-1B. 2k-1+1C. 2k-1D. 2k+16、具有5层结点的平衡二叉树至少有 A 个结点。

A. 12B. 11C. 10D. 97、下面关于B-和B+树的叙述中，不正确的是 C 。

A. B-树和B+树都是平衡的多叉树B. B-树和B+树都可用于文件的索引结构C. B-树和B+树都能有效地支持顺序检索D. B-树和B+树都能有效地支持随机检索8、下列关于m阶B-树的说法错误的是 D 。

A. 根结点至多有m棵子树B. 所有叶子结点都在同一层次C. 非叶结点至少有m/2（m为偶数）或m/2+1(m为奇数)棵子树D. 根结点中的数据是有序的9、下面关于哈希查找的说法正确的是 C 。

A. 哈希函数构造得越复杂越好，因为这样随机性好，冲突小B. 除留余数法是所有哈希函数中最好的C. 不存在特别好与坏的哈希函数，要视情况而定D. 若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单地将该元素删去即可10、与其他查找方法相比，散列查找法的特点是 C 。

数据结构试卷（五）一、选择题(30分)1．数据的最小单位是（）。

(A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量2．设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4的一趟希尔排序结束后前4条记录关键字为（）。

(A) 40，50，20，95 (B) 15，40，60，20(C) 15，20，40，45 (D) 45，40，15，203．设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（）。

(A) 15，25，35，50，20，40，80，85，36，70(B) 15，25，35，50，80，20，85，40，70，36(C) 15，25，35，50，80，85，20，36，40，70(D) 15，25，35，50，80，20，36，40，70，854．函数substr(“DATASTRUCTURE”，5，9)的返回值为（）。

(A) “STRUCTURE”(B) “DATA”(C) “ASTRUCTUR”(D) “DATASTRUCTURE”5．设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（）。

(A) O(log2n) (B) O(1) (C) O(n2) (D) O(n)6．设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为N l，……，度数为m的结点数为Nm，则N0=（）。

(A) N l+N2+……+Nm (B) l+N2+2N3+3N4+……+(m-1)Nm(C) N2+2N3+3N4+……+(m-1)Nm (D) 2N l+3N2+……+(m+1)Nm7．设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（）次。

(A) 25 (B) 10 (C) 7 (D) 18．设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为（）。

单选题1.从原理上讲，折半查找法要求查找表中各元素的键值必须是____∙ A 递增或递减∙ B 递增∙ C 递减∙ D 无序单选题2.关于判定树，下列说法不正确的是____∙ A 判定树是对有序序列进行二分查找得到的树∙ B n个结点的判定树的深度为[log2n]+1∙ C 判定树的叶子结点都在同一层∙ D 判定树除去最后一层结点以后是满二叉树或空二叉树单选题3.在顺序表{2、5、7、10、14、15、18、23、35、41、52}中，用二分法查找关键码12需做____次关键码比较∙ A 2∙ B 3∙ C 4∙ D 5单选题4.对线性表进行二分查找时，要求线性表必须____ ∙ A 以顺序方式存储∙ B 以顺序方式存储且元素有序∙ C 以链式方式存储∙ D 以链式方式存储且元素有序单选题5.折半查找算法的时间复杂度是____∙ A O(n2)∙ B O(n)∙ C O(log2n)∙ D O(nlog2n)单选题6.若用二分查找法取得的中间位置元素键值大于被查找值，说明被查找值位于中间值的前面，下次的查找区间为从原开始位置至____∙ A 该中间位置∙ B 该中间位置－1∙ C 该中间位置＋1∙ D 该中间位置／2单选题7.对包含N个元素的散列表进行查找，平均查找长度____∙ A 为O(log2N)∙ B 为O(N)∙ C 不直接依赖于N∙ D 上述三者都不是单选题8.若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不会超过____∙ A n/2∙ B n∙ C (n+1)/2∙ D n+1单选题9.分别以下列序列构造二叉排序树，则与其它几个序列构造的结果不同的是____∙ A （80，70，60，75，90，85，100，10）∙ B （80，90，85，70，60，10，75，100）∙ C （80，90，70，85，10，60，75，100）∙ D （80，90，100，70，85，60，10，75）单选题10.如果某二叉树的左右子树的高度差的绝对值不大于1，则一定是平衡二叉树∙ A 正确∙ B 不正确单选题11.AVL树的任何子树都是AVL树。

数据结构实验报告五,查找与排序-查找与排序一、实验目的：1．理解掌握查找与排序在计算机中的各种实现方法。

2．学会针对所给问题选用最适合的算法。

3．熟练掌握常用排序算法在顺序表上的实现。

二、实验要求：掌握利用常用的查找排序算法的思想来解决一般问题的方法和技巧，进行算法分析并写出实习报告。

三、实验内容及分析：设计一个学生信息管理系统，学生对象至少要包含：学号、性别、成绩1、成绩总成绩等信息。

要求实现以下功能：1．平均成绩要求自动计算；2．查找：分别给定学生学号、性别，能够查找到学生的基本信息（要求至少用两种查找算法实现）；3．? 排序：分别按学生的学号、成绩1、成绩2、平均成绩进行排序（要求至少用两种排序算法实现）。

四、程序的调试及运行结果五、程序代码#includestdio.h#includestring.hstruct student//定义结构体{char name;int a1,a2,a3,num;double pow;}zl;int count=0;void jiemian1(); //主界面//函数声明int jiemian2(); //选择界面void luru(); //录入函数void xianshi(); //显示void paixv(); //排序void diaoyong(int); //循环调用选择界面void tianjia(); //添加信息void chaxun1(); //按学号查询详细信息void chaxun2(); //按姓名查询详细信息void xiugai(); //修改信息void shanchu(); //删除信息void main() //main函数{jiemian1();//函数点用}void jiemian1() //主界面定义{char a;printf(“\n\n\n\n\t\t\t学员信息管理器\n\n\n\t\t\t 数据结构课程设计练习六\n\n\n\t\t\t 09信计2:于学彬\n\n“);printf("\n\t\t\t 按回车键继续:");scanf("%c",system("cls");jiemian2();}int jiemian2() //选择界面{int a,b;printf("*******************************主要功能********************************");printf("\n\n\n\n\t\t\t\t1.录入信息\n\n\t\t\t\t2.添加信息\n\n\t\t\t\t3.查看信息\n\n\t\t\t\t4.查询信息\n\n\t\t\t\t5.修改信息\n\n\t\t\t\t6.删除信息\n\n\t\t\t\t7.退出\n\n\t\t\t\t请选择:");scanf("%d",switch(a){case 1:system("cls");luru();break;case 2:system("cls");tianjia();break;case 3:system("cls");paixv();break;case 4:system("cls");printf("1.按学号查询详细信息\n2.按姓名查询详细信息\n请选择:");scanf("%d",switch(b){case 1:system("cls");chaxun1();break;case 2:system("cls");chaxun2();break;} break;case 5:system("cls");xiugai();break;case 6:system("cls");shanchu();break;case 7:system("cls");return a;break;}}void diaoyong(int b) //循环调用选择界面{char a='y';printf("是否返回选择页(y/n):");fflush(stdin);//清空输入缓冲区，通常是为了确保不影响后面的数据读取（例如在读完一个字符串后紧接着又要读取一个字符，此时应该先执行fflush(stdin);)a=getchar();system("cls");while(a=='y'||a=='Y'){b=jiemian2();if(b==7){break;}}}void luru() //录入函数{char a;//='y';do{printf("请输入学员信息:\n");printf("学号:");scanf("%d",zl[count].num);//调用结构体printf("姓名:");fflush(stdin);gets(zl[count].name);printf("三门成绩:\n");printf("成绩1:");scanf("%d",zl[count].a1);printf("成绩2:");scanf("%d",zl[count].a2);printf("成绩3:");scanf("%d",zl[count].a3);zl[count].pow=(zl[count].a1+zl[count].a2+zl[count].a3)/3;//求平均数printf("是否继续(y/n):");fflush(stdin);a=getchar();count++;system("cls");}while(a=='y'count100);//paixv();diaoyong(count);}void tianjia() //添加信息{char a='y';do{printf("请输入学员信息:\n");printf("学号:");scanf("%d",zl[count].num);printf("姓名:");//fflush(stdin);gets(zl[count].name);printf("三门成绩:\n");printf("成绩1:");scanf("%d",zl[count].a1);printf("成绩2:");scanf("%d",zl[count].a2);printf("成绩3:");scanf("%d",zl[count].a3);zl[count].pow=(zl[count].a1+zl[count].a2+zl[count].a3)/3; printf("是否继续(y/n):");//fflush(stdin);a=getchar();count++;system("cls");}while(a=='y'count100);paixv(count);diaoyong(count);}void xianshi() //显示{int i;printf("学号\t \t姓名\t\t\t平均成绩\n");for(i=0;icount;i++){printf("%d\t \t%s\t\t\t%f\n",zl[i].num,zl[i].name,zl[i].pow); }}void paixv() //排序{int i,j;struct student zl1;printf("排序前:\n");xianshi();for(i=0;icount;i++){for(j=1;jcount-i;j++){if(zl[j-1].powzl[j].pow){zl1=zl[j-1];zl[j-1]=zl[j];zl[j]=zl1;}}}printf("排序后:\n");xianshi();diaoyong(count);}void chaxun1() //按学号查询详细信息{int i,num;printf("请输入要查询学员的学号:");scanf("%d",num);printf("学号\t姓名\t成绩1\t成绩2\t成绩3\t平均成绩\n"); for(i=0;icount;i++){if(zl[i].num==num){printf("%d\t%s\t%d\t%d\t%d\t%.2f\n",zl[i].num,zl[i].name,zl[i].a1,zl[i].a2,zl [i].a3,zl[i].pow);}}diaoyong(count);}void chaxun2() //按姓名查询详细信息{int i;struct student zl1;printf("请输入要查询学员的姓名:");fflush(stdin);gets();printf("学号\t姓名\t成绩1\t成绩2\t成绩3\t平均成绩\n");for(i=0;icount;i++){if((strcmp(zl[i].name,))==0)//比较两个字符串的大小{printf("%d\t%s\t%d\t%d\t%d\t%.2f\n",zl[i].num,zl[i].name,zl[i].a1,zl[i].a2,zl [i].a3,zl[i].pow);}}diaoyong(count);}void xiugai() //修改信息{int i,num;printf("请输入要查询学员的学号:");scanf("%d",num);printf("学号\t姓名\t成绩1\t成绩2\t成绩3\t平均成绩\n");for(i=0;icount;i++){if(zl[i].num==num){break;}}printf("%d\t%s\t%d\t%d\t%d\t%.2f\n",zl[i].num,zl[i].name,zl[i].a1,zl[i].a2,zl [i].a3,zl[i].pow);printf("请输入学员信息:\n");printf("学号:");scanf("%d",zl[i].num);printf("姓名:");fflush(stdin);gets(zl[i].name);printf("三门成绩:\n");printf("成绩1:");scanf("%d",zl[i].a1);printf("成绩2:");scanf("%d",zl[i].a2);printf("成绩3:");scanf("%d",zl[i].a3);zl[i].pow=(zl[i].a1+zl[i].a2+zl[i].a3)/3;printf("学号\t姓名\t成绩1\t成绩2\t成绩3\t平均成绩\n"); printf("%d\t%s\t%d\t%d\t%d\t%.2f\n",zl[i].num,zl[i].name,zl[i].a1,zl[i].a2,zl[i].a3,zl[i].pow);diaoyong(count);}void shanchu() //删除信息{int num,i,j;printf("请输入要删除的学员学号:");scanf("%d",num);for(i=0;icount;i++){if(zl[i].num==num){for(j=i;jcount;j++){zl[j]=zl[j+1];}}}count--;xianshi();diaoyong(count);}。

北京物资学院信息学院实验报告
课程名_数据结构与算法
实验名称查找与排序
实验日期年月日实验报告日期年月日姓名______ ___ 班级_____ ________ 学号___
一、实验目的
1.掌握线性表查找的方法；
2.了解树表查找思想；
3.掌握散列表查找的方法.
4.掌握插入排序、交换排序和选择排序的思想和方法；
二、实验内容
查找部分
1.实现顺序查找的两个算法（P307）, 可以完成对顺序表的查找操作, 并根据查到和未查到两种情况输出结果；
2.实现对有序表的二分查找；
3.实现散列查找算法(链接法)，应能够解决冲突；
排序部分
4.分别实现直接插入排序、直接选择排序、冒泡排序和快速排序算法
三、实验地点与环境
3.1 实验地点
3.2实验环境
(操作系统、C语言环境)
四、实验步骤
（描述实验步骤及中间的结果或现象。

在实验中做了什么事情, 怎么做的, 发生的现象和中间结果, 给出关键函数和主函数中的关键段落）
五、实验结果
六、总结
（说明实验过程中遇到的问题及解决办法；个人的收获；未解决的问题等）。

东北农业大学网络教育学院数据结构作业题(一)、选择题(每题2分，共20 分)1在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为( )。

2A Qn) B、O(n/2) C、O(1) D O(n )2.带头结点的单链表first为空的判定条件是( )。

A、first == NULL ;B、first->link == NULL ;C、first->link == first ;D、first != NULL ;3•在一棵树中，( )没有前驱结点。

A、分支结点B、叶结点C、树根结点D、空结点4•在有向图中每个顶点的度等于该顶点的( )。

A、入度B、出度C、入度与出度之和D、入度与出度之差5.对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为( ) 的值除以9。

A、20B、18C、25D、226•下列程序段的时间复杂度为( )。

s=0;for(i=1 ; i<n; i++)for(j=1 ; j<n ; j++)s+=i*j ;2A、O(1)B、O(n)C、O(2n)D、O(n)7•栈是一种操作受限的线性结构，其操作的主要特征是( )。

A、先进先出B、后进先出C、进优于出D、出优于进&假设以数组A[n]存放循环队列的元素，其头、尾指针分别为front和rear。

若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为( )。

4•在二叉树的第i 层上至多有 ______________ 结点。

5.对于一棵具有 n 个结点的二叉树，若一个结点的编号为A、 C、 (rear-front-1) % n B 、(rear-front) % n (front-rear+1) % nD 、(rear-front+n) % n高度为5的完全二叉树中含有的结点数至少为(16B 、17C 、3110.如图所示有向图的一个拓扑序列是D 、32)A 、 ABCDEFB 、 FCBEADC 、 FEDCBAD 、 DAEBCF二、填空题(每空1分，共20 分)1. n (n > 0)个顶点的无向图最多有2.在一棵AVL 树中，每个结点的左子树高度与右子树高度之差的绝对值不超过 ________ 。

数据结构第4-5章作业及答案⼀、填空题1. 不包含任何字符（长度为0）的串称为空串；由⼀个或多个空格（仅由空格符）组成的串称为空⽩串。

2. 设S=“A;/document/Mary.doc”，则strlen(s)= 20 , “/”的位置为3。

3. ⼦串的定位运算称为串的模式匹配；被匹配的主串称为⽬标串，⼦串称为模式。

4、若n为主串长，m为⼦串长，则串的古典（朴素）匹配算法最坏的情况下需要⽐较字符的总次数为(n-m+1)*m。

5、假设有⼆维数组A6×8，每个元素⽤相邻的6个字节存储，存储器按字节编址。

已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为288 B ；末尾元素A57的第⼀个字节地址为1282 ；若按⾏存储时，元素A14的第⼀个字节地址为(8+4)×6+1000=1072 ；若按列存储时，元素A47的第⼀个字节地址为(6×7＋4)×6＋1000）＝1276 。

(注：数组是从0⾏0列还是从1⾏1列计算起呢？由末单元为A57可知，是从0⾏0列开始！)6、设数组a[1…60, 1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为8950 。

答：不考虑0⾏0列，利⽤列优先公式：LOC(a ij)=LOC(a c1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L 得：LOC(a32,58)=2048+[(58-1)* (60-1+1)+32-1]]*2＝89507、三元素组表中的每个结点对应于稀疏矩阵的⼀个⾮零元素，它包含有三个数据项，分别表⽰该元素的⾏下标、列下标和元素值。

8、⼆维数组A[10][20]采⽤列序为主⽅式存储，每个元素占10个存储单元，且A[0][0]的存储地址是2000，则A[6][12]的地址是32609、已知⼆维数组A[20][10]采⽤⾏序为主⽅式存储,每个元素占2个存储单元,并且A[10][5]的存储地址是1000,则A[18][9]的存储地址是 116810、⼴义表((a,b),c,d)的表头是(a,b) ,表尾是 (c,d)11、⼴义表((((a),b),c),d)的表头是(((a),b),c) ，表尾是(d)12、已知⼆维数组A[10][20]采⽤⾏序为主⽅式存储，每个元素占2个存储单元,并且A[0][0]的存储地址是1024, 则A[6][18]的地址是130013、若串的长度不能确定，可采⽤动态存储结构，为串值分配⼀个存储空间，同时建⽴⼀个串的描述⼦以指⽰串值的长度和串在存储空间中的位置，称该结构为堆/堆结构14、稀疏矩阵⼀般的压缩存储⽅法有两种，即三元组表和⼗字链表。

数据结构作业题及答案第一章绪论1、简述下列概念：数据、数据元素、数据结构、逻辑结构、存储结构、线性结构、非线性结构。

数据：指能够被计算机识别、存储和加工处理的信息载体。

数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。

数据元素有时可以由若干数据项组成。

数据结构：指的是数据之间的相互关系，即数据的组织形式。

一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。

逻辑结构：指各数据元素之间的逻辑关系。

存储结构：就是数据的逻辑结构用计算机语言的实现。

线性结构：数据逻辑结构中的一类，它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。

线性表就是一个典型的线性结构。

非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。

2、常用的存储表示方法有哪几种?顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。

由此得到的存储表示称为顺序存储结构。

链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。

由此得到的存储表示称为链式存储结构。

索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。

散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。

3、求解下列算法的时间复杂度(1)i=1;k=0 while(i<n){k=k+10*i;i++;}T(n)=n-1∴T(n)=O(n)这个函数是按线性阶递增的(2)i=0;k=0;do{k=k+10*i;i++;} while(i<n);T(n)=n∴T(n)=O(n)这也是线性阶递增的(3)i=1;j=0;while(i+j<=n) {if(i<j)j++; else i++;}T(n)=n/2∴T(n)=O(n)虽然时间函数是n/2,但其数量级仍是按线性阶递增的。

作业1. 线性表编程作业：1．将顺序表逆置，要求用最少的附加空间。

参考答案#include <>#include <>#include <>#define LIST_INIT_SIZE 100#define LISTINCREMENT 10#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef int ElemType;typedef struct{ ElemType *elem;int length;int listsize;}SqList;立单链表 ");printf("2.取元素值 ");printf("3.查找 \n");printf("4.插入 ");printf("5.删除 ");printf("6.显示\n");printf("7.删除大于mink且小于maxk的元素值 ");printf("8.就地升序排序\n");printf("9.就地逆置 ");printf("a.有序表插入 ");printf("q.退出\n");printf("\n请选择操作：");fflush(stdin);scanf("%c",&choice);switch(choice){case '1': printf("请输入单链表中结点个数：");scanf("%d",&n);Create_L2(L,n);break;case '2': printf("请输入元素位序：");scanf("%d",&i);GetElem_L(L,i,e);printf("元素值为：%d\n",e);break;case '3': printf("请输入要查找的元素：");scanf("%d",&e);if(dlbcz(L,e))printf("查找成功！");elseprintf("查找失败。