南京师范大学《计算机科学与技术》期末试卷及答案

南京师范大学《计算机科学与技术》期末试卷及答案考试时间：______分钟总分：______分姓名：______一、单项选择题（每题2分，共20分。请将正确选项的字母填在题后的括号内）1.下列关于算法特性的描述，错误的是（）。A.有穷性B.确定性C.可行性D.最优性（注：算法不一定是最优的，只是正确的）2.在顺序存储的线性表中，插入和删除元素的主要困难是（）。A.元素移动量大B.可能造成数据丢失C.需要额外的存储空间D.算法复杂度高3.下列数据结构中，适合用来表示稀疏矩阵的是（）。A.顺序表B.链栈C.二维数组D.三元组表4.若线性表的顺序存储地址从1开始，元素E5插入到第3个位置上，插入后E5的地址是（）。（假设每个元素占用等长存储单元）A.7B.8C.9D.105.在下列排序算法中，平均时间复杂度最小的是（）。A.冒泡排序B.选择排序C.插入排序D.归并排序6.下列关于二叉树的叙述中，正确的是（）。A.二叉树的任何一棵子树都有左右两个子树B.二叉树的度必为2C.非空二叉树有n个结点，则其深度为log2(n)D.完全二叉树是度为2的有序树7.操作系统通过（）管理内存资源。A.设备驱动程序B.中断处理程序C.内存管理模块D.进程调度程序8.在多道程序设计中，产生死锁的一个必要条件是（）。A.资源互斥使用B.资源有限性C.请求与保持D.循环等待9.假设某计算机的存储器字长为16位，则能表示的无符号整数范围是（）。A.0~65535B.-32768~32767C.-32769~32767D.0~3276710.下列协议中，不属于应用层协议的是（）。A.HTTPB.FTPC.TCPD.SMTP二、填空题（每空2分，共20分。请将答案填写在横线上）1.计算机算法是指对问题求解步骤的______描述。2.在栈的操作中，插入元素的操作称为______，删除元素的操作称为______。3.循环队列的判满条件（基于数组实现，假设数组大小为n，头指针为front，尾指针为rear）是______。4.快速排序算法的平均时间复杂度是______。5.磁盘调度算法中的______算法总是将磁头移动到当前磁道的最远端。6.操作系统的基本功能包括进程管理、______管理、文件管理和设备管理。7.在TCP/IP协议簇中，IP协议工作在______层。8.一个完整的计算机系统由硬件系统和______系统组成。9.十进制数25转换为二进制数是______。10.万维网（WWW）应用层使用的协议主要是______。三、判断题（每题2分，共10分。请将判断结果“正确”或“错误”填在题后的括号内）1.线性表可以是空表。（______）2.在二叉搜索树中，任意结点的左子树上所有的结点值均小于该结点的值。（______）3.分时系统是共享系统，但不是多道程序系统。（______）4.程序计数器（PC）存放的是下一条要执行的指令的地址。（______）5.并发是指两个或多个事件在同一时间发生，并行是指两个或多个事件在同一时间间隔内发生。（______）四、简答题（每题5分，共20分）1.简述栈和队列的主要区别。2.解释什么是“虚拟内存”，并说明其实现的主要技术。3.什么是总线？简述总线的主要性能指标。4.说明TCP协议与UDP协议的主要区别。五、综合应用题（每题10分，共30分）1.已知一个线性表L=(12,23,36,45,58)。现在要求：a.依次删除L中的第2个和第4个元素，并写出删除后的线性表。b.将元素67插入到删除后的线性表的第3个位置，并写出插入后的线性表。（假设使用顺序表存储，无需考虑溢出问题）2.设计算法，查找有序数组A[1..n]中元素x的位置。如果找到，返回其索引；如果未找到，返回0。要求使用二分查找算法，并用伪代码描述。（无需考虑case语句）3.假设有一个磁盘块，其柱面号为50，磁头初始位于柱面30，当前请求服务的磁盘访问请求序列（按访问的柱面号排列）为：55,58,50,40,30。请使用FCFS（先来先服务）磁盘调度算法计算磁头移动的总距离。---试卷答案一、单项选择题1.D解析：算法不一定要求是最优的，只需要是正确的、可行的、有穷的、确定性的即可。2.A解析：在顺序存储结构中，插入或删除元素通常需要移动大量元素来保持数据结构的连续性，这是其主要困难。3.D解析：三元组表（或称为稀疏矩阵压缩存储）可以有效存储稀疏矩阵，只存储非零元素及其行、列下标，节省空间。4.C解析：插入位置是第3个，则其后元素依次后移，E5需要移动到原第3、4、5个元素后面，其新位置是原位置+3。5.D解析：归并排序的平均和最坏时间复杂度均为O(nlogn)，而冒泡、选择、插入排序的平均时间复杂度为O(n^2)。6.D解析：A错误，子树可以只有左或只有右；B错误，二叉树可以是度为1或0；C错误，深度可能大于log2(n)；D正确，完全二叉树是满足特定条件的满二叉树。7.C解析：内存管理模块是操作系统负责管理内存分配和回收的核心部分。8.D解析：死锁的四个必要条件是：互斥、占有并等待、非抢占、循环等待。其中循环等待是其中一个必要条件。9.A解析：16位无符号整数可以表示0到2^16-1，即0到65535。10.C解析：TCP是传输层协议，而HTTP、FTP、SMTP都是应用层协议。二、填空题1.清晰2.入栈，出栈3.(rear+1)%n==front4.O(nlogn)5.到达顶6.文件7.网络接口（或链路）8.软件9.1100110.HTTP三、判断题1.正确2.正确3.错误解析：分时系统是共享系统，也是多道程序系统，旨在让多个用户同时使用计算机。4.正确5.错误解析：并发是指多个事件在同一时间间隔内发生，并行是指多个事件在同一时刻发生。四、简答题1.栈是后进先出（LIFO）的数据结构，只允许在一端进行插入和删除操作；队列是先进先出（FIFO）的数据结构，允许在一端插入（队尾），另一端删除（队头）。2.虚拟内存是一种让操作系统以为计算机拥有比实际物理内存更大的内存空间的技术。主要实现技术包括分段、分页，以及页面置换算法（如LRU）和快表（TLB）。3.总线是计算机各功能部件之间传输信息的公共通路。主要性能指标包括总线宽度（决定数据传输速率）、总线频率（决定传输时钟速率）、总线传输速率等。4.TCP是面向连接的、可靠的、基于字节流的传输协议，提供数据分段、重传、流量控制、拥塞控制等功能；UDP是无连接的、不可靠的、基于数据报的传输协议，速度快但不对数据包的丢失进行保证。五、综合应用题1.a.L=(12,36,45,58)解析：删除第2个元素23，删除第4个元素45，剩余元素为12,36,58，45被删除。b.L=(12,36,67,58)解析：在元素36之后插入67，得到12,36,67,58。2.伪代码：functionbinary_search(A,n,x)low=1high=nwhilelow<=highmid=floor((low+high)/2)ifA[mid]==xreturnmidelseifA[mid]<xlow=mid+1elsehigh=mid-1return0解析：二分查找在有序数组中查找元素，通过比较中间元素与目标值，决定在左半部分还是右半部分