程序员笔试题:浪潮软件研发B卷

浪潮软件研发B卷（60分钟）

注：对于有C和JAVA选择的试题，考生可以选择其中一种解答，请在答题卡中标明。即选择C语言试题解答，则解答的JAVA试题不计分；选择JAVA语言，解答的C语言试题不计分。

一、 填空题，共52分，每空2分

1.在计算机中，最适合进行数字加减运算的数字编码是____,最适合表示浮点数阶码的数字编码是______。

2.如果主存容量为16M字节，且按字节编址，表示该主存地址至少应需要__位。

3.中断响应时间是指_ ______从发出中断请求到进入中断处理所用的时间

4.表达式a*（b+c）-d的后缀表达形式为_________。

5.若二叉树的先序遍历序列为ABDECF，中序遍历序列DBEAFC，则其后序遍历序列为____________。

6.以比较为基础的排序算法在最坏情况下的计算时间下界为________。

7.若广义表L=（（1，2，3）），则L的深度为______。

8.某双向链表中的结点如下图所示，删除t所指结点的操作为________。

„

next

9.在_____存储结构中，数据结构中元素的存储地址与其关键字之间存在某种映射关系。

10.在TCP/IP网络中，为各种公共服务保留的端口号范围是_____。

11.OSI传统7层指的是：物理层、数据链路层、_____、传输层、话路层、_____和应用层。

12.关系模式R（U，F），其中U=（W,X,Y,Z）,F={WX→Y,W→X,X→Z，yVw}。关系模式R的候选码是_______，_____是无损连接并保持函数依赖的分解。

13.软件设计的主要任务是设计软件的结构、过程和模块，其中软件结构设计的

主要任务是要确定_____。

14.常见的软件开发模型有瀑布模型、演化模型、螺旋模型、喷泉模型等。其中

______模型适用于需求明确或很少变更的项目，______模型主要用来描述面向对

象的软件开发过程。

15.在UML提供的图中，______用于描述系统与外部系统及用户之间的交互；

______用于按时间顺序描述对象间的交互。

【C语言】：

16.设有定义语句int（*f）（int）；则f是____________。

17.函数调用语句：func（f2（v1，v2），（v3，v4，v5），（v6，max（v7，v8）））

中func函数的实参个数是____________。

18.变量a中的数据用二进制表示的形式是01011101，变量b中的数据用二进制

表示的形式是11110000，若要求将a的高4位取反，低4位不变，所要执行运

算是______。

19.设fp为指向某二进制文件的指针，且已读到此文件末尾，则函数feof（fp）

的返回值为____________。

20.已有定义：double*p；请写出完整的语句，利用malloc函数使p指向一个双

精度型的动态存储单元______。

21.C程序经过编译、______步骤之后才能形成一个真正可执行的二进制机器指

令文件。

【JAVA】:

16.FileInputStream是字节流；BufferedWriter是字符流；ObjectOutputStream

是____________。

17.保证JAVA语言可移植性的特征是____________。

18.如果有一个类MyFrame是Frame的子类，能够被不同包中的类所使用，请写

出该类的声明头：______。

19.在java中，用package语句说明一个包时，该包的层次结构必须与______

相同。

20.在java中，能实现多重继承效果的方式是______。

21.线程在生命周期中要经历5状态，分别是新建状态、可运行状态、运行状态、

______状态和终止状态。

二、选择题，共8分，每空1分

1.采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为

______。

2.在C++中，下列函数______不能重载。

3.下面程序段的时间复杂度为______。

For（int i=0；i

For（int j=0；j

a[i][j]=i*j;

A.O(m2) B.O(n2) C.O(m*n) D.O(m+n)

4.如果事务T获得了数据项Q上的排它锁，则T对Q______。

A.只能读不能写 B.只能写不能读

C.既可读又可写 D.不能读不能写

5.一进程刚获得三个主存块的使用权，若该进程访问页面的次序是｛1321215123｝，采用LRU算法时，缺页数是______次。

A.3 B.4 C.5 D.6

6.在下面的两个关系中，职工号和部门号分别为职工关系和部门关系的主键（或

称主码）职工（职工号、职工名、部门号、职务、工资）

部门（部门号、部门名、部门人数、工资总额）

在这两个关系的属性中，只有一个属性是外键（或称外来键、外码、外来码），

它是______

A.职工关系的“职工号” B.职工关系的“部门号”

C.部门关系的“职工号” D.部门关系的“部门号”

7.某二叉树的前序和后序序列正好相反，则该二叉树一定是_______的二叉树。

A.空或只有一个节点 B.高度等于其节点数

C.任一结点无左孩子 D.任意节点无右孩子

8.有权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼数，它的带权路径

长度为_______。

A.24 B.71 C.48 D.53

三、问答题（共10分）

1.接口是否可继承接口？抽象类是否可实现接口？抽象类是否可继承实体类？

（共3分）

2.TCP和UDP的区别？（共2分）

3.列举面向对象的特征，并介绍主流面向对象语言中数据类型的分类及该类型存

储位置之间区别？（共5分）

四、程序题，共30分

1. 阅读以下说明和C程序，将应填入__(n)__处的字句写在答题纸对应栏内。

（共10分、每空2分）

说明：假设需要将N个任务分配给N个工人同时去完成，每个人都能承担

这N个任务，但费用不同。下面的程序用回溯法计算总费用最小的一种工

作分配方案，在该方案中，为每个人分配1个不同的任务。

程序中，N个任务从0开始依次编号，N个工人也从0开始依次编号，

主要的变量说明如下：

C[i][j]:将任务i分配给工人j的费用；

task[i]:值为0表示任务i未分配，值为j表示任务i分配给工人j；

worker[k]:值为0表示工人k未分配任务，值为1表示工人k已分配

任务；

mincost:最小总费用。

【C 程序】

#include

#define N 8 /*N 表示任务数和工人数*/

Int c[N][N];

unsigned int mincost=65535; /*设置的初始值，大于可能的费用*/

int task[N], temp[N], worker[N];

void plan(int k,unsigned int cost)

{ int I;

if (__(1)__&& cost

mincost=cost;

for(i=0; i

else{

for(i=0; i

if (worker[i]==0 &&___(2)__){

worker[i]=1; task[k]=__(3)__;

Plan(__(4)__,cost+c[k][i]);

__(5)__; task[k]=0;

}/*if*/

}

}/*Plan*/

voin main()

{ int I,j;

for(i=0; i

全局数组的初值*/

worker[i]=0; task[i]=0; temp[i]=0;

for(j=0; j

scanf(“%d”,&c[i][j]);

}

Plan(0, 0) /*从任务0开始分配*/

printf(“\n 最小差用=%d\n”, mincost);

for(i=0; i

printf(“Task% isassigned to Worker%d\n”,I,temp[i])

} /*main*/

2. 阅读以下说明，回答问题1至问题4，将解答填入答题纸的对应栏内。（共

10分）

说明：

某宾馆需要建立一个住房管理系统，部分的需求分析结果如下：

(1) 一个房间有多个床位，同一房间内的床位具有相同的收费标准。

不同房间的床位收费标准可能不同。

(2) 每个房间有房间号（如201、202等）、收费标准、床位数目等信

息。

(3) 每位客人有身份证号码、姓名、性别、出生日期和地址等信息。

(4) 对每位客人的每次住宿，应该记录其入住日期、退房日期和预付

款额日期。

(5) 管理系统可查询出客人所住房间号。

根据以上的需求分析结果，设计一种关系模型如图 2-1 所示：

图 2-1 住房管理系统的实体联系图

1）根据上述说明和实体-联系图，得到该住房管理系统的关系模式如下所示，请

补充住宿关系。（2分）

房间（房间号，收费标准，床位数目）

客人（身份证号，姓名，性别，出生日期，地址）

住宿（______、_______，入住日期，退房日期，预付款额）

2）请给出问题1住宿关系的主键和外键。（2分）

3）若将上述关系直接实现为对应的物理表，现需查询在2005年1月1日到2005

年12月31日期间，在该宾馆住宿次数大于5次的客人身份证号，并且按照

入住次数进行降序排列。下面是实现该功能的SQL语句，请填补语句中的空

缺。（3分）

SELECT 住宿.身份证号,count(入住日期) FROM 住宿，客人

WHERE 入住日期 >= ‘20050101’ AND 入住日期

AND 住宿.身份证号 = 客人.身份证号

GROUP BY _(2)_

_(3)_ count(入住日期) >5

_(4)_

4）为加快SQL语句的执行效率，可在相应的表上创建索引。根据问题3中的SQL

语句，除主键和外键外，还需在那个表的的哪些属性上创建索引，应该创建

什么类型的索引，请说明原因。（3分）

3. 完成下列的快速排序算法，可以选择C或JAVA部分解答。（10分）

【C】: int partitions(int a[],int low,int high) void quicksort(int

a[],int n)

{int pivotkey=a[low]; {___(5)___;

//a[0]=a[low]; }

While(low

{while(___(1)___) //#include

--high; #include”myfunc.h”//存放于

个人函

a[low]=a[high]; 数库中

while(___(2)___) main()

++low; {int

a[high]=a[low];

i,a[11]={0,11,12,5,6,13,8,9,14,7,10};

}

for(i=0;i

//a[low]=a[0]; printf(“\n”);

a[low]=pivotkey; quicksort(a,10);

return low; for(i=0;i

} printf(“\n”);

void qsort(int a[],int low,int high) }

{int pivottag;

if(___(3)___)

{//递归调用

pivottag=___(4)___;

qsort(a,low,pivottag-1);

qsort(a,pivottag+1,high);

}

}

【JAVA】：

/**

*快速排序

*/

Public static void main(String [] args) {

Random random =new Random();

Int[] pDtat=new int[10];

For(int i=0;i

Integer a=random.nextInt(100);

pData[i]=a;

System.out.print(pData[i]+””);

}

System.out.print();

Int left=0;

Int right=pData.length-1; (1) for(int i=0;i

System.out.print(pData[i]+””); } System.out.println();

}

Public static int[] Sort(int[] pData,int left,int right){ Int middle,str Temp;

Int i=left;

Int j=right; Middle= (2) ; do{ While( (3) ) I++; While( (4) ) j--; if(i

System.out.print(pData[k]+””); } System.out.println();

}while( (5) );//如果两边扫描的下标交错，完成一次排序

If(left

Sort(pData,left,j);//递归调用 If(right>i)

Sort(pData,i,right);//递归调用 Return pData;

}

}