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

软件技术基础模拟试题及参考答案一、单项选择题（本大题共15小题，每小题2分，共30分。在每小题给出的四个选项中，只有一项是符合题目要求的）1.下列关于数据结构的叙述中，正确的是（）。A.数据的逻辑结构与存储结构无关B.数据的存储结构独立于其逻辑结构C.线性表的逻辑结构与采用顺序存储或链式存储无关D.数组的逻辑结构属于非线性结构2.某算法的时间复杂度为O(A.2B.4C.8D.163.设循环队列的存储空间为Q[A.front==rearB.(rear+1)%M==frontC.rear==M-1D.(front+1)%M==rear4.已知一棵完全二叉树有n个节点，则该二叉树的深度为（）。（其中⌊xA.⌊B.⌊C.⌈D.⌊5.在一个无向图中，所有顶点的度数之和为m，则该图的边数为（）。A.mB.mC.mD.26.下列排序算法中，在最坏情况下时间复杂度为O(nlA.快速排序B.归并排序C.堆排序D.冒泡排序7.操作系统中最基本的两个特征是（）。A.并发和异步B.共享和虚拟C.并发和共享D.虚拟和异步8.产生死锁的四个必要条件中，不包括（）。A.互斥条件B.请求和保持条件C.环路等待条件D.抢占式调度条件9.在分页存储管理系统中，若页大小为4KB，则十进制逻辑地址A.页号2，偏移量364B.页号2，偏移量260C.页号3，偏移量364D.页号3，偏移量26010.软件工程中，需求分析阶段产生的核心文档是（）。A.概要设计说明书B.软件需求规格说明书C.详细设计说明书D.项目开发计划11.在面向对象方法中，实现对象间通信的机制称为（）。A.继承B.封装C.消息传递D.多态12.下列关于软件测试的叙述中，正确的是（）。A.软件测试的目的是证明软件没有错误B.软件测试应从代码编写完成后开始C.黑盒测试是一种基于程序内部逻辑结构的测试方法D.白盒测试又称为结构测试或逻辑驱动测试13.在关系数据库中，消除属性间的部分函数依赖和传递函数依赖所达到的范式分别是（）。A.1NF和2NFB.2NF和3NFC.3NF和BCNFD.BCNF和4NF14.在TCP/IP参考模型中，TCP协议工作在（）。A.应用层B.传输层C.网际层D.网络接口层15.下列IP地址中，属于C类私有地址的是（）。A.B.C.00D.二、填空题（本大题共10小题，每小题2分，共20分）1.数据的存储结构主要分为顺序存储结构、链式存储结构、__________和散列存储结构。2.在一个长度为n的有序顺序表中进行折半查找，其时间复杂度为__________。3.已知一棵二叉树的前序遍历序列为ABDECFG，中序遍历序列为DBEAFCG，则其后序遍历序列为__________。4.深度为k的完全二叉树至少有__________个节点。5.进程的三种基本状态为就绪态、执行态和__________。6.虚拟存储器的容量受限于计算机的__________和CPU的地址结构。7.在软件生命周期中，软件定义时期通常划分为问题定义、可行性研究和__________三个阶段。8.面向对象建模中，最常用的三种动态模型是对象模型、动态模型和__________。9.在SQL语言中，实现数据检索的语句是__________，实现数据删除的语句是DELETE。10.计算机网络按照覆盖范围分类，可分为局域网（LAN）、城域网（MAN）和__________（WAN）。三、判断题（本大题共10小题，每小题1分，共10分。正确的打“√”，错误的打“×”）1.栈和队列都是限制存取点的线性数据结构，栈遵循后进先出原则，队列遵循先进先出原则。（）2.哈希表的查找效率主要取决于哈希函数和冲突解决方法，与装填因子无关。（）3.快速排序算法在所有情况下都是最快的，其最坏时间复杂度也为O(4.多道程序设计技术允许多个程序同时存在于内存中，并交替使用CPU。（）5.信号量机制中，若信号量的初值为1，则使用P、V操作可以实现进程间的互斥，但无法实现同步。（）6.软件危机的主要表现为软件开发成本和进度估计不准确，以及软件维护困难等。（）7.黑盒测试的等价类划分方法需要将程序的输入域划分为若干个等价类，从中选取代表性数据作为测试用例，既包含有效等价类也包含无效等价类。（）8.关系数据库中，外键的作用主要是为了实现实体完整性约束。（）9.在网络分层模型中，下层为其上一层提供服务，且同一层内的协议可以独立工作。（）10.IPv6采用128位地址长度，从根本上解决了IPv4地址枯竭的问题。（）四、简答题（本大题共4小题，每小题5分，共20分）1.简述进程与线程的区别与联系。2.简述软件测试中黑盒测试和白盒测试的概念，并列举至少三种各自常用的测试方法。3.什么是数据库事务？简述事务的ACID特性。4.简述快速排序的基本思想，并说明其在最好和最坏情况下的时间复杂度及其产生原因。五、综合应用题（本大题共2小题，每小题10分，共20分。要求写出详细的计算或推导过程）1.假设有一组权值集合W=2.在某银行家算法系统中，有A,B,进程Allocation(ABC)Max(ABC)$P_0$010753$P_1$200322$P_2$302902$P_3$211222$P_4$002433已知当前系统Available(可用资源)向量为(3（1）请计算各进程的Need矩阵（仍需各类资源数）。（2）利用银行家算法判断当前系统是否处于安全状态。如果安全，请给出一个安全序列；如果不安全，请说明原因。（3）若此时进程提出资源请求Req参考答案及详细解析一、单项选择题（本大题共15小题，每小题2分，共30分）1.【答案】C【解析】选项A错误，逻辑结构反映数据元素间的逻辑关系，独立于计算机，与存储结构无关，此表述本身看似正确，但不如C准确且全面；选项B错误，存储结构是逻辑结构在计算机中的表示，依赖于逻辑结构；选项C正确，线性表的逻辑结构是线性的，无论采用顺序存储（顺序表）还是链式存储（链表），其逻辑结构均不改变；选项D错误，数组在逻辑结构上属于线性结构，虽然多维数组可以看作是数组嵌套，但一般不归类为非线性结构（如树或图）。2.【答案】B【解析】算法时间复杂度为O()，假设原运行时间为T=c·3.【答案】B【解析】循环队列为了区分队空和队满，通常牺牲一个存储单元。队空条件为`front==rear`，队满条件为`(rear+1)%M==front`，即队尾指针的下一个位置是队头指针。4.【答案】A【解析】完全二叉树的深度公式为⌊lon⌋+1。证明：深度为k的完全二叉树，其前k−1层为满二叉树，节点数为−1，加上第k层至少1个节点，故n≥；同时前k层满二叉树节点为5.【答案】B【解析】在无向图中，每条边连接两个顶点，在计算各顶点度数之和时，每条边会被其连接的两个顶点各计算一次。因此，所有顶点的度数之和为2m（m为边数）。题目中给定的度和为m，说明实际边数为m6.【答案】C【解析】快速排序最坏时间复杂度为O()；归并排序最坏时间复杂度为O(nlon)，但空间复杂度为7.【答案】C【解析】操作系统的基本特征包括并发、共享、虚拟和异步。其中，并发和共享是最基本的两个特征。并发是多道程序设计的基础，而共享则是并发执行的必然要求。8.【答案】D【解析】产生死锁的四个必要条件是：互斥条件、请求和保持条件、不剥夺条件（非抢占式）和环路等待条件。D选项“抢占式调度条件”与不剥夺条件相反，不属于死锁产生的必要条件。9.【答案】A【解析】页大小为4KB=4096字节。逻辑地址8452除以4096，商为2，余数为8452−10.【答案】B【解析】需求分析阶段的主要任务是确定软件系统必须“做什么”，产生的核心文档是《软件需求规格说明书》（SRS）。概要设计和详细设计属于软件设计阶段。11.【答案】C【解析】继承是类与类之间的关系；封装是隐藏对象属性和实现细节的机制；多态是不同对象对同一消息的不同响应；消息传递是面向对象中实现对象间通信和交互的机制。12.【答案】D【解析】软件测试的目的是发现程序中的错误，而不是证明没有错误，A错；测试应尽早进行，贯穿整个生命周期，B错；黑盒测试是基于功能需求，不考虑内部逻辑，C错；白盒测试基于程序内部逻辑结构，又称结构测试，D正确。13.【答案】B【解析】1NF消除非主属性对码的部分函数依赖达到2NF；消除非主属性对码的传递函数依赖达到3NF。14.【答案】B【解析】TCP（传输控制协议）提供面向连接的、可靠的字节流服务，工作在TCP/IP模型的传输层。IP工作在网际层，HTTP工作在应用层。15.【答案】C【解析】A类私有地址：~55；B类私有地址：~55；C类私有地址：~55。选项C属于C类私有地址。二、填空题（本大题共10小题，每小题2分，共20分）1.【答案】索引存储结构【解析】常见的四种存储结构为顺序、链式、索引和散列（哈希）。2.【答案】O【解析】折半查找每次将查找区间缩小一半，最多比较次数为⌊lon3.【答案】DEBFGCA【解析】前序为根左右，中序为左根右。前序首元素A为根，中序中A左侧DBE为左子树，右侧FCG为右子树。递归分析：左子树前序BDE，中序DBE，B为根，D为左，E为右。右子树前序CFG，中序FCG，C为根，F为左，G为右。后序为左右根：左子树后序DEB，右子树后序FGC，加上根A，为DEBFGCA。4.【答案】【解析】深度为k的完全二叉树，前k−1层是满二叉树，节点数为−1，第k5.【答案】阻塞态【解析】进程的基本状态包括就绪、执行和阻塞（等待）。6.【答案】内存容量【解析】虚拟存储器是将内存和外存结合，其最大容量由内存容量和外存容量共同决定，但实际可用容量受限于计算机系统的地址结构（CPU地址总线位数）。7.【答案】需求分析【解析】软件定义时期包括问题定义、可行性研究和需求分析。8.【答案】功能模型【解析】面向对象建模的三大模型为：对象模型（静态结构）、动态模型（交互行为）和功能模型（数据变换）。9.【答案】SELECT【解析】SQL语言中，数据检索使用SELECT语句，数据更新使用UPDATE，数据删除使用DELETE，数据插入使用INSERT。10.【答案】广域网【解析】按覆盖范围分类，网络分为局域网（LAN）、城域网（MAN）和广域网（WAN）。三、判断题（本大题共10小题，每小题1分，共10分）1.【答案】√【解析】栈和队列都是操作受限的线性表，栈仅允许在栈顶操作（LIFO），队列仅允许在队尾入队、队头出队（FIFO）。2.【答案】×【解析】哈希表的查找效率不仅取决于哈希函数和冲突解决方法，还与装填因子（α）密切相关。装填因子越大，冲突概率越高，查找效率越低。3.【答案】×【解析】快速排序的平均时间复杂度为O(nl4.【答案】√【解析】多道程序设计技术允许将多个作业同时放入内存，它们共享CPU和其他系统资源，在宏观上同时运行，微观上交替执行。5.【答案】×【解析】信号量初值为1，配合P、V操作既可以实现互斥（临界区管理），也可以实现同步（前驱关系）。初值为0常用于实现同步。6.【答案】√【解析】软件危机的典型表现包括开发成本超支、进度拖延、软件质量低下、维护困难等。软件工程正是为了解决软件危机而提出的。7.【答案】√【解析】等价类划分法不仅需要划分有效等价类（符合需求规格的输入），还必须划分无效等价类（非法、错误或异常输入），以确保程序的容错能力。8.【答案】×【解析】外键的作用是为了实现参照完整性约束，保证数据的一致性；主键用于实现实体完整性约束。9.【答案】√【解析】网络分层体系结构中，下层通过服务访问点（SAP）为上层提供服务，上层无需了解下层实现细节；对等层之间的通信规则称为协议。10.【答案】√【解析】IPv4采用32位地址，约有43亿个地址；IPv6采用128位地址，提供几乎无限的地址空间，有效解决了IPv4地址枯竭问题。四、简答题（本大题共4小题，每小题5分，共20分）1.【参考答案】（1）区别：①调度与资源分配：进程是操作系统进行资源分配和保护的基本单位，拥有独立的地址空间和系统资源；线程是CPU调度和分派的基本单位，自身基本上不拥有系统资源，只拥有一点在运行中必不可少的资源（如程序计数器、寄存器、栈），它与同属一个进程的其他线程共享该进程的全部资源。②系统开销：在创建、撤销和上下文切换时，进程的系统开销远大于线程。由于线程共享进程地址空间，线程切换只需保存少量寄存器和栈指针，开销小。③并发性：进程间可以并发执行，线程间也可以并发执行，但同一进程内的多个线程并发执行效率更高。（2）联系：一个进程可以包含一个或多个线程，线程必须存在于进程中，是进程的一部分。进程为线程提供运行环境，线程是进程执行的具体执行单元。2.【参考答案】（1）概念：①黑盒测试：把测试对象看作一个黑盒子，测试人员完全不考虑程序内部的逻辑结构和内部特性，只依据程序的需求规格说明书，检查程序的功能是否按照需求规格说明书的规定正常使用。黑盒测试又称为功能测试。②白盒测试：把测试对象看作一个透明的盒子，测试人员利用程序内部的逻辑结构及有关信息，设计或选择测试用例，对程序所有逻辑路径进行测试，确定实际状态与预期状态是否一致。白盒测试又称为结构测试。（2）常用方法：①黑盒测试常用方法：等价类划分法、边界值分析法、错误推测法、因果图法等。②白盒测试常用方法：逻辑覆盖法（如语句覆盖、判定覆盖、条件覆盖、判定/条件覆盖、条件组合覆盖、路径覆盖）、基本路径测试法等。3.【参考答案】（1）概念：数据库事务是访问并可能操作各种数据项的一个数据库操作序列，这些操作要么全部执行，要么全部不执行，是一个不可分割的工作单位。（2）ACID特性：①原子性：事务是一个完整的操作，包含在其中的所有数据库操作要么全部成功执行，要么全部不执行。如果事务中某操作失败，则整个事务回滚到初始状态。②一致性：事务在执行前后，必须使数据库从一个一致性状态转变到另一个一致性状态。即事务执行的结果必须满足数据库的完整性约束。③隔离性：在并发环境中，当多个事务并发执行时，一个事务的执行不应影响其他事务的执行。各并发事务之间相互隔离，互不干扰。④持久性：事务一旦提交成功，它对数据库中数据的改变就是永久性的。即使系统发生故障，数据库也不会丢失已提交事务的执行结果。4.【参考答案】（1）基本思想：快速排序采用分治法。在待排序的序列中任选一个元素作为基准（pivot），通过一趟排序将序列分为两部分：一部分中所有元素的值均小于或等于基准元素的值，另一部分中所有元素的值均大于基准元素的值。此时基准元素已处于其最终排好序的正确位置。然后，对这两个子序列分别递归地进行快速排序，直到整个序列有序。（2）时间复杂度及原因：①最好情况：O(nlon)。此时每次划分都能将序列非常均匀地分为两个长度大致相等的子序列，递归树的深度为②最坏情况：O()。此时待排序序列已经有序（正序或逆序），每次选取的基准元素总是序列中的最大或最小值，导致划分极度不平衡，一个子序列长度为n−1，另一个为0。递归树退化为单支树，深度变为n，需要进行五、综合应用题（本大题共2小题，每小题10分，共20分）1.【参考答案】（1）构造哈夫曼树的过程：权值集合W=每次选择权值最小的两个节点合并，生成新的节点，其权值为两者之和。设节点结构表示为（权值），过程如下：第一步：从2,3,剩余节点：4,第二步：从4,(5),剩余节点：7,第三步：从7,8,剩余节点：9,第四步：从9,(9),剩余节点：(15第五步：将(15)和(18哈夫曼树构建完成，根节点权值为33。（2）带权路径长度（WPL）计算：根据哈夫曼树，各叶子节点所在深度如下：权值9（原节点）：深度2。路径贡献：9权值15的子树由7和8构成：权值7：深度2。路径贡献：7权值8：深度2。路径贡献：8权值18的子树由4和(5权值4：深度3。路径贡献：4(5权值2：深度4。路径贡献：2权值3：深度4。路径贡献：3WPL计算公式为WWP或者直接计算非叶子节点权值之和：5+（3）哈夫曼编码（规定左分支为0，右分支为1，从根出发）：9：根直接走左子树或右子树，假设9在左，编码为`0`N3(15)在右子树，右子树再分：7：`10`8：`11`N4(18)在右子树的另一侧，假设9在左，则N4在右：N2(9)在左：`10`等会冲突，重新梳理树形：根节点（33）├──左子：9（深度2）->编码假设为`0`└──右子：N4(18)（深度1）├──左子：N2(9)（深度2）│├──左子：4->编码`100`│└──右子：N1(5)│├──左子：2->编码`1010`│└──右子：3->编码`1011`└──右子：N3(15)（深度2）├──左子：7->编码`110`└──右子：8->编码`111`（注：左右分支的0/1分配可对调，只要满足前缀码要求即可，以下为一种标准答案）权值9的编码：`0`权值4的编码：`100`权值2的编码：`1010`权值3的编码：`1011`权