考研算法题集锦.docx
《考研算法题集锦.docx》由会员分享，可在线阅读，更多相关《考研算法题集锦.docx（19页珍藏版）》请在冰点文库上搜索。
考研算法题集锦
苏州市职业大学20─20学年第学期试卷
标准答案及评分标准
《》
（集中/分散A/B卷开/闭卷笔试/上机）
一、算法设计题
1.设二叉树bt采用二叉链表结构存储。
试设计一个算法输出二叉树中所有非叶子结点，并求出非叶子结点的个数。
【答案】
intcount=0;
voidalgo2（BTNode*bt）{
if（bt）{
if（bt->lchild||bt->rchild）{
printf（bt->data）;
count++;
}
algo2（bt->lchild）;
algo2（bt->rchild）;
}
}
2.阅读下列函数arrange（）
intarrange（inta[],int1,inth,intx）
{//1和h分别为数据区的下界和上界
inti,j,t；
i=1；j=h；
while（iwhile（i=x）j--；
while（i=x）i++；
if（i{t=a[j]；a[j]=a[i]；a[i]=t；}
}
if（a[i]elsereturni－1；
}
（1）写出该函数的功能；
（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&&jq=p;p=p->next;j++;
}
s=（LNode*）malloc（sizeof（Lnode））;
s->data=y;
q->next=s;
s->next=q;
}
4.二叉排序树的类型定义如下：
typedefstructBSTNode{∥二叉排序树的结点结构
intdata;∥数据域
structBSTNode*lchild,*rchild;∥左、右孩子指针
}BSTNode,*BSTree;
设计递归算法，统计一棵二叉排序树T中值小于a的结点个数。
【答案】
intf34（BSTreeroot）
{
intcount;
BSTNode*p;
p=root;
if（p&&p->dataf34（p->lchild）;
returncount;
}
5.设二叉树T采用二叉链表结构存储，试设计算法求出二叉树中离根最近的第一个叶子结点。
（注：
结点按从上往下，自左
至右次序编号）
【答案】
BTNode*Firstleaf（BTNode*bt）
{InitQueue（Q）;//初始化队列Q
if（bt）{
EnQueue（Q,bt）;;
while（!
EmptyQueue（Q））{
DeQueue（Q,p）;
if（!
p->lchild&&!
p->rchild）returnp;
if（p->lchild）EnQueue（Q,p->lchild）;
if（p->rchild）EnQueue（Q,p->rchild）;
}
}
}
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【答案】
intalgo1（LNode*ha,LNode*hb,inti）{
for（p=hb;p->next;p=p->next）;
for（j=1,q=ha;jnext;
p->next=q->next;
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;is=（BTNode*）malloc（sizeof（BTNode））;
s->data=T[i].data;
s->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->next;
while（p->next）{
if（p->datanext->data）p=p->next;
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;
h->next=p=（LNode*）malloc（sizeof（Lnode））;
p->next=q=（LNode*）malloc（sizeof（Lnode））;
p->data=q->data=1;
for（i=3;i<=n;i++）{
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）{
if（bt->data>=’a’&&bt->data<=’z’）
bt->data-=32;
algo2（bt->lchild）;
algo2（bt->rchild）;
}
}
12.假设线性表以带表头结点的循环单链表表示。
试设计一个算法，在线性表的第k个元素前插入新元素y。
假如表长小于k，则插在表尾。
【答案】
voidInsertlist（LNode*h,intk,ElemTypey）
{
q=h;P=h->next;j=1;
while（p!
=h&&jq=p;p=p->next;j++;
}
s=（LNode*）malloc（sizeof（Lnode））;
s->data=y;
q->next=s;
s->next=q;
}
13.有一带表头结点的单链表，其结点的元素值以非递减有序排列，编写一个算法在该链表中插入一个元素x，使得插入后的单链表仍有序。
【答案】
voidalgo1（LNode*H,ElemTpx）
{
s=（LNode*）malloc（sizeof（LNode））;
s->data=x;
q=H;p=H->next;
while（p&&p->data<=x）
{
q=p;p=p->next;
}
s->next=p;q->next=s;
}
14.二叉排序树的类型定义如下：
typedefstructBSTNode{∥二叉排序树的结点结构
intdata;∥数据域
structBSTNode*lchild,*rchild;∥左、右孩子指针
}BSTNode,*BSTree;
设计递归算法，统计一棵二叉排序树T中值小于a的结点个数。
【答案】
intf34（BSTreeroot）
{
intcount;
BSTNode*p;
p=root;
if（p&&p->dataf34（p->lchild）;
returncount;
}
15.有一带表头结点的单链表，其结点的data域的类型为字符型，编写一个算法删除该链表中的数字字符。
【答案】
voidDel_digit（LNode*h）{
for（p=h;p->next;）{
q=p->next;
if（q->data>=’0’&&q->data<=’9’）
{p->next=q->next;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）{
if（（bt->lchild&&bt->rchild）&&（bt->lchild->data>bt->rchild->data））{
x=bt->lchild;
bt->lchild=bt->rchild;
bt->rchild=x;
}
algo2（bt->lchild）;
algo2（bt->rchild）;
}
}
18.设二叉树T采用二叉链表结构存储，试设计算法求出二叉树的深度。
【答案】
intDeep（BTNode*bt）{
if（bt==NULL）return0;
left=Deep（bt->lchild）;
right=Deep（bt->rchild）;
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）
{
initStack（s）;//初始化栈
while（n）
{k=n%8;
n=n/8;
push（s,k）;
}
while（EmptyStack（s））//判断栈是否为空
{pop（s,k）;
printf（“%d”,k）;
}
}
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->next;p->next;）{
q=p->next;
if（p->data==q->data）{
p->next=q->next;
free（q）;
}
elsep=q;
}
}
23.编写一个算法，判断带表头结点的单链表是否递增有序。
【答案】
intfun（LNode*h）
{p=h->next;
while（p->next）
{q=p->next;
if（q->data>p->data）return0;
p=q;
}
return1;
}
24.假设有两个带表头结点的单链表HA和HB，设计算法将单链表HB插入到单链表HA的第i（0【答案】
voidfun（LNode*ha,LNode*hb,inti）
{for（p=hb;p->next;p=p->next）;
for（j=1,q=ha;jq=q->next;;
p->next=q->next;
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）{
if（bt）{
if（bt->data>=’A’&&bt->data<=’Z’||bt->data>=’a’&&bt->data<=’z’）letter++;
if（bt->data>=’0’&&bt->data<=’9’）digit++;
algo2（bt->lchild）;
algo2（bt->rchild）;
}
}
27.假设以单链表表示线性表,单链表的类型定义如下:
typedefstructnode{
DataTypedata;
structnode*next;
}LinkNode,*LinkList;
编写算法,将一个头指针为head且不带头结点的单链表改造为一个含头结点且头指针仍为head的单向循环链表,并分析算法的时间复杂度。
【答案】
LinkListf34（LinkListhead）
{
LinkListp,s;
p=head;
while（p->next）p=p->next;
s=（LinkList）malloc（sizeof（LinkNode））;
s->next=head;
p->next=s;
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为全局变量*/
voidalgo2（BTNode*bt）{
if（bt）{
if（bt->data>=’A’&&bt->data<=’Z’）
count++;
algo2（bt->lchild）;
algo2（bt->rchild）;
}
}
30.假设带表头结点的双向循环链表定义如下：
typedefstructdunode{
chardata;
structdunode*prior,*next;
}DuNode;
现用该链表存放字符串，编写一个算法，判断该字符串是否中心对称关系。
例如字符串“xyzzyx”和“xyzyx”都是中心对称的。
【答案】
intfun（DuNode*h）
{p=h->next;q=h->prior;
while（p!
=q&&p->prior!
=q）
{
if（q->data==p->data）
{p=p->next;q=q->prior;}
elsereturn0;
}
return1;
}
31.假设以带头结点的单链表表示线性表，单链表的类型定义如下：
typedefintDataType;
typedefstructnode{
DataTypedata;
structnode*next;
}LinkNode,*LinkList;
编写算法，删除线性表中最大元素（假设最大值唯一存在）。
函数原型为：
voidf34（LinkListhead）;
【答案】
voidf34（LinkListhead）
{
inte;
LinkListp,q,s,spre;//s指向最大值的那个结点
spre=head;s=head->next;
q=s;p=s->next;
while（p）
{
if（s->datadata）
{s=p;spre=q;}
q=p;
p=p->next;
}
e=s->data;
spre->next=s->next;
free（s）;
}
升级会员 