王 芳，蔡 沂

?

基于生成樹的學(xué)生互校驗(yàn)簽到應(yīng)用研究

王 芳，蔡 沂

（華南理工大學(xué) 廣州學(xué)院計(jì)算機(jī)工程學(xué)院，廣東 廣州 510800）

文中提出了一種課堂簽到方案，主要思路是通過學(xué)生座位信息之間的相互校驗(yàn)來驗(yàn)證簽到的真實(shí)性。首先，文中描述了該簽到方案的工作流程；然后設(shè)計(jì)了基于生成樹的相互校驗(yàn)算法；最后分析了該簽到方案的優(yōu)勢(shì)。分析和測(cè)試結(jié)果表明：該簽到方案能夠快速產(chǎn)生簽到結(jié)果、防止代簽、減少遲到早退；基于該方案的簽到系統(tǒng)實(shí)現(xiàn)簡單，具有很強(qiáng)的實(shí)用性和推廣價(jià)值。

簽到；生成樹；選座；相互校驗(yàn)；考勤

0 引言

大學(xué)課堂簽到可以粗略地分為人工簽到和自動(dòng)簽到兩類。人工簽到或點(diǎn)名不僅消耗了課堂時(shí)間，而且具有較大的局限性，遲到、早退、代簽等現(xiàn)象時(shí)有發(fā)生。隨著移動(dòng)互聯(lián)網(wǎng)技術(shù)的發(fā)展，近年來涌現(xiàn)出大批手機(jī)簽到系統(tǒng)，如使用無線局域網(wǎng)和手機(jī)IMEI的簽到系統(tǒng)[1]、使用藍(lán)牙技術(shù)和二維碼技術(shù)的點(diǎn)名軟件[2]、基于微信公眾號(hào)的簽到[3]、基于WIFI的室內(nèi)定位簽到[4]、基于WIFI熱點(diǎn)和MAC地址的手機(jī)簽到[5-6]、基于GPS定位的簽到[7-8]等，但都存在無法精確判斷學(xué)生是否在教室內(nèi)、是否簽到后離開等問題。還有些方案依賴于特定的手機(jī)操作系統(tǒng)和網(wǎng)絡(luò)設(shè)備的支持，在學(xué)校推廣和普及的難度較大。

本文提出一種基于生成樹的學(xué)生互校驗(yàn)簽到方案。該方案要求學(xué)生在規(guī)定時(shí)間內(nèi)提交自己的座位號(hào)，并且通過掃碼獲取前后左右的位置信息。系統(tǒng)通過課堂上所有簽到學(xué)生位置信息之間的相互校驗(yàn)生成簽到座位表，簽到座位表直觀地展示了學(xué)生的入座情況，方便教師使用手機(jī)快速查看和操作。為縮短簽到位置信息的校驗(yàn)時(shí)間，本文提出一種基于生成樹的相互校驗(yàn)算法。最后，文章分析了基于本方案的課堂簽到系統(tǒng)的優(yōu)勢(shì)。

1 系統(tǒng)設(shè)計(jì)與功能描述

本文針對(duì)大學(xué)課堂準(zhǔn)確并快速簽到設(shè)計(jì)一種簽到方案，能較大程度上避免學(xué)生抱著僥幸心理逃課、遲到、早退。主要包括學(xué)生選座、教師考勤、學(xué)生確認(rèn)入座、系統(tǒng)校驗(yàn)簽到信息、系統(tǒng)生成簽到座位表、教師管理考勤記錄等功能，所有操作都在手機(jī)上完成。圖1給出了此課堂簽到方案的工作流程圖。

圖1 系統(tǒng)工作流程

功能描述如下：（1）學(xué)生選座：學(xué)生選擇即將要上的課程，進(jìn)入對(duì)應(yīng)教室座位表頁面選座；（2）開始考勤：教師選擇正在上的課程，進(jìn)入對(duì)應(yīng)教室座位表頁面查看選座情況，可開始考勤；（3）學(xué)生確認(rèn)入座：教師開始考勤后，教室座位表頁面顯示確認(rèn)入座倒計(jì)時(shí)，學(xué)生通過掃碼提交前后左右同學(xué)的位置信息完成確認(rèn)入座；（4）系統(tǒng)校驗(yàn)簽到信息：確認(rèn)入座倒計(jì)時(shí)結(jié)束，系統(tǒng)通過所有學(xué)生位置信息的相互校驗(yàn)得出每個(gè)學(xué)生的簽到結(jié)果；（5）系統(tǒng)生成簽到座位表：系統(tǒng)根據(jù)簽到結(jié)果將簽到有效的學(xué)生姓名顯示在教室座位表上；（6）教師確認(rèn)簽到座位表：教師查看簽到座位表，并可修改簽到座位表以應(yīng)對(duì)特殊情況；（7）結(jié)束考勤：教師點(diǎn)擊結(jié)束考勤按鈕表示完成本次課堂考勤，系統(tǒng)保存本次課堂考勤記錄；（8）管理考勤記錄：課后學(xué)生可查看自己的考勤記錄；教師可管理相關(guān)課程的考勤記錄，教師還可以登錄PC端后臺(tái)完成考勤記錄的統(tǒng)計(jì)、匯總和導(dǎo)出等。

2 互校驗(yàn)簽到理論依據(jù)與算法設(shè)計(jì)

2.1 座位表與選座

大學(xué)教室座位一般為m*n型，m為座位行數(shù)，n為座位列數(shù)。作者所在的學(xué)校已存在教室座位表系統(tǒng)，可直接使用。每個(gè)座位的座位號(hào)按行號(hào)和列號(hào)來編排，i-j表示第i行第j列座位的座位號(hào)（1≤i≤m, 1≤j≤n)。圖2為一個(gè)8行8列教室座位示意圖。

圖2 教室座位表

Fig.2 Classroom seating chart

學(xué)生上課之前，根據(jù)課程信息進(jìn)入相應(yīng)教室座位表頁面選座。圖3為某堂課選座座位表，灰色表示該座位已被某學(xué)生選中。

圖3 選座座位表

每個(gè)選座的學(xué)生都將產(chǎn)生一條如表1所示的選座記錄。表中省略了與課程相關(guān)的教室和上課時(shí)間等信息，本文暫不討論簽到記錄與課程相關(guān)信息的關(guān)聯(lián)。

2.2 確認(rèn)入座與位置信息

上課后，教師可開始考勤，學(xué)生需要確認(rèn)入座。

表1 選座記錄

Tab.1 Seat selection record

一次有效的簽到需要得到鄰座同學(xué)位置信息的證明，確認(rèn)入座是為了讓學(xué)生提交其前后左右位置同學(xué)的信息（學(xué)生通過掃描鄰座同學(xué)的二維碼來提交其位置信息）。由于方向的相對(duì)性，當(dāng)某學(xué)生的前方位置有人時(shí)，他把前方學(xué)生的信息填入自己的‘前位’中，同時(shí)他也將被前方位置的學(xué)生填入其‘后位’中；當(dāng)某學(xué)生的左方位置有人時(shí)，他把左方學(xué)生的信息填入自己的‘左位’中，同時(shí)他也將被左方位置的學(xué)生填入其‘右位’中。左右位置與前后位置同理，不再累述。

系統(tǒng)可設(shè)置確認(rèn)入座時(shí)間段，比如學(xué)生必須在教師開始考勤后的5分鐘內(nèi)完成確認(rèn)入座操作。在確認(rèn)入座時(shí)間段內(nèi)，已選座的學(xué)生還可以重新選座（換座）。學(xué)生要確保自己前后左右至少有一個(gè)位置有學(xué)生坐，這樣才能被他人填入位置信息中，才能使自己得到校驗(yàn)。學(xué)生在確認(rèn)入座時(shí)填寫位置信息后將產(chǎn)生一條如表2所示的位置信息記錄。

表2 某學(xué)生的位置信息記錄

Tab.2 A student's location information record

表2為學(xué)生‘周圍’的位置信息記錄。根據(jù)表2以及前后左右座位的特點(diǎn)，可以由學(xué)生‘周圍’確認(rèn)入座的位置信息得到表3所示的座位對(duì)應(yīng)關(guān)系。

表3 由表2得出的學(xué)生座位對(duì)應(yīng)關(guān)系

Tab.3 The seat correspondence of students is obtained from table 2

用表3的座位對(duì)應(yīng)關(guān)系與表1的選座記錄進(jìn)行對(duì)比，不僅校驗(yàn)了學(xué)生‘周圍’的簽到記錄，同時(shí)也校驗(yàn)了學(xué)生‘張倩’和‘李悠’。由此可知，并不需要所有的學(xué)生都提交前后左右的位置信息，有些學(xué)生是主動(dòng)驗(yàn)證，如學(xué)生‘周圍’；有些學(xué)生是被動(dòng)驗(yàn)證，如學(xué)生‘張倩’和‘李悠’。

接下來我們要討論的問題是：如何利用最少的位置信息驗(yàn)證選座座位表中所有位置的簽到記錄。

2.3 位置信息的數(shù)學(xué)表示

2.3.1 無向圖

定義1 無向圖G=，其中：V是非空集合，稱為頂點(diǎn)集；E是V中元素構(gòu)成的無序二元組的集合，稱為邊集[9]。

若將選擇座位號(hào)i-j的學(xué)生看成頂點(diǎn)vi, j，圖3的選座座位表可轉(zhuǎn)化為圖4。

圖4 頂點(diǎn)化的選座座位表

若用座位前后左右的相鄰關(guān)系表示邊，則可能與頂點(diǎn)vi, j有關(guān)的邊為(vi–1, j, vi, j)、(vi, j, vi+1, j)、(vi, j–1, vi, j)、(vi, j, vi, j+1)，其中1≤i–1, i, i+1≤m，1≤j–1, j, j+1≤n。因此，圖4的選座座位表可表示成一個(gè)非連通的無向圖G，G有3個(gè)連通分量：G1、G2、G3，如圖5。

由此可得，所有的選座座位表都可以表示成類似圖5的無向圖，連通分量的個(gè)數(shù)大于等于1。又因?yàn)槊總€(gè)學(xué)生的前后左右至少有一個(gè)位置有同學(xué)坐，所以每個(gè)連通分量至少包含2個(gè)頂點(diǎn)。

2.3.2 生成樹

引理1 如果連通圖 G的一個(gè)子圖是一棵包含G的所有頂點(diǎn)的樹，則該子圖稱為G的生成樹（Spanning Tree）。生成樹是連通圖的包含圖中的所有頂點(diǎn)的極小連通子圖[10]。

引理2 若G是非連通的無向圖，則要若干次從外部調(diào)用DFS（Depth First Search深度優(yōu)先搜索）或BFS（Breadth First Search 廣度優(yōu)先搜索）算法，才能完成對(duì)G的遍歷。每一次外部調(diào)用，只能訪問到G的一個(gè)連通分量的頂點(diǎn)集，這些頂點(diǎn)和遍歷時(shí)所經(jīng)過的邊構(gòu)成了該連通分量的一棵DFS或BPS生成樹。G的各個(gè)連通分量的DFS或BFS生成樹組成了G的DFS或BFS生成森林[10-11]。

圖5 無向圖G，連通分量G1、G2、G3

由引理1和引理2可知，對(duì)于由選座座位表轉(zhuǎn)換成的無向圖G，通過對(duì)G的遍歷找到G的每個(gè)連通分量的生成樹，就找到了每個(gè)連通分量中連接所有頂點(diǎn)的最短連通路徑。

圖的生成樹不惟一。從不同的頂點(diǎn)出發(fā)進(jìn)行遍歷，可以得到不同的生成樹。[11]對(duì)于圖5中無向圖G的連通分量G3，若從頂點(diǎn)v6,1出發(fā)進(jìn)行遍歷，圖6為G3的一棵生成樹，v6,1為樹的根節(jié)點(diǎn)。

對(duì)于圖5生成樹中的節(jié)點(diǎn)，只要父節(jié)點(diǎn)位置所代表的學(xué)生提交其子節(jié)點(diǎn)位置的學(xué)生信息，就可以完成對(duì)圖中8個(gè)節(jié)點(diǎn)位置所代表的學(xué)生簽到信息的校驗(yàn)。

2.4 位置信息的收集

根據(jù)生成樹中節(jié)點(diǎn)之間的父子關(guān)系和節(jié)點(diǎn)本身的位置關(guān)系，系統(tǒng)向每個(gè)選座的學(xué)生發(fā)送收集位置信息的指令。由圖6和表4，座位號(hào)6-1的學(xué)生接收到的指令為“請(qǐng)?zhí)峤缓蠓胶陀曳酵瑢W(xué)信息”，座位號(hào)6-2的學(xué)生接收到的指令為“請(qǐng)?zhí)峤磺胺胶陀曳酵瑢W(xué)信息，并將你的信息提供給左方同學(xué)”，座位號(hào)8-2的學(xué)生接收到的指令為“請(qǐng)將你的信息提供給左方同學(xué)”，諸如此類。根據(jù)指令收集到的位置信息如表5所示。

圖6 連通分量G3的生成樹

表4 圖6樹的父子節(jié)點(diǎn)關(guān)系

Tab.4 The parent-child relationship of the tree in figure 6

表5 收集的位置信息

Tab.5 Collected location information

如果選座座位號(hào)為5-2的學(xué)生沒來，那么他將不會(huì)出現(xiàn)在座位號(hào)為6-2的學(xué)生的前方位置信息中。

如果選座座位號(hào)為8-2的學(xué)生沒來，那么他將不會(huì)出現(xiàn)在座位號(hào)為8-1的學(xué)生的右方位置信息中。而座位號(hào)為8-1的學(xué)生收到了“請(qǐng)?zhí)峤挥曳綄W(xué)生信息”的指令卻無信息可填，此時(shí)8-1的學(xué)生應(yīng)填寫有人坐的一個(gè)方向的同學(xué)信息來證明自己的存在（因?yàn)槊總€(gè)學(xué)生的前后左右至少有一個(gè)位置有同學(xué)坐，這是學(xué)生確認(rèn)入座的必要條件）。座位號(hào)8-1的學(xué)生應(yīng)提交補(bǔ)充信息“前方同學(xué)的信息：XXX”。

如果選座座位號(hào)為7-1的學(xué)生沒來，那么他將不會(huì)出現(xiàn)在座位號(hào)為6-1的學(xué)生的前方位置信息中。而座位號(hào)為7-2的學(xué)生收到了“請(qǐng)將你的信息提供給左方同學(xué)”的指令，當(dāng)他發(fā)現(xiàn)自己的信息無法被填入時(shí)（左方位置7-1無人），應(yīng)填寫有人坐的一個(gè)方向的學(xué)生信息來證明自己的存在。座位號(hào)7-2的學(xué)生應(yīng)提交補(bǔ)充信息“前方同學(xué)的信息：XXX”或“后方同學(xué)的信息：XXX”。

由此可知，對(duì)于由選座座位表轉(zhuǎn)換成的無向圖G的生成森林，只要生成樹中每個(gè)父節(jié)點(diǎn)位置所代表的學(xué)生填寫其子節(jié)點(diǎn)位置的學(xué)生信息，且當(dāng)有節(jié)點(diǎn)發(fā)現(xiàn)自己的信息無法被填入并且也沒有接收到填入他人信息的指令時(shí)能填寫補(bǔ)充信息來證明自己，就能收集到足夠的位置信息與選座座位表進(jìn)行對(duì)比校驗(yàn)，得出簽到結(jié)果。收集位置信息的過程即為獲取簽到記錄的過程，校驗(yàn)位置信息的過程即為驗(yàn)證簽到真實(shí)性的過程。

2.5 基于生成樹的互校驗(yàn)簽到算法設(shè)計(jì)

為了獲得足夠的位置信息與選座座位表進(jìn)行對(duì)比校驗(yàn)，系統(tǒng)要向選座的學(xué)生發(fā)送收集位置信息的指令。要向哪些學(xué)生發(fā)送指令？分別給他們發(fā)送什么樣的指令呢？這兩個(gè)問題才是獲取位置信息的關(guān)鍵所在。

算法1 基于生成樹的互校驗(yàn)簽到算法。

第1步：根據(jù)選座座位表生成無向圖G

第2步：調(diào)用DFS（或BFS）算法遍歷無向圖G，生成森林

第3步：對(duì)生成森林中的每棵生成樹，根據(jù)樹的生成路徑，調(diào)用generateOrders算法（見算法2）生成要發(fā)送給每個(gè)節(jié)點(diǎn)的指令

第4步：向每個(gè)節(jié)點(diǎn)表示的學(xué)生發(fā)送對(duì)應(yīng)的指令

第5步：獲取學(xué)生根據(jù)指令提交的位置信息

第6步：將位置信息與選座座位表進(jìn)行對(duì)比，生成簽到座位表

算法1第3步中對(duì)每棵生成樹調(diào)用名為gen-erate-Orders的算法：數(shù)組nodeArr[]用于存儲(chǔ)其生成路徑的節(jié)點(diǎn)信息，是算法1第2步的輸出；哈希表orderMap用于存儲(chǔ)節(jié)點(diǎn)與應(yīng)發(fā)送給節(jié)點(diǎn)的指令列表的鍵值對(duì)，初始情況下所有節(jié)點(diǎn)對(duì)應(yīng)的指令列表都為空。

算法2generateOrders生成指令算法。

for each fnode in nodeArr[]

for each snode in sonArr[]

orderList_of_fnode.add(orderStr_of_fnode), orderList_of_snode.add(orderStr_of_snode)//將前面構(gòu)造的指令字符串添加到對(duì)應(yīng)的指令列表中

orderMap.set(fnode, orderList_of_fnode), o-r---d-er-Map.set(snode, orderList_of_snode)//分別更新orderMap中key為fnode和snode的value

end for

end for

通過調(diào)用算法2，哈希表orderMap中存儲(chǔ)了要向node節(jié)點(diǎn)所表示的學(xué)生發(fā)送指令列表orderList。

3 系統(tǒng)分析與實(shí)現(xiàn)

3.1 算法時(shí)間復(fù)雜度

算法1第2步，調(diào)用DFS和BFS算法遍歷無向圖G，若用鄰接矩陣來實(shí)現(xiàn)，時(shí)間復(fù)雜度均為O(n2)，其中n為頂點(diǎn)數(shù)。

算法1第3步，對(duì)每棵生成樹調(diào)用算法2。因?yàn)槊靠蒙蓸渲辽儆?個(gè)節(jié)點(diǎn)，所以生成樹的數(shù)量一定小于n/2。而算法2中，因?yàn)槊總€(gè)節(jié)點(diǎn)最多有4個(gè)子節(jié)點(diǎn)，所以時(shí)間復(fù)雜度為O(n*4)。因此，算法1第3步的時(shí)間復(fù)雜度為O(n*4*n/2)=O(n2)。

算法1第6步，將位置信息與選座座位表進(jìn)行對(duì)比，時(shí)間復(fù)雜度也為O(n2)。

因?yàn)樗惴?的時(shí)間復(fù)雜度集中體現(xiàn)在第2步、第3步和第6步，所以基于生成樹的互校驗(yàn)簽到算法的時(shí)間復(fù)雜度為O(n2)[11]。

n為頂點(diǎn)數(shù)，即為一堂課上的學(xué)生數(shù)量。大學(xué)課堂一般為兩個(gè)行政班合并為一個(gè)教學(xué)班，人數(shù)在120人左右，對(duì)于時(shí)間復(fù)雜度為O(n2)的算法都能很快執(zhí)行完畢。算法1第4步為發(fā)送指令，第5步為表單提交，系統(tǒng)可設(shè)置學(xué)生必須在發(fā)送指令后的5分鐘內(nèi)完成確認(rèn)入座。

3.2 實(shí)現(xiàn)確認(rèn)入座

為了防止簽到作弊，教師開始考勤后，系統(tǒng)給每個(gè)選座的學(xué)生生成限本次考勤使用的二維碼，并設(shè)置有效時(shí)間，學(xué)生通過掃描二維碼來獲取指令中要求提供的鄰座同學(xué)的位置信息。如座位號(hào)6-1的學(xué)生接收到的指令為“請(qǐng)輸入后方和右方同學(xué)信息”，表示他要掃描后方和右方位置同學(xué)的二維碼；座位號(hào)6-2的學(xué)生接收到的指令為“請(qǐng)輸入前方和右方同學(xué)信息，并將你的信息提供給左方同學(xué)”，表示他要掃描前方和右方位置同學(xué)的二維碼，并將自己的二維碼提供給左方位置的同學(xué)掃描。

3.3 獲得簽到座位表

將學(xué)生在確認(rèn)入座時(shí)間段內(nèi)提交的位置信息與選座座位表進(jìn)行對(duì)比校驗(yàn)，可得出簽到座位表如 圖7。

圖7 簽到座位表

教師可查看并修改簽到座位表，以應(yīng)對(duì)特殊情況的出現(xiàn)。如有學(xué)生忘帶手機(jī)，教師可幫學(xué)生簽到。當(dāng)教師認(rèn)為不再需要修改簽到座位表時(shí)，可確認(rèn)簽到座位表以完成本次考勤。

3.4 非正常簽到分析

開始考勤后，系統(tǒng)向選座的學(xué)生發(fā)送收集位置信息的指令，學(xué)生根據(jù)指令提交位置信息以確認(rèn)入座，學(xué)生必須在規(guī)定時(shí)間段完成確認(rèn)入座。教師可自主選擇考勤的時(shí)間，遲到或早退的學(xué)生很可能不能按時(shí)完成確認(rèn)入座，也就無法簽到成功。

系統(tǒng)根據(jù)選座記錄和確認(rèn)入座記錄快速生成簽到結(jié)果，教師可以實(shí)時(shí)查看簽到座位表。教師在確認(rèn)簽到座位表之前可以修改簽到座位表，如教師在上課過程中發(fā)現(xiàn)有位置完成簽到卻無人，可判斷為早退，可點(diǎn)擊相應(yīng)座位取消其簽到或修改成早退狀態(tài)。

4 結(jié)語

本文提出基于生成樹的學(xué)生互校驗(yàn)簽到方案，利用學(xué)生之間的位置信息進(jìn)行相互校驗(yàn)，不但提高了簽到的效率，而且保證了簽到的真實(shí)性?；谠摲桨傅暮灥较到y(tǒng)不依賴除手機(jī)之外的其他設(shè)備、不限于某種手機(jī)操作系統(tǒng)。系統(tǒng)全部采用web實(shí)現(xiàn)，使它能快速集成到如微信、智慧校園、課程表等其他學(xué)生廣泛使用的應(yīng)用系統(tǒng)或平臺(tái)中，具有很強(qiáng)的實(shí)用性和推廣價(jià)值。

簽到的前提是選座，類似于電影院選座。對(duì)于一些有較多學(xué)生感興趣、教師授課方式生動(dòng)的課程，可能會(huì)出現(xiàn)“前排搶座”現(xiàn)象，在線選座也達(dá)到了在線搶座的目的。從心理學(xué)的角度來說，選座（搶座）行為可以提高學(xué)生上課的積極性。[12]

簽到活動(dòng)的第二步是確認(rèn)入座，由教師主動(dòng)發(fā)起。教師可根據(jù)實(shí)際情況決定是否對(duì)本堂課考勤，開始考勤才會(huì)有確認(rèn)入座流程。簽到活動(dòng)由學(xué)生通過互動(dòng)完成，確認(rèn)入座增強(qiáng)了學(xué)生簽到的主動(dòng)性，是一種積極的心理暗示。

大學(xué)課堂的座位選擇與教學(xué)情況緊密相關(guān)。教師預(yù)覽系統(tǒng)生成的簽到座位表，可以加深教師對(duì)學(xué)生的了解，使教師更好地把握課堂教學(xué)。系統(tǒng)將累計(jì)產(chǎn)生大量選座數(shù)據(jù)，這些數(shù)據(jù)不但可以用來分析學(xué)生上課時(shí)的座位分布對(duì)學(xué)生成績的影響[13]，而且可以分析教師的授課形式和授課質(zhì)量對(duì)學(xué)生學(xué)習(xí)積極性的影響。分析學(xué)生上課時(shí)的座位分布對(duì)學(xué)生成績的影響，讓老師更加了解學(xué)生，對(duì)成績不好的學(xué)生進(jìn)行勸導(dǎo)；分析教師的授課形式和授課質(zhì)量對(duì)學(xué)生學(xué)習(xí)積極性的影響，讓老師對(duì)自己的教學(xué)方式和手段進(jìn)行反思，推動(dòng)教學(xué)改革。[14]

[1] 劉冬梅, 任亞平, 周杰等. 基于Android的手機(jī)簽到系統(tǒng)[J]. 科技資訊, 2017, 14: 17-18.

[2] 陳三清, 殷鵬. 基于Android手機(jī)的課堂點(diǎn)名軟件設(shè)計(jì)與實(shí)現(xiàn)[J]. 電腦知識(shí)與技術(shù), 2017, 7, 95-99.

[3] 陳東偉, 譚建新, 溫家成等. 基于微信的考勤信息管理系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[J]. 信息技術(shù), 2017, 5, 85-88.

[4] 蔣航, 蔡秋楓. 基于室內(nèi)定位的學(xué)生簽到系統(tǒng)設(shè)計(jì)[J]. 電腦知識(shí)與技術(shù), 2017, 1, 54-55.

[5] 趙靚, 張玉. 基于WIFI熱點(diǎn)的手機(jī)簽到系統(tǒng)設(shè)計(jì)[J]. 計(jì)算機(jī)編程技巧與維護(hù), 2017, 6, 59-61.

[6] 肖俊生, 劉俊娟. 基于WI-FI的學(xué)生考勤系統(tǒng)研究與設(shè)計(jì)[J]. 工業(yè)控制計(jì)算機(jī), 2017, 1, 114-115.

[7] 張勁波, 周澤崇, 李雅杰等. 基于Android的上課簽到軟件分析與設(shè)計(jì)[J]. 電腦編程技巧與維護(hù), 2017, 2(3), 28.

[8] 徐寧. 基于微信平臺(tái)的并行簽到考勤管理系統(tǒng)[J]. 電腦知識(shí)與技術(shù), 2016, 30, 77-79.

[9] 耿素云, 屈婉玲, 張立昴. 離散數(shù)學(xué)[M]. 北京: 清華大學(xué)出版社, 2013.

[10] 李明哲等. 圖論及其算法[M]. 北京: 機(jī)械工業(yè)出版社, 2010.

[11] 嚴(yán)蔚敏, 吳偉民. 數(shù)據(jù)結(jié)構(gòu)(C語言版)[M]. 北京: 清華大學(xué)出版社, 2011.

[12] 王會(huì)廷, 張艷平, 閻慧. 大學(xué)生課堂行為的心理學(xué)研究[J]. 安徽工業(yè)大學(xué)學(xué)報(bào): 社會(huì)科學(xué)版, 2012, 29(3): 37-38.

[13] 王映學(xué), 段寶軍, 張曉州. 大學(xué)課堂座位選擇與學(xué)業(yè)成績的關(guān)系研究[J]. 重慶高教研究, 2017, 5(3): 65-72.

[14] 程永佳. 大學(xué)課堂有效教學(xué)的影響因素及提高策略[J]. 教育與教學(xué)研究, 2012, 26(5): 22-25.

Research on Class Sign_in Application Based on Validation between Classmates using Spanning Tree

WANG Fang, CAI Yi

(Guangzhou College of South China University of Technology, Guangzhou 510800, Guangdong, China)

In this paper, we put forward a class sign-in solution which verify the authenticity of sign-in by the seat information of classmates. Firstly, the work flow of this solution is described; secondly, the mutual validation algorithm based on Spanning Tree is described; finally, the greatest strengths of our solution are analyzed. Analysis results and test results show that using our solution can produce accurate sign-in results, prevent cheating, reduce arrive late and leave early, and the class sign-in system based on our solution is simple and very practical and has strong promotional value.

Class sign-in; Spanning Tree; Seat selection; Mutual validation; Attendance

TP311

A

10.3969/j.issn.1003-6970.2018.07.002

廣東省高等學(xué)校特色專業(yè)建設(shè)項(xiàng)目(JY170102)

王芳(1986-)，女，助教，主要研究方向：軟件工程、大數(shù)據(jù)技術(shù)；蔡沂，(1978-)，女，副教授，主要研究方向：網(wǎng)絡(luò)工程、信息安全。

本文著錄格式：王芳，蔡沂. 基于生成樹的學(xué)生互校驗(yàn)簽到應(yīng)用研究[J]. 軟件，2018，39（7）：06?-11