《数据结构上机试题[教育试题]》由会员分享，可在线阅读，更多相关《数据结构上机试题[教育试题]（22页珍藏版）》请在金锄头文库上搜索。
1、数据结构上机试题一、 顺序表的操作（1）插入元素操作：将新元素x插入到顺序表a中第i个位置。（2）删除元素操作：删除顺序表a中第i个元素。#include#include#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(ia.length+1|a.length=100);elsefor(j=a.length+1;ji;j-)a.dataj=a.d
2、ataj-1;a.dataj=x;a.length+; void deleted(sqlist &a ,int i)/ 删除元素操作int j;if(ia.length);elsefor(j=i;ja.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(a);/构造一个空表 coutn; cout输入表长为 n 个数: ; for(j=0;je; insert(a,j,e); cout插入前: ; for(j=0;ja.
3、length ;j+) couta.dataj ; couti; coutx; cout打算在第i个位置插入元素x ; insert(a,i-1,x);/由于从0开始，要构造显示从一开始，所以减1 cout插入后结果: ; for(j=0;ja.length;j+) couta.dataj ; couts; deleted(a,s-1);/由于从0开始，要构造显示从一开始，所以减1 cout删除后结果: ; for(j=0;ja.length;j+) couta.dataj ;二、单链表的操作（1）创建一个带头结点的单链表；（2）插入元素操作：将新元素x插入到单链表中第i个元素之后；（3）删除
4、元素操作：删除单链表中值为x的元素；#include#includetypedef 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请输入链表第ip-data;p-next=L-next;L-next=p;/插入元素操作：将
5、新元素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;/删除元素操作：删除单链表中值
6、为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)coutdatanext;void main()LNode * L,*p;/节点为Lint i,x,y,s,n;/i插入位置，X插入元素，y为删除元素，n表长coutn;createlist(L,n);cout输出插入之前：;p
7、rint(L);couti;coutx;insert(L,i,x);cout输出插入后：;print(L);couty;deleted(L,y);/删除元素操作：删除单链表中值为y的元素；cout输出删除后：;print(L);三、在顺序栈上实现将非负十进制数转换成二进制数#include#include#define 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-;co
8、utt;void main()int x,t;cout请输入你要转换的非负十进制数x:x;cout输出转换后的二进制数:;conversion(x);coutendl;四、在顺序表中采用顺序查找算法和折半查找算法寻找关键字X在顺序表中的位置。#include#include#define MAX 100/在顺序表中采用顺序查找算法和折半查找算法寻找关键字X在顺序表中的位置typedef struct int dataMAX;int length;sqlist;void init(sqlist &a)/线性表初始化 a.length=0;void insert(sqlist &a ,int i,
9、int x)/ 插入元素操作int j;if(ia.length+1|a.length=100);elsefor(j=a.length+1;ji;j-)a.dataj=a.dataj-1;a.dataj=x;a.length+; int search(sqlist &sq,int x)/顺序查找算法int i;for(i=0;isq.length;i+)/顺序表存储从0开始if(sq.datai=x)return i;int hsearch(sqlist &sq,int low,int high,int x)/折半查找算法int mid;while(lowx)high=mid-1;else i
10、f(sq.datamidx)low=mid+1;void main() sqlist sq;/线性表为sq int i,e,x,y,n;/i插入位置，x,y要查找元素，n表长 init(sq);/构造一个空表 coutn; cout输入表长为 n 个数: ; for(i=0;ie; insert(sq,i,e); cout查找前（便于判断）:endl; for(i=0;isq.length ;i+) coutsq.datai ; coutendl; cout采用顺序查找算法： endl; coutendl; coutx; coutendl; cout关键字x在顺序表中的位置为search(sq,x)+1endl; /下表从0开始，+1显示时，转化成从1开始了 cout采用折半查找算法： endl; coutendl; couty; coutendl; cout关键字y在顺序表中的位置为hsearch(sq,1,sq.length,y)+1endl; 五、将无序数列使用直接插入排序算法和快速排序算法将其排成递增有序数列。#include#include#define MAX 100/将无序数列使用直接插入排序算法和快速排序算法将其排成递增有序数列typedef struct int dataMAX;int length;sqlist;void init(sq
