2022年数据结构上机试题资料 .pdf

《2022年数据结构上机试题资料 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构上机试题资料 .pdf（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构上机试题竺涌楠 0865138213 一、顺序表的操作（1）插入元素操作： 将新元素 x 插入到顺序表 a 中第i 个位置。（2）删除元素操作：删除顺序表a 中第 i 个元素。#include #include #define MAX 100 ；typedef struct int 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) ; 名师

2、资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 18 页 - - - - - - - - - else for(j=a.length+1;ji;j-) a.dataj=a.dataj-1; a.dataj=x; a.length+; void deleted(sqlist &a ,int i)/ 删除元素操作 int j; if(ia.length) ; else for(j=i;ja.length;j+) a.dataj=a.dataj+1; a.length-; void

3、 main() sqlist a;/线性表为 a 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 18 页 - - - - - - - - - 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.length ;j+) couta.dataj ; cou

4、ti; coutx; cout打算在第 i 个位置插入元素 x ; insert(a,i-1,x);/由于从 0 开始，要构造显示从一开始，所以减 1 cout插入后结果 : ; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 18 页 - - - - - - - - - for(j=0;ja.length;j+) couta.dataj ; couts; deleted(a,s-1);/ 由于从 0 开始，要构造显示从一开始，所以减 1 cout删除后结果 : ; fo

5、r(j=0;ja.length;j+) couta.dataj ; 二、单链表的操作（1）创建一个带头结点的单链表；（2）插入元素操作：将新元素x 插入到单链表中第i个元素之后；（3）删除元素操作：删除单链表中值为x 的元素；#include #include 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 18 页 - - - - - - - - - typedef struct LNode int data; struct LNode *next; LNode; /创

6、建一个带头结点的长度长度长度为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; /插入元素操作：将新元素x 插入到单链表L 中第 i名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精

7、心整理 - - - - - - - 第 5 页，共 18 页 - - - - - - - - - 个元素之后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);/ 找到位置名师资

8、料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 18 页 - - - - - - - - - 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-nex

9、t; void print(LNode *&L) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 18 页 - - - - - - - - - LNode *p; p=L-next; while(p!=NULL) coutdatanext; void main() LNode * L,*p;/ 节点为 L int i,x,y,s,n;/i 插入位置， X 插入元素， y 为删除元素，n 表长coutn; createlist(L,n); cout输出插入之前： ; pri

10、nt(L); couti; coutx; insert(L,i,x); cout输出插入后： ; print(L); couty; deleted(L,y);/删除元素操作：删除单链表中值为y的元素；cout输出删除后： ; print(L); 三、在顺序栈上实现将非负十进制数转换成二进制数#include #include 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 18 页 - - - - - - - - - #define MAX 100 /在顺序栈上实现将非负

11、十进制数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-; coutt; void main() int x,t; cout请输入你要转换的非负十进制数x:x; cout输出转换后的二进制数 :; conversion(x); coutendl; 四、在顺序表中采用顺序查找算法和折半查找算法寻找关键字 X 在顺序表中的位置。#include #include #define MAX 100 /在顺序

12、表中采用顺序查找算法和折半查找算法寻找关键字 X 在顺序表中的位置typedef struct int dataMAX; int length; sqlist; void init(sqlist &a)/ 线性表初始化 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 18 页 - - - - - - - - - a.length=0; void insert(sqlist &a ,int i,int x)/ 插入元素操作 int j; if(ia.length+1|a.

13、length=100) ; else for(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)/ 折半查找算名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精

14、心整理 - - - - - - - 第 12 页，共 18 页 - - - - - - - - - 法 int mid; while(lowx) high=mid-1; else if(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 个数: ; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - -

15、 - - 第 13 页，共 18 页 - - - - - - - - - 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; couten

16、dl; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 18 页 - - - - - - - - - cout 关 键 字 y 在 顺 序 表 中 的 位 置 为hsearch(sq,1,sq.length,y)+1endl; 五、将无序数列使用直接插入排序算法和快速排序算法将其排成递增有序数列。#include #include #define MAX 100 /将无序数列使用直接插入排序算法和快速排序算法将其排成递增有序数列typedef struct int da

17、taMAX; int length; sqlist; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 18 页 - - - - - - - - - void init(sqlist &a)/ 线性表初始化 a.length=0; void insert(sqlist &a ,int i,int x)/ 插入元素 ,构造无序数列 int j; if(ia.length+1|a.length=100) ; else for(j=a.length+1;ji;j-) a.dat

18、aj=a.dataj-1; a.dataj=x; a.length+; void insertsort(sqlist &sq)/直接插入排序算法 int i ,j ; for(i=2;i=sq.length;i+) if(sq.dataisq.datai-1) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 18 页 - - - - - - - - - sq.data0=sq.datai; sq.datai=sq.datai-1; for(j=i-2;sq.data0s

19、q.datai-1;j-) sq.dataj+1=sq.dataj; sq.dataj+1=sq.data0; void main() sqlist sq;/线性表为 sq int i,e,x,n;/n 表长init(sq);/ 构造一个空表coutn; cout输入表长为n 个数: ; for(i=0;ie; insert(sq,i,e);/ 插入元素 ,构造无序数列 cout无序数列为 :endl; for(i=0;isq.length ;i+) coutsq.datai ; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 18 页 - - - - - - - - - coutendl; insertsort(sq); cout直接插入排序后数列为 :endl; for(i=0;isq.length ;i+) coutsq.datai ; coutendl; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 18 页 - - - - - - - - -