数据结构算法设计题复习题Word文件下载.doc
《数据结构算法设计题复习题Word文件下载.doc》由会员分享,可在线阅读,更多相关《数据结构算法设计题复习题Word文件下载.doc(11页珍藏版)》请在冰点文库上搜索。
(2)写一个调用上述函数实现下列功能的算法:
对一整型数组b[n]中的元素进行重新排列,将所有负数均调整到数组的低下标端,将所有正数均调整到数组的高下标端,若有零值,则置于两者之间,并返回数组中零元素的个
数。
(1)该函数的功能是:
调整整数数组a[]中的元素并返回分界值i,使所有<x的元素均落在a[1..i]上,使所有≥x的元素均落在a[i+1..h]上。
(2)intf(intb[],intn)或intf(intb[],intn)
{{
intp,q;
intp,q;
p=arrange(b,0,n-1,0);
p=arrange(b,0,n-1,1);
q=arrange(b,p+1,n-1,1);
q=arrange(b,0,p,0);
returnq-p;
returnp-q;
}}
3.假设线性表以带表头结点的循环单链表表示。
试设计一个算法,在线性表的第k个元素前插入新元素y。
假如表长小于k,则插在表尾。
voidalgo1(LNode*h,intk,ElemTypey){
q=h;
P=h->
next;
j=1;
while(p!
=h&
j<
k){
q=p;
p=p->
j++;
s=(LNode*)malloc(sizeof(Lnode));
s->
data=y;
q->
next=s;
next=q;
}
4.二叉排序树的类型定义如下:
typedefstructBSTNode{∥二叉排序树的结点结构
intdata;
∥数据域
structBSTNode*lchild,*rchild;
∥左、右孩子指针
}BSTNode,*BSTree;
设计递归算法,统计一棵二叉排序树T中值小于a的结点个数。
intf34(BSTreeroot)
{
intcount;
BSTNode*p;
p=root;
if(p&
p->
data<
a)count++;
f34(p->
returncount;
5.设二叉树T采用二叉链表结构存储,试设计算法求出二叉树中离根最近的第一个叶子结点。
(注:
结点按从上往下,自左
至右次序编号)
BTNode*Firstleaf(BTNode*bt)
{InitQueue(Q);
//初始化队列Q
if(bt){
EnQueue(Q,bt);
;
while(!
EmptyQueue(Q)){
DeQueue(Q,p);
if(!
p->
lchild&
!
rchild)returnp;
if(p->
lchild)EnQueue(Q,p->
rchild)EnQueue(Q,p->
}
6.已知一棵具有n个结点的完全二叉树被顺序存储在一维数组中,结点为字符类型,编写算法打印出编号为k的结点的双亲和孩子结点。
intalgo2(charbt[],intn,intk){
if(k<
1||k>
n)return0;
if(k==1)printf(“%cisaroot\n”,bt[1]);
elseprintf(“%c’sparentis%c\n”,bt[k],bt[k/2]);
if(2*k<
=n)printf(“%c’slchildis%c\n”,bt[k],bt[2*k]);
elseprintf(“%cisnotlchild\n”,bt[k]));
if(2*k+1<
=n)printf(“%c’srchildis%c\n”,bt[k],bt[2*k+1]);
elseprintf(“%cisnotrchild\n”,bt[k]));
return1;
7.编写算法,将非空单链表hb插入到单链表ha的第i(0<
i≤表长)个结点前。
intalgo1(LNode*ha,LNode*hb,inti){
for(p=hb;
next);
for(j=1,q=ha;
j<
i;
j++)q=q->
p->
next=q->
q->
next=hb->
next;
free(hb);
8.设二叉树T已按完全二叉树的形式存储在顺序表T中,试设计算法根据顺序表T建立该二叉树的二叉链表结构。
顺序表T定义如下:
structtree{
intno;
/*结点按完全二叉树的编号*/
ElEMTPdata;
/*数据域*/
}T[N];
/*N为二叉树T的结点数*/
BTNode*creat_tree(structtreeT[N])
{BTNode*p[MAX];
t=NULL;
for(i=0;
i<
N;
i++){
s=(BTNode*)malloc(sizeof(BTNode));
s->
data=T[i].data;
lchild=s->
rchild=NULL;
m=T[i].no;
p[m]=s;
if(m==1)t=s;
else{j=m/2;
if(m%2==0)p[j]->
lchild=s;
elsep[j]->
rchild=s;
}//slse
}//for
returnt;
}//creat_tree
9.编写算法判断带表头结点的单链表L是否是递增的。
若递增返回1,否则返回0。
intalgo1(LNode*L)
{
if(!
L->
next)return1;
p=L->
while(p->
next){
if(p->
data<
p->
next->
data)p=p->
elsereturn0;
return1;
10.假设一线性表由Fibonacci数列的前n(n≥3)项构成,试以带表头结点的单链表作该线性表的存储结构,设计算法建立该单链表,且将项数n存储在表头结点中。
Fibonacci数列根据下式求得:
1(n=1)
f(n)=1(n=2)
f(n-2)+f(n-1)(n≥3)
LNode*Creatlist(LNode*h,intn){
h=(LNode*)malloc(sizeof(Lnode));
h->
data=n;
next=p=(LNode*)malloc(sizeof(Lnode));
p->
next=q=(LNode*)malloc(sizeof(Lnode));
data=q->
data=1;
for(i=3;
=n;
q->
next=s=(LNode*)malloc(sizeof(Lnode));
s->
data=p->
data+q->
data;
s->
next=NULL;
p=q;
q=s;
}
returnh;
11.设二叉树T采用二叉链表结构存储,数据元素为字符类型。
设计算法将二叉链表中所有data域为小写字母的结点改为大写
字母。
voidalgo2(BTNode*bt){
if(bt->
data>
=’a’&
bt->
=’z’)
bt->
data-=32;
12.假设线性表以带表头结点的循环单链表表示。
voidInsertlist(LNode*h,intk,ElemTypey)
q=h;
while(p!
q=p;
s->
q->
13.有一带表头结点的单链表,其结点的元素值以非递减有序排列,编写一个算法在该链表中插入一个元素x,使得插入后的单链表仍有序。
voidalgo1(LNode*H,ElemTpx)
{
s=(LNode*)malloc(sizeof(LNode));
data=x;
q=H;
p=H->
while(p&
=x)
q=p;
next=p;
q->
14.二叉排序树的类型定义如下:
15.有一带表头结点的单链表,其结点的data域的类型为字符型,编写一个算法删除该链表中的数字字符。
voidDel_digit(LNode*h){
for(p=h;
){
q=p->
if(q->
=’0’&
=’9’)
{p->
free(q);
}
elsep=q;
}
}
16.利用栈的基本运算,编写一个算法,实现将整数转换成二进制数输出。
voidreturnDtoO(intnum)
initStack(s);
while(n)
{k=n%2;
n=n/2;
push(s,k);
while(EmptyStack(s))
{pop(s,k);
printf(“%d”,k);
17.设二叉树T采用二叉链表结构存储,数据元素为int型,试设计一个算法,若结点左孩子的data域的值大于右孩子的data域的值,则交换其左、右子树。
voidalgo2(bitreptrbt){
bitreptrx;
if((bt->
lchild&
rchild)&
(bt->
lchild->
rchild->
data)){
x=bt->
lchild;
bt->
lchild=bt->
rchild;
rchild=x;
}
18.设二叉树T采用二叉链表结构存储,试设计算法求出二叉树的深度。
intDeep(BTNode*bt){
if(bt==NULL)return0;
left=Deep(bt->
right=Deep(bt->
return(left>
right?
left:
right)+1;
19.设给定的哈希表存储空间为H(0~M-1),哈希函数的构造方法为“除留余数法”,处理冲突的方法为“线性探测法”,设计算法将元素e填入到哈希表中。
voidhash-insert(hashTableh[],intm,ElemTypee){
j=e%p;
if(h[j]!
=NULL)h[j]=e;
else{
do
{j=(j+1)%m;
}while(h[j]!
=NULL);
h[j]=e;
}
20.对于给定的十进制正整数,打印出对应的八进制正整数。
(利用栈)
voidDecToOct(intnum)
//初始化栈
{k=n%8;
n=n/8;
while(EmptyStack(s))//判断栈是否为空
21.一个正读和反读都相同的字符序列称为“回文”。
例如“abcba”和“1221”是回文,而“abcde”不是回文。
试写一个算法,要求利用栈的基本运算识别一个以@为结束符的字符序列是否是回文。
intPair(char*str){
InitStack(s);
p=str
for(;
*p!
=’@’;
p++)
Push(s,*p);
while(StackEmpty(s)){
Pop(s,y);
if(y!
=*str++)return0;
return1;
22.有一带表头结点的单链表,其结点的元素值以非递减有序排列,编写一个算法删除该链表中多余的元素值相同的结点(值相同的结点只保留一个)。
voidDelsame(LNode*h){
if(h->
next){
for(p=h->
q=p->
if(p->
data==q->
data){
p->
free(q);
elsep=q;
23.编写一个算法,判断带表头结点的单链表是否递增有序。
intfun(LNode*h)
{p=h->
while(p->
next)
{q=p->
next;
if(q->
data)return0;
p=q;
return1;
}
24.假设有两个带表头结点的单链表HA和HB,设计算法将单链表HB插入到单链表HA的第i(0<
voidfun(LNode*ha,LNode*hb,inti)
{for(p=hb;
for(j=1,q=ha;
j++)
q=q->
;
p->
q->
next=hb->
next;
free(hb);
25.假设以带头结点的单链表表示有序表,单链表的类型定义如下:
typedefstructnode{
DataTypedata;
structnode*next
}LinkNode,*LinkList;
编写算法,从有序表A中删除所有和有序表B中元素相同的结点。
(空)
26.设二叉树T采用二叉链表结构存储,数据元素为字符类型。
设计算法分别求出二叉链表中data域为英文字母和数字字符的
结点个数。
intletter=0,digit=0;
/*全局变量*/
voidalgo2(BTNode*bt){
=’A’&
=’Z’||bt->
=’z’)letter++;
=’9’)digit++;
27.假设以单链表表示线性表,单链表的类型定义如下:
typedefstructnode{
DataTypedata;
structnode*next;
}LinkNode,*LinkList;
编写算法,将一个头指针为head且不带头结点的单链表改造为一个含头结点且头指针仍为head的单向循环链表,并分析算法的时间复杂度。
LinkListf34(LinkListhead)
{
LinkListp,s;
p=head;
while(p->
next)p=p->
s=(LinkList)malloc(sizeof(LinkNode));
next=head;
head=s;
returnhead;
}
时间复杂度为:
O(n)
28.假设有向图以邻接表方式存储,编写一个算法判别顶点vi到顶点vj是否存在弧。
intIsArcs(ALgraphG,inti,intj){
/*判断有向图G中顶点i到顶点j是否有弧,是则返回1,否则返回0*/
p=G[i].firstarc;
while(p!
=NULL){
if(p->
adjvex==j)
return1;
p=p->
nextarc;
}
return0;
29.设二叉树T采用二叉链表结构存储,数据元素为字符类型。
设计算法求出二叉链表中data域为大写字母的结点个数。
intcount=0;
/*count为全局变量*/
=’Z’)
count++;
30.假设带表头结点的双向循环链表定义如下:
typedefstructdunode{
chardata;
structdunode*prior,*next;
}DuNod