福建省高职高专升本科入学考试计算机科学与技术专业知识试卷.doc

福建省高职高专升本科入学考试计算机科学与技术专业知识试卷

资料仅供参考
福建省高职高专升本科入学考试计算机科学与技术专业知识试卷
第一部分C语言程序设计(100分)
一、单项选择题(本大题共30小题，每小题2分，共60分)
在每小题列出的四个备选项中只有一个是符合题目要求的，请将正确答案代码填写在答题纸相应的位置上。写在试卷上不得分。
1．以下不属于合法C语言整型数的是
A．79L B．Oxab C．7e5 D．66
2．已知：int x=85：执行完(double)X后，x的数据类型是
A．int B．float C．double D．不确定
3．下面程序执行后的结果是
main()
{int x=108，y=017：
printf(“％2d，％2d＼n”，x，Y)： }
A．10，0l B．108，17 C．08，17 D．108，15
4．设下列A、B、C、D选项中的变量均已经定义或赋值，则下列正确的赋值语句是
A．i nt a=b=c=2： B．i++=k-9=j： C．c％=6：D．k=>f>=m
5．设整形变量x的值为3，则表示式“x>5？++x：--x，，的值是
A．3 B．4 C．2 D．1
6．假设所有变量均为整型，则表示式(a=3，b=6，++a，b++，a+b)的值为
A．9 B．10 C．1l D．12
7．判断char型变量cl是否为大写字母的正确的表示式为
A．’A’<=c1<=’Z’ B．(cl>=A)＆&(cl<=Z) C．’A’=cl ‖’Z’>=c1 D．cl>=’A’＆＆c1<=’Z’
8．若X为int型变量，则执行以下语句后，X的值为
X=10：X+=x-=X*X；
A．一180 B．180 C．0 D．-80
9．k=1； n=263；
do{k*=n％l0；
n／=l0； }while(n)；
问执行后，K的值为
A．6 B．36 C．18 D．0
10．下面程序执行后的结果是
Main（）
{int x=l，Y；
y=l；
if(x>0) （if(x>3)y=3；}
else y= -1；
printf(”％d＼n”，y)；}
A．1 B．-1 C．不确定 D．3
11．若变量已正确定义，要：将a和b中的数进行交换，下面选项中不正确的是
A．t=a，a=b，b=t； B．a=a+b，b=a-b，a=a-b； C．t=b；b=a；a=t；D．a=t；t=b；b=a；
12．问当a=l，b=0时下面程序段输出结果是
switch(a)
(case 0：printf(“0＼n”)；break；
case 1：switch(b)
{case 0：printf(“l＼n”)；
case l：printf(“2＼n”)；break；
case 2：printf(“3＼n”)；)
case 2：printf(“4＼n’’)；}
A．1 B．1 C．1 D．1
2 4 2
4
13．设有定义“int a，*p=＆a；”，以下scanf语句中能正确为变量a读入数据的是
A．scanf(‘‘％(1’’，P)； B．scanf(‘‘％(1”，a)； C．scanf(“％d"，＆p)； D．scanf(“％d”，*p)；
14．若有说明：int a[10]：则a数组元素的正确引用是
A．a[10] B．a[3．5] C．a(5) D．a[10一10]
15．已知a为整型变量，那么与表示式a!=0真假值情况不相同的表示式是
A．a>0 I l a<0 B．a C．!a==0 D．!a
16．若有说明：int a[][3]=(1，2，3，4，5，6，7，8，9，10}：则a数组第一维的大小是
A．不确定 B．5 C．4 D．定义有误
17．为了判断两个字符串sl和s2是否相等，应当使用
A．if(sl==s2) B．if(sl=s2) C．if(strcmp(sl，s2)==0) D．if(strcpy(sl，s2))
18．若有说明：int a[3][4]={0)：则以下正确的叙述是
A．只有元素a[0][0]可得到初值0 B．此说明语句不正确
C．数组a中各元素都可得到初值，但其值不一定是0 D．数组a中各元素都可得到初值0
19．设有定义：int a=2，b=3，c=4；，则以下选项中值为0的表示式是
A．(!a==1)&&(!b==0) B．a—b C．a＆&b D．a ‖(b+b)&＆(c-a)
20．已知： int a，b=32767;a=b+l; 则执行printf(“％d”，a)：的结果是
A．一1 B．65535 C．32768 D．一32768
21．以下程序的输出结果是
ff(int a，int b，int c)
{c=a+b;}
main()
{int c=7;
ff(c+l，c++，c);
printf(“％d＼n”，C);}
A．1 6 B．8 C． 15 D．7
22．下面程序的输出结果是
main()
{char a[20]={‘a’，’b’，’C’，’d’，’e’，’＼O’);
Drintf(“％s＼n"，a);
printf(“％s＼n”，a+1); )
A．abcde B．abcde＼0 C．abcde D．abcde＼0
bcde bcde＼0 cde cde
23．Main()
{int k=2;
{int k=l；printf(“％2d’’，k);}
printf(“％2d"，k);}
A．1 2 B．2 1 C．2 2 D．1 1
24. 当外部变量的作用域只限于本源程序单个文件时，应使用 加以声明
A。static B．extern C．auto D．register
25．有以下程序段
int n，t=2，s=0：
scanf (％d”，&n);
do{s=s+t; t=t-2; }while(t!=n);
为使此程序段不陷入死循环，从键盘输入的数据应该是
A．任意正奇数 B．任意负偶数 C．任意正偶数 D．任意负奇数
26．设函数fun的定义形式为 void fun(char ch，float x){…) 则以下对函数fun的调用语句中，正确的是
A．fun(”abc”，3．0); B．t=fun(‘D’，16．5); C．fun(‘65’，2．8); D．fun(32，32);
27．有以下程序
#define f(x)(X*X)
main()
{int i1，i2;
il=f(8)／f(4); i2=f(4+4)／f(2+2);
printf(”％d，％d＼n”，il，i2); }
程序运行后的输出结果是
A．64，28 B．4，4 C. 4, 3 D. 64, 64
28．以下程序的输出结果是
Main()
{struct cmplx{int x;int Y;)cnum[2]={2，4，3，1)；
printf(”％d＼n”，cnum[0]．y／cnum[0]．x*cnum[1]．y); }
A．0 B．2 C．3 D．6
29．若要用fopen函数打开一个新的二进制文件，该文件要既能读也能写，打开时的文件使用方式是
A．”ab+” B．” wb+” C. “rb+” D. “ab”
30．#include<stdio．h>
main()
{char cl=’1’，c2=’2’;
cl=getchar(); c2=getchar 0;
putchar(c1)，P putchar(c2); }
当运行时输入:a<回车>后，以下叙述正确的是
A．变量c1被赋予字符a，c2被赋予回车符 B．程序将等待用户输入第2个字符
C．变量cl被赋予字符a，c2中仍是原有字符2 D．变量c1被赋予字符a，c2中将无确定值
二、程序阅读题(本大题共4小题，每小题5分，共20分)
阅读下列程序，将输出结果写到答题纸的相应位置。写在试卷上不得分。
31．Main()
{static int X[]={2，3，4);
int s，i，*p;
s=l; p=x;
for(i=0;i<3；i++)
s*=*(p+i);
printf(”％d＼n”，s); }
32．main()
{int i，j，x=0;
for(i=0;i<2;i++)
{x++;
for(j=0;j<=3;j++)
{if(j％2)
continue;
x++;
printf(”x=％d＼n”，x); }
33．Main()
{char s[]=”ABCD”，*p;
for(p=s：p<s+4；p++)
printf(”％s＼n”，p);}
34．int f(int b[]，int 13)
{int i，r=l;
for(i=l：i<=n;i+=2)
r=r*b[i]; return r; }
main（）
{int x，a[]={1，2，3，4，5，6，7，8，9);
x=f(a，6);
printf(”x=％d＼n”，X); }
三、完善下列程序(本大题共3小题，每空2分，共20分)
请在答题纸相应的位置上填上正确答案。写在试卷上不得分。
35．下面程序是输出两个字符串中对应相等的字符。
Maln（）
{char x[ ]=“programming”, y[ ]=” Fortran”：
int i=0：
whi le( ① )
if(x[i]==y[i]) ·
printf(”％c”， ②)：
else ③ ； )
36．下面程序的功能是从3个红球，5个白球，6个黑球中任取8个，且其中至少要有1个白球，输出所有可能的方案。
Main（）
{int i，j，k；
for(i=0；i<=3：i++)
for( ①)
(k= ② ：
if(k>=0&& ③ )
printf(‘‘％3d，％3d，％3d＼n’’，i，J，k)； } }
37．下面程序的功能是将一组字符中的大写字母转化成小写字母并输出，其它字母照原样输出，读到“木”号时退出。
#include”stdio．h”
main()
{char ch；
printf(”Please input string：”)；
ch=getchar 0；
while( ① )
{
if( ② &＆ ③ )
④ ；
Putchar（ch);
ch=getchar 0; } }
第二部分数据结构(共1 00分)
一、单项选择题(本大题共1 2小题，每小题2分，共24分)
在每小题列出的四个备选项中只有一个是符合题目要求的，请在答题纸相应位置上填上正确答案。写在试卷上不得分。
1．用非递归方法实现递归算法时一般要使用
A．循环队列 B．栈 C．二叉树 D．双向队列
2．对于一个具于n个顶点和e条弧的赋权有向图，如果用赋权邻接矩阵表示这个图，请问求单源最短路径的Dijkstra算法的时间复杂度为
A．0(n) B．O(n+e) C．0(n) D．0(2e)
3．设语句x++的执行时间是单位时间，则以下语句的时间复杂度为
for(i=l;i<=n;i++)
for(j=I;j<=n;j++)
X++;
A．0(1) B．0(n)
4．一棵高度为h的非空二叉树(设只含根结点的二叉树的高度为1)最多有( )个结点。
A．2h B．2h—l
5．赋权有向图G用邻接矩阵A存储，则顶点i的入度等于
A．第i行非∞的元素之和 B．第i列非∞的元素之和
C．第i行非∞且非0的元素个数 D．第i列非∞且非0的元素个数
6．设双链表的结点类型定义如下：
typedef struct node * link：
typedef struct node{
Listltem element;
link left; link right;
}*p，*q，r
删除双链表中结点P(由P指向的结点)的操作是
A．q=p->left：r=p->right：q->right=r：r->1eft=q： B．q=p->right；r=p->eft：q->right=r：r->left=q：
C．q=p->left：r=P->right：q->left=r：r->right=q： D．q=p->left：r=p->right：q->right=r->left：
7．会引起循环队列队头位置发生变化的操作是
A．出队列 B．入队列 C．取队首元素 D．取队尾元素
8．如图l所示，若从顶点Vl(Vl表示顶点①)出发进行广度优先搜索，则得到的顶点的访问序列为

A．V1→V8→V3→V4→V5→V6→V7→V2 B．V1→V2→V3→V7→V5→V6→V4→V8
C．V1→V2→V5→V4→V3→V6→V7→V8 D．V1→V2→V3→V4→V5→V6→V7→V8
9．下列排序算法中，时间复杂度不受数据初始状态影响，为0(nlogn)的是
A．堆排序 B．冒泡排序 C．直接选择排序 D．快速排序
10．用指针实现二叉树时，在n个结点的二叉树中含有( )空指针。
A．n B．n．1 C．n+l D．2n
11．对一棵二叉搜索树进行( )得到的结点的访问序列是一个有序序列。
A．前序遍历 B. 中序遍历 C．后序遍历 D．层次遍历
12．合并排序算法的时间复杂度为
A．0(n2) B．0(nlogn) C．0(10gn) D．0(n)
二、填空题(本大题共7小题，每空2分，共16分)
请在答题纸相应的位置上填上正确答案。写在试卷上不得分。
13．在一个长度为n的顺序表的第i(1≤i≤n)个元素之前插入一个元素，需要后移 个元素。
14．设某哈夫曼树有n个叶子结点，则该哈夫曼树的总结点数是 。
15．设有一序列8、53、37、28，当使用直接插入排序从小到大排序时，其比较次数 。
16．设SQ为循环队列，存储在数组queue[0．．m一1]中，则SQ入队操作对其队尾指针rear的修改是
17．若待排序的序列中存在多个记录具有相同的键值，经过排序，这些记录的相对次序依然保持不变，则称这种排序方法是 的，否则称为 的。
18．在一个具有n个顶点的无向图中，要连通所有顶点则至少需要 条边。
19. 在有向图中，以顶点v为起点的弧的数目称为v的
三、应用题(本大题共4小题，每小题10分，共40分)
请在答题纸相应位置上填上正确答案。写在试卷上不得分。
20．已知关键字序列(12，77，21，65，38，7，40，53)，采用直接插入排序法按关键字递增排序，给出每一趟排序的结果。
21．已知散列表长度为10(散列地址空间为0．．9)，使用线性重新散列技术解决冲突，现有一组单词(SUN，MON，TUE，WED，’TH[J，FRI，SAT)，其对应的散列函数值分别为(3，2，6，3，2，5，6)，请画出插入这组单词后的散列表a
22．假设一棵二叉树的先序(前序)序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK。
(1)请画出该二叉树：
(2)请写出该二叉树的后序遍历序列。
23．根据Prim算法画出图2中的赋权无向图G的最小生成树，要求依次画出从顶点①开始生成最小生成树的
过程。

四、算法设计题(本大题共2小题，每小题10分，共20分)
请在答题纸相应位置上填写上正确答案。写在试卷上不得分
24．阅读下面的程序，它将集合A和集合B归并为一个集合C，归并前集合A和集合B中的元素按值非递减有序排列，归并后集合C中的元素仍按值非递减有序排列且集合C不需要另建新表的结点空间。集合的链表结点结构定义如下，请完善下列程序。
typedef struct LNode{
ElemType data；
struct node *next；
}*LinkList；
void MergeSet(LinkList La,LinkList Lb)
{ LinkList pa,pb，pc，p；
pa=La；
pb=Lb；
pc=NULL； ／／NULL表示空指针；
while( ① )
{ If (pa->data<=pb->data)
{ if(pc!=NULL)
{ ② ；
P=p->next； }
Else {
pc=pa; p=pc; }
③ ; }
else
{ if(pc!=NULL)
{ ④ ； P=->next; }
else
{ pc=pb；
p=pc； }
⑤ ；} }
p->next=(pa!=NULL)?pa：pb； }
25．二叉排序(搜索)树t以二叉链表为存储结构，请编写算法实现在二叉排序树上查找值为x的结点。
相关类型定义如下：
typedef int TreeItem；
typedef struct btnode *btlink；
typedef struct btnode{
Treeltem data；
btlink lchild，rchild； /*左右孩子结点指针*／
}BiTNode；
算法的函数原型给定为：BiTN0de LocateX(BiTNode*t，TreeItem x)。
第三部分 操作系统(共1 00分)
一、单项选择题(本大题共1 5 dJ、题，每小题2分，共30分)
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将其代码填写在答题纸相应的位置上。写在试卷上不得分。
1．操作系统是一种
A．系统软件 B．应用软件 C．通用软件 D．工程软件
2．分时操作系统为用户服务采用的策略是
A．短作业优先 B．时间片轮转 C．可靠性和灵活性 D．先来先服务
3．经过下面的数据结构，操作系统能对进程进行管理的是
A．PCB B．DCI、 C．CHCI、 D．．ICB
4．一般地缓冲池位于
A．磁盘 B．寄存器 C．内存 D．设备控制器
5．一个运行的进程用完了分配的时间片后，状态将变为
A．运行 B．等待 C．就绪 D．由用户自己确定
6．对进程的管理和控制使用的是
A．指令 B．信号量 C．信箱通信 D．原语
7．对于两个并发进程，设互斥信号量IIlutex，若murex：：一l，则表示
A．没有进程进入临界区 B．有一个进程进入临界区
C．有一个进程进入临界区，另一个在等待 D．两个都进入临界区
8．系统“抖动”现象的发生是由于下面因素引起的
A．交换的信息量过大 B．请求页式管理方案 C．内存容量不足 D．交换算法选择不当
9．经过硬件和软件的功能扩充，把原来独占的设备改造成能为若干用户共享的设备，这种设备称为
A．存储设备 B．系统设备 c．虚拟设备 D．用户设备
10．一个文件的相对路径指定总是开始于
A．根目录 B．当前目录 C．多级目录 D．子目录
11．位示图用于
A．磁盘空间的管 B．主存空间的共享 C．文件目录的查找 D．文件的保护与加密
12．Linux系统中，内存管理采用的是
A．通道技术 B．SPOOl。ING技术 C．虚拟文件管理技术 D．虚拟存储技术
13．在各种作业调度算法中，若所有作业同时到达，则平均等待时间最短的算法是
A．先来先服务 B．高响应比优先 C．短作业优先 D．优先数
14．NFS表示的是
A．磁盘系统 B．网络文件系统C．中断系统 D．操作系统
15．避免死锁的一个著名算法是
A．先入先出法 B．优先级算法 C．资源按序分配法 D．银行家算法
二、填空题(本大题共7'JI、题，每空2分，共20分)
请在答题纸相应的位置上填写正确答案。写在试卷上不得分。
16．文件系统采用二级目录结构，目的是能够解决 问题。
17．在可变分区管理中，最先适应法(FF)是按分区的 顺序排列空闲内存块的。
18．通道是独立于主CPU的专用于输入输出的 。
19．操作系统提供的两个接口是 和 。
20．若干事件在同一时刻发生称为 ；在同一时间间隔内发生称为 。
21．文件 ，是指避免因有意或无意的操作使文件受到破坏
22．有如下磁盘服务请求队列：88、23、180、67、35、48、124、65，当前磁头在53道，若按FCFS和最短查找时间优先算法，磁头移动的磁道序列分别是 ; .
三、简答题(本大题共4,JI、题，每小题5分，共20分)
请在答题纸相应的位置上填写正确答案。写在试卷上不得分。
23．试说明临界资源与临界区的概念，它们有何不同?
24．在设备管理中，为什么要引入缓冲区?缓冲区有哪些类型?
25. 内存管理有哪些主要功能?其目的是什么?
26．简述SPOOLING系统的组成及各组成软件模块的作用。
四、综合应用题(本大题共3小题，每小题1 0分，共30分)
请在答题纸相应的位置上填写正确答案。写在试卷上不得分。
27．假设缓冲区由n个单元组成，信号量mutex用于生产者与消费者的互斥，初值为1，设empty是生产者的私有信号量，表示缓冲区中空单元数，初值为n，设full是消费者的私有信号量，表示缓冲区中非空单元数，初值为0。
试分析下列算法(程序)在解决生产者～消费者同步问题时会产生什么后果?请回答问题并写出正确的生产者与消费者进程的同步算法(程序)。
生产者进程： 消费者进程：
begin begin
P(mutex) P(mutex)
P(empty) P(full)
送数据到缓冲区某单元 取缓冲区某单元数据
v(full) V(empty)
V(mutex) V(mutex)
end end
28. 设有一组作业，它们的提交时间与运行时间如下所示，试求在单道程序(不可抢占)方式下，采用高响应比优先算法，作业的执行顺序和平均周转时
作业号 提交时间 运行时间(分钟)
1 9：00 55
2 9：40 20
3 9：50 10
4 10：10 5
29. 若在一分页存储管理系统中，某作业的页表如下所示，已知页面大小为1024字节，试将逻辑地址101 1，2148，5012转换为相应的物理地址。
页号 块号
0 2
1 3
2 1
3 6