《C语言数据结构编程题.doc》由会员分享，可在线阅读，更多相关《C语言数据结构编程题.doc（17页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1、将一整数逆序后放入一数组中（要求递归实现）void convert(int *result, int n) if(n=10)convert(result+1, n/10);*result = n%10;int main(int argc, char* argv) int n = , result20=;convert(result, n);printf(%d:, n);for(int i=0; i= average)printf(%d:%dn, number, score);return average; else printf(Average=%dn, total/n);return t
2、otal/n;int main(int argc, char* argv) find(0, 0);3、递归实现回文判断（如：abcdedbca就是回文，判断一个面试者对递归理解的简单程序）int find(char *str, int n) if(n=n; i-) resultj = *source+;resultj+1 = 0;find(source, result, n-1);int main(int argc, char* argv) int const n = 3;char *source = ABCDE, resultn+1 = 0;if(n0 & strlen(source)0 &
3、 nn) while(m%n != 0) n+;m /= n;prim(m, n);printf(%d*, n);int main(int argc, char* argv) int n = ;printf(%d=, n);prim(n, 2);6、寻找迷宫的一条出路，o：通路； X：障碍。（大家经常谈到的一个小算法题）#define MAX_SIZE 8int H4 = 0, 1, 0, -1; int V4 = -1, 0, 1, 0; char MazeMAX_SIZEMAX_SIZE = X,X,X,X,X,X,X,X, o,o,o,o,o,X,X,X, X,o,X,X,o,o,o,X
4、, X,o,X,X,o,X,X,o, X,o,X,X,X,X,X,X,X,o,X,X,o,o,o,X, X,o,o,o,o,X,o,o, X,X,X,X,X,X,X,X;void FindPath(int X, int Y) if(X = MAX_SIZE | Y = MAX_SIZE) for(int i = 0; i MAX_SIZE; i+)for(int j = 0; j MAX_SIZE; j+) printf(%c%c, Mazeij, j MAX_SIZE-1 ? : n);else for(int k = 0; k = 0 & Y = 0 & Y MAX_SIZE & X MA
5、X_SIZE & o = MazeXY) MazeXY = ; FindPath(X+Vk, Y+Hk); MazeXY =o; int main(int argc, char* argv) FindPath(1,0);7、随机分配座位，共50个学生，使学号相邻的同学座位不能相邻(早些时候用C#写的，没有用C改写）。static void Main(string args)int Tmp = 0, Count = 50;int Seats = new intCount;bool Students = new boolCount;System.Random RandStudent=new Sys
6、tem.Random();StudentsSeats0=RandStudent.Next(0,Count)=true;for(int i = 1; i Count; ) Tmp=(int)RandStudent.Next(0,Count); if(!StudentsTmp)&(Seatsi-1-Tmp!=1) & (Seatsi-1 - Tmp) != -1) Seatsi+ = Tmp;StudentsTmp = true;foreach(int Student in Seats) System.Console.Write(Student + );System.Console.Read();
7、8、求网格中的黑点分布。现有6*7的网格，在某些格子中有黑点，已知各行与各列中有黑点的点数之和，请在这张网格中画出黑点的位置。（这是一网友提出的题目，说是他笔试时遇到算法题）#define ROWS 6#define COLS 7int iPointsRROWS = 2, 0, 4, 3, 4, 0; / 各行黑点数和的情况int iPointsCCOLS = 4, 1, 2, 2, 1, 2, 1; / 各列黑点数和的情况int iCount, iFound;int iSumRROWS, iSumCCOLS, GridROWSCOLS;int Set(int iRowNo) if(iRowN
8、o = ROWS) for(int iColNo=0; iColNo COLS & iSumCiColNo=iPointsCiColNo; iColNo+) if(iColNo = COLS-1) printf(nNo.%d:n, +iCount); for(int i=0; i ROWS; i+) for(int j=0; j COLS; j+) printf(%d%c, Gridij, (j+1) % COLS ? : n); iFound = 1;/ iFound = 1，有解 else for(int iColNo=0; iColNo COLS; iColNo+) if(iPoints
9、RiRowNo = 0) Set(iRowNo + 1); else if(GridiRowNoiColNo=0) GridiRowNoiColNo = 1; iSumRiRowNo+; iSumCiColNo+; if(iSumRiRowNoiPointsRiRowNo & iSumCiColNo=iPointsCiColNo) Set(iRowNo);else if(iSumRiRowNo=iPointsRiRowNo & iRowNo = 0 & Value = 0) Found = 1;int Sum = 0;for(int i=0; iN & Flagi != 0; i+) Sum
10、+= StampFlagi;printf(%d , StampFlagi);printf(tSum=%dnn, Sum);else for(int i=1; i0; i+)if(Value-Stampi = 0) Flagk+ = i;Combine(n-1, Value-Stampi);Flag-k = 0;return Found;int main(int argc, char* argv) for(int i=1; Combine(N, i); i+, Found=0);10、大整数数相乘的问题。（这是2002年在一考研班上遇到的算法题）void Multiple(char A, cha
11、r B, char C) int TMP, In=0, LenA=-1, LenB=-1; while(A+LenA != 0); while(B+LenB != 0); int Index, Start = LenA + LenB - 1; for(int i=LenB-1; i=0; i-) Index = Start-; if(Bi != 0) for(int In=0, j=LenA-1; j=0; j-) TMP = (CIndex-0) + (Aj-0) * (Bi - 0) + In; CIndex- = TMP % 10 + 0; In = TMP / 10; CIndex =
12、 In + 0; int main(int argc, char* argv) char A = ; char B = ;char Csizeof(A) + sizeof(B) - 1; for(int k=0; k= 0 & strSourceIndex 0 & strSourceIndex = strSourceIndex-1+1) iLen+; / 连续数字的长度增1 else / 出现字符或不连续数字 if(iLen iMax) iMax = iLen; iHead = iTmp; / 该字符是数字，但数字不连续 if(strSourceIndex = 0 & strSourceInd
13、ex = 9) iTmp = Index; iLen = 1; for(iTmp=0 ; iTmp iMax; iTmp+)/ 将原字符串中最长的连续数字串赋值给结果串 strResultiTmp = strSourceiHead+; strResultiTmp=0; return iMax;/ 返回连续数字的最大长度int main(int argc, char* argv) char strSource=ads3slDF3456ld345AA, char strResultsizeof(strSource);printf(Len=%d, strResult=%s nstrSource=%s
14、n, GetSubString(strSource, strResult), strResult, strSource);12、四个工人，四个任务，每个人做不同的任务需要的时间不同，求任务分配的最优方案。（2005年5月29日全国计算机软件资格水平考试软件设计师的算法题）。#include stdafx.h#define N 4intCostNN = 2, 12, 5, 32,/ 行号：任务序号，列号：工人序号 8, 15, 7, 11,/ 每行元素值表示这个任务由不同工人完成所需要的时间 24, 18, 9, 6, 21, 1, 8, 28;int MinCost=1000;int Task
15、N, TempTaskN, WorkerN;void Assign(int k, int cost) if(k = N) MinCost = cost;for(int i=0; iN; i+)TempTaski = Taski; else for(int i=0; iN; i+) if(Workeri=0 & cost+Costki MinCost) / 为提高效率而进行剪枝Workeri = 1;Taskk = i; Assign(k+1, cost+Costki); Workeri = 0; Taskk = 0;int main(int argc, char* argv) Assign(0
16、, 0);printf(最佳方案总费用=%dn, MinCost);for(int i=0; i=k & j=k;k+)if(Boardi-kj-k)return 0;for(k=1; i=k;k+)if(Boardi-kj)return 0;for(k=1; i=k & j+kN;k+)if(Boardi-kj+k)return 0;return 1;void Trial(int i, int n) / 寻找合适下棋位置if(i = n) for(int k=0; kn; k+) for(int m=0; mn; m+)printf(%d , Boardkm);printf(n);print
17、f(n); else for(int j=0; jn; j+) Boardij = 1;if(Valid(i,j)Trial(i+1, n);Boardij = 0;int main(int argc, char* argv) Trial(0, N);14、实现strstr功能，即在父串中寻找子串首次出现的位置。（笔试中常让面试者实现标准库中的一些函数）char * strstring(char *ParentString, char *SubString) char *pSubString, *pPareString;for(char *pTmp=ParentString; *pTmp; p
18、Tmp+) pSubString = SubString;pPareString = pTmp;while(*pSubString = *pPareString & *pSubString != 0) pSubString+;pPareString+;if(*pSubString = 0) return pTmp;return NULL;int main(int argc, char* argv) char *ParentString = happy birthday to you!;char *SubString = birthday;printf(%s,strstring(ParentSt
19、ring, SubString);15、现在小明一家过一座桥，过桥的时候是黑夜，所以必须有灯。现在小明过桥要1分，小明的弟弟要3分，小明的爸爸要6分，小明的妈妈要8分，小明的爷爷要12分。每次此桥最多可过两人，而过桥的速度依过桥最慢者而定，而且灯在点燃后30分就会熄灭。问小明一家如何过桥时间最短？（原本是个小小智力题，据说是外企的面试题，在这里用程序来求解）#include stdafx.h#define N 5#define SIZE 64/ 将人员编号：小明-0，弟弟-1，爸爸-2，妈妈-3，爷爷-4/ 每个人的当前位置：0-在桥左边， 1-在桥右边int PositionN; / 过桥临
20、时方案的数组下标； 临时方案； 最小时间方案； int Index, TmpSchemeSIZE, SchemeSIZE; / 最小过桥时间总和，初始值100；每个人过桥所需要的时间int MinTime=100, TimeN=1, 3, 6, 8, 12; / 寻找最佳过桥方案。Remnant:未过桥人数; CurTime:当前已用时间; / Direction:过桥方向,1-向右,0-向左void Find(int Remnant, int CurTime, int Direction) if(Remnant = 0) / 所有人已经过桥，更新最少时间及方案 MinTime=CurTime
21、; for(int i=0; i=0; i+) Schemei = TmpSchemei; else if(Direction = 1) / 过桥方向向右，从桥左侧选出两人过桥 for(int i=0; iN; i+) if(Positioni = 0 & CurTime + Timei MinTime) TmpSchemeIndex+ = i; Positioni = 1; for(int j=0; j Timej ? Timei : Timej); if(Positionj = 0 & CurTime + TmpMax MinTime) TmpSchemeIndex+ = j; Posit
22、ionj = 1; Find(Remnant - 2, CurTime + TmpMax, !Direction); Positionj = 0; TmpScheme-Index = -1; Positioni = 0; TmpScheme-Index = -1; else / 过桥方向向左，从桥右侧选出一个人回来送灯 for(int j=0; jN; j+) if(Positionj = 1 & CurTime+Timej MinTime) TmpSchemeIndex+ = j; Positionj = 0; Find(Remnant+1, CurTime+Timej, !Directio
23、n); Positionj = 1; TmpScheme-Index = -1; int main(int argc, char* argv) for(int i=0; iSIZE; i+) / 初始方案内容为负值，避免和人员标号冲突 Schemei = TmpSchemei = -1;Find(N, 0, 1); / 查找最佳方案 printf(MinTime=%d:, MinTime);/ 输出最佳方案 for(int i=0; i=0; i+=3) printf( %d-%d %d, Schemei, Schemei+1, Schemei+2); printf(bb );16、2005年
24、11月金山笔试题。编码完成下面的处理函数。函数将字符串中的字符*移到串的前部分，前面的非*字符后移，但不能改变非*字符的先后顺序，函数返回串中字符*的数量。如原始串为：ab*cd*e*12，处理后为*abcde12，函数并返回值为5。（要求使用尽量少的时间和辅助空间）int change(char *str) /* 这个算法并不高效，从后向前搜索效率要高些 */int count = 0;/* 记录串中字符*的个数 */for(int i=0, j=0; stri; i+) /* 重串首开始遍历 */if(stri=*) /* 遇到字符* */for(j=i-1; strj!=*&j=0; j
25、-) /* 采用类似插入排序的思想，将*前面 */strj+1=strj; /* 的非*字符逐个后移，直到遇到*字符 */strj+1 = *;count+;return count;int main(int argc, char* argv) char str = ab*cd*e*12;printf(str1=%sn, str);printf(str2=%s, count=%d, str, change(str);/ 终于得到一个比较高效的算法，一个网友提供，估计应该和金山面试官的想法一致。算法如下：int change(char *str) int i,j=strlen(str)-1;fo
26、r(i=j; j=0; j-) if(stri!=*) i-; else if(strj!=*) stri = strj;strj = *;i-;return i+1;17、2005年11月15日华为软件研发笔试题。实现一单链表的逆转。#include stdafx.htypedef char eleType;/ 定义链表中的数据类型typedef struct listnode / 定义单链表结构eleType data;struct listnode *next;node;node *create(int n) / 创建单链表，n为节点个数node *p = (node *)malloc(
27、sizeof(node);node *head = p; head-data = A;for(int i=B; inext = (node *)malloc(sizeof(node);p-data = i;p-next = NULL;return head;void print(node *head)/ 按链表顺序输出链表中元素for(; head; head = head-next)printf(%c , head-data);printf(n);node *reverse(node *head, node *pre) / 逆转单链表函数。这是笔试时需要写的最主要函数node *p=head
28、-next;head-next = pre;if(p)return reverse(p, head);elsereturn head;int main(int argc, char* argv) node *head = create(6);print(head);head = reverse(head, NULL);print(head);18、编码实现字符串转整型的函数（实现函数atoi的功能），据说是神州数码笔试题。如将字符串 ”+123”123, ”-0123”-123, “123CS45”123, “123.45CS”1
29、23, “CS123.45”0#include stdafx.hint str2int(const char *str) / 字符串转整型函数int i=0, sign=1, value = 0;if(str=NULL) return NULL;/ 空串直接返回 NULLif(str0=- | str0=+) / 判断是否存在符号位i = 1;sign = (str0=- ? -1 : 1);for(; stri=0 & stri=9; i+)/ 如果是数字，则继续转换value = value * 10 + (stri - 0);return sign * value;int main(int argc, char *argv) char *str = -123.45CS67; int val = str2int(str);printf(str=%stval=%dn, str, val);19、歌德巴赫猜想。任何一个偶数都可以分解为两个素数之和。（其实这是个C二级考试的模拟试题）#include stdafx.h#include math.hint main(int argc, char* argv) int Even=78, Prime1, Prime2, Tmp1, Tmp2;for(Prime1=3