*必填

信息

（笔试时间120分钟）

一、简答题（本题共30分）

1.请说说C++/Java/Objective-C/C#语言是如何体现面向对象思想的。（10分）

2.请用C++或者Java编程语言实现多态。（10分）

3.编写一个栈的压栈操作（push），栈的结构定义如下：

Struct Static{

Element* base;//栈底

Element* top;//当前栈顶

Int capacity;//栈的当前容量

}

实现以下函数：

bool push(Stack* s,Element elem);//s已被初始化，Element为基本数据类型，初始化大小为：INIT_SIZE（10分）

二、算法与程序设计（本题45分）

1.查找某一字串中字串的个数，比如：字串 ”hello world!” 中字串的个数为2，实现其函数。（15分）

2.请使用非递归方式实现二叉树的后序遍历，要求时间复杂度和空间复杂度都为O(n)。（15分）

3.给定一个链表，其中的节点有两个指针：指针一指向之后第一个节点，指针二指向之后第二个节点。请设计一个函数，删除链表中所有值为M的节点。（15分）

三、系统设计题（本题共25分）

1.基于手机系统平台，设计一个Push（消息推送）系统，包括手机端和Push server端。这套Push服务系统是一个基础服务系统，不包括具体业务逻辑功能，是一个开放系统，开放给第三封应用开发者使用。请基于手机系统的一些特性，来设计这套Push系统。

1）请描述一些这套系统手机端部分设计时需要考虑的关键性能指标有哪些。（5分）

2）请画出手机端程序的系统结构图。（8分）

3）请画出第三方程序使用这套系统时所涉及的相关部分的系统结构图。（8分）

4）你觉得基于这套系统能够开发一个什么样的第三方程序。请给出一个例子。（4分）