（计算机软件与理论专业论文）基于internet的分布式考试系统.pdf

些! ! ! ! ! 墨堕坌鱼：! 三主暨墨竺y 3 9 一7 57基于i n t e r n e t 的分布式考试系统摘要本文以计算机基本知识与操作技能为研究对象，对国内教学与考核的现状进行较全面的调研，并对与这类考试系统相关的技术进行较全面的分析，在此基础上，应用计算机网络技术、a s p 技术等完成了基于i n t e r a c t 的分布式考试系统。该系统包括：报名系统、试题模板生成系统、自动阅卷系统等。，坛系统突破了传统上计算机辅助测试以客观选择和判断题为主要题型的考t核方式，实现了基于i n t e r n e t 的w o r d 、e x c e l 等操作题的管理、自动阅卷，能够更加准确的在分布式环境下对计算机操作能力进行评价。论文通过整数规划方法对前期的试题模板生成算法进行改进，能够基于试题难度系数等参数对试题模板进行优化，从而优化试题结构；为了提高系统的安全性，本论文将m d 5 加密算法应用于考生登录系统。建立基于i n t e r n e t 的分布式考试系统是计算机辅助教育领域的一个重要方r 刁。面，j 本文研制的系统可以有效地提高考试系统的规范化、自动化及大规模考试的效率，并已经在青岛市相关单位推广使用。关键词：分布式考试、成卷、线性规划、m d 5 加密i n t e r n e t b a s e dd i s t r i b u t e de x a m i n a t i o ns y s t e ma b s t r a c tb a s e du p o nt h er e v i e wo ns t u d i e sf o rt e s tt e c h n i q u e so fc o m p u t e rk n o w l e d g ea n do p e r a t i o n ，ai n t e r n e t b a s e dd i s t r i b u t e de x a m i n a t i o ns y s t e mh a sb e e nd e v e l o p e du s i n gc o m p u t e rn e t w o r kt e c h n i q u e s ，a s pt e c h n i q u e s i ti n c l u d e sr e g i s t e rs y s t e m ，t e s tp a p e rt e m p l a t es y s t e m ，e v a l u a t i o ns y s t e m ，a n ds oo n t h es y s t e mr e a l i z e sa u t o m a t i cm a n a g e m e n ta n de v a l u a t i o nf o ral o to fo p e r a t i n gt y p e so fq u e s t i o n so fw o r d 、e x c e lo nt h ei n t e m e t i tc a nb eu s e dt oj u d g ec o m p u t e ro p e r a t i n gs k i l l so fm a n yu s e r sa tt h es a m et i m el i n e a rp r o g r a m m i n ga l g o r i t h mi su s e dt oo p t i m i z et h et e s tp a p e rt e m p l a t es t r u c t u r eb a s e do nd i f f i c u l tf a c t o r so fd i f f e r e n tq u e s t i o n s t h em d 5a l g o r i t h mi su s e di nr e g i s t e r i n gs u b s y s t e mt oi m p r o v es e c u r i t yo fu s i n gt h es y s t e mc a r le n h a n c ef o r m a l i z a t i o n ，a u t o m a t i o na n de f f i c i e n c yo fal a r g es c a l ei n t e m e t - b a s e de x a m i n a t i o n ，a n di th a sb e e nu s e ds u c c e s s f u l l yi naf e wo r g a n i z a t i o n si nq i n g d a oc i t yk e y w o r d s ：d i s t r i b u t e de x a m i n a t i o n ，c o m p u t e r m a k i n gt e s tp a p e gl i n e a rp r o g r a m m i n g ，m d 5a l g o r i t h m2第一章引言1 1 网络化的计算机辅助教学及计算机辅助测试计算机辅助教学( 简称c a i c o m p u t e ra id e di n s t r u c t i o n ) 是计算机相关技术在教育领域的重要应用。c a i 通过计算机辅助教师执行全部或部分教学任务，模拟教师的教学行为，形成有序的教学信息，向学习者传授知识，训练其技能，达到激发学习者的学习积极性和主动性，提高教学效率和增强教学效果的目的。c a i 系统是在学习者和计算机之间的一系列交互活动中展开教学的。计算机主要以文字、图表、图像、声音、动画、视频等方式呈现各种知识信息，学习者通过显示设备与计算机“会话”，用键盘、鼠标或其它设备输入信息，适时控制计算机的“讲解”速度。这种“人一机”交互活动是由c a i 软件系统控制的 2 6 1 0随着计算机网络技术的发展，计算机辅助教学逐步与计算机局域网、广域网技术融合在一起。即，目前的计算机辅助教学不再是狭域的、单机化的，而已经转变为网络化的计算机辅助教学。这种系统可以依托网络把多种现代化的教学设备有机地结合为一体，实时、高效地采集、加工处理和传输及播放文本、图像、声音等多媒体信息，充分发挥人和设备的潜力与整体效能，达到教学信息资源和设备资源共享，从而丰富教学手段，改善教学环境，给多学科、多课程的教学、科研、管理提供广阔的活动空间，为教学内容、方法与手段的改革，提高教学质量和效益提供重要条件。一l 二l 竺兰二尘l 二二_ 一计算机辅助测验( c a t c o m p u t e ra i d e dt e s t ) 是计算机在测验及其评价中的应用。在计算机辅助教学多样化的环境中，考试一直是评定教与学效果的重要依据，随着计算机辅助测试技术的发展和测试平台的转移，以w e b 为基础的计算机辅助测试环境也渐具规模。这类网络化测验系统具有以下优点：1 ) 提升测试、批阅与评分效率，使教师有较多的时间用在教学内容与方法研究上。2 ) 便于教师搜集教学反馈信息，协助教师分析测试难度等。3 ) 提供一致性的测试准备与试题制作，使测试趋向标准化。4 ) 有利于发展网络多媒体测试模式。5 ) 减少纸上作业，降低人工操作出错的机率。6 ) 易于反复练习，能迅速提供测试结果与正确的导引信息。7 ) 可以不受时空限制。8 ) 易于建立竞争式环境，提高学习动机与成效。1 2 论文的选题背景本论文研究对计算机基本知识和基本操作技能进行测试的基于计算机网络的分布式考试系统。计算机知识已经成为普通高等学校理科、工科、文科、医学等各个专业课程体系的重要公共基础课程。一方面，计算机知识与计算机技术是上述各专业的强有力的工具；另一方面，计算机技术与这些学科深层次的交叉产生了许多以计算为特征的新的学科或研究方向，大大促进了这些传统学：。：。：= ：= 二二二二= 二二二一科的发展。为推动我国高校计算机基础教育，早在8 0 年代中期，我国高校计算机基础教育研究会就提出了在高校非计算机专业进行分层次教学的设想。即，计算机入门和程序设计、微机原理与应用、计算机软件应用基础、结合各专业的计算机专业课程。1 9 9 4 年，国家教育部考试中心推出了面向全社会的“计算机等级考试”；1 9 9 5 年后，国家教育部高教司相继组织制订了普通高校非计算机专业计算机基础课程教学大纲，并将课程分为三个层次：计算机文化基础、计算机应用基础、计算机技术基础。1 9 9 6 年6 月，山东省教育厅组织了首次大学生计算机文化基础统考，并从教学大纲、教材建设、考试系统研制开发等多个方面进行推动，取得了良好的效果 z 6 l o于此同时，国内众多省份和城市对干部、公务员和专业技术人员提出了对计算机知识与应用技能培训和考核的具体要求，其内容与普通高校对非计算机专业学生学习的计算机文化知识基本相同。由于计算机技术发展迅速，计算机知识更新的周期越来越短，给教学大纲的制订、教材的编写、考试的组织等带来了很大困难。自9 0 年代以来，相关学习内容实现了由o o s 向w i n d o w s 操作平台的过度，同时，正在由单机系统向局域网、互联网( i n t e r n e t ) 过度。除最基本的计算机知识外，需要学习的软件系统的操作方式、软件工具及相关技术在不断的更二_ = = = 二_ l = i 二_ = = _ 二一新，考核的内容和模式也随之不断变化。计算机应用基础重在操作，其学习和培训的主要学时分配在操作技能的实验环节。这样，再采用传统的纸面理论考核的方式已不能胜任，研究和开发能有效考核学员的真实操作水平的考试软件系统成为摆在计算机基础教育工作者面前的一个艰巨任务。相关考试有如下特点1 ) 通常每次考试范围较大，一般是分布在一个或多个校区的一个年级的学生( 如，学校组织期末考试) ：或者是分布在一个城市的多个考点，且每个考点有多个考场( 如，某个城市组织的干部计算机技能考试) ；也可能是分布在多个学校的多个考场( 如，省内范围的普通高校统考) 。2 ) 由于计算机资源的限制等问题，通常每个考点需连续组织多场次考试。3 ) 考试组织比较复杂，通常包括：报名、发准考证、分配考场、考试过程组织、阅卷、成绩统计、发合格证等多个环节4 ) 现场考试的环境应与学习和实际使用的环境一致。5 ) 考试的内容和考试题型不断更新。随着互联网时代的到来，互联网为信息和技术的交流提供更大、更广阔的空间，使信息的地域差别逐渐消失。互联网已经成为一种新的社会媒介，也为计算机辅助教学和计算机辅助测试的发展提供了广阔的空间，从而产生了飞速发展的计算机远程教学，并且参加远程教育的学生与教师也越来越多，远程教育支撑平台的作用也越来越重要。远程教育支撑平台就是用i n t e r n e t 技术对网络上的各种教育资源进行管理和使用，对参加远程教育的教师和学生进行管理的一个系统。它包括各种硬件资源、服务器工作平台、w e b 服务器、数据库服务器、w e b 服务器与数据库服务器接口技术以及各种资源和信息的存储组织等。在这个背景下，根据普通高校计算机知识与操作技能考试的特点，以对计算机基础知识和计算机基本操作进行考核为目的，结合上面所介绍的网络化辅助教学及计算机辅助测试技术，本文提出了基于i n t e r n e t 的分布式考试系统，1 3 国内外现状和发展趋势计算机辅助教学与计算机辅助测试系统是目前国内外教育界研究的热点。这些系统的开发依赖于各个学科的专业知识、计算机软件技术、计算机网络技术等，其中，各个专业的c a i 成果已经比较丰富，但是，由于不同范围的考试组织及不同类型题目自动阅卷的困难，使得c a t 系统的研制明显滞后。随着基于i n t e r n e t 的计算机远程教学的逐步普及，新的教学形式对考试手段提出了新的要求，也为网络环境下的计算机考试系统的研制提供了可行性。近年来，普通高校和中等专业技术学校纷纷建立自己的校园网，并且连接到i n t e r n e t 。这样，基于i n t e r n e t 平台的全自动化、分布式、功能高度集成的考试网络系统的研制成为必然。国外率先成功采用远程网络的系统主要有英语的t o e f l 、g r e 考试，及微软、思科的水平认证考试，及众多大学自行研制的课程学习测试系统。这些系统主要以选择、判断等的客观题的形式考核。国内的西安交通大学、湖南大学、重庆大学、西北大学等也相继基于i n t e r n e t 网络开发了针对客观题的网上测试系统。但是，对于大量的课程，上述形式的考试很难考察学员的实际动手能力，必须逐步开发能够真实反映学生操作技能的软件系统( 2 5 1o1 4 本文工作概述本论文研究基于i n t e r n e t 的分布式考试系统的设计与实现，该系统用于对计算机基础文化知识和计算机基本操作进行考核。主要工作如下：i ) 完成整个考试系统实施模式和详细设计。包括：报名系统、试题模板生成系统、考试环境生成系统、自动阅卷系统等。2 ) 针对考试系统中动态成卷算法进行研究，对题目的各项考核系数建立线性整数规划模型，采用优化算法，求出最佳的试题组合，从而达到最佳的考核效果。3 ) 探讨系统的安全性问题，将m d 5 加密算法应用于考试系统中。第二章基于i n t e r n e t 的分布式考试系统的分析2 1 对基于i n t e r n e t 的分布式考试系统的需求近年来，i n t e r n e t 网络及以其为基础的i n t r a n e t e x t r a n e t 网络飞速发展，各大、中、小学的教学平台、企业管理信息系统平台及政府办公自动化系统平台等均已采用该网络技术，对学生、干部及专业技术人员进行计算机普及教育的内容也拓展到与该技术相关的内容，随之而来的问题是，这类知识大范围考试的形式也必须进行改变。这些改变不仅局限在技术上，更重要的是会对未来考试的组织模式产生深远的影响。为此，提出研制基于i n t e r n e t i n t r a n e t e x t r a n e t 的完全分布式、远程计算机无纸化考试网络系统。2 2 基于i n t e r n e t 的分布式考试系统的网络平台本论文的分布式考试系统的网络平台是基于i n t e r n e t 的，该系统是一个基于w e b 环境的集题库管理、试卷生成、自动阅卷、考生答卷管理于体的分布式无纸化考试系统。系统由两大部分组成：软件系统、题库及管理系统。其中，题库包含选择题、判断题、填空题、汉字输入题、w o r d 操作题、w o r d 制表题、e x c e l 操作题等七类试题；试题按类别进行组织。在软件上采用了o l e 技术、a c t i v e x 技术等，同时，提供了有效的系统扩充方法，在考试过程中，可以进行多场次考试和灵活多变的考试环境设置。为了更好的满足题库管理、试卷生成、考生答卷管理、远程试题与答案传送、报名与证件打印于一体的集成化分布式无纸化考试系统的要求，在系统的设计过程中，对系统的设计方案与实施技术进行了多次的讨论，最终确定为现行系统。在制定开发策略时，首要考虑是系统规划。因为是基于i n t e r n e t 环境的考试系统，我们重点考虑了以服务器为考试中心的“集中式”方案；“集中式”是将整个系统集中存放在w e b 服务器上，考生登录考试系统主页面，所有的操作内容和操作结果均存放在服务器上，这种方案具有易于管理、实现简单等特点。系统扩充策略意指可以随时加入适当的模块来扩展系统的功能，而无须变更现有的系统系统运行模式如下：图2 - 1 系统运行模式! ：! ：2 ：二_ 二= = - 一2 3 基于i n t e l n e t 的分布式考试系统的相关软件技术2 3 1 系统主体采用a s p 技术a s p 全称m i c r o s o f ta c t i v es e r v e rp a g e s ，是一套微软开发的服务器端脚本环境，a s p 内含于i i s3 0 和4 0 之中，通过a s p 我们可以结合h t m l 网页、a s p 指令和a c t i v e x 元件建立动态、交互且高效的w e b 服务器应用程序。有了a s p 就不必担心客户的浏览器是否能运行你所编写的代码，因为所有的程序都将在服务器端执行，包括所有嵌在普通h t m l 中的脚本程序。当程序执行完毕后，服务器仅将执行的结果返回给客户浏览器，这样也就减轻了客户端浏览器的负担，大大提高了交互的速度。以下罗列了a c t i v es e r v e r p a g e s 所独具的一些特点：1 ) 使用v b s c r i p t 、j s c r i p t 等简单易懂的脚本语言，结合h t m l 代码，即可快速地完成网站的应用程序。2 ) 无须编译，容易编写，可在服务器端直接执行。3 ) 使用普通的文本编辑器，如w i n d o w s 的记事本，即可进行编辑设计。4 ) 与浏览器无关( b r o w s e ri n d e p e n d e n c e ) ，用户端只要使用可执行h t m l 码的浏览器，即可浏览a c t i v es e r v e r p a g e s 所设计的网页内容。a c t i v es e r v e r p a g e s所使用的脚本语言( v b s c r i p t 、j s c r i p t ) 均在w e b 服务器端执行，用户端的浏览器不需要能够执行这些脚本语言。5 ) a c t i v es e r v e rp a g e s 能与任何a c t i v e xs c r i p t i n g 语言相容。除了可使用v b s c r i p t 或j s c r i p t 语言来设计外，还通过p l u g - i n 的方式，使用由第三方所提供的其他脚本语言，譬如r e x x 、p e r l 、t c l 等。脚本引擎是处理脚本程序的c o m ( c o m p o n e n to b j e c tm o d e l ) 构件。61a c t i v es e r v e rp a g e s 的源程序，不会被传到客户浏览器，因而可以避免所写的源程序被他人剽窃，也提高了程序的安全性。7 ) 可使用服务器端的脚本来产生客户端的脚本。8 ) 面向对象( o b j e c t o r i e n t e d ) 。9 ) a c t i v e xs e r v e rc o m p o n e n t s ( a c t i v e x 服务器构件) 具有无限可扩充性。可以使用v i s u a lb a s i c 、j a v a 、v i s u a lc + + 、c o b o l 等编程语言来编写你所需要的a c t i v e xs e r v e rc o m p o n e n t 。a s p 所需的环境如下：m i c r o s o f ti n t e r n e ti n f o r m a t i o ns e r v e rv e r s i o n3 0 4 0o nw i n d o w sn ts e r v e rm i c r o s o f tp e e rw e bs e r v i c e sv e r s i o n3 0o nw i n d o w sn tw o r k s t a t i o nm i c r o s o f ip e r s o n a lw e bs e r v e ro nw i n d o w s9 5 9 8正如前文所述，与般的程序不同，a s p 程序无须编译，a s p 程序的控制部份是使用v b s c r i p t 、j s c r i p t 等脚本语言来设计的，当执行a s p 程序时，脚本程序将一整套命令发送给脚本解释器，由脚本解释器进行翻译并将其转换成服务器所能执行的命令。当然，同其他编程语言一样，a s p 程序的编写也遵循一定的规则。当安装a s p 时，系统提供了两种脚本语言：v b s r c i p t 和j s c r i p t ，而v b s c r i p t 则被作为系统默认的脚本语言。2 3 2 成卷和阅卷中的o l e a c t i v e x 技术o l e 对象链接和嵌入( o b j e c tl i n k i n ga n de m b e d d i n g ) 是m i c r o s o f t 公司同计算机界合作并发展起来的产品规范，目前已发展成为m i c r o s o f t 公司面向对象策略的基石。许多大的w i n d o w s 应用程序都是围绕它设计的。从用户角度讲，o l e是一种能使它们共享不同应用程序信息资源的技术，用户能够构造声、文、图、像、影于一体的复合文档，可以很容易地集成应用程序。从开发商的角度看，o l e 是一个可解决许多难题的技术，w i n d o w s 开发商面临的最大的难题之一是让应用程序之间的相互通信，在过去，没有一个工业标准，o l e 所做的正是标准化这些协议。组件对象模型c o m ( c o m p o n e n to b j e c tm o d e l ) 是o l e 的基础，它不但提供了一个实现o l e 的框架，还为一整类新软件提出了- - f o 全新的设计思想。它是一种面向对象的结构，定义了一套对象间相互通信的标准方式，规定了如何使一些小的、定义良好的软件模块在系统中共享。依照这种结构，可以将若干组件组合起来，以建立更大的和更复杂的系统。分布式组件对象模型d c o m ( d i s t r i b u t e dc o m p o n e n to b j e c tm o d e l ) 是c o m的一个扩展，它使得在不同的计算机上运行的o l e 应用程序可以通过网络相互通信，形成分布式的o l e 应用程序，支持远程自动化。链接和嵌套是o l e 的基本功能，是实现并扩展动态数据交换( d d e ) 的一种技术。应用这种技术，可以把不同工具产生的图表、文件和图片组合到一个连续完整的文件中去。o l e 比d d e 更进了一步，d d e 仅仅传递消息，而通过o l e传递的信息的表达形式和原始应用程序中的一模一样。a c t i v e x 是一个m i c r o s o f t 的术语，它指的是一组包括控件，d l l 和a c t i v e x文档的组件，通常是以动态链接库的形式存在，因此必须在一个叫容器的独立执行软件中运行。这样的容器包括a u t h e r w a r e 、d e l p h i 、v i s u a lb a s i c 、v i s u a lc + 、i n t e r a c te x p l o r e r 、a c c e s s 等。a c t i v e x 控件数据输入和函数功能执行都必须通过容器，因此a c t i v e x 控件和容器都必须支持特定的接口协议。根据m i c r o s o f t 规范，a c t i v e x 控件应具备：i ) n 性和方法：a c t i v e x 控件必须提供属性的名称、方法的名称及参数，通过这项机制，容器可以存取和改变a c t i v e x 控件的属性参数。2 ) 事件：a c t i v e x 控件由这项机制通知容器在a c t i v e x 控件中发生的事件，比如属性参数的改变，用户按下鼠标键等。3 ) 存储：容器由这项机制通知a c t i v e x 控件存储和提取有关信息数据等。a c f i v e x 控件只要在w i n d o w s 的r e g i s t r y 数据库中注册，就可以像其他w i n d o w s 应用程序一样发挥各自的功能。a c t i v e x 控件是一个模块化的灵活对象，如果某个应用程序或网页需要增加项特殊的功能，无须重写整个程序，只要灵活地插入一个具有此项功能的a c t i v e x 控件即可实现。a c t i v e x 的优势还在于它的动态可交互性，用户可以动态地在使用过程中，通过改变它的属性和参数，在应用程序中实现自己的特殊要求。第三章基于i n t e r n e t 的分布式考试系统设计3 1 分布式考试系统的业务流程考生在从报名开始整个考试系统的业务流程如下图所示卜锄记i上f获得霉喜霉号：上上上图3 - 1 业务流程图考生首先登录报名系统，输入自己的资料姓名、性别、单位等，获得自己的准考证号，考试号，其中考试号是后面考试过程获得试卷的依据，然后登录进考试系统进行考试，考试完毕查询成绩。3 2 分布式考试系统的功能模块系统包括报名系统、成卷系统、阅卷系统、查询系统等几个主要功能模块，对其功能及实现分别阐述如下：( 1 ) 报名系统：考生首先登录报名系统后，完成注册，注册自己的各项数据资料，系统验证，看是否属于考生范围，然后返回考生唯一的准考证号码和考试号码。在服务器端数据库中存储考生的各项资料。( 2 ) 成卷系统：成卷系统的功能是出具一份满足考试要求的试卷，针对成卷系统有专门的出题策略。整个考试系统考核的题型包括选择题、判断题、填空题、汉字输入题、w o r d 操作题、w o r d 制表题、e x c e l 操作题等七类试题；试题按类别进行组织。( 3 ) 阅卷系统：对于不同的考试题型，采取不同的阅卷方式，选择题、判断题、填空题、汉字输入题在考生提交答案以后，在服务器端的a s p 相应文件中即可完成，并将成绩插入数据库中，而操作题的阅卷则在考生将答案上传到服务器后，调用可执行程序完成，并将成绩插入数据库中。( 4 ) 查询系统：考生输入自己的准考证号，系统根据准考证号码，从后台数据库中查询出考生的成绩，并以h t m l 格式的文件发送到考生浏览器端。3 3 分布式考试系统的详细设计从逻辑角度看，整个考试系统其核心组成部分关系，如下图所示图3 - 2 分布式考试系统核心组成部分关系图下面沿着考生参加考试所经历的流程，阐述考试系统的具体设计，首先开始考生报名，考生在经过身份验证以后，进入报名系统，系统给出考生在后面考试过程中所用到的准考证号、考试号，然后考生开始考试，考生输入自己的准考证号和考试号，系统调出该考生的考卷，考生开始答题，并将答案上传，考试结束时，系统给出成绩的查询日期和查询方法，最后，考生在指定时间，查询成绩。系统流程如图3 3 所示：考试中心服务器图3 - 3 系统详细设计流程图7第四章基于i n t 。，n 。t 的分布式考试系统设计和实现中的关键技术4 1 成卷理论的研究与设计思想基于试题库的成卷过程，可以看成是将一组命题要求转化为寻找满足该要求的，题库中试题组成子集的过程，如图4 - l 所示命题要求可分为四类图4 - 1 成卷过程简图第一类只需给出有关考试的宏观要求，如课程名、考试目的、考试范围、考生对象、答卷时间等，其余信息由系统自动识别。第二类不但需要给出第一类命题要求的基本信息，而且还应给出部分相关课程考试的量化要求信息，如考试范围，难度系数等。第三类要求给出相关课程考试的全部量化信息。第四类需要给出考试的各道试题的详细指标要求值。基本成卷模式包括了对难度、内容、题型、教学要求等的规定。这些基本模式是成卷的依据。基本成卷模式应包括以下几个内容难度一时间分布曲线难度一一分数分布曲线题类一分数分布曲线题型一一分数分布曲线教学要求度一分数分布曲线在实际考试中，各门课依据考核内容和考核目的不同，基本成卷模式中各个内容的指标不一样。指标是指用来描述每一道试题特征的参数，比如考核内容、分值等。本论文所研制的考试系统涉及考核内容、难度系数、答题时间等对试题描述的参数。在此基础上，根据对题库中试题描述的知识库即试题考核性能指标体系，还可以增加考核指标，进而在优化模型中。增加约束条件，达到更好的考核效果。成卷模式最终必须通过具体的试题来反映，以下探讨如何运用定的搜索策略，即出题策略，从试题库中挑选试题，并满足多种约束要求。成卷系统可由下图表示：图4 - 2 成卷系统框图其中，推理机制是根据人一机接口提出的参数，按照一定的出题策略，搜索试题；试题指标体系是指试题的各种特性的量化参数。在论文中，试题指标体系的作用体现在试题数据库的结构中。试题数据库用于存储试题，人一机接口提供人一机界面，确定考核参数。4 2 对已有成卷算法的比较通过对各种考试系统的考查，在成卷技术上列出以下2 种有代表性的算法( 1 ) 向量贴近算法“”：采用“贴近成卷算法。该算法的任务是根据考试模板中所定义的参数从题库中找出合适的试题，这样就有一个度量问题，为此本文引入了线性代数中反映两向量相近程度的方法作为“贴近，的度量。设有一向量为v = v ，v ：，v 。 ，另有一向量为g = g - ，g 一g n ) 。其中，v ，v 一v n 和g ，g 一g 。为向量在x 。，x ：，x 方向的分量，向量v 和g 的相近程度可用v 和g 之间的夹角的余弦来反映。以此为基础的“贴近”成卷算法如下：1 ) 根据试题模板中每题的参数构成此题的向量：v 2i v i ，v z ，v n a2 ) 从题库中随机抽取一题，同时构成此题的向量：g 2 g i ，g 一g n 。3 ) 计算v 和g 的夹角余弦。4 ) 若满足要求则取下一题，并转i ) ；否则，转2 ) 。( 2 ) 随机线性规则算法1 ：设总分为g ，每种题型题量为a 1 k ，第i种题型分数难度分别为b i ，c i ，j ，则应满足：ka 门* b d - - - g ，c i j 一d m j c i ，j + 且内容比例符合要求。算法如下：1 ) 参数设置，初始化；2 ) 计算当前需出试题的总分：g ；3 ) 产生 1 g 的随机数；4 ) 计算当前需出试题中各部分剩余比例分数；5 ) 若此随机数落在哪个比例区间，则在此内容出试题；6 ) 选取需出题型( 按所需分数，每小题总分大小产生随机数按概率选) ：7 ) 随机抽题，g = g7 一r ( r 为当前题的分数) ：8 ) 屏蔽该题并将所有与该题同知识点题目作标记( 被屏蔽的题目在本次组卷中不再选用，被作标记的题目在本份试卷中亦不再选用，但下一次可用( 在一次组多份试卷的情况下) ) ：9 ) 判断g 是否大于o ，若是返回3 ) 执行，否则往下执行；从以上两种算法中，我们可以看出，上面两种算法都是在给定的考核参数下，到题库中去寻找试题，然后经过计算看是否满足参数，不满足再继续寻找，在这些成卷策略下，系统能够找到满足给定参数的试题组成试卷，但不能满足是最优的试题组合，为此，本论文提出t 1 1 2 ，f & 算法成卷技术，它将试题的多种性能参数考虑进去，找出在满足给定考试条件下的最佳试题组合，组成试卷。4 3 优化算法成卷技术4 3 1 优化思想概述及线性整数规划“1 。“1( 1 ) 优化问题的基本概念随着生产、经济、技术的发展，工程技术、管理人员在实际工作中，经常面临这样的一类问题：工程设计中怎样选择参数，使得设计既满足要求又能降低成本：资源分配中，怎样的分配方案既能满足各方面的基本要求，又能获得好的经济效益等等，这一类问题的共同特点，就是在所有可能方案中，选出最合理的，达到事先规定的最优目标的方案，这个方案就是最优方案，寻找最优方案的方法称为最优化方法。由于优化是要在一切可能的方案中寻找最优的方案，往往要进行大量的计算，电子计算机的出现，大大促进了数学最优化方法的迅速发展。线性规划和非线性规划是属于数学最优化方法。用线性规划和非线性规划来求解最优化问题，首先要以数学的形式来描述所要求解的问题，即建立数学模型。在建立数学模型时，一方面希望建立一个完善的模型，另一方面又希望使建立的模型容易处理和求解。所建立的数学模型如能较好的表示真实问题，则模型的解也将是真实问题的最优解，反之一个不好的数学模型，即使求解很精确，其解也不会是真实问题的解。同时，如果所建立的数学模型无法求解，那么，再好的数学模型也是没有用的。因此，必须所建立的数学模型能在较好的反映真实问题的前提下，使其便于处理。( 2 ) 优化问题的数学模型一个优化问题的提出，要包括三个方面的正确确定，即变量、约束和目标函数。其中，1 ) 变量在对某一优化问题求解时，有些基本参数是要在求解过程中选定的，我们把这些基本参数称为变量。变量一般是一些相互独立的基本参数，一组变量的数值表示了优化问题的一种方案。：= 二二= ：= l - 二二= = - - 一即n 个变量z ，z ：，_ ，_ 可以按一定次序排列成数组，表示一个n 维向量x =x ，是n 维向量x 的第i 个分量，式中t 为转置符。以n 个变量为坐标轴组成的实空间，被称为n 维实欧氏空间，用r “表示。n 维空间中的一点就代表了一个方案。n 维空间是由r 1 个变量确定的方案的集合，用x r “表示。空间中任一方案k ，被认为是从空间原点出发的向量k 。2 ) 约束上面所提到的变量不仅在规定范围内取值，且各变量之间还必须满足一定的关系，所以说n 维空间是所有方案的集合，并不完全被实际问题所接受。由实际问题所引起的对变量取值的限制，称为约束。约束一般可以表示为变量的不等式约束和等式约束。即g j ( ) = g j ( x l ，x 2 ，石3 x 。) 0( 4 - 2 )或者g j ( z ) = 毋( x i ，z 2 ，玛，_ 。) 0( 4 3 )或者 ，( x ) ： ，( x ，x 2 ，_ x 。) = o( 4 4 )式中l 和m 分别表示不等式约束和等式约束的条件数。在求解优化问题过程中，一个不等式约束条件g ( x ) o ，或g ( x ) = o 可将n维空间划分为两部分：一部分满足约束条件，g ( x ) o ，：另一部分不满足约束条件，如g ( x ) ，o ，：这两部分的分界面称为约束面，g ( z ) = o ，如下图所示：g ( z ) = o甙抑 h j ( h i 0 ) 就化为y o。如果变量的符号不受限制，则可引进两个新的变量y 和，并以生! ! 生竺! ! 堕坌塑查重堕墨笙一：y ：一y ，代入问题的目标函数和约束条件中消去x 。，同时在约束条件中增加y i o ，y ：o 两个约束条件。将线性规划的标准形用矩阵表示为r a i nz = c 。xs t 爿x = bx 0其中c = ( c 1 ，c 2 ，c 。) 7 ，x = ( 工l ，z 2 ，z 。) 7爿= ( 吼) 。，b = ( 6 ，b 2 ，b )再把上面的形式写成表格形式下面对以上表格进行如下运算a ) 底线以上部分进行行交换。b ) 底线以上某一行乘一非零常数。c ) 底线以上的行进行倍加运算。d ) 把底线以上行乘常数后加至底行( 包括右下端) 上。当表格具有如下特点：1 ) 中心部位具有单位子块。( 4 - 1 2 )墨王! ! 塑! ! 生堕坌塑苎耋堕墨堕一2 ) 右列元素非负。3 ) 底行相应于单位子块的位置为0 。4 ) 底行其他元素非负。则从表格中立即可以读出线性规划的最优解和最优值。最优解的读法为，单位子块中l 所对应的变量取相应右列的植，不在单位子块位置中的变量取值o ，而右下端元素变号即为最优解。对表格进行变换的过程中，如果表已经具备1 ) ，2 ) ，3 ) 三个特点，而在第4 ) 个特点不具备的条件下，采用单纯形法得到第4 )个特点的具体步骤如下：前提：设当前的表格已具备第1 ) ，2 ) ，3 ) 三个特点，设般为a l l口l2 d 1 hb l-a m ia m 21 “n n n6 。c ic 2 c 一五步骤：1 ) 从底行负元素中任选一个，设为c ，这一步称为选择进基变量。2 ) 从所选元素对应列( x 列) 底线以上的正元素中按下列规则选定一元素啪且满足鲁呻鼬。 o 垄主! ! 竺竺竺塑坌塑茎耋堕墨堕一一3 ) 利用初等行变换及倍加至底行的运算，把变为l ，该列的其他元素( 包括底行相应的元素) 变为0 ，这一步运算称为旋转运算。4 ) 若底行运算均非负，算法终止，否则回1 ) 。求出线性规划的最优解之后，在此基础上，利用分支定乔法求解线性整数规划的最优解，步骤如下：1 ) 求出线性规划的最优解之后，查看所求出的最优解，如果不为整数解，用采取分支的办法，将它排除掉，即任意利用一个取非整数的变量把可行域分成两部分，也就是分为两支，并把解线性规划得到的相应的最优值作为线性整数规划的最优值的下界。例如若最优解为x = 1 0 3 ，x ：= 4 3 ，z = 2 6 3 。则我们利用x ，= 1 0 3 把可行域分眠阡3 秕阿的两部分这样既把x = 1 0 3 ，x ：= 4 3 这个点排除了，又保证不会排除所要求的线性整数规划的最优点。把z = 2 6 1 3 作为整数规划最优值的下界。2 ) 考虑可行域被分成的两部分中，其中的一部分，即其中的一支，和约束方程组成新的线性规划模型，然后再对其用步的算法求出最优解。3 ) 考察求出的最优解，如果仍不为整数，重复1 ) ，2 ) 的步骤，并且考查2 )步中没有考虑的l 步中划分的另一支。4 ) 所有分支考察完毕，所得到的最好的整数解，即为原线性整数规划的最优解。兰王望竺竺璺竺坌鱼茎耋堕墨堑一以上几步中注意的几点在考查分支的过程中，一个分支被考查完毕的标志是下面条件之一1 ) 不考虑整数约束后的线性规划无解。2 ) 不考虑整数约束后的线性规划的最优解不是整数。3 ) 不考虑整数约束后的线性规划的最优值超过原问题最优值的上界，这说明原问题的最优值肯定整个问题求解结束的标志是下列条件之一1 ) 各个分支均己查清，则所得整数解中最好者即为原问题的最优解。2 ) 某个分支中，得到整数解且相应目标函数等于原问题最优值之下界，则该整数解为原问题的最优解。整个分支定界法的求解过程如下图兰主! ! 竺竺璺竺坌塑壅耋兰墨竺一无解图4 4 分支定界法求解过程4 3 2 数学规划模型的建立及求解o无解成卷系统是计算机考试系统的核心部分，基于试题库的成卷过程，可以看成是将一组命题要求转化为寻找满足该组要求的题库中试题组成的试题子集过程。苎士! ! 竺竺曼塑坌塑茎耋兰墨堑一成卷系统的核心部分为是出题策略。服务器端试题库中的试题具有很多属性，如难度系数、预计答题时间、考核内容、分值等。其中，比较重要的是考虑难度系数和答题时问，确定方法如下。日，“，n ，棚。代表n 个难度系数，即n 个难度级别；b ，b 2 ，6 ，6 。代表n 个不同的答题时间；z ，x 2x ，x 。代表每个难度级别中所抽取试题数目；h u m l ，r l u m 2 ，t l u m 3 n u m 。代表题库中存储的每个难度级别的试题数目。假如用户对一道题型( 比如选择题) 提出的难度系数为a ，答题时间为b ，根据匕述的线性规划方法建立数学模型如下，r a i nz = x t 十x 2 + x 3 + ”+ x h( a 1 一a ) x l + ( 口2 一a ) x 2 + ( 口3 一a ) x 3 + ( d 。一a ) x 。= 0( b 1 一b ) x 1 + ( b 2 一b ) x 2 + ( b 3 一b ) x 3 + ( 6 。一b ) x 。= ox l + x 2 + z 3 + x 4 + x 。l0 。l n u m l0 0 2 r u r n 20 x 。r b m 。上述线性规划模型的愀m i n z = x l + x 2 + x 3 + + x 。，其意义为，在满足用户的难度级别、答题时间等命题要求的情况下，寻找最优解，使得既满足考核要求，又使题目数量最少。制定出题策略的依据为以上模型的最优解苎王! ! 堡竺生塑坌塑壅耋堕墨竺一。：，x ，根据上面所讨论的分支定界法所实现的算法实例如下。假定一道题型有5 个难度级别，即5 个难度系数，分别为2 ，3 ，6 ，5 ，8 ，即，令口。：2 ，口，= 3 ，吼= 6 ，口。= 5 ，= 8 它们所对应的答题时间分别为3 ，2 ，l ，4 ，5 ，单位为分钟，即令岛= 3 ，b 2 = 2 ，b 3 = 1 ，b 。= 4 ，b ，= 5 ，用户给出的总难度系数为3 ，即a = 3 ，答题时间为2 分钟，即1 3 = 2 ，t u m l ，h u m 2 ，h u m 3 ，n u m 4 ，n u m 5 的值分别为5 ，3 ，3 ，4 ，5 ，我们得到如下的规划：r a i nz = z l + x 2 + x 3 + x 4 + x 5一x l + 3 x 3 + 2 x 4 + 5 x 5 = 0 x i x 3 + 2 x 4 十3 x s = 0 x l + x 2 + x 3 + x 4 + x 5 10 x 50 x ，30sx ，30 x 40sx 。5调用根据分支定界方法编制程序所计算出的一组最优解为x l = 0 ，x 2 = 1 ，托= o ，x 4 = 0 ，墨= 0目标函数值为：z = 1其意义为：在用户要求总难度系数为3 ，答题时间为2 分钟的情况下，出题策略应为选取以上第二个难度系数的试题一道。些主! ! ! ! ! ! 生堕坌查苎耋堕墨笙4 3 3 算法在系统中的具体实现( i ) 系统的数据库内容在服务器端的m ss q ls e r v e r 数据库中，存储有很多张表，按功能划分，有存储考生档案信息的表格，有用于系统成卷的表格，即存储成卷信息的表格，有存储试题的表格，还有存储考生成绩的表格。与成卷密切相关的内容除了存储的试题外，还有考核性能参数表、试卷模板表、试题模板表等，我们先假设本次考试中有三种题型：选择题、判断题、填空题。针对成卷功能，数据库中用于存储成卷信息的表格如下：考核性能参数表题考难答难难难难难难该该型核度题度度度度度度题题内级时级级级级级级型型容别间别别别别别别题题目目l2ni2n总总题题题苴盥堕数分目目目题题题量数数数数分分分黉量量值值值堇王生兰竺! ! 塑坌塑茎耋苎墨兰l 一试卷模板表i d教选选选填填填判判判题师择择择空空空断断断目姓题题题题题题题题题合名难难难难难难难难难计度度度度度度度度度数级级级级级级级级级量别别别别别别别别别l2nl2ni2n题题题题题题题题题目目目目数目目目目目数数数数数数数数量量量量量量量量量试题模板表教i d选选选判判判填填填师择择择断断断空空空姓题题题题题题题题题名难难难难难难难难难度度度度度度度度度l2nl2ni2n的的的的的的的的的题题题题题题题题题号号号号号号号号号3 7兰王! ! 堡翌坐竺坌塑壅耋堕墨堕一一试题表圈4 - 5 数据库内窬从上面的数据库结构中，可以看到在试卷模板表、试题模板表中，都有i d这个属性，这个属性是和教师相对应的，每个出题老师有一个i d