程序员面试宝典(C++例题)(共18页)

1、第3章 链表3.4 堆栈(duzhn)的实现说明：请对堆栈这种数据结构(sh j ji u)做出评论。用C+语言来实现一个堆栈，你可以选用链表或动态数组来实现你的堆栈；并请对你的决定做出解释。你为堆栈设计的程序接口必须完备(wnbi)、规范、和易于使用。解答：堆栈是一种先入后出、后入先出的数据结构。class IntStackstruct Nodeint idata;Node* pnext;public:IntStack ():isize(0),phead(NULL) IntStack ()while(phead!=NULL)Node*p = phead;phead = phead-pnext

2、;delete p;isize = 0;void Push(int i)Node* p = new Node;p-idata = i;p-pnext = phead;phead = p;+isize;bool Pop(int& iout) bool ret = false;if(isize0)iout = phead-idata;Node* p = phead;phead = phead-pnext;delete p;-isize; ret = true;return ret;int Size()return isize;private:int isize;Node* phead;templa

3、teclass Stackstruct NodeType idata;Node* pnext;public:Stack():isize(0),phead(NULL)Stack()while(phead!=NULL)Node*p = phead;phead = phead-pnext;delete p;isize = 0;void Push(Type& i)Node* p = new Node;p-idata = i;p-pnext = phead;phead = p;+isize;bool Pop(Type& tout) bool ret = false;if(isize0)tout = ph

4、ead-idata;Node* p = phead;phead = phead-pnext;delete p;-isize; ret = true; return ret;int Size()return isize;private:int isize;Node* phead;3.5 链表的尾指针(zhzhn)说明：有一个单向链表，它的元素全都是些整数。head和tail分别(fnbi)指向该链表第一个元素（即头元素）和最后一个元素（即尾元素）的全局性指针。请实现调用接口如下所示的两个C语言函数：int Delete(element *elem);int InsertAfter(element

5、 *elem, int data);Delete函数只有一个输入参数，他就是那个将被删除的元素。InsertAfter函数由两个输入参数，第二个输入参数给出了新元素的取值，它将被插入到第一个输入参数所指定的元素的后面。当需要把新元素插入到链表的开头作为新的头元素时，函数InsertAfter的第一个输入参数（即被声明(shngmng)为element类型的那个输入参数）将被设置为NULL。如果执行成功，这两个函数将返回“1”；如果不成功，将返回“0”。element *head, *tail;int Delete(element* elem) int ret = 0; if(elem=NULL

6、) return ret; if(elem=head) if(head=tail) head=(tail=NULL); else head = head-next; delete elem; ret = 1; return ret; element* p0=NULL,*p1 = head; while(p1!=NULL) if(p1=elem) break; else p0 = p1; p1 = p1-next; if(p1!=NULL) p0-next = p1-next; delete p1; ret = 1; return ret;element *head,*tail;int Inse

7、rtAfter(element* elem, int data) int ret = 0; element *p = new element; p-data = data; p-next = NULL; if(elem=NULL) if(head=NULL) head = (tail=p); else p-next = head; head = p; ret = 1; return ret; else element* p1=head; while(p1!=NULL) if(p1=elem) break; else p1=p1-next; if(p1!=NULL) p-next = p1-ne

8、xt; p1-next = p; ret = 1; return ret;3.6 对RemoveHead函数进行(jnxng)纠错说明(shumng)：下面是一个用来删除单向链表的头元素的函数。请找出其中的程序漏洞并加以纠正。void RemoveHead(node *head)free(head);head = head-next;解答(jid)：void RemoveHead(node *&head)if(head=NULL) return;node* p = head;head = head-next;free(p);3.7 链表中的倒数第m个元素说明：给定一个单向链表，请设计一个既节省

9、时间又节省空间的算法来找出该链表中的倒数第m个元素。实现这个算法，并为可能出现的特例情况安排好处理措施。“倒数第m个元素”是这样规定的：当m=0时，链表的最后一个元素（尾元素）将被返回。解答：node* FindInvM(node* head, int m)if(head=NULL) return NULL;node* pm=head,*p=head;int ipm=0;while(p-next!=NULL)p = p-next;if(ipmnext;if(ipm=m) return pm;else return NULL;3.8 链表的扁平化说明：给定一个双向链表。这个双向链表中的每一个元素

10、除固有的后指针和前指针外，还有子指针，每个子指针可能指向也可能不指向另一个双向链表。而那些子双向链表本身(bnshn)还可能有一个或者多个子双向链表，从而形成一种多层次的数据结构，如图所示：对这个链表进行扁平化，使全体节点都出现在一个只有一个层次的双向链表里。已知条件只有原多层次双向链表的第一层次的头指针(zhzhn)和尾指针。下面是各节点的+语言(yyn)struct定义：struct nodenode *next;node *prev;node *child;int value; ;void ExpandList(node* pnode)while(pnode!=NULL)if(pnode

11、-child!=NULL)node* p0=pnode-child,*p1=p0;while(p1-next!=NULL) p1 = p1-next;node*pp1 = pnode-next;pnode-next = p0; p1-next = pp1;if(pp1!=NULL) pp1-prev = p1; p0-prev = pnode;pnode = pnode-next;3.9 空链表与循环(xnhun)链表bool IsLoopLink(node* head)node* p = head;if(p=NULL) return false;stl:set pset;stl:pairst

12、l:set:iterator, bool pl;pl = pset.insert(p);while(p-next!=NULL)p=p-next;pl = pset.insert(p);if(pl.second=false) return true;return false;第4章 树和图4.3 二叉树：左遍历(bin l)可使用(shyng)递归。4.4 二叉树：左遍历(bin l)，不使用递归使用堆栈缓存子节点。4.5 二叉树：最低公共祖先找出根节点到子节点的路径数组，两个数组中最后一个相同的节点就是最低公共(gnggng)祖先。第5章 数组与字符串5.3 第一个无重复(chngf)字符（1

13、）以字母(zm)为Key建立hash数组，第一遍+hash数组，第二遍找数组为1的字母，O（2n）；（2）从首字母开始，判断其是否还有相同字母，类似排序，O(n2)5.4 删除特定字符对remove建立hash数组，字符为key；遍历str字符串，如果字符在remove中则不拷贝，否则拷贝前移。效率在O（n+m）。5.5 颠倒单词的出现顺序对字符串进行(jnxng)反向遍历，找到空格则复制单词。5.6 整数(zhngsh)/字符串之间的转换主要是判断+-号和计算(j sun)字符串长度，其他好做。第6章 递归算法6.1 二分法搜索6.2 字符串的全排列6.3 字符串的全组合(zh)6.4 电话

14、(dinhu)键单词第7章 其他程序设计(chn x sh j)问题7.5 绘制八分之一圆形7.6 矩形是否(sh fu)重叠7.7 字节(z ji)的升序存储和降序存储方式7.8 “1”的个数7.9 简单(jindn)的SQL查询7.10 公司(n s)和员工数据库7.11 最大值，不允许(ynx)使用统计功能7.12 生产者/消费者问题(wnt)第8章 与技术(jsh)、测量、排序有关的智力题8.1 开锁ANS: take an example of 10, emulate the open and close, and then find the rule.You will find t

15、hat all the opened number is a square number, so the opened number is:1,4,9,16,25,36,49,64,81,100.8.2 三个开关(kigun)ANS: you need to touch the lamp. Firstly open the lamp for 1minute, then closed it, and open the next one. You should go to the room and touch the closed lamp to determine which the first

16、 warm lamp is.8.3 过桥(u qio)ANS: (2+1)(1)(5+10)(2)(2+1)=178.4 找石头(sh tou)ANS: 3 3 2第9章 与图形和空间(kngjin)有关的智力题9.1 船和码头ANS: 绳子rope9.2 数方块ANS: 3*3*3-1*1*1=8ANS: 4*4*4-2*2*2 = 569.3 狐狸(h li)与鸭子ANS: the duck could fly.9.4 导火索ANS: burn wire1 from 2 endpoint and burn wire2 from 1 endpoint meanwhile,When the w

17、ire1 burn out, burn wire2 the other endpoint.It will spend 45 minutes when the wire2 burn out.9.5 躲火车(huch)ANS: 第10章 计算机基础知识10.3 C+和Java10.4 头文件10.5 C存储(cn ch)类别10.6 Friend类10.7 类与结构(jigu)的区别10.8 父类与子类10.9 参数传递10.10 宏与Inline函数(hnsh)10.11 继承(jchng)10.12 面向对象的程序设计(chn x sh j)10.13 与线程有关的程序设计问题10.14 废弃内存的自动回收10.15 32位操作系统(co zu x tn)10.16 网络(wnglu)性能10.17 高速(o s)磁盘缓存10.18 数据库的优点10.19 加密技术10.20 新的加密算法10.21 哈希表与二元搜索树第11章 非技术问题11.2 你打算从事(cngsh)哪方面的工作？11.3 你最喜欢的程序设计语言(yyn)是哪一种？11.4 你的工作习惯(xgun)是怎样的