OnlineJudge在數據結構教學中的應用

文/向程冠 熊偉程 熊世桓

1 引言

目前，在大數據、計算機科學與與技術、人工智能、物聯網等專業中，計算機程序設計類課程一直處于“飯碗”課程的地位，在所有的程序設計類課程中，數據結構與算法課程是必不可少的，是專業核心課程，學生打下扎實的計算機程序編寫能力基礎是學生學好專業方向課程的重要保障。2018年9月，教育部在《淘汰“水課”打造“金課”教育部要求提升本科教育教學質量》的通知中明確要求“各高校要認真查找課堂建設和管理中存在的突出問題和薄弱環節，嚴管、嚴抓教學秩序，制定整改措施，明確時間節點，落實責任到人，把從嚴管理的規矩立起來、把課堂教學建設強起來、把課堂教學質量提起來。同時，要全面梳理各門課程的教學內容，淘汰‘水課’、打造‘金課’，合理提升學業挑戰度、增加課程難度、拓展課程深度，切實提高課程教學質量”，更關注以學生為中心的教學改革刻不容緩，把數據結構與算法這門課程打造成“金課”也是各高校積極研究的課題。

數據結構是一門實踐性很強的課程，從事教學的教師們一直樂此不疲地進行教學改革，力求尋找一種事半功倍的教學方法來提高學生的程序設計能力，可令人遺憾的是大多數教師僅關注了“教法”的改革，忽略了“學法”改革的重要性。課堂上，主要還是以理論講授為主，不重視學生的代碼實現能力的訓練，雖然在期末的考試中，大多數學生可以順利過關，在優秀以上等級的學生也不在少數，可實踐動手能力較差，大多數學生根本不會算法實現，導致學生成為所謂的計算機“理論”人才。原因在于過分強調老師在教學的的主導地位，忽略了學生的中心地位，把寶貴的課堂變成了學生觀看教師工作和表演的場地，把學生當成了過客，直接導致學生的程序和算法設計能力太差，學生動手能力沒有得到訓練，最終失去了對專業的認同感。這種以教師為中心的傳統教學方法，實驗課形同虛設，教師完全沒有展示算法的實現過程，實驗課的監管不嚴。作業以紙質為主，教師的批閱工作量巨大，期末測評方式以筆試為主，無法評出學生對課程的掌握情況，教師閱卷時也只能看看程序設計題目的大體情況，沒有機器的驗證，也沒有數據集的測試。因此，教學改革需關注學生動力能力的訓練，教師少講，學生多練，變筆試為機試，通過測評系統完成練習、小測、考試。本文根據我校近幾年的教學實際情況，利用OnlineJudge 平臺，要求學生在平臺上至少完成800 道程序題，至少提交1 萬行代碼，程序設計類課程在練習、測試均使用OnlineJudge完成，通過從2014年開始引入OnlineJudge 系統進行教學以來，我校學生的程序設計能力大幅上升，取得顯著的教學效率。

表1：Onlinejudge 測試結果

2 OnlineJudge概述

OnlineJudge 系統（簡稱OJ）主要應用于程序算法設計類的編程比賽中，選手通過瀏覽器和客戶端向測試服務器提交代碼，由測評機調用預先設置好的數據集作為輸入對選手提交的程序代碼進行測評，以考查代碼的正確性、時間復雜度、空間復雜度，如ACM/ICPC（國際大學生程序設計競賽），使用對運行代碼進行測評。一般情況下，Onlinejudge 系統采用兩種計分模式：ACM/ICPC 模式與測試點得分模式。前者必須滿足所有測試點均通過正確性、時間度和空間復雜度的驗證才算正確，成績記錄只有正確和不正確兩種結果；后者按通過的正確性、時間復雜度和空間復雜度驗證的測試點分別給分，并以累加分數作為最終得分，測試數據的設置可選擇不同數據規模，也可選擇設置不同的得分點，以考查選手的程序設計能力。目前，國內比較受歡迎的Onlinejudge系統有北京大學的POJ（PKU JudgeOnline，http://poj.org）、浙江大學的ZOJ（http://acm.zju.edu.cn）、杭州電子科技大學HDUOJ（http://acm.hdu.edu.cn）、貴州師范學院的碼學堂（https://www.maxuetang.cn）等。國外的有TopCoder、Codeforces、AtCoder、SPOJ、USACO 等。

通常Onlinejudge 會在提交程序源碼后，反饋執行結果，大多數的Onlinejudge 提供的反饋結果如表1所示。

3 在數據結構課程中使用OnlineJudge

3.1 用線上可以免費使用的OnlineJudge系統完成學生的平時程序編寫練習

在數據結構課程的日常教學中，如果所有的程序練習題與測試數據集都由任課老師來準備，這將是一個非常龐大的工作量，并且剛參加工作的教師不一定具備出題的能力。因此，在教學中可采用在線的可免費使用的OnlineJudge 系統完成平時訓練，如CCF（中國計算機學會）提供的程序設計在線評測系統（http://oj.noi.cn/oj/），系統中的題目含基本的程序設計算法類題目，教學中可先對題目作出篩選，設計好學生需要完成的題目，要求學生注冊賬號后按時完成老師要求的題目，但由于教師無法通過系統監控到學生的完成情況，教師可在線下檢查學生的完成情況。為了達到良好的訓練效果，線下監督是關鍵，不然學生沒完成或直接復制別人的代碼。要求學生至少完成其中的200 道題目，當學生有一定基礎后，可適當增加難度。待學生有一定基礎后，再選擇如POJ、ZOJ 之類的Onlinejudge 系統，教師根據教學大綱與教學計劃，先作好題目的規劃，再組織學生完成有一定難度的題目。

3.2 自搭OnlineJudge系統完成測試與末考

在數據結構的教學中，如果任課教師需要自己開發一套OnlineJudge 系統，其難度還是比較大的。任課教師可以在網上尋找開源的OnlineJudge 系統進行安裝后使用，比如哈工大的Onlinejudge，Hustoj 等，教師可根據操作手冊下載并完成安裝，通常需要在校園網內搭建即可，一般情況下用幾臺普通的計算機便可實現搭建適用于教學的Onlinejudge 系統。Onlinejudge 系統中最核心的是題庫建設，任課教師可逐步完成自己的題庫，在開始時，可在網上下載已經出好的數據集，熟悉后再進一步自己出題，還可在網上購買別人的試題。建立題庫后及時對學生進行測試，在課堂上利用課前十分鐘完成一道學生練習過的程序題，旨在檢查學生是否在課下完成老師布置的任務，小測完成后無需講解。

在期末考試中變筆試為機考，一方面大大減輕了老師的閱卷工作量，另一位方面更能檢測出學生的程序設計水平，Onlinejudge 系統可當場出分，學生可當場知道自己的分數，能公平客觀地反映出學生的學習情況。

4 結束語

將Onlinejudge 引入數據結構課程的課堂教學中，變傳統的筆試為機試，體現了以學生為中心，加強學生動手能力的訓練，從而提高學生的程序設計能力。經過近幾年的教學實踐，學生的程序設計能力大幅提升，教學效果明顯。