l. 数据结构 (75 分)
2 操作系统或C语言程序设计 (75 分)
报考010 信息科学技术学院下述5个专业的考生请选择操作系统作答
081201 计算机系统结构
081 202 计算机软件与理论
081203 计算机应用技术
085400 电子信息(专业学位)下设 02(全日制)计算机技术
报考044 智能科学与工程学院下述 2 个专业的考生请选择C语言程序设计作答
0812 Z3 人工智能考试科目：848 计算机基础综合
085400 电子信息(专业学位)下设01(全日制)人工智能
考生注意： 所有答案必须写在答题纸(卷)上，写在本试题上一律不给分.
第一部分 数据结构 ( 75 分)
一、 单项选择题(每题 1 分 ，共 8 分)
1. 为了操作方便，用单链表表示的 链式队列的队头应设在链表的( )位置。
A. 表头 B. 表尾 C. 表头和表尾均可 D. 链中
2. 一棵完全二叉树上有2001 个结点，其 中叶子结点的个数是 ( )。
A.500 B.501 C.1000 D.1001
3. 采 用邻接表存储的图，其深 度优先遍历类似千二叉树的( )。
A. 先序遍历 B.中序遍历 C. 后序遍历 D. 按层次遍历
4. 在含有N 个结点的线索二叉树中线索的数目为( )。
A. 2N B. N C. N-1 D. N+l
5. 若有一个栈的输入序列是I , 2 , 3, ... , n, 输出序列的第一个元素是 n, 则第 i 个输出元素是( )。
A. n-i B.n-i-1 C. n-i+ l D不确定
6. 二维数组行下标的范围从0 到 5 , 列下标的范围从 0 到 4, M 按行存储时元素M[3][4]的地址与M 按列存储时元素( )的地址相同。
A.M[l][4] B.M[3][4] C.m[1][3] D.M[4][4]
7. 已知一个有序表为 (18 , 26, 35, 59, 63, 75, 81), 则折半查找35 需要比较( )次。
A.I B.2 C.3 0.4
8. 以下排序算法中，占用辅助空间最多的是 ( )。
A堆 排序 B希 尔排序 C快速排序 D归 并排序
二.判断题(每题1分，共10分， 正确的写True, 错误的写false)
l. 栈和字符串都是线性结构.
2. 线性表中的每一个元素都有一个前 驱和一个后继元素。
3. 一棵树转换为二叉树后， 根结点没有右孩子.
4. 拓扑排序是一种内部排序的仅法.
5. 在中序线索化链表中， 如果结点有右子树，则结点的后继为对右子树进行中序遴历时访问的第一个结点.
.6 在一个有向图的邻接表或逆邻接表中，如 果某个顶点的链表为空， 则该顶点的度一定为零。
7. 哈夫曼树中权值最小的结点离根最近.
8. 无向图的邻接矩阵一定是对称的.
9. 用邻接矩阵法存储一个图时，在 不考虑压缩存储的情况下， 所占用的存储空间大小与图中结点的个数有关，而与图的边数无关。
10. 由同一 组关键字集合构造的各棵二叉排序树的形态不一定相同， 但平均查找长度相同。
三.填空题(共5 空，每空2 分，共10 分)
1、一组记录的关键字为( 87, 41, 52, 47, 36, 23, 89, 7 ) , 则利用归并排序的方法对该序
列作递增排序时第一趟排序的结果为 (1) 。
2、高度为h 的完全二叉树至少有 (2) 个结点，最多有 (3) 个结点。
3、如果一颗二叉树MT 是由有序树T 转换而来的， 那么 MT 中结点的中序遍 历序列相当于树中结点的 (4) 序列。
4 、 一组记录的排序码为(45, 56, 49, 33, 20, 72, 87, 30), 则利用快速排序的方法，以 第一个记录为基准得到的第一次划分结果为 (5) 。
四.简答题(共 4 小题，每题6 分，共24 分)
1. 若二叉树中各结点值均不相同。已知一个二叉树的前序和中序分别为 ABCDEFGH 和BDCEAFHG, 请画出此二叉树。
2. 应用栈操作求解算术表达式： 7+3X (5+6), 画出栈的变化过程。
3. 设有6 个字符 ( a, b, c, d, e, f), 其权值为( 14, 13, 16, 12, 18, 17), 请构造其Huffman
树， 给出它们的Huffman 编码以及编码的平均长度。
4. 设关键字序列为(15, 27, 50, 73, 49, 61, 37, 60), 散列表长m= l 4, 哈希函数为H(k)=k
mod I J. ( 1 ) 试给出采用二次探测法处理冲突的散列表; ( 2 ) 查找关键字49 时， 需要依次与哪些关键字比较; (3 ) 求等概率下查找成功的平均查找长度。
五.编写算法 (共 3 小题，每小题 7-8分，共 23 分)
I. 假设二叉树采用二叉链表存储， 试写出中序遍历二叉树的非递归算法，要求：先描 述二叉树的数据类型。(7 分)
2. 编写实现栈的两个基本运算的函数：入栈和出栈 (要求 采用顺序存储结构)。(8 分)
3. 假设无向图G 采用邻接表存储，编 写程序， 判断图G 是否是连通图。如果是连通图返回I,否则 返回 0。要求先给出算法思想，再写出相应代 码。(8 分)
第二部分 操作系统 ( 75 分)
一、判断题(每小题)分，共10 分，正确的回答True, 错误的回答Fal se)
1. 外存的连续组织方式比链式组织方式更能节省存储空间。
2. 分页管理比分段忤理更适合动态链接的存储方式 .
3. 管程每次只允许一个进程进入.
4. 进程在临界区内执行是不允许中断的.
5. 磁盘调度算法中、最短寻道时间优先(SSTF)算法会产生 ”饥饿“现象。
6. 操作系统提供给程序员的接口是库函数。
7. 在虚存系统中，只要磁盘空间无限大， 作业就能拥有任意大的地址空间。
8. 所有进程都进入等待状态时，系 统陷入死锁。
9. 对于一个具有三级索引表的文件，存取一个记录需要访问三次磁盘。
10. 并发性是指若干事件在同一时刻发生。
二、填空题(每小题1 分，共10 分)
I. 辅存空闲块的管理方法有(写出三种以上)： (1) 。
2. 常用的存储保护技术有： (2) 。
3 . 分页存储管理的置换策略有(写出三种以上)：(3)。
4. 有两个程序： A 程序按顺序使用CPU IO 秒、设备甲5 秒、CPU5 秒、设备乙10 秒、CPU IO秒 ; B 程序按顺序使用设备甲10 秒、CPU IO 秒、设备乙5 秒、CPU S 秒、设备乙10 秒。在顺序环境下， 执行上述程序， CPU 的利用率约为 (4) '若允许它们采用非抢占方式并发执行，若不考虑切换等开销，则 CPU 的利用率约为 (5) 。
5. 在页式和段式存储管理中， (6) 。存储管理提供的逻辑地址是连续的。
6. UNIX 进程间的通信机制主要有(写出四种或以上)： (7) 。
7. 设备独立性概念的要点是： (8) 。
8 . 设备的1/0 方式主要有程序轮询方式、中断方式和(9) 。
9. 稷盖技术与虚拟存储器都能扩充内存， 它们之间的主要区别是： (10) 。
三、单选题(每小1题分，共10 分)
I. 磁盘的I/0 控制主要采取( )方式。
A程 序I/0 8.中断 C.DMA D.SPOOLing
2. 位示图可用于 ( )。
A.文件目录的查找 B 磁盘空间的管理
C.内存空间的共享 D实 现文件的保护和保密
3. UNIX 文件系统对磁盘空间的管理采用( )。
A. FAT表法 8 . 位示图法 C. 空闲块链接法 D. 空闲块成组链接法
4. 在可变式分区分配方案中，某一作业完成后，系统收回其主存空间，并与相邻空闲区合并，为此需修改空闲区表， 造成空闲区数减1 的情况是( )。
A. 无上邻空闲区，也无下邻空闲区 B.有上邻空闲区，但无下邻空闲区
C. 有下邻空闲区，但无上邻空闲区 D有上邻空闲区，也有下邻空闲区
5. 产生死锁的主要原因是进程运行推进的顺序不合适及( )。
A. 系统资源不足和系统中的进程太多
B. 资源的独占性和系统中的进程太多
C. 进程调度不当和资源的独占性
D. 资源分配不当和系统资源不足
6. 实时系统的引入是为了使计算机( )响应外部事件的请求
A. 快速 8 . 按对象要求时间 C. 按人反应速度 D. 按人动作的速度
7. 信号量用于解决互斥问题时( )。
A. 其初值必须为正数 B. 其初值必须为正整数
C. 其初值可以为 0 D. 其初值为 1
8. 通道在输入输出操作完成或出错时， 就形成( )等候CPU 来处理。
A. 硬件故障中断 B. 程序中断 c. 外部中断 D. I/ 0 中断
9.计算机操作系统中，若 WAIT、SIG NAL 操作的信号量S 初值为3, 当前值为-2, 则表示当前有( )个等待信号量S 的进程。
A. I B. 2 C. 3 D.O
10银行家算法是一种( )算法
A. 死锁避免 B. 死锁预防 C. 死锁检测 D. 死锁解除
四、简答题(每小5题分，共25 分)
].使用文件前为什么要先打开文件简?述打开文件/home/userO1/myfile 的过程?
2. 页式虚拟存储管理采用位示图技，术设主存有16384 块，采用32位的512个字作为位示图。若块号、字号和位号(从高位到低位)分别1从、0、0开始。试计算：5998 块对应的字号和位号：198字的20位对应千哪一块?
3. 进程控制块包含哪些类型的信息?进程控制块的信息太多内存放不下应该怎样解决?
4. 操作系统中为什么要引入缓冲技术，缓冲池技术有什么优点?
5. 分析下面的程序输出多少个A 和 B?
int main(void)
{ int i;
for(i=O; i <2; i++){
forkO;
printf("A");
｝
printf("B\n");
｝
五、应用题(每小题 10 分，共 20 分)
1. 有四个进程 A、B、C、D。进程 A 通过一个缓冲区不断地向进程 B、C、D 发送信息， A 每向缓冲区送入一个信息后，必须等 进程 B、C、D 都取走后才可以发送下一个信息， B、C、D对 A 送入的信息各取一次，请 用信号量机制实现他们之间的正确通信。( 10 分)
2. 某文件系统要存储的文件大小有以下统计规律：
( 1) 文件大小 l KB 占 40%
(2) l KB<文件 大小 6 KB 占 30%
(3) 6KB<文件大小 128KB 占 20%
(4) 128 KB<文件大小 768KB 占 8%
(5) 768 KB<文件大小 16 MB 占 2% 。
假设该文件系统的磁盘块大小为 1024 字节，盘块的编号 最长为 4 字节，文件描述结 构中可存放10个盘块 编号。 设计目标是使访问文件时具 有尽可能小的平均访问磁盘次数，请 为该系统设计文件的物理结构，用图文 描述其设计思想，并计算其平均访问磁盘次数。(10分)
第三部分 C 语言程序设计( 75 分)
一、 单项选择题(每题2 分， 共20 分)
l. 下列哪一项不是C 语言合法标识符(
A. Jq, ,_double).B. double_kp
C. double_2000 D. 2000_double
2. 已定义int i = l , double j = 3, 那么整型变氪int k = i/2 + 2*j 的值是多少?( )
A. 7 B. 5 C. 6 D. 3
3. 下列程序的输出是什么? ( )
#include int main(void) {
inti= l, j=2;
for (int k = O; k < 10; k++) i++;
j++;
prin顷"i = %d, j =¾d\n", i, j); return O;
｝
A. i = 11,j= 3B. i = 2, j = 3C. i= 11,j= 12D. i=2,j=12
4. 定义char strO = "I love China", 那么数组str 的长度是多少?( )
A. 10 B. 11 C. 12D. 13
5. 已定义整型变量i = 10 和j = 1, 且有赋值表达式廿j = 3 + i-- * 2, 经过上述赋值表达式运算之后 i 和 j 的值分别是多少?( )
A. i = 9, j = 23B. i= l0,j=23C. i = 9, j =24D. i = I0, j = 24
6. 如下程序使用关键字static 修饰函数func_x, 此时func_x具备如下哪种性质?( )
static int func_x(void)
A. 返回值无法修改
C. 函数无法被其他文件使用B. 函数内的变量变为静态变量
D. 函数返回值为静态变量
7. 函数func_c 的定义如下， 那么调用func_c(l, 2)会得到如下哪种结果?( )
void func_c(int a, int b) { a= a+ b;
b = a- b;
a= a- b;
printf("%d, ¾d", a, b);
｝
A. 1. 2 B. 1. 1 C. 2. 2 D. 2. I
s . 已 定义数组 int a[51 "' { I. 2. 3, 4. 5 }和指针 int • p "' &a[ 2I, 那么表达式- - • p ++的值是多少?
A. 2 8 . 3 C. 4 D. 5
9、已定义枚举 cnum WKD {su , mo, tu. th, fr, sa} wo rkday, 下列说法正确的是哪一项?( )
A. SU 是变量 B. mo 代表一个字符串
C. WKD 可以省略 D. sa 不能 与 fr 做比较
10. 对千函数 void func_c(int• ptr l , int ptr2) {ptr l ++; ptr2++;} , main 函数调用 func_c(p I, p2) 后 ，变 量 p l 和 p2 的值会出现下列哪种情况?( )
A. pl 的值发生变化，p2的值发生变化 B. p1 的值发生变化， p2的值不发生变化
C. pl 的值不发生变化，p2的值发生变化 D. p1的值不发生变化，p2的值不发生变化
二.判断题(每题1 分，共 10 分，正确的打√ 错误的 打 X)
1. 算法的特点之一是有穷性。
2. 结构体各个成 员变量之间的 地址都是相同的 。
3. 字符串就是字符数组。
4. C语言中，下列 程序会输出 " Hello JN U"。
char • Get usr st ringO {
char strO = "He llo JNU" ; return str;
｝
int main(void) {
char* p = Get_u sr_string(); printf("%s\n", p);
return O;
｝
5. 二进制文件与 ASCII文件只是编码方式不同， 其占用的存储空间相同。
6. 关键字extern可以将外部变量的作用域扩展到其他文件。
7. 指针就是地址。
8. C语言中，下列定义是不合法的。
int sum_array( int a[n], int n)
{
9. 数组名是指针变压.
10. 非静态的局部变量存在于内存中的栈区域
三.简答题(共3 小题，每题8 分， 共24分)
I. 给出循环for(表达式 I, 表达式2, 表达式3){ 循环体｝的执行过程。( 8 分)
2. 分别指出int *pO, int (*p)O, void *p 和 int *p[6的] 意义。(8 分)
3. 什么是动态分配内存? ( 2 分) 给出C语言提供的管理内存的函数名称及功能(6 分)
四.编写程序(共2 小题，第1小题8分，第2小题13 分，共21分)
I. 设计C 语言程序实现牌型识别，具体规则如下，用户输5入张牌， 根据这5 张牌的点数和花色识别出不同的牌型，规 定如果 5 张牌的花色相同那么牌型为Flush, 如果 5 张牌的大小刚好依次递进称为Straigh t。其中，牌 的点数从小到大为2, …，9, t, j, q, k, a, 花色为c, d, h, s。例如：
23456 (该行是用户对牌点数的输入)
shsss (该行是用户对牌花色的输入)
Straight (该行是程序判断牌型后的输出)
2 6 aj 9 ccccc Flush
23456
sssss
Straight and Flush
a) 给出程序设计的思路( 2 分)
b) 写出关键的程序代码(6 分)
2.队列是一种常用的数据管理工具，其特点是先进先出，对外提供队列是否为空和满、数据入队、数据出队、清空队列的接口函，数设计C 语言程序通过数组来模拟队列的功能。
a) 列出要实现上述功能的各个函数的声明和功能注释( 5 分)
b) 写出函数定义的关键程序代码( 8 分)
|
