插入排序，選擇排序，冒泡排序，歸并排序（c語言實現）

今天復習了下一些常見的排序算法,并用c語言實現了下。代碼如下：
#include<stdio.h>
#include<stdlib.h>

#define MAX 65536 /*用于歸并排序中的哨兵*/

/*簡單插入排序,時間復雜度為o(n2),穩定排序，適合已經排好序的*/
void insertSort(int arr[],int len)
{
    int i,j;
    int key;
    for(i=1;i<len;i++)
    {
        key=arr[i];
        for(j=i-1;j>=0;j--)
        {
            if(arr[j]>key)
                arr[j+1]=arr[j];
            else
                break;
        }
        arr[j+1]=key;
    }
}

/*選擇排序，時間復雜度為o(n2),不穩定排序，適合規模比較小的*/
void selectSort(int arr[],int len)
{
    int i,j,temp;
    for(i=0;i<len;i++)
    {
        for(j=i+1;j<len;j++)
        {
            if(arr[i]>arr[j])
            {
                temp=arr[i];
                arr[i]=arr[j];
                arr[j]=temp;
            }
        }
    }
}

/*冒泡排序，時間復雜度為o(n2),穩定排序，適合規模比較小的*/
void bubbleSort(int arr[],int len)
{
    int i,j,temp;
    for(i=0;i<len;i++)
    {
        for(j=0;j<len-i-1;j++)
        {
            if(arr[j]>arr[j+1])
            {
                temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
            }
        }
    }
}

/*合并（歸并）排序,時間復雜度為o(nlogn),穩定排序，適合規模比較大的排序*/
void merge(int arr[],int p,int q,int r)
{
    int *A,*B;
    int n1,n2,i,j,k;
    n1=q-p+1;
    n2=r-q;
    if((A=(int*)malloc((n1+1)*sizeof(int)))==NULL)
    {
        perror("malloc error");
        exit(1);
    }
    if((B=(int*)malloc((n2+1)*sizeof(int)))==NULL)
    {
        perror("malloc error");
        exit(1);
    }
    for(i=0;i<n1;i++)
    {
        A[i]=arr[p+i];
    }
    A[i]=MAX;
    for(i=0;i<n2;i++)
    {
        B[i]=arr[q+i+1];
    }
    B[i]=MAX;
    i=0;j=0;
    for(k=p;k<=r;k++)
    {
        if(A[i]>B[j])
        {
            arr[k]=B[j];
            j++;
        }else{
            arr[k]=A[i];
            i++;
        }
    }
}

void mergeSort(int arr[],int begin,int end)
{
    int mid;
    if(begin<end)
    {
        mid=(begin+end)/2;
        mergeSort(arr,begin,mid);
        mergeSort(arr,mid+1,end);
        merge(arr,begin,mid,end);
    }
}

int main()
{
    int a[8]={5,2,4,7,1,3,2,6};
    int b[8]={5,2,4,7,1,3,2,6};
    int c[8]={5,2,4,7,1,3,2,6};
    int d[8]={5,2,4,7,1,3,2,6};

    int i;
    /*測試插入排序*/
    insertSort(a,8);
    printf("after 插入排序\n");
    for(i=0;i<8;i++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");

    /*測試選擇排序*/
    selectSort(b,8);
    printf("after 選擇排序\n");
    for(i=0;i<8;i++)
    {
        printf("%d ",b[i]);
    }
    printf("\n");

    /*測試冒泡排序*/
    bubbleSort(c,8);
    printf("after 冒泡排序\n");
    for(i=0;i<8;i++)
    {
        printf("%d ",c[i]);
    }
    printf("\n");

    /*測試歸并排序*/
    mergeSort(d,0,7);

    printf("after 歸并排序\n");
    for(i=0;i<8;i++)
    {
        printf("%d ",d[i]);
    }
    printf("\n");
}

posted @ 2011-03-15 16:15 周強閱讀(5355) | 評論 (0) | 編輯收藏

KMP算法實現

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

/*naive string-matching algorithm,T為原始字符串，P為需要匹配的字符串*/
void naiveMatch(char *T,char *P)
{
    int lenT,lenP,i,j;
    lenT=strlen(T);
    lenP=strlen(P);
    if(lenT<lenP)/*需要匹配的字符串比原始字符串還要長出錯*/
    {
        perror("input error");
        return ;
    }
    for(i=0;i<(lenT-lenP+1);i++)
    {
        for(j=0;j<lenP;j++)
        {
            if(T[i+j]!=P[j])
                break;
        }
        if(j==lenP)
            printf("string match at place %d\n",i);
    }
}

/*kmp預處理需要的匹配串*/
void getNext(char *p,int next[])
{
    int len,i,j;
    len=strlen(p);
    next[0]=0;
    for(i=1;i<len;i++)
    {
        j=next[i-1];
        while((p[i-1]!=p[j-1])&&(j!=0))
        {
            j=next[j-1];
//            printf("j= %d\n",j);
        }
        next[i]=j+1;
        printf("next[i]=%d\n",next[i]);
    }
}

/*kmp字符串匹配算法*/
void kmp(char *t,char *p,int next[])
{
    int lent,lenp,i,j;
    lent=strlen(t);
    lenp=strlen(p);
    i=0;
    j=0;
    while(i<(lent))
    {
        if((j==-1)||(t[i]==p[j]))
        {
            i++;
            j++;

//            printf("i=%d,j=%d\n",i,j);
        }
        else
        {

//            printf("in else i=%d,j=%d\n",i,j);
            j=next[j]-1;
        }
        if(j==(lenp))
        {
            printf("match at place %d\n",i-lenp);
        }
    }
}

int main()
{
    char p[10]="0001";
    char t[20]="000010001010001";
    naiveMatch(t,p);/*測試普通字符串匹配算法*/
    char p1[10]="abaabcac";
    char t1[20]="acabaabaabcacaabc";
    int len=strlen(p1);
    int *next;
    next=(int*)malloc(sizeof(int)*len);
    getNext(p1,next);
    kmp(t1,p1,next);/*測試kmp算法*/

    getNext(p,next);
    kmp(t,p,next);/*測試kmp算法*/
}

posted @ 2011-03-02 12:23 周強閱讀(391) | 評論 (0) | 編輯收藏

epoll模型（轉載）

epoll精髓

在linux的網絡編程中，很長的時間都在使用select來做事件觸發。在linux新的內核中，有了一種替換它的機制，就是epoll。
相比于select，epoll最大的好處在于它不會隨著監聽fd數目的增長而降低效率。因為在內核中的select實現中，它是采用輪詢來處理的，輪詢的fd數目越多，自然耗時越多。并且，在linux/posix_types.h頭文件有這樣的聲明：
#define __FD_SETSIZE    1024
表示select最多同時監聽1024個fd，當然，可以通過修改頭文件再重編譯內核來擴大這個數目，但這似乎并不治本。

epoll的接口非常簡單，一共就三個函數：
1. int epoll_create(int size);
創建一個epoll的句柄，size用來告訴內核這個監聽的數目一共有多大。這個參數不同于select()中的第一個參數，給出最大監聽的fd+1的值。需要注意的是，當創建好epoll句柄后，它就是會占用一個fd值，在linux下如果查看/proc/進程id/fd/，是能夠看到這個fd的，所以在使用完epoll后，必須調用close()關閉，否則可能導致fd被耗盡。

2. int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event);
epoll的事件注冊函數，它不同與select()是在監聽事件時告訴內核要監聽什么類型的事件，而是在這里先注冊要監聽的事件類型。第一個參數是epoll_create()的返回值，第二個參數表示動作，用三個宏來表示：
EPOLL_CTL_ADD：注冊新的fd到epfd中；
EPOLL_CTL_MOD：修改已經注冊的fd的監聽事件；
EPOLL_CTL_DEL：從epfd中刪除一個fd；
第三個參數是需要監聽的fd，第四個參數是告訴內核需要監聽什么事，struct epoll_event結構如下：
struct epoll_event {
__uint32_t events; /* Epoll events */
epoll_data_t data; /* User data variable */
};

events可以是以下幾個宏的集合：
EPOLLIN ：表示對應的文件描述符可以讀（包括對端SOCKET正常關閉）；
EPOLLOUT：表示對應的文件描述符可以寫；
EPOLLPRI：表示對應的文件描述符有緊急的數據可讀（這里應該表示有帶外數據到來）；
EPOLLERR：表示對應的文件描述符發生錯誤；
EPOLLHUP：表示對應的文件描述符被掛斷；
EPOLLET：將EPOLL設為邊緣觸發(Edge Triggered)模式，這是相對于水平觸發(Level Triggered)來說的。
EPOLLONESHOT：只監聽一次事件，當監聽完這次事件之后，如果還需要繼續監聽這個socket的話，需要再次把這個socket加入到EPOLL隊列里

3. int epoll_wait(int epfd, struct epoll_event * events, int maxevents, int timeout);
等待事件的產生，類似于select()調用。參數events用來從內核得到事件的集合，maxevents告之內核這個events有多大，這個 maxevents的值不能大于創建epoll_create()時的size，參數timeout是超時時間（毫秒，0會立即返回，-1將不確定，也有說法說是永久阻塞）。該函數返回需要處理的事件數目，如返回0表示已超時。

--------------------------------------------------------------------------------------------

從man手冊中，得到ET和LT的具體描述如下

EPOLL事件有兩種模型：
Edge Triggered (ET)
Level Triggered (LT)

假如有這樣一個例子：
1. 我們已經把一個用來從管道中讀取數據的文件句柄(RFD)添加到epoll描述符
2. 這個時候從管道的另一端被寫入了2KB的數據
3. 調用epoll_wait(2)，并且它會返回RFD，說明它已經準備好讀取操作
4. 然后我們讀取了1KB的數據
5. 調用epoll_wait(2)......

Edge Triggered 工作模式：
如果我們在第1步將RFD添加到epoll描述符的時候使用了EPOLLET標志，那么在第5步調用epoll_wait(2)之后將有可能會掛起，因為剩余的數據還存在于文件的輸入緩沖區內，而且數據發出端還在等待一個針對已經發出數據的反饋信息。只有在監視的文件句柄上發生了某個事件的時候 ET 工作模式才會匯報事件。因此在第5步的時候，調用者可能會放棄等待仍在存在于文件輸入緩沖區內的剩余數據。在上面的例子中，會有一個事件產生在RFD句柄上，因為在第2步執行了一個寫操作，然后，事件將會在第3步被銷毀。因為第4步的讀取操作沒有讀空文件輸入緩沖區內的數據，因此我們在第5步調用 epoll_wait(2)完成后，是否掛起是不確定的。epoll工作在ET模式的時候，必須使用非阻塞套接口，以避免由于一個文件句柄的阻塞讀/阻塞寫操作把處理多個文件描述符的任務餓死。最好以下面的方式調用ET模式的epoll接口，在后面會介紹避免可能的缺陷。
   i    基于非阻塞文件句柄
   ii   只有當read(2)或者write(2)返回EAGAIN時才需要掛起，等待。但這并不是說每次read()時都需要循環讀，直到讀到產生一個EAGAIN才認為此次事件處理完成，當read()返回的讀到的數據長度小于請求的數據長度時，就可以確定此時緩沖中已沒有數據了，也就可以認為此事讀事件已處理完成。

Level Triggered 工作模式
相反的，以LT方式調用epoll接口的時候，它就相當于一個速度比較快的poll(2)，并且無論后面的數據是否被使用，因此他們具有同樣的職能。因為即使使用ET模式的epoll，在收到多個chunk的數據的時候仍然會產生多個事件。調用者可以設定EPOLLONESHOT標志，在 epoll_wait(2)收到事件后epoll會與事件關聯的文件句柄從epoll描述符中禁止掉。因此當EPOLLONESHOT設定后，使用帶有 EPOLL_CTL_MOD標志的epoll_ctl(2)處理文件句柄就成為調用者必須作的事情。

然后詳細解釋ET, LT:

LT(level triggered)是缺省的工作方式，并且同時支持block和no-block socket.在這種做法中，內核告訴你一個文件描述符是否就緒了，然后你可以對這個就緒的fd進行IO操作。如果你不作任何操作，內核還是會繼續通知你的，所以，這種模式編程出錯誤可能性要小一點。傳統的select/poll都是這種模型的代表．

ET(edge-triggered) 是高速工作方式，只支持no-block socket。在這種模式下，當描述符從未就緒變為就緒時，內核通過epoll告訴你。然后它會假設你知道文件描述符已經就緒，并且不會再為那個文件描述符發送更多的就緒通知，直到你做了某些操作導致那個文件描述符不再為就緒狀態了(比如，你在發送，接收或者接收請求，或者發送接收的數據少于一定量時導致了一個EWOULDBLOCK 錯誤）。但是請注意，如果一直不對這個fd作IO操作(從而導致它再次變成未就緒)，內核不會發送更多的通知(only once),不過在TCP協議中，ET模式的加速效用仍需要更多的benchmark確認（這句話不理解）。

在許多測試中我們會看到如果沒有大量的idle -connection或者dead-connection，epoll的效率并不會比select/poll高很多，但是當我們遇到大量的idle- connection(例如WAN環境中存在大量的慢速連接)，就會發現epoll的效率大大高于select/poll。（未測試）

另外，當使用epoll的ET模型來工作時，當產生了一個EPOLLIN事件后，
讀數據的時候需要考慮的是當recv()返回的大小如果等于請求的大小，那么很有可能是緩沖區還有數據未讀完，也意味著該次事件還沒有處理完，所以還需要再次讀取：
while(rs)
{
buflen = recv(activeevents[i].data.fd, buf, sizeof(buf), 0);
if(buflen < 0)
{
    // 由于是非阻塞的模式,所以當errno為EAGAIN時,表示當前緩沖區已無數據可讀
    // 在這里就當作是該次事件已處理處.
    if(errno == EAGAIN)
     break;
    else
     return;
   }
   else if(buflen == 0)
   {
     // 這里表示對端的socket已正常關閉.
   }
   if(buflen == sizeof(buf)
     rs = 1;   // 需要再次讀取
   else
     rs = 0;
}

還有，假如發送端流量大于接收端的流量(意思是epoll所在的程序讀比轉發的socket要快),由于是非阻塞的socket,那么send()函數雖然返回,但實際緩沖區的數據并未真正發給接收端,這樣不斷的讀和發，當緩沖區滿后會產生EAGAIN錯誤(參考man send),同時,不理會這次請求發送的數據.所以,需要封裝socket_send()的函數用來處理這種情況,該函數會盡量將數據寫完再返回，返回 -1表示出錯。在socket_send()內部,當寫緩沖已滿(send()返回-1,且errno為EAGAIN),那么會等待后再重試.這種方式并不很完美,在理論上可能會長時間的阻塞在socket_send()內部,但暫沒有更好的辦法.

ssize_t socket_send(int sockfd, const char* buffer, size_t buflen)
{
ssize_t tmp;
size_t total = buflen;
const char *p = buffer;

while(1)
{
    tmp = send(sockfd, p, total, 0);
    if(tmp < 0)
    {
      // 當send收到信號時,可以繼續寫,但這里返回-1.
      if(errno == EINTR)
        return -1;

      // 當socket是非阻塞時,如返回此錯誤,表示寫緩沖隊列已滿,
      // 在這里做延時后再重試.
      if(errno == EAGAIN)
      {
        usleep(1000);
        continue;
      }

      return -1;
    }

    if((size_t)tmp == total)
      return buflen;

    total -= tmp;
    p += tmp;
}

return tmp;
}

posted @ 2011-03-02 12:23 周強閱讀(385) | 評論 (0) | 編輯收藏

epoll模型實例（轉載）

epoll學習筆記

epoll有兩種模式,Edge Triggered(簡稱ET) 和 Level Triggered(簡稱LT).在采用這兩種模式時要注意的是,如果采用ET模式,那么僅當狀態發生變化時才會通知,而采用LT模式類似于原來的 select/poll操作,只要還有沒有處理的事件就會一直通知.

以代碼來說明問題:
首先給出server的代碼,需要說明的是每次accept的連接,加入可讀集的時候采用的都是ET模式,而且接收緩沖區是5字節的,也就是每次只接收5字節的數據:

#include < iostream >
#include < sys / socket.h >
#include < sys / epoll.h >
#include < netinet / in.h >
#include < arpa / inet.h >
#include < fcntl.h >
#include < unistd.h >
#include < stdio.h >
#include < errno.h >

using namespace std;

#define MAXLINE 5
#define OPEN_MAX 100
#define LISTENQ 20
#define SERV_PORT 5000
#define INFTIM 1000

void setnonblocking( int sock)
{
     int opts;
    opts = fcntl(sock,F_GETFL);
     if (opts < 0 )
    {
        perror( " fcntl(sock,GETFL) " );
         exit ( 1 );
    }
    opts = opts|O_NONBLOCK;
     if (fcntl(sock,F_SETFL,opts) < 0 )
    {
        perror( " fcntl(sock,SETFL,opts) " );
         exit ( 1 );
    }
}

int main()
{
     int i, maxi, listenfd, connfd, sockfd,epfd,nfds;
    ssize_t n;
    char line[MAXLINE];
    socklen_t clilen;
     // 聲明epoll_event結構體的變量,ev用于注冊事件,數組用于回傳要處理的事件
    struct epoll_event ev,events[ 20 ];
     // 生成用于處理accept的epoll專用的文件描述符
    epfd = epoll_create( 256 );
    struct sockaddr_in clientaddr;
    struct sockaddr_in serveraddr;
    listenfd = socket(AF_INET, SOCK_STREAM, 0 );
     // 把socket設置為非阻塞方式
     // setnonblocking(listenfd);
     // 設置與要處理的事件相關的文件描述符
    ev.data.fd = listenfd;
     // 設置要處理的事件類型
    ev.events = EPOLLIN|EPOLLET;
     // ev.events = EPOLLIN;
     // 注冊epoll事件
    epoll_ctl(epfd,EPOLL_CTL_ADD,listenfd, & ev);
    bzero( & serveraddr, sizeof(serveraddr));
    serveraddr.sin_family = AF_INET;
    char * local_addr = " 127.0.0.1 " ;
    inet_aton(local_addr, & (serveraddr.sin_addr)); // htons(SERV_PORT);
    serveraddr.sin_port = htons(SERV_PORT);
    bind(listenfd,(sockaddr * ) & serveraddr, sizeof(serveraddr));
    listen(listenfd, LISTENQ);
    maxi = 0 ;
     for ( ; ; ) {
         // 等待epoll事件的發生
        nfds = epoll_wait(epfd,events, 20 , 500 );
         // 處理所發生的所有事件
         for (i = 0 ;i < nfds; ++ i)
        {
             if (events[i].data.fd == listenfd)
            {

                clilen=sizeof(struct sockaddr);
                connfd = accept(listenfd,(struct sockaddr * ) & clientaddr, & clilen);
                 if (connfd < 0 ){
                    perror( " connfd<0 " );
                     exit ( 1 );
                }
                 // setnonblocking(connfd);
                char * str = inet_ntoa(clientaddr.sin_addr);
                cout << " accapt a connection from " << str << endl;
                 // 設置用于讀操作的文件描述符
                ev.data.fd = connfd;
                 // 設置用于注測的讀操作事件
                ev.events = EPOLLIN|EPOLLET;
                 // ev.events = EPOLLIN;
                 // 注冊ev
                epoll_ctl(epfd,EPOLL_CTL_ADD,connfd, & ev);
            }
             else if (events[i].events & EPOLLIN)
            {
                cout << " EPOLLIN " << endl;
                 if ( (sockfd = events[i].data.fd) < 0 )
                    continue;
                 if ( (n = read(sockfd, line, MAXLINE)) < 0 ) {
                     if (errno == ECONNRESET) {
                        close(sockfd);
                        events[i].data.fd = - 1 ;
                    } else
                        std::cout << " readline error " << std::endl;
                } else if (n == 0 ) {
                    close(sockfd);
                    events[i].data.fd = - 1 ;
                }
                line[n] = ' \0';
                cout << " read " << line << endl;
                 // 設置用于寫操作的文件描述符
                ev.data.fd = sockfd;
                 // 設置用于注測的寫操作事件
                ev.events = EPOLLOUT|EPOLLET;
                 // 修改sockfd上要處理的事件為EPOLLOUT
                 // epoll_ctl(epfd,EPOLL_CTL_MOD,sockfd, & ev);
            }
             else if (events[i].events & EPOLLOUT)
            {
                sockfd = events[i].data.fd;
                write(sockfd, line, n);
                 // 設置用于讀操作的文件描述符
                ev.data.fd = sockfd;
                 // 設置用于注測的讀操作事件
                ev.events = EPOLLIN|EPOLLET;
                 // 修改sockfd上要處理的事件為EPOLIN
                epoll_ctl(epfd,EPOLL_CTL_MOD,sockfd, & ev);
            }
        }
    }
    return 0 ;
}

下面給出測試所用的Perl寫的client端,在client中發送10字節的數據,同時讓client在發送完數據之后進入死循環, 也就是在發送完之后連接的狀態不發生改變--既不再發送數據, 也不關閉連接,這樣才能觀察出server的狀態:

#! / usr / bin / perl

use IO::Socket;

my $host = " 127.0.0.1 " ;
my $port = 5000 ;

my $socket = IO::Socket::INET -> new ( " $host:$port " ) or die " create socket error $@ " ;
my $msg_out = " 1234567890 " ;
print $socket $msg_out;
print " now send over, go to sleep

\n " ;

while ( 1 )
{
sleep( 1 );
}

運行server和client發現,server僅僅讀取了5字節的數據,而client其實發送了10字節的數據,也就是說,server僅當第一次監聽到了EPOLLIN事件,由于沒有讀取完數據,而且采用的是ET模式,狀態在此之后不發生變化,因此server再也接收不到EPOLLIN事件了.
(友情提示:上面的這個測試客戶端,當你關閉它的時候會再次出發IO可讀事件給server,此時server就會去讀取剩下的5字節數據了,但是這一事件與前面描述的ET性質并不矛盾.)

如果我們把client改為這樣:

#! / usr / bin / perl

use IO::Socket;

my $host = " 127.0.0.1 " ;
my $port = 5000 ;

my $socket = IO::Socket::INET -> new ( " $host:$port " ) or die " create socket error $@ " ;
my $msg_out = " 1234567890 " ;
print $socket $msg_out;
print " now send over, go to sleep

\n " ;
sleep( 5 );
print " 5 second gone

send another line\n " ;
print $socket $msg_out;

while ( 1 )
{
sleep( 1 );
}

可以發現,在server接收完5字節的數據之后一直監聽不到client的事件,而當client休眠5秒之后重新發送數據,server再次監聽到了變化,只不過因為只是讀取了5個字節,仍然有10個字節的數據(client第二次發送的數據)沒有接收完.

如果上面的實驗中,對accept的socket都采用的是LT模式,那么只要還有數據留在buffer中,server就會繼續得到通知,讀者可以自行改動代碼進行實驗.

基于這兩個實驗,可以得出這樣的結論:ET模式僅當狀態發生變化的時候才獲得通知,這里所謂的狀態的變化并不包括緩沖區中還有未處理的數據,也就是說,如果要采用ET模式,需要一直read/write直到出錯為止,很多人反映為什么采用ET模式只接收了一部分數據就再也得不到通知了,大多因為這樣;而LT 模式是只要有數據沒有處理就會一直通知下去的.

補充說明一下這里一直強調的"狀態變化"是什么:

1)對于監聽可讀事件時,如果是socket是監聽socket,那么當有新的主動連接到來為狀態發生變化;對一般的socket而言,協議棧中相應的緩沖區有新的數據為狀態發生變化.但是,如果在一個時間同時接收了N個連接(N>1),但是監聽socket只accept了一個連接,那么其它未 accept的連接將不會在ET模式下給監聽socket發出通知,此時狀態不發生變化;對于一般的socket,就如例子中而言,如果對應的緩沖區本身已經有了N字節的數據,而只取出了小于N字節的數據,那么殘存的數據不會造成狀態發生變化.

2)對于監聽可寫事件時,同理可推,不再詳述.

而不論是監聽可讀還是可寫,對方關閉socket連接都將造成狀態發生變化,比如在例子中,如果強行中斷client腳本,也就是主動中斷了socket連接,那么都將造成server端發生狀態的變化,從而server得到通知,將已經在本方緩沖區中的數據讀出.

把前面的描述可以總結如下:僅當對方的動作(發出數據,關閉連接等)造成的事件才能導致狀態發生變化,而本方協議棧中已經處理的事件(包括接收了對方的數據,接收了對方的主動連接請求)并不是造成狀態發生變化的必要條件,狀態變化一定是對方造成的.所以在ET模式下的,必須一直處理到出錯或者完全處理完畢,才能進行下一個動作,否則可能會發生錯誤.

另外,從這個例子中,也可以闡述一些基本的網絡編程概念.首先,連接的兩端中,一端發送成功并不代表著對方上層應用程序接收成功, 就拿上面的client測試程序來說,10字節的數據已經發送成功,但是上層的server并沒有調用read讀取數據,因此發送成功僅僅說明了數據被對方的協議棧接收存放在了相應的buffer中,而上層的應用程序是否接收了這部分數據不得而知;同樣的,讀取數據時也只代表著本方協議棧的對應 buffer中有數據可讀,而此時時候在對端是否在發送數據也不得而知.

posted @ 2011-03-02 12:22 周強閱讀(636) | 評論 (0) | 編輯收藏

筆試題2（轉載）

筆試題二（轉）

給定九個數，例如：1，3，3，5，6，7，8，8，9計算出這九個數的排列的種數。需要考慮重復情況，如果給定9個1，則只有一種結果。
限制：不能使用stl庫
要求：完成函數 unsigned int foo(unsigned int *arr);
輸入算法代碼，并給出算法復雜度分析。

分析：

#include <cstdlib>
#include <iostream>

using namespace std;
unsigned int foo(unsigned int *arr)
{
    unsigned int p[] ={1,2,6,24,120,720,5040,40320,362880};
    unsigned int i,j,c,s=p[8];//first the number is p^9₉
    for(i = 0; i < 7; i++)
       for(j = i+1; j < 8; j++)
       {
           if(arr[i]>arr[j]) //swap two number
           {
               arr[i]^=arr[j];
               arr[j]^=arr[i];
               arr[i]^=arr[j];
           }
       }
    i = 0;
    c = 0;
    while(i<8)
    {
        j = i+1;
        while(arr[i]==arr[j])//compute the number of the repetition
        {
            c++;
            j++;
        }
        s/=p[c];
        c=0;
        i=j;
    }
    return s;
}

int main()
{
    unsigned int a[]={1,3,3,5,6,7,8,8,9};
    cout<<"The number of permutation is: "<<foo(a)<<endl;
    system("pause");
    return 0;
}
還可以改進排序那部分。

轉一個經典的題目：

給一個天平,問如何用3次把這個小球找出來
并且求出這個小球是比其他的輕還是重
將12個球分別編號為a1,a2,a3.......a10,a11,a12.
第一步：將12球分開3撥，每撥4個，a1~a4第一撥，記為b1， a5~a8第2撥，記為b2，其余第3撥，記為b3；
第二步：將b1和b2放到天平兩盤上，記左盤為c1，右為c2；這時候分兩中情況：

1.c1和c2平衡，此時可以確定從a1到a8都是常球；然后把c2拿空，并從c1上拿下a4，從a9到a12四球里隨便取三球，假設為a9到a11，放到c2上。此時c1上是a1到a3，c2上是a9到a11。從這里又分三種情況：
     A：天平平衡，很簡單，說明沒有放上去的a12就是異球，而到此步一共稱了兩次，所以將a12隨便跟11個常球再稱一次，也就是第三次，馬上就可以確定a12是重還是輕；
     B：若c1上升，則這次稱說明異球為a9到a11三球中的一個，而且是比常球重。取下c1所有的球，并將a8放到c1上，將a9取下，比較a8和a11（第三次稱），如果平衡則說明從c2上取下的a9是偏重異球，如果不平衡，則偏向哪盤則哪盤里放的就是偏重異球；
     C：若c1下降，說明a9到a11里有一個是偏輕異球。次種情況和B類似，所以接下來的步驟照搬B就是；

2.c1和c2不平衡，這時候又分兩種情況，c1上升和c1下降，但是不管哪種情況都能說明a9到a12是常球。這步是解題的關鍵。也是這個題最妙的地方。
     A：c1上升，此時不能判斷異球在哪盤也不能判斷是輕還是重。取下c1中的a2到a4三球放一邊，將c2中的a5和a6放到c1上，然后將常球a9放到c2上。至此，c1上是a1，a5和a6，c2上是a7，a8和a9。此時又分三中情況：
         1）如果平衡，說明天平上所有的球都是常球，異球在從c1上取下a2到a4中。而且可以斷定異球輕重。因為a5到a8都是常球，而第2次稱的時候c1是上升的，所以a2到a4里必然有一個輕球。那么第三次稱就用來從a2到a4中找到輕球。這很簡單，隨便拿兩球放到c1和c2，平衡則剩余的為要找球，不平衡則哪邊低則哪個為要找球；
         2）c1仍然保持上升，則說明要么a1是要找的輕球，要么a7和a8兩球中有一個是重球（這步懂吧？好好想想，很簡單的。因為a9是常球，而取下的a2到a4肯定也是常球，還可以推出換盤放置的a5和a6也是常球。所以要么a1輕，要么a7或a8重）。至此，還剩一次稱的機會。只需把a7和a8放上兩盤，平衡則說明a1是要找的偏輕異球，如果不平衡，則哪邊高說明哪個是偏重異球；
         3）如果換球稱第2次后天平平衡打破，并且c1降低了，這說明異球肯定在換過來的a5和a6兩求中，并且異球偏重，否則天平要么平衡要么保持c1上升。確定要找球是偏重之后，將a5和a6放到兩盤上稱第3次根據哪邊高可以判定a5和a6哪個是重球；
     B：第1次稱后c1是下降的，此時可以將c1看成c2，其實以后的步驟都同A，所以就不必要再重復敘述了。至此，不管情況如何，用且只用三次就能稱出12個外觀手感一模一樣的小球中有質量不同于其他11球的偏常的球。而且在稱的過程中可以判定其是偏輕還是偏重。

3.U2 合唱團在17 分鐘內得趕到演唱會場，途中必需跨過一座橋，四個人從橋的同一端出發，你得幫助他們到達另一端，天色很暗，而他們只有一只手電筒。一次同時最多可以有兩人一起過橋，而過橋的時候必須持有手電筒，所以就得有人把手電筒帶來帶去，來回橋兩端。手電筒是不能用丟的方式來傳遞的。四個人的步行速度各不同，若兩人同行則以較慢者的速度為準。Bono 需花1 分鐘過橋，Edge 需花2 分鐘過橋，Adam需花 5 分鐘過橋，Larry 需花10 分鐘過橋。他們要如何在17 分鐘內過橋呢？（有個同濟的學生寫文章說他當時在微軟面試時就是碰到了這道題，最短只能做出在19分鐘內過橋，微軟的人對他講這樣的結果已經是不錯的了！）
A點到 B 點
1 和2 過去 2 分鐘 2
2 過來 4 分鐘 2+2=4
10和 5過去 14 分鐘 4+10=14
1 過來 15 分鐘 14+1=15
1 和2 過去 17 分鐘 15+2=17

第一組
　　1.燒一根不均勻的繩，從頭燒到尾總共需要1個小時。現在有若干條材質相同的繩子，問如何用燒繩的方法來計時一個小時十五分鐘呢?
       ans:三根繩，開始的時候，第一根點燃兩端，第二根點燃一端，第三根不點。第一根繩燒完(30分鐘)后，點燃第二根繩的另一端，第二根只要15分鐘就可以燒完了，第二根繩燒完(45分鐘)后，點燃第三根繩子兩端，第三根繩燒完(1小時15分)后，計時完成

　　2.你有一桶果凍，其中有黃色、綠色、紅色三種，閉上眼睛抓取同種顏色的兩個。抓取多少個就可以確定你肯定有兩個同一顏色的果凍?

　　3.如果你有無窮多的水，一個3公升的提捅，一個5公升的提捅，兩只提捅形狀上下都不均勻，問你如何才能準確稱出4公升的水?

　　4.一個岔路口分別通向誠實國和說謊國。來了兩個人，已知一個是誠實國的，另一個是說謊國的。誠實國永遠說實話，說謊國永遠說謊話。現在你要去說謊國，但不知道應該走哪條路，需要問這兩個人。請問應該怎么問?

　　5.12個球一個天平，現知道只有一個和其它的重量不同，問怎樣稱才能用三次就找到那個球。13個呢?(注意此題并未說明那個球的重量是輕是重，所以需要仔細考慮)

　　6.在9個點上畫10條直線，要求每條直線上至少有三個點?

　　7.在一天的24小時之中，時鐘的時針、分針和秒針完全重合在一起的時候有幾次?都分別是什么時間?你怎樣算出來的?

　　8.怎么樣種植4棵樹木，使其中任意兩棵樹的距離相等?

　　第二組

　　1.為什么下水道的蓋子是圓的?

　　2.中國有多少輛汽車?

　　3.將汽車鑰匙插入車門，向哪個方向旋轉就可以打開車鎖?

　　4.如果你要去掉中國的34個省(含自治區、直轄市和港澳特區及臺灣省)中的任何一個，你會去掉哪一個，為什么?

　　5.多少個加油站才能滿足中國的所有汽車?

　　6.想象你站在鏡子前，請問，為什么鏡子中的影象可以顛倒左右，卻不能顛倒上下?

　　7.為什么在任何旅館里，你打開熱水，熱水都會瞬間傾瀉而出?

　　8.你怎樣將Excel的用法解釋給你的奶奶聽?

　　9.你怎樣重新改進和設計一個ATM銀行自動取款機?

　　10.如果你不得不重新學習一種新的計算機語言，你打算怎樣著手來開始?

　　11.如果你的生涯規劃中打算在5年內受到獎勵，那獲取該項獎勵的動機是什么?觀眾是誰?

　　12.如果微軟告訴你，我們打算投資五百萬美元來啟動你的投資計劃，你將開始什么樣商業計劃?為什么?

　　13.如果你能夠將全世界的電腦廠商集合在一個辦公室里，然后告訴他們將被強迫做一件事，那件事將是什么?　

第三組

　　1.你讓工人為你工作7天，回報是一根金條，這個金條平分成相連的7段，你必須在每天結束的時候給他們一段金條。如果只允許你兩次把金條弄斷，你如何給你的工人付費?

2.有一輛火車以每小時15公里的速度離開北京直奔廣州，同時另一輛火車每小時20公里的速度從廣州開往北京。如果有一只鳥，以30公里每小時的速度和兩輛火車同時啟動，從北京出發，碰到另一輛車后就向相反的方向返回去飛，就這樣依次在兩輛火車之間來回地飛，直到兩輛火車相遇。請問，這只鳥共飛行了多長的距離?

　　3.你有四個裝藥丸的罐子，每個藥丸都有一定的重量，被污染的藥丸是沒被污染的藥丸的重量+1。只稱量一次，如何判斷哪個罐子的藥被污染了?

　　4.門外三個開關分別對應室內三盞燈，線路良好，在門外控制開關時候不能看到室內燈的情況，現在只允許進門一次，確定開關和燈的對應關系?

　　5.人民幣為什么只有1、2、5、10的面值?

　　6.你有兩個罐子以及50個紅色彈球和50個藍色彈球，隨機選出一個罐子，隨機選出一個彈球放入罐子，怎么給出紅色彈球最大的選中機會?在你的計劃里，得到紅球的幾率是多少?

　　7.給你兩顆6面色子，可以在它們各個面上刻上0-9任意一個數字，要求能夠用它們拼出任意一年中的日期數值

　　第四組

　　第一題 . 五個海盜搶到了100顆寶石，每一顆都一樣大小和價值連城。他們決定這么分：

　　抽簽決定自己的號碼(1、2、3、4、5)

　　首先，由1號提出分配方案，然后大家表決，當且僅當超過半數的人同意時，按照他的方案

　　進行分配，否則將被扔進大海喂鯊魚

　　如果1號死后，再由2號提出分配方案，然后剩下的4人進行表決，當且僅當超過半數的人同

　　意時，按照他的方案進行分配，否則將被扔入大海喂鯊魚

　　依此類推

　　條件：每個海盜都是很聰明的人，都能很理智地做出判斷，從而做出選擇。

　　問題：第一個海盜提出怎樣的分配方案才能使自己的收益最大化?

　　第二題 . 一道關于飛機加油的問題，已知：

　　每個飛機只有一個油箱，

　　飛機之間可以相互加油(注意是相互，沒有加油機)

　　一箱油可供一架飛機繞地球飛半圈，

　　問題：

　　為使至少一架飛機繞地球一圈回到起飛時的飛機場，至少需要出動幾架飛機?(所有飛機從同一機場起飛，而且必須安全返回機場，不允許中途降落，中間沒有飛機場)第三題. 汽車加油問題

　　一輛載油500升的汽車從A開往1000公里外的B，已知汽車每公里耗油量為1升，A處有無窮多的油，其他任何地點都沒有油，但該車可以在任何地點存放油以備中轉，問從A到B最少需要多少油

　　第四題. 擲杯問題

　　一種杯子，若在第N層被摔破，則在任何比N高的樓層均會破，若在第M層不破，則在任何比M低的樓層均會破，給你兩個這樣的杯子，讓你在100層高的樓層中測試，要求用最少的測試次數找出恰巧會使杯子破碎的樓層。

　　第五題. 推理游戲

　　教授選出兩個從2到9的數，把它們的和告訴學生甲，把它們的積告訴學生乙，讓他們輪流猜這兩個數

　　甲說：“我猜不出”

　　乙說：“我猜不出”

　　甲說：“我猜到了”

　　乙說：“我也猜到了”

　　問這兩個數是多少

　　第六題. 病狗問題

一個住宅區內有100戶人家，每戶人家養一條狗，每天傍晚大家都在同一個地方遛狗。已知這些狗中有一部分病狗，由于某種原因，狗的主人無法判斷自己的狗是否是病狗，卻能夠分辨其他的狗是否有病，現在，上級傳來通知，要求住戶處決這些病狗，并且不允許指認他人的狗是病狗(就是只能判斷自己的)，過了7天之后，所有的病狗都被處決了，問，一共有幾只病狗?為什么?

　　第八題. 監獄里有100個房間，每個房間內有一囚犯。一天，監獄長說，你們獄房外有一電燈，你們在放風時可以控制這個電燈(熄或亮)。每天只能有一個人出來放風，并且防風是隨機的。如果在有限時間內，你們中的某人能對我說： “我敢保證，現在每個人都已經至少放過一次風了。”我就放了你們!問囚犯們要采取什么策略才能被監獄長放掉?如果采用了這種策略，大致多久他們可以被釋放?

第五組

　　1.某手機廠家由于設計失誤，有可能造成電池壽命比原來設計的壽命短一半(不是沖放電時間)，解決方案就是免費更換電池或給50元購買該廠家新手機的折換券。請給所有已購買的用戶寫信告訴解決方案。

　　2.一高層領導在參觀某博物館時，向博物館館員小王要了一塊明代的城磚作為紀念，按國家規定，任何人不得將博物館收藏品變為私有。博物館館長需要如何寫信給這位領導，將城磚取回。

　　3.營業員小姐由于工作失誤，將2萬元的筆記本電腦以1.2萬元錯賣給李先生，王小姐的經理怎么寫信給李先生試圖將錢要回來?

　　4.給你一款新研制的手機，如果你是測試組的組長，你會如何測試?

　　5.如何為函數int atoi(const char * pstr)編寫測試向量?

　　第六組

　　1.鏈表和數組的區別在哪里?

　　2.編寫實現鏈表排序的一種算法。說明為什么你會選擇用這樣的方法?

　　3.編寫實現數組排序的一種算法。說明為什么你會選擇用這樣的方法?

　　4.請編寫能直接實現char * strcpy(char * pstrDest,const char * pstrSource)函數功能的代碼。

　　5.編寫反轉字符串的程序，要求優化速度、優化空間。

　　6.在鏈表里如何發現循環鏈接?

　　7.給出洗牌的一個算法，并將洗好的牌存儲在一個整形數組里。

　　8.寫一個函數，檢查字符是否是整數，如果是，返回其整數值。(或者：怎樣只用4行代碼

　　9.給出一個函數來輸出一個字符串的所有排列。

　　10.請編寫實現void * malloc(int)內存分配函數功能一樣的代碼。

　　11.給出一個函數來復制兩個字符串A和B。字符串A的后幾個字節和字符串B的前幾個字節重疊。

　　12.怎樣編寫一個程序，把一個有序整數數組放到二叉樹中?

　　13.怎樣從頂部開始逐層打印二叉樹結點數據?請編程。

　　14.怎樣把一個鏈表掉個順序(也就是反序，注意鏈表的邊界條件并考慮空鏈表)? --

　　15.請編寫能直接實現int atoi(const char * pstr)函數功能的代碼

-----------------------------------------------------------------------------------
第一組題答案：

　　
　　2)根據抽屜原理，4個

　　3)3升裝滿;3升-〉5升(全注入);3升裝滿;3升-〉5升(剩1升);5升倒掉;3升-〉5升(注入1升);3升裝滿;3升-〉5升;完成(另：可用回溯法編程求解)

　　4)問其中一人：另外一個人會說哪一條路是通往誠實國的?回答者所指的那條路必然是通往說謊國的。

　　5)12個球：

　　第一次：4，4 如果平了：

　　那么剩下的球中取3放左邊,取3個好球放右邊，稱：

　　如果左邊重，那么取兩個球稱一下，哪個重哪個是次品，平的話第三個重，是次品，輕的話同理

　　如果平了，那么剩下一個次品，還可根據需要稱出次品比正品輕或者重

　　如果不平：

　　那么不妨設左邊重右邊輕，為了便于說明，將左邊4顆稱為重球，右邊4顆稱為輕球，剩下4顆稱為好球

　　取重球2顆，輕球2顆放在左側，右側放3顆好球和一顆輕球

　　如果左邊重

　　稱那兩顆重球，重的一個次品，平的話右邊輕球次品

　　如果右邊重

　　稱左邊兩顆輕球，輕的一個次品

　　如果平

　　稱剩下兩顆重球，重的一個次品，平的話剩下那顆輕球次品

　　13個球：

　　第一次：4，4，如果平了

　　剩5顆球用上面的方法仍舊能找出次品，只是不能知道次品是重是輕

　　如果不平，同上　

6)

　　o o o

　　o o o

　　o o o

　　7)

　　23次，因為分針要轉24圈，時針才能轉1圈，而分針和時針重合兩次之間的間隔顯然>1小時，它們有23次重合機會，每次重合中秒針有一次重合機會，所以是23次

　　重合時間可以對照手表求出，也可列方程求出

　　8)

　　在地球表面種樹，做一個地球內接的正四面體，內接點即為所求

　　第二組無標準答案

　　第三組

　　1. 分成1,2,4三段，第一天給1，第二天給2取回1，第3天給1，第4天給4取回1、2，第5天給1，第6天給2取回1，第七天給1

　　2. 求出火車相遇時間，鳥速乘以時間就是鳥飛行的距離

　　3. 四個罐子中分別取1,2,3,4顆藥丸，稱出比正常重多少，即可判斷出那個罐子的藥被污染

　　4. 三個開關分別：關，開，開10分鐘，然后進屋，暗且涼的為開關1控制的燈，亮的為開關2控制的燈，暗且熱的為開關3控制的燈

　　5. 因為可以用1，2，5，10組合成任何需要的貨幣值，日常習慣為10進制

　　6. 題意不理解...*_*

　　7. 012345 0126(9)78

　　第四組都是很難的題目

　　第一題：97 0 1 2 0 或者 97 0 1 0 2 (提示：可用逆推法求出)

　　第二題：3架飛機5架次，飛法：

ABC 3架同時起飛，1/8處，C給AB加滿油，C返航，1/4處，B給A加滿油，B返航，A到達1/2處，C從機場往另一方向起飛，3/4處，C同已經空油箱的A平分剩余油量，同時B從機場起飛，AC到7/8處同B平分剩余油量，剛好3架飛機同時返航。所以是3架飛機5架次。第三題：需要建立數學模型

　　(提示，嚴格證明該模型最優比較麻煩，但確實可證，大膽猜想是解題關鍵)

　　題目可歸結為求數列 an=500/(2n+1) n=0,1,2,3......的和Sn什么時候大于等于1000,解得n>6

　　當n=6時，S6=977.57

　　所以第一個中轉點離起始位置距離為1000-977.57=22.43公里

　　所以第一次中轉之前共耗油 22.43*(2*7+1)=336.50升

　　此后每次中轉耗油500升

　　所以總耗油量為7*500+336.50=3836.50升

　　第四題：需要建立數學模型

　　題目可歸結為求自然數列的和S什么時候大于等于100，解得n>13

　　第一個杯子可能的投擲樓層分別為：14，27，39，50，60，69，77，84，90，95，99，100

　　第五題：3和4(可嚴格證明)

　　設兩個數為n1，n2，n1>=n2，甲聽到的數為n=n1+n2，乙聽到的數為m=n1*n2

　　證明n1=3，n2=4是唯一解

　　證明：要證以上命題為真，不妨先證n=7

　　1)必要性：

　　i) n>5 是顯然的，因為n<4不可能，n=4或者n=5甲都不可能回答不知道

　　ii) n>6 因為如果n=6的話，那么甲雖然不知道(不確定2+4還是3+3)但是無論是2，4還是3，3乙都不可能說不知道(m=8或者m=9的話乙說不知道是沒有道理的)

iii) n<8 因為如果n>=8的話，就可以將n分解成 n=4+x 和 n=6+(x-2)，那么m可以是4x也可以是6(x-2) 而4x=6(x-2)的必要條件是x=6即n=10，那樣n又可以分解成8+2，所以總之當n>=8時，n至少可以分解成兩種不同的合數之和，這樣乙說不知道的時候，甲就沒有理由馬上說知道。

　　以上證明了必要性

　　2)充分性

　　當n=7時，n可以分解成2+5或3+4

　　顯然2+5不符合題意，舍去，容易判斷出3+4符合題意，m=12，證畢

　　于是得到n=7 m=12 n1=3 n2=4是唯一解。第六題：7只(數學歸納法證明)

　　1)若只有1只病狗，因為病狗主人看不到有其他病狗，必然會知道自己的狗是病狗(前提是一定存在病狗)，所以他會在第一天把病狗處決。

　　2)設有k只病狗的話，會在第k天被處決，那么，如果有k+1只，病狗的主人只會看到k只病狗，而第k天沒有人處決病狗，病狗主人就會在第k+1天知道自己的狗是病狗，于是病狗在第k+1天被處決

　　3)由1)2)得，若有n只病狗，必然在第n天被處決

　　第八題：

　　約定好一個人作為報告人(可以是第一個放風的人)

　　規則如下：

　　1、報告人放風的時候開燈并數開燈次數

　　2、其他人第一次遇到開著燈放風時，將燈關閉

　　3、當報告人第100次開燈的時候，去向監獄長報告，要求監獄長放人......

　　按照概率大約30年后(10000天)他們可以被釋放

　　第五組無標準答案

　　第六組部分題參考答案：

　　4.

char * strcpy(char * pstrDest,const char * pstrSource)
{
assert((pstrDest!=NULL)&&(pstrSource!=NULL));
char * pstr=pstrDest;
while((*(pstrDest++)=*(pstrSource++))!='\0');
        return pstr;
}

　　5.

char * strrev(char * pstr)
{
assert(pstr!=NULL);

char * p=pstr;
char * pret=pstr;
while(*(p++)!='\0');
p--;
char tmp;
while(p>pstr)
{
  tmp=*p;
  *(p--)=*(pstr);
  *(pstr++)=tmp;
}
return pret;

百度筆試題：
IP段格式:ip1 ip2。之間以空格分開，ip形式為X.X.X.X，數據保存在文件中，文件不超過2k行，無序。現在要求編寫算法去掉可重IP，可重有三種形式：包含、交疊、緊靠。

例如，文件內容為：
10.0.0.0 10.0.0.12
10.0.0.5 10.0.0.10    ( <= 包含)
10.0.0.8 10.0.0.15    ( <= 交疊)
10.0.0.15 10.0.0.24   ( <= 緊靠)

最后輸出為:
10.0.0.0 10.0.0.24

code：
/*
**這個函數的作用是將文件中的一行對應的兩個數據轉換成整形的數據
**比如把10.0.0.0 10.0.0.12 轉換后，left=10*2^24,就是10.0.0.0對應的整數，每個數字對應8位，right=left+12
*/
void ParseLine( char line[], size_t length, unsigned int &left, unsigned int &right)
{
    size_t i;
    for( i=0; i<length; i++ )
    {
        if ( line[i]=='.' || line[i]==' ' )//將點變成0
        {
            line[i]=0;
        }
    }
    char *p   = (char*)&left;
    char *num = line;
    for( i=3; i<4; --i ) //size是size_t，而size_t是unsigned int，所以i=0再自減后變成了最大的整數，循環就會終止
    {
// cout<<i<<",";
        *(p+i) = strtol( num, &num ,10 );
        cout<<static_cast<int>(*(p+i))<<",";
        ++num;
// cout<<num<<":";
    }
    cout<<endl;
    p = (char*)&right;
    for( i=3; i<4; --i )
    {
        *(p+i) = strtol( num, &num, 10 );
        ++num;
    }
}

void UniqueSequence( vector<unsigned int> & uSeq, unsigned int left, unsigned int right )
{
    size_t i, lPos=-1, rPos=-1;
    for( i=0; i<uSeq.size(); i++ )
    {
        if( left <= uSeq.at(i) )
        {
            lPos = i;
            break;
        }
    }
    for( ;i<uSeq.size(); i++ )
    {
        if( right<=uSeq.at(i) )
        {
            rPos=i;
            break;
        }
    }
    if( lPos == -1 )
    {
        uSeq.push_back( left );
        uSeq.push_back( right );
        return;
    }

    if( lPos%2 == 0 )
    {
        if( uSeq.at(lPos)==left )
        {
        }
  else
        {
            uSeq.insert( uSeq.begin()+lPos, left );
        }
    }
else
    {
        --lPos;
    }
    if( rPos == -1 )
    {
        uSeq.erase( uSeq.begin()+(lPos+1), uSeq.end() );
        uSeq.push_back(right);
    }
else if( rPos%2 == 0 )
    {
        if( uSeq.at(rPos)== right )
        {
            uSeq.erase( uSeq.begin()+(lPos+1), uSeq.begin()+(rPos+1) );
        }
  else
        {
            uSeq.erase( uSeq.begin()+(lPos+1), uSeq.begin()+rPos );
            uSeq.insert( uSeq.begin()+rPos, right );
        }
    }
else
    {
        uSeq.erase( uSeq.begin()+(lPos+1), uSeq.begin()+rPos );
    }
}

void PrintIP( unsigned int num )
{
    char *p = (char*)&num;
    for( size_t i=3;i>0; --i)
    {
        cout<< (int)p[i]<<".";
    }
    cout<<(int)p[0];
}

#define MAX_BUFFER_LENGTH 100
int main()
{
    unsigned int left, right;
    char buffer[MAX_BUFFER_LENGTH];
    ifstream infile( "test.txt" );
    if( infile.fail() )
    {
        return 0;
    }
    vector<unsigned int> uSeq;
    while( infile.getline(buffer, MAX_BUFFER_LENGTH) )
    {
        ParseLine(buffer, strlen(buffer), left, right);
// cout<<left<<","<<right<<endl;
        UniqueSequence( uSeq, left, right );
  for( size_t i=0; i<uSeq.size(); i+=2 )
    {
        PrintIP(uSeq.at(i) );
        cout<<" ";
        PrintIP(uSeq.at(i+1));
        cout<<endl;
    }
  cout<<endl;
    }
    for( size_t i=0; i<uSeq.size(); i+=2 )
    {
        PrintIP(uSeq.at(i) );
        cout<<" ";
        PrintIP(uSeq.at(i+1));
        cout<<endl;
    }
    return 0;
}

/*long strtol( const char *nptr, char **endptr, int base ),其中nptr是以NULL結尾字符串，endptr是字符串停止掃描的地方（Pointer to character that stops scan），strtol returns the value represented in the string nptr，The strtol function converts nptr to a long. strtol stops reading the string nptr at the first character it cannot recognize as part of a number. This may be the terminating null character, or it may be the first numeric character greater than or equal to base.
string = "-10110134932This stopped it";
l = strtol( string, &stopstring, 10 );
printf( "string = %s", string );
printf("   strtol = %ld", l );
printf("   Stopped scan at: %s", stopstring );
string = "10110134932";
printf( "string = %s\n", string );
/* Convert string using base 2, 4, and 8: */
for( base = 2; base <= 8; base *= 2 )
{
     /* Convert the string: */
     ul = strtoul( string, &stopstring, base );
     printf( "   strtol = %ld (base %d)\n", ul, base );
     printf( "   Stopped scan at: %s\n", stopstring );
}
打印的結果是：
string = -10110134932This stopped it   strtol = -2147483647   Stopped scan at: This stopped itstring = 10110134932
strtol = 45 (base 2)
Stopped scan at: 34932
strtol = 4423 (base 4)
Stopped scan at: 4932
strtol = 2134108 (base 8)
Stopped scan at: 932
*/

5.如果存在兩個變量：a和b，不使用“if”、“?:”、 “switch”和其它的判斷語句，找出兩個數中的最大值。
答案：( ( a + b ) + abs( a - b ) ) / 2

6. 寫一個函數找出一個整數數組中，第二大的數（microsoft）
       const int MINNUMBER = -32767 ;
       int find_sec_max( int data[] , int count)
       {
                int maxnumber = data[0] ;
                int sec_max = MINNUMBER ;
                for ( int i = 1 ; i < count ; i++)
                {
                    if ( data[i] > maxnumber )
                    {
                         sec_max = maxnumber ;
                         maxnumber = data[i] ;
                    }
                    else
                    {
                             if ( data[i] > sec_max )
                                     sec_max = data[i] ;
                    }
                }
                return sec_max ;
        }

posted @ 2011-03-02 12:19 周強閱讀(389) | 評論 (0) | 編輯收藏

筆試題（轉載）

筆試題（轉）

一、如何判斷一個單鏈表是有環的？（注意不能用標志位，最多只能用兩個額外指針）
   struct node { char val; node* next;}
   bool check(const node* head) {} //return false : 無環；true: 有環
    一種O（n）的辦法就是（搞兩個指針，一個每次遞增一步，一個每次遞增兩步，如果有環的話兩者必然重合，反之亦然）：
    bool check(const node* head)
    {
         if(head==NULL)
             return false;
        node *low=head, *fast=head->next;
         while(fast!=NULL && fast->next!=NULL)
        {
               low=low->next;
               fast=fast->next->next;
               if(low==fast)
                    return true;
        }
       return false;
   }

二、刪除一個單項鏈表的最中間的元素，要求時間盡可能短（不能使用兩次循環）
struct link
{
    int data;
    struct link *next;
};
void delMiddle(link *head)
{
   if(head == NULL)
           return;
   else if(head->next == NULL)
    {
           delete head;
           return;
    }
   else
   {
            link *low = head;
            link *fast = head->next;
            while(fast != NULL && fast->next != NULL)
           {
                      fast = fast->next->next;
                      if(fast == NULL)
                                    break;
                       low = low->next;
            }
            link *temp = low->next;
            low->next = low->next->next;
            delete temp;

    }
}
int main()
{
      struct link *head,*l;
       struct link *s;
       head = (link*)malloc(sizeof(link));
       head->data=0;
      head->next = NULL;
       l = head;
      for(int i=1; i<9; i++)
       {
            s = (link*)malloc(sizeof(link));
            s->data = i;
            s->next = NULL;
            l->next= s;
            l = l->next;
      }
       print(head);
      delMiddle(head);
       print(head);
       return 0;
}

三、輸入n，求一個n*n矩陣，規定矩陣沿45度線遞增(威盛)
/**
* 得到如下樣式的二維數組
* zigzag（jpeg編碼里取象素數據的排列順序）
*
*   0, 1, 5, 6,14,15,27,28,
*   2, 4, 7,13,16,26,29,42,
*   3, 8,12,17,25,30,41,43,
*   9,11,18,24,31,40,44,53,
*   10,19,23,32,39,45,52,54,
*   20,22,33,38,46,51,55,60,
*   21,34,37,47,50,56,59,61,
*   35,36,48,49,57,58,62,63
*/
void zigzag(int n)
{
int **a =(int**) malloc(n*sizeof(int *)); //分配空間

if(NULL == a)
  return ;
int i;
for(i = 0; i < n; i++) {
        if((a[i] =(int*) malloc(n * sizeof(int))) == NULL) {
            while(--i>=0)
                free(a[i]);
            free(a);
            return;
        }
    }

bool flag = false; //這個標志位用來判斷是從45度角生成還是225度角生成
int count = 0;
for(i=0; i<n; i++) //生成的上半部分的數據
{

  if(flag)
  {
   for(int r = 0; r<=i; r++)
   {
    a[r][i-r] = count;
    count++;
   }
   flag = false;
  }
  else
  {
   for(int r = i; r>=0; r--)
   {
    a[r][i-r] = count;
    count++;
   }
   flag = true;
  }
}
for(i=n-1; i>=0; i--) //生成的是下半部分的數據
{
// cout<<i<<endl;
  if(flag)
  {
   for(int r = 0; r<=i-1; r++)
   {
    int r1 = n-i+r;       //代表當前行
    int c1 = 2*n-i-1-r1; //代表當前列
    a[r1][c1] = count;
    count++;
   }
   flag = false;
  }
  else
  {
   for(int r = i-1; r>=0; r--)
   {
    cout<<"ddd"<<endl;
    int r1 = n-i+r;
    int c1 = 2*n-i-1-r1;
//   cout<<r1<<","<<c1<<endl;
    a[r1][c1] = count;
    count++;
   }
   flag = true;
  }
}
for(int r = 0; r<n; r++)
{
  for(int c=0; c<n; c++)
   cout<<a[r][c]<<",";
  cout<<endl;
}
}
int main()
{
int n;
cin>>n;
zigzag(n);
return 0;
}
網上還有一個人寫了一個比較巧的算法：
/**
* 得到如下樣式的二維數組
* zigzag（jpeg編碼里取象素數據的排列順序）
*
*   0, 1, 5, 6,14,15,27,28,
*   2, 4, 7,13,16,26,29,42,
*   3, 8,12,17,25,30,41,43,
*   9,11,18,24,31,40,44,53,
*   10,19,23,32,39,45,52,54,
*   20,22,33,38,46,51,55,60,
*   21,34,37,47,50,56,59,61,
*   35,36,48,49,57,58,62,63
*/

#include <stdio.h>
int main()
{
    int N;
    int s, i, j;
    int squa;
    scanf("%d", &N);
    /* 分配空間 */
    int **a = malloc(N * sizeof(int *));
    if(a == NULL)
        return 0;
    for(i = 0; i < N; i++) {
        if((a[i] = malloc(N * sizeof(int))) == NULL) {
            while(--i>=0)
                free(a[i]);
            free(a);
            return 0;
        }
    }
    /* 數組賦值 */
    squa = N*N;
    for(i = 0; i < N; i++)
        for(j = 0; j < N; j++) {
            s = i + j;
            if(s < N)
                a[i][j] = s*(s+1)/2 + (((i+j)%2 == 0)? i : j);
            else {
                s = (N-1-i) + (N-1-j);
                a[i][j] = squa - s*(s+1)/2 - (N - (((i+j)%2 == 0)? i : j));
            }
        }
    /* 打印輸出 */
    for(i = 0; i < N; i++) {
        for(j = 0; j < N; j++)
            printf("%-6d", a[i][j]);
        printf("\n");
    }
    return 0;
}

四、打印1到1000的整數，不能使用流程控制語句(for,while,goto等)也不能使用遞歸
1.
typedef struct _test{
    static int a;
    _test(){
        printf("%d\n",_test::a);
        a++;
    }
}Test;
int Test::a = 1;

int   main()
{
    Test tt[1000];
    return 0;
}
2.
#include <stdio.h>
#define B P,P,P,P,P,P,P,P,P,P
#define P L,L,L,L,L,L,L,L,L,L
#define L I,I,I,I,I,I,I,I,I,I,N
#define I printf( "%3d ",i++)
#define N printf( "\n ")
int main()
{
int i = 1;
B;
}
或
#define A(x) x;x;x;x;x;x;x;x;x;x;
int main ()
{
    int n = 1;
    A(A(A(printf ("%d ", n++))));

    return 0;
}

五、struct S {
int i;
int * p;
};
void main()
{
S s;
int * p = &s.i;
p[0] = 4;
p[1] = 3;
s.p = p;
s.p[1] = 1;
s.p[0] = 2;
}
問程序會在哪一行死掉。（microsoft）
解： S   s;
         int   *   p   =   &s.i;        //s.i的地址存儲在p里
        p[0]   =   4;                    //修改了s.i
         p[1]   =   3;                    //修改了s.p
        s.p   =   p;                    //s.p指向s.i
        s.p[1]   =   1;               //修改s.p本身
        s.p[0]   =   2;               //s.p指向的是0x00000001,嘗試向這里寫,出錯
     s.p[0] = 2; 時出錯
     因為s.p存的是s.i的地址,s.p[1]為s.p,當s.p[1]=1時,s.p此時存放的是1了,而不是地址s.i,故在s.p[0] = 2時出錯.
此時相當于s.p=ox00000001;地址ox0000001 = 2;當然就出錯了

如果語句s.p[0] =2 先于s.p[1]=1則程序就不會出錯.此時語句相當于s.i=2;s.p=1;

六、題目描述：
1. int swap(int *x,int *y)
{
if(x==NULL ¦ ¦ y==NULL)
return -1;
*x += *y;
*y = *x- *y;
*x -= *y;
return 1;
}
請改錯，溢出已經考慮，不是錯誤
2.
void foo(int *x, int *y)
{
*x += *y;
*x += *y;
}
void fun(int *x, int *y)
{
*x += 2 * (*y);
}
問兩個函數是否等價，能否互換
解答：第一題的函數是交換。但假如考慮x, y都是指向同一個變量,結果是這個變量的值為0.
第二題的兩個函數是有區別的,也考慮x,y是指向同一個變量.這樣第一個函數的結果是這個變量的4倍.但第二個函數的結果是變量的3倍.

posted @ 2011-03-02 12:19 周強閱讀(435) | 評論 (0) | 編輯收藏

迅雷面試題（轉載）

1.下列程序的輸出結果為：(B)
#include<iostream.h>
void main()
{
       char* a[ ] = { "hello", "the", "world"};
       char** pa = a;
       pa++;
       cout<<”*pa<<endl;
}
A) theworld    B) the   C) ello    D) ellotheworld

2. 已知二叉樹后序遍歷序列是bfegcda，中序遍歷序列是badefcg，它的前序遍歷序列是：(B)
A) abcdefg     B) abdcefg    C) adbcfeg    D) abecdfg

3. 棧和隊列的共同特點是：(C)
A) 都是先進先出                 B) 都是先進后出
C) 只允許在短點處插入和刪除元素 D) 沒有共同點

4. 下面程序的運行結果為：(A)
#include <iostream.h>
void main()
{
       int a, x;
       for(a = 0, x = 0; a<=1 && !x++; a++)
       {
              a++;
       }
       cout<< a << x <<endl;
}
A) 21             B) 22             C) 32             D) 41

5. 下列選項，不正確的是：(B) while后沒有分號
A) for(int a=1; a<=10; a++);
B) int a=1;
   do
   {
              a++;
   }while(a<=10)
C) int a=1;
   while(a<=10)
   {
          a++;
}
D) for(int a= 1; a<=10; a++)a++;
6. 下面關于數組的初始化正確的是：(B)
A) char str[2] = {“a”,”b”};
B) char str[2][3]={“a”,”b”};
C) char str[2][3]={{‘a’,’b’},{‘e’,’d’},{‘e’,’f’}};
D) char str[] = {“a”, “b”};

7. 下列說法正確的是：(B)
A) 內聯函數在運行時是將該函數的目標代碼插入每個調用該函數的地方
B) 內聯函數在編譯時是將該函數的目標代碼插入每個調用該函數的地方
C) 類的內聯函數必須在類體內定義
D) 類的內聯函數必須在類體外通過關鍵字inline定義

8．下面對靜態成員的描述中，正確的是：(D)
A) 靜態數據成員可以在類體內初始化
B) 靜態數據成員不可以被類的對象調用
C) 靜態數據成員不能受private控制符的作用
D) 靜態數據成員可以直接用類名調用

9. 下列運算符中，在C++語言中不能重載的是：(C)
A) *                B) >=             C) ::              D) delete

10 下面關于多態性的描述，錯誤的是：(C)
A) C++語言的多態性分為編譯時的多態性和運行時的多態性
B) 編譯時的多態性可通過函數重載實現
C) 運行時的多態性可通過模板和虛函數實現 //模板的是編譯時多態性，而虛函數是運行時
D) 實現運行時多態性的機制稱為動態綁定

11. 如果進棧序列為e1,e2,e3,e4,e5,則可能的出棧序列是：(D)
A) e3,e2,e5,e4,e1
B) e2,e3,e5,e4,e1
C)    e3,e2,e4,e5,e1
D) 以上都有可能

12 下面關于類和對象的描述中，錯誤的是：(A)
A) 類就是C語言中的結構體類型，對象就是C語言中的結構體變量
B) 類和對象之間的關系是抽象和具體的關系
C) 對象是類的實例，一個對象必須屬于一個已知的類
D) 類是具有共同行為的若干對象的統一描述體

13.下面關于數組的描述錯誤的是：（D）
A) 在C++語言中數組的名字就是指向該數組第一個元素的指針
B) 長度為n的數組，下標的范圍是0－n-1
C) 數組的大小必須在編譯是確定
D) 數組只能通過值參數和引用參數兩種方式傳遞給函數
注釋：
在把數組作為參數傳遞給函數時，有值傳遞(by value)和地址傳遞(by reference)兩種方式。
    在值傳遞方式中，要在數組參數的尾部加上一對方括號([])，調用函數時只需將數組的地址(即數組名)傳遞給函數。
    例如：如果數組x被聲明為：int x[10];
    那麼函數被說明為：void byval_func(int[]);
    參數int[]告訴編譯程序byval_func()函數只有一個參數,即一個由int型值組成的數組。
函數調用時只需將數組名傳遞給函數:byval_func(x);
#include <stdio.h>
void byval_func(int[]);
void main(void);
void main(void)
{
     int x[10];
     int y;
     for(y=0;y<10;y++)
         x[y]=y;
     byval_func(x);
}
void byal_func(int i[])
{
     int y;
     for(y=0;y<10;y++)
        printf("%d\n",i[y]);
}
在值傳遞方式中,數組x將被復制一份,復制所得的數組將被存放在棧中,然后由byval_func()函數接收并打印出來。由於傳遞給 byval_func()函數的是初始數組的一份拷貝，因此在byval_func()函數內部修改傳遞過來的數組對初始數組沒有任何影響。
    值傳遞方法的開銷是很大的，因為首先它要完整地復制初始數組并將這份拷貝存放到棧中，這將耗費相當可觀的運行時間，因而值傳遞方法效率較低；其次，初始化數組的拷貝需要占用額外的內存空間（棧中的內存）；最后，編譯程序需要專門產生一部分用來復制初始數組的代碼，這將使程序變大。
    地址傳遞方法克服了值傳遞方法的缺點。在地址傳遞方法中，傳遞給函數的是指向初始數組的指針，不用復制數組，因此程序變得簡練，也節省了棧中的內存空間。在地址傳遞過程中,只需在函數原形中將函數的參數說明為指向數組元素數據類型的一個指針。
    例如同樣定義一個數組x：int x[10];
    那麼函數被說明為：int const_funt(const int*);
    參數const int*告訴編譯程序const_funt()函數只有一個參數,即指向一個int類型常量的指針。
    函數調用時只需將數組的地址傳遞給函數:const_func(x);
#include <stdio.h>
void const_func(const int*);
void main(void);
void main(void)
{
     int x[10];
     int y;
     for(y=0;y<10;y++)
         x[y]=y;
     constl_func(x);
}
void const_func(const int*i)
{
     int y;
     for(y=0;y<10;y++)
        printf("%d\n",*(i+y));
}
在值傳遞方式中,沒有復制初始數組并將其拷貝存放在棧中,const_func()函數只接收到指向一個int類型常量的指針,因此在編寫程序時要保證傳遞給const_func()函數的是指向一個由int類型常量組成的數組的指針。const修飾符的作用是防止意外修改初始數組中的某一個元素。

14．引用標準庫時，下面的說法你認為哪個是正確的：（B）
A) 語句#include “stdlib.h”是正確的，但會影響程序的執行速度
B) 語句#include <stdlib.h>是正確的，而去程序執行速度比#include “stdlib.h”要快
C) 語句#include <stdlib.h>和#include “stdlib.h”都是正確的，程序執行速度沒有區別
D) 語句#include “stdlib.h”是錯誤的
注釋：include   ""是先從本地目錄開始尋找，然后去尋找系統路徑，而Include   <>   相反先從系統目錄，后從本地目錄，

15.設a、b、c、d、m、n均為int型變量，且a=5、b=6、c=7、d=8、m=2、n=2,則邏輯表達式（m=a>b）&&(n=c>d)運算后，n的值為：（C）
A) 0               B) 1               C) 2               D) 7

16．不能作為重載函數的調用的依據是：（C）
A) 參數個數                              B) 參數類型
C) 函數類型                              D) 函數名稱

17．下列程序的輸出結果為: (D)
#include< iostream. h>
int func(int n)
{
　　if〔n<1)return 1;
else return n+func(n-1);
return 0;
}
void main()
{
cout<<func(5)<<endl;
}
A) 0        B)10             C)15            D)16

18. 建立派生類對象時,3種構造函數分別是a(基類的構造函數)、b(成員對象的構造函數)、c(派生類的構造函數)這3種構造函數的調用順序為: (A)
A)abc                                                              　　B)acb
C)cab                                                                     D)cba

19. 如果友元函數重載一個運算符時，其參數表中沒有任何參數則說明該運算符是：（D）
A）一元運算符                                                      B）二元運算符
C）選項A）和選項B）都可能                               D）重載錯誤
解析：C++中用友元函數重載運算符至少有一個參數，重載一目運算符要有一個參數，重載二目運算符要有兩個參數。

20. 有以下程序段：（D）？
#define F(X,Y)   (X)--; (Y)++ (X)*(Y);
…
int i, a = 3, b = 4;
for( i = 0; i<5; i++)   F(a,b)
printf(“%d, %d”, a, b);
輸出結果是：（）
A) 3, 4                                       B) 3, 5
C) -2, 5                                     D) -2, 9

21. 下列for循環的循環體執行次數為：（A）
for(int i(10), j(1); i=j=0; i++, j--)
A) 0;       B) 1;       C) 無限;        D)以上都不對

22. 下面程序的輸出結果是（D）
char *p1= “123”, *p2 = “ABC”, str［50］= "xyz";
strcpy（str+2,strcat（p1,p2））;
cout << str;
A）xyz123ABC                                                       B）z123ABC
C）xy123ABC                                                        D）出錯

23．下面函數的執行結果是輸出（B）
char str[ ] = “xunlei”;
char *p = str;
int n = 10;
printf(“%d, %d, %d\n”, sizeof(str), sizeof(p), sizeof(n));
A) 4, 4, 4                                                 B) 7, 4, 4
C) 6, 4, 4                                                 D) 6, 6, 4

33. 有下列程序段：
char *p, *q;
p = (char*) malloc(sizeof(char) * 20);
q = p;
scanf(“%s %s”, p, q);
printf(“%s %s\n”, p, q);
若從鍵盤輸入：abc def，則輸出結果是（A）
A) def def                     B) abc def
C) abc d                       D) d d
解析：q=p;因此p,q指向的是同一段內存.scanf先是把abc寫到p指向的空間,再把def寫到q指向的空間,也就是同一段空間,因此abc被def覆蓋了.

34．現在有以下語句：
struct _THUNDER{
       int iVersion;
       char cTag;
       char cAdv;
       int iUser;
       char cEnd;
}Thunder;
int sz = sizeof(Thunder);
則執行后，變量sz的值將得到（D）
A) 11             B) 12             C) 13             D) 16

35. 有如下程序段：
void GetMemeory(char* p)
｛
              p = (char*) malloc (100);
｝
void test()
{
char *str=NULL;
GetMemory(str);
strcpy(str,”Thunder”);
strcat(str+2, “Downloader”);
printf(str);
}
請問運行Test函數結果是：（D）
A) Thunder Downloader                                 B) under Downloader
C) Thunderownloader                                    D) 程序崩潰
解析：在函數中給指針分配空間，實際上是給指針的臨時變量分配空間，函數結束后，這個臨時變量也消亡，而str仍然為NULL，沒有為其分配空間，此時strcpy()是肯定會出錯的。

36. 函數調用exec((v1,v2), (v3,v4,v5),v6,v7);中，實參的個數是（A）
A) 4               B) 5               C) 6               D) 7

37. p是指向類X的成員m的指針，s是類X的一個對象。現要給m賦值，（C）是正確的。
A) s.p = 5                                                        B) s->p = 5
C) s.*p = 5                                                      D) *s.p = 5

38. 函數fun（char* p） { return p;}的返回值是（B）
A)無確切值                                              B) 行參p中存放的地址值
C) 一個臨時存儲單元的地址                   D) 行參p自身的地址值

39．a,b均為不等于0的整形變量，以下關系式恒成立的是：（C）
A) a*b/a*b == 1                                 B) a/b*b/a == 1
C) a/b*b + a%b == a                          D) a/b*b == a

40. 設有如下說明：
       typedef struct ST{ long a; int b; char c[2]; } NEW;
則下面敘述中正確的是：(C)
A）以上的說明形式非法                            B）ST是一個結構體類型
C）NEW是一個結構體類型                D）NEW是一個結構體變量

41. 下列表達式正確的是：（C）
A) 9++                  B) （x+y）++              C) c+++c+++c++                D) ++（a-b--）

42．在int b[ ][3] = {{1},{3,2},{4,5,6},{0}};中，sizeof(b) = （D）。
A) 4                      B) 12                    C) 28                    D) 48

43．以下程序的輸出結果是：(D)
#define M(x,y,z) x*y+z
main()
{
       int a=1, b=2, c=3;
       printf(“%d\n”,M(a+b,b+c,c+a));
}
A）19                   B) 17                    C) 15                    D) 12

44．若有以下定義和語句：
int u=010, v= 0x10, w=10;
printf(“%d，%d,%d\n”,u,v,w);
則輸出結果是：(A)
A)8,16,10     B)10,10,10      C)8,8,10      D)8,10,10

45. 下面程序段的輸出結果是：（B）
int a=5, b=4, c=3, d=2;
if(a>b>c)
       printf(“%d\n”,d);
else if((c-1>=d)==1)
       printf(“%d\n”, d+1);
else
       printf(“%d\n”, d+1);
A) 2                      B) 3                      C) 4                   D) 編譯錯誤

46．有如下程序段，請問k的值是：（D）
enum {a, b=5, c, d=4, e} k; k =c;
A) 3                      B）4                     C) 5                      D) 6

47．有如下程序段：
int i, n = 0;
double x = 1, y1 = 2.1/1.9, y2 = 1.9/2.1;
for( i = 1; i<22; i++)
       x = x*y1;
while( x!=1.0)
{
       x =x*y2;
       n++;
}
printf(“%d\n”, n);
請問執行結果是：（A）
A) 21                    B) 22                    C)無限循環                  D) 程序崩潰

48. 用樹形結構表示實體之間聯系的模型是（C）
A) 關系模型                       B) 網狀模型                C) 層次模型                D)以上三個都是

49．有如下程序段：
char fun(char *);
main()
{
       char *s = “one”, a[5] = {0}, (*f1)(char *) = fun, ch;
}
則對函數fun的調用語句正確的是（C）
A) *f1(&a);                  B) f1（*s）;                 C) f1(&ch)                   D) ch = *f1(s);要改成（*f1）(s)才正確

50．有如下程序段：
int c = 23;
printf(“%d\n”, c&c);
請問執行結果是：（C）
A) 0               B) 46             C) 23                    D) 以上都不對

posted @ 2011-03-02 12:18 周強閱讀(851) | 評論 (0) | 編輯收藏

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

Just enjoy programming

導航

統計

常用鏈接

留言簿(2)

隨筆分類

隨筆檔案

文章分類

相冊

技術牛人

搜索

最新評論

閱讀排行榜

評論排行榜