软件技术基础模拟题及参考答案

软件技术基础模拟题及参考答案一、单项选择题（每题2分，共40分）1.在数据结构中，从逻辑上可以将数据结构分为（）。A.动态结构和静态结构B.线性结构和非线性结构C.顺序结构和链式结构D.紧凑结构和非紧凑结构2.下列算法的时间复杂度为（）。```cintcount=0;for(inti=0;i<n;i++){for(intj=i;j<n;j++){count++;}}```A.OB.OC.OD.O3.设栈的输入序列为1,2,3,4，则以下哪个序列不可能是栈的输出序列？（）A.1,2,3,4B.2,1,4,3C.3,1,2,4D.4,3,2,14.在一个单链表中，若要删除指针p所指结点的后继结点（假设后继结点存在），下列代码正确的是（）。A.`q=p->next;p->next=q->next;free(q);`B.`q=p->next;p=q->next;free(q);`C.`q=p;p=p->next;free(q);`D.`q=p->next->next;p->next=q;free(q);`5.深度为k（根结点深度为1）的完全二叉树至少有（）个结点。A.B.−C.−D.6.对于一个具有n个顶点的无向图，若采用邻接矩阵存储，则该矩阵的大小为（）。A.nB.C.nD.n7.在下列排序算法中，最坏情况下时间复杂度为O(A.快速排序B.归并排序C.堆排序D.基数排序8.任何一个无向连通图的最小生成树（）。A.只有一棵B.至少有一棵C.可能有多棵，但其所有边的权值之和必定相等D.边数可能大于顶点数减一9.在操作系统中，并发性是指若干事件在（）发生。A.同一时刻B.同一时间间隔内C.不同时刻D.不同时间间隔内10.下列关于进程与线程的描述中，正确的是（）。A.线程是资源分配的基本单位，进程是调度的基本单位B.线程拥有独立的地址空间，进程不拥有C.一个进程可以包含多个线程，这些线程共享进程的资源D.线程的切换开销比进程大11.若系统中有5个同类资源，多个进程竞争该资源。若要保证系统不会发生死锁，则参与竞争的进程数和每个进程的最大资源需求量应满足（）。假设进程数为P，每个进程最多需要R个资源。A.PB.PC.PD.P12.在分页存储管理系统中，逻辑地址到物理地址的转换是由（）完成的。A.编译器B.链接器C.操作系统D.硬件地址转换机构13.下列页面置换算法中，可能会产生Belady异常现象的是（）。A.最佳置换算法（OPT）B.先进先出置换算法（FIFO）C.最近最久未使用置换算法（LRU）D.时钟置换算法（CLOCK）14.在软件工程中，瀑布模型本质上是一种（）模型。A.线性B.迭代C.并行D.螺旋15.软件测试中的“白盒测试”主要关注于（）。A.软件的功能是否正确B.软件的内部逻辑结构和处理过程C.软件的输入输出对应关系D.软件的用户体验16.在结构化分析方法中，用于描述系统逻辑功能的工具是（）。A.数据流图（DFD）B.实体关系图（ER图）C.判定表D.程序流程图17.关系型数据库中，实现实体完整性约束的手段是（）。A.主键B.外键C.检查约束D.非空约束18.在SQL语言中，删除一个视图的命令是（）。A.`DELETEVIEW`B.`DROPVIEW`C.`REMOVEVIEW`D.`ERASEVIEW`19.在计算机网络中，物理层的主要功能是（）。A.路由选择B.差错控制C.在物理媒体上透明地传输原始比特流D.建立和管理会话20.如果IP地址为，子网掩码为，那么该子网的网络地址和广播地址分别是（）。A.和55B.和55C.和54D.和54二、填空题（每空2分，共30分）1.数据的物理结构在计算机存储器中的实现，通常有两种基本方法：__________存储和__________存储。2.在一个长度为n的顺序表中插入一个元素，平均需要移动__________个元素；删除一个元素，平均需要移动__________个元素。3.哈夫曼树是一种带权路径长度最短的二叉树，若某哈夫曼树有n个叶子结点，则该树共有__________个结点。4.在无向图的邻接矩阵中，若顶点i和顶点j之间有边相连，则矩阵中第i行第j列的元素和第j行第i列的元素的值均为__________。5.任何一个线程都由三个基本状态组成，分别是就绪状态、执行状态和__________状态。6.进程的同步是指多个相互合作的进程，在一些关键点上可能需要__________；而进程的互斥是指多个进程在共享临界资源时，必须__________。7.虚拟存储器的实现原理是基于程序的局部性原理，局部性包括时间局部性和__________局部性。8.软件工程的三要素是方法、工具和__________。9.衡量软件独立性的两个定性度量标准是内聚性和__________。10.在数据库设计中，将E-R图转换为关系模型属于__________设计阶段的主要任务。11.事务具有四个基本特性，分别是原子性、一致性、隔离性和__________。12.在网络协议的TCP/IP模型中，处于应用层和网际层之间的层次是__________层。13.在计算机网络通信中，多路复用技术常用于提高物理信道的利用率，常见的方法有频分多路复用、时分多路复用、波分多路复用和__________多路复用。三、简答题（每题10分，共40分）1.请简述栈和队列在逻辑结构上的主要区别，并分别列举一个在实际软件系统中的典型应用场景。2.什么是死锁？产生死锁的四个必要条件是什么？破坏“循环等待资源”条件通常采用什么方法？3.什么是软件的白盒测试？请列举至少三种白盒测试的逻辑覆盖标准，并按由弱到强的顺序排列。4.请简述关系型数据库中第三范式（3NF）的定义，并说明满足3NF的必要性。四、综合应用与计算题（每题15分，共45分）1.已知一组权值集合为W=2.在一个采用请求分页存储管理系统中，某进程的逻辑地址空间为16页，每页大小为2KB，内存物理地址空间为64KB。系统为该进程分配了4个物理块。假设该进程依次访问的逻辑页号序列为：1,2,3,4,1,2,5,1,2,3,4,5。（15分）（1）请计算逻辑地址和物理地址的结构（页号位数和页内偏移位数）。（2）若采用先进先出（FIFO）页面置换算法，请给出缺页中断的次数及缺页率（请写出推导过程，计算缺页率使用LaTeX公式）。（3）若采用最近最久未使用（LRU）页面置换算法，请给出缺页中断的次数及缺页率。3.设有一个关系数据库包含三个关系模式：学生表S（Sno,Sname,Age,Sdept）--学号,姓名,年龄,所在系课程表C（Cno,Cname,Credit）--课程号,课程名,学分选课表SC（Sno,Cno,Grade）--学号,课程号,成绩请使用标准SQL语言完成以下操作：（15分）（1）查询选修了课程号为"C01"且成绩大于80分的学生的学号和姓名。（2）查询每门课程的课程号、课程名以及选修该课程的平均成绩，结果按平均成绩降序排列。（3）创建一个名为"优秀学生"的视图，包含选修了"C02"课程且成绩大于90分的学生的学号、姓名和成绩。4.在一个采用CSMA/CD协议的以太网中，网络的数据传输速率为100Mbps，信号在电缆上的传播速度为（1）该网络的单程传播时延是多少？（使用LaTeX公式写出计算过程）（2）该网络的最短帧长度是多少？（使用LaTeX公式写出计算过程）（3）若在此网络中发送一个长度为1500字五、参考答案及详细解析一、单项选择题1.【答案】B【解析】数据的逻辑结构是指数据元素之间的逻辑关系，与存储结构无关，分为线性结构（如线性表、栈、队列）和非线性结构（如树、图）。物理结构（存储结构）才分为顺序存储和链式存储。2.【答案】C【解析】这是一个嵌套循环。外层循环执行n次。内层循环的执行次数依赖于外层变量i。当i=0时内层执行n次，i=1时执行n−1次，...，3.【答案】C【解析】栈的特性是后进先出（LIFO）。对于序列3,1,2,4：要想输出3，必须先压入1,2,3，然后弹出3。此时栈顶元素是2，下一个输出的必须是2，但不可能是1。因此3,1,2,4是不可能出现的输出序列。4.【答案】A【解析】在单链表中删除p的后继结点q，需要将p的next指针指向q的next指针，然后释放q。A选项完全符合此逻辑：先用q保存p的后继，然后修改p的next指向q的next，最后释放q。5.【答案】A【解析】深度为k的完全二叉树，最少结点的情况是第k层只有一个结点，前k−1层为满二叉树。此时结点总数为6.【答案】B【解析】无向图有n个顶点，采用邻接矩阵存储时，是一个n×n的矩阵，因此矩阵大小为7.【答案】A【解析】快速排序在最坏情况下（例如数组已经有序），每次划分只能分出一个元素，退化为冒泡排序，时间复杂度为O()。归并排序和堆排序的最坏复杂度均为O(8.【答案】C【解析】无向连通图的最小生成树可能有多棵（当存在权值相同的边时），但不管有几棵，其所有边的权值之和必定是相等的且最小。A和B的说法过于绝对，D是错误的，生成树的边数必定等于顶点数减一。9.【答案】B【解析】并发是指多个事件在同一时间间隔内发生，宏观上同时发生，微观上交替执行。并行是指多个事件在同一时刻发生（通常需要多核或多处理器）。10.【答案】C【解析】在支持多线程的操作系统中，进程是资源分配的基本单位，线程是调度的基本单位。一个进程可以包含多个线程，且这些线程共享该进程的地址空间和资源。线程的切换开销通常比进程小。11.【答案】A【解析】要保证系统不发生死锁，最极端的情况是每个进程都只差一个资源就能满足要求。即每个进程都已经获得了R−1个资源。如果系统资源总数减去P×(R−112.【答案】D【解析】在分页存储管理中，逻辑地址到物理地址的转换是由内存管理单元（MMU）中的硬件地址转换机构（如页表寄存器、快表TLB等）自动完成的，对用户和程序透明。13.【答案】B【解析】Belady异常现象是指当分配的物理块数增加时，缺页率反而增加的现象。只有先进先出（FIFO）算法可能会产生这种异常，LRU和OPT等栈式算法不会产生。14.【答案】A【解析】瀑布模型规定了软件生命周期各项活动的严格顺序，自上而下，相互衔接，如同瀑布流水一般，是一种典型的线性模型。15.【答案】B【解析】白盒测试把测试对象看作一个透明的盒子，测试人员需要了解程序的内部逻辑结构和处理过程。黑盒测试则关注于功能需求，即输入输出对应关系。16.【答案】A【解析】数据流图（DFD）是结构化分析（SA）中用于描述系统逻辑功能的主要工具，通过数据流、加工、数据存储和外部实体来图形化表示系统。17.【答案】A【解析】实体完整性要求主属性不能取空值。在关系型数据库中，通过定义主键来实现实体完整性约束。18.【答案】B【解析】SQL语言中删除视图使用`DROPVIEW`命令，删除表使用`DROPTABLE`。`DELETE`用于删除表中的数据行。19.【答案】C【解析】物理层位于OSI模型的最底层，其主要任务是在物理媒体上透明地传输原始比特流，不关心数据的含义和格式。20.【答案】A【解析】IPv4地址为32位，子网掩码为表示前24位为网络号，后8位为主机号。将该IP地址的主机部分全置0得到网络地址；将主机部分全置1得到广播地址55。二、填空题1.【答案】顺序；链式【解析】数据结构在计算机中的物理表示（存储映像），根据结点间关系的不同表示方法，通常分为顺序存储结构和链式存储结构。顺序存储借助元素在存储器中的相对位置来表示逻辑关系，链式存储借助指针表示逻辑关系。2.【答案】；【解析】在长度为n的顺序表中插入元素，有n+1个位置可选，平均移动次数为。删除元素有n个位置可选，平均移动次数为。3.【答案】2【解析】哈夫曼树中不存在度为1的结点。每次合并两个子树生成一个新根结点，生成n个叶子结点需要进行n−1次合并，每次合并产生一个度为2的内部结点。总结点数4.【答案】1【解析】无向图的邻接矩阵是对称矩阵，若i和j之间有边相连，则A[i]5.【答案】阻塞【解析】线程的基本状态包括就绪状态（具备运行条件，等待CPU）、执行状态（占用CPU运行）和阻塞状态（因等待某事件而暂停执行，如I/O请求）。6.【答案】等待（或协调）；互斥执行（或排队）【解析】进程同步是指多个进程为了完成同一任务而相互合作，在执行顺序上需要相互协调等待；进程互斥是指多个进程在竞争共享临界资源时，必须保证在同一时刻只允许一个进程进入临界区。7.【答案】空间【解析】程序的局部性原理是指程序在执行时呈现出空间局部性和时间局部性。时间局部性是指刚访问过的指令/数据不久后可能再次被访问；空间局部性是指一旦程序访问了某个存储单元，不久后其附近的存储单元也可能被访问。这是虚拟存储器的基础。8.【答案】过程【解析】软件工程的三要素是方法（解决软件开发的“如何做”）、工具（支持方法的自动或半自动机制）和过程（为了获得高质量软件所需要的一系列任务框架）。9.【答案】耦合性【解析】软件设计的目标是“高内聚、低耦合”。内聚性衡量模块内部各元素结合的紧密程度；耦合性衡量模块之间依赖的紧密程度。10.【答案】逻辑【解析】数据库设计通常分为概念设计、逻辑设计和物理设计。将E-R图转换为关系模型属于逻辑设计阶段的主要工作。11.【答案】持久性【解析】事务的ACID特性：原子性、一致性、隔离性、持久性。持久性是指事务一旦提交，其对数据库的改变是永久的，即使系统故障也不丢失。12.【答案】传输（或网络接口）【解析】在TCP/IP四层模型中，应用层下面是传输层，传输层下面是网际层（网络层），网际层下面是网络接口层（有时合并物理层和数据链路层称为网络接口层）。13.【答案】码分【解析】多路复用技术主要分为：频分多路复用（FDM）、时分多路复用（TDM）、波分多路复用（WDM）和码分多路复用（CDMA）。三、简答题1.【答案】栈和队列都是操作受限的线性表，它们在逻辑结构上同属线性结构，但在操作规则上有本质区别：（1）栈是限制仅在表的一端进行插入和删除的线性表，其操作规则是“后进先出”。删除和插入操作都在栈顶进行。（2）队列是限制在表的一端进行插入、在另一端进行删除的线性表，其操作规则是“先进先出”。插入在队尾，删除在队头。应用场景举例：栈的应用场景：函数调用的系统栈（保存返回地址和局部变量）、表达式求值、括号匹配检验、深度优先搜索（DFS）算法中的路径记录。队列的应用场景：操作系统中的作业调度（如打印机任务队列）、广度优先搜索（BFS）算法中的待访问节点记录、键盘缓冲区。2.【答案】死锁是指多个进程在运行过程中，因争夺资源而造成的一种僵局。当进程处于这种僵持状态时，若无外力干预，它们都将无法再向前推进。产生死锁的四个必要条件为：（1）互斥条件：进程对所分配到的资源进行排他性使用，即在一段时间内某资源只由一个进程占用。（2）请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已被其他进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不放。（3）不剥夺条件：进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。（4）循环等待条件：在发生死锁时，必然存在一个“进程—资源”的环形链，即进程集合,,…,中的正在等待占用的资源，正在等待占用的资源，...，正在等待占用的资源。破坏“循环等待”条件通常采用的方法是：资源顺序分配法。即将系统中的所有资源按某种规则进行线性编号，规定每个进程必须按编号递增的顺序请求资源。如果需要同类资源的多个实例，必须一次性请求完毕。3.【答案】白盒测试也称结构测试或逻辑驱动测试，它是把测试对象当作一个透明的盒子，测试人员利用程序内部的逻辑结构及有关信息，设计或选择测试用例，对程序所有逻辑路径进行测试，以确定程序的实际执行状态与预期状态是否一致。白盒测试主要关注程序内部的执行流程。常见的逻辑覆盖标准由弱到强的顺序排列如下：（1）语句覆盖：使得程序中每条可执行语句至少被执行一次。（2）判定覆盖（也称分支覆盖）：使得程序中每个判定的取真分支和取假分支至少执行一次。（3）条件覆盖：使得判定中的每个逻辑条件的可能取值（真/假）至少满足一次。（4）判定-条件覆盖（分支-条件覆盖）：使得判定中每个条件的所有可能取值至少执行一次，同时每个判定的可能结果也至少执行一次。（5）条件组合覆盖：使得每个判定中所有可能的条件取值组合都至少执行一次。（6）路径覆盖：要求设计足够的测试用例，覆盖程序中所有可能的独立执行路径。4.【答案】关系型数据库中的第三范式（3NF）定义：设关系模式R∈2NF（第二范式），如果关系模式必要性说明：如果一个关系模式不满足3NF，存在传递依赖，例如关系模式（学号，姓名，系名，系主任），其中学号为主键，学号决定系名，系名决定系主任，即系主任传递依赖于学号。这种结构会带来以下问题：1.数据冗余：每个系的学生都会重复存储系名和系主任信息，浪费存储空间。2.插入异常：如果一个系刚成立，还没有学生，则无法将系名和系主任的信息存入数据库中（因为缺乏主键学号）。3.删除异常：如果某系的所有学生都被删除，系的相关信息也随之被删除。4.更新异常：如果某系更换系主任，需要修改所有该系学生的记录，工作量巨大且容易造成数据不一致。满足3NF能够最大程度地消除数据冗余和操作异常，保证数据的完整性和一致性，是数据库逻辑设计的良好规范。四、综合应用与计算题1.【答案】已知权值集合W=初始森林状态：=2合并步骤如下：第一步：选出权值最小的2和3，合并为5。当前森林状态：=第二步：选出权值最小的4和5（假设选原来权值为4和由2,3合并来的5），合并为9。当前森林状态：=第三步：选出权值最小的5和6，合并为11。当前森林状态：=第四步：选出权值最小的7和9，合并为16。当前森林状态：=第五步：选出权值最小的11和16，合并为27。当前森林状态：=27哈夫曼树结构构造完毕。各叶子结点的带权路径长度为该结点的权值乘以其到根结点的路径长度（深度）。根据构造过程，可推算各叶子结点路径长度：权值7和9合并时路径长度增加1，权值2,3,4合并为9，权值5,6合并为11。更精确地计算各叶子节点深度：2深度为4，3深度为4，4深度为3，5深度为3，6深度为3，7深度为2。（注：由于哈夫曼树在合并时左子树和右子树没有严格规定，具体的深度可能因画法不同有所变化，但带权路径长度之和必定是唯一的唯一值）。带权路径长度（WPL）计算公式如下：WW因此，该哈夫曼树的带权路径长度WPL为79。2.【答案】（1）计算逻辑地址和物理地址的结构：逻辑地址空间为16页，因此页号需要lo16=4位二进制表示。每页大小为2KB，即内存物理地址空间为64KB，即字节，物理地址总长度为16位。系统分配了4个物理块，每块大小也是2KB。由于物理块号只需在0~3之间区分，最多使用2位二进制。但在完整的物理地址结构中，物理地址由物理块号和块内偏移组成，物理地址长度为16位。即物理地址结构为：5位块号+11位块内偏移（若系统块数较多时），但针对当前进程分配的4个块，块内偏移依然占11位。（2）采用FIFO页面置换算法分析：初始物理块为空。访问序列为：1,2,3,4,1,2,5,1,2,3,4,5。FIFO原则：淘汰最先进入内存的页面。访问1：缺页。调入1。队列：[1]。缺页次数1访问2：缺页。调入2。队列：[1,2]。缺页次数2访问3：缺页。调入3。队列：[1,2,3]。缺页次数3访问4：缺页。调入4。队列：[1,2,3,4]。缺页次数4，4个物理块已满。访问1：命中。1在内存中。队列不变：[1,2,3,4]。访问2：命中。2在内存中。队列不变：[1,2,3,4]。访问5：缺页。淘汰队首1，调入5。队列：[2,3,4,5]。缺页次数5访问1：缺页。淘汰队首2，调入1。队列：[3,4,5,1]。缺页次数6访问2：缺页。淘汰队首3，调入2。队列：[4,5,1,2]。缺页次数7访问3：缺页。淘汰队首4，调入3。队列：[5,1,2,3]。缺页次数8访问4：缺页。淘汰队首5，调入4。队列：[1,2,3,4]。缺页次数9访问5：缺页。淘汰队首1，调入5。队列：[2,3,4,5]。缺页次数10总缺页次数为10次。总访问次数为12次。缺页率计算公式如下：F这正是FIFO算法中可能出现的Belady异常现象的体现（虽然这里没有对比不同块数的缺页率，但大量命中页面被淘汰反映了FIFO的问题）。（3）采用LRU页面置换算法分析：LRU原则：淘汰最近最长时间未被访问的页面。我们记录每个页面最近一次被访问的时间戳或顺序。访问1：缺页。内存：{1}。缺页1访问2：缺页。内存：{1,2}。缺页2访问3：缺页。内存：{1,2,3}。缺页3访问4：缺页。内存：{1,2,3,4}。缺页4，内存满。访问1：命中。内存更新最近访问时间为：{2,3,4,1}。访问2：命中。内存更新为：{3,4,1,2}。访问5：缺页。淘汰最久未访问的3。调入5。内存：{4,1,2,5}。缺页5访问1：命中。内存：{4,2,5,1}。访问2：命中。内存：{4,5,1,2}。访问3：缺页。淘汰最久未访问的4。调入3。内存：{5,1,2,3}。缺页6访问4：缺页。淘汰最久未访问的5。调入4。内存：{1,2,3,4}。缺页7访问5：缺页。淘汰最久未访问的1。调入5。内存：{2,3,4,5}。缺页8总缺页次数为8次。总访问次数为12次。缺页率计算公式如下：L3.【答案】