lab12 线性表查找

实验十二线性表查找

一、实验目的

（1）掌握顺序查找、折半查找、索引查找的算法思想；

（2）掌握折半查找算法的实现方法；

（3）分析折半查找成功和失败的条件；

（4）熟练应用折半查找。

二、实验环境

Windows 2000以上版本的操作系统，Visual C++ 6.0版编程环境。

三、实验内容和步骤（根据ListInArray工程完成下面各题目）

1.下面所示是在序列{0, 10, 20, 30, 40, 50, 60, 70, 80, 90}中用折半的思想查找“15”的

过程，请写出查找“80”的过程。

查找80的过程：

第一次：在【0-90】之间查找，与40比较

第二次：在【50-90】之间查找，与70比较

第三次：在【80-90】之间查找，与80比较

查找成功

2.将在上述序列中查找数据“15”、“25”、“80”的过程分别记录在下面表格中。然后

在intBinarySearch(LIST L, DataType item)函数中设置断点，分别在断点①处观察本次查找区间，在断点②处观察下次查找区间，用“F5”调试程序，根据观察得到的数据分析查找成功和失败的条件分别是什么，并考虑如果要将“15”、“25”、“80”三个数插入到有序表中且保持有序性不变，则插入位置应如何表示。

3.应用：利用折半查找算法在有序表中插入一个元素，并保持表的有序性。在

ListInArray工程中添加新接口intListInsert_Binary(LIST &L, DataType item)实现上述功能。

4.查看IndexSearch工程，验证索引查找的过程。

数据结构线性表2答案

习题二 一、选择题 1．在一个长度为n的顺序表中删除第i个元素（0＜i

01顺序结构的线性表插入删除查找

//* * * * * * * * * * * * * * * * * * * * * * * //PROGRAM NAME :顺序结构的线性表 * //CONTENT :插入,删除,查找 * //* * * * * * * * * * * * * * * * * * * * * * * #include #include #include #define MAX 30 //定义线性表的最大长度 enum BOOL{False,True}; //定义BOOL型 typedef struct{ char elem[MAX]; //线性表 int last; //last指示当前线性表的长度 }sqlisttp; void initial(sqlisttp &); //初始化线性表 BOOL insert(sqlisttp &,int,char); //在线性表中插入元素 BOOL del(sqlisttp&,int,char &); //在线性表中删除元素 int locate(sqlisttp,char); //在线性表中定位元素 void print(sqlisttp); //显示线性表中所有元素 void main() {sqlisttp S; //S为一线性表 int loc,flag=1; char j,ch; BOOL temp; textbackground(3); //设置屏幕颜色 textcolor(15); clrscr(); //---------------------------程序解说-------------------------- printf("本程序用来实现顺序结构的线性表。\n"); printf("可以实现查找、插入、删除等操作。\n"); //------------------------------------------------------------- initial(S); //初始化线性表 while(flag) { printf("请选择:\n"); printf("1.显示所有元素\n"); printf("2.插入一个元素\n"); printf("3.删除一个元素\n"); printf("4.查找一个元素\n"); printf("5.退出程序 \n"); scanf(" %c",&j); switch(j) {case '1':print(S); break; //显示所有元素 case '2':{printf("请输入要插入的元素(一个字符)和插入位置:\n"); printf("格式：字符，位置；例如:a,2\n"); scanf(" %c,%d",&ch,&loc); //输入要插入的元素和插入的位置

线性表实验报告：针对链式或顺序存储的线性表实现指定的操作(二份)

、格式已经给出，请同学们参考书写。其中，第一项可补充，第二、三项不修改，第四项为可选项，第六项为参考程序，第五、七、八项需自己上机调试程序书写。注意：红色字体为提示内容，大家不要往实验报告上抄。 实验一:线性表的顺序存储结构的表示和实验 ——学生成绩管 理系统 一、实验目的：通过上机调试程序，充分理解和掌握有关线性表的定义、实现及操作。 二、实验环境 Win2003/win xp +Visual C++ 三、基本要求：利用顺序表来制作一个学生成绩表 1、建立头文件，包含数据类型定义和基本操作。 2、建立程序文件利用顺序表表完成一个班级的一个学期的所有课程的管理：能够增加、删除、修改学生的成绩记录。 四、简要的需求分析与概要设计（本项为可选项，选作时参考课

五、详细的算法描述： 六、实验步骤（以下为参考程序，已经调试运行通过）#include #include using namespace std; const int LISTINITSIZE=100; const int LISTINCREMENT=10; struct student { char no[20];

char name[20]; int english; int math; }; typedef student elemtype; struct sqlist { elemtype *elem; int length; int listsize; int incrementsize; }; //初始化顺序表l void initlist(sqlist &l,int maxsize=LISTINITSIZE,int incresize=LISTINCREMENT) { l.elem=new elemtype[maxsize]; l.length=0; l.listsize=maxsize; l.incrementsize=incresize;

数据结构 第九章 查找 作业及答案

第九章查找 一、填空题 1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是。 2. 线性有序表（a 1，a 2 ，a 3 ，…，a 256 )是从小到大排列的，对一个给定的值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

掌握线性表的基本操作：插入、删除、查找在顺序存储结构上的实现。

洛阳理工学院实验报告

附：源程序： #include #define ERROR 0 #define OK 1 #define MAXSIZE 100 typedef int ElemType; typedef struct { ElemType elem[MAXSIZE]; int last; }SeqList; void insert(SeqList *L) { int elem;

int i,j,k,t; int flag=1; printf("请输入数据:\n"); while(flag) { scanf("%d",&elem); if (elem==-1) break; if (L->last>MAXSIZE-1) { printf("顺序表已满！\n"); return; } L->last++; L->elem[L->last]=elem; } k=L->last; for(j=0;jelem[i]>L->elem[i+1]) {t=L->elem[i];L->elem[i]=L->elem[i+1];L->elem[i+1]=t;} } int DelList(SeqList *L,int key) { int i; int k; if (L->last<0) { return ERROR;

} for (i=0;i<=L->last;i++) { if (L->elem[i]==key) { for (k=i;klast;k++) L->elem[k]=L->elem[k+1]; L->last--; return OK; } } return ERROR; } void printSeq(SeqList *L) { int i; if (L->last<0) { printf("没有任何元素！\n"); } for (i=0;i<=L->last;i++) { printf("%4d",L->elem[i]); if ((i+1)%8==0) { printf("\n"); } } printf("\n");

数据结构练习题-线性表

第2章线性表 一选择题 1．下述哪一条是顺序存储结构的优点？（） A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示 2．下面关于线性表的叙述中，错误的是哪一个？（） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 3．线性表是具有n个（）的有限序列（n>0）。 A．表元素 B．字符 C．数据元素 D．数据项 E．信息项 4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。 A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表 5. 链表不具有的特点是（） A．插入、删除不需要移动元素 B．可随机访问任一元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比 6. 下面的叙述不正确的是（） A．线性表在链式存储时，查找第i个元素的时间同i的值成正比 B. 线性表在链式存储时，查找第i个元素的时间同i的值无关 C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比 D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关 7. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）(1<=i<=n+1)。 A. O(0) B. O(1) C. O(n) D. O(n2) 8. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（）。 A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) 9．线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（）A．O（i） B．O（1） C．O（n） D．O（i-1） 10．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（）。 A．p->next=s;s->next=p->next; B． s->next=p->next;p->next=s; C．p->next=s;p->next=s->next; D． p->next=s->next;p->next=s; 11．对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）A．head==NULL B．head→next==NULL C．head→next==head D．head!=NULL 二、判断 1. 链表中的头结点仅起到标识的作用。( ) 2. 顺序存储结构的主要缺点是不利于插入或删除操作。( ) 3．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。( ) 4．顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。( ) 5. 对任何数据结构链式存储结构一定优于顺序存储结构。( ) 6．集合与线性表的区别在于是否按关键字排序。( ) 7. 线性表的特点是每个元素都有一个前驱和一个后继。( )

数据结构练习附答案

一、单项选择题 1.逻辑关系是指数据元素间的（） A．类型 B．存储方式 C．结构 D．数据项 2.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构 为( ) A．顺序表 B.用头指针表示的单循环链表 C. 用尾指针表示的单循环链表 D. 单链表 3.设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear 为队尾指针，则执行出队操作后其头指针front值为（） A．front=front+1 B．front= (front+1)%(m-1) C．front=(front-1)%m D．front=(fro nt+1)%m 4.在具有n个单元的顺序存储的循环队列中，假定front和rear分别 为队头指针和队尾指针，则判断队满的条件为( )。 A．rear％n==front B．(front+l)％n==rear C．rear％n-1==front D．(rear+l)％n==front 5.在具有n个单元的顺序存储的循环队列中，假定front和rear分别 为队头指针和队尾指针，则判断队空的条件为( )。 A．rear％n==front B．front+l=rear C．rear==front D．(rear+l)％n=front 6.已知一颗二叉树上有92个叶子结点，则它有____个度为2的结点。 ( ) A. 90 B. 91 C. 92 D. 93 7.在一棵非空二叉树的中序遍历序列中，根结点的右边_____。 A. 只有右子树上的所有结点 B. 只有右子树上的部分结点 C. 只有左子树上的所有结点 D. 只有左子树上的部分结点 8.有n条边的无向图的邻接表存储法中，链表中结点的个数是( )个。 A. n B. 2n C. n/2 D. n*n 9.判断有向图是否存在回路，除了可利用拓扑排序方法外，还可以利 用（）。 A. 求关键路径的方法 B.求最短路径的方法 C. 深度优先遍历算法 D.广度优先遍历算法 10.对线性表进行二分查找时，要求线性表必须( )。

顺序存储结构的线性表

顺序存储结构的线性表 线性表是最常用且比较简单的一种结构，它是由有限个数据元素组成的有序集合，每个数据元素有一个数据项或者含多个数据项。例如26个英文字母表（A，B，……Z）是一个线性表，表中每一个数据元素由单个字母组成数据项。又如表5.0.1也是一个线性表，表中含八个数据元素，每一个数据元素由n个选手在该项目的竞赛成绩组成。 线性表具有如下结构特征： （1）均匀性。即同一线性表的名数据元素的数据类型一致且数据项相同。 （2）有序性。表中数据元素之间的相对位置是线性的，即存在性一的“第一个”和“最后一个”数据元素。除第一个 和最后一个外，其他元素前面均只有一个数据元素（直接前趋）和后面均只有一个数据元素（直接后继）。 按照表中数据元素的存储方式分顺序存储结构和链式存储结构两类线性表。 1、序存储结构 顺序存储结构是指用一组地址连续的存储单元依次线性表的元素，通常用数组实现。数组的物理实现是一块连续的存储空间，它是按首址（表中第1个元素的地址）+位移来访问每一个元素。 设 loc(a[i])-----A数组中元素i的内存地址(c<=i<=d);

loc(b[i,j])----Bo数组中（i,j）元素的内存地址 (c1<=I<=d1,c2<=j<=d2); loc(a[i])=loc(a[c])+(i-c)*la，la-------atype类型的长度； loc(b[i,j]=loc(b[c1,c2])+((d2-c2+1)*(i-c1)+(j-c2))*lb，lb----atype 类型长度； 一维数组按照下标递增的顺序访问表中元素； a[c]->a[c+1]->……->a[d] 二维数按照先行后列的顺序访问表中元素： b[c1,c2]->b[c1,c+1]->……b[c1,d2]->……>b[i-1,d2]->b[i,c2]-> ……->b[d1,d2-1]->b[d1,d2] 在数组中，数据元素的下标间接反映了数据据元素的存储地址。而计算机内存是随机存储取的装置，所以在数组中存取一个数据元素只要通过下标计算它的存储地址就行了，数组中任意一个元素的存取时间都相等。从这个意义上讲，数组的存储存储结构是一个随机存取的结构。 问题是，虽然数组的顺序分配结构比较简单，便于随机访问数组中的任一元素。但如果数组要保持线性表的特征的话（由下标指明元素间的有序性），其增删操作的效率比较低。特别，当数组很大时，插入与删除运算颇为费时。因此，比较小的数组或元素不常变（很少进行插入与删除运算）的数组可用作线性表，而对于大的线性表或元素经常变动的线性表，可以采链式存储结构。 2、链式存储结构

第9章 查找练习题及答案

第九章查找 单项选择题 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]上进行二分查找，则比较一次查找成功的结点数为，则

线性表的顺序储存结构

交通大学《算法与数据结构》课程 实验报告 班级：计算机科学与技术2014级2班 实验项目名称：线性表的顺序储存结构 实验项目性质： 实验所属课程：算法与数据结构 实验室(中心)： B01407 指导教师：鲁云平 实验完成时间：2016 年 3 月21 日

一、实验目的 1、实现线性表的顺序存储结构 2、熟悉C++程序的基本结构，掌握程序中的头文件、实现文件和主文件之 间的相互关系及各自的作用 3、熟悉顺序表的基本操作方式,掌握顺序表相关操作的具体实现 二、实验容及要求 对顺序存储的线性表进行一些基本操作。主要包括： （1）插入：操作方式为在指定元素前插入、在指定元素之后插入、在指定位置完成插入 （2）删除：操作方式可分为删除指定元素、删除指定位置的元素等，尝试实现逻辑删除操作。 （3）显示数据 （4）查找：查询指定的元素（可根据某个数据成员完成查询操作） （5）定位操作：定位指定元素的序号 （6）更新：修改指定元素的数据 （7）数据文件的读写操作等。 其它操作可根据具体需要自行补充。 要求线性表采用类的定义,数据对象的类型自行定义。 三、实验设备及软件 VC6.0 四、设计方案

㈠题目 线性表的顺序存储结构 ㈡设计的主要思路 1、新建SeqList.h头文件，定义SeqList模板类 2、设计类数据成员，包括：T *data（用于存放数组）、int maxSize （最大可容表项的项数）、int last（当前已存表项的最后位置） 3、设计类成员函数，主要包括： int search(T& x)const;//搜索x在表中位置，函数返回表项序号 int Locate(int i)const;//定位第i个表项，函数返回表项序号 bool getData(int i,T& x)const;//去第i个表项的值 void setData(int i,T& x)//用x修改第i个表项的值 bool Insert(int i,T& x);//插入x在第i个表项之后 bool Remove(int i,T& x); //删除第i个表项，通过x返回表项的值 bool IsEmpty();//判表空否，空则返回true；否则返回false bool IsFull();//判表满否，满则返回true；否则返回false void input(); //输入 void output();//输出 void ofile();/存储在文件中 void ifile();//读取文件并显示 ㈢主要功能 1、建立新表 2、对表进行插入（指定元素前、后以及指定位置插入）、删除（指定 元素删除及指定位置删除）、修改等操作 3、显示当前操作表的全部容 4、存储在文件中 5、从文件中读取表 五、主要代码 ㈠SeqList.h中的主要代码： 1、类成员声明部分： protected: T *data; //存放数组 int maxSize; //最大可容纳表项

试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。

数据结构复习笔记 作者: 网络转载发布日期: 无 数据就是指能够被计算机识别、存储和加工处理的信息的载体。 数据元素是数据的基本单位，有时一个数据元素可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。如整数这个集合中，10这个数就可称是一个数据元素.又比如在一个数据库(关系式数据库)中，一个记录可称为一个数据元素，而这个元素中的某一字段就是一个数据项。 数据结构的定义虽然没有标准，但是它包括以下三方面内容：逻辑结构、存储结构、和对数据的操作。这一段比较重要，我用自己的语言来说明一下，大家看看是不是这样。 比如一个表(数据库)，我们就称它为一个数据结构，它由很多记录(数据元素)组成，每个元素又包括很多字段(数据项)组成。那么这张表的逻辑结构是怎么样的呢? 我们分析数据结构都是从结点(其实也就是元素、记录、顶点，虽然在各种情况下所用名字不同，但说的是同一个东东)之间的关系来分析的，对于这个表中的任一个记录(结点)，它只有一个直接前趋，只有一个直接后继(前趋后继就是前相邻后相邻的意思)，整个表只有一个开始结点和一个终端结点，那我们知道了这些关系就能明白这个表的逻辑结构了。 而存储结构则是指用计算机语言如何表示结点之间的这种关系。如上面的表，在计算机语言中描述为连续存放在一片内存单元中，还是随机的存放在内存中再用指针把它们链接在一起，这两种表示法就成为两种不同的存储结构。(注意，在本课程里，我们只在高级语言的层次上讨论存储结构。) 第三个概念就是对数据的运算，比如一张表格，我们需要进行查找，增加，修改，删除记录等工作，而怎么样才能进行这样的操作呢? 这也就是数据的运算，它不仅仅是加减乘除这些算术运算了，在数据结构中，这些运算常常涉及算法问题。 弄清了以上三个问题，就可以弄清数据结构这个概念。 -------------------------------------------------------------------------------- 通常我们就将数据的逻辑结构简称为数据结构，数据的逻辑结构分两大类：线性结构和非线性结构(这两个很容易理解) 数据的存储方法有四种：顺序存储方法、链接存储方法、索引存储方法和散列存储方法。-------------------------------------------------------------------------------- 下一个是难点问题，就是算法的描述和分析，主要是算法复杂度的分析方法及其运用。首先了解一下几个概念。一个是时间复杂度，一个是渐近时间复杂度。前者是某个算法的时间耗费，它是该算法所求解问题规模n的函数，而后者是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。 当我们评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度，因此，在算法分析时，往往对两者不予区分，经常是将渐近时间复杂度T(n)=O(f(n)简称为时间复杂度，其中的f(n)一般是算法中频度最大的语句频度。 此外，算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。但是我们总是考虑在最坏的情况下的时间复杂度。以保证算法的运行时间不会比它更长。 常见的时间复杂度，按数量级递增排列依次为：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、k次方阶O(n^k)、指数阶O(2^n)。 时间复杂度的分析计算请看书本上的例子，然后我们通过做练习加以领会和巩固。 数据结构习题一 --------------------------------------------------------------------------------

数据结构期末考试试题和标准答案及评分标准

《数据结构》试题（A卷） （考试时间： 90分钟） 一、单项选择题（本大题共15小题，每小题2分，共30分） （每题只有一个选项是正确的,将答案填写在括号内，错选、多选不得分） 1.（）是组成数据的基本单位，是一个数据整体中相对独立的单元。 A．数据 B.数据元素 C.数据对象 D.数据结构 2.算法计算量的大小称为算法的（）。 A.效率 B.复杂度 C.数据元素之间的关系 D.数据的存储方法 3.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入或删除运算，则采用以下（）方式最节省时间。 A.链式存储 B. 索引存储 C.顺序存储 D.散列存储 4.下述哪一条是顺序存储结构的优点？（） A.存储密度大 B.插入运算方便 C.删除运算方便 D.可方便地用于各种逻辑结构的存储表示 5.在一个单链表中，若删除p所指结点的后续结点，则执行（）。 A.p->next=p->next->next B.p->next=p->next C.p=p->next;p->next=p->next->next D.p=p->next->next 6.带头结点的单链表head为空的判定条件是（）。 A.head==NULL B.head->next==NULL C.head->next==head D.head!==NULL 7.非空的循环单链表head的尾结点(由p所指向)满足（）。 A.p->head==NULL B.p==NULL C.p->next==head D.p==head 8.下面关于线性表的叙述中，错误的是哪一个？（） A.线性表采用顺序存储，必须占用一片连续的存储单元。 B.线性表采用顺序存储，便于进行插入和删除操作。 C.线性表采用链式存储，不必占用一片连续的存储单元。 D.线性表采用链式存储，便于插入和删除操作。 9.队列操作的原则是（）。 A.后进先出 B.先进先出 C.只能进行插入 D.只能进行删除 10.栈中允许进行插入和删除的一端称为（）。 A.栈首 B.栈尾 C.栈顶 D.栈底 11．假设以数组A[n]存放循环队列的元素，其首尾指针分别为front和rear，则当前队列中的元素个数为（）。 A．（rear-front+n）%n B. rear-front+1 C. (front-rear+n)%n D.(rear-front)%n 12.最大容量为n的循环队列，队尾指针是rear，队首指针是front，则队空的判断条件是（ ）。 A.（rear+1）%n==front B.rear==front C.rear+1==front D.(rear-1)%n==front 13.将一个十进制的数转换成二进制的数，可以使用以下一种称为（）的数据结构。 A. 图 B. 树 C. 广义表 D. 栈 14. 把一棵树转换为二叉树后，这棵二叉树的形态是（）。 A. 有2种 B. 有3种 C. 有4种 D. 唯一的 15.一棵左右子树均不空的二叉树在先序线索化后，其中空链域的个数是（）。

数据结构-线性表输入,输出,插入,删除,查找

创建一个线性表实现输入，输出，插入，删除，定位。 （注意：不论在调用哪个函数前，都要先使L.elem=a，就是使指针elem回到数组a的首地址。） #include #include #include #define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量 #define LISTINCREMENT 10 //线性表存储空间的分配增量 #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int ElemType; //接下来ElemType代表的就是int typedef int Status; //Status也代表int int i,*p,*q; //p，q都是指针类型 ElemType e; typedef struct { ElemType *elem; //定义成指针类型//存储空间基址 int length; //当前长度 int listsize; //当前分配的存储容量(以sizeof(ElemType)为单位) }SqList; //***********************构建空的线性表*************************// Status InitList_Sq(SqList &L) //构建一个空的线性表L { L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!L.elem) exit(OVERFLOW); //存储分配失败 L.length=0; //空表长度为0 L.listsize=LIST_INIT_SIZE; //初始存储容量 return OK; } //**************************线性表输入函数*********************// void input(SqList &L) //输入函数 { scanf("%d",L.elem); //要先输入一个，不然一开始就是0，无法进行循环while(*L.elem) // 加*是因为elem是指针，加之后才代表值{ L.elem++; //输入后指针后移 L.length++; //表长加1 scanf("%d",L.elem); //循环中也要再输入 } } //**************************线性表打印函数********************// void print(SqList &L) //输出函数

数据结构作业五

1. 分别画出在线性表（a,b,c,d,e,f,g）中进行折半查找，以查关键字等于e、f和g的过程。 (1)查e Step 1: a b c d e f g ↑↑↑ low mid high de high=mid – 1; Step 3: a b c d e f g ↑ low/high mid e==e return(mid); (2)查f Step 1: a b c d e f g ↑↑↑ low mid high d ST.elem[0] ) BiSearch( ST, low, mid-1 ); if( ST.elem[mid] < ST.elem[0] ) BiSearch( ST, mid+1, high); } else return (mid); }

线性表详细教案

教案 学科名称：计算机导论 课题：数据结构基础（新课） 教学目标：让学生了解数据结构在信息技术中的重要性，为让学生通过学习数据结构基础，能过更好的学习算法和程序设计。教学内容：向学生阐述数据结构的运用和几种典型的数据结构（线性表、堆栈、队列）及其定义和特征。 教学重点：了解什么是数据结构，数据结构的类型的表现和实现。教学难点：熟悉几种典型数据结构（线性表、堆栈、队列）的运算及其存储方式。 教学策略：讲授法，演示法，和操练法。举一些典型的例子，演示数据结构的存储和区别，主要以幻灯片的方式来演示。 教学过程： 一数据结构含义 (提问：什么是数据结构？) 所谓数据结构是带有结构的数据元素的集合，结构反映了数 据元素相互之间存在的某种联系。（这里所说的“数据”，是 指描述客观事物的数、字符以及所有能输入到计算机并且被 计算机处理的符号的集合。因此，在计算机科学技术中，“数 据”的含义是十分广泛的，它不仅可以是数值，其他如字符、 图形、图像、乃至声音等信息都可以视为数据。数据集合中 每一个个体称为数据元素，它是数据的基本单位。）

（1）不同角度看数据结构 学科角度：数据结构是计算机科学技术的一个分支，它主要 研究数据的逻辑结构（即数据元素之间的逻辑关系）和物理 结构（即数据在计算机中是如何表示的）以及它们之间的关 系。 课程角度：数据结构是计算机科学技术的一门重要的专业基 础课，其中系统介绍线性表、堆栈、队列、串、数组和广义 表、树、图等基本类型的数据结构及其相应的运算的实现算 法。 二、几种典型的数据结构 1、线性表 （1）线性表的定义（提问：看到线性表会联想到什么？｛数 轴｝、坐标） 线性表是一种简单且最常用的数据结构。一个线性表是n 个数据元素的有序列，每一个数据元素根据不同的情况可以 是一个数、一个符号或者一个记录等信息。例如：英文字母 表（A,B,C,D,E,…，Z）就是一个线性表，其中的数据元素 就是单个的字母。 数据元素、数据项 数据元素是数据的基本单位，它也可以再由不可分割的数据项组成。如图示：

数据结构线性表单链表的查找、插入、删除

实验报告 课程名称数据结构 姓名 学号 专业班级 指导教师

目录 第二章线性表的查找、插入、删除 (1) 1.1顺序表的查找 (1) 1.2顺序表的插入 (3) 1.3顺序表的删除 (7) 单链表的建立、插入、删除 (10) 2.1 单链表的建立（尾插法） (10) 2.2 单链表的插入 (13) 2.3 单链表的删除 (17) 第三章栈 (24) 3.1链栈 (24) 3.2 顺序栈 (28) 3.3队列 (30) 3.4辉三角 (35) 第四章串 (23) 4.1字符串的建立 (23) 4.2顺序串的插入 (25)

1.线性表的查找、插入、删除 1.1顺序表的查找 程序： #include #include #include #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define ElemType int #define MAXSIZE 100 /*此处的宏定义常量表示线性表可能达到的最大长度*/ typedef struct { ElemType elem[MAXSIZE]; /*线性表占用的数组空间*/ int last; /*记录线性表中最后一个元素在数组elem[]中的位置（下标值），空表为-1*/ }Seqlist; int Locate(Seqlist L,ElemType e)

/*在顺序表L中查找与e相等的元素，若L。elem[i]=e,则找到该元素，并返回i+1，若找不到，则返回-1*/ { int i=0; /*i为扫描计数器，初值为0，即从第一个元素开始比较*/ while ((i<=https://www.wendangku.net/doc/d38611675.html,st)&&(L.elem[i]!=e)) /*顺序扫描表，直到找到值为e的元素，或扫描到表尾仍没找到*/ i++; if(i<=https://www.wendangku.net/doc/d38611675.html,st) return (i+1); /*若找到值为e的元素，则返回其序号*/ else return(-1); /*若没找到，则返回空序号*/ } void main() { Seqlist l; int p,q,r; int i; printf("请输入线性标的长度:"); scanf("%d",&r); https://www.wendangku.net/doc/d38611675.html,st=r-1; printf("请输入线性表的各元素值：\n"); for (i=0;i<=https://www.wendangku.net/doc/d38611675.html,st;i++) {

第10章 查找

一、选择题 ( )7、下面关于二分查找的叙述正确的是。 A）表必须有序，表可以顺序方式存储，也可以链表方式存储； C）表必须有序，而且只能从小到大排列； B）表必须有序且表中数据必须是整型，实型或字符型； D）表必须有序，且表只能以顺序方式存储； ( ) 14．长度为12的有序表采用顺序存储结构，使用二分查找技术，在等概率情况下，查找成功时的平均查找长度是。 A. 37/12 B. 62/13 C. 39/12 D. 49/13 ( ) 14、折半查找法要求查找表中各元素的关键字必须是排列。 A）递增或递减 B）递增 C）递减 D）无序 ( ) 13、一棵7阶B-树的根结点及非根分支结点所包含的关键字的个数至少分别为A）1，3 B）2，4 C）3，5 D） 6，6 2、设有100个元素，用折半查找法进行查找时，在查找成功的情况下，最大比较次数是_____ 。 A.100 B.50 C.99 D.7 4、指出在顺序表{2、 5、7、10、14、15、18、23、35、41、52}中，用二分法查找12，需做多少次比较。 ______ A、2 B、3 C、4 D、5 6、从二叉排序树中查找一个元素时，其时间复杂度大致为________。 A、 O(n) B、 O(1) C、 O(log2n) D、 O(n2) 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(log2n)（C）O(n)（D）O(log2n) 5.二分查找和二叉排序树的时间性能（）。 （A）相同? （B）不相同? （C）无法比较 6.有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当二分查找值为82的结点时,（）次比较后查找成功。 （A）1（B）2（C）4（D）8 8.有一个长度为12的有序表,按二分查找法对该表进行查找,在表内各元素等概率情况下查找