升研教育考研频道为23考研、24考研的同学们整理了“暨南大学2022年招收攻读硕士学位研究生入学考试试题：848计算机基础综合”的相关信息，希望对正在备考的你有所帮助。考研复习效率不高怎么办？自己备考抓不住重点？想报考985/211等热门院校，但是没把握？升研教育推出考研集训营，全日制封闭式面授，10余年授课经验的老师，浓厚的学习氛围助你冲击目标、一战上研！

暨南大学2022年招收攻读硕士学位研究生入学考试试题：848计算机基础综合

招生专业与代码:试卷内容结构

1.数据结构(75分)

2.操作系统或C语言程序设计(75 分)

报考010信息科学技术学院下述5个专业的考生请选择操作系统作答

081201计算机系统结构

081202计算机软件与理论

081203计算机应用技术

085400电子信息(专业学位)下设02(全8日制计算机技术

报考044智能科学与工程学院下述2个专业的考生请选择C语言程序设计作答

081223人工智能

085400电子信息(专业学位)下设01(全日制)人工智能

考试科目: 848计算机基础综合

第一部分数据结构(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

C. N-I

D. N+1

5.若有一个栈的输入序列是1, 2, 3, .... n,输出序列的第一个元素是n, 则第i个输出元素是()。

A. n-i .

B.n-i-1

C. n-i+1

D.不确定

6.二维数组行下标的范围从0到5,列下标的范围从0到4, M按行存储时元素M[3][4]的地址与M按列存储时元素( ) 的地址相同。

A.M[1][4]

B.M[3][4]

C.m[1][3]

D.M[4][4]

7.已知一个有序表为(18， 26, 35, 59, 63，75, 81), 则折半查找35需要比较( ) 次。

A.1

B.2

C.3

D.4

8.以下排序算法中，占用辅助空间最多的是()。

A.堆排序

B.希尔排序

C.快速排序

D.归并排序

二.判断题(每题1分，共10分，正确的写True,错误的写False)

1.栈和字符串都是线性结构。

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)，请构造其Huffiman树，给出它们的Huffman编码以及编码的平均长度。

4、设关键字序列为(15, 27, 50， 73，49， 61, 37, 60), 散列表长m=14,哈希函数为H(k)=k mod 11, (1)试给出采用二次探测法处理冲突的散列表; (2) 查找关键字49时，需要依次与哪些关键字比较; (3) 求等概率下查找成功的平均查找长度。

五、编写算法(共3小题，每小题7-8分，共23分)

1、假设二叉树采用二叉链表存储，试写出中序遍历二叉树的非递归算法，要求:先描述二叉树的数据类型。(7分)

2、编写实现栈的两个基本运算的函数:入栈和出栈(要求采用顺序存储结构)。(8 分)

3、假设无向图G采用邻接表存储，编写程序，判断图G是否是连通图。如果是连通图返回I,否则返回0.要求先给出算法思想，再写出相应代码。(8 分)

第二部分操作系统(75分)

一、判断题(每小题1分，共10分，正确的回答True,错误的回答False)

1、外存的连续组织方式比链式组织方式更能节省存储空间。

2、分页管理比分段管理更适合动态链接的存储方式。

3、管程每次只允许一个进程进入。

4、进程在临界区内执行是不允许中断的。

5、磁盘调度算法中，最短寻道时间优先(SSTF)算法会产生“饥饿”现象。

6、操作系统提供给程序员的接口是库函数。

7、在虚存系统中，只要磁盘空间无限大，作业就能拥有任意大的地址空间。

8、所有进程都进入等待状态时，系统陷入死锁。

9、对于一个具有三级索引表的文件，存取一个记录需要访问三次磁盘。

10、并发性是指若干事件在同一时刻发生。

二、填空题(每小题1分，共10分)

1、辅存空闲块的管理方法有(写出三种以上):_(1) 。

2、常用的存储保护技术有: (2)。

3、分页存储管理的置换策略有(写出三种以上):_(3)。

4、有两个程序: A程序按顺序使用CPU 10秒、设备甲5秒、CPU5秒、设备乙10秒、CPU 10秒; B程序按顺序使用设备甲10秒、CPU10秒、设备乙5秒、CPU5秒、设备乙10秒。在顺序环境下，执行上述程序，CPU 的利用率约为 (4)， 若允许它们采用非抢占方式并发执行，若不考虑切换等开销，则CPU的利用率约为 (5) 。

5、在页式和段式存储管理中， (6) 存储管理提供的逻辑地址是连续的。

6、UNIX进程间的通信机制主要有(写出四种或以上): (7)。

7、设备独立性概念的要点是: (8)。

8、设备的I/O方式主要有程序轮询方式、中断方式和(9)。

9、覆盖技术与虚拟存储器都能扩充内存，它们之间的主要区别是: (10)。

三、单选题(每小题1分，共10分)

1、磁盘的I/O控制主要采取( )方式。

A.程序I/O

B.中断

C.DMA

D.SPOOLing

2.位示图可用于( )。

A.文件目录的查找

B.磁盘空间的管理

C.内存空间的共享

D.实现文件的保护和保密

3. UNIX文件系统对磁盘空间的管理采用( )。

A. FAT表法

B.位示图法

C.空闲块链接法

D. 空闲块成组链接法

4.在可变式分区分配方案中，某一作业完成后，系统收回其主存空间，并与相邻空闲区合并, 为此需修改空闲区表，造成空闲区数减1的情况是( )。

A.无上邻空闲区，也无下邻空闲区

B.有上邻空闲区，但无下邻空闲区

C.有下邻空闲区，但无上邻空闲区

D.有上邻空闲区，也有下邻空闲区

5.产生死锁的主要原因是进程运行推进的顺序不合适及( )。

A.系统资源不足和系统中的进程太多

B.资源的独占性和系统中的进程太多

c.进程调度不当和资源的独占性

D.资源分配不当和系统资源不足

6.实时系统的引入是为了使计算机( ) 响应外部事件的请求

A.快速.

B.按对象要求时间

C. 按人反应速度

D.按人动作的速度

7.信号量用于解决互斥问题时( )。

A.其初值必须为正数

B. 其初值必须为正整数

C.其初值可以为0

D.其初值为1

8.通道在输入输出操作完成或出错时，就形成( ) 等候CPU来处理。

A.硬件故障中断

B. 程序中断

C. 外部中断

D. 1/0中断

9.计算机操作系统中，若WAIT. SIGNAL操作的信号量s初值为3，当前值为2，则表示当前有()个等待信号量S的进程。

A.1

B. 2

C.3

D.0

10.银行家算法是一种( ) 算法

A.死锁避免

B. 死锁预防

C.死锁检测

D.死锁解除

四、简答题(每小题5分,共25分)

1.使用文件前为什么要先打开文件?简述打开文件home/user01/myfile的过程? 

2.页式虚拟存储管理采用位示图技术，设主存有16384 块，采用32位的512 个字作为位示图。若块号、字号和位号(从高位到低位)分别从1、0、0开始。试计算:5998块对应的字号和位号:198字的20位对应于哪一块?

3.进程控制块包含哪些类型的信息?进程控制块的信息太多内存放不下应该怎样解决?

4.操作系统中为什么要引入缓冲技术，缓冲池技术有什么优点?

5.分析下面的程序输出多少个A和B?

五、应用题(每小题10分,共20分)

1.有四个进程A、B、C、D。进程A通过一个缓冲区不断地向进程B、C、D发送信息，A每向缓冲区送入一个信息后，必须等进程B、C、D都取走后才可以发送下一个信息，B、C、D对A送入的信息各取一次， 请用信号量机制实现他们之间的正确通信。(10 分)

2.某文件系统要存储的文件大小有以下统计规律:

(1)文件大小≤1KB占40%

(2) 1KB<文件大小≤6KB占30%

(3) 6KB<文件大小≤128KB占20%

(4) 128 KB<文件大小≤768KB占8% .

(5) 768 KB<文件大小≤16MB占2%。 .

假设该文件系统的磁盘块大小为1024字节，盘块的编号最长为4字节，文件描述结构中可存放10个盘块编号。设计目标是使访问文件时具有尽可能小的平均访问磁盘次数，请为该系统设计文件的物理结构,用图文描述其设计思想，并计算其平均访问磁盘次数。(10 分)

第三部分C语言程序设计(75 分)

单项选择题(每题2分，共20分)

1.下列哪一项不是C语言合法标识符( )。

A. kp_ double

B. double_ kp

C. double_ 2000

D.2000_ double

2.已定义inti=l, doublej=3,那么整型变量intk=i/2 +2*j的值是多少? ( )

A.7

B. 5

C.6

D. 3

3.下列程序的输出是什么? ( )

A. i=ll,j=3

B. i=2,j=3

C. i=1l,j= 12

D. i=2,j= 12

4.定义char str[] =“I love China",那么数组str的长度是多少? ( )

A.10

B.11

C.12

D.13

5.已定义整型变量i=10和j=1，且有赋值表达式++j=3+i--*2,经过上述赋值表达式运算之后i和j的值分别是多少? ( )

A. i=9,j=23

B. i= 10,j=23

C. i=9,j= 24

D. i= 10,j= 24

6.如下程序使用关键字static 修饰函数func x,此时func_ x具备如下哪种性质? ( )

static int func_ x(void)

A.返回值无法修改

B.函数内的变量变为静态变量

C.函数无法被其他文件使用

D.函数返回值为静态变量

7.函数func_ c的定义如下，那么调用func _c(l, 2)会得到如下哪种结果? ( )

A.1.2

B. 1,1

C. 2.2

D.2.1

8.已定义数组int al[S]= {，2.3, 4.5}和指针int *p= &a[2],那么表达式--*p ++的值是多少?

()

A.2

B.3

C. 4

D.5

9.已定义枚举cnum WKD {su, mo, tu, th, fr, sa} workday,下列说法正确的是哪一项? ( )

A. su是变量

B. mo 代表一个字符串

C. WKD可以省略

D. sa不能与fr做比较

10.对于函数void func. c(int *ptrl, int ptr2) {ptr1++; ptr2++;}, main 函数调用func _c(pI, p2)后，变量p1和p2的值会出现下列哪种情况?()

A. pl的值发生变化，p2 的值发生变化

B. pl的值发生变化，p2的值不发生变化

C. pl 的值不发生变化，p2 的值发生变化

D. p1 的值不发生变化，p2的值不发生变化

二.判断题(每题1分，共10分，正确的打小，错误的打X)

1.算法的特点之一是有穷性。

2.结构体各个成员变量之间的地址都是相同的。

3.字符串就是字符数组。

4. C语言中，下列程序会输出“Hello JNU"。

5.二进制文件与ASCII文件只是编码方式不同，其占用的存储空间相同。

6.关键字exterm可以将外部变量的作用域扩展到其他文件。

7.指针就是地址。

8. C语言中，下列定义是不合法的。

9.数组名是指针变量。

10.非静态的局部变量存在于内存中的栈区域。

三，简答题(共3小题，每题8分,共24分)

1.给出循环for(表达式I, 表达式2,表达式3) {循环体}的执行过程。(8分)

2.分别指出int *p0, int (*p)0, void *p和int *p[6]的意义。(8分)

3.什么是动态分配内存? (2 分)给出C语言提供的管理内存的函数名称及功能(6分)

四.编写程序(共2小题，第1小题8分，第2小题13分，共21分)

1.设计C语言程序实现牌型识别，具体规则如下，用户输入5张牌，根据这5张牌的点数和花色识别出不同的牌型，规定如果5张牌的花色相同那么牌型为Flush, 如果5张牌的大小刚好依次递进称为Straight。其中，牌的点数从小到大为2, ...j.,a，,花色为c,d,h,so 例如: 

a)给出程序设计的思路 (2分)

b)写出关键的程序代码 (6 分)

2.队列是一种常用的数据管理工具，其特点是先进先出，对外提供队列是否为空和满、数据入队、数据出队、清空队列的接口函数，设计C语言程序通过数组来模拟队列的功能。

a)列出要实现 上述功能的各个函数的声明和功能注释(5分)

b)写 出函数定义的关键程序代码(8分)