C语言数据结构编程题探素Word格式.docx
《C语言数据结构编程题探素Word格式.docx》由会员分享，可在线阅读，更多相关《C语言数据结构编程题探素Word格式.docx（25页珍藏版）》请在冰点文库上搜索。
returntotal/n;
}
find（0,0）;
3、递归实现回文判断（如：
abcdedbca就是回文，判断一个面试者对递归理解的简单程序）
intfind（char*str,intn）{
if（n<
=1）return1;
elseif（str[0]==str[n-1]）returnfind（str+1,n-2）;
elsereturn0;
char*str="
abcdedcba"
;
%s:
%s\n"
str,find（str,strlen（str））?
"
Yes"
:
No"
）;
4、组合问题（从M个不同字符中任取N个字符的所有组合）
voidfind（char*source,char*result,intn）{
if（n==1）{
while（*source）
%s%c\n"
result,*source++）;
inti,j;
for（i=0;
source[i]!
=0;
i++）;
for（j=0;
result[j]!
j++）;
for（;
i>
=n;
i--）{
result[j]=*source++;
result[j+1]='
\0'
find（source,result,n-1）;
}
intconstn=3;
char*source="
ABCDE"
result[n+1]={0};
0&
&
strlen（source）>
n<
=strlen（source））
find（source,result,3）;
5、分解成质因数（如435234=251*17*17*3*2，据说是华为笔试题）
voidprim（intm,intn）{
if（m>
n）{
while（m%n!
=0）n++;
m/=n;
prim（m,n）;
%d*"
intn=435234;
%d="
prim（n,2）;
6、寻找迷宫的一条出路，o：
通路；
X：
障碍。
（大家经常谈到的一个小算法题）
#defineMAX_SIZE8
intH[4]={0,1,0,-1};
intV[4]={-1,0,1,0};
charMaze[MAX_SIZE][MAX_SIZE]={{'
X'
'
},
{'
o'
{'
{'
{'
{'
}};
voidFindPath（intX,intY）{
if（X==MAX_SIZE||Y==MAX_SIZE）{
for（inti=0;
i<
MAX_SIZE;
for（intj=0;
j<
j++）
%c%c"
Maze[i][j],j<
MAX_SIZE-1?
'
\n'
}elsefor（intk=0;
k<
4;
k++）
if（X>
=0&
Y>
Y<
MAX_SIZE&
X<
==Maze[X][Y]）{
Maze[X][Y]='
FindPath（X+V[k],Y+H[k]）;
Maze[X][Y]='
FindPath（1,0）;
7、随机分配座位，共50个学生，使学号相邻的同学座位不能相邻（早些时候用C#写的，没有
用C改写）。
staticvoidMain（string[]args）
{
intTmp=0,Count=50;
int[]Seats=newint[Count];
bool[]Students=newbool[Count];
System.RandomRandStudent=newSystem.Random（）;
Students[Seats[0]=RandStudent.Next（0,Count）]=true;
for（inti=1;
Count;
）{
Tmp=（int）RandStudent.Next（0,Count）;
if（（!
Students[Tmp]）&
（Seats[i-1]-Tmp!
=1）&
（Seats[i-1]-Tmp）!
=-1）{
Seats[i++]=Tmp;
Students[Tmp]=true;
foreach（intStudentinSeats）
System.Console.Write（Student+"
System.Console.Read（）;
8、求网格中的黑点分布。
现有6*7的网格，在某些格子中有黑点，已知各行与各列中有黑点
的点数之和，请在这张网格中画出黑点的位置。
（这是一网友提出的题目，说是他笔试时遇
到算法题）
#defineROWS6
#defineCOLS7
intiPointsR[ROWS]={2,0,4,3,4,0};
//各行黑点数和的情况
intiPointsC[COLS]={4,1,2,2,1,2,1};
//各列黑点数和的情况
intiCount,iFound;
intiSumR[ROWS],iSumC[COLS],Grid[ROWS][COLS];
intSet（intiRowNo）{
if（iRowNo==ROWS）{
for（intiColNo=0;
iColNo<
COLS&
iSumC[iColNo]==iPointsC[iColNo];
iCol
No++）
if（iColNo==COLS-1）{
\nNo.%d:
\n"
++iCount）;
ROWS;
for（intj=0;
COLS;
%d%c"
Grid[i][j],（j+1）%COLS?
iFound=1;
//iFound=1，有解
iColNo++）{
if（iPointsR[iRowNo]==0）{
Set（iRowNo+1）;
}elseif（Grid[iRowNo][iColNo]==0）{
Grid[iRowNo][iColNo]=1;
iSumR[iRowNo]++;
iSumC[iColNo]++;
if（iSumR[iRow
No]<
iPointsR[iRowNo]&
iSumC[iColNo]<
=iPointsC[iColNo]）
Set（iRowNo）;
elseif（iSumR[iRowNo]==iPointsR[iRowNo]&
iRowNo<
ROWS）
Grid[iRowNo][iColNo]=0;
iSumR[iRowNo]--;
iSumC[iColNo]--;
returniFound;
//用于判断是否有解
8、求网格中的黑点分布。
9、有4种面值的邮票很多枚，这4种邮票面值分别1,4,12,21，现从多张中最多任取5张进
行组合，求取出这些邮票的最大连续组合值。
（据说是华为2003年校园招聘笔试题）
#defineN5
#defineM5
intk,Found,Flag[N];
intStamp[M]={0,1,4,12,21};
//在剩余张数n中组合出面值和Value
intCombine（intn,intValue）{
if（n>
Value==0）{
Found=1;
intSum=0;
for（inti=0;
N&
Flag[i]!
i++）{
Sum+=Stamp[Flag[i]];
%d"
Stamp[Flag[i]]）;
\tSum=%d\n\n"
Sum）;
}elsefor（inti=1;
M&
!
Found&
n>
0;
if（Value-Stamp[i]>
Flag[k++]=i;
Combine（n-1,Value-Stamp[i]）;
Flag[--k]=0;
returnFound;
for（inti=1;
Combine（N,i）;
i++,Found=0）;
10、大整数数相乘的问题。
（这是2002年在一考研班上遇到的算法题）
voidMultiple（charA[],charB[],charC[]）{
intTMP,In=0,LenA=-1,LenB=-1;
while（A[++LenA]!
='
while（B[++LenB]!
intIndex,Start=LenA+LenB-1;
for（inti=LenB-1;
=0;
Index=Start--;
if（B[i]!
0'
）{
for（intIn=0,j=LenA-1;
j>
j--）{
TMP=（C[Index]-'
）+（A[j]-'
）*（B[i]-'
）+In;
C[Index--]=TMP%10+'
In=TMP/10;
C[Index]=In+'
}
charA[]="
21839244444444448880088888889"
charB[]="
38888888888899999999999999988"
charC[sizeof（A）+sizeof（B）-1];
for（intk=0;
k<
sizeof（C）;
k++）
C[k]='
C[sizeof（C）-1]='
Multiple（A,B,C）;
C[i]!
%c"
C[i]）;
11、求最大连续递增数字串（如“ads3sl456789DF3456ld345AA”中的“456789”）
intGetSubString（char*strSource,char*strResult）{
intiTmp=0,iHead=0,iMax=0;
for（intIndex=0,iLen=0;
strSource[Index];
Index++）{
if（strSource[Index]>
&
strSource[Index]<
9'
strSource[Index-1]>
strSource[Index]==strSource[Index-1]+1）{
iLen++;
//连续数字的长度增1
}else{//出现字符或不连续数字
if（iLen>
iMax）{
iMax=iLen;
iHead=iTmp;
//该字符是数字，但数字不连续
）{
iTmp=Index;
iLen=1;
for（iTmp=0;
iTmp<
iMax;
iTmp++）//将原字符串中最长的连续数字串赋值给结果
串
strResult[iTmp]=strSource[iHead++];
strResult[iTmp]='
returniMax;
//返回连续数字的最大长度
charstrSource[]="
ads3sl456789DF3456ld345AA"
charstrResult[sizeof（strSourc
e）];
printf（"
Len=%d,strResult=%s\nstrSource=%s\n"
GetSubString（strSource,strResult）,strResult,strSource）;
12、四个工人，四个任务，每个人做不同的任务需要的时间不同，求任务分配的最优方案。
（2005年5月29日全国计算机软件资格水平考试——软件设计师的算法题）。
#include"
stdafx.h"
#defineN4
intCost[N][N]={{2,12,5,32},//行号：
任务序号，列号：
工人序号
{8,15,7,11},//每行元素值表示这个任务由不同工人完成所需
要的时间
{24,18,9,6},
{21,1,8,28}};
intMinCost=1000;
intTask[N],TempTask[N],Worker[N];
voidAssign（intk,intcost）{
if（k==N）{
MinCost=cost;
N;
TempTask[i]=Task[i];
i++）{
if（Worker[i]==0&
cost+Cost[k][i]<
MinCost）{//为提高效率而进行剪枝
Worker[i]=1;
Task[k]=i;
Assign（k+1,cost+Cost[k][i]）;
Worker[i]=0;
Task[k]=0;
}
Assign（0,0）;
最佳方案总费用=%d\n"
MinCost）;
i++）/*输出最佳方案*/
\t任务%d由工人%d来做：
i,TempTask[i],Cost[i][TempTask[i]]）;
13、八皇后问题，输出了所有情况，不过有些结果只是旋转了90度而已。
（回溯算法的典型
例题，是数据结构书上算法的具体实现，大家都亲自动手写过这个程序吗？
）
#defineN8
intBoard[N][N];
intValid（inti,intj）{//判断下棋位置是否有效
intk=1;
for（k=1;
=k&
=k;
k++）
if（Board[i-k][j-k]）return0;
if（Board[i-k][j]）return0;
j+k<
if（Board[i-k][j+k]）return0;
return1;
voidTrial（inti,intn）{//寻找合适下棋位置
if（i==n）{
for（intk=0;
n;
k++）{
for（intm=0;
m<
m++）
printf（"
Board[k][m]）;
for（intj=0;
j<
j++）{
Board[i][j]=1;
if（Valid（i,j））
Trial（i+1,n）;
Board[i][j]=0;
Trial（0,N）;
14、实现strstr功能，即在父串中寻找子串首次出现的位置。
（笔试中常让面试者实现标准
库中的一些函数）
char*strstring（char*ParentString,char*SubString）{
char*pSubString,*pPareString;
for（char*pTmp=ParentString;
*pTmp;
pTmp++）{
pSubString=SubString;
pPareString=pTmp;
while（*pSubString==*pPareString&
*pSubString!
pSubString++;
pPareString
升级会员 