1、数据结构是一门研究计算机中（　 　）对象及其关系的学科。

A　数值运算　　 B　非数值运算　　 C　集合　　 D　非集合

2、存储器的管理不能完成下述（　 　）功能。

A．虚拟存储　 B．地址变换与重定位 C．内存分配与回收　D．进程调度

3、在计算机系统中， 控制和管理各种资源， 有效地组织多道程序运行的系统软件称作(　 )。

A 文件系统　　B 操作系统　　 C 网络管理系统　　D 数据库管理系统

4、进程调度根据一定的调度算法， 从(　　)队列中挑选出合适的进程。

A 阻塞　　　B 就绪　　 C　 运行　　 D等待

5、虚拟存储管理策略可以(　 )。

A扩大物理内存容量　 B扩大物理外存容量

C扩大逻辑内存容量　 D扩大逻辑外存容量

6、算法分析的目的是____。

A找出数据结构的合理性　　　　B研究算法中输入和输出的关系

C分析算法的效率以求改进　　　D分析算法的易懂性和文档性

7、在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（　　）。A　P〈—next(S)；S〈—next(P)　　B　next(S)〈—next(P)；next(P)〈—S

C　next(S)〈—next(P)；S〈—P　 D　next(P)〈—S；　next(S)〈—P

8、用链表表示线性表的优点是 (　　　 )。

A. 便于随机存取　　　　　　　　　　　　　 B. 花费的存储空间比顺序表少

C. 便于插入与删除　　　　　　　　　　　　D. 数据元素的物理顺序与逻辑顺序相同

9、线性表是（　　）。

A一个有限系列，可以为空　　　　　　B一个有限系列，不能为空

C一个无限系列，可以为空　　　　　　D一个无限系列，不能为空

10、线性表采用链式存储时，其地址（　 ）。

A　必须是连续的　　　　　　　 B　部分地址是连续的

C　一定是不连续的　　　　　　D　连续与否均可以

11、在栈当中，若输入序列为（A,B,C,D）不可能的输出有（　）。

　　 A　(A,B,C,D)　　B　(D,C,B,A)　　 C　(A,C,D,B)　　　D　(C,A,B,D)

12、栈和队列的共同特点是____。

A都是先进后出　　　　　　　　　 B 都是先进先出

C只允许在端点处插入和删除　　　 D没有共同点

13、设有一个8×6矩阵A，以行优先顺序存储，a11为第一个元素，其存储地址为1，每个元素占一个地址空间，则 a56地址为（　）。

A　23　　　　　　 B　30　　　　　 C　31　　　　　　　D　45

14、若已知一棵二叉树先序序列为ABCDEFG，中序序列为CBDAEGF，则其后序序列为(　)。

　　　 A　CDBGFEA　　 B　CDBFGEA　　C　CDBAGFE　　D　BCDAGFE

15、中序遍历一棵二叉排序树所得到的结点序列是键值的（　C　 ）序列。

A递增或递减　　 B递减　　

　　 C递增　　　　　 D无序

16、采用对分查找方法进行查找，数据文件应为（　），且限于（　）。

A　有序表　顺序存储结构　　　　　　　B　有序表　链式存储结构

C　随机表　顺序存储结构　　　　　　　　D　随机表　链式存储结构

17、操作系统具有进程管理、存储管理、文件管理和设备管理的功能，在以下有关的描述中，哪一个是不正确的（　　）。

A　进程管理主要是对程序进行管理　　B　存储管理主要是管理内存资源

C　文件管理可以有效地支持对文件的操作，解决文件共享、保密和保护问题D　设备管理是指计算机系统中除CPU和内存外所有输入、输出设备的管理

18、用某种排序方法对关键字序列（25，84，21，47，15，27）进行排序时，序列的变化情况如下：

　　15，84，21，47，25，27，

15，21，84，47，25，27，

15，21，25，47，84，27，则所采用的排序方法是（　 ）。

A．选择排序　　 B．交换排序　　 C．冒泡排序　　D．快速排序

19、设哈希函数为H(k)=k mod p，散列地址区间为[1…m],k为关键字。为了减少发生冲突，一般取p为（ ）。

A．小于m的最大奇数　　　　　　 B．小于m的最大偶数

C．小于m的最大质数　　　　　　 D．小于m的最大合数

20、在分段管理中,下列说法正确的是(　 ).

A 以段为单位分配,每段是一个连续存储区　 B段与段之间必定不连续

C 段与段之间必定连续　　　　　　　　　 D每段是等长的

二、填空题（每空1分，共10分）

1、在具有n个单元的循环队列中，队满时共有______　_个元素。

2、具有n个叶子的二叉树，每个叶子的权值为Wi(1≤i≤n)其中带权路径最小的二叉树被称为______　_ 。　　　　

3、具有个结点的完全二叉树的深度为______　_ 。

4、若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个________矩阵。

5、为度量一个搜索算法的性能，需要在________复杂度和空间方面进行权衡。

6、CPU输出数据的速度远远高于打印机的打印速度，为了解决这一矛盾，可采用____　　技术。

7、为了保证CPU执行程序指令时能正确访问存储单元，需要将用户程序中的逻辑地址转换为运行时可由机器直接访问的物理地址，这一过程称为　　　 。

8、支持程序浮动的地址转换机制是　　　 。

9、在计算机系统中,控制和管理各种资源,有效地组织多道程序运行的系统软件称作　　　　　。

10、组成数据的基本单位是　　　　　。

三、简答题（共20分）

1、(6分)操作系统中存储器管理的主要功能是什么? 什么是虚拟存储器?

2. (4分)作业调度和进程调度之间有什么不同?

3、(4分)程序与进程的关系是怎样

的?

4、(6分)操作系统中，产生死锁的原因和必要条件分别是什么？

四、计算题（共30分）

1、(9分)某采用页式存储管理的系统，接收了一个共7页面的作业。该作业执行时依次访问的页面为:1、2、3、4、2、1、5、6、2、1、2、3、7。若系统分配给改作业的页架数为4，请用先进先出(FIFO)调度算法，计算作业执行过程中会产生多少次缺页中断?写出依次产生缺页中断后应淘汰的页以及最后留驻主存4个页面的顺序(所有内存开始时都是空的，要求写出计算过程)。

2、(9分)对给定的7个顶点的有向图的邻接矩阵如下：

1）画出该有向图；

（2）画出邻接表；

（3）若将图看成AOE网，列出其关键活动及相应的有向边，关键路径的长度是多少？

3、(12分)试按表( 10,8,9,12,20,5,6,15,19,25 )中元素的排列次序, 将所有元素插入一棵初始为空的二叉排序树中, 使之仍是一棵二叉排序树，

(1)试画出插入完成之后的二叉排序树；

(2)若查找元素19,它将依次与二叉排序树中哪些元素比较大小?

(3)对该树进行中序遍历,试写出中序遍历序列。

(4)假设每个元素的查找概率相等,试计算该树的平均查找长度 ASL。下载本文