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

南京师范大学《计算机科学与技术》期末试卷（含答案）考试时间：______分钟总分：______分姓名：______一、解释下列术语：计算机总线、虚拟内存、TCP协议、数据库范式、算法复杂度。二、简述二叉搜索树的主要性质，并说明在二叉搜索树中插入一个新节点和删除一个节点（非叶子节点）的主要步骤。三、设有一个关系数据库表“学生”（学号，姓名，专业，年级，成绩），请写出SQL查询语句：1.查询所有计算机科学专业的学生信息。2.查询平均成绩大于80分的学生的学号和姓名。3.查询每个专业的学生人数。4.查询成绩不及格（假设不及格为60分以下）的学生姓名和成绩，并按成绩降序排列。四、描述操作系统中的进程与线程的区别，并说明使用多线程技术的主要优势。五、解释“网络分层”的概念，并简述OSI七层网络模型和TCP/IP四层（或五层）网络模型的层次划分及其主要功能。六、给定以下递归函数定义的斐波那契数列F：F(0)=0F(1)=1F(n)=F(n-1)+F(n-2)(n>=2)1.用伪代码或C/C++/Java代码实现计算F(n)的递归算法。2.分析上述递归算法的时间复杂度。3.提出一种改进算法（如使用记忆化递归或迭代方法）来计算F(n)，并说明其优点。七、假设我们要设计一个简单的文件系统，用于管理磁盘上的文件。请简述文件系统需要实现的基本功能，并说明在磁盘上如何表示一个文件（例如，使用目录结构或文件分配表FAT的方法）。八、编写一个函数（用C/C++/Java伪代码表示），实现将一个给定的非负十进制整数N转换为二进制字符串。要求不能使用库函数直接转换。九、什么是图？请解释图的两种基本表示方法（邻接矩阵和邻接表）的优缺点，并说明在什么情况下选择哪种表示方法可能更合适。十、分析以下代码片段的执行结果，并解释其中的关键概念（如：堆栈、参数传递、返回值、作用域）。```c#include<stdio.h>voidfunctionA(intx){inty=10;printf("InfunctionA,x=%d,y=%d\n",x,y);}intfunctionB(inta,intb){inttemp=a;a=b;b=temp;returna+b;}intmain(){intx=5,y=8;printf("BeforefunctionA,x=%d,y=%d\n",x,y);functionA(x);printf("AfterfunctionA,x=%d,y=%d\n",x,y);intresult=functionB(x,y);printf("AfterfunctionB,x=%d,y=%d,result=%d\n",x,y,result);return0;}```试卷答案一、1.计算机总线：计算机系统中用于连接各个功能部件（如CPU、内存、输入输出设备）并传输信息的公共通信干线，分为数据总线、地址总线和控制总线。2.虚拟内存：一种内存管理技术，它将物理内存和磁盘空间结合起来使用，使计算机能够执行比实际物理内存更大的程序。通过使用磁盘空间作为“内存”，扩展了可用地址空间，提高了内存利用率。3.TCP协议：传输控制协议（TransmissionControlProtocol）是一种面向连接的、可靠的、基于字节流的传输层通信协议。它提供数据分段、按序传输、错误检测、重传和流量控制等功能，确保数据在网络中的可靠交付。4.数据库范式：数据库设计中的规范化理论，旨在减少数据冗余、消除数据依赖异常，确保数据库的合理性和一致性。常见的范式有第一范式（1NF）、第二范式（2NF）、第三范式（3NF）等。5.算法复杂度：衡量算法效率的指标，通常关注算法执行时间（时间复杂度）和所需存储空间（空间复杂度）。常用表示方法有大O记法（BigOnotation），描述算法运行时间或空间随输入规模增长的变化趋势。二、主要性质：1.对于任意节点，其左子树中所有节点的值均小于该节点的值。2.对于任意节点，其右子树中所有节点的值均大于该节点的值。3.左右子树也分别为二叉搜索树。4.节点具有唯一值，不存在重复值。插入步骤：1.如果二叉搜索树为空，则新节点成为根节点。2.否则，将新节点与根节点比较：*如果新节点值小于根节点值，则向左子树继续比较插入。*如果新节点值大于根节点值，则向右子树继续比较插入。3.重复比较，直到找到空位置，将新节点插入。删除步骤（非叶子节点）：1.情况一：被删除节点只有一个孩子。找到被删除节点的一个孩子节点，用该孩子节点替换被删除节点的位置。2.情况二：被删除节点有两个孩子。通常采用“后继替代法”或“前驱替代法”。*后继替代法：找到被删除节点右子树中的最小值节点（后继节点），用该后继节点的值替换被删除节点的值，然后删除原后继节点（此时后继节点一定是叶子节点或只有一个孩子，转化为情况一处理）。*前驱替代法：找到被删除节点左子树中的最大值节点（前驱节点），用该前驱节点的值替换被删除节点的值，然后删除原前驱节点（同样转化为情况一处理）。三、1.`SELECT*FROM学生WHERE专业='计算机科学';`2.`SELECT学号,姓名FROM学生WHERE成绩>80.0GROUPBY学号,姓名;`3.`SELECT专业,COUNT(*)AS学生人数FROM学生GROUPBY专业;`4.`SELECT姓名,成绩FROM学生WHERE成绩<60.0ORDERBY成绩DESC;`四、区别：*进程：操作系统资源分配的基本单位，是运行中的程序实例。每个进程拥有独立的内存空间（地址空间），互不干扰。进程之间通过操作系统提供的机制（如管道、信号量）进行通信。*线程：CPU调度的基本单位，是进程内的一个执行流。同一进程内的多个线程共享进程的地址空间、资源（如打开的文件、全局变量）。线程之间可以通过共享内存进行直接通信，切换开销较小。优势：1.提高程序的响应速度：在单个进程内，一个线程阻塞（如等待I/O）不会影响其他线程的执行，可以使程序保持响应。2.提高程序并发性：多线程可以在多核处理器上实现真正的并行执行，提高程序的执行效率。3.资源共享与通信方便：线程共享进程资源，避免了进程间通信的开销，数据共享更直接。4.设计简化：对于一些并发任务，使用多线程比使用多进程设计更简单。五、网络分层概念：将复杂的网络通信功能划分为若干个功能明确、相对独立的层次，每一层只负责特定的任务，层与层之间通过接口（Interface）和协议（Protocol）进行交互。这种分层的结构简化了网络设计、实现、维护和故障排除。OSI七层模型：1.物理层：提供物理连接，传输比特流（0和1）。2.数据链路层：在相邻节点间的链路上提供可靠的数据传输（帧），处理错误检测/纠正。3.网络层：负责路由选择，实现逻辑寻址（IP地址），将数据包从源主机传输到目的主机。4.传输层：提供端到端的可靠（TCP）或不可靠（UDP）数据传输服务，处理连接管理、数据分段、流控制和差错控制。5.会话层：建立和管理应用程序之间的会话（连接）。6.表示层：处理数据的表示形式，如加密、解密、压缩、格式转换。7.应用层：为用户应用程序提供网络服务接口，如HTTP,FTP,SMTP,DNS。TCP/IP四层模型（或五层）：1.网络接口层（或链路层）：对应OSI的物理层和数据链路层，处理硬件地址（MAC地址）和数据链路协议。2.网络层（或互联网层）：对应OSI的网络层，处理IP地址和路由，核心是IP协议。3.传输层：对应OSI的传输层，提供TCP和UDP协议。4.应用层：对应OSI的应用层、表示层和会话层，包含所有高层协议（HTTP,FTP,DNS等）。主要功能：各层主要负责封装/解封装数据、处理特定协议、提供特定服务（如路由、传输、会话管理等）。六、1.递归算法（伪代码）：```FunctionFibonacci(n)Ifn==0ThenReturn0ElseIfn==1ThenReturn1ElseReturnFibonacci(n-1)+Fibonacci(n-2)EndIfEndFunction```C/C++/Java代码（类似）：```cintFibonacci(intn){if(n==0)return0;if(n==1)return1;returnFibonacci(n-1)+Fibonacci(n-2);}```2.时间复杂度分析：该递归算法的时间复杂度是指数级的，为O(2^n)。因为每调用一次`Fibonacci(n)`，平均会引发两次递归调用`Fibonacci(n-1)`和`Fibonacci(n-2)`，导致调用树的规模呈指数增长。3.改进算法（迭代方法）：```cintFibonacci_iterative(intn){if(n==0)return0;if(n==1)return1;intprev=0,curr=1;for(inti=2;i<=n;i++){inttemp=curr;curr=prev+curr;prev=temp;}returncurr;}```优点：*时间复杂度低：迭代方法的时间复杂度为O(n)，随着n的增大，效率远高于递归方法。*空间复杂度低：迭代方法只需要常数级的额外空间（O(1)），而递归方法需要O(n)的栈空间（最坏情况）。七、基本功能：1.文件创建与删除：允许用户创建新文件和删除不再需要的文件。2.文件读写：提供读取文件内容和写入文件内容（覆盖或追加）的功能。3.文件目录管理：创建、删除、查询目录（文件夹），管理文件在目录中的组织。4.文件命名与路径：为文件分配唯一名称，支持通过路径名定位文件。5.文件属性管理：设置或查询文件的属性（如只读、隐藏、归档等）。6.文件共享与保护：控制不同用户对文件的访问权限。7.文件存储分配：在磁盘上为文件分配存储空间，管理空闲空间。磁盘表示方法：1.目录结构（树状结构）：文件系统以树形结构组织文件和目录。每个磁盘有一个根目录（如Linux的"/"，Windows的"根盘符:\")。文件和子目录存储在目录项中，目录项包含文件名、属性、指向数据块的指针等。优点是结构清晰，便于组织管理；缺点是路径长度可能过长，查找速度可能受限于目录深度。2.文件分配表（FAT-FileAllocationTable）：为磁盘上的每个文件分配一个表项（ENT），表项记录文件名、属性、起始簇号以及指向后续数据簇的指针链。优点是相对简单，支持文件碎片整理（通过指针链）；缺点是表项占用空间，FAT表损坏可能导致数据丢失（如长文件支持不佳的早期FAT版本）。3.索引节点（Inode-IndexNode，类Unix系统）：每个文件对应一个索引节点，Inode是一个数据结构，不存储文件名和内容，而是存储文件属性和指向数据块的指针（直接指针、一次间接指针、二次间接指针等）。文件名存储在目录项中。优点是文件与内容分离，便于实现硬链接；缺点是查找文件时需要先找到Inode，再通过Inode查找数据块，可能稍慢。八、```cchar*DecToBin(intN){if(N==0)return"0";//处理0的特殊情况intsize=32;//假设使用32位整数表示char*binary=(char*)malloc(size+1);//分配存储二进制字符串的内存(+1用于'\0')if(!binary)returnNULL;//内存分配失败intindex=0;while(N>0){intbit=N%2;//取当前最低位的二进制值binary[index++]='0'+bit;//转换为字符'0'或'1'并存储N/=2;//整除2，准备取下一个位}binary[index]='\0';//添加字符串结束符//翻转字符串，因为生成的二进制数是低位在前char*result=(char*)malloc(index+1);if(!result){free(binary);returnNULL;}for(inti=0;i<index;i++){result[i]=binary[index-1-i];}result[index]='\0';free(binary);//释放临时空间returnresult;}```解析思路：1.基础原理：十进制转二进制采用“除2取余法”。将十进制数不断除以2，记录每次的余数，直到商为0。将所有余数按倒序排列，即得到对应的二进制表示。2.实现步骤：*初始化：检查N是否为0，是则直接返回"0"。准备一个足够长的字符数组来存储二进制结果（考虑整数最大值）。*循环除余：使用循环，每次用N除以2，将余数（0或1）转换为字符'0'或'1'，存储在数组中。同时更新N为当前的商，继续循环直到N为0。*字符串结束：循环结束后，在数组末尾添加字符串结束符'\0'。*结果翻转：由于上述方法是从最低位开始生成二进制字符串，而通常我们需要的顺序是最高位到最低位。因此，需要创建一个新的结果字符串，并将原字符串中的字符按逆序复制过去。*内存管理：注意动态内存的申请和释放，避免内存泄漏。*错误处理：检查动态内存分配是否成功。九、图定义：图是一种由节点（或称为顶点Vertex）和边（或称为弧Arc/Edge）组成的集合。图用于表示对象之间的多种关系，是计算机科学中一种重要的非线性数据结构。表示方法：1.邻接矩阵（AdjacencyMatrix）：*结构：使用一个二维数组`matrix[N][N]`（N为节点数量）表示。`matrix[i][j]`的值表示节点i和节点j之间是否有边。对于无向图，通常`matrix[i][j]`等于`matrix[j][i]`。对于有向图，`matrix[i][j]`表示从i到j是否有边。*优点：*实现简单。*非常方便检查节点i和节点j之间是否有边（只需查看`matrix[i][j]`）。*空间复杂度与节点数量平方成正比（O(N^2)），对于稠密图（边数接近N^2）效率较高。*缺点：*空间浪费严重，对于稀疏图（边数远小于N^2）非常低效（大量空间存储为0）。*判断所有出边或入边需要遍历一整行或一整列。2.邻接表（AdjacencyList）：*结构：使用一个包含N个元素的数组（或链表数组），数组的第i个元素存储一个链表（或集合），该链表（或集合）包含所有与节点i相邻的节点。*优点：*空间效率高，只存储实际存在的边，对于稀疏图非常节省空间（空间复杂度约为O(N+E)，N为节点数，E为边数）。*添加边和删除边（对于无向图）的操作相对简单快捷。*遍历节点i的所有邻接节点非常快（只需遍历与i相连的链表）。*缺点：*检查节点i和节点j之间是否有边需要遍历节点i对应的链表，时间复杂度可能较高（最坏为O(N)）。*实现相对邻接矩阵稍复杂。选择依据：*稠密图：通常选择邻接矩阵，因为边数多，节省检查边是否存在的时间（O(1)vsO(N)）。*稀疏图：通常选择邻接表，因为节点数远大于边数，节省空间（O(N^2)vsO(N+E)）。*特定算法需求：某些图算法（如Floyd-Warshall算法）天然适合邻接矩阵；而BFS、DFS等遍历算法，邻接表通常更高效。十、执行结果分析：```BeforefunctionA,x=5,y=8InfunctionA,x=5,y=10//functi