計算機等級考試中的數(shù)據(jù)結(jié)構(gòu)

摘 要：由于計算機技術(shù)的廣范普及，越來越多的人報考計算機等級考試，等級考試分為基礎(chǔ)知識和上機操作兩部分，其中基礎(chǔ)知識中的數(shù)據(jù)結(jié)構(gòu)考點，對于非計算機專業(yè)的考生來說是一個難點，本文主要介紹等級考試中如何解決數(shù)據(jù)結(jié)構(gòu)相關(guān)知識點，以便圓滿的結(jié)束考試。

關(guān)鍵詞：計算機等級考試；公共基礎(chǔ)知；數(shù)據(jù)結(jié)構(gòu)

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：1674-7712 （2013） 18-0000-01

一、計算機等級考試的重要性

隨著計算機技術(shù)的迅速發(fā)展，計算機在各個領(lǐng)域的應(yīng)用逐步推廣，操作和應(yīng)用計算機成為人們必須掌握的一種基本技能。一些企事業(yè)部門把計算機理論知識和實踐操作能力作為上崗資格、職稱評定、人員錄用的依據(jù)之一，可見操作和應(yīng)用計算機對于日常生活和工作尤為重要。全國計算機等級考試（National Computer Rank Examination，簡稱NCRE），是經(jīng)原國家教育委員會（現(xiàn)教育部）批準(zhǔn)，由教育部考試中心主辦，面向社會，用于考查應(yīng)試人員計算機應(yīng)用知識與技能的全國性計算機水平考試體系。NCRE考試采用全國統(tǒng)一命題，統(tǒng)一考試的形式。一年組織兩次考試，一般為3月倒數(shù)第一個周六和9月倒數(shù)第二個周六。等級考試分為兩個部分，一是公共基礎(chǔ)知識，二是上機操作，其中公共基礎(chǔ)知識由30分改為40分，上機操作由70分改為60分，二級公共基礎(chǔ)知識分為四個部分：數(shù)據(jù)結(jié)構(gòu)與算法、程序設(shè)計基礎(chǔ)、軟件工基礎(chǔ)、數(shù)據(jù)庫設(shè)計基礎(chǔ)。這里我們僅對數(shù)據(jù)結(jié)構(gòu)常考查知識點進行剖析。

二、數(shù)據(jù)結(jié)構(gòu)知識點剖析

計算機科學(xué)是一門研究用計算機進行信息表示和處理的科學(xué)。這里面涉及到兩個問題：信息的表示，信息的處理。信息的表示又影響到處理信息的程序的效率。隨著計算機的普及，信息量的增加，信息范圍的拓寬，使許多系統(tǒng)程序和應(yīng)用程序的規(guī)模很大，結(jié)構(gòu)又相當(dāng)復(fù)雜。因此，為了編寫出一個“好”的程序，必須分析待處理的對象的特征及各對象之間存在的關(guān)系，這就是數(shù)據(jù)結(jié)構(gòu)這門課所要研究的問題。

數(shù)據(jù)結(jié)構(gòu)在計算機專業(yè)基礎(chǔ)課中也屬于比較難的一門課程，學(xué)習(xí)時不能死記硬背，必須進行理解。數(shù)據(jù)結(jié)構(gòu)在各年等級考試中所占的分值很高，下圖是筆者統(tǒng)計的最近四次二級考試中數(shù)據(jù)結(jié)構(gòu)所占的分值，可以看出，對于總分為40分的基礎(chǔ)知識中，數(shù)據(jù)結(jié)構(gòu)所占的比例是很高的，考生應(yīng)該重視起來。數(shù)據(jù)結(jié)構(gòu)知識的考核點主要有兩部分：（1）棧和隊列：此知識點基本年年出題，可以看作是必考題，一般都是考查相關(guān)概念，棧是后進先出表即FILO表，而隊列是先進先出表即FIFO表，考生只要牢記概念及基本性質(zhì)就可以得滿分。（2）二叉樹性質(zhì)：此知識點基本也是年年出題，可以看作是必考題，主要考查四個性質(zhì)，其中性質(zhì)3考查率比較高。除此之外還有二叉數(shù)的遍歷，排序和查找在考試中也會涉及到，對于二叉數(shù)的遍歷，一般是給出樹求某種遍歷，考生只要熟記三種遍歷的規(guī)則就可以了，排序主要考查時間復(fù)雜度，查找主要考查最壞比較次數(shù)，考生需要認(rèn)真看書并加以理解。

三、經(jīng)典例題

（一）下列關(guān)于棧敘述正確的是（）

A）棧頂元素最先能被刪除；

B）棧頂元素最后才能被刪除；

C）棧底元素永遠(yuǎn)不能被刪除；

D）以上三種說法都不對。

這道題主要考查棧的基本概念，對于概念考生不應(yīng)只是死記，要深刻的理解。棧和隊列都是操作受限的線性表，其中棧是只能在表尾進行插入和刪除操作，表尾端對應(yīng)棧頂，而表頭端對應(yīng)棧底，棧又叫后進先出表（FILO），根據(jù)棧的概念我們可以找出正確答案，A是正確的，棧頂元素最先被刪除，它是后進先出表。

（二）下列關(guān)于二叉樹的敘述中，正確的是（）

A）葉子結(jié)點總是比度為2的結(jié)點少一個；

B）葉子結(jié)點總是比度為2的結(jié)點多一個；

C）葉子結(jié)點數(shù)是度為的結(jié)點數(shù)的兩倍；

D）度為2的結(jié)點數(shù)是度為1的結(jié)點數(shù)的兩倍。

這道題主要考查數(shù)據(jù)結(jié)構(gòu)中二叉數(shù)的性質(zhì)3的應(yīng)用，對于任意一棵二叉數(shù)，度為2的結(jié)點n2個，度為0的結(jié)點n0個，則n0=n2+1。度為0的結(jié)點即為葉子結(jié)點，也就是說葉子結(jié)點永遠(yuǎn)比度為2的結(jié)點多一個，根據(jù)性質(zhì)3，我們可以給出正確答案B。

（二）對下列二叉樹進行前序遍歷的結(jié)果為（）

A）DYBEAFCZX；B）YDEBFZXCA；C）ABDYECFXZ；D）ABCDEFXYZ。

這道題主要考查二叉樹的遍歷，二叉樹的遍歷有三種：前序遍歷、中序遍歷、后序遍歷，其中都是以根結(jié)點為基準(zhǔn)，前序遍歷的規(guī)則是DLR，也就是先遍歷根，再遍歷左子樹，最后遍歷右子樹，對于其子樹也要遵循這個原則。由圖可知A是根，所以先序遍歷應(yīng)該是A-左子樹-右子樹，其中左子樹先序遍歷也應(yīng)該滿足規(guī)則，即BDYE，右子樹先序遍歷是CFXZ，所以綜合起來應(yīng)該是ABDYECFXZ，可知C是正確答案。

四、結(jié)束語

雖然等級考試基礎(chǔ)知識中的數(shù)據(jù)結(jié)構(gòu)有一定的難度，但只要認(rèn)真理解相關(guān)概念，多做題，舉一反三，認(rèn)真做好筆記，考生就會在等級考試中勝出。

參考文獻(xiàn)：

[1]教育部考試中心.全國計算機等級考試二級公共基礎(chǔ)教程[M].北京：高等教育出版社，2007，9.

[2]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京：清華大學(xué)出版社，2001，2.

[作者簡介]董大偉（1977.3-），講師，碩士，研究方向：計算機應(yīng)用。