為五月最后統(tǒng)考拼搏,穩(wěn)做王者看誰與爭鋒?第一章概論 自測題答案 姓名 班級題號四五總分題分3315982015100得分ー、填空題（每空1分共33分）.ー個計算機系統(tǒng)包括硬件系統(tǒng)和軟件系統(tǒng)兩大部分.一臺計算機中全部程序的集合稱為這臺計算機的 軟件資源/（系統(tǒng)）.計算機軟件可以分為系統(tǒng)軟件和應(yīng)用軟件兩大類科學(xué)計算程序包屬于應(yīng)用軟件診斷程序?qū)儆谙到y(tǒng)軟件（工具）.一種用助憶符號來表示機器指令的操作符和操作數(shù)的語言是 匯編語言.數(shù)據(jù)結(jié)構(gòu)是ー門研究非數(shù)值計算的程序設(shè)計問題中計算機的操作對象 以及它們之間的關(guān)系 和運算等的學(xué)科.數(shù)據(jù)結(jié)構(gòu)被形式地定義為(DR)其中D是 數(shù)據(jù)元素 的有限集合R是D上的關(guān)系有限集合.數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)和數(shù)據(jù)的運算這三個方面的內(nèi)容.數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類它們分別是線性結(jié)構(gòu)和非線性結(jié)構(gòu).線性結(jié)構(gòu)中元素之間存在ー對ー關(guān)系樹形結(jié)構(gòu)中元素之間存在ー對多關(guān)系圖形結(jié)構(gòu)中元素之間存在多對多關(guān)系.在線性結(jié)構(gòu)中第一個結(jié)點沒有前驅(qū)結(jié)點其余每個結(jié)點有且只有1個前驅(qū)結(jié)點:最后ー個結(jié)點沒有后續(xù)結(jié)點其余每個結(jié)點有且只有1個后續(xù)結(jié)點.在樹形結(jié)構(gòu)中樹根結(jié)點沒有前驅(qū)結(jié)點其余每個結(jié)點有且只有 1 個前驅(qū)結(jié)點;葉子結(jié)點沒有后續(xù)結(jié)點其余每個結(jié)點的后續(xù)結(jié)點數(shù)可以任意多個.在圖形結(jié)構(gòu)中每個結(jié)點的前驅(qū)結(jié)點數(shù)和后續(xù)結(jié)點數(shù)可以任意多個.數(shù)據(jù)的存儲結(jié)構(gòu)可用四種基本的存儲方法表示它們分別是順序、鏈式、索引和散列.數(shù)據(jù)的運算最常用的有5種它們分別是插入、刪除、修改、査找、排序

.ー個算法的效率可分為時間 效率和空間效率和若干個被調(diào)用的其它函數(shù)組. K00年省統(tǒng)考!!任何ー個C程序都由 和若干個被調(diào)用的其它函數(shù)組成.100年省統(tǒng)考題】變量ー經(jīng)說明就確定該變量的取值范圍(即存儲單元)及確定變量所允許的運算就確定該變量的取值范圍(即存儲單元)及確定變量所允許的運算二、單項選擇題(每小題1分共15分)(B)1.通常所說的主機是指:A)CPUB)CPU和內(nèi)存 〇CPU、內(nèi)存與外存 D)CPU、內(nèi)存與硬盤(C)2.在計算機內(nèi)部一切信息的存取、處理和傳送的形式是:A)ACSII碼B)BCD碼C)二進制 D)十六進制(D)3.軟件與程序的區(qū)別是:A)程序價格便宜、軟件價格昂貴;B)程序是用戶自己編寫的而軟件是由廠家提供的;0程序是用高級語言編寫的而軟件是由機器語言編寫的;D)軟件是程序以及開發(fā)、使用和維護所需要的所有文檔的總稱而程序只是軟件的一部分(C)4.所謂"裸機”是指:A)單片機B)單板機〇不裝備任何軟件的計算機 D)只裝備操作系統(tǒng)的計算機(D)5.應(yīng)用軟件是指:A)所有能夠使用的軟件 B)能被各應(yīng)用單位共同使用的某種軟件C)所有微機上都應(yīng)使用的基本軟件 D)專門為某ー應(yīng)用目的而編制的軟件(*A)6.K00年省統(tǒng)考!]C語言中的常量可分為整型常量、實型常量、字符型常量及(枚舉）四種（A）符號常量 （B）長整型常量（〇邏輯常量（D）二進制整數(shù)（*C）7.編譯程序的功能是:A）發(fā)現(xiàn)源程序中的語法錯誤C）將源程序編譯成目標程序語言程序舉）四種（A）符號常量 （B）長整型常量（〇邏輯常量（D）二進制整數(shù)（*C）7.編譯程序的功能是:A）發(fā)現(xiàn)源程序中的語法錯誤C）將源程序編譯成目標程序語言程序（A）8.系統(tǒng)軟件中最重要的是:A）操作系統(tǒng)B）語言處理系統(tǒng)理系統(tǒng)（C）9.可移植性最好的計算機語言是:A）機器語言 B）匯編語言B）改正源程序中的語法錯誤D）將某一高級語言程序翻譯成另一種高級0工具軟件 D）數(shù)據(jù)庫管0高級語言D）自然語言（B）10.非線性結(jié)構(gòu)是數(shù)據(jù)元素之間存在ー種:A）一對多關(guān)系 B）多對多關(guān)系 C）多對ー關(guān)系 D）ー對ー關(guān)系（C）11.數(shù)據(jù)結(jié)構(gòu)中與所使用的計算機無關(guān)的是數(shù)據(jù)的A）存儲B）物理（C）12.算法分析的目的是:A）找出數(shù)據(jù)結(jié)構(gòu)的合理性0分析算法的效率以求改進結(jié)構(gòu):0邏輯 D）物理和存儲B）研究算法中的輸入和輸出的關(guān)系D）分析算法的易懂性和文檔性（A）13.算法分析的兩個主要方面是:A）空間復(fù)雜性和時間復(fù)雜性0可讀性和文檔性B）正確性和簡明性D）數(shù)據(jù)復(fù)雜性和程序復(fù)雜性（C）14.計算機算法指的是：A）計算方法 B）排序方法0解決問題的有限運算序列 D）調(diào)度方法（B）15.計算機算法必須具備輸入、輸出和 等5個特性A）可行性、可移植性和可擴充性0確定性、有窮性和穩(wěn)定性B）可行性、確定性和有窮性D）易讀性、穩(wěn)定性和安全性三、簡答題（每小題3分共9分）.我們知道計算機只能執(zhí)行機器指令為什么它能運行用匯編語言和高級語言編寫的程序?答:靠匯編程序?qū)R編語言或高級語言翻譯轉(zhuǎn)換為目標程序（即機器語言）.【嚴題集1.2②】數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型兩個概念之間有區(qū)別嗎?答:簡單地說數(shù)據(jù)結(jié)構(gòu)定義了一組按某些關(guān)系結(jié)合在一起的數(shù)組元素數(shù)據(jù)類型不僅定義了一組帶結(jié)構(gòu)的數(shù)據(jù)元素而且還在其上定義了一組操作.簡述線性結(jié)構(gòu)與非線性結(jié)構(gòu)的不同點答：線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是ー對ー的非線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是多對多的四、R00年統(tǒng)考題》閱讀下列C程序段寫出相應(yīng)的執(zhí)行結(jié)果(每小題4分共8分)1.printf("Inputx");scanf("%d"&x);if(x<=30)if(x>20)y=x;elseif(x>10)y=2*x;if(x>0&&x<30)printf("x=%dy=%d"xy);elseprintf("輸入數(shù)據(jù)錯!”)；試寫出當x分別為!88時的執(zhí)行結(jié)果答:運行結(jié)果為:x=18y=36x=8y=運行前的值且從x=30開始為數(shù)據(jù)錯五、【嚴題集1.8④】分析下面各程序段的時間復(fù)雜度(每小題5分共20分)六、設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu)S=(DR)試按各小題所給條件畫出這些邏輯結(jié)構(gòu)的圖示并確定相對于關(guān)系R哪些結(jié)點是開始結(jié)點哪些結(jié)點是終端結(jié)點?(每小題5分共15分).【嚴蔚敏習(xí)題集P71.3②】D={dld2d3d4} R={(dld2)(d2d3)(d3d4))答:dlfd2fd3fd4 dl-無直接前驅(qū)是首結(jié)點 d4ー無直接后繼是尾結(jié)點D={dld2d9}R={(dld2)(dld3)(d3d4)(d3d6)(d6d8)(d4d5)(d6d7)(d8d9))答:此圖為樹形結(jié)構(gòu) dlー無直接前驅(qū)是根結(jié)點 d2d5d7d9ー無直接后繼是葉子結(jié)點D={dld2d9}R={(dld3)(dld8)(d2d3)(d2d4)(d2d5)(d3d9)(d5d6)(d8d9)(d9d7)(d4d7)(d4d6))答:此圖為圖形結(jié)構(gòu) dld2ー無直接前驅(qū)是開始結(jié)點 d6d7ー無直接后繼是終端結(jié)點班級第2章自測卷答案題號班級四五六七總分題分1310101071040100得分ー、填空（每空1分共13分）.【嚴題集2.2①】在順序表中插入或刪除ー個元素需要平均移動表中一半元素具體移動的元素個數(shù)與表長和該元素在表中的位置有關(guān).線性表中結(jié)點的集合是有限的結(jié)點間的關(guān)系是ー對ー的.向ー個長度為n的向量的第i個元素（IWiWn+l）之前插入一個元素時需向后移動n-i+1個元素.向ー個長度為n的向量中刪除第i個元素（IWiWn）時需向前移動n-i個元素.在順序表中訪問任意ー結(jié)點的時間復(fù)雜度均為0（1）因此順序表也稱為隨機存取的數(shù)據(jù)結(jié)構(gòu).【嚴題集2.2①】順序表中邏輯上相鄰的元素的物理位置必定相鄰單鏈表中邏輯上相鄰的元素的物理位置不一定相鄰.【嚴題集2.2①】在單鏈表中除了首元結(jié)點外任ー結(jié)點的存儲位置由其直接前驅(qū)結(jié)點的鏈域的值指示8,在n個結(jié)點的單鏈表中要刪除已知結(jié)點?p需找到它的前驅(qū)結(jié)點的地址其時間復(fù)雜度為〇（n）二、判斷正誤（在正確的說法后面打勾反之打叉）（每小題1分共10分）（X）1.鏈表的每個結(jié)點中都恰好包含一個指針答:錯誤鏈表中的結(jié)點可含多個指針域分別存放多個指針例如雙向鏈表中的結(jié)點可以含有兩個指針域分別存放指向其直接前趨和直接后繼結(jié)點的指針（X）2.鏈表的物理存儲結(jié)構(gòu)具有同鏈表一樣的順序錯鏈表的存儲結(jié)構(gòu)特點是無序而鏈表的示意圖有序（X）3.鏈表的刪除算法很簡單因為當刪除鏈中某個結(jié)點后計算機會自動地將后續(xù)的各個單元向前移動錯鏈表的結(jié)點不會移動只是指針內(nèi)容改變（X）4.線性表的每個結(jié)點只能是ー個簡單類型而鏈表的每個結(jié)點可以是一個復(fù)雜類型錯混淆了邏輯結(jié)構(gòu)與物理結(jié)構(gòu)鏈表也是線性表!且即使是順序表也能存放記錄型數(shù)據(jù)(X)5.順序表結(jié)構(gòu)適宜于進行順序存取而鏈表適宜于進行隨機存取錯正好說反了順序表オ適合隨機存取鏈表恰恰適于"順藤摸瓜”(X)6.順序存儲方式的優(yōu)點是存儲密度大旦插入、刪除運算效率高錯前一半正確但后一半說法錯誤那是鏈式存儲的優(yōu)點順序存儲方式插入、刪除運算效率較低在表長為n的順序表中插入和刪除ー個數(shù)據(jù)元素平均需移動表長一半個數(shù)的數(shù)據(jù)元素(X)7.線性表在物理存儲空間中也一定是連續(xù)的錯線性表有兩種存儲方式順序存儲和鏈式存儲后者不要求連續(xù)存放(X)8.線性表在順序存儲時邏輯上相鄰的元素未必在存儲的物理位置次序上相鄰錯誤線性表有兩種存儲方式在順序存儲時邏輯上相鄰的元素在存儲的物理位置次序上也相鄰(X)9.順序存儲方式只能用于存儲線性結(jié)構(gòu)錯誤順序存儲方式不僅能用于存儲線性結(jié)構(gòu)還可以用來存放非線性結(jié)構(gòu)例如完全ニ叉樹是屬于非線性結(jié)構(gòu)但其最佳存儲方式是順序存儲方式（后一節(jié)介紹）（X）10.線性表的邏輯順序與存儲順序總是一致的錯理由同7鏈式存儲就無需一致三、單項選擇題（每小題1分共10分）（C）1.數(shù)據(jù)在計算機存儲器內(nèi)表示時物理地址與邏輯地址相同并且是連續(xù)的稱之為:（A）存儲結(jié)構(gòu) （B）邏輯結(jié)構(gòu)（C）順序存儲結(jié)構(gòu) （D）鏈式存儲結(jié)構(gòu)（B）2.ー個向量第一個元素的存儲地址是100每個元素的長度為2則第5個元素的地址是（A）110 （B）108 （〇!00 （D）120（A）3.在n個結(jié)點的順序表中算法的時間復(fù)雜度是0（1）的操作是:（A）訪問第i個結(jié)點（IWiWn）和求第i個結(jié)點的直接前驅(qū)（2<iWn）（B）在第i個結(jié)點后插入一個新結(jié)點（IWiWn）（〇刪除第i個結(jié)點（IWiくn）（D）將n個結(jié)點從小到大排序（B）4.向ー個有!27個元素的順序表中插入一個新元素并保持原來順序不變平均要移動個元素（A）8 （B）63.5 （063 （D）7（A）5.鏈接存儲的存儲結(jié)構(gòu)所占存儲空間:分兩部分一部分存放結(jié)點值另一部分存放表示結(jié)點間關(guān)系的指針只有一部分存放結(jié)點值（〇只有一部分存儲表示結(jié)點間關(guān)系的指針（D）分兩部分一部分存放結(jié)點值另一部分存放結(jié)點所占單元數(shù)（B）6.鏈表是ー種采用 存儲結(jié)構(gòu)存儲的線性表;（A）順序（B）鏈式 （C）星式 （D）網(wǎng)狀（D）7.線性表若采用鏈式存儲結(jié)構(gòu)時要求內(nèi)存中可用存儲単元的地址:（A）必須是連續(xù)的 （B）部分地址必須是連續(xù)的一定是不連續(xù)的 （D）連續(xù)或不連續(xù)都可以（B）8.線性表L在 情況下適用于使用鏈式結(jié)構(gòu)實現(xiàn)（A）需經(jīng)常修改L中的結(jié)點值 （B）需不斷對L進行刪除插入（〇L中含有大量的結(jié)點 （D）L中結(jié)點結(jié)構(gòu)復(fù)雜（C）9.單鏈表的存儲密度（A）大于1： （B）等于1； （C）小于1； （D）不能確定（B）10.設(shè)al、a2、a3為3個結(jié)點整數(shù)P034代表地址則如下的鏈式存儲結(jié)構(gòu)稱為P0P0—>al3—>a24—>A3（A）循環(huán)鏈表（B）單鏈表（C）雙向循環(huán)鏈表（D）雙向鏈表四、簡答題（每小題5分共10分）.【嚴題集2.3②］試比較順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)的優(yōu)缺點在什么情況下用順序表比鏈表好?答:①順序存儲時相鄰數(shù)據(jù)元素的存放地址也相鄰（邏輯與物理統(tǒng)ー）;要求內(nèi)存中可用存儲單元的地址必須是連續(xù)的優(yōu)點:存儲密度大（=1?）存儲空間利用率高缺點:插入或刪除元素時不方便②鏈式存儲時相鄰數(shù)據(jù)元素可隨意存放但所占存儲空間分兩部分一部分存放結(jié)點值另一部分存放表示結(jié)點間關(guān)系的指針優(yōu)點:插入或刪除元素時很方便使用靈活缺點:存儲密度小?1）存儲空間利用率低順序表適宜于做査找這樣的靜態(tài)操作;鏈表宜于做插入、刪除這樣的動態(tài)操作若線性表的長度變化不大且其主要操作是查找則采用順序表；若線性表的長度變化較大且其主要操作是插入、刪除操作則采用鏈表.【嚴題集2.1①】描述以下三個概念的區(qū)別:頭指針、頭結(jié)點、首元結(jié)點（第一個元素結(jié)點）在單鏈表中設(shè)置頭結(jié)點的作用是什么?答:首元結(jié)點是指鏈表中存儲線性表中第一個數(shù)據(jù)元素al的結(jié)點為了操作方便通常在鏈表的百元結(jié)點之前附設(shè)ー個結(jié)點稱為頭結(jié)點該結(jié)點的數(shù)據(jù)域中不存儲線性表的數(shù)據(jù)元素其作用是為了對鏈表進行操作時可以對空表、非空表的情況以及對首元結(jié)點進行統(tǒng)ー處理頭指針是指向鏈表屮第一個結(jié)點（或為頭結(jié)點或為首元結(jié)點）的指針若鏈表中附設(shè)頭結(jié)點則不管線性表是否為空表頭指針均不為空否則表示空表的鏈表的頭指針為空這三個概念對單鏈表、雙向鏈表和循環(huán)鏈表均適用是否設(shè)置頭結(jié)點是不同的存儲結(jié)構(gòu)表示同一邏輯結(jié)構(gòu)的問題頭結(jié)點head—>datalink頭指針 首元結(jié)點簡而言之頭指針是指向鏈表中第一個結(jié)點（或為頭結(jié)點或為首元結(jié)點）的指針;頭結(jié)點是在鏈表的首元結(jié)點之前附設(shè)的ー個結(jié)點;數(shù)據(jù)域內(nèi)只放空表標志和表長等信息（內(nèi)放頭指針?那還得另配ー個頭指針!?。。┦自亟Y(jié)點是指鏈表中存儲線性表中第一個數(shù)據(jù)元素al的結(jié)點五、【軟考題】線性表具有兩種存儲方式即順序方式和鏈接方式現(xiàn)有一個具有五個元素的線性表し={2317470531）若它以鏈接方式存儲在下列100?119號地址空間中每個結(jié)點由數(shù)據(jù)（占2個字節(jié)）和指針（占2個字節(jié)）組成如下所示:05U17X23V31Y47100120其中指針XYZ的值分別為多少?該線性表的首結(jié)點起始地址為多少?末結(jié)點的起始地址為多少?（10分）答:X=116Y=0 Z=100 首址=108 末址=112六、閱讀分析題（10分）【嚴題集2.10②】指出以下算法中的錯誤和低效（即費時）之處并將它改寫為?個既正確乂髙效的算法答:錯誤有兩處:①參數(shù)不合法的判別條件不完整例如表長為!0若從第一位置(i=l)刪除10個元素(k=10)要求合理但會被判為非法合法的入口參數(shù)條件為(0<i^a.length)"(0〈k〈a.length-i)應(yīng)將if(i<lIIk<0IIi+k>a.length)returnINFEASIBLE改為:if(!((0〈iくa.length)"(oWkくa.length-i)))returnINFEASIBLE第二個FOR語句中元素前移的次序錯誤應(yīng)將for(j=a.length;j>=i+l;j-)a.elem[j-l]=a.elem[j]：改為for(j>=i+l;j=a.length;j++)a.elem[j-l]=a.elem[j];七、編程題(每題10分共40分).【徐士良題集2002年1月省統(tǒng)考題】寫出在順序存儲結(jié)構(gòu)下將線性表逆轉(zhuǎn)的算法要求使用最少的附加空間解:輸入:長度為n的線性表數(shù)組A(l;n)輸出:逆轉(zhuǎn)后的長度為n的線性表數(shù)組A(l;n)C語言描述如下(其中ET為數(shù)據(jù)元素的類型)：.【嚴題集2.6②】已知L是無表頭結(jié)點的單鏈表且P結(jié)點既不是首元結(jié)點也不是尾元結(jié)點請寫出在P結(jié)點后插入S結(jié)點的核心語句序列答:此題答案不唯一但若從己給定序列中挑選則限制頗多Q=P;(11)P=L;while(P->next!=Q)P=P->next;(10)P=Q：(4)S->next=P->next;P->next=S;3.編寫程序?qū)⑷舾烧麛?shù)從鍵盤輸入以單鏈表形式存儲起來然后計算單鏈表中結(jié)點的個數(shù)（其中指針P指向該鏈表的第一個結(jié)點）注:統(tǒng)計結(jié)點個數(shù)是【省統(tǒng)考樣題】的要求也是教材P604-6計算鏈表長度的要求編程又簡單很容易作為考題解：編寫C程序劃下（已上機通過）：全局變量及函數(shù)提前說明：#include<stdio.h>#include<stdlib.h>typedefstructliuyu{intdata;structliuyu*link;}test;liuyu*p*q*r*head;intm=sizeof(test);voidmain() /?第一步從鍵盤輸入整數(shù)不斷添加到鏈表?/{inti;head=(test*)malloc(m);/*m=sizeof(test);*/p=head;i=0;while(i!=-9999){printf(*/ninputaninteger[stopby'-9999']:");scanf(*%d*&i)；p->data=i; /*inputdataissaved*/p->link=(test*)malloc(m);/*m=sizeof(test));*/q=p;p=p->link;)q->link=NULL; /?原先用p->link=NULL似乎太晚!*/p=head;i=0; /*統(tǒng)計鏈表結(jié)點的個數(shù)并打印出來?/while(p->link!=NULL){printf(細d”p->data);p=p->link;i++；}printf[\nnodenumber=%d\n，zi-1)：/?結(jié)點的個數(shù)不包括ー9999*/}0301陳建武:.程序中統(tǒng)計結(jié)點數(shù)應(yīng)是i個而不是i~l.假設(shè)鏈表表長為ni從〇開始則在統(tǒng)計某ー結(jié)點后i加一此時P已指向下一個結(jié)點第一結(jié)點統(tǒng)計結(jié)束i為1p指向第二結(jié)點即當P指向尾結(jié)點(第n個結(jié)點)時i的值為n-1while循環(huán)條件不符(指針域為null)退出循環(huán)即得統(tǒng)計的結(jié)點數(shù)為n-1.所以i的值就是結(jié)點數(shù)不必再減ー. 請編寫26個字母按特定字母值插入或刪除的完整程序可自行選用順序存儲或鏈表結(jié)構(gòu)答:#include<stdio.h> /?全局變量及函數(shù)提前說明:*/#include<stdlib.h>typedefstructliuyu{chardata;structliuyu*link;}test;liuyu*p*head;intL; /?元素的個數(shù)?/intm=sizeof(test);voidbuildO； /?主函數(shù)中會被調(diào)用的函數(shù)應(yīng)當預(yù)先說明?/voiddisplay();intinsertchar(charchar); /?插入一個字母在第字母Y之前若無字母則加到末尾?/intdelet_char(char); /?刪除元素X注意保存X的前趨元素指針!*/voidbuildO{inti;voidbuildO{inti;head=(test*)malloc(m);p=head;for(i=l;iくL;i++){p->data=i+，a-1;p->link=(test*)malloc(m);p=p->link;}p->data=i+*a'-！.；p->link=NULL;/*字母鏈表的生成?//*m=sizeof(test);*//*'a'也可用其ASCII碼97來表示/*m=sizeof(test));*//? */voiddisplay() /?字母鏈表的輸出?/{p二head;while(p->link!=NULL){printf(*%c*p->data);p=p->link;}printf("%c\n"p->data);/* */intinsert_char(charXcharY) /*插入一個字母X在某個字母Y之前若找不到Y(jié)字母則加到末尾?/{p二head;r=(test*)malloc(m);rー)data二X;if(headー〉data=Y){head=r;r->link=p;}else{while((p->data!=Y)&&(p->link!=NULL)){q=p;p=p->link;}if(p->data==Y){q->link=r;r->link=p;}else{p->link=r;r->link=NULL;}L++；return(0);}/* */intdelet_char(charX)/?刪除元素X注意保存X的前趨元素指針!*/{p二head;if(head->data==X){head=head->link;free(p);}else{while((p->data!=X)&&(p->link!=NULL)){q=P；p=p->link;}if(p->data==X){q->link二p->link;free(p); }elsereturn(-1);L—;return(0);}/? */voidmain(void) /?字母線性表的生成和輸出?/(L=26;buildO;display();printf(insertreturnvalue二%d\ninsert_char('L''W'));display();printfldeletereturnvalue二％d\ndelet_char('z'));display();}附:屏幕上顯示的執(zhí)行結(jié)果是:abcdefghijklmnopqrstuvwxyzinsertreturnvalueニ0abcd9efghijklmnopqrstuvwxyzLdeletereturnvalueニ0abcdefghijklmnopqrstuvwxyL0301陳建武修改意見:一,display0函數(shù)代碼可優(yōu)化為四行voiddisplay() /?字母鏈表的輸出?/{p=head;while(p->link!=NULL)〃改為while(p)因為當p指向尾結(jié)點時p不為null條件成立循環(huán)//printf()然后P被賦值為null此時循環(huán)條件不符退出正好.{printf("%c"p->data);p=p->link;}printf("%c\n"p->data);〃用while(p)此行可刪二.對intinsert_char(charXcharY)若用帶頭結(jié)點的鏈表代碼可減為10行我的程序如下(若參數(shù)沒有slistp代碼要多一行讓q指向頭指針)voidInsertFind(slistpcharinsertcharcharinsertpos)〃字母insertpos前插入字母insertchar{slistppriornewnode;〃ncwnode新結(jié)點pprior為插入位置結(jié)點的直接前驅(qū)newnode=newliuyu;//為新結(jié)點分配內(nèi)存newnode->data=insertchar;〃對結(jié)點數(shù)據(jù)域初始化while(p) 〃當p指向尾結(jié)點時最后一次循環(huán)(pprior=p; 〃pprior從頭指針開始//p從首元結(jié)點開始指向P的直接前驅(qū)p=p->next//p從首元結(jié)點開始不斷前移直至最后p為nullif(p&&(p->data==insertpos))〃當p為null或者結(jié)點p的數(shù)據(jù)域為所要插入的字母break! 〃則退出循環(huán)}newnode->next=pprior->next!〃在找到的位置前插入pprior->next=newnode;}對刪除結(jié)點的操作若有頭結(jié)點同樣可以減少代碼由此可見創(chuàng)建一個頭結(jié)點對簡化程序有很大的幫助.上面的觀點僅供參考不對之處清指教!第3章棧和隊列自測卷答案 姓名 班級題號四五六總分題分151020202015100得分ー、填空題（每空1分共15分）.【李春葆】向量、棧和隊列都是線性結(jié)構(gòu)插入和刪除元素;插入和刪除元素;對于隊列只能在隊尾 插入和隊首刪除元素.棧是ー種特殊的線性表允許插入和刪除運算的一端稱為棧頂不允許插入和刪除運算的一端稱為 棧底.隊列是被限定為只能在表的一端進行插入運算在表的另一端進行刪除運算的線性表.在ー個循環(huán)隊列中隊首指針指向隊首元素的前一個位置.在具有n個單元的循環(huán)隊列中隊滿時共有n-1個元素.向棧中壓入元素的操作是先移動棧頂指針后存入元素.從循環(huán)隊列中刪除ー個元素時其操作是先移動隊首指針后取出元素.K00年統(tǒng)考題》帶表頭結(jié)點的空循環(huán)雙向鏈表的長度等于 0解:二、判斷正誤（判斷下列概念的正確性并作出簡要的說明）（每小題1分共10分）（X）1.線性表的每個結(jié)點只能是ー個簡單類型而鏈表的每個結(jié)點可以是一個復(fù)雜類型錯線性表是邏輯結(jié)構(gòu)概念可以順序存儲或鏈式存儲與元素數(shù)據(jù)類型無關(guān)（x）2.在表結(jié)構(gòu)中最常用的是線性表棧和隊列不太常用錯不一定吧?調(diào)用子程序或函數(shù)常用CPU中也用隊列（ノ）3.棧是ー種對所有插入、刪除操作限于在表的一端進行的線性表是ー種后進先出型結(jié)構(gòu)（V）4.對于不同的使用者ー個表結(jié)構(gòu)既可以是棧也可以是隊列也可以是線性表正確都是線性邏輯結(jié)構(gòu)棧和隊列其實是特殊的線性表對運算的定義略有不同而已（X）5.棧和鏈表是兩種不同的數(shù)據(jù)結(jié)構(gòu)錯棧是邏輯結(jié)構(gòu)的概念是特殊殊線性表而鏈表是存儲結(jié)構(gòu)概念二者不是同類項（X）6.棧和隊列是ー種非線性數(shù)據(jù)結(jié)構(gòu)錯他們都是線性邏輯結(jié)構(gòu)棧和隊列其實是特殊的線性表對運算的定義略有不同而已（V）7.棧和隊列的存儲方式既可是順序方式也可是鏈接方式（V）8.兩個棧共享一片連續(xù)內(nèi)存空間時為提高內(nèi)存利用率減少溢出機會應(yīng)把兩個棧的棧底分別設(shè)在這片內(nèi)存空間的兩端(x)9.隊是?種插入與刪除操作分別在表的兩端進行的線性表是一種先進后出型結(jié)構(gòu)錯后半句不對(X)10.ー個棧的輸入序列是12345則棧的輸出序列不可能是12345錯有可能三、單項選擇題(每小題1分共20分)(B)1.K00年元月統(tǒng)考題!!棧中元素的進出原則是A,先進先出 B.后進先出C.?？談t進 D.棧滿則出(C)2.K李春葆)!若已知一個棧的入棧序列是123n其輸出序列為P1p2p3pn若pl=n則pi為C.n-i+1C.n-i+1D.不確定解釋:當pl=n即n是最先出棧的根據(jù)棧的原理n必定是最后入棧的那么輸入順序必定是12則出棧的序列是n(B)3.K李春葆』判定一個棧ST(最多元素為mO)為空的條件是A.ST->top<>0B,ST->top=0 C.ST->topOmOD.ST->top=mO(B)4.K李春葆』判定一個隊列QU(最多元素為mO)為滿隊列的條件是A.QU->rear—QU->front==mOB.QU->rear—QU->front-1==mOC.QU->front==QU->rear D.QU->front==QU->rear+l(D)5.數(shù)組Q[n]用來表示一個循環(huán)隊列f為當前隊列頭元素的前一位置r為隊尾元素的位置假定隊列中元素的個數(shù)小于n計算隊列中元素的公式為(A)r—f; (B)(n+f—r)%n;(C)n+r—f; (D)(n+r—f)%n6.198初程P71】 從供選擇的答案中選出應(yīng)填入下面敘述 ? 內(nèi)的最確切的解答把相應(yīng)編號寫在答卷的對應(yīng)欄內(nèi)設(shè)有4個數(shù)據(jù)元素al、a2、a3和a4対他們分別進行棧操作或隊操作在進?；蜻M隊操作時按al、a2、a3、a4次序每次進入ー個元素假設(shè)棧或隊的初始狀態(tài)都是空現(xiàn)要進行的棧操作是進棧兩次出棧一次再進棧兩次出棧一次;這時第一次出棧得到的元素是 A第二次出棧得到的元素是 B是;類似地考慮對這四個數(shù)據(jù)元素進行的隊操作是進隊兩次出隊一次再進隊兩次出隊一次；這時第一次出隊得到的元素是 C第二次出隊得到的元素是 D

經(jīng)操作后最后在棧中或隊中的元素還有E個供選擇的答案:A?D：①al②a2 ③a3④a4E：①1 ②2 ③3 @0答:ABCDE=241227.194初程P75】從供選擇的答案中選出應(yīng)填入下面敘述 ? 內(nèi)的最確切的解答把相應(yīng)編號寫在答卷的對應(yīng)欄內(nèi)棧是ー種線性表它的特點是A設(shè)用ー維數(shù)組A[1n]來表示ー?個棧A[n]為棧底用整型變量T指示當前棧頂位置A[T]為棧頂元素往棧中推入(PUSH)ー個新元素時變量T的值B;從棧中彈出(POP)ー個元素時變量T的值C設(shè)?？諘r有輸入序列abc經(jīng)過PUSHPOPPUSHPUSHPOP操作后從棧中彈出的元素的序列是D變量T的值是E供選擇的答案：⑤隨機進出⑥減2A：⑤隨機進出⑥減2C：①加1②減1③不變 ④清0⑤加2D：①a

TOC\o"1-5"\h\zb ②bc ③ca ④ba ⑤cb @acE：①n+1 ②n+2 ③n④n-1 ⑤n-2答案:ABCDE=22164注意向地址的高端生長稱為向上生成堆棧;向地址低端生長叫向下生成堆棧本題中底部為n向地址的低端遞減生成稱為向下生成堆棧8.191初程P77】從供選擇的答案中選出應(yīng)填入下面敘述 ? 內(nèi)的最確切的解答把相應(yīng)編號寫在答卷的對應(yīng)欄內(nèi)在做進棧運算時應(yīng)先判別棧是否A!在做退棧運算時應(yīng)先判別棧是否B當棧中元素為n個做進棧運算時發(fā)生上溢則說明該棧的最大容量為C為了增加內(nèi)存空間的利用率和減少溢出的可能性山兩個棧共享一片連續(xù)的內(nèi)存空間時應(yīng)將兩棧的D 分別設(shè)在這片內(nèi)存空間的兩端這樣只有當E時ォ產(chǎn)生上溢供選擇的答案:AB：①空②滿C：①nT②nD： ①長度 ②深度③上溢④下溢③n+1 ④n/2③棧頂 ④棧底E：①兩個棧的棧頂同時到達?？臻g的中心點②其中一個棧的棧頂?shù)竭_?？臻g的中心點③兩個棧的棧頂在達?？臻g的某一位置相遇④兩個棧均不空且ー個棧的棧頂?shù)竭_另ー個棧的棧底答案:ABCDE=21243四、簡答題（每小題4分共20分）.【嚴題集3.2①和3.11①】說明線性表、棧與隊的異同點劉答:相同點:都是線性結(jié)構(gòu)都是邏輯結(jié)構(gòu)的概念都可以用順序存儲或鏈表存儲;棧和隊列是兩種特殊的線性表即受限的線性表只是對插入、刪除運算加以限制不同點：①運算規(guī)則不同線性表為隨機存取而棧是只允許在一端進行插入、刪除運算因而是后進先出表LIFO;隊列是只允許在一端進行插入、另一端進行刪除運算因而是先進先出表FIFO②用途不同堆棧用于子程調(diào)用和保護現(xiàn)場隊列用于多道作業(yè)處理、指令寄存及其他運算等等.【統(tǒng)考書P604T1難于嚴題集3.1①】設(shè)有編號為124的四輛列車順序進入一個棧式結(jié)構(gòu)的車站具體寫出這四輛列車開出車站的所有可能的順序劉答：至少有14種①全進之后再出情況只有1種:4321②進3個之后再出的情況有3種34234314③進2個之后再出的情況有5種2431 2341 213421432134④進1個之后再出的情況有5種431213421341243.【劉自編】假設(shè)正讀和反讀都相同的字符序列為"回文"例如'abba"和‘a(chǎn)bcba,是回文'abcde,和‘a(chǎn)babab,則不是回文假設(shè)一字符序列已存入計算機請分析用線性表、堆棧和隊列等方式正確輸出其回文的可能性?答:線性表是隨機存儲可以實現(xiàn)靠循環(huán)變量(j-)從表尾開始打印輸出;堆棧是后進先出也可以實現(xiàn)靠正序入棧、逆序出棧即可;隊列是先進先出不易實現(xiàn)哪種方式最好要具體情況具體分析若正文在機內(nèi)已是順序存儲則直接用線性表從后往前讀取即可或?qū)⒍褩ｍ旈_到數(shù)組末尾然后直接用POP動作實現(xiàn)(但堆棧是先減后壓還是 )若正文是單鏈表形式存儲則等同于隊列需開輔助空間可以從鏈首開始入棧全部壓入后再依次輸出.【統(tǒng)考書P604-13］順序隊的"假溢出"是怎樣產(chǎn)生的?如何知道循環(huán)隊列是空還是滿?答;一般的ー維數(shù)組隊列的尾指針已經(jīng)到了數(shù)組的上界不能再有入隊操作但其實數(shù)組中還有空位置這就叫"假溢出"采用循環(huán)隊列是解決假溢出的途徑另外解決隊滿隊空的辦法有三:①設(shè)置一個布爾變量以區(qū)別隊滿還是隊空;②浪費ー個元素的空間用于區(qū)別隊滿還是隊空③使用ー個計數(shù)器記錄隊列中元素個數(shù)(即隊列長度)我們常采用法②即隊頭指針、隊尾指針中有一個指向?qū)嵲囟愆`個指向空閑元素判斷循環(huán)隊列隊空標志是:f=rear 隊滿標志是:f=(r+l)%N5.【統(tǒng)考書P604-14I設(shè)循環(huán)隊列的容量為40(序號從0到39)現(xiàn)經(jīng)過一系列的入隊和出隊運算后有①front=llrear=19;②front=19rear=ll;問在這兩種情況下循環(huán)隊列中各有元素多少個?答:用隊列長度計算公式:(N+r-f)%N①L=(40+19-11)%40=8 ②L=(40+11-19)%40=32五、閱讀理解(每小題5分共20分至少要寫出思路).【嚴題集3.7①】按照四則運算加、減、乘、除和幕運算(t)優(yōu)先關(guān)系的慣例并仿照教材例3-2的格式畫出對下列算術(shù)表達式求值時操作數(shù)棧和運算符棧的變化過程：A-BXC/D+EtF答：.【嚴題集3.3②】寫出下列程序段的輸出結(jié)果(棧的元素類型SElemType為char)voidmain(){StackS;Charxy;InitStack(S);X='c';y='k，;Push(Sx);Push(S'a');Push(Sy)；Pop(Sx);Push(S't');Push(Sx);Pop(Sx);Push(S'sD；while(!StackEmpty(S)){Pop(Sy);printf(y);};Printf(x);)答:輸出為“stack”.【嚴題集3.12②】寫出下列程序段的輸出結(jié)果(隊列中的元素類型QElemType為char)voidmain(){QueueQ;InitQueue(Q);Charx='e';y='c';EnQueue(Q'h');EnQueue(Q'r');EnQueue(Q'y');DeQueue(Qx);EnQueue(Qx);DeQueue(Qx);EnQueue(Q'a');while(!QueueEmpty(Q)){DeQueue(Qy);printf(y);};Printf(x);}答:輸出為"char".【嚴題集3.13②】簡述以下算法的功能(棧和隊列的元素類型均為int)voidalgo3(Queue&Q){StackS;intd;InitStack(S);while(!QueueEmpty(Q)){DeQueue(Qd);Push(Sd):}；while(!StackEmpty(S)){Pop(Sd);EnQueue(Qd);答:該算法的功能是:利用堆棧做輔助將隊列中的數(shù)據(jù)元素進行逆置六、算法設(shè)計（每小題5分共15分至少要寫出思路）.【李春葆及嚴題集3./r/