Chinaunix

标题: 笔试题 [打印本页]

作者: 人月神话 时间: 2006-12-29 15:07
标题: 笔试题
1.T(n) = 4T(n/2) + n^2 * lgn T(n) 的复杂度是多少 -------李博
解答:
根据 master method 定理2
a= 4, b =2, f(n)= n^2*lgn
n^(log(b,a))=n^(log(2,4))= n^2

f(n)=n^2*lgn=O(n^2*(lgn)^1 )  k = 1;

应该说满足条件2

T(n)=O(n^2*(lgn)^(k+1)) = O(n^2*(lgn)^2)

以下三题为laomai提出;
第一题，
给一个四字节的long表示的秒数，
1、把他转换成ascii格式的时间，可以使用你知道的工具或者平台，
解答:ctime()或者 localtime() + asctime();
2、自己写函数把这个整数转换成主机字节序，即自己实现ntohl函数

解答:
void exchange(char* chars,int len)
{
int i;
char temp;
for(i=0 ;i
long MyN2L(long nl)
{
long hl=0;
char theb[4] = {0};
memcpy(theb, &nl, 4);
exchange(theb, 4);
memcpy(&hl, theb, 4);
return hl;
}

第二题
int main(int argc, char* argv[])
{
return 0;
}
在vc6的release模式下编译后，在项目的release目录里会有一个文件
CppConsole.exe
要求：
1、找出这个pe的dos stub
2. 将dos stub的反汇编代码写出来
3、将dos stub存成com文件，在dos下执行
4、执行后可能会有乱码，请指出原因并解决它
(附加题)5. 修改编译选项加上自己的dos stub
解答:
windows为了保证和dos上面的程序兼容性,在可执行文件的头部加入了dos文件格式头;
查看pe的格式我们可以知道,
Offset 0  1  2  3  4  5  6  7 8  9  A  B  C  D  E  F

000000  4d 5a 90 00 03 00 00 00  04 00 00 00 ff ff 00 00  MZ..........ÿÿ..
000010  b8 00 00 00 00 00 00 00  40 00 00 00 00 00 00 00  ¸.......@.......
000020  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  ................
000030  00 00 00 00 00 00 00 00  00 00 00 00 d8 00 00 00  ............Ø...
000040  0e 1f ba 0e 00 b4 09 cd  21 b8 01 4c CD 21 54 68  ..º..´.Í!¸.LÍ!Th
000050  69 73 20 70 72 6F 67 72  61 6D 20 63 61 6E 6E 6F  is program canno
000060  74 20 62 65 20 72 75 6E  20 69 6E 20 44 4F 53 20  t be run in DOS
000070  6D 6F 64 65 2E 0D 0D 0A  24 00 00 00 00 00 00 00  mode....$.......
这个就是最简单的文件头,包括dos-header和dos-stub
dos-header有64个字节长,出去最后4个字节为d8000000是指向pe的偏移指针,这里我们不说pe;
64个字节后就是dos-stub了,直接copy出来,保存为2进制的文件,就可以在dos状态下运行;
这段代码本身就是为了在dos下允许考虑的.
在运行的过程中你会发现有乱发发生,是因为在偏移量的时候没有考虑到相对地址的转变,因为我们是直接从别的代码中拷贝出来的,
所以这里就会存在地址的偏移,用debug工具可以检查到地址偏移量为010e,这个地方正好是This.....字符串的开始.
修改这个偏移量以后,就解决了乱码的问题;
(附加题)在vc的或者汇编的连接选项中都可以添加上自己的dos-stub程序,dos-stub程序规定为自己定义的dos程序,原则上你可以在这里
添加任何的dos程序;VC的连接选项加上/stub:filename 这里的filename修改为一个dos程序就可以了.
BTW,其实这段DOS-STUB是可以不要的,直接去掉就可以,不过你得注意d8000000的指向pe的地址偏移量,这个地方就得相应的修改;这在代
码瘦身中常会用到.....
第三题:
其中f(0)=f(1)=1, f(n) = f(n-1)+f(n-2)模板偏特化实现
#include
using namespace std;
template
struct fib
{
static const int result = fib::result + fib::result;
};
template
struct fib
{
static const int result = 0;
};
template
struct fib
{
static const int result = 1;
};
int _tmain(int argc, _TCHAR* argv[])
{
cout ::result

本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u/25217/showart_223124.html

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)