康長青　朱麗娟　胡春陽　吳中博　王敏

摘? 要： 綜合性實驗案例是提升實踐教學(xué)質(zhì)量的關(guān)鍵環(huán)節(jié)。針對現(xiàn)有的數(shù)據(jù)結(jié)構(gòu)算法時空分析實驗安排缺失或綜合性不強的現(xiàn)狀，提出融合知識、能力、素質(zhì)的綜合性實驗設(shè)計模式。通過課前資料查詢，課上對比分析和課后優(yōu)化拓展三個階段，介紹了綜合性實驗案例的設(shè)計框架和能力素質(zhì)目標(biāo)。詳細介紹了結(jié)構(gòu)體和函數(shù)、空間復(fù)雜度、時間復(fù)雜度和系統(tǒng)優(yōu)化四個功能模塊的階段實驗?zāi)繕?biāo)、分級遞進內(nèi)容和教學(xué)策略。給出了實驗的考核方案和教學(xué)效果分析。該教學(xué)模式有助于達成一流本科課程目標(biāo)，可供同行借鑒和參考。

關(guān)鍵詞： 綜合性實驗; 數(shù)據(jù)結(jié)構(gòu); 設(shè)計框架; 對比分析; 教學(xué)策略

中圖分類號：G642? ? ? ? ? 文獻標(biāo)識碼：A? ? ?文章編號：1006-8228（2022）04-83-03

Comprehensive experimental case design in the course of data structure

Kang Changqing Zhu Lijuan Hu Chunyang Wu Zhongbo Wang Min

（1. School of Computer Engineering， Hubei University of Arts and Science， Xiangyang， Hubei 441053， China;

2. School of Physics and Electronic Engineering， Hubei University of Arts and Science）

Abstract： Comprehensive experimental cases have an important impact on improving teaching quality. Taking algorithm time complexity and space complexity of data structure as examples，the existing algorithms experiments have the disadvantages of lack of arrangement or lack of comprehensiveness. A comprehensive experimental design model that integrates knowledge， ability and quality was proposed to solve the above problems. Firstly， the design framework and goals of comprehensive experimental cases are introduced through three stages of pre-class information search， comparative analysis in class， and optimization and expansion after class. Then the stage experiment objectives， graded progressive content and teaching strategies of the four functional modules of structure and function， space complexity， time complexity and system optimization were presented in detail. Finally， the evaluation method of the experiment and the analysis of the teaching effect were given. The proposed model is beneficial to achieving the goals of first-class undergraduate courses and has some reference significance and promotion value.

Key words： comprehensive experiment; data structure; design framework; comparative analysis; teaching strategies

0 引言

教育部《關(guān)于一流本科課程建設(shè)的實施意見》中要求確立學(xué)生中心、產(chǎn)出導(dǎo)向、持續(xù)改進的理念，提升課程的高階性，突出課程的創(chuàng)新性，增加課程的挑戰(zhàn)度[1]。在此背景下，地方應(yīng)用型本科院校如何進行專業(yè)核心課程的改革和建設(shè)[2]，對人才培養(yǎng)質(zhì)量的提高起著舉足輕重的作用。

數(shù)據(jù)結(jié)構(gòu)作為計算機類專業(yè)課程體系中的核心課程，理應(yīng)率先進行高階性、創(chuàng)新性和挑戰(zhàn)性改革，努力創(chuàng)建省級一流本科課程。

掌握算法的時間分析和空間分析的技術(shù)是數(shù)據(jù)結(jié)構(gòu)課程的教學(xué)目標(biāo)之一[3，4]，經(jīng)常采用傳統(tǒng)的課堂講授來達成目標(biāo)，存在學(xué)生印象不深，方法未學(xué)會，短時間不能掌握等問題，而現(xiàn)有的算法時空分析實驗要么安排缺失，要么綜合性不強[5]，因此論文提出采用綜合性實驗案例設(shè)計來達成課程目標(biāo)，并逐步培養(yǎng)學(xué)生解決復(fù)雜工程問題的綜合能力和高級思維。

1 融合知識、能力、素質(zhì)的綜合實驗課設(shè)計思路

算法的時空分析實驗是數(shù)據(jù)結(jié)構(gòu)課程的第一個實驗，考慮以提升學(xué)生綜合能力和素質(zhì)為重點目標(biāo)，重新設(shè)計算法的時空分析實驗內(nèi)容如表1所示。

從表1可以看出，實驗分為五個功能模塊，分別為：結(jié)構(gòu)體和函數(shù)復(fù)習(xí)模塊，空間復(fù)雜度模塊，時間復(fù)雜度模塊，系統(tǒng)優(yōu)化模塊、實驗總結(jié)和分析模塊。

結(jié)構(gòu)體和函數(shù)復(fù)習(xí)模塊主要考慮學(xué)生程序設(shè)計基礎(chǔ)薄弱的現(xiàn)狀，設(shè)計一些程序填空題和編程興趣題，用兩周時間，在課前完成，培養(yǎng)學(xué)生查閱文獻，溝通交流的意識，讓學(xué)生反思自己的知識薄弱點，主動查缺補漏?？臻g復(fù)雜度模塊主要任務(wù)是同一問題的不同函數(shù)設(shè)計，培養(yǎng)學(xué)生程序設(shè)計和軟件測試技能，學(xué)會在判斷和權(quán)衡的基礎(chǔ)上深度分析，樹立空間資源管理和積極學(xué)習(xí)的意識。 時間復(fù)雜度模塊要求對數(shù)學(xué)問題進行快慢算法的設(shè)計，培養(yǎng)學(xué)生算法設(shè)計和測試技巧，樹立探究和驗證，克服障礙，勇于探究的職業(yè)技能和態(tài)度。系統(tǒng)優(yōu)化模塊通過讓學(xué)生查閱閱讀實用的系統(tǒng)優(yōu)化資料，培養(yǎng)學(xué)生整體思維，分析確定系統(tǒng)優(yōu)化的優(yōu)先級和焦點，激發(fā)求知欲和終生學(xué)習(xí)的意識，為自己進行職業(yè)規(guī)劃，明確自己職業(yè)的任務(wù)和責(zé)任。實驗總結(jié)分析模塊主要對實驗進行總結(jié)和分析，內(nèi)容包括解決問題的新思路，自己實驗工作的優(yōu)勢和不足，在綜合能力提升方面的進步等等，鍛煉學(xué)生的圖標(biāo)和寫作交流能力，為未來職業(yè)工作匯報和團隊交流，打下基礎(chǔ)。

2 綜合性實驗具體案例設(shè)計和實踐

依據(jù)表1的實驗設(shè)計思路，開展綜合性實驗具體案例設(shè)計，因此我們精心設(shè)計了五個功能模塊（結(jié)構(gòu)體和函數(shù)復(fù)習(xí)模塊，空間復(fù)雜度模塊，時間復(fù)雜度模塊，系統(tǒng)優(yōu)化模塊和實驗總結(jié)和分析模塊）的實驗子目標(biāo)、實驗內(nèi)容和教學(xué)策略等。

2.1 結(jié)構(gòu)體和函數(shù)復(fù)習(xí)模塊案例設(shè)計

實驗?zāi)繕?biāo)：①能夠?qū)W會使用文獻搜索技巧查詢資料;②學(xué)會庫函數(shù)的調(diào)用，掌握計算代碼段運行時間的基本步驟;③能夠掌握常見的庫函數(shù)的調(diào)用錯誤及調(diào)試方法。

實驗內(nèi)容：①在C語言庫文件time.h中有哪些不同的結(jié)構(gòu)體和操作日期和時間的函數(shù)，這些結(jié)構(gòu)體的詳細成員有哪些，代表的含義是什么？有哪些操作日期和時間的函數(shù)以及函數(shù)的作用是什么？②以結(jié)構(gòu)體time_t，和對應(yīng)的time（）函數(shù)為例，給出一段成功調(diào)用time（）的程序代碼并截圖給出效果圖;③以結(jié)構(gòu)體timeb，或clock_t為例，給出計算代碼段運行時間的程序代碼和運行結(jié)果;④程序調(diào)試中有哪些常見的調(diào)用錯誤。⑤分析time_t， timeb， timeval， clock_t這四個結(jié)構(gòu)體調(diào)用時間精度的差別和適用范圍。

教學(xué)策略：以學(xué)生線下自學(xué)為主，通過小組交流匯報，肯定學(xué)生的過程努力和結(jié)果。教師講解關(guān)鍵字搜索和中英文資料搜索的技巧。

2.2 空間復(fù)雜度測試模塊案例設(shè)計

實驗?zāi)繕?biāo)：①了解軟件測試中的靜態(tài)測試，動態(tài)測試和單元測試;②理解空間復(fù)雜度的概念和理論分析方法;③培養(yǎng)合理利用空間資源的意識，判斷和權(quán)衡，主動問題分析。

實驗內(nèi)容：①用循環(huán)的編程思想依次輸出從N個有規(guī)律整數(shù)的函數(shù)設(shè)計（程序1）;②編寫一個遞歸的函數(shù)（程序2），實現(xiàn)依次輸出N個有規(guī)律整數(shù);③針對程序1和2，給出一組相同N的值來確定兩個程序都能正常運行，其中一個非正常運行，利用空間復(fù)雜度的概念，分析兩個程序的空間復(fù)雜度。

教學(xué)策略：教師講解各種測試概念，強調(diào)測試的重要性，引導(dǎo)學(xué)生分析遞歸程序的復(fù)雜度，學(xué)生自主完成函數(shù)設(shè)計和軟件測試。

2.3 時間復(fù)雜度測試模塊案例設(shè)計

實驗?zāi)繕?biāo)：①掌握利用遞推算法求解問題;②理解時間復(fù)雜度的概念和理論分析方法;③學(xué)會調(diào)用時間函數(shù)，編寫同一問題不同算法的運行時間的程序;④了解利用軟件測試技術(shù)，分析驗證不同算法的時間效率。

實驗內(nèi)容：①利用循環(huán)語句設(shè)計算法（算法1）進行多項式1+x+…+ x求和，并分析其時間復(fù)雜度;②利用遞推算法（算法2）進行多項式1+x+…+x求和，并分析其時間復(fù)雜度;③利用timeb，及相關(guān)函數(shù)設(shè)計利用循環(huán)和非遞推算法的計算時間的程序;④軟件測試中計算時間都為零，原因是什么，如何設(shè)計輸入相同的避免函數(shù)時間為零;⑤分析表2中X和N的值是否相同，兩個程序輸入?yún)?shù)不一樣，能夠比較算法的計算時間？兩個算法的計算時間是否和理論復(fù)雜度的分析結(jié)果一致，為什么？

教學(xué)策略：學(xué)生自主完成算法設(shè)計和問題分析，輔助部分學(xué)生進行遞推算法的計算程序設(shè)計，必要時提供參考代碼，引導(dǎo)學(xué)生克服困難和障礙，學(xué)會分析實驗結(jié)果，驗證理論。

2.4 系統(tǒng)優(yōu)化模塊案例設(shè)計

實驗?zāi)繕?biāo)：①培養(yǎng)學(xué)生整體思維，系統(tǒng)思維和把握熱點技術(shù)趨勢的思維;②學(xué)會采用探究式學(xué)習(xí)進行系統(tǒng)優(yōu)化，了解算法級別，函數(shù)級別，循環(huán)級別，語句級別，指令級別優(yōu)化串行代碼，激發(fā)求知欲并養(yǎng)成終生學(xué)習(xí)的良好習(xí)慣。③逐步養(yǎng)成盡善盡美的工作態(tài)度，崇尚奮斗，勇于擔(dān)當(dāng)?shù)募覈閼选?/p>

實驗內(nèi)容：①閱讀谷歌公司的C++編碼規(guī)范中的頭文件規(guī)則和命名約定規(guī)則，改造自己編寫的程序;②閱讀文獻[6]中的算法性能和程序性能的度量與分析，串行代碼性能優(yōu)化技術(shù)，談?wù)勀愕恼J識和看法;③Linux環(huán)境下提供了納秒級精度的計時函數(shù)clock_gettime，在Linux環(huán)境下使用GCC編譯器能否解決資金算法計時為0的問題;④基于SSE/AVX的向量化編程方法，改造算法，并進行時間效率的對比和分析。

教學(xué)策略：要求學(xué)生自主完成閱讀任務(wù)，鼓勵學(xué)生以小組形式完成探究性實驗任務(wù)，把握系統(tǒng)優(yōu)化的思維，強調(diào)代碼規(guī)范對于求職面試和職業(yè)生涯的重要性。

2.5 實驗總結(jié)分析模塊案例設(shè)計

實驗?zāi)繕?biāo)：①鍛煉學(xué)生的圖表和文字寫作交流能力;②良好的軟件工程文檔和職業(yè)工作匯報材料;③學(xué)會利用口頭和文字材料進行團隊協(xié)作和溝通。

實驗內(nèi)容：①對實驗結(jié)果進行分析，有沒有解決求解程序運行時間到新方法和思路？②程序中遇見的錯誤有哪些，和自己如何解決的？未解決的問題有哪些？③在算法設(shè)計，資料查找，對比分析，軟件測試，溝通交流等綜合能力提升方面，收獲和不足有哪些？是否有未來的學(xué)習(xí)計劃和努力方向？

2.6 綜合實驗項目考核設(shè)計

針對本次算法的時空分析綜合性實驗，設(shè)計實驗考評成績構(gòu)成和評價方式為：結(jié)構(gòu)體和函數(shù)模塊占15%，采用組內(nèi)成員互評得分方式;空間復(fù)雜度模塊占20%，以同學(xué)間現(xiàn)場檢查互評進行;時間復(fù)雜度模塊占40%，以教師檢查提問形式評價;系統(tǒng)優(yōu)化模塊占15%，采用小組匯報整體得分形式;最終實驗報告（含實驗總結(jié)和分析模塊）的占10%，需要學(xué)生提交到在線作業(yè)批改系統(tǒng)，教師通過內(nèi)容查重后，單獨評價。

經(jīng)過以上綜合式實驗內(nèi)容設(shè)計和實踐后，學(xué)生普遍反映該實驗項目銜接自然，挑戰(zhàn)度較高，完成實驗后增加了對算法的感性認識，增強了學(xué)習(xí)興趣，特別在程序設(shè)計，文獻查找，對比分析，系統(tǒng)思維，溝通討論等綜合能力提升度較大，取得了良好的教學(xué)成效。

3 結(jié)論

一流本科課程要求增加課程的高階性、創(chuàng)新性和挑戰(zhàn)度，要求培養(yǎng)學(xué)生解決復(fù)雜問題的綜合能力和高級思維。本論文以數(shù)據(jù)結(jié)構(gòu)課程中的算法時空分析內(nèi)容為例，兼顧地方應(yīng)用型本科高校的實際，探索了融合知識、能力、素質(zhì)的綜合性實驗設(shè)計思路，取得了良好的教學(xué)效果，對其他相關(guān)課程的改革有一定的借鑒和參考意義。當(dāng)然該綜合性教學(xué)案例也存在耗費時間長，對基礎(chǔ)不好的學(xué)生挑戰(zhàn)性較高的不足，未來我們將在課程實踐中不斷聽取學(xué)生的意見，并持續(xù)改進和優(yōu)化案例，努力提升實踐教學(xué)質(zhì)量。

參考文獻（References）：

[1] 教育部關(guān)于一流本科課程建設(shè)的實施意見[EB/OL].http：//www.moe.gov.cn/srcsite/A08/s7056/201910/t20191031_406269.html.

[2] 李敏之，王陽萍，李海軍.新工科建設(shè)指引下的西部高校一流本科課程建設(shè)——以大學(xué)計算機基礎(chǔ)課程為例[J].計算機教育，2020，311（11）：93-97

[3] 陳越，何欽銘.數(shù)據(jù)結(jié)構(gòu)[M].北京：高等教育出版社，2012

[4] 陳越，何欽銘，馮雁.“數(shù)據(jù)結(jié)構(gòu)”綜合性課程設(shè)計教學(xué)探索與實踐[J].計算機教育，2008，68（8）：56-57

[5] 張兆維，王建華，陶曦鳴.“數(shù)據(jù)結(jié)構(gòu)”課程的課內(nèi)實驗教學(xué)探索與實踐[J]. 計算機時代，2020，335（5）：96-99

[6] 劉文志.并行算法設(shè)計與性能優(yōu)化[M].北京：機械工業(yè)出版社，2015