快速排序是一种典型分治算法。采用快速排序对数组A[p..r]排序三个步骤如下: 分解：选择一个枢轴（pivot）元素划分数组。将数组A[p..r]划分为两个子数组（可能为空） A[p..q-1]和A[q+1..r]，使得A[q]大于等于A[p..q-1]中每个元素，小于A[q+1..r]中每个元素。q值在划分过程中计算。 递归求解：通过递归调用快速排序，对子数组A[p..q-1]和A[q+1..r]分别排序。 合并：快速排序在原地排序，故不需合并操作。 【问题1】 下面是快速排序伪代码，请填补其中空缺。伪代码中主要变量说明如下： A：待排序数组 p, r：数组元素下标，从p到r q：划分位置 x：枢轴元素 i：整型变量，用于描述数组下标。下标小于或等于i元素值小于或等于枢轴元素值 j：循环控制变量，表示数组元素下标 QUICKSORT( A, p, r ){if ( p 大于 r ){q = PARTITION( A,p,r ) ;QUICKSORT( A, p, q-1 );QUICKSORT( A, q+1, r );}}PARTITION( A, p, r ){x= A[r]; i = p - 1;for( j = p ; j 大于= r - 1; j++ ){if ( A[j] 大于= x ){i = i + 1 ;交换A[i] 和 A[j];}}交换 （1） 和 （2） //注：空（1）和空（2）答案可互换，但两空全部答对方可得分return （3） } 【问题2】（1） 假设要排序包含n个元素数组，请给出在各种不同划分情况下，快速排序时间复杂度，用O记号。最佳情况为 （4）平均情况为 （5）最坏情况为 （6） （2） 假设要排序n个元素都具有相同值时，快速排序运行时间复杂度属于哪种情况? （7）（最佳、平均、最坏） 【问题3】（1） 待排序数组是否能被较均匀地划分对快速排序性能有重要影响，因此枢轴元素选取非常重要。有人提出从待排序数组元素中随机地取出一个元素作为枢轴元素，下面是随机化快速排序划分伪代码-利用原有快速排序划分操作，请填充其中空缺处。其中，RANDOM( i,j )表示随机取i到j之间一个数，包括i和j。 RANDOMIZED-PARTITION( A,p,r ){i = RANDOM( p,r );交换（8）和（9）; //注：空（8）和空（9）答案可互换，但两空全部答对方可得分return PARTITION( A,p,r );} （2） 随机化快速排序是否能够消除最坏情况发生? （10）（是或否）
【问题1】（1）A[i+1] 或 A[r] （2）A[r] 或 A[i+1] （3）i+1 【问题2】（4）O(nlgn) 或 O(nlog2n) （5）O(nlgn) 或 O(nlog2n) （6）O(n2 ) （7）最坏 【问题3】（8）A[i] （9）A[r] （10）否
该题主要考查考生对分治算法快速排序理解，对伪代码、快速排序复杂度掌握，做题关键是要读懂题干，理解题干中对算法描述。 问题1考查是算法伪代码表示。分治法设计思想是将一个难以直接解决问题，分解成一些规模较小相同问题，各个击破。其快速排序算法核心处理是进行划分，根据枢轴元素值，把一个较大数组分成两个较小子数组。一个子数据组所有元素值小于等于枢轴元素值，一个子数组所有元素值大于枢轴元素值，而子数组内元素不排序。以最后一个元素为枢轴元素进行划分，从左到右依次访问数组每一个元素，与枢轴元素比较大小，并进行元素交换。在问题1给出伪代码中，当循环结束后，A[p..i]中值小于等于枢轴元素值x，而A[i+1..r-1]中值应大于x。此时A[i+1]是第一个比A[r]大元素，于是A[r]与A[i+1]交换，得到划分后两个子数组。由于划分操作（即PARTITION操作）返回枢轴元素值，因此返回值为i+1。 问题2考查是算法时间复杂度分析。当每次都能做均匀划分时，是算法最佳情况，其时间复杂度为T( N )=2T( n/2 )+O( N )，即时间复杂度为O( nlgn )；算法最坏情况是每次为极不均匀划分，即长度为n数组划分后一个子数组为n-1，一个为0，其时间复杂度为T( N )=T( n-1 )+O( N )，即时间复杂度为O( n2 )；算法平均情况分析起来比较复杂，假设数组每次划分为9/10:1/10，此时时间复杂度可以通过计算得到为O(nlgn)；也就是说在平均情况下快速排序仍然有较好性能。问题2中假设要排序n个元素都具有相同值时，快速排序运行时间复杂度，属于最坏情况，因为每次都划分为长度为n-1和0两个子数组。 问题3中，由于随机化快速排序划分调用了PARTITION操作，而传统划分每次以数组最后一个元素作为枢轴元素。随机化快速排序消除了输入数据不同排列对算法性能影响，降低了极端不均匀划分概率，但不能保证不会导致最坏情况发生。
某监理单位承担了某政府机关网络平台和机房建设工程监理工作。通过公开招标，确定工程承建单位是公司A，按照《合同法》要求与公司A签订了工程建设合同并在合同中规定，公司A可以将机房工程这样非主体、非关键性子工程分包给具备相关资质专业公司。在工程项目实施过程中，发生了如下事件：
事件1：公司A在征得建设单位同意后，将其中机房工程建设工作分包给具有相应资质公司B，并将分包结果以书面形式通知了监理单位。
事件2：在机房工程施工中，总监理工程师在巡视中发现施工人员为了赶工期，把信号线和电源线放在了同一线槽中，违反了有关规范中信号线防干扰规定。总监理工程师随即要求公司B保护好施工现场并于2小时内将发生质量事故情况以书面形式上报建设单位和监理单位以便共同确认处理意见。
事件3：签订合同后，公司A向监理提交了《网络工程建设进度计划》，监理审核后认为该计划符合要求并予以签认。
事件4：工程验收是信息网络系统建设收尾工作，公司A按《网络工程建设进度计划》规定时间于9月10日完工，并于9月15日提出验收申请。在确认工程项目已经达到验收条件情况下，三方决定对项目实施验收，成立工程验收小组由5人组成，其中建设单位项目负责人1人、监理单位人员1人、外聘专家3人。
【问题1】在事件1中，公司A分包过程是否妥当？为什么？
【问题2】在事件2中，总监理工程师做法是否妥当？为什么？
【问题3】在事件3中，监理单位做法妥当吗？阐述监理在实施进度控制时，可以采用基本措施是什么。
【问题4】在事件4中，验收小组组成妥当吗？为什么？正式验收一般程序包括八个步骤，请列出。
信息网络系统是信息系统重要组成部分，对信息网络系统监理工程实施是信息网络工程建设重要组成部分。
【问题1】信息网络系统现场实施通常分哪几个步骤进行？（5分）
【问题2】请简述网络设备采购到货环节监理流程。（5分）
【问题3】请列出两种信息网络系统常用监理方法，并对列出监理方法给出简要说明。（5分）
【问题4】在信息网络系统完工时，应由建设单位、承建单位和监理单位三方共同确定验收方案。验收方案确认重点工作之一就是确认工程验收基本条件是否满足要求，这时监理单位主要工作是什么？（5分）
根据你所学监理知识，回答问题1至问题5，将解答填入答题纸对应栏内。（每个问题，回答一条得一分，每个问题只需答对4条即满分）
【问题1】（4分）
信息网络系统验收前提条件是什么？
【问题2】（4分）
信息应用系统验收前提条件有哪些？
【问题3】（4分）
网络设备和TCP/IP网络检测主要考虑技术指标有哪些，分别对四个指标名字进行简要解释。（只写出四个指标名字，可以给满分）
【问题4】（4分）
光缆测试有哪四种？各有什么工具测？
【问题5】（4分）
根据发改委55号令，初步验收时，建设单位对？、？、？、？进行验收，形成初验报告？
某工程，实施过程中发生如下事件：[事件1]：总监理工程师组建项目监理机构组织形式如图2015-1-1所示。
[事件2]：在第一次工地会议上，总监理工程师提出以下两方面要求，一是签发工程暂停令情形包括：①建设单位要求暂停施工；②施工单位拒绝项目监理机构管理；③施工单位采用不适当施工工艺或施工不当，造成工程质量不合格。二是签发监理通知单情形包括：①施工单位违反工程建设强制性标准；②施工存在重大质量、安全事故隐患。[事件3]：专业监理工程师编写深基坑工程监理实施细则主要内容包括：专业工程特点、监理工作方法及措施。其中，在监理工作方法及措施中提出：①要加强对深基坑工程施工巡视检查；②发现施工单位未按深基坑工程专项施工方案施工，应立即签发工程暂停令。[事件4]：施工过程中，施工单位对需要见证取样一批钢筋抽取试样后，报请项目监理机构确认。监理人员确认试样数量后，通知施工单位将试样送到检测单位检验。问题：1.指出图1-1所示项目监理机构组织形式属哪种类型，说明其主要优点。（5分）2.指出事件2中签发工程暂停令和监理通知单情形不妥项，并写出正确做法。（5分）3.写出事件3中监理实施细则还应包括内容。指出监理工作方法及措施中提出具体要求是否妥当并说明理由。（3分）4.指出事件4中施工单位和监理人员不妥之处，写出正确做法。（2分）
【说明】某企业信息系统工程项目，包括网络建设、机房系统建设、软件开发等多个项目，甲公司为建设单位，通过公开招投标方式选择乙为承建方，丙为监理方，在项目实施过程中发生了如下事件： 【事件1】为保证系统建设过程中开发需求准确无误，在软件开发之前，监理方严格执行信息系统建设相关规定，协助承建方完成了需求分析。 【事件2】在项目业务软件开发实施过程中，由于乙方由于原因导致项目进度滞后，甲丶丙方多次要求乙方尽快调整进度。迫于甲丶丙方压力，乙方在甲、丙方不知情情况下，从其他项目组抽调多名技术人员，加入到本项目现场开发工作中，丙方在发现后立刻向乙方发停工令，要求新加入人员所承担工作暂时停工，乙方认为监理方做法错误并影响了工程进度，并应该补偿有此造成工期损失。 【事件3】在项目实施过程中，为了确保代码质量，承建单位除了按合同要求对开发过程进行有效控制外，还将测试覆盖率由 60%提高到 90%，为此增加成本 57 万。实施完成后，承建单位向监理工程师提出费用补偿要求。 【事件4】在一次项目沟通会上，甲方提出对软件功能进行小幅调整，会上通过甲乙方充分讨论，均认为需求变更确有必要，工作量增加不大，乙方便同意了甲方变更要求并实施。 【问题1】 （6分） 针对事件 1，需求分析阶段成果有哪些？ 【问题2】 （6分）在事件2中，作为监理工程师，请回答；（1） 监理方做法是错误吗？请说出理由。（2） 乙方新进人员资质有问题吗？请说出理由。（3） 应该给乙方相应工期补偿吗？ 【问题3】 （4分）针对问题3，作为监理工程师，你是否同意承建单位费用补偿要求，并说明理由。 【问题4】 （4分） 请指出事件4中应用软件变更中存在错误做法。
【说明】某单位拟通过公开招标方式选择一家集成单位承担收款系统开发工作，开标现场共有3家单位前来投标。 【事件1】招标人组建了总人数为6人评标委员会，其中招标人代表1人，招标代理机构代表1人，法律顾问2人，技术专家2人。监理方受建设方委托组织整个评标过程，因为监理方经验非常丰富，整个评标过程非常顺利，最终评标组组长签字确认中标企业后，报建设单位执行。 【事件2】整个招投标流程甲方并不清楚，因此咨询监理方相关内容。 【事件3】采用公开招标前甲方无法独立完成可行性分析，因此找到监理方，希望监理方协助其完成可行性分析。 【问题1】 （5分）请指出事件1所描述评标过程中存在问题有哪些、分别说明原因。 【问题2】 （6分）招投标过程包括哪些内容？ 【问题3】 （4分） 监理方是否需要协助甲方完成可行性分析，如果是请指出监理方在进行可行性分析应关注哪些方面？
根据你所学监理知识，回答问题1至问题5，将解答填入答题纸对应栏内。（每个问题，回答一条得一分，每个问题只需答对4条即满分）
【问题1】（4分）
工程验收监理报告必须包括哪些要素？
【问题2】（4分）
工程监理总结报告包括哪些方面？
【问题3】（4分）
信息网络系统集成一般体系框架分为哪些平台？
【问题4】（4分）
信息网络系统过程控制常用监理方法有哪些？
【问题5】（4分）
双绞线指标有哪些？
政府投资建设某工程，施工合同约定：生产设备由建设单位直接向设备制造厂商采购；幕墙工程属于依法必须招标暂估价分包项目，由施工合同双方共同招标确定专业分包单位；材料费中应包含技术保密费、专利费、技术资料费等。工程实施过程中发生如下事件：[事件1]：进行挖孔桩检测时，项目监理机构发现部分桩实际承载力达不到设计要求。经查，确认是因地质勘察资料有误所致，施工单位按程序对这些桩进行了相应技术处理，并提出工期和费用索赔申请。[事件2]：施工过程中，施工单位按合同约定使用其拥有专利新材料前，项目监理机构要求对新材料验收标准组织专家论证。结算工程款时，施工单位要求建设单位支付新材料专利使用费。[事件3]：生产设备安装完毕后进行单机无负荷试车不满足验收要求，经查，设备本身存在缺陷，须更换设备零部件。施工单位按约定程序向项目监理机构提出了零部件拆除、重新购置和重新安装费用索赔申请。施工合同中约定施工单位负责到场生产设备清点、验收和接收，为此，建设单位建议施工单位直接向设备制造厂商提出费用索赔申请。[事件4]：幕墙分包工程招标工作启动前，施工单位向项目监理机构提交施工招标方案提出：①采用议标方式招标；②投标单位应有安全生产许可证和满足分包工程试验检测资质要求自有试验室；③由中标单位与施工单位双方签订分包合同；④中标单位如不服从施工单位管理导致生产安全事故发生，应承担主要责任。问题：1.针对事件1，写出项目监理机构对部分桩实际承载力达不到设计要求时处理程序。（3分）2.事件1中，施工单位提出工期和费用索赔是否成立?说明理由。（3分）3.事件2中，新材料验收标准应由哪家单位组织专家论证?指出施工单位要求支付新材料专利使用费是否成立并说明理由。（3分）4.事件3中，施工单位提出费用索赔申请中哪些可以获得批准?施工单位是否应采纳建设单位建议?说明理由。（3分）5.指出事件4中招标方案不妥之处，并说明理由。（3分）
某信息系统网络工程建设内容包括网络系统和存储备份系统采购、安装和调试等工作。监理在项目建设过程中，应适时开展对承建单位提交测试计划、测试方案、测试记录和测试报告等测试文档审查工作，同时还要对承建单位测试工作进行抽检。
【问题1】（4分）
在承建单位开展网络测试工作过程中，监理要对关键网络设备和关键部件工作状况、链路冗余能力、Telnet控制测试，以及VLAN TRUNK、VPN、FTP、DHCP等功能测试过程进行监督检查。
请简述在网络设备测试过程中，监理除了对上述已经描述测试过程进行监督检查外，还需要检查其他哪些测试过程？
【问题2】（4分）
请指出网络设备主要测试技术指标，并分别说明这些测试指标作用。
【问题3】（2分）
请列举至少两个网络应用性能测试工具名称。
某地区政府部门建设一个面向公众服务综合性网络应用系统，主要包括机房建设、网络和主机平台建设以及业务应用系统开发，某监理公司承担了该项目全过程监理任务。在工程项目实施过程中，发生了如下事件：
事件1：在监理合同签订后，由于工期紧张，建设单位要求承建单位提前进行应用系统需求调研与分析，同时向监理单位提出对需求调研与分析过程进行质量把关要求。在此情况下，监理单位为满足建设单位要求，决定由参加本项目现场实施工作监理工程师编写监理规划并直接报送建设单位，监理规划部分内容提纲如下：
1. 工程概况
2. 监理范围、内容与目标
3. 工程专业特点
4. 监理依据、程序、措施及制度
5. 监理控制要点目标
6. 监理工具和设施
事件2：机房建设子项工程承建单位按照要求，将其根据下表给定逻辑关系绘制双代号网络计划（如下图所示）提交给监理单位审核。
事件3：在实施监理工作之前，监理单位与建设单位就"进度控制程序"实施原则进行了充分沟通并达成一致意见。确定监理单位采用进度控制工作程序从监理单位审查承建单位工程进度计划开始，然后对计划进行跟踪检查、分析（与计划目标偏离程度），并根据执行情况采取相应措施。
【问题1】（5分）
在事件1中，你认为监理单位在监理规划编制方面是否有不妥之处？为什么？
【问题2】（5分）
如果你是本项目监理工程师，请指出事件2中绘图错误（在以下选项中选择；错选则本题不得分；少选得部分分）。
