5．写一段程序，出数组中第k大小的数，输出数所在的位置。例如{2，4，3，4，7}中，第一大的数是7，位置在4。第二大、第三大的数都是4，位置在1、3随便输出哪一个均可。函数接口为：int find_orderk(const int* narry,const int n,const int k)
要求算法复杂度不能是O(n^2）
答案：可以先用快速排序进行排序，其中用另外一个进行地址查
代码如下，在VC++6.0运行通过。给分吧^-^
//快速排序
printf怎么加endl#include<iostream>
usingnamespacestd;
intPartition (int*L,intlow,int high)
{
inttemp = L[low];
intpt = L[low];
while (low < high)
{
while (low < high && L[high] >= pt)
--high;
L[low] = L[high];
while (low < high && L[low] <= pt)
++low;
L[low] = temp;
}
L[low] = temp;
returnlow;
}
voidQSort (int*L,intlow,int high)
{
if (low < high)
{
intpl = Partition (L,low,high);
QSort (L,low,pl - 1);
QSort (L,pl + 1,high);
}
}
int main ()
{
intnarry[100],addr[100];
intsum = 1,t;
cout << "Input number:" << endl;
cin >> t;
while (t != -1)
{
narry[sum] = t;
addr[sum - 1] = t;
sum++;
cin >> t;
}
sum -= 1;
QSort (narry,1,sum);
for (int i = 1; i <= sum;i++)
cout << narry[i] << '\t';
cout << endl;
intk;
cout << "Please input place you want:" << endl;
cin >> k;
intaa = 1;
intkk = 0;
for (;;)
{
if (aa == k)
break;
if (narry[kk] != narry[kk + 1])
{
aa += 1;
kk++;
}
}
cout << "The NO." << k << "number is:" << narry[sum - kk] << endl;
cout << "And it's place is:" ;
for (i = 0;i < sum;i++)
{
if (addr[i] == narry[sum - kk])
cout << i << '\t';
}
return0;
}
int main(void)
{
int MAX = 10;
int *a = (int *)malloc(MAX * sizeof(int));
int *b;
FILE *fp1;
FILE *fp2;
fp1 = fopen("a.txt","r");
if(fp1 == NULL)
{printf("error1");
exit(-1);
}
fp2 = fopen("b.txt","w");
if(fp2 == NULL)
{printf("error2");
exit(-1);
}
int i = 0;
int j = 0;
while(fscanf(fp1,"%d",&a[i]) != EOF)
{
i++;
j++;
if(i >= MAX)
{
MAX = 2 * MAX;
b = (int*)realloc(a,MAX * sizeof(int));
if(b == NULL)
{
printf("error3");
exit(-1);
}
a = b;
}
}
for(;--j >= 0;)
fprintf(fp2,"%d\n",a[j]);
fclose(fp1);
fclose(fp2);
return 0;
}
6.void g(int**);
int main()
{
int line[10],i;
int *p=line;
for (i=0;i<10;i++)
{
*p=i;
g(&p);
}
for(i=0;i<10;i++)
printf("%d\n",line[i]);
return 0;
}
void g(int**p)
{
(**p)++;
(*p)++;
}
输出？
答案：1
2
3
4
5
6
7
8
9
10
这道题目不是很好理解，我们可以把题目g函数改为
void g(int**s)
{
(**s)++;
(*s)++;
}
这样不容易看混淆s就是一个形式参数，g(&p)输入的就是p的地址，这样有如下指向：*p－》p－》line调用函数时候，**s对应*p即数组中的数,*s对应p即数组数字的地址，这样就可以知道了(**s)++是line中的内容增加；(*s)++是地址增加。
7.写出程序运
行结果
int sum(int a)
{
auto int c=0;
static int b=3;
c+=1;
b+=2;
return(a+b+c);
}
void main()
{
int I;
int a=2;
for(I=0;I<5;I++)
{
printf("%d,", sum(a));
}
}
答案：static会保存上次结果，记住这一点，剩下的自己写
输出：8,10,12,14,16,
8.int a[3];
a[0]=0; a[1]=1; a[2]=2;
int *p, *q;
p=a;
q=&a[2];
则a[q-p]=a[2]
答案：指针一次移动一个int但计数为1，p＝a；q＝a＋2。
1.分析下面的程序：
void GetMemory(char **p,int num)
{
*p=(char *)malloc(num);
}
int main()
{
char *str=NULL;
GetMemory(&str,100);
strcpy(str,"hello");
free(str);
if(str!=NULL)
{
strcpy(str,"world");
}
printf("\n str is %s",str);
getchar();
}
问输出结果是什么？
答案：输出str is world。
free 只是释放的str指向的内存空间，它本身的值还是存在的.
所以free之后，有一个好的习惯就是将str=NULL.
此时str指向空间的内存已被回收，如果输出语句之前还存在分配空间的操作的话，这段存储空间是可能被重新分配给其他变量的,
尽管这段程序确实是存在大大的问题（上面各位已经说得很清楚了），但是通常会打印出world来。
这是因为，进程中的内存管理一般不是由操作系统完成的，而是由库函数自己完成的。
当你malloc一块内存的时候，管理库向操作系统申请一块空间（可能会比你申请的大一些），然后在这块空间中记录一些管理信息（一般是在你申请的内存前面一点），并将可用内存的地址返回。但是释放
内存的时候，管理库通常都不会将内存还给操作系统，因此你是可以继续访问这块地址的，只不过。。。。。。。。楼上都说过了，最好别这么干。
2.运行的结果为什么等于15
#include "stdio.h"
#include "string.h"
void main()
{
char aa[10];
printf("%d",strlen(aa));
}
答案：sizeof()和初不初始化，没有关系；strlen()和初始化有关。
3.给定结构struct A
{
char t:4;
char k:4;
unsigned short i:8;
unsigned long m;
}；问sizeof(A) = ?
答案：给定结构
struct A
{
char t:4; //4位
char k:4; //4位
unsigned short i:8; //8位 这里要偏移2字节保证4字节对齐
unsigned long m; //4个字节
}; // 共8字节
4。分析一下
#include<iostream.h>
#include <string.h>
#include <malloc.h>
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
typedef struct AA
{
int b1:5;
int b2:2;
}AA;
void main()
{
AA aa;
char cc[100];
strcpy(cc,"0123456789abcdefghijklmnopqrstuvwxyz");
memcpy(&aa,cc,sizeof(AA));
cout << aa.b1 <<endl;
cout << aa.b2 <<endl;
}
答案： -16和１
首先sizeof(AA)的大小为4,b1和b2分别占5bit和2
bit.
经过strcpy和memcpy后,aa的4个字节所存放的值是:
0,1,2,3的ASC码，即00110000,00110001,00110010,00110011
所以，最后一步：显示的是这４个字节的前５位，和之后的２位
分别为：10000，和01
因为int是有正负之分 所以是-16和１
5.求函数返回值，输入x=9999;
int func （ x ）
{
int countx = 0;
while ( x )
{
countx ++;
x = x&(x-1);
}
return countx;
}
结果呢？
答案：知道了这是统计9999的二进制数值中有多少个1的函数，且有
9999＝9×1024＋512＋256＋15
9×1024中含有1的个数为2；
512中含有1的个数为1；
256中含有1的个数为1；
15中含有1的个数为4；
故共有1的个数为8，结果为8。
1000 - 1 = 0111，正好是原数取反。这就是原理。
用这种方法来求1的个数是很效率很高的。
不必去一个一个地移位。循环次数最少。
6.int a,b,c 请写函数实现C=a+b ，不可以改变数据类型，如将c改为long int，关键是如何处理溢出问题
答案：bool add (int a, int b,int *c)
{
*c=a+b;
return (a>0 && b>0 &&(*c<a || *c<b) || (a<0 && b<0 &&(*c>a || *c>b)));
}
7.分析：
struct bit
{ int a:3;
int b:2;
int c:3;
};
int main()
{
bit s;
char *c=(char*)&s;
cout<<sizeof(bit)<<endl;
*c=0x99;
cout << s.a <<endl <<s.b<<endl<<s.c<<endl;
int a=-1;
printf("%x",a);
return 0;
}
输出为什么是？
答案：4
1
-1
-4
ffffffff
因为0x99在内存中表示为 100 11 001 , a = 001, b = 11, c = 100（在vc环境中，一般是由右到左进行分配的）
当c为有符合数时, c = 100, 最高1为表示c为负数，负数在计算机用补码表示，所以c = -4；同理
b = -1;
当c为有符合数时, c = 100，即 c = 4，同理 b = 3
8.改错：
#include <stdio.h>
int main(void) {
int **p;
int arr[100];
p = &arr;
return 0;
}
答案：搞错了，是指针类型不同,
int **p; //二级指针
&arr; //得到的是指向第一维为100的数组的指针
应该这样写#include <stdio.h>
int main(void) {
int **p, *q;
int arr[100];
q = arr;
p = &q;
return 0;
9.下面这个程序执行后会有什么错误或者效果:
#define MAX 255
int main()
{
unsigned char A[MAX],i; //i被定义为unsigned char
for (i=0;i<=MAX;i++)
A[i]=i;
}
答案：死循环加数组越界访问（C/C++不进行数组越界检查）
MAX=255
数组A的下标范围为:0..MAX-1，这是其一..
其二.当i循环到255时，循环内执行:
A[255]=255;
这句本身没有问题..但是返回for (i=0;i<=MAX;i++)语句时,
由于unsigned char的取值范围在(0..255),i++以后i又为0了..无限循环下去.
11.struct name1{
char str;
short x;
int num;
}
struct name2{
char str;
int num;
short x;
}
sizeof(struct name1)=？？,sizeof(struct name2)=？？
答案：size
of(struct name1)=8,sizeof(struct name2)=12
在第二个结构中，为保证num按四个字节对齐，char后必须留出3字节的空间；同时为保证整个结构的自然对齐（这里是4字节对齐），在x后还要补齐2个字节，这样就是12字节。
//memmove()功能将指针src指向的前n个字节拷贝到dest指向的前n个内存区域中
//可能出现dest和scr内存重叠的情况，都进行了很好的处理，这也是和mencpy()的区别之处
vord *memmove(void *dest,const void *src,size_t count)
{
void *ret=dest;
if(dest<=src||dest>=src+count)
{
while(count--)
*dest++=*src++
}
else
{
dest+=count-1;
src+=count-1;
while(count--)
*dest--=*src--
}
return ret;
}
//void *memset(void *s,int c,int n)
/
/用c填充由指针s指向的内存区域的前n个字节.返回指向该内存区域的指针s.s并不一定是指向字符的指针,
//以是指向任何类型的指针，甚至可以是指向结构的指针.
int memcmp (const void * buf1,const void * buf2, size_t count)
{
if (!count)
return(0);
while ( --count && *(char *)buf1 == *(char *)buf2 ) {
buf1 = (char *)buf1 + 1;
buf2 = (char *)buf2 + 1;
}
return( *((unsigned char *)buf1) - *((unsigned char *)buf2) );
}
char * strcat (char * dst, const char * src )
{
char * cp = dst;
while( *cp )
cp++; /* find end of dst */
while( *cp++ = *src++ ) ; /* Copy src to end of dst */
return( dst ); /* return dst */
}
int strcmp (const char * src, const char * dst)
{
int ret = 0 ;
while( ! (ret = *(unsigned char *)src - *(unsigned char *)dst) && *dst)
++src, ++dst;
if ( ret < 0 )
ret = -1 ;
else if ( ret > 0 )
ret = 1 ;
return( ret );
}
void *memcpy(void *pvTo, const void *pvFrom, size_t size)
{
assert((pvTo != NULL) && (pvFrom != NULL)); // 使用断言
byte *pbTo = (byte *) pvTo; // 防止改变pvTo的地址
byte *pbFrom = (byte *) pvFrom; // 防止改变pvFrom的地址
while(size -- > 0 )
*pbTo ++ = *pbFrom ++ ;
return pvTo;
}
Kingsoft
一、请你就C/C++或者JAVA代码行数、注释行数统计工具的实现，描述一下：
需要考虑哪些过滤条件？你如何处理？
答：过滤条件：（取得每行并去掉两头的空格后）
⑴空行，行的长度为0；⑵如果是以//开头，为注释行；⑶//在行中，并判断不是在字符串中，即“”中，为代码+注释混合行，//在“”中时为代码行；⑷如果/*在行中，判断是否是在“”内，否则为注释行，*/不在“”中时是结束 ；⑸/* */只在一行，判断行中是否有代码，无代码为注释行，有代码是混合行；⑹/* */多行
，并且/*前无代码，/*后无代码，去掉其中空行都是注释行；⑺/* */多行，/*在代码后，或*/后有代码，有混合行；⑻一行中有2个/*并且就1个*/，此行为混合行，其后是注释行。
怎样提升这个工具的易用性？
答：把这个工具设置成图形界面，用户只需输入文件名或者在文件对话框中选择文件即可点击运行输出结果。
本题只需要提供思路文档，不需要程序代码。
二、给定一个自然数n，试完成如下程序，它输出不大于n的所有素数（质数）。
请提供程序代码，以及思路文档。
答：思路：求出一个数j的平方根sqrt(j)，将j除以2~sqrt(j)之间的数，只要除尽一次，就不是素数，之后数j加2。
#include<stdio.h>
#include<math.h>
void main()
{ int N=1000;
int i,j,k,m=0;
for(j=1;j<N;j=j+2) /*1-N间的素数*/
{ k=(int)sqrt(j); /*求平方根*/
for(i=2;i<=k;i++)
{ if(j%i==0) /*只要除尽一次，就不是素数*/
break;
}
if(i>k) /*/除到k一直没除尽，是素数*/
printf("%d ",j);
}
}
请分析一下可以从哪些角度可优化该程序的时间性能？
答：偶数（除了2）不能为素数；判断一个数j是否为素数，只要将其除以2 ~ sqrt(j)之间的素数，更进一步，没有必要对所有奇数进行试除，只需对所有sqrt(j)以内的所有质数试除就可以了。
三、高精度乘法
用户输入两个不大于 256 位的正整数，由程序进行乘法运算，并显示运算过程与结果。例：
输入：12, 32
输出：
１２
× ３２
————————
２４
３６
————————
３８４
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#define max 256
int A[max],B[max];
int Alen,Blen;
int S[max *2];
void InputAB() //输入A B
{ int c;
while (!isdigit(c = getchar())) ;
Alen=1;
A[0]= c - '0';
while (isdigit(c = getchar()))
A[Alen++] = c - '0';
while (!isdigit(c = getchar())) ;
Blen = 1;
B[0] = c - '0';
while (isdigit(c = getchar()))
B[Blen++] = c - '0';
}
void Print(int Array[], int len) //输出数组
{ int i=0;
while ((i<len) && (Array[i] == 0) )
i++;
if (i == len)
{ printf(“0 \n”);
return;
}
for ( ;i < len; i++)
printf(“%d”,Array[i]);
printf(“\n”);
}
void Mul(int Array[], int len, int n, int Result[], int zeros) //相乘
{ int i;
for (i = len - 1; i >= 0; i--)
Result[i+1] = Array[i]*n;
Result[0] = 0;
for (i = len; i > 0; i--)
{ if (Result[i] >= 10) //大于10的进位
{ Result[i-1] +=Result[i] / 10;
Resul
t[i] %= 10;
}
}
for (i = 1; i <= zeros; i++)
Result[len+i] = 0;
}
void Add(int total[], int tlen, const int add[], int alen) //各行相加
{ int i,k = tlen;
while ((tlen > 0) && (alen > 0)) //相加
{ tlen--;
alen--;
total[tlen] += add[alen];
}
for (i = k - 1; i>=0; i--)
if (total[i] >= 10) //大于10的进位
{ total[i - 1] += total[i] / 10;
total[i] %= 10;
}
}
void main()
{ int i,j;
int temp[max*2];
InputAB();
Print(A,Alen);
printf(“*”);
Print(B,Blen);
printf("-----\n");
for(i = Blen-1; i >= 0; i--)
{ for(j=Blen-i,j>=0;j--) //输出空格
{ printf(“ ”);
}
Mul(A, Alen, B[i], temp, Blen - 1 -i);//B中的一个数与A的所有数相乘
Print(temp, Alen + 1); //输出相乘过程中的每行
Add(S, max*2, temp, Alen + Blen - i);//每行相加
}
printf("-----\n");
Print(S, max*2);
}
}
四、输入一个N进制数，将其转换成 M 进制数（1<N<=16，1<M<=16)
#include <iostream.h>
#include <stdio.h>
#include <stack.h>
#include <assert.h>
#include <math.h>
using namespace std;
int main()
{
char digit[16] = {0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F};
cout <<"输入待转换整数: ";
char c;
char a[80];
char b[80];
int i=0,j=0,length;
while ((c = getchar())!='\n') //输入
{a[i]=c;
i++;
}
length=i; //输入的数的位数 0~i-1
for(j=0;j<length;j++) //转化成数值
{ if( a[j]>='0'&&a[j]<='9' )
b[j] = a[j] - '0';
else if( a[j]>='a'&&a[j]<='f' )
b[j] = a[j] -'a' +10;
else if( a[j]>='A'&&a[j]<='F' )
b[j] = a[j] -'A' +10;
else
return FALSE;
}
cout<<"输入的数是多少进制N："；
int n
cin>>n;
assert((n>1)&&(n<=16));
int num=0;
for(i=0,j=length-1;j>=0;j--,i++)//输入的数转成十进制
{num+=b[i]*pow(n,j);
}
cout <<"转换成进制数M： ";
int m;
cin >>m;
cout <<endl;
assert((m>1)&&(m<=16));
stack<char> stk;
char remain;
while (num!=0)//转成M进制
{
remain = digit[num%m];
stk.push(remain);
num/= m;
}
cout <<"结果: ";//输出结果
while(!pty())
{
cout <&p();
stk.pop();
}
cout <<endl;
return 0;
}
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论