【原创】<笔试题> 深圳市天软科技开发有限公司

时间：2018.03.03 上午

1、编写函数，实现字符串比较功能。

参考：http://blog.csdn.net/liubinzi123/article/details/8271683

/*

* Copyright (c) 2012, 烟台大学计算机学院

* All rights reserved.

* 作 者：  刘同宾

* 完成日期：2012 年 12 月 07 日

* 版 本 号：v1.0

*

* 输入描述：

* 问题描述： 写一函数，实现两个字符串的比较，即自己写一个strcmp函数

* 程序输出：

* 问题分析：略

* 算法设计：略

*/ 

#include<iostream>

using namespace std;

int main()

{

    int strcmp(char *p1,char *p2);  //函数声明

    char str1[],str2[],*p1,*p2;//定义两个字符数组，和两个字符指针

    int m;

    cout<<"请输入第一个字符串："<<endl;  //输入两个字符数组

    cin>>str1;

    cout<<"请输入第二个字符串："<<endl;

    cin>>str2;

    p1=&str1[];  //指针分别指向两个字符数组的首元素

    p2=&str2[];

    m=strcmp(p1,p2);  //函数调用

    cout<<"结果为："<<m<<endl;

    return ;

}

//定义字符串比较函数

int strcmp(char *p1,char *p2)

{

    int i;

    i=;

    while(*(p1+i)==*(p2+i))

    {

        if(*(p1+i++)=='\0' && *（p2+i++）== '\0')   //全部字符相同时返回结果0

        {

            return ;

        }

    }

    return (*(p1+i)-(*(p2+i)));//不同时返回结果为第一对不同字符的ASCII码的差值

}

2、描述题：说一下对web的认识，实现方式、应用途径、以及相关技术。

答：在网页设计中称为网页，表现为三种形式，即超文本（hypertext）、超媒体（hypermedia）、超文本传输协议（HTTP）。

Web是一种典型的分布式应用结构。Web应用中的每一次信息交换都要涉及客户端和服务端。因此， Web开发技术大体上也可以被分为客户端技术和服务端技术两大类。

Web客户端的主要任务是展现信息内容。Web客户端设计技术主要包括：HTML语言、Java Applets（动态web页面）、脚本程序（JavaScrip）、CSS、DHTML、插件技术以及VRML技术。

Web服务端的开发技术也是由静态向动态逐渐发展、完善起来的。Web服务器技术主要包括服务器、CGI（common gateway interface公共网关接口技术）、PHP、ASP、ASP.NET、Servlet和JSP技术。

3、递归调用程序结果

4、SQL 语句增删改查（参考：//blog.csdn.net/wxw20147854/article/details/55549296）

（1）表

创建数据库： create database dbname
删除数据库： drop database dbname
创建表： create table tname()
-------括号里面是自己需要的各种参数
删除表： drop table tname

（2）数据
插入数据： insert into tname(field1, field2) values(value1, value2)
删除数据： delete from tname ------删除表中的所有数据
delete from tname where 条件表达式 ------删除表中符合条件的数据
更新数据： update tname set field1=value1, field2=value2 where 条件表达式 ------更新满足条件的项
查找数据： select * from tname ------查找表中的所有数据
select * from tname where field=value ------查找符合条件的数据
select * from tname where field like '%value%' ------查找符合条件的数据，模糊查找

5、函数 f（x）= a0 + a1 * x^1 + a2 * x^2 + ...... + an * x^n

系数数组 double A[ N +1 ]

#include <stdio.h>

#define MAXN 10

double f( int n, double a[], double x );

int main()

{

    int n, i;

    double a[MAXN], x;

    scanf("%d %lf", &n, &x);

    for ( i=; i<=n; i++ )

        scanf(“%lf”, &a[i]);

    printf("%.1f\n", f(n, a, x));   // 调用

    return ;

}

double f ( int n, double a[ ], double x )

{    int i;

    double t= ;

    double sum = a[  ];

    for ( i = ; i <= n; i++ ){

        t= t* x;

        sum += t* a[ i ];

 }

return sum;

}

6、在一个字符串中找到第一个只出现一次的字符

方法一：

最直观的想法是从头开始扫描这个字符串中的每个字符。当访问到某字符时拿这个字符和后面的每个字符相比较，如果在后面没有发现重复的字符，则该字符就是只出现一次的字符。如果字符串有n个字符，每个字符可能与后面的O(n)个字符相比较，因此这种思路时间复杂度是O(n2)。

char findonce(char * str){

        if (NULL == str)

               return '\0' ;

        for (int i = ;str[i] != '\0';i++){

               int j = i+;

               while (str[j]!= '\0' )
              {

                      if (str[j] != str[i])

                           j++;

                      else

                            break ;  // 已重复出现过，则不用再往后比较

              }

               if (str[j] == '\0' )

                      return str[i];

       }

        return '\0' ;

}

方法二：

我们试着去找一个更快的方法。由于题目与字符出现的次数相关，我们是不是可以统计每个字符在该字符串中出现的次数？要达到这个目的，我们需要一个数据容器来存放每个字符的出现次数。在这个数据容器中可以根据字符来查找它出现的次数，也就是说这个容器的作用是把一个字符映射成一个数字。在常用的数据容器中，哈希表正是这个用途。

由于字符（char）是一个长度为8的数据类型，因此总共有可能256 种可能。于是我们创建一个长度为256的数组，每个字母根据其ASCII码值作为数组的下标对应数组的对应项，而数组中存储的是每个字符对应的次数。这样我们就创建了一个大小为256，以字符ASCII码为键值的哈希表。（256个字符我们建立一个256个数组，数组用来存放字符的次数，使用字符的ASCII值作为数组的下标）

我们第一遍扫描这个数组时，每碰到一个字符，在哈希表中找到对应的项并把出现的次数增加一次。这样在进行第二次扫描时，就能直接从哈希表中得到每个字符出现的次数了。

char FirstNotRepeatingChar(char* pString)

{

      // invalid input

      if(!pString)

            return '\0';

      // 1、初始化

      const int tableSize = ;

      unsigned int hashTable[tableSize];

      for(unsigned int i = ; i < tableSize; ++ i)

            hashTable[i] = ;

      //2、以字符的ASCII作为数组下标，求每个字符出现的次数

      char* pHashKey = pString;

      while(*(pHashKey) != '\0')

            hashTable[*(pHashKey++)] ++;

      // 3、找到第一次出现一次的字符，就是在数组中第一次存储为1所对应的字符

      pHashKey = pString;

      while(*pHashKey != '\0')

      {

            if(hashTable[*pHashKey] == )

                  return *pHashKey;

            pHashKey++;

      }

      // if the string is empty

      // or every char in the string appears at least twice

      return '\0';

}

7、判断一个自然数是否是某个数的平方。当然不能使用开方运算。（参考：http://blog.csdn.net/elton_xiao/article/details/41172769）

假设待判断的数字是 N。

方法1：

遍历从1到N的数字，求取平方并和N进行比较。
如果平方小于N，则继续遍历；如果等于N，则成功退出；如果大于N，则失败退出。
复杂度为O(n^0.5)。

方法2：
使用二分查找法，对1到N之间的数字进行判断。

复杂度为O(log n)。

bool square(int n)

{

        int l = , h = n;

        while (l <= h)

        {

                const int m = (l+h)/;

                const int s = m * m;

                if (s == n)

                        return true;

                else if (s < n)

                        l = m + ;

                else

                        h = m - ;

        }

        return false;

}

方法3：
由于
(n+1)^2
=n^2 + 2n + 1，
= ...
= 1 + (2*1 + 1) + (2*2 + 1) + ... + (2*n + 1)
注意到这些项构成了等差数列（每项之间相差2）。

所以我们可以比较 N-1， N - 1 - 3， N - 1 - 3 - 5 ... 和0的关系。

即，将一个数连续减去，1，3，5，7，9，11，13,...

如果大于0，则继续减；如果等于0，则成功退出；如果小于 0，则失败退出。

复杂度为O(n^0.5)。不过方法3中利用加减法替换掉了方法1中的乘法，所以速度会更快些。

bool square(int n)

{

    int i = ;

    n = n - i;

    while(n > )

    {

        i += ;

        n -= i;

    }

    if( n ==  )

        return true;

    else

        return false;

}

巴特西

【原创】<笔试题> 深圳市天软科技开发有限公司

最新文章

热门文章