转载请标明出处,原文地址:http://blog.csdn.net/hackbuteer1/article/details/11473405
一、简答题
(1)一位老师有2个推理能力很强的学生,他告诉学生他手里有以下的牌:
黑桃:2 , 5 , 7 , 9 , J , K
红心:3 , 4 , 9 , J , K
梅花:5 , 8 , 9 , Q
方块:2 , 7 , 8
然后从中拿出一张牌,告诉A这张牌的大小,告诉了B这张牌的花色;
A:我不知道这张是什么牌
B:我就知道你肯定不知道这张是什么牌
A:现在我知道
B:现在我也知道了
请问这张是什么牌?
答:方块8
(2)有11个乒乓球,其中有一个球是伪劣产品并存在质量较轻的问题,现有一个没有砝码的天平,只能称3次把那个假货给称出来。
答:
第一次,天平两端各放5个乒乓球,如果天平平衡,那么剩下的那个就是伪劣产品。
如果不平衡,则将天平较轻那端的5个乒乓球选出来,然后在天平两端各放2个乒乓球,如果天平平衡,那么剩下的那个就是伪劣产品。否则,将天平较轻那端的2个乒乓球选出来,放在天平上重新测量,天平较轻端的那个乒乓球就是伪劣产品。
(3)说明指针与引用的区别。
答:●指针是一个实体,而引用仅是个别名;
●引用只能在定义时被初始化一次,之后不可变;指针可变;引用“从一而终”,指针可以“见异思迁”;
●引用没有const,指针有const,const的指针不可变;
●引用不能为空,指针可以为空;
●“sizeof 引用”得到的是所指向的变量(对象)的大小,而“sizeof 指针”得到的是指针本身的大小;
●指针和引用的自增(++)运算意义不一样;
●引用是类型安全的,而指针不是 (引用比指针多了类型检查
从内存分配上看:程序为指针变量分配内存区域,而引用不分配内存区域。指针:指向另一个内存空间的变量,我们可以通过它来索引另一个内存空间的内容,本身有自己的内存空间。
(4)列出C++类型转换操作符,并分别举例。
dynamic_cast: 在多态类型转换时使用,用来执行继承体系中"安全的向下转型或跨系转型动作",就是子类对象指针转化为父类对象指针。实现在运行时,并进行运行时检测,如果转换失败,返回值是NULL。
static_cast:与dynamic_cast相反,static_cast是在编译时转换类型的,故称为static_cast,它可以用在值类型转换中
const_cast:一般用于去除const, volatile等修饰属性上.
reinterpret_cast:特意用于底层的强制转型,这个操作符能够在非相关的类型之间转换。操作结果只是简单的从一个指针到别的指针的值的二进制拷贝。在类型之间指向的内容不做任何类型的检查和转换。
(5)写个简单的函数,用于判断CPU的字节序(little endian/big endian)
- //若处理器是Big_endian的,则返回0;若是Little_endian的,则返回1。
- int checkCPU(void)
- {
- union
- {
- int a;
- char b;
- }c;
- c.a = 1;
- return (c.b == 1);
- }
(6)实现一个128位整数的类,并且完成后面的函数,测试一个数是否为素数。
class int128
{
};
bool isPrime(int128 & number)
{
...
}
答:
- #include<bitset>
- #include<algorithm>
- #include<iostream>
- #include<string>
- #include<deque>
- using namespace std;
- class int128;
- void shift(int128 & in,deque<bool> & de);
- template<size_t N>
- bool operator<(bitset<N> const& b1,bitset<N> const& b2)
- {
- int i=N;
- while( i-- && b1[i]==b2[i] ) { }
- return ((-1 == i) ? false : (b1[i]<b2[i]));
- }
- class int128
- {
- bitset<128> number;
- public:
- explicit int128(string str):number(str){}
- int128(bitset<128>const& b):number(b){}
- int128(int a=0,int b=0,int c=0,int d=0)
- {
- bitset<32> b1(a),b2(b),b3(c),b4(d);
- int i, k=128;
- for(i=32; i; number[--k]=b1[--i]) { }
- for(i=32; i; number[--k]=b2[--i]) { }
- for(i=32; i; number[--k]=b3[--i]) { }
- for(i=32; i; number[--k]=b4[--i]) { }
- }
- bool operator[](size_t i)const
- {
- return number[i];
- }
- bitset<128>::reference operator[](size_t i)
- {
- return number[i];
- }
- friend bool operator<(int128 const& i1,int128 const& i2)
- {
- return i1.number<i2.number;
- }
- friend int128 operator+(int128 const& i1,int128 const& i2)
- {
- if(i1==0)return i2;if(i2==0)return i1;
- int128 result;
- bitset<2> sum; //存放0+1、1+1的结果,把进位也包含在里面了
- for(int i=0;i<128;++i)
- {
- sum=i1[i]+i2[i]+sum.to_ulong();
- result[i]=sum[0];
- sum>>=1; //把进位挪到低位
- }
- return result;
- }
- friend int128 operator-(int128 const& i1,int128 const& i2)
- {
- if(i2==0)
- return i1;
- int128 result=i1;
- for(int i=0;i<128;++i)
- {
- if(i2[i]==0) {}
- else
- {
- if(result[i]==1)
- result[i]=0;
- else
- {
-
int k=i;
//当前为0,处理连续借位的情况 - while(k<128 && result[k]==0)
- {
- result[k]=1;
- ++k;
- }
- if(k!=128)
- result[k]=0;
- }
- }
- }
- return result;
- }
- friend int128 operator*(int128 const& i1,int128 const& i2)
- {
- if(i1==0 || i2==0)
- return int128();
- if(i1==1)
- return i2;
- if(i2==1)
- return i1;
- int128 acc=int128();
- for(int i=0;i<128;++i)
- {
-
if(i2[i]==1)
//乘一下,往右挪一下加 - {
- acc=acc+(i1<<i);
- }
- }
- return acc;
- }
- friend int128 operator/(int128 const& i1,int128 const& i2)
- {
- if(i1 < i2)
- return int128();
- deque<bool> de;
- bool flag = 0;
-
for(int i = 127 ; i >= 0 ; --i)
//先把被除数放在队列里面 - {
- if(flag == 0 && i1[i] == 0) {}
- else
- {
- flag = 1;
- de.push_back(i1[i]);
- }
- }
- int128 div = int128(); //被除数
- int128 result = int128(); //结果
- while(!de.empty())
- {
- shift(div,de); //从高位把被除数一位的挪出来
-
if(div < i2)
//挪出来以后看看能不能处以div - {
- result = result<<1; //不能除,当前结果商0
- }
-
else
//当前结果商1 - {
- result = (result<<1) + int128(0,0,0,1); //1保存到result
- div = div - i2; //除了一个i2,减掉
- }
- }
- return result;
- }
-
friend int128 operator%(int128 const& i1,int128 const& i2)
//思路同上 - {
- if(i1 < i2)
- return i1;
- deque<bool> de;
- bool flag = 0;
- for(int i = 127 ; i >= 0 ; --i)
- {
- if(flag == 0 && i1[i] == 0) {}
- else
- {
- flag = 1;
- de.push_back(i1[i]);
- }
- }
- int128 div = int128();
- int128 result = int128();
- while(!de.empty())
- {
- shift(div,de);
- if(div < i2)
- {
- result = result<<1;
- }
- else
- {
- result = (result<<1) + int128(0,0,0,1);
- div = div - i2;
- }
- }
- return div;
- }
- friend bool operator==(int128 const& i,int const k)
- {
- bitset<32> bb(k);
- for(int g = 0 ; g < 32 ; ++g)
- {
- if(i[g] != bb[g])
- return 0;
- }
- return 1;
- }
- void operator=(bitset<128>const& b)
- {
- number = b;
- }
- friend ostream& operator<<(ostream& o,int128 const& i)
- {
- o<<i.number;
- return o;
- }
- int128 operator<<(size_t step)const
- {
- return int128(number<<step);
- }
- unsigned long to_ulong()const
- {
- return *((unsigned long*)&number);
- }
- public:
- bool ToDecimalStr(std::string &str)
- {
- str.clear();
- char buf[128] = {0};
- int128 Radix(0, 0, 0, 10);
- for(int128 num = number; !(num == 0); num = num/Radix)
- {
- if( sprintf_s(buf, 64, "%d", ((int)(num%Radix).to_ulong())) < 0 )
- {
- return false;
- }
- str = buf + str;
- }
- return true;
- }
- static void Print(int128 & data, bool bEndl = true)
- {
- string str;
- if( data.ToDecimalStr(str) )
- {
- printf("%s%s", str.c_str(), (bEndl?"\n":""));
- }
- }
- };
- static int128 const one = int128(0,0,0,1);
- template<size_t N>
- void add_one(bitset<N>& b)
- {
- int i = 0;
- while(i < N && b[i] == 1)
- {
- b[i] = 0;
- ++i;
- }
- if(i == N)
- return;
- b[i] = 1;
- }
- void add_one(int128& k)
- {
- int i = 0;
- while(i < 128 && k[i] == 1)
- {
- k[i] = 0;
- ++i;
- }
- if(i == 128)
- return;
- k[i] = 1;
- }
- void shift(int128 & in,deque<bool> & de)
- {
- if(de.front()==1)
- {
- de.pop_front();
- in=(in<<1)+one;
- }
- else
- {
- de.pop_front();
- in=in<<1;
- }
- }
- bool IsPrime(int128 const& number)
- {
- for(int128 i = int128(0,0,0,2) ; i < number ; add_one(i))
- {
- if(number%i == 0)
- return 0;
- }
- return 1;
- }
(7)对二叉树进行排序,排序后的结果为二叉排序树。
二叉排序树又称二叉查找树,它或者是一棵空树,或者是具有下列性质的二叉树:(1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值;(2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值;(3)左、右子树也分别为二叉排序树;
struct STreeNode
{
int key;
STreeNode* left_child;
STreeNode* right_child;
};
//返回值为排序后的根节点
STreeNode* bt2bst(STreeNode* root_node)
{
}
- struct STreeNode
- {
- int key;
- STreeNode* left_child;
- STreeNode* right_child;
- };
- void InsertBST(STreeNode* t , int key)
- {
- if(NULL == t)
- {
- t = new STreeNode;
- t->left_child = t->right_child = NULL;
- t->key = key;
- return;
- }
- if(key < t->key)
- InsertBST(t->left_child , key);
- else
- InsertBST(t->right_child , key );
- }
- //先序遍历树并插入建立排序树
- void PreOrder(STreeNode* t , STreeNode* tBST)
- {
- if(NULL != t)
- {
- InsertBST(tBST , t->key);
- PreOrder(t->left_child , tBST);
- PreOrder(t->right_child , tBST);
- }
- }
- //目标函数
- STreeNode* bt2bst(STreeNode* root_node)
- {
- STreeNode* bstTreeRoot = NULL;
- PreOrder(root_node , bstTreeRoot);
- return bstTreeRoot;
- }
二、扩展题
(1)列出几种你了解的IPC机制。
答:共享内存:是一片指定的物理内存区域,这个区域通常是在存放正常程序数据区域的外面, 它允许两个或多个进程共享一给定的存储区,是针对其他通信机制运行效率较低而设计的。使得多个进程可以访问同一块内存空间,是最快的可用IPC形式。往往与其它通信机制,如信号量结合使用,来达到进程间的同步及互斥。
信号量(semaphore):主要作为进程间以及同一进程不同线程之间的同步手段。
套接口(Socket):更为一般的进程间通信机制,可用于不同机器之间的进程间通信。起初是由Unix系统的BSD分支开发出来的,但现在一般可以移植到其它类Unix系统上。
消息队列(MessageQueue)是一个结构化的排序内存段表,这个队列是进程存放或检索数据的地方,是一个消息的链表,可以被多个进程所共享。
(2)列举一种死锁发生的场景,并给出解决方案。
答:最经典的场景就是生产者/消费者,生产者线程生产物品,然后将物品放置在一个空缓冲区中供消费者线程消费。消费者线程从缓冲区中获得物品,然后释放缓冲区。由于生产者/消费者都在操作缓冲区,容易导致死锁的发生。
可以通过添加锁的保护来对缓冲区进行互斥的访问,保证某一时刻只有一个线程对缓冲区进行操作,当缓冲区满的时候,生产者线程就会挂起,同时通知消费者线程。而缓冲区空的时候,消费者线程就会挂起,同时通知生产者线程。
(3)列举编写一个TCP的服务器端程序可能需要用到的socket API,如果这些API的调用有先后关系,请按先后关系列出。
(4)举例说明什么是MVC。
答:MVC是一个设计模式,它强制性的使应用程序的输入、处理和输出分开。使用MVC应用程序被分成三个核心部件:模型、视图、控制器。它们各自处理自己的任务。
视图是用户看到并与之交互的界面。对老式的Web应用程序来说,视图就是由HTML元素组成的界面,在新式的Web应用程序中,HTML依旧在视图中扮演着重要的角色,作为视图来讲,它只是作为一种输出数据并允许用户操纵的方式。
模型表示企业数据和业务规则。在MVC的三个部件中,模型拥有最多的处理任务。由于应用于模型的代码只需写一次就可以被多个视图重用,所以减少了代码的重复性。
控制器接受用户的输入并调用模型和视图去完成用户的需求。所以当单击Web页面中的超链接和发送HTML表单时,控制器本身不输出任何东西和做任何处理。它只是接收请求并决定调用哪个模型构件去处理请求,然后用确定用哪个视图来显示模型处理返回的数据。