数据结构上机试题.docx

数据结构上机试题一、顺序表的操作
(1) 插入元素操作：将新元素X插入到顺序表a中第 i个位置。
(2) 删除元素操作：删除顺序表a中第i个元素。
#include<iostream.h>#include<stdlib.h>#defineMAX100;typedef struct {
int datafl 00];
int length;}sqlist;void init(sqlist &a)〃线性表初始化(
a.lcngth=0;}void insert(sqlist &a jnt i,int x)// 插入元素操作{
int j;
if(i<01 | i>a.length+l | | a.length==100)
else{
cout«n请输入插入的位置i： n;
cin>>i;
cout«n请输入插入的元素x: ”；
cin>>x;
insert(L,i,x);
cout«"输出插入后：”；
print(L);
cout«n请输入删除的元素y：
cin>>y;
deleted(L,y);〃删除元素操作：删除单链表中值为y 的元素；
cout<< ”输出删除后：”;
print(L);}Bl •C:\DOCUIENTS AND SETTI»GS\ADIINISTRATOR\桌面\ 111111 \Debug\ 111111. exeM

Bl •C:\DOCUIENTS AND SETTI»GS\ADIINISTRATOR\桌面\ 111111 \Debug\ 111111. exeM
12 3 4 5 6 元元元元元; 6个个个个个个
12 3 4 5 6
3
4
5
6 素99
— 元 6 — n表表表表表表之入后后 长链链链链槌链入插入除 交入入入入入插入插删 人出
3 9
9 尸4 兀 5X
2
4
5
9
9
6
2 1请输入插入的位置2
2 1请输入删除的元素9： 3
1 Press any key to continue
X三、在顺序栈上实现将非负十进制数转换成二进制数#includc<iostrcam.h>#include<stdlib.h>
#define MAX 100〃在顺序栈上实现将非负十进制数X转换成二进制数 void conversion(int &x){
int stack [MAX];
int top=-l;
int t;
while (x)
{stack [++top]=x%2;x=x/2;
}
while(top!=-l)
{t=stack[top—];cout<<t;
}}void main。
int x,t; coutVV”请输入你要转换的非负十进制数x:H«endl; cin>>x;
cout<< ”输出转换后的二进制数:”； conversion(x);
cout<<endl;SI •C:\DOCUMEITS AND SETT IMG SXADIIMISTRATOR '桌面\qqq\Debug\qqq.exe'-OX
四、在顺序表中采用顺序查找算法和折半查找算法寻 找关键字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+l | | a.length==100)
else{
for(j=a.length+l;j>i;j—)a.data[j]=a. data [j -1 ];
a.data[j]=x;
a.lcngth++;
}}int search(sqlist &sq,int x)〃顺序查找算法{
int i;
for(i=0;iVsq.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-l;else if(sq.data[mid] <x)low=mid+l;
}}void main。
{
sqlist sq;//线性表为 sqint i,e,x,y,n;//i插入位置，x,y要查找元素，n表长 init(sq);//构造一个空表
coutvv”输入表长n:H；
cin>>n;
cout«H输入表长为H«n«n个数：”； for(i=0;i<n;i++)
{
cin>>e;
insert(sq,i,e);
}
cout«H查找前(便于判断)：!，«endl;
for(i=0;i<sq.length ;i++)
cout<<sq.datap] <<n
cout<<endl;
cout«H采用顺序查找算法：”v Vendl;
cout<<endl;
cout<<H输入要查找元素关键字x ”；
cin>>x;
cout<<endl;
cout«n关键字H«X«H在顺序表中的位置为H«search(sq,x)+l«endl; //下表从 0 开始,+1 显示时, 转化成从1开始了
coutVV”采用折半查找算法：H«endl;
cout<<endl;
cout«H输入要查找元素关键字y n;
cin>>y;
cout<<endl;
cout«n关键字n«y«n在顺序表中的位置为H < <hsearch (sq,l ,sq.length,y)+1 < <endl;
Si •C:\DOCUMEKTS AW) SETTIHGS\ADIINISTRATOR\^®\qqq\Debug\qqq. exe
..n ：10输入表长为 10 个数：36 35 29 64 1 85 66 48 25 14 羞找俞（便于判断）:
36 35 29 64 1 85 66 48 25 14采用顺序查找算法：
输入要查找元素关键字x 64关键字64在顺匠表中的位置为4采用折半查找算法：
输入要查找元素关键字' 64关键字64在顺序表中的何置为4Press any key to continue五、将无序数列使用直接插入排序算法和快速排序算
法将其排成递增有序数列。
#include<iostream.h> #include<stdlib.h> #dcfine MAX 100〃将无序数列使用直接插入排序算法和快速排序算法将其排成递增有序数列typedef struct
in t data [MAX];
int length;}sqlist;void init(sqlist &a)〃线性表初始化{
a.lcngth=0;}void insert(sqlist &a ,int ijnt x)// 插入元素，构造无序数 列{
int j;
if(i<01 | i>a.length+l | | a.length==100).
clsc{
fbr(j=a.length+1 ;j >i;j—)a.data [j]=a.data[j-l];
a.data[j]=x;
a.length++；
}}〃将哨兵放在a.data[n]中，被排序的记录放在 a.data[O..n-l]中，直接插入排序算法。
void insertsort(sqlist &a)〃直接插入排序算法 {
int i,j;
int n=a.length; for(i=n-2;i>=0;i—)if(a.data[i]>a.data[i+l]){a.datafn]=a.data[i];//a.data[n]是口 肖兵 j=i+l；
do{a.data[j-l]=a.data[j]; j++;
} while(a.data[j] <a.data[nj); a.data[j-l]=a.data[n];}}int Partition(sqlist &a,int i,int j) {
int pivot=a.data[i];
while (i<j)
for(j=a.lcngth+1 ;j >i;j—)a. data [j]=a. data [j -1 ];
a.data[j]=x;
a.length++；
}}void dcleted(sqlist &a jnt i)// 删除元素操作{
int j;
if(ivO&&i>a. length)
else
{fbr(j 二 i;j v a.length;j++)a.data[j]=a.data[j+1];a.length—;
}}void mainQ(
sqlist a;〃线性表为a
int i,e,x,n,j,s;〃i插入位置，e动态建线性表要用，X插 while (i <j &&a.data [j] >=pivot)
j--; if(i<j)
a.data[i++]=a.data[j]; while(i<j&&a.data[i]<=pivot)i++；if(i<j)a.data [j—]=a.data [i];
}
a.data [i]=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 mainQ
sqlist sql,sq2;//线性表为 sql ,sq2
int i,e,x,nl ,n2;//n 表长 init(sql);//构造一个空表 coutVV”输入表长nl: n； cin>>nl;
cout«H输入表长为”vvnl<v”个数：七 for(i=0;i<nl;i++)
{
cin>>e;
insert(sql,i,e);〃插入元素,构造无序数列 } cout«"无序数列为:"«endl; for(i=0;i<sql .length ;i++)
cout<<sql .data[i] <<M
cout<<endl;
insertsort(sql);
coutvv”直接插入排序后数列为:” v Vendl; for(i=O;i<sql .length ;i++)
cout<<sql.data[i]<<n
cout<<endl;
cout<<endl;
cout<<endl;
init(sq2);//构造一个空表
cout<<H输入表长n2: n；
cin>>n2;
cout«H输入表长为H«n2«n个数：七
for(i=0;i<n2;i++)
{
cin>>e;
insert(sq2,i,e);〃插入元素,构造无序数列 }
cout«n无序数列为:H«endl;
for(i=0;i<sq2.1ength ;i++)
cout<<sq2.data[i] <<n
cout<<endl;
QuickSort(sq2,0, n2-l);
cout<<”快速排序后数列为:"<<endl;
for(i=0;i<sq2.1ength ;i++)
cout<<sq2.data[i]<<M
cout<<endl;四 *C: \Progra> Files\licrosoft Visual StudioMyProjects\l 111111111 l\Debu... - [□ X输入表长nl： 5输入表长有5个数：1 9 3 5 7 无序教列为：
1 9 3 5 7直接插入排序后数列为：
1 3 5 7 9费入表长n2：10输入表长为10 个数：1 3 296 34 26 57 2 18 66 14 无序薮列为：
1 3 296 34 26 57 2 18 66 14快速排序后数列为：
1 2 3 14 18 26 34 57 66 296Press any key to continue.
如有侵权请联系告知删除，感谢你们的配合!
入元素，n表长
init(a);//构造一个空表
cout<<H输入表长n: ”；
cin>>n;coutvv”输入表长为“vvnvv”个数：”； for(j=O;j<n;++j)
{
cin>>e;
insert(a,j,e);
}
COUtVV” 插入前：”；
for(j=0;j<a.length ;j++)
cout<<a.data[j] <<M
coutVV”输入要插入位置i:”；
cin>>i;
cout<<H输入要插入的元素x:H；
cin>>x;
coutvv”打算在第yvivv”个位置插入元素H«x ; insert(a,i-l,x);〃由于从0开始，要构造显示从一开始, 所以减1
cout«"插入后结果："；
for(j=O;j < a.length;j + +)
cout<<a.data[j] <<n
COUtVV”输入要删除的位置s:
cin>>s;
deleted(a,s-l);//由于从0开始，要构造显示从一开始, 所以减1
coutvv”删除后结果：”
for(j=0;j <a.length;j + +)
cout<<a.data[j] <<H
MM JA J XXXV AZ A A XJR\7AA \/AV \7TCB>M 'AAAAAAA\ AAAAAAA. <7 A G输/\表长n ：5输入表长为5个数：1 2 3 4 5指入俞：1 2 3 4 5输入要插入位置i：2
葡入要捶入的元素x：8打字在第2个位置插入元素8插入后结果：1 8 2 3 4 5输入要删除的位置s：3lllll
"III

lllll
"III
飘|除后结果：1 8 3 4 5 Press any key to continue二、单链表的操作
(1) 创建一个带头结点的单链表；
(2) 插入元素操作：将新元素x插入到单链表中第i 个元素之后；
(3) 删除元素操作：删除单链表中值为x的元素；#include<iostream.h>#include < s tdlib. h >typedef struct LN ode
int data;
struct LN ode *next;} LN ode;〃创建一个带头结点的长度长度长度为n的链表
L；void createlist(LNode *&L ,int n){
int i;
LN ode *p;
L= (LNode *)malloc(sizeof(LNode));
L->next = NULL;
for(i=l;i<=n;i++)
{p=(LNode *)malloc(sizcof(LNode));cout<< ”请输入链表第”<<i<< ”个元素"；cin>>p->data; p->next=L->next;
L->next=p;〃插入元素操作：将新元素X插入到单链表L中第i个元素之后void insert(LNodc *&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->ncxt=p->ncxt;
p->next=q;break;}p=p->next;
}
if(p->next 二二NULL) q=(LNodc *)malioc(sizeof(LNode));//找到位置 q->data=x;〃放入数据 q->next=p->next;p->next=q;}}
〃删除元素操作：删除单链表中值为X的元素；void deleted (LN ode *&L ,int x){
LN ode *p,*q；
p 二 L;
while(p->next!=N ULL)
{if(p->next->data==x){q=p->next;
p->next=p->next->next;free(q);}
p=p->next;
}}void print(LNode *&L)
LN ode *p;
p=L->next;
while(p!=NULL)
{
cout<<p->data<<H H; p=p->next;
}}void main。
{
LNodc * L,*p;〃节点为 L
int i,x,y,s,n;//i插入位置，X插入元素，y为删除元 素，n表长
coutvv”输入表长n:H；
cin>>n;
createlist(L?n);
coutvv”输出插入之前：”；
print(L);