【精品】IT笔试题目集.doc

【精品】IT笔试题目集.doc编程和测试设计题(2道)
(一) 简述：实现一个函数，对一个正整数n,算得到1需要的最少操作次
数：
如果n为偶数，将其处以2；
如果n为奇数，可以加1或减1；
一直处理下去。
例子：
ret = func(7);
ret = 4,可以证明最少需要4次运算
n = 7
n—6
n/2 3
n/2 2
n++ 1
要求：实现函数(实现尽可能高效)
Int func (unsign int n) ； n为输入，返回最小的运算次数。
给出思路(文字描述)，完成代码，并分析你算法的时间复杂度。
请列举测试方法和思路
int function(unsigned int n) {
if (n == 1) return 0:
if (n%2 == 0) return 1 + function(n/2):
return 2 + min(function((n + 1)/2), function((n - 1)/2));
理解了动态规划的思想，就很容易理解这里面的问题。因为动态规划本质上 就是保存运算结果的递归，虽然递归算法经常会有指数级别的搜索节点，但这些 节点往往重复率特别高，当保存每次运算的节点结果后，在重复节点的计算时，
就可以直接使用已经保存过的结果，这样就大大提高了速度(每次不仅减少一个 节点，而且同时消灭了这个节点后面的所有分支节点)。
在这个问题里是什么情况呢？仔细分析就会发现，在整个搜索数中，第存层 的节点只有两种可能性几» fcffn » fc- I-这意味着整个搜索树事实上只有 21og”.个节点。所以这个递归算法本质上的运算复杂度只有O(logn)。这已经是 最优的了
以下代码打印的结果是(假设运行在i386系列计算机上)：C
struct st_t
{
int status;
short* pdata;
char errstr[32];
};
st_t st[16];
char* p = (char*) (st[2]. errstr + 32);
printf("%d", (p - (char*) (st))):
A 32 B 114
C 120 D 1112
同一进程下的线程可以共享以下：B
A. stack B. data section
C. register set D. thread ID
解：线程共享的环境包括：进程代码段、进程的公有数据(利用这些共享的 数据，线程很容易的实现相互之间的通讯)、进程打开的文件描述符、信号的处 理器、进程的当前目录和进程用户ID与进程组ID。
进程拥有这许多共性的同时，还拥有自己的个性。有了这些个性，线程 才能实现并发性。这些个性包括：
线程ID
每个线程都有自己的线程ID,这个ID在本进程中是唯一的。进程用此来 标识线程。
寄存器组的值
由于线程间是并发运行的，每个线程有自己不同的运行线索，当从一个线程 切换到另一个线程上时，必须将原有的线程的寄存器集合的状态保存，以便将来 该线程在被重新切换到时能得以恢复。
线程的堆栈
堆栈是保证线程独立运行所必须的。线程函数可以调用函数，而被调用函数 中又是可以层层嵌套的，所以线程必须拥有自己的函数堆栈，使得函数调用可以 正常执行，不受其他线程的影响。
错误返回码
由于同一个进程中有很多个线程在同时运行，可能某个线程进行系统调 用后设置了 errno值，而在该线程还没有处理这个错误，另外一个线程就在此时 被调度器投入运行，这样错误值就有可能被修改。所以，不同的线程应该拥有自 己的错误返回码变量。
线程的信号屏蔽码
由于每个线程所感兴趣的信号不同，所以线程的信号屏蔽码应该由线程自己 管理。但所有的线程都共享同样的信号处理器。
线程的优先级
由于线程需要像进程那样能够被调度，那么就必须要有可供调度使用的参数，这个参数 就是线程的优先级
.是面向对象程序设计语言中的一种机制。这种机制实现了方法的定义与具 体的对象无关，而对方法的调用则可以关联于具体的对象。
(Inhertance) (Template)
C,对象的自身引用(Self-Reference) (Dynamic Binding)
Co要点解析：选项b的"模板(template)”是面向对象技术的一种参数化类。
”多态性”使作用于不同对象的同一个操作可以有不同的解释，从而产生不同的执行结 果。
选项C的"动态绑定(dynamicbinding)”是面向对象程序设计语言中的一种机制。这种 机制实现了方法的定义与具体的对象无关，而对方法的调用则可以关联于具体的对象。。
int Replace(Stringtype &