第1章程序員試題歷年考試情況分析

1、第1章 程序員試題歷年考試情況分析1.1 上午題歷年試題及考點(diǎn)分析程序員考試科目1計(jì)算機(jī)軟硬件基礎(chǔ)知識(shí)，也就是程序員上午題，是以選擇題的方式進(jìn)行考試的，其知識(shí)點(diǎn)包括計(jì)算機(jī)科學(xué)基礎(chǔ)、計(jì)算機(jī)硬件基礎(chǔ)知識(shí)、計(jì)算機(jī)軟件基礎(chǔ)知識(shí)、軟件開(kāi)發(fā)和維護(hù)、計(jì)算機(jī)安全知識(shí)、標(biāo)準(zhǔn)化基礎(chǔ)知識(shí)、專(zhuān)業(yè)英語(yǔ)等方面。在上午題的知識(shí)點(diǎn)中，主要以記憶為主，要比較全面地進(jìn)行復(fù)習(xí)，在復(fù)習(xí)的時(shí)候不必太深究。相對(duì)于下午題來(lái)說(shuō)，上午題是比較簡(jiǎn)單的。表1.1是從2000年到2006年上半年所有上午試題的知識(shí)點(diǎn)分布。表1.1 上午試題知識(shí)點(diǎn)分布2000年2001年2002年2003年2004年（上）2004年（下）2005年（上）2005年（下

2、）2006年（上）數(shù)據(jù)結(jié)構(gòu)10106888799信息技術(shù)基礎(chǔ)004965645操作系統(tǒng)555555655程序設(shè)計(jì)語(yǔ)言558556676軟件工程559646746面向?qū)ο?93333010數(shù)據(jù)庫(kù)原理10107556756多媒體553333433計(jì)算機(jī)硬件基礎(chǔ)202015151615131615網(wǎng)絡(luò)原理555555466其他000053564專(zhuān)業(yè)英語(yǔ)101010101010101010合計(jì)758475747575757675從表1.1中可以看出，知識(shí)點(diǎn)的考點(diǎn)分布沒(méi)有太大的變化，基本上覆蓋了大學(xué)本科計(jì)算機(jī)專(zhuān)業(yè)的所有專(zhuān)業(yè)課程。近三四次的考試中，還出現(xiàn)了一些日常操作中的題目，如Windows的操作及Of

3、fice系列軟件的操作，當(dāng)然，這些對(duì)考生來(lái)說(shuō)不是什么難題，因?yàn)榇蠹艺於荚谑褂?。在?fù)習(xí)的時(shí)候不宜過(guò)早地復(fù)習(xí)上午試題，因?yàn)槿菀淄?，編者建議在考試前半個(gè)月開(kāi)始復(fù)習(xí)上午題，多看書(shū)，多看練習(xí)，特別是一些練習(xí)題后面的解答，都是復(fù)習(xí)和記憶的重點(diǎn)。還有就是要把近兩三年的試題都要看一遍、做一遍，這樣比較容易把握以后的出題方向。1.2 下午題歷年試題及考點(diǎn)分析程序員考試科目2程序設(shè)計(jì)，也就是我們常說(shuō)的下午題，是以筆試填空的方式進(jìn)行考試，1996年以前是考C語(yǔ)言和CASL匯編語(yǔ)言，1996年到1998年考C語(yǔ)言和FORTRAN語(yǔ)言，1999年到2004年都只考C語(yǔ)言，2004年出了新考綱后就擴(kuò)充到必選C，可選C

4、+、Java、VB中的一種語(yǔ)言，并且一年考試兩次，讓考生有更多的機(jī)會(huì)參加這個(gè)考試。1999年以后，程序員考綱上所涉及的面比較廣，但實(shí)際上所考的內(nèi)容主要是C語(yǔ)言基礎(chǔ)上的數(shù)據(jù)結(jié)構(gòu)，在2004年新考綱之前，雖然有提及C+和面向?qū)ο蟮脑O(shè)計(jì)方法，但實(shí)際上考試的內(nèi)容全部是C語(yǔ)言，新考綱出來(lái)之后，試題的題型結(jié)構(gòu)有所改變，可以選做部分試題，加入了面向?qū)ο蟮某绦蛟O(shè)計(jì)，使用的語(yǔ)言也從單一的C語(yǔ)言擴(kuò)充到C+、Java、VB，讓考生有更多的選擇機(jī)會(huì)，但同時(shí)也增加了一定的難度，使得考生必須在掌握C語(yǔ)言之外還要掌握一門(mén)面向?qū)ο蟮某绦蛟O(shè)計(jì)語(yǔ)言。當(dāng)然，這也是程序設(shè)計(jì)語(yǔ)言的一個(gè)必然的發(fā)展方向。下面從2000年到2006年上半年

5、所有試題所涉及的考點(diǎn)進(jìn)行列表分析。1.2.1 2000年至2006年試題2000年下午試題一共有4道題，25個(gè)空，所涉及的算法、知識(shí)點(diǎn)及數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)如表1.2所示。表1.2 2000年下午試題考點(diǎn)分析題 號(hào)算 法知 識(shí) 點(diǎn)存 儲(chǔ) 結(jié) 構(gòu)一鏈表合并線性表指針判斷數(shù)組元素遞增數(shù)組、遞歸數(shù)組二長(zhǎng)整數(shù)格式化整數(shù)數(shù)組求組合整數(shù)數(shù)組三中綴表達(dá)式轉(zhuǎn)后綴棧指針表達(dá)式計(jì)算棧數(shù)組四貪心算法數(shù)組數(shù)組2001年下午試題一共5道題，25個(gè)空，所涉及的算法、知識(shí)點(diǎn)及數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)如 表1.3所示。2002年下午試題一共5道題，25個(gè)空，所涉及的算法、知識(shí)點(diǎn)及數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)如 表1.4所示。2003年下午試題一共5道題，25個(gè)

6、空，所涉及的算法、知識(shí)點(diǎn)及數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)如 表1.5所示。表1.3 2001年下午試題考點(diǎn)分析題 號(hào)算 法知 識(shí) 點(diǎn)存 儲(chǔ) 結(jié) 構(gòu)一字符串比較字符串指針計(jì)算鞍點(diǎn)矩陣數(shù)組二鏈表逆置線性表指針三文件的合并與恢復(fù)文件操作文件四雙向循環(huán)鏈表操作線性表指針五整數(shù)的分解數(shù)組、遞歸數(shù)組表1.4 2002年下午試題考點(diǎn)分析題 號(hào)算 法知 識(shí) 點(diǎn)存 儲(chǔ) 結(jié) 構(gòu)一顯示器編程多媒體、移位及邏輯運(yùn)算數(shù)組二字符串連接字符串指針求數(shù)組中最大元素下標(biāo)數(shù)組數(shù)組三直接插入排序排序數(shù)組數(shù)組逆置數(shù)組、遞歸數(shù)組四素?cái)?shù)篩選素?cái)?shù)數(shù)組五二叉排序樹(shù)結(jié)點(diǎn)插入二叉排序樹(shù)、查找、遞歸指針表1.5 2003年下午試題考點(diǎn)分析題 號(hào)算 法知 識(shí) 點(diǎn)存

7、儲(chǔ) 結(jié) 構(gòu)一查找折半查找、流程圖數(shù)組二查找字符串指針查找五叉排序樹(shù)、非遞歸指針三排序線性表、鏈表操作指針?biāo)脑匾苿?dòng)數(shù)組數(shù)組五棧和隊(duì)列的操作棧和隊(duì)列指針2004年上半年下午試題一共9道題，可以選做其中的25個(gè)空（或問(wèn)題），所涉及的算法、知識(shí)點(diǎn)及數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)如表1.6所示。表1.6 2004年上半年下午試題考點(diǎn)分析題 號(hào)算 法知 識(shí) 點(diǎn)存 儲(chǔ) 結(jié) 構(gòu)一快速排序快速排序、N-S圖、遞歸數(shù)組任選一題二判斷回文字符串指針字符串處理字符串?dāng)?shù)組三VB基礎(chǔ)VB基礎(chǔ)知識(shí)任選一題四進(jìn)制轉(zhuǎn)換數(shù)組、棧操作數(shù)組五VB組件應(yīng)用下拉列表框、文本框續(xù)表 題 號(hào)算 法知 識(shí) 點(diǎn)存 儲(chǔ) 結(jié) 構(gòu)任選一題六鏈表操作線性表指針七VB窗

8、口操作時(shí)間組件任選一題八所得稅計(jì)算數(shù)組數(shù)組九VB個(gè)人稅計(jì)算選擇結(jié)構(gòu)程序設(shè)計(jì)2004年下半年下午試題一共8道題，可以選做其中的25個(gè)空（或問(wèn)題），所涉及的算法、知識(shí)點(diǎn)及數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)如表1.7所示。表1.7 2004年下半年下午試題考點(diǎn)分析題 號(hào)算 法知 識(shí) 點(diǎn)存 儲(chǔ) 結(jié) 構(gòu)一二進(jìn)制求補(bǔ)流程圖數(shù)組二排序交換排序及其效率數(shù)組三元素移動(dòng)指針運(yùn)算、鏈表操作鏈表任選一題四統(tǒng)計(jì)競(jìng)賽結(jié)果結(jié)構(gòu)體、選擇排序結(jié)構(gòu)體、數(shù)組五VB（程序內(nèi)容和第四題C語(yǔ)言一樣）常用控件、基本函數(shù)任選一題六C+基礎(chǔ)繼承、抽象類(lèi)、動(dòng)態(tài)綁定七VB數(shù)據(jù)庫(kù)應(yīng)用文本框、命令按鈕、數(shù)據(jù)控件八Java基礎(chǔ)繼承、抽象類(lèi)、動(dòng)態(tài)綁定2005年上半年下午試題一

9、共8道題，可以選做其中的25個(gè)空（或問(wèn)題），所涉及的算法、知識(shí)點(diǎn)及數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)如表1.8所示。表1.8 2005年上半年下午試題考點(diǎn)分析題 號(hào)算 法知 識(shí) 點(diǎn)存 儲(chǔ) 結(jié) 構(gòu)一奇偶校驗(yàn)異或運(yùn)算、流程圖二最大公約數(shù)最大公約數(shù)字符串處理字符串指針三二叉樹(shù)結(jié)點(diǎn)的查找與刪除二叉樹(shù)二叉樹(shù)任選一題四子方陣查找二維數(shù)組數(shù)組五VB基礎(chǔ)組件列表框的常用屬性任選一題六Java應(yīng)用程序Java Applet類(lèi)七VB基礎(chǔ)組件VB內(nèi)部組件DriveListBox、DirListBox、FileListBox八C+基礎(chǔ)枚舉類(lèi)型2005年下半年下午試題一共8道題，可以選做其中的25個(gè)空（或問(wèn)題），所涉及的算法、知識(shí)點(diǎn)及數(shù)據(jù)存

10、儲(chǔ)結(jié)構(gòu)如表1.9所示。2006年上半年下午試題一共8道題，可以選做其中的25個(gè)空（或問(wèn)題），所涉及的算法、知識(shí)點(diǎn)及數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)如表1.10所示。表1.9 2005年下半年下午試題考點(diǎn)分析題 號(hào)算 法知 識(shí) 點(diǎn)存 儲(chǔ) 結(jié) 構(gòu)一字符串處理字符串處理、流程圖數(shù)組二線性表查找線性表數(shù)組三二分法查找線性表、二分查找數(shù)組任選一題四VB基礎(chǔ)標(biāo)簽、文本框、命令按鈕五二叉排序樹(shù)創(chuàng)建二叉排序樹(shù)樹(shù)任選一題六C+基礎(chǔ)類(lèi)的定義、查錯(cuò)七VB基礎(chǔ)時(shí)鐘組件及圖形編程八Java類(lèi)基礎(chǔ)Stock類(lèi)和JavaMain類(lèi)表1.10 2006年上半年下午試題考點(diǎn)分析題 號(hào)算 法知 識(shí) 點(diǎn)存 儲(chǔ) 結(jié) 構(gòu)一矩陣轉(zhuǎn)置矩陣、流程圖矩陣二普通數(shù)

11、據(jù)處理循環(huán)三棧操作棧的操作棧任選一題四數(shù)據(jù)處理結(jié)構(gòu)體數(shù)組處理結(jié)構(gòu)體數(shù)組五VB基本控件基本控件任選一題六C+基礎(chǔ)類(lèi)的定義、查錯(cuò)七VB基礎(chǔ)時(shí)鐘組件及圖形編程八Java類(lèi)基礎(chǔ)類(lèi)、查錯(cuò)1.2.2 命題方向的變化及分析對(duì)上面的列表進(jìn)行分析，我們可以看出一些程序員考試命題方向的變化，現(xiàn)從幾方面列舉如下。1語(yǔ)言的選擇從1996年以前的C語(yǔ)言和CASL匯編語(yǔ)言，到C語(yǔ)言和FORTRAN語(yǔ)言，再到只考C語(yǔ)言，以及到現(xiàn)在的在C語(yǔ)言和C+、Java、VB中進(jìn)行選擇，可見(jiàn)軟考始終緊跟著社會(huì)的需要，也緊跟著編程語(yǔ)言的發(fā)展方向，唯有發(fā)展與改變才能讓軟考充滿活力。這也許是軟考越來(lái)越受到社會(huì)認(rèn)同的一個(gè)重要原因！下面我們?cè)賮?lái)看

12、一個(gè)表，分析一下所考語(yǔ)言在選擇上有什么變化，如表1.11所示。從表1.11中可以得到一個(gè)信息：C語(yǔ)言始終是考試的最為突出的重點(diǎn)。例如，在2004年上半年改了考綱后的第一次考試中，最多可以選擇20個(gè)VB空，而只選5個(gè)C語(yǔ)言的空，但在接下來(lái)的下半年考試中，這個(gè)情況就馬上改了，最多只可選10個(gè)VB空，最少要做15個(gè)C語(yǔ)言空，而且一直延用至今。在考綱所增加的幾種語(yǔ)言當(dāng)中，Visual Basic是可表1.11 程序語(yǔ)言題量變化表（單位：空）時(shí) 間CVBC+Java最多可選C語(yǔ)言數(shù)量最多可選VB數(shù)量最多可選Java數(shù)量最多可選C+數(shù)量2000年25000250002001年25000250002002年

13、25000250002003年25000250002004年上半年2520002520002004年下半年2010552010552005年上半年2010552010552005年下半年2010552010552006年上半年201055201055供選題較多的一種，它是Microsoft公司開(kāi)發(fā)的基于BASIC的可視化程序設(shè)計(jì)語(yǔ)言，它在其編程系統(tǒng)中采用了面向?qū)ο?、事件?qū)動(dòng)的編程機(jī)制，用一種巧妙的方法把Windows編程的復(fù)雜性封裝起來(lái)，提供了一種所見(jiàn)即所得的可視化程序設(shè)計(jì)方法，為廣大的計(jì)算機(jī)專(zhuān)業(yè)學(xué)習(xí)人員、編程愛(ài)好者的程序編寫(xiě)帶來(lái)了極大的方便。所以，本書(shū)在最后一章為考生講解Visual Bas

14、ic程序設(shè)計(jì)，希望可以為讀者沖刺程序員考試提供一定的幫助。2知識(shí)點(diǎn)的選擇從2000年到2006年試題所考查的知識(shí)點(diǎn)上來(lái)看，C語(yǔ)言及數(shù)據(jù)結(jié)構(gòu)的主要考查的知識(shí)點(diǎn)沒(méi)有太大的變化，線性表、鏈表、字符串、二叉樹(shù)、排序和查找等幾大主要知識(shí)點(diǎn)在不斷的輪著出現(xiàn)。所以，本書(shū)將對(duì)這些主要知識(shí)點(diǎn)在解題中的運(yùn)用進(jìn)行重點(diǎn)講解和分析，但關(guān)于這些知識(shí)點(diǎn)本身的基本概念則只是略提，讀者可通過(guò)查閱數(shù)據(jù)結(jié)構(gòu)的相關(guān)教材去復(fù)習(xí)那些基礎(chǔ)知識(shí)。3題型的選擇從軟考的題型來(lái)看，2002年以前的考試基本上是以傳統(tǒng)題型為主，多數(shù)考經(jīng)典算法，只對(duì)各種常用算法熟練掌握即可通過(guò)。但從2002年以后，題型逐漸開(kāi)始變化。如2002年的下午第一題就不再以傳統(tǒng)

15、的方式出題，而是以算法分析的方式，或是說(shuō)程序文檔化的方式進(jìn)行考查，要求能夠讀懂對(duì)問(wèn)題的分析。這是一個(gè)很大的突破，要求應(yīng)試者不只是會(huì)做一些傳統(tǒng)的題目，還要學(xué)會(huì)分析一個(gè)問(wèn)題，從而得出解決問(wèn)題的算法。到2003年的下午第一題，在2002年的基礎(chǔ)上，題型進(jìn)一步改成以偽代碼的形式。到2004年上半年新考綱后，下午第一題變?yōu)橛肗-S圖形式描述算法的題型，由于流程圖、N-S圖都是用來(lái)描述算法的非?？茖W(xué)而且經(jīng)典的方法，所以從2004年上半年出現(xiàn)這種題型后，一直到2006年上半年的考試，每次的下午題第一題都是這種題型，相信以后這種題型還會(huì)繼續(xù)出現(xiàn)。其他一些題目的題型上也有一定的變化，以前傳統(tǒng)的各種較為經(jīng)典的算法

16、出現(xiàn)得越來(lái)越少，取而代之的是各種比較新的應(yīng)用型的題目，或者是把各種經(jīng)典的算法集中到一起出一些比較綜合性質(zhì)的題目。特別是一些處理比較現(xiàn)實(shí)問(wèn)題的題目，通常都是以比較大篇幅的題目出現(xiàn)。這類(lèi)型的題目所用到的算法不會(huì)難，主要是要求考生比較快就可以理解題目的意思，從而把握出題者的思路，快速地做出解答。當(dāng)然，只要我們把基礎(chǔ)的算法都較為熟練地掌握后，題型上的變化并不會(huì)給我們解題帶來(lái)多大的影響。1.3 個(gè)人經(jīng)驗(yàn)及應(yīng)試建議1.3.1 作者輔導(dǎo)經(jīng)驗(yàn)C語(yǔ)言是下午題的難點(diǎn)，如果C語(yǔ)言學(xué)得比較好，在上午題的基礎(chǔ)知識(shí)上下一些功夫，再學(xué)一種面向?qū)ο蟮木幊?，如VB、C+或Java，我個(gè)人覺(jué)得VB比較簡(jiǎn)單。本科大二、大三的學(xué)生用

17、一到兩個(gè)月的課余時(shí)間來(lái)作準(zhǔn)備，一般來(lái)說(shuō)通過(guò)率是比較高的。專(zhuān)科生相對(duì)來(lái)說(shuō)時(shí)間要長(zhǎng)一點(diǎn)，認(rèn)真的話，半年也差不多了。當(dāng)然，這不是絕對(duì)的，我遇到過(guò)復(fù)習(xí)兩個(gè)星期就通過(guò)的學(xué)生，因?yàn)樗腃語(yǔ)言和數(shù)據(jù)結(jié)構(gòu)學(xué)得很好。筆者有過(guò)多年的程序員輔導(dǎo)經(jīng)驗(yàn)，發(fā)現(xiàn)在程序員的應(yīng)試準(zhǔn)備過(guò)程中，最大難度的還是C語(yǔ)言及數(shù)據(jù)結(jié)構(gòu)，如果用兩個(gè)月的時(shí)間來(lái)準(zhǔn)備，那么要用一個(gè)半月的時(shí)間來(lái)復(fù)習(xí)C語(yǔ)言和數(shù)據(jù)結(jié)構(gòu)，另外在考試前的半個(gè)月，認(rèn)真地復(fù)習(xí)上午試題的基礎(chǔ)部分。以這種時(shí)間安排方式，相對(duì)來(lái)說(shuō)，比較容易通過(guò)程序員考試。除本書(shū)外，個(gè)人建議參考資料兩本：一本是清華大學(xué)出版社出版的程序員教程，此教程比較詳細(xì)地講解了上午題的內(nèi)容。另一本是清華大學(xué)出版社出版

18、的C語(yǔ)言程序設(shè)計(jì)（第二版），譚浩強(qiáng)著，此書(shū)對(duì)C語(yǔ)言的講解可謂是經(jīng)典之作。學(xué)習(xí)C語(yǔ)言的時(shí)候，要多進(jìn)行練習(xí)，這個(gè)是基礎(chǔ)，把基礎(chǔ)打好后，再進(jìn)入到數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的最好辦法是認(rèn)真地看算法，仔細(xì)分析算法的運(yùn)行過(guò)程，體會(huì)各種數(shù)據(jù)結(jié)構(gòu)的定義、用途及其基本操作。對(duì)各種不同的數(shù)據(jù)結(jié)構(gòu)的常規(guī)算法要非常熟練，如樹(shù)、鏈表、棧等結(jié)構(gòu)的基本操作是要熟記下來(lái)的。1.3.2 應(yīng)試建議程序員解題速度是練出來(lái)的，熟能生巧，只有通過(guò)大量的習(xí)題的調(diào)試或解答才能夠達(dá)到比較快的速度和以不變應(yīng)萬(wàn)變的程度。不要認(rèn)為大量練習(xí)只是簡(jiǎn)單的題海戰(zhàn)術(shù)，在任何學(xué)習(xí)過(guò)程中，只有經(jīng)過(guò)大量的練習(xí)，才能達(dá)到從量變到質(zhì)變的過(guò)程。學(xué)習(xí)從來(lái)都是沒(méi)有捷徑可

19、尋的。特別要鍛煉的是讀別人程序的能力，能夠從程序中比較快速地讀出程序編寫(xiě)者的意圖也就成功了一半。一個(gè)比較好的建議就是，在看本書(shū)提供的一些算法的時(shí)候，先不要看提示，只看代碼，練習(xí)從代碼就可以看出整個(gè)題目的意思。剛開(kāi)始會(huì)比較難，但習(xí)慣一段時(shí)間后，對(duì)將來(lái)做程序員的試題有很大的幫助。本書(shū)的最大特點(diǎn)是編排了大量的練習(xí)題，特別是程序題。可以這樣說(shuō)，只要把本書(shū)所列的程序做熟并理解，下午題的C語(yǔ)言部分就不用擔(dān)心了。從最近兩年的試題變化來(lái)看，C語(yǔ)言試題呈現(xiàn)出偏重基礎(chǔ)題，偏重于應(yīng)用，而難度不會(huì)太大。做完題之后要檢查，如果變量多的話，列一個(gè)變量表，模擬檢查運(yùn)行情況，看變量的變化，用這種方法可以比較準(zhǔn)確地查出程序是否

20、出錯(cuò)。1.3.3 解題方法我們?cè)谧鱿挛珙}的時(shí)候，可以大概依照如下的思路來(lái)做解答。1理解題意主要是根據(jù)問(wèn)題的描述來(lái)確定問(wèn)題的已知條件，并了解算法（程序）要達(dá)到的目的。通俗地講，就是要知道問(wèn)題的輸入和輸出。2確定算法每個(gè)題目在前面都有描述，通過(guò)對(duì)描述的分析，要確定題目應(yīng)該屬于哪一類(lèi)數(shù)據(jù)結(jié)構(gòu)以及相應(yīng)的算法。有些題目可能不屬于任何數(shù)據(jù)結(jié)構(gòu)，則它可能與某類(lèi)算法有關(guān)；但也有一些算法純粹是數(shù)學(xué)方法。題目前面描述是非常重要的，對(duì)試題的解答起著重要的指導(dǎo)作用。在描述中同時(shí)要理解算法過(guò)程。在分析算法時(shí)，可以以某個(gè)具體實(shí)例來(lái)試驗(yàn)。在有些時(shí)候，即使看不懂整道程序題，還是可以根據(jù)提示看懂其中的部分代碼段，也可以完成一定

21、的空格的填寫(xiě)。3理解程序分析程序結(jié)構(gòu)，如果有很多子函數(shù)，首先弄清楚各函數(shù)之間的關(guān)系和各函數(shù)的作用；如果程序較長(zhǎng)，則應(yīng)該根據(jù)算法過(guò)程，把每個(gè)程序段與算法的每個(gè)過(guò)程對(duì)應(yīng)起來(lái)，確定相應(yīng)的程序段功能。在程序中，已經(jīng)定義了某些變量，則在理解程序時(shí)，首先必須理解這些變量的含義。4根據(jù)C語(yǔ)言的語(yǔ)法填空示例：2004年上半年程序員下午試題試題六。函數(shù)DelAInsB（LinkedList La，LinkedList Lb，int key1，int key2，int len）的功能是，將線性表A中關(guān)鍵碼為keyl的結(jié)點(diǎn)開(kāi)始的len個(gè)結(jié)點(diǎn)，按原順序移至線性表B中關(guān)鍵碼為key2的結(jié)點(diǎn)之前，若移動(dòng)成功，則返回0；否

22、則返回1。線性表的存儲(chǔ)結(jié)構(gòu)為帶頭結(jié)點(diǎn)的單鏈表，La為表A的頭指針，Lb為表B的頭指針。單鏈表結(jié)點(diǎn)的類(lèi)型定義為：typedef struct node int key; struct node *next;*LinkedList;函數(shù)(1)int DelllnsB(LinkedLiSt La,LinkedList Lb,int keyl,int key2,int len)(2) LinkedList p,q,s,prep,pres;(3) int k,(4) if(!La->next | !Lb->next | len<=0) return 1;(5) p=La->nex

23、t; prep=La;(6) while(p && p->key != keyl)/*查找表A中鍵值為key1的結(jié)點(diǎn)*/(7) prep=p;p=p->next;(8) (9) if(!p) return 1;/*表A中不存在鍵值為key1的結(jié)點(diǎn)*/(10) q=p; k=1;(11) while(q && (1) )/*在表A中找出待刪除的len個(gè)結(jié)點(diǎn)*/(12) (2) ; k+;(13) (14) if(!q) return 1;/*表A中不存在要被刪除的len個(gè)結(jié)點(diǎn)*/(15) s=Lb->next; (3) ;(16) while(s

24、 && s->key != key2)/*查找表B中鍵值為key2的結(jié)點(diǎn)*/(17) pres = s; s = s->next;(18) (19) if(!s) return 1;/*表B中不存在鍵值為key2的結(jié)點(diǎn)*/(20) (4) =q->next;/*將表A中的len個(gè)結(jié)點(diǎn)刪除*/(21) q->next= (5) ;(22) pres->next=p;/*將len個(gè)結(jié)點(diǎn)移至表B*/(23) return 0;(24) 解：（1）理解題目。已知條件為兩個(gè)鏈表La和Lb，最后得到的結(jié)果也是兩個(gè)鏈表，只不過(guò)是La中的部分結(jié)點(diǎn)移動(dòng)到Lb中，因此

25、，本問(wèn)題主要是解決是怎么移動(dòng)的。（2）算法。在題目中沒(méi)有給出結(jié)點(diǎn)移動(dòng)的算法，我們先可以結(jié)合實(shí)例自己設(shè)計(jì)一個(gè)算法，然后看是不是與程序中的算法一致。如果不是，則再找算法。在自己設(shè)計(jì)算法的時(shí)候，最好的辦法是先看一看題目給出的算法提示，在給出的代碼中，總是有一些蛛絲馬跡可以讓我們找到突破口的，這些地方一般都會(huì)給出題目所用算法的暗示。如圖1.1所示，如果我們找到實(shí)線的指針，它們分別指向La中的key1結(jié)點(diǎn)（p指針）、key1的前一個(gè)結(jié)點(diǎn)（q指針）、Aj（從key1結(jié)點(diǎn)開(kāi)始的第len個(gè)結(jié)點(diǎn)，r指針）和Lb中的key2的前一個(gè)結(jié)點(diǎn)（s指針），則根據(jù)鏈表操作，用圖中的虛線指針連接，我們就可以把La中從key1

26、結(jié)點(diǎn)開(kāi)始的len個(gè)結(jié)點(diǎn)全部移動(dòng)到Lb鏈表中。因此算法大致如下所示。 找到p和q指針。圖1.1 鏈表結(jié)點(diǎn)移動(dòng) 找到r指針。 找到s指針。 r->next=s->next（把Aj結(jié)點(diǎn)連接到K2結(jié)點(diǎn)之前）。 s->next=q（把K1結(jié)點(diǎn)連接到原來(lái)Lb中K2結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)的后面）。注意：經(jīng)過(guò)、兩步操作，即實(shí)現(xiàn)了移動(dòng)操作。 要注意的是現(xiàn)在La鏈表已經(jīng)斷開(kāi)，也必須重新連接上。但是注意一下程序，就會(huì)發(fā)現(xiàn)里面有很多判斷，主要是看判斷是否可以移動(dòng)。我們考慮后（也可以看程序）發(fā)現(xiàn)，在以下幾種情況下，操作不能進(jìn)行。 La或Lb是空鏈表。 len表示個(gè)數(shù)的值，因此不能不大于0。 La中不存在ke

27、y1的結(jié)點(diǎn)。 La中從key1結(jié)點(diǎn)開(kāi)始的結(jié)點(diǎn)個(gè)數(shù)小于len個(gè)。 Lb中不存在key2的結(jié)點(diǎn)。（3）現(xiàn)在是看程序結(jié)構(gòu)是不是和我們自己考慮的算法符合。程序段（5）（8）：其中有p指針在向后移動(dòng)，一直到key1為止，因此，它們的功能就是找到指向key1結(jié)點(diǎn)的指針；同時(shí)，另有一個(gè)指針prep一直在p的后面，因此它就是指向key1的前一個(gè)結(jié)點(diǎn)的指針。程序段（10）（13）：其中有一個(gè)k變量，每次循環(huán)后增加1，因此它是一個(gè)計(jì)數(shù)器。通過(guò)計(jì)數(shù)len次，就可以找到從key1結(jié)點(diǎn)開(kāi)始的第len個(gè)結(jié)點(diǎn)。這時(shí)，應(yīng)該有一個(gè)指針（q）同時(shí)移動(dòng)，使得這個(gè)指針就是指向第len個(gè)結(jié)點(diǎn)的指針。程序段（15）（18）：其中有s指針在向后移動(dòng)，一直到key2為止，因此，它們的功能就是找到指向key2的前一個(gè)結(jié)點(diǎn)的指針。程序段（20）（22）：就是移動(dòng)La中的結(jié)點(diǎn)到Lb，并把La中斷開(kāi)的鏈表連接。從上述的分析發(fā)現(xiàn)，程序結(jié)構(gòu)是和我們自己考慮的算法一致的。（4）考慮細(xì)節(jié)，并填空。 我們的目的是找指向第len個(gè)結(jié)點(diǎn)的指針，找到后循環(huán)應(yīng)該結(jié)束，因此，要填k<len。有同學(xué)可能會(huì)考慮填k<=len，這時(shí)，大家可以用一個(gè)實(shí)例試一下。譬如len=3，你會(huì)發(fā)現(xiàn)，指針其實(shí)只要移