试题五（共 15分）
阅读以下说明和C++代码，将应填入 （n） 处的字句写在答题纸的对应栏内。
【说明】
已知类 LinkedList 表示列表类，该类具有四个方法：addElement()、lastElement()、umberOfElement()以及removeLastElement()。四个方法的含义分别为：
void addElement(Object): 在列表尾部添加一个对象；
Object lastElement(): 返回列表尾部对象；
int numberOfElement(): 返回列表中对象个数；
void removeLastElement(): 删除列表尾部的对象。
现需要借助LinkedList来实现一个Stack栈类，C++代码1和C++代码2分别采用继承和组合的方式实现。
【C++代码 1】
class Stack :public LinkedList{
public:
void push(Object o){ addElement(o); }; //压栈
Object peek(){ return （1） ; }; //获取栈顶元素
bool isEmpty(){ //判断栈是否为空
return numberOfElement() == 0;
};
Object pop(){ //弹栈
Object o = lastElement();
（2） ;
return o;
};
};
【C++代码 2】
class Stack {
private:
（3） ;
public:
void push(Object o){ //压栈
list.addElement(o);
};
Object peek(){ //获取栈顶元素
return list. （4） ;
};
bool isEmpty(){ //判断栈是否为空
return list.numberOfElement() == 0;
};
Object pop(){//弹栈
Object o = list.lastElement();
list.removeLastElement();
return o;
};
};
【问题】
若类LinkedList新增加了一个公有的方法removeElement(int index)，用于删除列表中第index个元素，则在用继承和组合两种实现栈类Stack的方式中，哪种方式下Stack对象可访问方法removeElement(int index)？ （5） （A. 继承 B. 组合）
试题六（共 15分）
阅读以下说明和Java代码，将应填入 （n） 处的字句写在答题纸的对应栏内。
【说明】
已知类 LinkedList 表示列表类，该类具有四个方法：addElement()、lastElement()、umberOfElement()以及removeLastElement()。四个方法的含义分别为：
void addElement(Object): 在列表尾部添加一个对象；
Object lastElement(): 返回列表尾部对象；
int numberOfElement(): 返回列表中对象个数；
void removeLastElement(): 删除列表尾部的对象。
现需要借助LinkedList来实现一个Stack栈类， Java代码1和Java代码2分别采用继承和组合的方式实现。
【Java代码1】
public class Stack extends LinkedList{
public void push(Object o){ //压栈
addElement(o);
}
public Object peek(){ //获取栈顶元素
return （1） ;
}
public boolean isEmpty(){ //判断栈是否为空
return numberOfElement() == 0;
}
public Object pop(){ //弹栈
Object o = lastElement();
（2） ;
return o;
}
}
【Java代码2】
public class Stack {
private （3） ;
public Stack(){
list = new LinkedList();
}
public void push(Object o){
list.addElement(o);
}
public Object peek(){//获取栈顶元素
return list. （4） ;
}
public boolean isEmpty(){//判断栈是否为空
return list.numberOfElement() == 0;
}
public Object pop(){ //弹栈
Object o = list.lastElement();
list.removeLastElement();
return o;
}
}
【问题】
若类LinkedList新增加了一个公有的方法removeElement(int index)，用于删除列表中第index个元素，则在用继承和组合两种实现栈类Stack的方式中，哪种方式下Stack对象可访问方法removeElement(int index)？ （5） （A. 继承 B. 组合）
试题六参考答案
（1）lastElement() （3分）
（2）removeLastElement() （3分）
（3）LinkedList list （3分）
（4）lastElement() （3分）
（5）A，或继承 （3分）
●设将整数1、2、3、4依次进栈，只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题：
1.当入、出栈次序为Push (1) ，Pop ()，Push (2) ，Push (3) ，Pop()，Push (4) ，Pop()，出栈的数字序列为何?(这里Push(i)表示i进栈，Pop()表示出栈) (26)
2.能否得到出栈序列1、4、2、3和1、4、3、2？答案为 (27) 。
3.请分析研究1、2、3、4的24种排列中， (28) 序列是可以通过相应的入、出栈操作得到的。
(26) A．1，3，4
B．1，4，2，3
C．1，4，3
D．3，4，1
(27) A．可以
B．不可以
C．不确定
D．随机获得
(28) A．1，3，2，4
B．4，2，3，1
C．2，4，1，3
D．3，1，4，2
请使用VC6或使用【答题】菜单打开考生文件夹proj2下的工程proj2，此工程包含有一个源程序文件proj2．cpp，其中定义了Stack类和ArrayStack类。 Stack是一个用于表示数据结构“栈”的类，栈中的元素是字符型数据。Stack为抽象类，它只定义了栈的用户接口，如下所示： 公有成员函数 功能 push 入栈：在栈顶位置添加一个元素 pop 退栈：取出并返回栈顶元素 ArrayStack是Stack的派生类，它实现了Stack定义的接口。ArrayStack内部使用动态分配的字符数组作为栈元素的存储空间。数据成员maxSize表示的是栈的最大容量，top用于记录栈顶的位置。成员函数push和pop分别实现具体的入栈和退栈操作。 请在程序中的横线处填写适当的代码，然后删除横线，以实现上述功能。此程序的正确输出结果应为： a，b，C C，b，a 注意：只在指定位置编写适当代码，不要改动程序中的其他内容，也不要删除或移动“//****料found****”。 //proj2．cpp include<iostream> using namespacc std； class Stack{ public： virtual void push(char C)=0； virtual char pop=0； }；
class ArrayStack：public Stack{ char*P； int maxSizc； int top； public： ArravStack（int s） { top=0； maxSize=s： //*********found********* P=______； } ～ArrayStack { //*********found********* _______； } void push(char c) } if(top==maxSize){ cerr<<”Overflow! \n”： return； } //*********found********* _______； top++： } char pop { if(top==0){ cerr<<”Underflow!、n”； return‘\0’; } Top--； //*********found********* ______； } }； void f(Stack&sRef) { char ch[]={‘a’，‘b’，‘c’}； cout<<ch[0]<<”，”<<ch[1]<<”，”<<ch[2]<<endl； sRef．push(oh[0])；sRef．push(ch[1])；sRef．push(ch[2])； cout<<sRef．poP<<”，”； cout<<sRef．poP<<”，”； cout<<sRef．poP<<endl； } int main { ArrayStack as(10)； f(as)： return 0： }
(1)Ilew char[s]
(2)delete[]P
(3)P[top]=e
(4)return P[top]
【考点分析】
本题主要考查的是表示栈的抽象类Stack类及它的派生类ArrayStaek类、纯虚函数和成员函数。栈的节点一般使用指针表示，定义构造函数时要给指针分配空间，使用New语句来完成。～ArrayStack是析构函数，因为前面已经使用new来分配空间了，因此在这里要用delete语句来释放指针。
【解题思路】
(1)主要考查的是ArrayStack类的构造函数，在函数中要为P申请S个char型空间，应使用语句P=flew char[s]；。
(2)主要考查析构函数，使用delete语句释放指针，即delete[]P；。
(3)主要考查push函数，top表示栈顶元素下标，添加的数据放到栈顶，因此使用语句P[top]=c；。
(4)主要考查pop函数，输出栈顶数据，top表示栈顶元素下标，因此使用语句return P[top]；。
阅读以下说明C++代码，将应填入(n)处的字句写在对应栏内。
[说明]
以下程序的功能是实现堆栈的一些基本操作。堆栈类stack共有三个成员函数：empty判断堆栈是否为空；push进行人栈操作；pop进行出栈操作。
[C++程序]
include "stdafx. h"
include ＜iostream, h＞
eonst int maxsize = 6;
class stack {
float data[ maxsize];
int top;
public:
stuck(void);
～ stack(void);
bool empty(void);
void push(float a);
float pop(void);
};
stack: :stack(void)
{ top =0;
cout ＜ ＜ "stack initialized." ＜ ＜ endl;
}
stack:: ～stack(void) {
cout ＜ ＜" stack destoryed." ＜ ＜ endl;
bool stack:: empty (void) {
return (1);
void stack: :push(float a)
if(top= =maxsize) {
cout ＜ ＜ "Stack is full!" ＜ ＜ endl;
return;
data[top] =a;
(2);
}
float stack:: pop (void)
{ if((3)){
cout＜ ＜ "Stack is undcrflow !" ＜ ＜ endl;
return 0;
(4);
return (5);
}
void main( )
{ stack s;
coat ＜ ＜ "now push the data:";
for(inti=l;i< =maxsize;i+ +) {
cout＜ ＜i＜ ＜" ";
s. push(i);
}
coat ＜ ＜ endl;
cout＜ ＜ "now pop the data:";
for(i = 1 ;i ＜ = maxsize ;i + + )
cout＜ ＜s. pop()＜ ＜" ";
}
北京旷视科技有限公司12月招聘面试题面试题面试官常问到的一些题目整理如下：问题 Q1：什么是Python？使用Python有什么好处？可用的回答 ：Python是一种编程语言，包含对象，模块，线程，异常和自动内存管理。Python的好处在于它简单易用，可移植，可扩展，内置数据结构，并且它是一个开源的。问题 Q2：请用代码简答实现stack？可用的回答 ： stack的实现代码（使用python内置的list），实现起来是非常的简单，就是list的一些常用操作 class Stack(object): def _init_(self): self.stack = def push(self, value): # 进栈 self.stack.append(value) def pop(self): #出栈 if self.stack: self.stack.pop() else: raise LookupError(stack is empty!) def is_empty(self): # 如果栈为空 return bool(self.stack) def top(self): #取出目前stack中最新的元素 return self.stack-1 问题 Q3：分布式爬虫主要解决什么问题？可用的回答 ： 面对海量待抓取网页，只有采用分布式架构，才有可能在较短时间内完成一轮抓取工作。它的开发效率是比较快而且简单的。 问题 Q4：什么是Python？使用Python有什么好处？可用的回答 ：Python是一种编程语言，包含对象，模块，线程，异常和自动内存管理。Python的好处在于它简单易用，可移植，可扩展，内置数据结构，并且它是一个开源的。问题 Q5：简述 OSI 七层协议？可用的回答 ： OSI是Open System Interconnection的缩写，意为开放式系统互联。 OSI七层协议模型主要是： 1. 应用层（Application） 应用层 是最靠近用户的OSI层。这一层为用户的应用程序（例如电子邮件、文件传输和终端仿真）提供网络服务。 2. 表示层（Presentation） 表示层 可确保一个系统的应用层所发送的信息可以被另一个系统的应用层读取。 例如，PC程序与另一台计算机进行通信，其中一台计算机使用扩展二一十进制交换码（EBCDIC），而另一台则使用美国信息交换标准码（ASCII）来表示相同的字符。 如有必要，表示层会通过使用一种通格式来实现多种数据格式之间的转换。 3. 会话层（Session） 会话层 通过运输层（端口号：传输端口与接收端口）建立数据传输的通路。 主要在你的系统之间发起会话或者接受会话请求（设备之间需要互相认识可以是IP也可以是MAC或者是主机名） 4. 传输层（Transport） 运输层 定义了一些传输数据的协议和端口号（WWW端口80等），如： TCP（transmission control protocol 传输控制协议，传输效率低，可靠性强，用于传输可靠性要求 高，数据量大的数据） UDP（user datagram protocol用户数据报协议，与TCP特性恰恰相反，用于传输可靠性要求不高，数据 量小的数据，如QQ聊天数据就是通过这种方式传输的） 主要是将从下层接收的数据进行分段和传输，到达 目的地址后再进行重组。常常把这一层数据叫做段。 5. 网络层（Network） 网络层 在位于不同地理位置的网络中的两个主机系统之间提供连接和路径选择。 Internet的发展使得从世界各站点 访问信息的用户数大大增加，而网络层正是管理这种连接的层。 6. 数据链路层（Data Link） 数据链路层 定义了如何让格式化数据以进行传输，以及如何让控制对物理介质的访问。 这一层通常还提供错误检测和纠正，以确保数据的可靠传输。 7. 物理层（Physical） 物理层 主要定义物理设备标准，如网线的接口类型、光纤的接口类型、各种传输介质的传输速率等。 它的主要作用是 传输比特流（就是由1、0转化为电流强弱来进行传输,到达目的地后在转化为1、0，也就是我们常说的数模转 换与模数转换）。 这一层的数据叫做比特。 问题 Q6：scrapy和requests的使用情况？可用的回答 ： requests 是 polling 方式的，会被网络阻塞，不适合爬取大量数据 scapy 底层是异步框架 twisted ，并发是最大优势 问题 Q7：什么是arp协议？可用的回答 ： ARP（Address Resolution Protocol）即地址解析协议， 用于实现从 IP 地址到 MAC 地址的映射，即询问目标IP对应的MAC地址。 问题 Q8：TCP和UDP的区别？可用的回答 ： TCP与UDP基本区别 1. 基于连接与无连接 2. TCP要求系统资源较多，UDP较少 3. UDP程序结构较简单 4. 字节流模式（TCP）与数据报模式(UDP); 5. TCP保证数据正确性，UDP可能丢包 6. TCP保证数据顺序，UDP不保证 具体编程时的区别 1.socket()的参数不同 2.UDP Server不需要调用listen和accept 3.UDP收发数据用sendto/recvfrom函数 4.TCP：地址信息在connect/accept时确定 5
（ 15 ）请将下列栈类 Stack 补充完整
class Stack{
private:
int pList[100]; // int 数组 , 用于存放栈的元素
int top; // 栈顶元素 ( 数组下标 )
public:
Stack():top(0){}
void Push(const int &item); // 新元素 item 压入栈
int Pop(void); // 将栈顶元素弹出栈
};
void Stack::Push(const int &item){
if(top == 99) // 如果栈满 , 程序终止
exit(1);
top++; // 栈顶指针增 1
___________;
}
int Stack::Pop(){
if(top<0) // 如果栈空 , 程序终止
exit(1);
return pList[top--];
}
以下程序实现栈的入栈和出栈的操作。其中有两个类：一个是节点类node,它包含点值和指向上一个节点的指针 prev；另一个类是栈类 stack, 它包含栈的头指针 top。
生成的链式栈如下图所示。
〈IMG nClick=over(this) title=放大 src="tp/jsj/2jc++j28.1.gif"〉
下面是实现程序，请填空完成此程序。
include 〈iostream〉
using namespace std;
class stack;
class node
{
int data;
node *prev;
public:
node(int d, node *n)
{
data=d;
prev=n;
}
friend class stack;
};
class stack
{
node *top; //栈头
public:
stack()
{
top=0;
}
void push(int i)
{
node *n=【 】;
top=n;
}
int pop()
{
node *t=top;
if (top)
{
top=top-〉prev;
int c= t-〉data;
delete t;
return c;
}
return 0;
}
int main ()
{
stack s;
s.push(6);
s.push(3);
s.push (1);
return 0;
}
阅读以下说明和C++程序，将应填入(n)处的字句写在对应栏内。
【说明】
以下程序的功能是设计一个栈类stack＜T＞，并建立一个整数栈。
【程序】
include ＜ iostream. h ＞
include ＜ stdlib. h ＞
const int Max =20; //栈大小
template ＜ class T ＞
class stack{ //栈元素数组
T s[Max]; //栈顶下标
int top;
public:
stack( )
{
top =-1; //栈顶初始化为-1
}
void push( const T &item); //item入栈
T pop( ); //出栈
int stackempty( ) const; //判断栈是否为
};
template ＜ class T ＞
void stack ＜T ＞::push(const T &item)
{
if(top==(1))
{
cout ＜＜"栈满溢出" ＜＜endl;
exit(1);
}
top ++
s[top] = item;
}
template ＜ class T ＞
T stack＜T＞ ::pop()
{
T temp;
if(top==(2))
{
cout ＜＜"栈为空，不能出栈操作" ＜ ＜ endl;
exit(1);
}
temp =s[top];
top --;
return temp;
}
template ＜ class T ＞
int stack ＜ T ＞:: stackempty( ) const
{ return top == -1;
{
void main( )
{
stack ＜int＞ st;
int a[] ={1,2,3,4,5};
cout ＜＜"整数栈" ＜＜endl;
cout ＜＜"入栈序列:" ＜＜endl;
for(int i=0;i＜4;i ++)
{
cout ＜＜a[i] ＜＜" ";
(3);
}
cout ＜＜ endl ＜＜"出栈序列";
while((4))
tout＜＜(5)＜＜" ";
cout＜ ＜ endl;
}
下面是一个栈类的模板，其中push函数将元素i压入栈顶，pop函数弹出栈顶元素。栈初始为空，top值为0，栈顶元素在stack[top-1]中，在下面横线处填上适当的语句，完成栈类模板的定义。
template＜class t＞
class Tstack
{
enum{size=1000};
T stack[size]
int top;
public:
Tsack():top(0){}
void push(const T&i){
if(top＜size)
stack[top++]=i;
}
T pop()
{
if(top==O)exit(1)；//栈空时终止运行
retum【 】;
}
};
请将下列栈类Stack的横线处补充完整。
class Stack{
private:
int pList[100]; ∥int数组，用于存放栈的元素
int top; ∥栈顶元素(数组下标)
public:
Stack():top(0){}
void Push(const int &item); ∥新元素item