厦大软件技术基础期末试卷(A).doc

软件技术基础期末试卷(A)一、 判断题。请判断下面每一个结论是否正确，对不正确的结论，请分析原因，并修改为正确结论。(45分)(1) 同线性表的顺序存储结构相比，线性表的链式存储结构，不要求逻辑上相邻的数据元素在物理位置上也相邻，而且可以在程序运行期间动态生成线性表，从而提高了存储空间的利用效率，但失去了顺序表随机存取的优点。(2) 栈和队列是操作受限的特殊线性表。栈所采用的是后进先出(LIFO)的访问方法，而队列采用的是先进先出的访问方法(FIFO)。(3) 哈希表(又称散列表)查找是通过一个哈希函数，由数据元素的关键字直接得到哈希地址来查找元素，选取一个计算简单且均匀映射的哈希函数，可以完全避免冲突，提高查询效率。(4) 快速排序的基本操作是选取基准元对序列进行划分，对同一待排序列，如果选取的基准元不同，排序速度可能不同。在快速排序中，如果为每次划分所选取的基准元恰好是序列中所有元素的中位数，这时排序所进行的比较次数最少，排序速度最快。(5) 2-路归并排序是一种稳定的排序算法，其运行效率与快速排序是同一数量级，但实现时需要一个与待排序列一样大小的辅助数组，从而消耗较多的存储空间。(6) 操作系统作为资源管理器，只负责对CPU、内存和I/O设备等硬件资源的管理。(7) 对于偶尔需要通信的线程，即使它们平时相互独立工作，也说这些线程是同步执行的。(8) 假定共享同一个变量的两个线程需要在线程执行期间的某个时间，对哪个共享变量进行更新。再假定这两个线程没有设置在同时更新一个共享变量时互斥，那么在两个线程执行时，系统肯定会失败。(9) 进程不会因为竞争处理器而死锁，FIFO进程调度策略不会造成进程无限延期。(10) 在虚拟内存管理系统中，用户的虚拟地址空间远大于真实的地址空间，系统必须提供一种方式把程序和数据保存在更大的辅助存储器中，因此系统可以直接从辅助存储器运行一个进程，无须将进程的代码和数据装入主存中。(11) 在分页内存管理技术中，主内存被划分为与页面大小一样的块，而每一个进程平均有半个内存块被浪费，因此页面尺寸越小越好。(12) 同分页技术相比，分段实现了程序与数据的分离，更易于实现代码和数据的有效共享，当不同的进程想要共享同一个代码段时，只需要在各进程的段表中都登记一项，使其基地址都指向该代码段在内存中的起始地址，而各共享进程并不需要以同样的段号定义该段。(13) 应用缓冲技术可以缓解CPU和I/O设备间速度不匹配的矛盾，提高它们之间的并行性，同时，又可减少对CPU的中断次数，放宽CPU对中断响应时间的要求。(14) 文件系统为每个文件都设置一个文件控制块，文件目录就是文件控制块的集合，系统使用文件名查询文件目录，就可以得到文件在外存存放的物理位置，从而实现了文件的“按名存取”。(15) 数据库管理系统(DBMS)实现了数据独立性，将数据库和访问数据库的应用分离，对数据库定义的任何修改就不会影响到相应的应用，相关的应用程序不必随数据库定义的修改而一同修改。二、 对下图中的无向图进行分析，解答下列问题。(15分)(1) 给出此图的邻接矩阵；(2) 给出由V1开始的深度优先遍历序列;(3) 给出由V1开始的广度优先遍历序列。三、 下图中用户空间有两个进程，其中进程A的优先级高于进程B，仔细分析该图后，解答下列问题(20分)。(1) 请给出核心空间中A、B、C、D、E所代表的操作系统程序的名称。(2) 编译程序将如何处理进程A中的语句“rw=write(fd,buf,count;)”，该语句的执行将导致进程A和进程B的状态发生什么样的变化？(3) 进程B在执行过程中发生了磁盘I/O中断，这将导致进程A和进程B的状态发生什么样的变化？(4) 请给出图中导致程序D运行的两种时机。(5) 比较操作系统程序和E的联系与差别。四、请给出二叉树链式存储的节点