数据结构上机试题教育试题

1、数据结构上机试题一、 顺序表的操作（1）插入元素操作：将新元素x插入到顺序表a中第i个位置。（2）删除元素操作：删除顺序表a中第i个元素。#include<iostream.h>#include<stdlib.h>#define max 100；typedef structint data100;int length;sqlist;void init(sqlist &a)/线性表初始化 a.length=0;void insert(sqlist &a ,int i,int x)/ 插入元素操作int j;if(i<0|i>a.length+1

2、|a.length=100);elsefor(j=a.length+1;j>i;j-)a.dataj=a.dataj-1;a.dataj=x;a.length+; void deleted(sqlist &a ,int i)/ 删除元素操作int j;if(i<0&&i>a.length);elsefor(j=i;j<a.length;j+)a.dataj=a.dataj+1;a.length-;void main() sqlist a;/线性表为a int i,e,x,n,j,s;/i插入位置，e动态建线性表要用，x插入元素，n表长 init(

3、a);/构造一个空表 cout<<"输入表长 n: " cin>>n; cout<<"输入表长为 "<<n<<" 个数: " for(j=0;j<n;+j) cin>>e; insert(a,j,e); cout<<"插入前: " for(j=0;j<a.length ;j+) cout<<a.dataj<<" " cout<<"输入要插入位置i: &qu

4、ot; cin>>i; cout<<"输入要插入的元素x: " cin>>x; cout<<"打算在第"<<i<<"个位置插入元素"<<x ; insert(a,i-1,x);/由于从0开始，要构造显示从一开始，所以减1 cout<<"插入后结果: " for(j=0;j<a.length;j+) cout<<a.dataj<<" " cout<<"

5、输入要删除的位置s: " cin>>s; deleted(a,s-1);/由于从0开始，要构造显示从一开始，所以减1 cout<<"删除后结果: " for(j=0;j<a.length;j+) cout<<a.dataj<<" "二、单链表的操作（1）创建一个带头结点的单链表；（2）插入元素操作：将新元素x插入到单链表中第i个元素之后；（3）删除元素操作：删除单链表中值为x的元素；#include<iostream.h>#include<stdlib.h>typed

6、ef struct lnodeint data;struct lnode *next;lnode;/创建一个带头结点的长度长度长度为n的链表l；void createlist(lnode *&l ,int n)int i;lnode *p;l=(lnode *)malloc(sizeof(lnode);l->next=null;for(i=1;i<=n;i+)p=(lnode *)malloc(sizeof(lnode);cout<<"请输入链表第"<<i<<"个元素"cin>>p-&g

7、t;data;p->next=l->next;l->next=p;/插入元素操作：将新元素x插入到单链表l中第i个元素之后void insert(lnode *&l ,int i,int x)int j=0;lnode *p,*q;p=l;while(p->next!=null)j+;if(j=i)q=(lnode *)malloc(sizeof(lnode);/找到位置q->data=x;/放入数据q->next=p->next;p->next=q;break;p=p->next;if(p->next=null)q=(lno

8、de *)malloc(sizeof(lnode);/找到位置q->data=x;/放入数据q->next=p->next;p->next=q;/删除元素操作：删除单链表中值为x的元素；void deleted(lnode *&l ,int x)lnode *p,*q;p=l;while(p->next!=null)if(p->next->data=x)q=p->next;p->next=p->next->next;free(q);p=p->next;void print(lnode *&l)lnode *

9、p;p=l->next;while(p!=null)cout<<p->data<<" "p=p->next;void main()lnode * l,*p;/节点为lint i,x,y,s,n;/i插入位置，x插入元素，y为删除元素，n表长cout<<"输入表长 n: "cin>>n;createlist(l,n);cout<<"输出插入之前："print(l);cout<<"请输入插入的位置i: "cin>>i;

10、cout<<"请输入插入的元素x: "cin>>x;insert(l,i,x);cout<<"输出插入后："print(l);cout<<"请输入删除的元素y: "cin>>y;deleted(l,y);/删除元素操作：删除单链表中值为y的元素；cout<<"输出删除后："print(l);三、在顺序栈上实现将非负十进制数转换成二进制数#include<iostream.h>#include<stdlib.h>#defi

11、ne max 100/在顺序栈上实现将非负十进制数x转换成二进制数void conversion(int &x)int stackmax;int top=-1;int t;while(x)stack+top=x%2;x=x/2;while(top!=-1)t=stacktop-;cout<<t;void main()int x,t;cout<<"请输入你要转换的非负十进制数x:"<<endl;cin>>x;cout<<"输出转换后的二进制数:"conversion(x);cout<

12、<endl;四、在顺序表中采用顺序查找算法和折半查找算法寻找关键字x在顺序表中的位置。#include<iostream.h>#include<stdlib.h>#define max 100/在顺序表中采用顺序查找算法和折半查找算法寻找关键字x在顺序表中的位置typedef struct int datamax;int length;sqlist;void init(sqlist &a)/线性表初始化 a.length=0;void insert(sqlist &a ,int i,int x)/ 插入元素操作int j;if(i<0|i&g

13、t;a.length+1|a.length=100);elsefor(j=a.length+1;j>i;j-)a.dataj=a.dataj-1;a.dataj=x;a.length+; int search(sqlist &sq,int x)/顺序查找算法int i;for(i=0;i<sq.length;i+)/顺序表存储从0开始if(sq.datai=x)return i;int hsearch(sqlist &sq,int low,int high,int x)/折半查找算法int mid;while(low<=high)mid=(low+high)/

14、2;if(sq.datamid=x)return mid;else if(sq.datamid>x)high=mid-1;else if(sq.datamid<x)low=mid+1;void main() sqlist sq;/线性表为sq int i,e,x,y,n;/i插入位置，x,y要查找元素，n表长 init(sq);/构造一个空表 cout<<"输入表长 n: " cin>>n; cout<<"输入表长为 "<<n<<" 个数: " for(i=0;i

15、<n;i+) cin>>e; insert(sq,i,e); cout<<"查找前（便于判断）:"<<endl; for(i=0;i<sq.length ;i+) cout<<sq.datai<<" " cout<<endl; cout<<"采用顺序查找算法： "<<endl; cout<<endl; cout<<"输入要查找元素关键字x " cin>>x; cout<

16、;<endl; cout<<"关键字"<<x<<"在顺序表中的位置为"<<search(sq,x)+1<<endl; /下表从0开始，+1显示时，转化成从1开始了 cout<<"采用折半查找算法： "<<endl; cout<<endl; cout<<"输入要查找元素关键字y " cin>>y; cout<<endl; cout<<"关键字"<

17、;<y<<"在顺序表中的位置为"<<hsearch(sq,1,sq.length,y)+1<<endl; 五、将无序数列使用直接插入排序算法和快速排序算法将其排成递增有序数列。#include<iostream.h>#include<stdlib.h>#define max 100/将无序数列使用直接插入排序算法和快速排序算法将其排成递增有序数列typedef struct int datamax;int length;sqlist;void init(sqlist &a)/线性表初始化 a.leng

18、th=0;void insert(sqlist &a ,int i,int x)/ 插入元素,构造无序数列int j;if(i<0|i>a.length+1|a.length=100);elsefor(j=a.length+1;j>i;j-)a.dataj=a.dataj-1;a.dataj=x;a.length+; /将哨兵放在a.datan中，被排序的记录放在a.data0.n-1中，直接插入排序算法。void insertsort(sqlist &a)/直接插入排序算法int i,j;int n=a.length;for(i=n-2;i>=0;i-

19、) if(a.datai>a.datai+1) a.datan=a.datai;/a.datan是哨兵 j=i+1; do a.dataj-1=a.dataj; j+;while(a.dataj<a.datan);a.dataj-1=a.datan;int partition(sqlist &a,int i,int j)int pivot=a.datai;while(i<j)while(i<j&&a.dataj>=pivot) j-; if(i<j) a.datai+=a.dataj; while(i<j&&a.

20、datai<=pivot) i+; if(i<j) a.dataj-=a.datai; a.datai=pivot; return i;void quicksort(sqlist &a,int low,int high)/快速排序 int pivotpos; /划分后的基准记录的位置if(low<high)/仅当区间长度大于1时才须排序pivotpos=partition(a,low,high); quicksort(a,low,pivotpos-1); quicksort(a,pivotpos+1,high); void main() sqlist sq1,sq2;

21、/线性表为sq1,sq2 int i,e,x,n1,n2;/n表长 init(sq1);/构造一个空表 cout<<"输入表长 n1: " cin>>n1; cout<<"输入表长为 "<<n1<<" 个数: " for(i=0;i<n1;i+) cin>>e; insert(sq1,i,e);/ 插入元素,构造无序数列 cout<<"无序数列为:"<<endl; for(i=0;i<sq1.length ;i+) cout<<sq1.datai<<" " co