历年计算机软考程序员重点题真题及答案软考程序员

历年计算机软考程序员重点题真题及答案软考程序员一、单项选择题（每题1分，共50分）1.在数据结构中，栈和队列的共同特点是（）。A.只允许在端点处插入和删除元素B.都是先进先出C.都是先进后出D.没有共同点答案：A2.用链接方式存储的队列，在进行插入运算时（）。A.仅修改头指针B.头、尾指针都要修改C.仅修改尾指针D.头、尾指针可能都要修改答案：D3.以下数据结构中，属于非线性结构的是（）。A.栈B.队列C.完全二叉树D.线性表答案：C4.设有一棵二叉树，其叶子结点数为n0，度为2的结点数为n2，则n0与n2的关系是（）。A.n0=n2+1B.n0=n21C.n0=2n2D.n2=n0+1答案：A5.在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（）。A.不一定相同B.都相同C.都不相同D.互为逆序答案：B6.若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个（）。A.上三角矩阵B.稀疏矩阵C.对角矩阵D.对称矩阵答案：D7.在面向对象方法中，一个对象请求另一对象为其服务的方式是通过发送（）。A.调用语句B.命令C.口令D.消息答案：D8.软件生命周期中所花费用最多的阶段是（）。A.详细设计B.软件编码C.软件测试D.软件维护答案：D9.下列叙述中，不属于软件需求规格说明书的作用的是（）。A.便于用户、开发人员进行理解和交流B.反映出用户问题的结构，可以作为软件开发工作的基础和依据C.作为确认测试和验收的依据D.便于开发人员进行需求分析答案：D10.下列不属于软件工程的3个要素的是（）。A.工具B.过程C.方法D.环境答案：D11.单个用户使用的数据视图的描述称为（）。A.外模式B.概念模式C.内模式D.存储模式答案：A12.子模式DDL用来描述（）。A.数据库的总体逻辑结构B.数据库的局部逻辑结构C.数据库的物理存储结构D.数据库的概念结构答案：B13.在数据库的三级模式结构中，描述数据库中全体数据的全局逻辑结构和特征的是（）。A.外模式B.内模式C.存储模式D.模式答案：D14.关系数据库管理系统能实现的专门关系运算包括（）。A.排序、索引、统计B.选择、投影、连接C.关联、更新、排序D.显示、打印、制表答案：B15.索引属于（）。A.模式B.内模式C.外模式D.概念模式答案：B16.在关系数据库中，用来表示实体之间联系的是（）。A.树结构B.网结构C.线性表D.二维表答案：D17.将E-R图转换到关系模式时，实体与联系都可以表示成（）。A.属性B.关系C.键D.域答案：B18.SQL语言又称为（）。A.结构化定义语言B.结构化控制语言C.结构化查询语言D.结构化操纵语言答案：C19.设有下列二叉树，对此二叉树中序遍历的结果是（）。（图示为：根结点A，左孩子B（有左孩子D），右孩子C（有右孩子E））A.ABCDEB.DBEAC.DBEACD.DEBAC答案：C20.希尔排序法属于哪一种类型的排序法（）。A.交换类排序法B.插入类排序法C.选择类排序法D.建堆排序法答案：B21.下列关于队列的叙述中正确的是（）。A.在队列中只能插入数据B.在队列中只能删除数据C.队列是先进先出的线性表D.队列是先进后出的线性表答案：C22.对长度为N的线性表进行顺序查找，在最坏情况下所需要的比较次数为（）。A.N+1B.NC.(N+1)/2D.N/2答案：B23.在计算机中，算法是指（）。A.查询方法B.加工方法C.解题方案的准确而完整的描述D.排序方法答案：C24.栈底至栈顶依次存放元素A、B、C、D，在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是（）。A.ABCEDB.DBCEAC.CDABED.DCBEA答案：D25.线性表的顺序存储结构和线性表的链式存储结构分别是（）。A.顺序存取的存储结构、顺序存取的存储结构B.随机存取的存储结构、顺序存取的存储结构C.随机存取的存储结构、随机存取的存储结构D.任意存取的存储结构、任意存取的存储结构答案：B26.在单链表中，增加头结点的目的是（）。A.方便运算的实现B.使单链表至少有一个结点C.标识表结点中首结点的位置D.说明单链表是线性表的链式存储实现答案：A27.软件设计包括软件的结构、数据接口和过程设计，其中软件的过程设计是指（）。A.模块间的关系B.系统结构部件转换成软件的过程描述C.软件层次结构D.软件开发过程答案：B28.为了避免流程图在描述程序逻辑时的灵活性，提出了用方框图来代替传统的程序流程图，通常也把这种图称为（）。A.PAD图B.N-S图C.结构图D.数据流图答案：B29.数据处理的最小单位是（）。A.数据B.数据元素C.数据项D.数据结构答案：C30.下列有关数据库的描述，正确的是（）。A.数据库是一个DBF文件B.数据库是一个关系C.数据库是一个结构化的数据集合D.数据库是一组文件答案：C31.单个用户使用的数据视图的描述称为（）。A.外模式B.概念模式C.内模式D.存储模式答案：A32.需求分析阶段的任务是确定（）。A.软件开发方法B.软件开发工具C.软件开发费用D.软件系统功能答案：D33.算法分析的目的是（）。A.找出数据结构的合理性B.找出算法中输入和输出之间的关系C.分析算法的易懂性和可靠性D.分析算法的效率以求改进答案：D34.链表不具有的特点是（）。A.不必事先估计存储空间B.可随机访问任一元素C.插入删除不需要移动元素D.所需空间与线性表长度成正比答案：B35.已知数据表A中每个元素距其最终位置不远，为节省时间，应采用的算法是（）。A.堆排序B.直接插入排序C.快速排序D.直接选择排序答案：B36.用链表表示线性表的优点是（）。A.便于插入和删除操作B.数据元素的物理顺序与逻辑顺序相同C.花费的存储空间较顺序存储少D.便于随机存取答案：A37.下列不属于结构化分析的常用工具的是（）。A.数据流图B.数据字典C.判定树D.PAD图答案：D38.软件开发的结构化生命周期方法将软件生命周期划分成（）。A.定义、开发、运行维护B.设计阶段、编程阶段、测试阶段C.总体设计、详细设计、编程调试D.需求分析、功能定义、系统设计答案：A39.在软件工程中，白箱测试法可用于测试程序的内部结构。此方法将程序看做是（）。A.循环的集合B.地址的集合C.路径的集合D.目标的集合答案：C40.在数据管理技术发展过程中，文件系统与数据库系统的主要区别是数据库系统具有（）。A.数据无冗余B.数据可共享C.专门的数据管理软件D.特定的数据模型答案：D41.分布式数据库系统不具有的特点是（）。A.分布式B.数据冗余C.数据分布性和逻辑整体性D.位置透明性和复制透明性答案：B42.下列说法中，不属于数据模型所描述的内容的是（）。A.数据结构B.数据操作C.数据查询D.数据约束答案：C43.在计算机系统中，操作系统是（）。A.一般应用软件B.核心系统软件C.用户应用软件D.系统支撑软件答案：B44.支持多道程序设计的操作系统在运行过程中，不断地选择新进程运行来实现CPU的共享，但其中（）不是引起操作系统选择新进程的直接原因。A.运行进程的时间片用完B.运行进程出错C.运行进程要等待某一事件发生D.有新进程进入就绪状态答案：D45.在分时系统中，时间片一定时，（），响应时间越长。A.内存越大B.用户数越多C.内存越小D.用户数越少答案：B46.在下列解决死锁的方法中，属于死锁预防策略的是（）。A.银行家算法B.资源有序分配法C.死锁检测法D.资源分配图化简法答案：B47.在请求分页存储管理中，若采用FIFO页面淘汰算法，则当分配的页面数增加时，缺页中断的次数（）。A.减少B.增加C.无影响D.可能增加也可能减少答案：D48.文件系统的主要目的是（）。A.实现对文件的按名存取B.实现虚拟存储C.提高外存的读写速度D.用于存储系统文件答案：A49.下列（）是文件系统需要解决的问题。I.文件存储空间的管理II.文件的按名存取III.文件的读/写管理IV.文件目录的建立A.I和IIB.I,II和IIIC.I,II和IVD.全部答案：D50.在TCP/IP参考模型中，与OSI参考模型的网络层对应的是（）。A.主机-网络层B.互连层C.应用层D.传输层答案：B二、多项选择题（每题2分，共20分。每题至少有两个正确选项，多选、少选、错选均不得分）1.下列属于软件设计阶段产物的有（）。A.数据流图B.程序流程图C.系统结构图D.伪代码E.数据字典答案：B,C,D2.关于栈和队列，以下说法正确的有（）。A.栈是后进先出的线性表B.队列是先进先出的线性表C.栈和队列都是线性结构D.栈和队列都既可以用顺序存储结构，也可以用链式存储结构E.对栈的插入和删除操作只能在栈底进行答案：A,B,C,D3.下列属于黑盒测试方法的有（）。A.等价类划分B.边界值分析C.错误推测法D.逻辑覆盖E.基本路径测试答案：A,B,C4.在关系数据库中，对关系模式规范化的主要目的是（）。A.减少数据冗余B.提高查询速度C.避免插入、删除和更新异常D.简化数据模型E.增强数据的安全性答案：A,C5.进程的三种基本状态是（）。A.就绪状态B.执行状态C.阻塞状态D.创建状态E.终止状态答案：A,B,C6.下列属于操作系统的功能的有（）。A.处理机管理B.存储器管理C.设备管理D.文件管理E.用户接口管理答案：A,B,C,D,E7.下列属于TCP/IP协议簇中应用层协议的有（）。A.HTTPB.FTPC.TCPD.IPE.SMTP答案：A,B,E8.关于数据库系统的特点，以下说法正确的有（）。A.数据的结构化B.数据的高共享性和低冗余性C.数据的独立性D.数据由DBMS统一管理和控制E.数据完全无冗余答案：A,B,C,D9.下列排序算法中，哪些是稳定的排序算法（）。A.冒泡排序B.直接插入排序C.快速排序D.归并排序E.堆排序答案：A,B,D10.下列属于面向对象方法基本特征的有（）。A.标识唯一性B.分类性C.多态性D.封装性E.模块独立性答案：A,B,C,D三、填空题（每空1分，共20分）1.在长度为n的顺序表中插入一个元素，需要平均移动________个元素。答案：n/22.深度为k的完全二叉树至少有________个结点。答案：2^(k-1)3.在二叉树的第i层上至多有________个结点。答案：2^(i-1)4.对于具有n个顶点的无向图，其邻接矩阵的大小为________。答案：n×n5.在面向对象方法中，________是指一个类实例被多个变量引用。答案：对象引用6.软件测试的步骤主要包括：单元测试、________、确认测试和系统测试。答案：集成测试7.数据字典是各类数据描述的集合，它通常包括数据项、数据结构、数据流、________和处理过程五个部分。答案：数据存储8.数据库系统的三级模式结构由外模式、________和内模式组成。答案：模式9.在关系数据库中，关系模式是型，关系是________。答案：值10.SQL语言中，实现数据查询的语句是________。答案：SELECT11.进程由程序、________和进程控制块三部分组成。答案：数据12.产生死锁的四个必要条件是：互斥条件、请求和保持条件、________和循环等待条件。答案：不剥夺条件13.虚拟存储器的最大容量是由计算机的________结构决定的。答案：地址14.在文件系统中，文件的逻辑结构可分为________文件和记录式文件两类。答案：流式15.IP地址属于________类地址。答案：C16.在TCP协议中，通过________机制来保证数据的可靠传输。答案：确认与重传17.将高级语言源程序翻译成机器语言程序的两种方式是________和解释。答案：编译18.算法的时间复杂度是指算法所需要的________。答案：计算工作量19.在循环队列中，队头指针指向队头元素的________位置。答案：前一个20.在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点的________域指示。答案：指针四、简答题（每题5分，共30分）1.简述栈和队列的区别。答案：栈（Stack）是一种后进先出（LIFO）的线性表，其插入和删除操作只能在表的一端（称为栈顶）进行。队列（Queue）是一种先进先出（FIFO）的线性表，其插入操作在表的一端（称为队尾）进行，删除操作在表的另一端（称为队头）进行。主要区别在于操作的位置和顺序不同。2.什么是数据库的三级模式结构？其优点是什么？答案：数据库的三级模式结构由外模式、模式和内模式组成。外模式是用户视图，是数据库用户能看见和使用的局部数据的逻辑结构和特征描述。模式是全局视图，是所有用户的公共数据视图，描述数据库中全体数据的逻辑结构和特征。内模式是存储视图，是数据物理结构和存储方式的描述。其优点是保证了数据的物理独立性和逻辑独立性。逻辑独立性是指当模式改变时，通过调整外模式/模式映像，使外模式保持不变，从而应用程序不必修改。物理独立性是指当内模式改变时，通过调整模式/内模式映像，使模式保持不变，从而保证了应用程序与物理存储的独立性。3.简述进程与线程的主要区别。答案：进程是资源分配和调度的基本单位，拥有独立的地址空间和系统资源。线程是进程中的一个执行实体，是CPU调度和分派的基本单位，它本身不拥有系统资源，只拥有一点在运行中必不可少的资源（如程序计数器、寄存器和栈），但它可以与同属一个进程的其他线程共享进程所拥有的全部资源。一个进程可以包含多个线程。线程的创建、切换和撤销开销远小于进程。4.什么是软件生命周期？通常分为哪几个阶段？答案：软件生命周期是指软件产品从提出、实现、使用维护到停止使用退役的全过程。通常划分为三个时期：软件定义时期、软件开发时期和软件运行维护时期。具体可分为以下几个阶段：可行性研究与计划制定、需求分析、软件设计（概要设计和详细设计）、软件实现（编码）、软件测试、运行和维护。5.简述TCP协议和UDP协议的主要区别。答案：TCP（传输控制协议）是面向连接的、可靠的、基于字节流的传输层通信协议。它提供全双工通信，通过确认、重传、流量控制和拥塞控制等机制保证数据传输的可靠性，但开销较大，速度相对较慢。UDP（用户数据报协议）是无连接的、不可靠的传输层协议。它只是简单地把数据报发送出去，不保证数据能到达目的地，也不保证顺序，但开销小，传输速度快。TCP适用于要求可靠传输的应用，如文件传输、电子邮件等；UDP适用于对实时性要求高、能容忍少量数据丢失的应用，如视频流、语音通话等。6.简述快速排序的基本思想。答案：快速排序的基本思想是采用分治策略。首先从待排序序列中选取一个元素作为基准（通常选第一个元素）。通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比基准小，另一部分记录的关键字均比基准大。然后分别对这两部分记录递归地进行快速排序，以达到整个序列有序。具体过程是设置两个指针low和high，分别指向序列的起始和末尾，从high所指位置向前搜索找到第一个小于基准的元素，交换到low位置；然后从low所指位置向后搜索找到第一个大于基准的元素，交换到high位置；重复直到low=high，该位置即为基准的最终位置。五、应用题（共30分）1.应用题-计算类（10分）假设有一个带头结点的单链表L，其结点结构为（data,next）。请写出在该链表中查找值为x的结点，并返回其指针的算法（函数）描述。若找不到，返回NULL。答案：```ctypedefstructLNode{intdata;structLNodenext;structLNodenext;}LNode,LinkList;}LNode,LinkList;LNodeSearch_Node(LinkListL,intx){LNodeSearch_Node(LinkListL,intx){//L为带头结点的单链表的头指针LNodep=L->next;//从第一个元素结点开始LNodep=L->next;//从第一个元素结点开始while(p!=NULL){if(p->data==x){returnp;//找到，返回结点指针}p=p->next;}returnNULL;//未找到，返回NULL}```2.应用题-分析类（10分）有一个仓库可以存放A和B两种产品，但要求：（1）每次只能存入一种产品（A或B）；（2）-N<(A产品数量B产品数量)<M。其中，N和M是正整数。试用P、V操作描述产品A和产品B的入库过程。答案：设两个信号量：Sa用于控制A产品的入库条件，初始值为M-1；Sb用于控制B产品的入库条件，初始值为N-1。另设一个互斥信号量mutex，用于互斥访问共享变量，初始值为1。共享变量：countA表示A产品当前数量，countB表示B产品当前数量，初始均为0。```pascalProcess_A(){//A产品入库进程while(true){P(Sa);//检查能否再放入A（即A-B是否小于M-1）P(mutex);//执行A产品入库操作countA++;V(mutex);V(Sb);//放入一个A后，A-B的值增1，相当于B-A的值减1，可能允许B产品入库条件满足}}Process_B(){//B产品入库进程while(true){P(Sb);//检查能否再放入B（即B-A是否小于N-1）P(mutex);//执行B产品入库操作countB++;V(mutex);V(Sa);//放入一个B后，B-A的值增1，相当于A-B的值减1，可能允许A产品入库条件满足}}```注意：初始值Sa=M-1,Sb=N-1，是因为当countA-countB=M-1时，再放入一个A就会达到M，违反条件。同理，countB-countA=N-1时，再放入一个B就会达到N。3.应用题-综合类（10分）设有关系模式R（U，F），其中U={A,B,C,D,E}，F={AB→C,B→D,C→E,EC→B,AC→B}。（1）求（AB）关于函数依赖集F的闭包（AB）⁺。（2）R的候选键是什么？（3）R最高属于第几范式？为什么？（4）若R不属于3NF，请将其分解为3NF，并保持函数依赖。答案：（1）求（AB）⁺：初始化：X={A,B}根据AB→C，将C加入X，X={A,B,C}根据B→D，将D加入X，X={A,B,C,D}根据C→E，将E加入X，X={A,B,C,D,E}不再有新的属性加入。因此，（AB）⁺={A,B,C,D,E}。（2）因为（AB）⁺=U，且A⁺和B⁺都不等于U（A⁺可能只含A，B⁺={B,D}），所以AB是候选键。检查其他属性组合：AC？(AC)⁺：由AC→B，得B；由AB→C已有；由B→D得D；由C→E得E。所以(AC)⁺=U，AC也是候选键。同理，EC？(EC)⁺：由EC→B得B；由B→D得D；由AB→C已有；由C→E已有；所以(EC)⁺=U，EC也是候选键。候选键有：AB,AC,EC。（3）R最高属于1NF，因为存在非主属性对候选键的部分函数依赖和传递函数依赖。例如，对于候选键AB，有B→D，即非主属性D部分依赖于候选键AB