经典数据结构上机题_答案解析

数据结构上机实验题目

实验一线性表的顺序存储结构

实验学时 2学时

背景知识:顺序表的插入、删除及应用。

目的要求：

1．掌握顺序存储结构的特点。

2．掌握顺序存储结构的常见算法。

实验容

1．输入一组整型元素序列，建立顺序表。

2．实现该顺序表的遍历。

3．在该顺序表中进行顺序查找某一元素,查找成功返回1,否则返回0。4．判断该顺序表中元素是否对称,对称返回1,否则返回0。

5．实现把该表中所有奇数排在偶数之前,即表的前面为奇数,后面为偶数。

6．输入整型元素序列利用有序表插入算法建立一个有序表。

7．利用算法6建立两个非递减有序表并把它们合并成一个非递减有序表。

8. 利用该顺序结构实现循环队列的入队、出队操作。

8．编写一个主函数,调试上述算法。

#include

#include

#define OVERFLOW 0

#define MAXSIZE 100

typedef int ElemType;

typedef struct list

{ElemType elem[MAXSIZE];

int length;

}Sqlist;

void Creatlist(Sqlist &L)

{int i;

printf("请输入顺序表的长度："); //输入一组整型元素序列，建立一个顺序表。

scanf("%d",&L.length);

for(i=0;i

scanf("%d",&L.elem[i]);

}

void printlist(Sqlist &L) //以输出的形式实现对该顺序表的遍历{int i;

for(i=0;i

printf("%d ",L.elem[i]);

printf("\n");

}

void Searchlist(Sqlist &L,int x) //在顺序表中进行顺序查找某一元

素x，查找成功则返回其存储位置i，否则返回错误信息

{int i,k=-1;

for(i=0;i

if(L.elem[i]==x){

k=i+1;printf("%d ",k);}

if(k==-1)

printf("error!");

printf("\n");

}

void Inseri(Sqlist &L,int i,int x) //在顺序表的第i个位置上插入一个元素x

{int j;

for(j=L.length;j>=i;j--)

L.elem[j]=L.elem[j-1];

L.elem[j]=x;

L.length++;

}

void Delete(Sqlist &L,int i) //删除顺序表中第i个元素

{int j;

for(j=i;j

L.elem[j-1]=L.elem[j];

L.length--;

void Insert(Sqlist &L,int x) //输入一个元素x，把它插入到有序表中，使顺序表依然有序。

{int i,j;

if(L.length==MAXSIZE) exit(OVERFLOW); //表满，不能插入

for(i=1;i<=L.length&&L.elem[i-1]<=x;i++);

for(j=L.length;j>=i;j--)

L.elem[j]=L.elem[j-1];

L.elem[i-1]=x;

L.length++;

}

void Creatlist_sorted(Sqlist &L) //利用有序表插入算法建立一个有序表

{int i,num;

ElemType x;

L.length=0;

printf("请输入顺序表的长度：");

scanf("%d",&num);

for(i=1;i<=num;i++)

{

scanf("%d",&x);

Insert(L,x);

}

void Merger(Sqlist &p,Sqlist &r,Sqlist &c) //建立两个非递减有序表，并把它们合并成一个非递减有序表

{

ElemType *a,*b,i=0,j=0,k=0;

a=&p.elem[0];

b=&r.elem[0];

c.length=p.length+r.length;

while(i

{if(*a>=*b)

{c.elem[k]=*b;b++;k++;j++;}

else {c.elem[k]=*a;a++;k++;i++;}

}

if(j==r.length)

for(;k

{c.elem[k]=*a;a++; }

else if(i==p.length)

for(;k

{c.elem[k]=*b;b++;}

}

void main()

{Sqlist L,M,N;

int x,i,n;

printf("1.建立一个顺序表.\n");

printf("2.以输出的形式对该顺序表遍历.\n");

printf("3.在顺序表中进行顺序查找某一元素x.\n");

printf("4.在顺序表的第i个位置上插入一个元素x.\n");

printf("5.删除顺序表中第i个元素.\n");

printf("6.利用有序表插入算法建立一个有序表.\n");

printf("7.建立两个非递减有序表，并把它们合并成一个非递减有序表.\n"); printf("8.输入一个元素x，把它插入到有序表中，使顺序表依然有序.\n"); while(1){

printf("请选择：");

scanf("%d",&n);

switch(n)

{case 1:Creatlist(L);break;

case 2:printlist(L);break;

case 3:printf("请输入要查找的元素x:");

scanf("%d",&x);

Searchlist(L,x);break;

case 4:printf("请输入要插入的位置i:");

scanf("%d",&i);

if(i<1||i>L.length+1){

printf("error!\n");break;}

printf("请输入要插入的值x:");

scanf("%d",&x);

Inseri(L,i,x);

printlist(L);break;

case 5:printf("请输入要删去的元素的位置i:");

scanf("%d",&i);

if(i<1||i>L.length){

printf("error!\n");break;}

Delete(L,i);

printlist(L);break;

case 6:Creatlist_sorted(L);

printlist(L);break;

case 7:Creatlist_sorted(L);

Creatlist_sorted(M);

Merger(L,M,N);

printlist(N);break;

case 8:Creatlist_sorted(L);

printf("请输入要插入的元素x:");

scanf("%d",&x);

Insert(L,x);

printlist(L);break;

}

}

}

实验二链式存储结构（一）----单向链表的有关操作

实验学时 3学时

背景知识：单向链表的插入、删除及应用。

目的要求

1．掌握单向链表的存储特点及其实现。

2．掌握单向链表的插入、删除算法及其应用算法的程序实现。

实验容

1．随机产生或键盘输入一组元素，建立一个带头结点的单向链表（无序）。

2．遍历单向链表。

3．把单向链表中元素逆置（不允许申请新的结点空间）。

4．在单向链表中删除所有的偶数元素结点。

5．编写在非递减有序链表中插入一个元素使链表元素仍有序的函数，并利用该函数建立一个非递减有序单向链表。

6．利用算法5建立两个非递减有序单向链表，然后合并成一个非递增

数据结构上机实验报告

数据结构上机实验报告 学院：电子工程学院 专业：信息对抗技术 姓名：

学号： 教师：饶鲜日期：

目录 实验一线性表................................................. - 4 - 一、实验目的................................................ - 4 - 二、实验代码................................................ - 4 - 三、实验结果............................................... - 14 - 四、个人思路............................................... - 15 -实验二栈和队列.............................................. - 15 - 一、实验目的............................................... - 15 - 二、实验代码............................................... - 16 - 三、实验结果............................................... - 24 - 四、个人思路............................................... - 25 -实验三数组.................................................. - 26 - 一、实验目的............................................... - 26 - 二、实验代码............................................... - 26 - 三、实验结果............................................... - 28 - 四、个人思路............................................... - 28 -实验四树.................................................... - 29 - 一、实验目的............................................... - 29 - 二、实验代码............................................... - 29 -

数据结构课程设计题目及要求

实验一~实验四任选一题；实验五~实验九任选一题。 实验一运动会分数统计 一、实验目的： （1）熟练掌握线性表的两种存储方式 （2）掌握链表的操作和应用。 （3）掌握指针、结构体的应用 （4）按照不同的学校，不同项目和不同的名次要求，产生各学校的成绩单、团体总分报表。 二、实验内容： 【问题描述】 参加运动会的n个学校编号为1~n。比赛分成m个男子项目和w个女子项目，项目编号分别为1~m和m＋1~m＋w。由于各项目参加人数差别较大，有些项目取前五名，得分顺序为7，5，3，2，1；还有些项目只取前三名，得分顺序为5，3，2。写一个统计程序产生各种成绩单和得分报表。 【基本要求】 产生各学校的成绩单，内容包括各校所取得的每项成绩的项目号、名次（成绩）、姓名和得分；产生团体总分报表，内容包括校号、男子团体总分、女子团体总分和团体总分。 【测试数据】 对于n＝4，m＝3，w＝2，编号为奇数的项目取前五名，编号为偶数的项目取前三名，设计一组实例数据。 【实现提示】 可以假设m≤20，m≤30，w≤20，姓名长度不超过20个字符。每个项目结束时，将其编号、类型符（区分取前五名还是前三名）输入，并按名次顺序输入运动员姓名、校名（和成绩）。 【选作内容】 允许用户指定某些项目可采取其他名次取法。

实验二停车场管理 一、实验目的： （1）熟练掌握栈顺存和链存两种存储方式。 （2）掌握栈的基本操作及应用。 （3）以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。 二、实验内容： 【问题描述】 设停车场是一个可停放n辆汽车的长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车信放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场院，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。 【基本要求】 以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。 【测试数据】 设n=2，输入数据为：(A，1，5)，（A，1，15），（A，3，20），（A，4，25），（A，5，30），（D，2，35），（D，4，40），（E，0，0）。其中：A表示到达（Arrival）；D表示离去（Departure）；E表示输入结束（End）。 【实现提示】 需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。 【选作内容】 （1）两个栈共享空间，思考应开辟数组的空间是多少？ （2）汽车可有不同种类，则他们的占地面积不同收费标准也不同，如1辆客车和1.5辆小汽车的占地面积相同，1辆十轮卡车占地面积相当于3辆小汽车的占地面积。（3）汽车可以直接从便道开走，此时排在它前面的汽车要先开走让路，然后再依次排到队尾。 （4）停放在便道上的汽车也收费，收费标准比停放在停车场的车低，请思考如何修改结构以满足这种要求。

数据结构上机实验

《数据结构》上机题（C语言程序） 北京科技大学数据结构上机实验 ivince 上机题1．输入数据（设为整型）建立单链表，并求相邻两节点data值之和为最大的第一节点。 例如输入：2 6 4 7 3 0（0为结束符），建立： 所求结果=4 程序结构：类型说明； 建表函数：Creatlist(L); 求值函数：Adjmax(L); main( ) { 变量说明； 调用Creatlist(L)建表；调用Adjmax(L)求值； 打印数据；释放链表空间； Y 继续？ N 停止} //ivince //启动程序后输入字符（每输入一个字符，都要回车结束），如果字符不是"@"和"0"，字符就会进队。输入"0",则队头元素出队；输入"@",所有元素出队。 //特殊情况：直接输入"0"，或直接输入"@"都已经做了相应处理 #include #include typedefstruct node { charch; struct node* next; }Qnode,*Qlink; typedefstruct { Qnode *front,*rear; }linkqueue; voidCreatqueue(linkqueue *q) { q->front=(Qlink)malloc(sizeof(Qnode)); q->front->next=NULL; q->rear=q->front; } intEmptyqueue (linkqueue *q) //判队空

{ if(q->front==q->rear) return(1); else return (0); } void Enqueue(linkqueue *q,char e) //元素e进队 { Qlink p=(Qlink)malloc(sizeof(Qnode)); //申请进队节点 p->ch=e; p->next=NULL; q->rear->next=p; q->rear=p; } intDequeue(linkqueue *q) //出队 { Qlink p; if (Emptyqueue(q)) return(NULL); //队空处理 else { p=q->front ; q->front=p->next ; free(p); return(q->front->ch); } } void main(void) //主函数 { linkqueue q; charch='0',ch2; Creatqueue(&q); printf("请输入字符，字符0出队字符@全部出队：\n"); while(ch!='@') { scanf("%c",&ch); fflush(stdin); //清除缓存字符 if(ch=='0') { ch2=Dequeue(&q); if(ch2!=NULL) printf("%c\n",ch2); else printf("目前队列中不存在任何元素!,请您先存入!!\n");

数据结构实验报告全集

数据结构实验报告全集 实验一线性表基本操作和简单程序 1．实验目的 （1）掌握使用Visual C++ 6.0上机调试程序的基本方法； （2）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2．实验要求 （1）认真阅读和掌握和本实验相关的教材内容。 （2）认真阅读和掌握本章相关内容的程序。 （3）上机运行程序。 （4）保存和打印出程序的运行结果，并结合程序进行分析。 （5）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include iostream.h>//头文件 #include//库头文件-----动态分配内存空间 typedef int elemtype;//定义数据域的类型 typedef struct linknode//定义结点类型 { elemtype data;//定义数据域 struct linknode *next;//定义结点指针 }nodetype; 2）创建单链表

nodetype *create()//建立单链表，由用户输入各结点data域之值，//以0表示输入结束 { elemtype d;//定义数据元素d nodetype *h=NULL,*s,*t;//定义结点指针 int i=1; cout<<"建立一个单链表"<> d; if(d==0) break;//以0表示输入结束 if(i==1)//建立第一个结点 { h=(nodetype*)malloc(sizeof(nodetype));//表示指针h h->data=d;h->next=NULL;t=h;//h是头指针 } else//建立其余结点 { s=(nodetype*) malloc(sizeof(nodetype)); s->data=d;s->next=NULL;t->next=s; t=s;//t始终指向生成的单链表的最后一个节点

数据结构实验报告-答案

数据结构(C语言版) 实验报告

专业班级学号姓名 实验1 实验题目：单链表的插入和删除 实验目的： 了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。 实验要求： 建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的字符串，先找到相应的结点，后删除之。 实验主要步骤： 1、分析、理解给出的示例程序。 2、调试程序，并设计输入数据（如：bat，cat，eat，fat，hat，jat，lat，mat，#），测 试程序的如下功能：不允许重复字符串的插入；根据输入的字符串，找到相应的结点并删除。 3、修改程序： （1）增加插入结点的功能。 （2）将建立链表的方法改为头插入法。 程序代码: #include"" #include"" #include"" #include"" typedef struct node . . 示意图：

head head head 心得体会： 本次实验使我们对链表的实质了解更加明确了，对链表的一些基本操作也更加熟练了。另外实验指导书上给出的代码是有一些问题的，这使我们认识到实验过程中不能想当然的直接编译执行，应当在阅读并完全理解代码的基础上再执行，这才是实验的意义所在。

实验2 实验题目：二叉树操作设计和实现 实验目的： 掌握二叉树的定义、性质及存储方式，各种遍历算法。 实验要求： 采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历 的操作，求所有叶子及结点总数的操作。 实验主要步骤： 1、分析、理解程序。 2、调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点（空指针）， 如ABD###CE##F##，建立二叉树，求出先序、中序和后序以及按层次遍历序列，求 所有叶子及结点总数。 实验代码 #include"" #include"" #include"" #define Max 20 ertex=a; irstedge=NULL; irstedge; G->adjlist[i].firstedge=s; irstedge; R[i] 留在原位

数据结构上机实验答案

《数据结构实验指导书》答案 实验一： 1、请编写函数int fun(int *a, int *b),函数的功能是判断两个指针a和b所指存储单 元的值的符号是否相同；若相同函数返回1，否则返回0。这两个存储单元中的值都不为0。在主函数中输入2个整数、调用函数fun、输出结果。 #include int fun(int *a, int *b) { if (*a*(*b)>0) return(1); else return(0); } main() { int x,y; scanf("%d%d",&x,&y); if (fun(&x,&y)) printf("yes\n"); else printf("no"); } 2、计算1+2+3+……+100，要求用指针进行设计。即设计函数int fun(int *n)实现求 1+2+3+……+*n，在主函数中输入、调用、输出结果。 #include int fun(int *n) { int i,sum=0; for (i=1;i<=*n;i++) sum+=i; return(sum); } main() { int x,sum; scanf("%d",&x); printf("the sum is %d\n",fun(&x)); } 3、函数的功能是求数组a中最大数的位置（位序号）。在主函数中输入10个整数、调用函

数fun、输出结果。 #define N 10 #include void input(int *a,int n) { int i; for (i=0;i*max) max=a+i; return(max-a); } main() {int a[N],maxi; input(a,N); maxi=fun(a,N); printf("\n the max position is %d\n",maxi); } 4、请编写函数fun(int *a,int n, int *odd, int *even),函数的功能是分别求出数组a 中所有奇数之和和所有偶数之和。形参n给出数组中数据的个数；利用指针odd和even分别返回奇数之和和偶数之和。在主函数中输入10个整数、调用函数fun、输出结果。 #define N 10 #include void input(int *a,int n) { int i; for (i=0;i

数据结构上机实验报告

数据结构实验报告 一．顺序表 要求：实现顺序表的初始化、在指定位置插入和删除元素。 算法思路：线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。顺序表的初始化操作就是为顺序表分配一个预定义大小的空间，并将线性表的当前长度设为“0”。线性表的插入操作是在线性表的第i-1个数据元素和第i个元素之间插入新的数据元素，使得长度为n的线性表变成长度为n+1的线性表，而删除恰好相反长度变为n-1的线性表，而且删除点后面的元素要往前移动一个位。 程序代码： #include #include #define MAXSIZE 50 typedef char elemtype; typedef struct //类型定义 { elemtype v[MAXSIZE]; int last; }SeqList; SeqList *Init_SeqList() //初始化操作 { SeqList *L; L=(SeqList*)malloc(sizeof(SeqList)); L->last=-1; return L; } void Create(SeqList *L) //建立顺序表 { int i=0; elemtype ch; scanf("%c",&ch); while(ch!='\n') { L->v[i++]=ch; scanf("%c",&ch); L->last=i-1; } } void PrintL(SeqList *L) //输出顺序表 { int i; printf("此表为:\n");

for(i=0;ilast;i++) { printf("%c",L->v[i]); } printf("%c\n",L->v[i]); } void Length(SeqList *L) //顺序表长度函数{ printf("此表长度:\n%d",L->last+1); printf("\n"); } void insert(SeqList *L,int i,elemtype x) //插入函数 { int j; if(L->last==0) printf("Error!\n"); if(i<1||i>L->last) printf("Error!"); for(j=L->last;j>=i-1;j--) L->v[j+1]=L->v[j]; L->v[i-1]=x; L->last++; PrintL(L); Length(L); } void Delete(SeqList *L,int i) //删除函数 { int j; if(L->last==-1) printf("Error!"); if(i<1||i>L->last+1) printf("Error!"); for(j=i;j<=L->last;j++) L->v[j-1]=L->v[j]; L->last--; PrintL(L); Length(L); } void main() //程序主函数 { int i,j,k; elemtype a,b;

数据结构上机答案(c语言版)

实习一： 1、编写一个读入一个字符串，把它存入一个链表，并按相反的次序打印的程序。 2、设有一个单位的人员工资有如下信息：name、department、 base pay、allowance、total。现从键盘输入一组人员工资数据并将它们存储到名为paydata的文件中；再从paydata取出工资数据并给每个人的base pay增加100元，增加后将工资数据显示于屏幕(每行1人)。请编写能够完成上述工作的程序。 代码如下： 1.#include #include #include void main() { char x; struct node //定义个结构node { char c; struct node *next; }; struct node *head,*pb,*pf,*p,*s,*t; //定义指针 printf("请输入字符串，按Enter结束！\n"); for(int i=0;x!='\n';i++) { pb=(struct node *)malloc(sizeof(struct node));//动态分配n字节的内存空间 scanf("%c",&pb->c); //输入字符 x=pb->c; if(i==0){ //输入的首个字符作为头结点pf head=pb; pf=head;} else if(pb->c!='\n'){ //如果输入的是Enter，输入终止，否则把字符依次存入链表 pf->next=pb; //把输入的字符pb存在pf后，pb后为空 pb->next=NULL;

数据结构上机例题及答案

习题二 ⒉１描述以下四个概念的区别：头指针变量，头指针，头结点，首结点（第一个结点）。解：头指针变量和头指针是指向链表中第一个结点（头结点或首结点）的指针；在首结点之前附设一个结点称为头结点；首结点是指链表中存储线性表中第一个数据元素的结点。若单链表中附设头结点，则不管线性表是否为空，头指针均不为空，否则表示空表的链表的头指针为空。 2.2简述线性表的两种存储结构有哪些主要优缺点及各自使用的场合。 解：顺序存储是按索引直接存储数据元素，方便灵活，效率高，但插入、删除操作将引起元素移动，降低了效率；而链式存储的元素存储采用动态分配，利用率高，但须增设表示结点之间有序关系的指针域，存取数据元素不如顺序存储方便，但结点的插入和删除十分简单。顺序存储适用于线性表中元素数量基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素的情况；而链式存储适用于频繁进行元素动态插入或删除操作的场合。 2.3 在头结点为h的单链表中，把值为b的结点s插入到值为a的结点之前，若不存在a，就把结点s插入到表尾。 Void insert(Lnode *h,int a,int b) {Lnode *p,*q,*s; s=(Lnode*)malloc(sizeof(Lnode)); s->data=b; p=h->next; while(p->data!=a&&p->next!=NULL) {q=p; p=p->next; } if (p->data==a) {q->next=s; s->next=p;} else

{p->next=s; s->next=NULL; } } 2.4 设计一个算法将一个带头结点的单链表A分解成两个带头结点的单链表A和B，使A中含有原链表中序号为奇数的元素，而B中含有原链表中序号为偶数的元素，并且保持元素原有的相对顺序。 Lnode *cf(Lnode *ha) {Lnode *p,*q,*s,*hb; int t; p=ha->next; q=ha; t=0; hb=(Lnode*)malloc(sizeof(Lnode)); s=hb; while(p->next!=NULL) {if (t==0) {q=p;p=p->next;t=1;} else {q->next=p->next; p->next=s->next; s->next=p; s=p; p=p->next; t=0; } } s->next=NULL; return (hb); }

数据结构练习1

华东理工大学网络学院 《数据结构》（ch1绪论和ch2线性表） 班级 学号 姓名 成绩 一、 名词解释（每小题2分，共10分） 1.数据结构 2. 线性结构 3.存储结构 4. 逻辑结构 5.非线性结构 答：1.数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。 2. 线性结构：数据逻辑结构中的一类。它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都有且只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。栈、队列、串等都是线性结构。 3. 存储结构：数据元素及其关系在计算机存储器内的表示，称为数据的存储结构。 4. 逻辑结构：指数据元素之间的逻辑关系。 5.非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。 二、 填空题（每小题1分，共10分） 1. 非空的循环单链表head的尾结点p满足条件 p->next==head 。 2. 对于给定的n个数据元素，可能构造出集合 、线性结构 、 树形结构和网状（图形）结构四种逻辑结构。 3. 一个算法具有有穷性、 确定性 、 可行性 、输入和输出五个重要特性。 4. 在一个单链表中p所指结点之后插入s所指结点时,应执行s->next= p->next 和p->next= S 的操作。 三、判断正误（在正确的说法后面打勾，反之打叉）（每小题1分，共10分） （ × ）1. 线性数据结构只能用顺序结构存放，非线性数据结构只能用链式存储存放。 （ √ ）2. 单链表中逻辑上相邻的元素未必在存储的物理位置次序上相邻。 （ × ）3. 链式存储是一种随机存取的数据结构。 （ √ ）4 顺序表中逻辑上相邻的元素的物理位置必定相邻。 （ × ）5. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 （ √ ）6. 在顺序表中按下标序号访问任意一结点的时间复杂度均为O(1) 。 （ √ ）7. 带头结点的单向链表L为空的判定条件是L->next=null。 （ √ ）8. 在顺序表中插入或删除一个元素，需要平均移动表中一半元素。 （ × ）9. 线性表的逻辑顺序与存储顺序总是一致的。。 （ √ ）10. 任何一个算法的设计取决于选定的数据（逻辑）结构，而算法的实现依赖于采用的存储结构。 四、单选题（每题2分，共30分） 1.有程序如下： i=1; k=0; while(i

数据结构上机实验指导

《数据结构》课程上机实验指导书 实验一 【实验名称】顺序表的基本算法 【实验目的】 创建一个顺序表，掌握线性表顺序存储的特点。设计和验证顺序表的查找、插入、删除算法。 【实验要求】 （1）从键盘读入一组整数，按输入顺序形成顺序表。并将创建好的顺序表元素依次打印在屏幕上。 设计一个带选择菜单的主函数，菜单中具备任意选择删除、插入、查找数据元素（2）的功能。 当选择删除功能时，从键盘读入欲删除的元素位置或元素值，按指定方式删除；3（）当选择插入功能时，从键盘读入新元素值和被插入位置，在指定位置插入；当选择查找功能时，从键盘读入欲查找的元素值，返回其位置序号。 （4）每种操作结束后，都能在屏幕上打印出此时顺序表元素的遍历结果。 【实验步骤】、实验前先写好算法。1 上机编写程序。2、编译。3、调试。4、 综合实例！，2-62-8！带菜单的主函数参考书上2.5，，，书上参考算法例程：2-12-42-5注意：顺序表的结构体！typedef struct { datatype items[listsize]; int length; }SpList; 实验二 【实验名称】单链表的基本算法 【实验目的】 创建一个单链表，掌握线性表链式存储的特点。设计和验证链表的查找、插入、删除、求表长的算法。【实验要求】 （1）从键盘读入一组整数，按输入顺序形成单链表。并将创建好的单链表元素依次打印在屏幕上。（注意：选择头插法或者尾插法！） 设计一个带选择功能菜单的主函数，菜单中至少具备任意选择删除、插入、查找（2）数据元素，和求单链表表长等几项功能。 当选择删除功能时，从键盘读入欲删除的元素位置，按指定位置删除；当选择插）（3入功能时，从键盘读入新元素值和被插入位置，在指定位置插入；当选择查找功能时，从键盘读入欲查找的元素值，返回其位置序号；当选择求表长功能时，返回该单链表表长的数值。 （4）每种操作结束后，都能在屏幕上打印出此时单链表元素的遍历结果。 【实验步骤】、实验前先写好算法。1 、上机编写程序。2 编译。3、调试。4、 综合实例！！带菜单的主函数参考书上，2-132-15，2-172.5，，书上参考算法例程：2-102-12 另外，注意，指针的初始化！指针的操作必须谨慎！链表的结构体如下：typedef struct Node { Datatype ch; struct Node *next; }LNode, *Pnode, *Linklist; 实验三

经典数据结构上机题_答案解析

数据结构上机实验题目 实验一线性表的顺序存储结构 实验学时 2学时 背景知识:顺序表的插入、删除及应用。 目的要求： 1．掌握顺序存储结构的特点。 2．掌握顺序存储结构的常见算法。 实验容 1．输入一组整型元素序列，建立顺序表。 2．实现该顺序表的遍历。 3．在该顺序表中进行顺序查找某一元素,查找成功返回1,否则返回0。4．判断该顺序表中元素是否对称,对称返回1,否则返回0。 5．实现把该表中所有奇数排在偶数之前,即表的前面为奇数,后面为偶数。 6．输入整型元素序列利用有序表插入算法建立一个有序表。 7．利用算法6建立两个非递减有序表并把它们合并成一个非递减有序表。 8. 利用该顺序结构实现循环队列的入队、出队操作。 8．编写一个主函数,调试上述算法。 #include #include

#define OVERFLOW 0 #define MAXSIZE 100 typedef int ElemType; typedef struct list {ElemType elem[MAXSIZE]; int length; }Sqlist; void Creatlist(Sqlist &L) {int i; printf("请输入顺序表的长度："); //输入一组整型元素序列，建立一个顺序表。 scanf("%d",&L.length); for(i=0;i

数据结构课程__课后习题答案

《数据结构简明教程》练习题及参考答案 练习题1 1. 单项选择题 （1）线性结构中数据元素之间是（）关系。 A.一对多 B.多对多 C.多对一 D.一对一 答：D （2）数据结构中与所使用的计算机无关的是数据的（）结构。 A.存储 B.物理 C.逻辑 D.物理和存储 答：C （3）算法分析的目的是（）。 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 答：C （4）算法分析的两个主要方面是（）。 A.空间复杂性和时间复杂性 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 答：A （5）计算机算法指的是（）。 A.计算方法 B. 排序方法 C.求解问题的有限运算序列 D.调度方法答：C （6）计算机算法必须具备输入、输出和（）等5个特性。 A.可行性、可移植性和可扩充性 B.可行性、确定性和有穷性 C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性 答：B 2. 填空题 （1）数据结构包括数据的①、数据的②和数据的③这三个方面的内容。 答：①逻辑结构②存储结构③运算

数据结构简明教程 （2）数据结构按逻辑结构可分为两大类，它们分别是①和②。 答：①线性结构②非线性结构 （3）数据结构被形式地定义为（D,R），其中D是①的有限集合，R是D上的②有限集合。 答：①数据元素②关系 （4）在线性结构中，第一个结点①前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点②后继结点，其余每个结点有且只有1个后继结点。 答：①没有②没有 （5）在树形结构中，树根结点没有①结点，其余每个结点有且只有②个前驱结点；叶子结点没有③结点，其余每个结点的后继结点数可以是④。 答：①前驱②1 ③后继④任意多个 （6）在图形结构中，每个结点的前驱结点数和后继结点数可以是（）。 答：任意多个 （7）数据的存储结构主要有四种，它们分别是①、②、③和④存储结构。 答：①顺序②链式③索引④哈希 （8）一个算法的效率可分为①效率和②效率。 答：①时间②空间 3. 简答题 （1）数据结构和数据类型两个概念之间有区别吗？ 答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素的集合。数据类型不仅定义了一组数据元素，而且还在其上定义了一组操作。 （2）简述线性结构、树形结构和图形结构的不同点。 答：线性结构反映结点间的逻辑关系是一对一的，树形线性结构反映结点间的逻辑关系是一对多的，图在结构反映结点间的逻辑关系是多对多的。 （3）设有采用二元组表示的数据逻辑结构S=(D,R)，其中D={a,b,…,i}，R={(a,b),(a,c),(c,d),(c,f),(f,h),(d,e),(f,g),(h,i)}，问相对于关系R，哪些结点是开始结点，哪些结点是终端结点？ 答：该逻辑结构为树形结构，其中a结点没有前驱结点，称为根结点，b、e、g、i结点没有后继结点，是终端结点，也称为叶子结点。 （4）以下各函数是算法中语句的执行频度，n为问题规模，给出对应的时间复杂度： T1(n)=n log2n-1000log2n T2(n)=3 log2 n-1000log2n

数据结构上机考试题

注意事项1. 考试时间2小时，13：00-15：00 2. 题目4选2 3. 所有题目均使用标准输入和标准输出3. 只提交源程序，文件后缀名只能是.C或.CPP 4. 源文件大小不能超过10K，否则会被当作恶意提交而扣分5. 严格按照题目要求输出，去掉不需要的提示信息或调试信息6. 在程序中不要使用fflush(stdin)函数，否则会导致结果错误另外注意：本次是模拟测试，上机时间是4个小时，我们考试时间从14点开始到17点30分结束。同学视自己的能力，能做几道做几道。 哈夫曼树 时间限制: 100 second 内存限制: 100 Kb 描述 构造哈夫曼树（最优二叉树） 输入 输入n个结点每个结点的权值 输出 构造哈夫曼树（是最优二叉树）得到每个结点的哈夫曼编码 输入样例 23 186 64 13 22 32 103 21 15 47 57 1 5 32 20 57 63 15 1 48 51 80 23 8 输出样例 1( 186):00 2( 64):1001 3( 13):101100 4( 22):110010 5( 32):11100 6( 103):011 7( 21):110001 8( 15):101101 9( 47):11010 10( 57):0101 11( 1):101111000 12( 5):10111101 13( 32):11101 14( 20):110000 15( 57):1010 16( 63):1000 17( 15):101110 18( 1):101111001 19( 48):11011 20( 51):0100 21( 80):1111 22( 23):110011 23( 8):1011111 提示 输入第一行是结点数23 第二行是这几个结点的权值输出格式为结点号（权值）：哈夫曼编码

南邮数据结构上机实验四内排序算法的实现以及性能比较

实验报告 （2015 / 2016学年第二学期） 课程名称数据结构A 实验名称内排序算法的实现以及性能比较 实验时间2016 年 5 月26 日 指导单位计算机科学与技术系 指导教师骆健 学生姓名耿宙班级学号B14111615 学院(系) 管理学院专业信息管理与信息系统

—— 实习题名:内排序算法的实现及性能比较 班级 B141116 姓名耿宙学号 B14111615 日期2016.05.26 一、问题描述 验证教材的各种内排序算法，分析各种排序算法的时间复杂度；改进教材中的快速排序算法，使得当子集合小于10个元素师改用直接插入排序；使用随即数发生器产生大数据集合，运行上述各排序算法，使用系统时钟测量各算法所需的实际时间，并进行比较。系统时钟包含在头文件“time.h”中。 二、概要设计 文件Sort.cpp中包括了简单选择排序SelectSort()，直接插入排序InsertSort()，冒泡排序BubbleSort()，两路合并排序Merge()，快速排序QuickSort()以及改进的快速排序GQuickSort()六个内排序算法函数。主主函数main的代码如下图所示： 三、详细设计 1.类和类的层次设计 在此次程序的设计中没有进行类的定义。程序的主要设计是使用各种内排序算法对随机 生成的数列进行排列，并进行性能的比较，除此之外还对快速排序进行了改进。下图为主函 数main的流程图：

——

main() 2.核心算法 1)简单选择排序： 简单选择排序的基本思想是：第1趟，在待排序记录r[1]~r[n]中选出最小的记录，将它与r[1]交换；第2趟，在待排序记录r[2]~r[n]中选出最小的记录，将它与r[2]交换；以此类推，第i趟在待排序记录r[i]~r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到

数据结构实验一题目一线性表实验报告

数据结构实验报告 实验名称：实验1——线性表 学生姓名： 班级： 班内序号： 学号： 日期： 1．实验要求 1、实验目的：熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法 学习指针、模板类、异常处理的使用 掌握线性表的操作的实现方法 学习使用线性表解决实际问题的能力 2、实验内容： 题目1： 线性表的基本功能： 1、构造：使用头插法、尾插法两种方法 2、插入：要求建立的链表按照关键字从小到大有序 3、删除 4、查找 5、获取链表长度 6、销毁 7、其他：可自行定义 编写测试main()函数测试线性表的正确性。 2. 程序分析 存储结构 带头结点的单链表

关键算法分析 1.头插法 a、伪代码实现：在堆中建立新结点 将x写入到新结点的数据域 修改新结点的指针域 修改头结点的指针域,将新结点加入链表中 b、代码实现： Linklist::Linklist(int a[],int n)

堆中建立新结点 b.将a[i]写入到新结点的数据域 c.将新结点加入到链表中 d.修改修改尾指针 b、代码实现: Linklist::Linklist(int a[],int n,int m)取链表长度函数 a、伪代码实现：判断该链表是否为空链表，如果是，输出长度0 如果不是空链表，新建立一个temp指针，初始化整形数n为0 将temp指针指向头结点 判断temp指针指向的结点的next域是否为空，如果不是，n加一，否 则return n 使temp指针逐个后移，重复d操作，直到temp指针指向的结点的next 域为0，返回n b 、代码实现 void Linklist::Getlength()Linklist(); cout<

《数据结构》上机实验一资料

青岛理工大学 数据结构课程实验报告 课程名称数据结构班级软件131 实验日期 4.15姓名学号实验成绩 实验名称线性表的顺序表示与链式表示 实验目的及要求实验目的 1.加深理解线性表的顺序表示与链式表示的意义和区别，掌握用它们表示时各基本操作的设计与实现。 2.学会定义线性表的顺序存储类型和链式存储类型，实现C程序的基本结构，对线性表的一些基本操作和具体的函数定义。 3.掌握线性表的基本操作（初始化、建立、插入、删除、遍历等）。 4.掌握对多函数程序的输入、编辑、调试和运行过程。 5.进一步熟练C语言的使用，特别是指针和链表的使用。能在实际应用背景下恰当选择顺序存储和链式存储。 实验要求 1.预习C语言中的结构的定义和基本操作方法 2.对线性表的每个基本操作用单独的函数实现 3.编写完整程序完成下面的实验内容并上机运行 4.整理并上交实验报告 实验环境硬件平台：普通的PC机 软件平台：Windows 2003操作系统编程环境：VisualC++ 实验内容1.分别建立包含10个数据元素的顺序线性表和链式线性表； 2.从键盘输入一个数据元素和插入位置k，将元素插入到线性表中第k（包含0号位置）个位置； 3.从键盘输入一个数据元素关键字或位置k（包含1号位置），从线性表中删除相应数据元素； 4.能完成查找功能； 5.给出程序及插入、删除前和插入、删除后线性表结果。 //创建顺式线性表 struct number *creat(void) { struct number *head,*p1; p1=head=(struct number*)malloc( SIZE * sizeof(struct number)); scanf("%ld",&p1->num); for(;p1->num!=0;L++) {

数据结构上机实验8

数据结构上机实验（八）图 班级：学号：姓名： 上机时间：地点： 一、实验目的 1.掌握图的各种存储结构，包括邻接矩阵和邻接表等。 2.掌握图的基本运算，包括创建图、输出图、深度优先遍历、广度优先遍历算 法等。 二、实验内容 1．实现图的相关运算，并在此基础上设计一个主程序完成如下功能： （以P234图8.26所示的有向图G为例） （1）建立如图8.26所示的有向图G的邻接矩阵并输出； （2）由有向图G的邻接矩阵产生邻接表并输出； （3）再由（2）的邻接表产生对应的邻接矩阵并输出。 2．实现图的遍历运算，并在此基础上设计一个主程序完成如下功能： （以P234图8.26所示的有向图G为例） （1）输出如图8.26所示的有向图G从顶点0开始的深度优先遍历序列（递归算法）； （2）输出如图8.26所示的有向图G从顶点0开始的深度优先遍历序列（非递归算法）； （3）输出如图8.26所示的有向图G从顶点0开始的广度优先遍历序列。 三、实验过程 1．了解常用函数所在的头文件 stdlib.h stdlib 头文件里包含了C语言的一些函数 该文件包含了的C语言标准库函数的定义 stdlib.h里面定义了五种类型、一些宏和通用工具函数。类型例如size_t、wchar_t、div_t、ldiv_t和lldiv_t；宏例如EXIT_FAILURE、EXIT_SUCCESS、RAND_MAX 和MB_CUR_MAX等等；常用的函数如malloc()、calloc()、realloc()、free()、system()、atoi()、atol()、rand()、srand()、exit()等等。具体的内容你自己可以打开编译器的include目录里面的stdlib.h头文件看看。 conio.h conio.h不是C标准库中的头文件。 conio是Console Input/Output（控制台输入输出）的简写，其中定义了通过控制台进行数据输入和数据输出的函数，主要是一些用户通过按键盘产生的对应操作，比如getch()函数等等。 &表示引用传递。在函数参数表中，出现带&这个的形参，表示引用传递。2．程序实现（以下代码仅起参考作用） （1）图的相关运算 #include