|
第一部分 客观题
一、 单项选择题(第1-20题，每小题1分，第21-30题，每小题2分，1-10题为操作系统部分，11-20题为数据结构部分，21-30题为C语言程序设计部分)
1-10操作系统部分
1. 下列关于管道（Pipe）通信的叙述中，正确的是( )。
A.一个管道可实现双向数据传输
B.管道的容量仅受磁盘容量大小限制
C.进程对管道进行读操作和写操作都可能被阻塞
D.一个管道只能有一个读进程或一个写进程对其操作
2. 避免死锁的一个著名的算法是( )。
A.先入先出法 B.银行家算法
C.优先级算法 D.资源按序分配法
3. 在9个生产者，6个消费者共享容量为8的缓冲区的生产者-消费者问题中，互斥使用缓冲区的信号量S的初始值为（ ）。
A.8 B.1 C.9 D.6
4. 一种既有利于短小作业又兼顾到长作业的作业调度算法是（ ）。
A.先来先服务 B.轮转 C.最高响应比优先 D.均衡调度
5. 分布式操作系统与网络操作系统本质上的不同在于（ ）。
A.实现各台计算机之间的通信
B.共享网络中的资源
C.满足较大规模的应用
D.系统中若干台计算机相互协作完成同一任务
6. 假定磁盘块的大小为1K，对于1.2MB的软盘，FAT需占用（ ）的存储空间
A. 1KB B. 1.5KB C. 1.8KB D. 2.4KB
7. 关于线程以下的说法正确的是（ ）。
A.同一进程中各线程可以共享进程的主存空间
B.同一进程中多线程不能独立执行
C.线程是资源分配的独立单位
D.线程是就是进程的另外一个称呼
8. 正在运行的进程需要向外设上输出数据，此时进程状态从（ ）。
A.等待态变为就绪态 B.运行态变为等待态
C.就绪态变为运行态 D.运行态变为就绪态
9. 有10个并发进程，每个进程对资源的最大需求数是3，当这10个进程共享m个资源时，m值最小取（ ）时不会发生死锁。
A. 3 B. 20 C. 30 D. 10
10. 当分时系统用户数为200个，对每个用户的响应时间为1s，时间片最大值是（ ）。
A. 5ms B. 10ms C. 200ms D. 0.1s
11-20数据结构部分
11. 若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是（ ）。
A.单链表 B.仅有头指针的单循环链表
C.双向链表 D.仅有尾指针的单循环链表
12. 循环链表的主要优点是（ ）。
A. 不再需要头指针
B. 已知某结点位置后能容易找到其直接前驱
C. 在进行插入、删除操作时能保证链表不断开
D. 从表中任一结点出发都能扫描整个链表
13. 将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为35的结点的左孩子编号为（ ）。
A. 34 B. 36 C. 70 D. 71
14. 按照二叉树的定义，具有3个结点的二叉树有（ ）种。
A. 3 B. 4 C. 5 D. 6
15. 任何一个无向连通图的最小生成树（ ）。
A. 只有一棵 B. 一棵或多棵 C. 一定有多棵 D. 可能不存在
16. 深度优先遍历类似于二叉树的（ ）。
A先序遍历 B中序遍历 C后序遍历 D层次遍历
17. 表达式a*(b+c)-d的后缀表达式是（ ）。
A. abcd+- B. abc+*d- C. abc*+d- D.-+*abcd
18. 如果无向图G必须进行两次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是 （ ）。
A.G肯定不是完全图 B.G中一定有回路 C.G一定不是连通图 D.G有2个连通分量
19. 算法的时间复杂度不是O(nlogn)的算法是（ ）。
A、快速排序 B.归并排序 C.堆排序 D.基数排序
20. 用邻接表表示图进行广度优先遍历时，通常采用（ ）来实现算法。
A.栈 B.队列 C.树 D.图
21-30 C语言程序设计部分
21. 下列哪一项是C语言合法标识符（ ）。
| A. int
|
B. extern
|
| C. 17_num
|
D. _1000_a
| 22. 已定义整型变量i = 5，j = 9，那么整型变量int k = i / 4 + 1.1 * j的值是多少？（ ）
23. 下列程序的输出是什么？（ ）
#include <stdio.h>
void swap(int p1, int p2) {
int *temp = &p1;
p1 = p2;
p2 = *temp;
}
int main(void) {
int i = 1, j = 2;
swap(i, j);
printf("i = %d, j = %d\n", i, j);
return 0;
}
|
| A. i = 1, j = 2
|
B. i = 2, j = 1
|
C. i = 1, j = 1
|
D. i = 2, j = 2
| 24. 对于整型数组a[8]和b[8]，下列说法正确的是哪一项（ ）
| A. a = b是合法的
|
B. 表达式a + 1 和 a + 2不能比较大小
|
| C. 赋值表达式*(a + 1) = *(b + 2)是合法的
|
D. a和&(*(a))的值不同
| 25. 已定义整型变量i和j，且i = 10，j = ++i * 3 - 8，经过上述赋值表达式运算之后i和j的值分别是多少？（ ）
| A. i = 11, j = 25
|
B. i = 10, j = 24
|
C. i = 11, j = 24
|
D. i = 10, j = 25
| 26. 如下程序使用关键字static修饰变量i，此时的i是何种变量？
static int i;
int main(void) {
…
}
| A. 静态全局变量
|
B. 静态局部变量
|
| C. 动态全局变量
|
D. 动态局部变量
| 27. 对于C语言的格式化输出，下列语句会得到哪种结果？（ ）
int i = 60;
printf("|%-6.3d|", i);
| A. |060 |
|
B. |060|
|
C. | 060|
|
D. |60|
| 28. 下列程序的输出是什么？（ ）
int a[2][3] = {0,0,1,1,2,2};
int (*p)[3] = a;
printf("%d", ++(*((*(p + 1)) + 2)));
29. 在定义int (*p)[8]中，p表示什么？（ ）
| A. p为函数指针
|
B. p是包含8个整形指针的数组
|
| C. p是指向由8个元素构成的一维数组的指针
|
D. p为指向整型变量的指针
| 30. 对于循环for(int i = 1; i < n; i++)，其循环体的执行次数为下列哪一项？（ ）
| A. n - 2
|
B. n - 1
|
C. n
|
D. n + 1
| 二、判断题(每小题1分，正确的写True，错误的写False，1-10题为操作系统部分，11-20题为数据结构部分，21-30题为C语言程序设计部分)
1-10 操作系统部分
1. 根据死锁定理，资源分配图中存在环路，就一定会产生死锁。
2. 虚拟存储器的容量是由用户和辅存所决定的。
3. 阻塞队列可能包含系统进程。
4. 只要破坏产生死锁的四个必要条件中的其中一个就可以预防死锁的发生。
5. 优化文件物理块的分布可显著地减少寻道时间，因此能有效地提高磁盘I/O的速度。
6. 字符设备指的是只能存取文本符号的设备。
7. 在用于同步时，信号量的初值设为负数表示缺少的资源个数。
8. 分时系统的时间片越小，响应速度越快，因此用户的满意度就越高。
9. 在内存利用率方面，分页存储管理比分段存储管理更高些。
10.任何手段都无法实现计算机系统资源之间的互换。
11-20 数据结构部分
11. 在一棵二叉树中，中序遍历的第一个结点，是二叉树的最左下结点。
12. 顺序表查找指的是在顺序存储结构上进行查找。
13. 已知一颗二叉树的先序序列和后序序列，一定能构造出该树。
14. 在一棵树中，堂兄弟的双亲是兄弟关系。
15. 不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。
16. 冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。
17. 分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。
18. 一个图按广度优先遍历的结果是唯一的。
19. 由树转化为二叉树，该二叉树的右子树不一定为空。
20. 无向图的邻接矩阵是对称的，因此可只存储矩阵的下三角阵。
21-30 C语言程序设计部分
21. C语言中，++运算符适用于float类型的变量，即如有定义float a，那么a++是合法的。
22. 结构体各个成员变量之间的地址都是相同的。
23. 在C语言中，常量没有数据类型。
24. 整型指针变量和字符型指针变量所占用的内存大小相同。
25. 二进制文件比ASCII文件占用更多的存储空间。
26. 局部变量一定存放在静态存储区。
27. 算数运算符的优先级高于关系运算符。
28. 除了注释以外，一段程序中的“{”和“}”的数量必须相同。
29. 以下程序的输出为0。
int a = 0;
if (a = 1)
printf("%d", a);
else
printf("0");
30. C语言动态分配的存储区域被称为堆区。
三、填空题（第1-10空，每空1分，第11-15空，每空2分，1-9题为操作系统部分，10-14题为数据结构部分）
1-9 操作系统部分
1. 为实现CPU与外部设备的并行工作, 系统必须引入（1）作为硬件基础。
2. 在磁盘调度策略中有可能使I/O请求无限期等待的调度算法是（2） 。
3. 在（3）的作业调度算法中，当各个作业等待时间相同时，运行时间短的作业将得到优先调度；当各个作业要求运行的时间相同时，等待时间长的作业得到优先调度。
4. UNIX的文件系统空闲空间的管理采用的是（4）法。
5. 同步机制要遵循的四条规则分别是空闲让进、忙则等待、 （5） 及让权等待。
6. 文件的三种物理结构是：顺序结构、（6） 、索引结构。
7. 分时系统的特点是：（7） 、交互性、独占性和及时性。
8. 虚拟存储器的特征是： （8） 、多次性、对换性和虚拟性。
9. n个进程共享m个同类资源(n≥m≥1,设信号量初值S=m)，S的值可能的变化范围是 （9） ，处于等待状态的进程数最多有（10）个。
10-14 数据结构部分
10．一组记录的排序码为(45，35，71，51，20，26，61，12)，则利用快速排序的方法，以第一个记录为基准得到的第一次划分结果为 （11） 。
11．在折半查找中，要求待查找的关键字序列必须 （12） ，这样才能进行查找操作。
12．设二叉树中度为0的结点数为30，度为1的结点数为20，则该二叉树中总共有 （13） 个结点数。
13．设矩阵是一个N×N对称矩阵，将其下三角部分按行序存放在一维数组中，对下三角部分中任一元素Aij(i>=j)，在一维数组中的下标位置k与i和j的关系为 （14） 。
14．在N个结点的线索二叉树中线索的数目为 （15） 。
第二部分 操作系统主观题
四、举例说明什么是实时系统中的优先级反转(或倒转)。(5分)
五、试比较内存管理和外存管理的异同点。(5分)
六、简述设备驱动程序的主要功能。(5分)
七、采取哪些措施才能提高文件检索的速度。(5分)
八、fork为创建进程的系统调用，下面的程序创建多少个子进程? 输出多少个A和B? (5分)
int main(void)
{ int i;
for(i=0; i<3; i++) {
if (fork()==0) printf("A");
}
printf(“B\n”);
}
九、一座小桥横跨南北两岸，南侧桥段和北侧桥段较窄只能通过一人，桥中央一处宽敞，允许两个人通过或歇息。南侧桥段和北侧桥段在任意时刻只允许一人过桥。请写出从北岸到南岸过桥的同步算法。(10分)
十、某系统的文件物理结构采用多级索引结构。索引结点共设置13个地址项，其中0到9项为直接地址项，后3项分别为一级、二级、三级间接地址。逻辑块和物理块大小均为1K字节，磁盘盘块地址占16位。(10分)
（1）请画出该文件系统文件索引结构示意图。
（2）列出计算该文件系统允许的最大文件的长度计算表达式。
（3）读取一个长256256字节的文件的全部数据，共需读盘多少次？
第三部分 数据结构主观题
十一、设一组初始记录关键字序列为（41，35，52，17，8，50，22，38），请分别给出第5趟简单选择排序和第4趟直接插入排序的结果。（5分）
十二、设计一数据结构，用来表示图的邻接矩阵存储结构（包括弧的结构和图的结构）。(5分)
十三、阅读下面的程序代码，写出此函数的功能。(5分)
void F( Bitree T, Stack& S )
{
if (T) {
Push( S, T->data );
if (!T->Lchild && !T->Rchild ) PrintStack(S);
else { F ( T->Lchild, S );
F( T->Rchild, S );
}
Pop(S);
}
}
十四、假设表中关键字序列为（41，36，58，12，79，25），将关键字依次插入一棵初始为空的二叉排序树，然后删除结点41。（1）画出二叉排序树的生成过程；（2）画出删除结点41后的二叉排序树。(6分)
十五、假设二叉树采用二叉链表存储结构，试编写一个非递归算法，输出中序遍历序列中第k个结点的数据值。(8分)
十六、试编写一个算法，在链式存储结构上实现直接插入排序算法。(8分)
十七、若矩阵Am*n中的某个元素aij是第i行中的最小值，同时又是第j列中的最大值，则称此元素为该矩阵中的一个马鞍点。假设二维数组存储矩阵Am*n，试编写求出矩阵中所有马鞍点的算法。(8分)
第四部分 C语言程序设计主观题
十八、在循环结构中，关键字break和continue的区别是什么？（8分）
十九、分别指出int *p(), int *p[6], void **p, 和int (*p)()的意义。（8分）
二十、简要介绍C语言中文件读写的安全标准流程。（8分）
二十一、奥林匹克运动会是四年一度的体育盛会，奖牌榜是展示各个国家奖牌数量的排行榜，排名规则如下：
j金牌数量优先级最高，即对于国家A和B，如果A的金牌数量多于B，那么A的排名高于B；
k银牌数量优先级次之，即对于国家A和B，如果A和B金牌数量相同，那么A和B的相对排名取决于银牌数量的相对大小；
l铜牌数量优先级最低，即对于国家A和B，如果A和B金牌、银牌数量相当的情况下才考虑铜牌数量，且排名由铜牌数量相对大小决定。（13分）
1. 给出奖牌榜排序算法的设计思路（5分）
2. 写出关键的程序代码（8分）
二十二、对于双精度的浮点数num，设计一个名为depart的函数，得到num的整数部分和小数部分，并将结果返回至main函数。（8分）
1. 给出设计思路和depart函数的原型（3分）
2. 给出函数实现的关键程序代码（5分）
|
您现在的位置： 