首页 > 代码库 > 最近的笔试题
最近的笔试题
1、顺序表的就地逆置
编写一个函数，实现顺序表的就地逆置，也就是说利用原表的存储空间将顺序表(a1,a2...an)逆置为(an,an-1...a2,a1)。
#include <iostream>#include <stdio.h>#include <stdlib.h>using namespace std;//线性表的动态顺序存储结构typedef int DataType; /*数据类型*/typedef int ElemType; /*元素类型*/#define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量#define LISTINCREMENT 10 //线性表存储空间的分配增量typedef struct{ ElemType *elem; //存储空间基址 int length; //当前长度 int listsize; //当前分配的存储容量}SqList;void InitList(SqList *L)//初始化{ L->elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));//分配空间 L->length = 0; //空表的长度为0 L->listsize = LIST_INIT_SIZE; //初始容量}void CreateList(SqList *L){ InitList(L); int i; for(i = 0; ; i ++) { scanf("%d", &L->elem[i]); if(L->elem[i]==-1) break; L->length++; }}void InsertList(SqList *L, int e){ int i; for(i = L->length-1; L->elem[i] > e; i--) //从顺序表最后一位开始，将所有大于e的元素向后移动 { L->elem[i+1] = L->elem[i]; } L->elem[i] = e; L->length++;}void ReverseList(SqList *L){ int i, temp; int n = L->length; for(i = 0; i < n/2; i ++) { temp = L->elem[i]; L->elem[i] = L->elem[n-1-i]; L->elem[n-1-i] = temp; }}void ListTraverse(SqList *L){ int n = L->length, i; for(i = 0; i < n-1; i++) printf("%d ", L->elem[i]); printf("%d\n",L->elem[n-1]);}int main(){ SqList L; CreateList(&L); ReverseList(&L); ListTraverse(&L); return 0;}
2、删除线性表中多余的元素
#include <iostream>#include<stdio.h>#include<stdlib.h>#define OK 1#define ERROR 0using namespace std;//采用的是线性表，单链表作为存储结构，在每一次的//比较是否与之前的元素是否相等，遍历一次链表时间复杂度O（n）typedef int ElemType;typedef int Status;typedef struct Node{ ElemType data; struct Node * next;}Node,*LinkList;//单链表的初始化Status InitLinkList(LinkList * L){ (*L)=(LinkList)malloc(sizeof(Node)); if((*L)==NULL) { //printf("内存分配失败！\n"); return 0; } (*L)->next=NULL; return OK;}//单链表的建立Status Create(LinkList * L,int n){ LinkList P,Q; ElemType Elem; Q=(*L); //printf("请按递增顺序输入元素：\n"); for(int i=0;i<n;i++) { P=(LinkList)malloc(sizeof(Node)); scanf("%d",&Elem); P->data=http://www.mamicode.com/Elem; Q->next=P; Q=P; } P->next=NULL; return OK;}//删除结点Status Delete(LinkList * L,int Location){ LinkList Q,P; int count=0; int k=Location+1; Q=(*L); P=(*L)->next; while(P->next) { Q=Q->next; P=P->next; count++; if(count==Location) { Q->next=P->next; } } return OK;}//定位删除结点的位置并删除Status Locate(LinkList * L){ LinkList First,Second; int count=1; First=(*L)->next; Second=(*L)->next->next; while(Second) { if(First->data=http://www.mamicode.com/=Second->data) { Delete(L,count); Second=Second->next; } else { count++; First=First->next; Second=Second->next; } } return OK;}void Print(LinkList * L){ LinkList P; P=(*L)->next; while(P) { printf("%d ",P->data); P=P->next; } printf("\n");}int main(){ LinkList L; int Number; InitLinkList(&L); //printf("请输入元素个数：\n"); scanf("%d",&Number); Create(&L,Number); //printf("输出链表：\n"); //Print(&L); Locate(&L); //printf("输出去掉相同元素后链表：\n"); Print(&L); return 0;}
3、表达式括号匹配
#include<stdio.h>#include<malloc.h>#include<string.h>#define STACK_INIT_SIZE 10#define STACK_GROW_SIZE 5#define ELEMTYPE char#define OK 1#define ERROR 0typedef struct { /*建立一个栈的首结点*/ ELEMTYPE * base; ELEMTYPE * top; int stacksize;} SpStack;int InitStack(SpStack *s) { /*建立空的栈并返回首地址*/ s->base=((ELEMTYPE*)malloc(STACK_INIT_SIZE*sizeof(ELEMTYPE))); if (!s->base) return ERROR; s->top=s->base; s->stacksize=STACK_INIT_SIZE; return OK;}int StackEmpty(SpStack *s) { /*判断栈是否为空*/ if (s->top==s->base) return OK; else return ERROR;}int Push(SpStack *s,ELEMTYPE e) { /*往栈顶插入元素即进栈*/ if (s->top-s->base>=s->stacksize) { /*判断是否栈满*/ s->base=((ELEMTYPE*)realloc(s->base,(s->stacksize+STACK_GROW_SIZE)*sizeof(ELEMTYPE))); if (!s->base) return ERROR; s->stacksize+=STACK_GROW_SIZE; s->top=s->base+s->stacksize; } *s->top++=e; return OK;}int Pop(SpStack *s,ELEMTYPE *e) { /*让栈顶元素依次输出即出栈*/ if (StackEmpty(s)) return ERROR; *e=*(--s->top); return OK;}int Comp(ELEMTYPE a,ELEMTYPE b) { if ((a==‘(‘&&b!=‘)‘) ||(a==‘[‘&&b!=‘]‘) ||(a==‘{‘&&b!=‘}‘)) { return ERROR; } else return OK;}int Count(SpStack *s) { ELEMTYPE e[STACK_INIT_SIZE*2]; ELEMTYPE e1; int i; InitStack(s); fgets(e,STACK_INIT_SIZE*2,stdin); if (‘\n‘==e[strlen(e)-1]) e[strlen(e)-1]=0; //printf("%s\n",e); for (i=0;e[i]!=‘\0‘;i++) { switch (e[i]) { case ‘(‘: case ‘[‘: case ‘{‘: Push(s,e[i]); break; case ‘)‘: case ‘]‘: case ‘}‘: if (StackEmpty(s)) { printf("ERROR\n"); //printf("%*s↖右括号多余\n",i+1,""); return(ERROR); } else Pop(s,&e1); if (!Comp(e1,e[i])) { printf("ERROR\n"); //printf("%*s↖左右匹配出错\n",i+1,""); return(ERROR); } } } if (!StackEmpty(s)) { //printf("%*s↖左括号多余\n",i,""); printf("ERROR\n"); return(ERROR); } else { printf("OK\n"); return(OK); }}int main() { SpStack s; Count(&s); free(s.base); return 0;}
4、两个已排序的数组进行合并
#include <iostream>#include <assert.h>#include<stdio.h>#include<stdlib.h>/**Describe:print the elements of the array*Data:5/11/2013*Author:pjgan*Version:1*tool:vc++2008*/void Global_printElements(const int *pArray,int Array_Length);/**Return: true is sorted**/bool Global_isSort(const int *pArray, int iArrayLeng);/**Return: is the returlts of the Merge Array_A and Array_B*/void *Global_Merge(const int *Array_A, int Array_A_Length, const int *Array_B, int Array_B_Length);void Global_printElements(const int *pArray,int Array_Length){ assert(pArray); int i = 0; for( ; i < Array_Length; ++i) { std::cout<<pArray[i]<<" "; } std::cout<<std::endl;}bool Global_isSort(const int *pArray, int iArrayLeng){ assert(pArray); int i = 0; int j = 0; for( ; i < (iArrayLeng-1); ++i) { for( j = ( i + 1); j < iArrayLeng; ++j) { if(pArray[i] > pArray[j]) return false; } } return true;}void *Global_Merge(const int *Array_A, int Array_A_Length, const int *Array_B, int Array_B_Length) { assert(Array_A && Array_B); bool bArrayAisSorted = Global_isSort(Array_A, Array_A_Length); bool bArrayBisSorted = Global_isSort(Array_B, Array_B_Length); if(bArrayAisSorted && bArrayBisSorted) { /* * i,j are the index of the Array_A and the Array_B */ int i = 0; int j = 0; int *pStoreMergeArrayData = http://www.mamicode.com/new int[Array_A_Length + Array_B_Length]; int MergeArrayIndex = 0; while(i < Array_A_Length && j < Array_B_Length) { if(Array_A[i] < Array_B[j]) { pStoreMergeArrayData[MergeArrayIndex++] = Array_A[i++]; } else { pStoreMergeArrayData[MergeArrayIndex++] = Array_B[j++]; } } while(i < Array_A_Length) { pStoreMergeArrayData[MergeArrayIndex++] = Array_A[i++]; } while(j < Array_B_Length) { pStoreMergeArrayData[MergeArrayIndex++] = Array_B[j++]; } return pStoreMergeArrayData; } else { std::cout<<"merge failed"<<std::endl; //exit(1); } return NULL;}int main() { int a[] = {1, 2, 3, 5, 8}; //int a[1005],b[1005],n,m,i1,j1; //scanf("%d %d",&n,&m); //for(i1=0;i1<n;i1++) // scanf("%d",&a[i1]); //for(j1=0;j1<m;j1++) // scanf("%d",&b[j1]); int b[] = {2, 6, 7, 10, 25, 33, 50}; int *MergeArray = (int *)Global_Merge(a, 5, b, 6); Global_printElements(MergeArray, 5+6); if(MergeArray != NULL) { delete MergeArray; MergeArray = NULL; } return 0;}
5、将一维数组中的元素向右循环移动k次
输入数据有多组，每组数据由两行组成，第一行是k和n，第二行n个整数的数列，数列中的元素以空格隔开。
#include <iostream>#include<stdio.h>#include<stdlib.h>#include<malloc.h>using namespace std;void fun(int *a,int k,int n){ int i,j,m; for ( i=0;i<k;i++ ) { m=a[n-1]; for ( j=n-1;j>0;j-- ) a[j]=a[j-1]; a[0]=m; }}int main(){ int k,n,i; int *a; while ( 1 ) { scanf("%d",&n); if (n>=0) if ( a=(int *)malloc(n*sizeof(int)) ) { for ( i=0;i<n;i++ ) scanf("%d",a+i); scanf("%d",&k); fun(a,k,n); for ( i=0;i<n;i++ ) printf("%d ",a[i]); printf("\n"); free(a); } }}
6、相邻最大差值
题目描述
请设计一个复杂度为O(n)的算法，计算一个未排序数组中排序后相邻元素的最大差值。
给定一个整数数组A和数组的大小n，请返回最大差值。
#include <iostream>#include <vector>using namespace std;class Gap {public: int maxGap(vector<int> A, int n) { int var_max = A[0], var_min = A[0]; for(int i = 1; i < n; i++){ if(var_max < A[i]) var_max = A[i]; if(var_min > A[i]) var_min = A[i]; } if(var_max == var_min) return 0; double var_unit = (double)(var_max - var_min)/(double)n; // vector<int> bucket[n+1]; vector<vector<int> > bucket(n+1); for(int i = 0; i < n; i++){ bucket[getIndex(var_unit, A[i], var_min)].push_back(A[i]); } int res = -1, tmp; int index1 = 0, index2 = 1; while(index2 < n+1){ // cout<<"index1: "<<index1<<"|| index2: "<<index2<<endl; if(!bucket[index1].empty() && !bucket[index2].empty()){ tmp = getMin(bucket[index2]) - getMax(bucket[index1]); index1++, index2++; if(tmp > res) res = tmp; } if(bucket[index1].empty()) index1++; if(bucket[index2].empty()) index2++; } return res; } int getIndex(double var_unit, int var, int var_min){ return ((double)(var-var_min)/var_unit); } int getMax(vector<int> A){ int tmp = A[0]; for(int i = 1; i < A.size(); i++){ if(tmp < A[i]) tmp = A[i]; } return tmp; } int getMin(vector<int> A){ int tmp = A[0]; for(int i = 1; i < A.size(); i++){ if(tmp > A[i]) tmp = A[i]; } return tmp; }};int main(){ vector<int> A; //3429,6401,8559,1052,4775,6220,3593,2406,4995 A.push_back(3429), A.push_back(6401), A.push_back(8559), A.push_back(1052), A.push_back(4775); A.push_back(6220), A.push_back(3593), A.push_back(2406), A.push_back(4995); Gap sorter; int res = sorter.maxGap(A, 9); cout<<res<<endl; return 0;}
最近的笔试题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。