数据结构上机试题一、顺序表的操作（1）插入元素操作：将新元素x插入到顺序表a中第i个位置。

（2）删除元素操作：删除顺序表a中第i个元素。

#include<iostream.h>#include<stdlib.h>#define MAX 100；typedef struct{int data[100];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||a.length==100);else{for(j=a.length+1;j>i;j--)a.data[j]=a.data[j-1];a.data[j]=x;a.length++;}}void deleted(sqlist &a ,int i)// 删除元素操作{int j;if(i<0&&i>a.length);else{for(j=i;j<a.length;j++)a.data[j]=a.data[j+1];a.length--;}}void main(){sqlist a;//线性表为aint i,e,x,n,j,s;//i插入位置，e动态建线性表要用，X插入元素，n表长init(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.data[j]<<" ";cout<<"输入要插入位置i: ";cin>>i;cout<<"输入要插入的元素x: ";cin>>x;cout<<"打算在第"<<i<<"个位置插入元素"<<x ; insert(a,i-1,x);//由于从0开始，要构造显示从一开始，所以减1cout<<"插入后结果: ";for(j=0;j<a.length;j++)cout<<a.data[j]<<" ";cout<<"输入要删除的位置s: ";cin>>s;deleted(a,s-1);//由于从0开始，要构造显示从一开始，所以减1cout<<"删除后结果: ";for(j=0;j<a.length;j++)cout<<a.data[j]<<" ";}二、单链表的操作（1）创建一个带头结点的单链表；（2）插入元素操作：将新元素x插入到单链表中第i 个元素之后；（3）删除元素操作：删除单链表中值为x的元素；#include<iostream.h>#include<stdlib.h>typedef struct LNode{int 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->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=(LNode *)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 *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;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>#define MAX 100//在顺序栈上实现将非负十进制数x转换成二进制数void conversion(int &x){int stack[MAX];int top=-1;int t;while(x){stack[++top]=x%2;x=x/2;}while(top!=-1){t=stack[top--];cout<<t;}}void main(){int x,t;cout<<"请输入你要转换的非负十进制数x:"<<endl;cin>>x;cout<<"输出转换后的二进制数:"; conversion(x);cout<<endl;}四、在顺序表中采用顺序查找算法和折半查找算法寻找关键字X在顺序表中的位置。

#include<iostream.h>#include<stdlib.h>#define MAX 100//在顺序表中采用顺序查找算法和折半查找算法寻找关键字X在顺序表中的位置typedef struct{int data[MAX];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||a.length==100);else{for(j=a.length+1;j>i;j--)a.data[j]=a.data[j-1];a.data[j]=x;a.length++;}}int search(sqlist &sq,int x)//顺序查找算法{int i;for(i=0;i<sq.length;i++)//顺序表存储从0开始if(sq.data[i]==x)return i;}int hsearch(sqlist &sq,int low,int high,int x)//折半查找算法{int mid;while(low<=high){mid=(low+high)/2;if(sq.data[mid]==x)return mid;else if(sq.data[mid]>x)high=mid-1;else if(sq.data[mid]<x)low=mid+1;}}void main(){sqlist sq;//线性表为sqint i,e,x,y,n;//i插入位置，x,y要查找元素，n表长init(sq);//构造一个空表cout<<"输入表长n: ";cin>>n;cout<<"输入表长为"<<n<<" 个数: ";for(i=0;i<n;i++){cin>>e;insert(sq,i,e);}cout<<"查找前（便于判断）:"<<endl;for(i=0;i<sq.length ;i++)cout<<sq.data[i]<<" ";cout<<endl;cout<<"采用顺序查找算法："<<endl;cout<<endl;cout<<"输入要查找元素关键字x ";cin>>x;cout<<endl;cout<<"关键字"<<x<<"在顺序表中的位置为"<<search(sq,x)+1<<endl; //下表从0开始，+1显示时，转化成从1开始了cout<<"采用折半查找算法："<<endl;cout<<endl;cout<<"输入要查找元素关键字y ";cin>>y;cout<<endl;cout<<"关键字"<<y<<"在顺序表中的位置为"<<hsearch(sq,1,sq.length,y)+1<<endl;}五、将无序数列使用直接插入排序算法和快速排序算法将其排成递增有序数列。