【正文】 素，其儲(chǔ)存位置（又稱(chēng)物理位置）不一定相鄰，數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域確定的。但由循環(huán)鏈表的特點(diǎn)可以看出，在對(duì)循環(huán)鏈表進(jìn)行插入和刪除過(guò)程中，實(shí)現(xiàn)了空表和非空表的運(yùn)算統(tǒng)一。2） 循環(huán)鏈表中最后一個(gè)結(jié)點(diǎn)的指針域不為空，而是指向表頭結(jié)點(diǎn)。7） 線(xiàn)性鏈表的排序。3） 將兩個(gè)線(xiàn)性鏈表按要求合并成一個(gè)線(xiàn)性鏈表。為了存儲(chǔ)線(xiàn)性表中的每一個(gè)元素，一方面要存出數(shù)據(jù)元素的值，另一方面要存儲(chǔ)各數(shù)據(jù)元素之間的前后件關(guān)系。所以只有選項(xiàng)D正確。提示：2007年4月真題選擇題第5題屬該題的類(lèi)似題目。所謂循環(huán)隊(duì)列，就是將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏輯上的環(huán)狀空間，供隊(duì)列循環(huán)使用。因此，隊(duì)列又稱(chēng)為“先進(jìn)先出”（First In First Out FIFO）的線(xiàn)性表。 提示：2008年4月真題選擇題第7題屬該題的類(lèi)似題目。即棧是按照“先進(jìn)后出”（First In Last “Out, FILO”）的原則組織數(shù)據(jù)的，因此，棧也被稱(chēng)為“先進(jìn)后出”表。 棧及其基本運(yùn)算216。 由此可以看出，在線(xiàn)性表的存儲(chǔ)結(jié)構(gòu)中，其前后件兩個(gè)元素在存儲(chǔ)空間中的緊鄰的， 且前后元素一定存儲(chǔ)在后件元素的前面。就稱(chēng)為非線(xiàn)性結(jié)構(gòu)。 如果一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)滿(mǎn)足下列兩個(gè)條件： 1）有且只有一個(gè)根結(jié)點(diǎn) 2）每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有有一個(gè)后件。數(shù)據(jù)結(jié)構(gòu)除了可用二元關(guān)系表示外，還可以用直觀(guān)的圖形表示。 2007年9月真題選擇題第5題考察程序的執(zhí)行效率也數(shù)據(jù)結(jié)構(gòu)的關(guān)系。所以選項(xiàng)C為正確答案。鏈接。（1）數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。2006年9月真題選擇題第7題。（1）算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量。二級(jí)VF知識(shí)點(diǎn) 第1章 基本數(shù)據(jù)結(jié)構(gòu)與算法1. 算法的基本概念 算法的指解題方案的準(zhǔn)確而完整的描述。算法的工作量用算法在所執(zhí)行的基本運(yùn)算次數(shù)來(lái)度量，而算法所執(zhí)行的基本運(yùn)算次數(shù)是問(wèn)題規(guī)模的函數(shù)，即 算法的工作量=f（n)其中N是問(wèn)題的規(guī)模。2007年4月真題選擇題第1題屬該題的類(lèi)似題目2007年4月真題選擇題第11題考察算法的特征。 一個(gè)數(shù)據(jù)結(jié)構(gòu)應(yīng)包含以下兩方面的信息： 1） 表示數(shù)據(jù)元素的信息； 2） 表示各數(shù)據(jù)元素之間的前后件關(guān)系。索引等?！?】 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指（ ） A) 存儲(chǔ)在外存中的數(shù)據(jù) B) 數(shù)據(jù)所占的存儲(chǔ)空間量 C) 數(shù)據(jù)在計(jì)算機(jī)中的順序存儲(chǔ)方式 D) 數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示 答案： D 解析：數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，也稱(chēng)為數(shù)據(jù)的物理結(jié)構(gòu)，它指的是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間的中的存放形式。2. 數(shù)據(jù)結(jié)構(gòu)的圖形表示【】 下列敘述中，正確的是（ ） A)一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)只能有一種存儲(chǔ)結(jié)構(gòu) B)數(shù)據(jù)的邏輯結(jié)構(gòu)屬于線(xiàn)性結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)屬于非線(xiàn)性結(jié)構(gòu) C)一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu)，且各種存儲(chǔ)結(jié)構(gòu)不影響數(shù)據(jù)處理的效率 D)一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu)，且各種存儲(chǔ)結(jié)構(gòu)影響數(shù)據(jù)處理的效答案：D解析：數(shù)據(jù)的邏輯結(jié)構(gòu)是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。在數(shù)據(jù)結(jié)構(gòu)的圖形表示中，對(duì)于數(shù)據(jù)集合中的每一個(gè)數(shù)據(jù)元素用中間標(biāo)有元素指的方框表示，一般稱(chēng)之為數(shù)據(jù)結(jié)點(diǎn)（簡(jiǎn)稱(chēng)為結(jié)點(diǎn)）。 則稱(chēng)該數(shù)據(jù)結(jié)構(gòu)為線(xiàn)性結(jié)構(gòu)。 線(xiàn)性表及其順序存儲(chǔ)結(jié)構(gòu) 1. 線(xiàn)性表的基本概念 線(xiàn)性表是有n（n≥0）個(gè)數(shù)據(jù)元素 a1,a2,...,an 組成的一個(gè)有限序列，表中的每一個(gè)數(shù)據(jù)元素，除了第一個(gè)外，有且只有一個(gè)前件，除了最后一個(gè)外，有且只有一個(gè)后件，即線(xiàn)性表或是一個(gè)空表。 3. 線(xiàn)性表的插入、刪除運(yùn)算下面討論線(xiàn)性表在順序存儲(chǔ)結(jié)構(gòu)下的插入與刪除的問(wèn)題。 隊(duì)列及其基本運(yùn)算1. 及其基本運(yùn)算 棧（stack）是限定在一端進(jìn)行插入和刪除運(yùn)算的線(xiàn)性表。 棧的基本運(yùn)算有三種： 入棧、出棧、和讀棧頂元素。 （1） 隊(duì)列的基本概念隊(duì)列是指允許在一端進(jìn)行插入，而在另一端進(jìn)行刪除的線(xiàn)性表。退隊(duì)←a1 a2 a3 an←入隊(duì)隊(duì)列的基本結(jié)構(gòu)如圖11所示。在循環(huán)隊(duì)列中，用隊(duì)尾指針rear指向隊(duì)列中的隊(duì)尾元素，用排頭指針front指向排頭元素的前一個(gè)位置，因此，從排頭指針front指向最后一個(gè)位置直到隊(duì)尾指針rear指向的位置之間，所有的元素均為隊(duì)列中的元素?！纠?7】 下列說(shuō)法中，正確的是（ ）。 提示：2007年9月真題填空題第3題考察循環(huán)隊(duì)列的存儲(chǔ)結(jié)構(gòu)。為此目的，將存儲(chǔ)空間中的每一個(gè)存儲(chǔ)節(jié)點(diǎn)分為兩部分：一部分用于存儲(chǔ)數(shù)據(jù)元素的值，稱(chēng)之為數(shù)據(jù)域；另一部分用于存放下一個(gè)數(shù)據(jù)元素的存儲(chǔ)序號(hào)（即存儲(chǔ)節(jié)點(diǎn)的地址），即指向后件節(jié)點(diǎn)，稱(chēng)為指針域。4） 將一個(gè)線(xiàn)性鏈表按要求進(jìn)行分解。8） 線(xiàn)性鏈表的查找。即循環(huán)鏈表中，所有結(jié)點(diǎn)的指針構(gòu)成了一個(gè)環(huán)狀鏈?！纠?8】 下列對(duì)于線(xiàn)性鏈表的描述中正確的是（ ）。 樹(shù)和二叉樹(shù) 樹(shù)的基本概念 樹(shù)是一種簡(jiǎn)單的非線(xiàn)性結(jié)構(gòu)。 性質(zhì)2 深度為m的二叉樹(shù)最多有2m1個(gè)結(jié)點(diǎn)。完全二叉樹(shù)：除最后一層外，每一層上的節(jié)點(diǎn)數(shù)都達(dá)到最大值；在最后一層上只缺少右邊的若干結(jié)點(diǎn)。如果從根節(jié)點(diǎn)開(kāi)始，按層序（每一層從左到右）用自然數(shù)1，2，…，n給結(jié)點(diǎn)編號(hào)，則對(duì)于編號(hào)為k（k=1，2，…，n）的結(jié)點(diǎn)有以下結(jié)論：若k=1，則該結(jié)點(diǎn)為根節(jié)點(diǎn)，他沒(méi)有父節(jié)點(diǎn)，若k＞1，則該結(jié)點(diǎn)的父節(jié)點(diǎn)編號(hào)為［k/2］。 答案：350個(gè)。 解析：滿(mǎn)二叉樹(shù)是相同深度的二叉樹(shù)中結(jié)點(diǎn)最多的一棵，所以由性質(zhì)2可知，深度為5的二叉樹(shù)最多有251=31個(gè)結(jié)點(diǎn)。 與線(xiàn)性鏈表類(lèi)似，用于存儲(chǔ)二叉樹(shù)中各元素的存儲(chǔ)結(jié)點(diǎn)也由兩部分組成；數(shù)據(jù)域和指針域。各個(gè)遍歷過(guò)程描述如下：（1） 前序遍歷（DLR）若二叉樹(shù)為空，則結(jié)束返回，否則：訪(fǎng)問(wèn)根節(jié)點(diǎn)；前序遍歷左子樹(shù)；前序遍歷右子樹(shù)。FECBA A）ABCDEF B) DBAECF C) BCDEFA D) DBEFCA D答案：D。故訪(fǎng)問(wèn)順序?yàn)椋篋→B→E→F→C→A?！纠?12】 對(duì)長(zhǎng)度為n的線(xiàn)性表進(jìn)行順序查找，在最壞的情況下所需要的比較次數(shù)是（ ）。 題目中的線(xiàn)性表的長(zhǎng)度為n，則在最壞情況下，需要比較n次。 這個(gè)過(guò)程一直進(jìn)行到查找成功或子表長(zhǎng)度為0（說(shuō)明現(xiàn)行表中沒(méi)有這個(gè)元素）為止。重要知識(shí)點(diǎn)216。然后從后往前掃描剩下的線(xiàn)性表，同樣，在掃描過(guò)程中主次比較兩個(gè)相鄰元素的大小。（2） 快速排序法快速排序法也會(huì)死一種交換類(lèi)排序方法，但由于它的排序速度比較快，因此稱(chēng)為快速排序法?！?13】 在最壞情況下，冒泡排序法需要的比較次數(shù)為 。（2） 希爾排序法 希爾排序法屬于插入類(lèi)排序，其基本思想為：將整個(gè)無(wú)序序列分割成若干小的子序列分別進(jìn)行插入排序。反復(fù)做第二部，知道剩下的子序列為空為止。（ ）。A）在隊(duì)列中只能插入數(shù)據(jù) B）在隊(duì)列中只能刪除數(shù)據(jù)C）隊(duì)列是“先進(jìn)先出”的線(xiàn)性表 D）隊(duì)列是“先進(jìn)后出”的線(xiàn)性表 ，葉結(jié)點(diǎn)的個(gè)數(shù)為（ ）。 A）2h1 B）2h C）2h+1 D）h+1 ，在最壞情況下，下列各排序法所對(duì)應(yīng)的比較次數(shù)中正確的是（ ）。,前序遍歷結(jié)果為ABDECF,則后序遍歷結(jié)果為 稱(chēng)為線(xiàn)性表的長(zhǎng)度。 要形成良好的程序設(shè)計(jì)風(fēng)格，主要應(yīng)注重和考慮下屬一些因素:源程序文檔化、數(shù)據(jù)說(shuō)明方法、語(yǔ)句的結(jié)構(gòu)以及輸入和輸出。 面向?qū)ο蠓椒ǖ幕靖拍罱Y(jié)構(gòu)化程序設(shè)計(jì)方法的主要原則為：1）自頂向下：程序設(shè)計(jì)時(shí)，應(yīng)先考慮總體，后考慮細(xì)節(jié)；先考慮全局目標(biāo)，后考慮局部目標(biāo)。4）限制使用GOTO語(yǔ)句?！纠?2】 下面對(duì)于結(jié)構(gòu)化程序設(shè)計(jì)方法的主要原則描述錯(cuò)誤的是（ ）。 穩(wěn)定性好。面向?qū)ο蠓椒ǖ幕靖拍蠲嫦驅(qū)ο蟮某绦蛟O(shè)計(jì)方法中涉及的對(duì)象是系統(tǒng)中用來(lái)描述客觀(guān)事物的一個(gè)實(shí)體，是構(gòu)成系統(tǒng)的一個(gè)基本單位，它由一組表示其靜態(tài)特征的屬性和它可執(zhí)行的一組操作組成?？陀^(guān)世界中的實(shí)體通常既具有靜態(tài)的屬性又具有動(dòng)態(tài)的行為，因此，面向?qū)ο蠓椒▽W(xué)中的對(duì)象是由描述該對(duì)象屬性的數(shù)據(jù)以及可以對(duì)這些數(shù)據(jù)施加的所有操作封裝在一起構(gòu)成的統(tǒng)一體。操作的過(guò)程對(duì)外是封閉的，即用戶(hù)只能看到這一操作實(shí)施后的結(jié)果。類(lèi)同對(duì)象一樣，包括一組數(shù)據(jù)屬性和在數(shù)據(jù)上的一組合法操作。一個(gè)消息有以下三部分組成：接收消息的對(duì)象的名稱(chēng)。繼承是使用已有的類(lèi)定義作為基礎(chǔ)，建立新類(lèi)的定義技術(shù)。這種層次結(jié)構(gòu)系統(tǒng)的一個(gè)重要性質(zhì)就是繼承，一個(gè)類(lèi)直接繼承其父類(lèi)的描述（數(shù)據(jù)和操作）或特性，子類(lèi)自動(dòng)地共享基類(lèi)中定義的數(shù)據(jù)和方法。 答案：對(duì)象。 答案：繼承。A）輸入、處理、輸出 B)樹(shù)形、網(wǎng)形、環(huán)形C）順序、選擇、循環(huán) D）主程序、子程序、函數(shù)（ ）。 A）可靠性 B）可重用性 C）可移植性 D）可修改性（ ）實(shí)現(xiàn)的。，而對(duì)象是類(lèi)的 。 （2）軟件危機(jī)與軟件工程軟件工程概念的出現(xiàn)源自軟件危機(jī)。2） 軟件開(kāi)發(fā)成本和進(jìn)度無(wú)法控制。軟件工程就是試圖用工程、科學(xué)和數(shù)學(xué)的原理與方法研制、維護(hù)計(jì)算機(jī)軟件的有關(guān)技術(shù)及管理方法?！边@些主要思想都是強(qiáng)調(diào)在軟件開(kāi)發(fā)過(guò)程中需要應(yīng)用工程化的原則。把需求分析、可行性研究、工程審核、質(zhì)量監(jiān)督等工程化的概念引入到軟件生產(chǎn)中，以期達(dá)到工程項(xiàng)目的三個(gè)基本要素（進(jìn)度、經(jīng)費(fèi)和質(zhì)量）的目標(biāo)。所以，軟件工程的過(guò)程是將軟件工程的方法和工具綜合起來(lái)，已達(dá)到合理、及時(shí)地進(jìn)行計(jì)算機(jī)軟件開(kāi)發(fā)的目的。確定待開(kāi)發(fā)軟件形同的開(kāi)發(fā)目標(biāo)和總的要求，給出它的功能、性能、可靠性以及接口等方面的可能方案，制定完成開(kāi)發(fā)任務(wù)的實(shí)施計(jì)劃。系統(tǒng)設(shè)計(jì)人員和程序設(shè)計(jì)人員應(yīng)該在反復(fù)理解軟件需求的基礎(chǔ)上，給出軟件的結(jié)構(gòu)、模塊的劃分、功能的分配以及處理流程。把軟件設(shè)計(jì)轉(zhuǎn)換成計(jì)算機(jī)可以接受的程序代碼。將已交付的軟件投入運(yùn)行，并在運(yùn)行使用中不斷地維護(hù)，根據(jù)新提出的需求進(jìn)行必要而且可能的擴(kuò)充和刪改。1） 軟件工程的原則。軟件開(kāi)發(fā)工具的完善和發(fā)展獎(jiǎng)促進(jìn)軟件開(kāi)發(fā)方法的進(jìn)步和完善，促進(jìn)軟件開(kāi)發(fā)的高速度和高質(zhì)量。計(jì)算機(jī)輔助軟件工程（Computer Aided Software Engineering,CASE）是當(dāng)前軟件開(kāi)發(fā)環(huán)境中富有特色的研究工作和發(fā)展方向?！。茫┸浖芷谑侵杠浖a(chǎn)品從考慮其概念開(kāi)始到該軟件不能使用位置的整個(gè)時(shí)期。選項(xiàng)Ｂ，根據(jù)“軟件危機(jī)的主要表現(xiàn)”可知此選項(xiàng)正確?！　　　⊥ㄟ^(guò)以上分析，得出正確答案為選項(xiàng)Ｄ?！　。茫┸浖こ讨饕墙鉀Q軟件開(kāi)發(fā)過(guò)程中的技術(shù)問(wèn)題?！纠常场俊　≤浖浅绦?、數(shù)據(jù)和相關(guān)文檔的集合，但是它只是　　　實(shí)體。Ａ）軟件交付使用后還需要進(jìn)行維護(hù)。　　答案：Ａ。軟件維護(hù)已知持續(xù)到軟件生命周期的結(jié)束。需求分析將創(chuàng)建所需的數(shù)據(jù)模型、功能模型和控制模型。涉及的主要任務(wù)是立獲取用戶(hù)需求的方法構(gòu)架，并支持和監(jiān)控需求獲取的過(guò)程。結(jié)構(gòu)化分析方法是結(jié)構(gòu)化程序設(shè)計(jì)理論在軟件需求分析階段的運(yùn)用。數(shù)據(jù)流圖（Data Flow Diagram ,DFD）是描述數(shù)據(jù)處理過(guò)程的工具，是需求理解的邏輯模型的圖形表示，她直接支持系統(tǒng)的功能建模。建立數(shù)據(jù)流圖的步驟如下：１） 由外向里，先畫(huà)系統(tǒng)的輸入輸出，再畫(huà)系統(tǒng)的輸入輸出，再畫(huà)系統(tǒng)的內(nèi)部；２） 自頂向下，順序完成頂層、中間層、底層數(shù)據(jù)流圖；３） 逐層分解。通常數(shù)據(jù)字典包含的信息有：名稱(chēng)、別名、何處使用/如何使用、內(nèi)容描述及補(bǔ)充信息等。 解析：有需求分析的相關(guān)概念和方法可知，需求分析的任務(wù)是發(fā)現(xiàn)需求、求精、建模和定義需求，因此，需求分析就是為了確定軟件系統(tǒng)的功能。軟件設(shè)計(jì)是一個(gè)迭代的過(guò)程，其一般過(guò)程是：先進(jìn)行高層次的結(jié)構(gòu)設(shè)計(jì)；后進(jìn)行低層次的過(guò)程設(shè)計(jì)；穿插進(jìn)行數(shù)據(jù)設(shè)計(jì)和接口設(shè)計(jì)。模塊化是指把一個(gè)待開(kāi)發(fā)的軟件分解成若干小的簡(jiǎn)單的部分，每個(gè)模塊可以完成一個(gè)特定的子功能，各個(gè)模塊可以按一定的方法組裝起來(lái)成為一個(gè)整體，從而實(shí)現(xiàn)整個(gè)系統(tǒng)的功能。模塊獨(dú)立性是指在每個(gè)模塊之完成系統(tǒng)要求的獨(dú)立的子功能，并且與其他模塊的聯(lián)系最少且接口簡(jiǎn)單。按內(nèi)聚性由弱到強(qiáng)排列，內(nèi)聚可以分為下列幾種：偶然內(nèi)聚、邏輯內(nèi)聚、時(shí)間內(nèi)聚、過(guò)程內(nèi)聚、通信內(nèi)聚、順序內(nèi)聚以及功能內(nèi)聚。遵循的原則——高內(nèi)聚低耦合。２） 數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫(kù)設(shè)計(jì)。經(jīng)常使用的結(jié)構(gòu)圖有四種模塊類(lèi)型：傳入模塊、傳出模塊、變換模塊和協(xié)調(diào)模塊。面向數(shù)據(jù)流設(shè)計(jì)方法的實(shí)施要點(diǎn)和設(shè)計(jì)過(guò)程有以下幾步：１） 分析、確認(rèn)數(shù)據(jù)流圖的類(lèi)型，區(qū)分是事務(wù)型還是變換型。４） 根據(jù)設(shè)計(jì)準(zhǔn)則對(duì)產(chǎn)生的結(jié)構(gòu)進(jìn)行細(xì)化和求精。２） 模塊規(guī)模適中。３） 深度、寬度、扇出和扇入適當(dāng)。對(duì)于那些不滿(mǎn)足這一條件的軟件結(jié)構(gòu)，修改的辦法是將判定點(diǎn)上移，或者將那些在作用范圍內(nèi)但是不再控制范圍內(nèi)的模塊移到控制范圍以?xún)?nèi)。７） 設(shè)計(jì)功能可預(yù)測(cè)的模塊。圖形工具：程序流程圖、NS、PAD及HIPO。語(yǔ)言工具：PDL（偽碼）。 解析：分析本題的四個(gè)選項(xiàng)如下： 選項(xiàng)A,偶然內(nèi)聚是指一個(gè)模塊內(nèi)的各處理元素之間沒(méi)有任何聯(lián)系。這是最強(qiáng)的內(nèi)聚。 1973年，Nossi和Shneiderman提出了用方框圖來(lái)代替