最新計算機軟件技術(shù)基礎(chǔ)試題庫

1、精品文檔(9)精品文檔、單項選擇題一個算法應(yīng)該是（A）程序B）問題求解步驟的描述D) A 和 CC）要滿足五個基本屬性算法指的是（A計算機程序B）解決問題的計算方法C）排序算法D）解決問題的有限運算序列。與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、個數(shù)無關(guān)的是數(shù)據(jù)的（A）存儲結(jié)構(gòu)B）邏輯結(jié)構(gòu)C)算法D）操作從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（兩大類。A）動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)B)順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)C）線性結(jié)構(gòu)、非線性結(jié)構(gòu)D)初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)）。F列敘述中正確的是（一個邏輯數(shù)據(jù)結(jié)構(gòu)只能有一種存儲結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)屬于線性結(jié)構(gòu)，存儲結(jié)構(gòu)屬于非線性結(jié)構(gòu)C)一個邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲結(jié)構(gòu),且各種存儲結(jié)構(gòu)不影響數(shù)

2、據(jù)處理的效率一個邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲結(jié)構(gòu),且各種存儲結(jié)構(gòu)影響數(shù)據(jù)處理的效率數(shù)據(jù)的基本單位是（A）數(shù)據(jù)項B）數(shù)據(jù)類型C）數(shù)據(jù)元素D）數(shù)據(jù)變量F列程序的時間復(fù)雜度為（i=0 ； s=0;while ( s<n) i+ ； s=s+i ； (8)A) O( n )B) O ( 2n)C) O( n)D) O (n2)F列程序段的漸進時間復(fù)雜度為（for( int i=1;i<=n;i+)for( int j=1;j<= m; j+)Aij = i*j ;A） O（m2）程序段如下:B) O(n2)C) O(m*n)D) (m+n)sum=0 ；for(i=1;i<=n

3、;i+)for(j=1;j<=n ;j+)sum+ ；精品文檔(10)其中n為正整數(shù)，則最后一行的語句頻度在最壞情況下是（3C） O（n ）A) O(n)B) O(nlogn)2D) O(n )在下面的程序段中，對 x的賦值語句的頻度為（for ( i=1; i>=n ;i+)for(j=1;j>=n ;j+)精品文檔x:=x+1;A) O(2 n)B)O( n)2C) O(n )D) O(log 2n)(11)程序段for(i:=n-1;i<=1;i-)for(j:=1; j>=i ;j+)if(aj>aj+1)t=aj;aj= aj+1;aj+1= t;

4、 (12)其中A) O(n )n為正整數(shù)，則最后一行的語句頻度在最壞情況下是（3C） O（n ）B) O(nlogn)2D) O(n )設(shè)有一個遞歸算法如下:int fact(i nt n)/*大于等于0*/if ( n<=0 )retur n1else returnn *fact (n-1)則計算fact（n）需要調(diào)用該函數(shù)的次數(shù)為(13)A) nB) n+1C) n+2D) n-1下述程序段中語句的頻度是（s=0;for(i=1;i<m;i+)for(j=0;j<=i;j+)(14)(1)A) (m 1)(m -1)s+=j;m( m -1)B)-2C)(m 2)(m 1

5、)m( m 1)D) 2若某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素， 省運算時間的存儲方式是（A）單鏈表C）雙鏈表則最節(jié)B）僅有頭指針的單循環(huán)鏈表D）僅有尾指針的單循環(huán)鏈表求循環(huán)鏈表中當(dāng)前結(jié)點的后繼和前驅(qū)的時間復(fù)雜度分別是（A) O(n)和 O(1)B) O(1)和 O(1)C) O(1)和 O(n)D) O(n)和 O(n)(15)求單鏈表中當(dāng)前結(jié)點的后繼和前驅(qū)的時間復(fù)雜度分別是（A) O ( n )和 0( 1)B) O (1 )和 0( 1)C) O (1 )和 O (n)D) O(n) 和 O( n)（16）非空的單循環(huán)鏈表的頭指針為head尾指針為rea

6、r,則下列條件成立的是（）。A) rear->next= =headB) rear->next->next= =headC) head->next= =rearD) head->next->next= =rear(17)從一個長度為 n 的順序表中刪除第 i個元素（1w i w n）時，需向前移動的元素的個數(shù)是）。(18)A）n-iB）n-i+1已知一個有序表為（ 13， 18， 24， 35，47，C）n-i-1D）i50， 62， 83， 90， 115， 134），當(dāng)二分檢索值為(19)(20)(21)(22)(23)(24)(25)(26)(27)9

7、0 的元素時，檢索成功需比較的次數(shù)是（）。A）1B）2假設(shè)以行優(yōu)先順序存儲三維數(shù)組 R696素占 4 個存儲單元,則存儲地址為 2836 的元素是（C)3，其中元素 R000D）4的地址為 2100，且每個元A) R333B) R334C) R435）。D) R434設(shè)有一個10階的對稱矩陣 A，采用壓縮存儲方式以行序為主序存儲，a00為第一個元素,其存儲地址為 0,每個元素占有 1 個存儲地址空間,則 a45 的地址為（A） 13B） 35線性表采用鏈?zhǔn)酱鎯r,節(jié)點的存儲的地址A） 必須是不連續(xù)的C） 必須是連續(xù)的用鏈表表示線性表的優(yōu)點是（A） 便于隨機存取C) 17D) 36B)D)）。B

8、)）。）。連續(xù)與否均可和頭節(jié)點的存儲地址相連續(xù)花費的存儲空間比順序表少C） 數(shù)據(jù)元素的物理順序與邏輯順序相同鏈表不具有的特點是（）。A） 插入、刪除不需要移動元素C） 不必事先估計存儲空間D)B)D)便于插入與刪除可隨機訪問任元素所需空間與線性長度成正比在長度為n的順序表中刪除第i個元素（1 w i W寸,元素移動的次數(shù)為（A) n-i+1B) iC) i+1D) n-i采用順序搜索方法查找長度為 n 的順序表示,搜索成功的平均搜索長度為（A) nB) n/2C) (n-1)/2）。）。D) (n+1)/2將長度為 n 的單鏈表鏈接在長度為m 的單鏈表之后的算法的時間復(fù)雜度為（）。A) O(1

9、)B) O(n)C) O(m)D) O(m+n)若不帶頭結(jié)點的單鏈表的頭指針為head，則該鏈表為空的判定條件是）。A) head=NULLB) head->next=NULL C) head!=NULLD) head->next=headA) 單鏈表C) 雙鏈表若允許表達(dá)式內(nèi)多種括號混合嵌套，的輔助結(jié)構(gòu)是(則為檢查表達(dá)式中括號是否正確配對的算法， 通常選用)。A) 棧B) 線性表C) 隊列D) 二叉排序樹順序棧 S 中 top 為棧頂指針，指向棧頂元素所在的位置， 進棧操作的主要語句為(elem 為存放棧的數(shù)組，則元素 e)。A) s.elem top =e； s.top=s.t

10、op+1；B) s.elem top+1 =e； s.top=s.top+1；C) s.top=s.top+1 ； s.elem top+1 =e；D) s.top=s.top+1 ； s.elem top =e；循環(huán)隊列sq中，用數(shù)組elem 0 25存放數(shù)據(jù)元素，sq.front指示隊頭元素的前一個位置， sq.rear指示隊尾元素的當(dāng)前位置，設(shè)當(dāng)前sq.front為20，sq.rear為12，則當(dāng)前隊列中的元素個數(shù)為()。A) 8 B) 16 C) 17 D) 18 鏈?zhǔn)綏Ｅc順序棧相比，一個比較明顯的優(yōu)點是()。A) 插入操作更加方便C) 不會出現(xiàn)?？盏那闆r一個遞歸的定義可以用遞歸過程求

11、解， 常遞歸過程比非遞歸過程( )。A) 較快 B) 較慢B) 通常不會出現(xiàn)棧滿的情況D) 刪除操作更加方便也可以用非遞歸過程求解， 但單從運行時間來看， 通C) 相同 D) 不定若已知一個棧的入棧序列是 1,2,3,4 為( )。，其輸出序列為p1,p2,p3.，n若 pi=門側(cè) piA) iB) n= =iC) n-i+1D) 不確定一個棧的入棧序列是a,b,c,d,e,則棧的不可能的輸出序列是()。A) edcbaB) decbaC) dceabD) abcde若進棧序列為 1， 2， 3， 4， 5， 6，且進棧和出?？梢源┎暹M行，則不可能出現(xiàn)的出棧序列 是()。A) 2， 4， 3，

12、 1， 5， 6B) 3，2，4，1， 6， 5C) 4， 3， 2， 1， 5， 6D) 2，3，5，1， 6， 4對于棧操作數(shù)據(jù)的原則是()。A) 先進先出B) 后進先出C) 后進后出D) 不分順序棧和隊列的共同點是()。A) 都是先進先出B) 都是先進后出(28)(29)(30)(31)(32)(33)(34)(35)(36)(37)(38)某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用 ( )存儲方式最節(jié)省運算時間。B) 僅有頭指針的單循環(huán)鏈表D) 僅有尾指針的單循環(huán)鏈表C) 只允許在端點處插入和刪除元素 D) 沒有共同點(39) 一個隊列的入隊序列是

13、1， 2，3，4，則隊列的輸出序列是()。A) 4,3,2,1B) 1,2,3,4 C)1,4,3,2 D) 3,2,4,1(40) 設(shè)數(shù)組 datam 作為循環(huán)隊列 SQ 的存儲空間， front 為隊頭指針， rear 為隊尾指針，則執(zhí)行 出對操作后其頭指針 front 值為( )。A) front=front+1C) front=(front-1)%m(41) 引起循環(huán)隊列隊頭位置發(fā)生變化的操作是A) 出隊 B) 入隊B) front=(front+1)%(m-1)D) front=(front+1)%m() 。C) 取隊頭元素 D) 取隊尾元素 設(shè)以數(shù)組Am存放循環(huán)隊列的元素，其頭尾指

14、針分別為front和rear，則當(dāng)前隊列中的元素個數(shù)為( )。A) (rear-front+m)%m B)rear-front+1C)(front-rear+m)%m D )(rear-front)%m(42) 二維數(shù)組 A1218 采用列優(yōu)先的存儲方法，若每個元素各占 3 個存儲單元，且 A00 地址 為 150，則元素 A97 的地址為 ()。A) 429B) 432C) 435 D) 438(43) 設(shè)有一個 10 階的對稱矩陣 A1010 ，采用壓縮方式按行將矩陣中下三角部分的元素存入一維數(shù)組B中，A00存入B0中，貝U A85在B中( )位置。A) 32B) 33C) 41D) 65

15、(44) 若對 n 階對稱矩陣 A 以行序為主序方式將其下三角形的元素(包括主對角線上所有元素 ) 依次存放于一維數(shù)組 B1.(n(n+1)/2 中，則在 B 中確定 aij(i<j)的位置k的關(guān)系為()。A) i*(i-1)/2+jB) j*(j-1)/2+iC) i*(i+1)/2+jD) j*(j+1)/2+i(45) 對稀疏矩陣進行壓縮存儲目的是()。A) 便于進行矩陣運算B)便于輸入和輸出C) 節(jié)省存儲空間D)降低運算的時間復(fù)雜度(46) 對廣義表 L=(a,b),(c,d),(e,f) 執(zhí)行操作 tail(tail(L) 的結(jié)果是 ( )。A) (e,f)B) (e,f)C)

16、 (f)D) ( )(47)設(shè)廣義表 L=(a,b,c) ，則 L 的長度和深度分別為()。A) 1 和 1B) 1和3C) 1 和 2D) 2 和 3(48)樹中所有結(jié)點的度之和等于所有結(jié)點數(shù)加()。A) 0B)1C) -1D) 2(49)在一棵具有n 個結(jié)點的二叉鏈表中，所有結(jié)點的空域個數(shù)等于()。A) nB) n-1C) n+1D) 2*n(50)某二叉樹的先序序列和后序序列正好相反，則該二叉樹一定是()的二叉樹。A) 空或只有一個結(jié)點B) 高度等于其節(jié)點數(shù)(51)(52)(53)(54)(55)C）任一結(jié)點無左孩子D）任一結(jié)點無右孩子含有10個結(jié)點的二叉樹中，度為0的結(jié)點數(shù)為4,則度為

17、A）3B）4C）5除第一層外，滿二叉樹中每一層結(jié)點個數(shù)是上一層結(jié)點個數(shù)的（A)1/2 倍B)1倍C) 2倍對一棵有100個結(jié)點的完全二叉樹按層編號，則編號為A）24B）25C）98可以惟一地轉(zhuǎn)化成一棵一般樹的二叉樹的特點是（2的結(jié)點數(shù)為（D)6D) 3倍49的結(jié)點，它的父結(jié)點的編號為D)99D）根結(jié)點沒有孩子A）根結(jié)點無左孩子B）根結(jié)點無右孩子C）根結(jié)點有兩個孩子設(shè)高度為h的二叉樹上只有度為 0和度為2的結(jié)點，則此類二叉樹中所包含的結(jié)點數(shù)至少為A) 2hB) 2h-1C)2h+1D) h+1(56)A) 4B) 5C) 6D) 7在一棵度為3的樹中，度為3的節(jié)點個數(shù)為2,度為2的節(jié)點個數(shù)為1，

18、則度為0的節(jié)點個數(shù)為（(57)設(shè)森林F對應(yīng)的二叉樹為 B,它有m個結(jié)點，B的根為p, p的右子樹結(jié)點個數(shù)為 n,森林F 中第一棵子樹的結(jié)點個數(shù)是（A)m-nB)m-n-1C) n+1D）條件不足，無法確定(58)1,(59)A) 98B) 89C) 50F列圖示的順序存儲結(jié)構(gòu)表示的二叉樹是（A ）9 10 !1 12D）沒有孩子04將一株有100個節(jié)點的完全二叉樹從上到下，從左到右依次進行編號，根節(jié)點的編號為 則編號為49的節(jié)點的 左孩子編號為（）°樹最適合用來表示( )。A) 有序數(shù)據(jù)元素B)無序數(shù)據(jù)元素C) 元素之間具有分支層次關(guān)系的數(shù)據(jù)D)元素之間無聯(lián)系的數(shù)據(jù)在一個非空二叉樹的

19、中序遍歷序列中，根結(jié)點的右邊( )。A) 只有右子樹上的所有結(jié)點B)只有右子樹上的部分結(jié)點C) 只有左子樹的上的部分結(jié)點D)只有左子樹上的所有結(jié)點任何一棵二叉樹的葉結(jié)點在先序、中序和后序遍歷序列中相對次序( )。(60)(61)(62)(63)(64)(65)(66)(67)(68)(69)(70)(3)A) 不發(fā)生改變B) 發(fā)生改變深度優(yōu)先遍歷類似于二叉樹的()。A) 先序遍歷B) 中序遍歷廣度優(yōu)先遍歷類似于二叉樹的()。A) 先序遍歷B) 中序遍歷任何一個無向連通圖的最小生成樹(A) 只有一棵B) 一棵或多棵C) 不能確定D)以上都不對C)后序遍歷D)層次遍歷C)后序遍歷D)層次遍歷)。一

20、定有多棵D)C)可能不存在注，生成樹不唯一，但最小生成樹唯一，即邊權(quán)之和或樹權(quán)最小的情況唯一)在分析折半查找的性能時常常加入失敗節(jié)點， 即外節(jié)點， 從而形成擴充的二叉樹。 若設(shè)失敗 節(jié)點 i 所在層次為 Li ，那么查找失敗到達(dá)失敗點時所做的數(shù)據(jù)比較次數(shù)是( )。A) Li+1 B) Li+2 C) Li-1 D) Li向一個有 127 個元素原順序表中插入一個新元素并保存原來順序不變，平均要移動( ) 個元素。A) 8B) 63.5C) 63D) 7由同一組關(guān)鍵字集合構(gòu)造的各棵二叉排序樹 ( )。A) 其形態(tài)不一定相同，但平均查找長度相同B) 其形態(tài)不一定相同，平均查找長度也不一定相同C)

21、其形態(tài)均相同，但平均查找長度不一定相同D) 其形態(tài)均相同，平均查找長度也都相同 衡量查找算法效率的主要標(biāo)準(zhǔn)是( )。A) 元素的個數(shù)B) 所需的存儲量C) 平均查找長度D) 算法難易程度適合對動態(tài)查找表進行高效率查找的組織結(jié)構(gòu)是( )。A) 有序表B) 分塊有序表C) 二叉排序樹D) 快速排序能進行二分查找的線性表 ,必須以()。A) 順序方式存儲，且元素按關(guān)鍵字有序B) 鏈?zhǔn)椒绞酱鎯?，且元素按關(guān)鍵字有序C) 順序方式存儲，且元素按關(guān)鍵字分塊有序D) 鏈?zhǔn)椒绞酱鎯?，且元素按關(guān)鍵字分塊有序(71) 為使平均查找長度達(dá)到最小 ,當(dāng)由關(guān)鍵字集合 05,11,21,25,37,40,41,62,84

22、構(gòu)建二叉排序樹時 第一個插入的關(guān)鍵字應(yīng)為( )A) 5 B)37 C) 41 D) 62(72) 對關(guān)鍵字序列 (56,23,78,92,88,67,19,34)進行增量為 3 的一趟希爾排序的結(jié)果為 ( )。A) (19,23,56,34,78,67,88,92)B) 23,56,78,66,88,92,19,34)C) (19,23,34,56,67,78,88,92)D) (19,23,67,56,34,78,92,88)(73) 用某種排序方法對關(guān)鍵字序列 35,84,21,47,15,27,68,25,20 進行排序時，序列的變化情況如 下：20,15,21,25,47,27,68,

23、35,8415,20,21,25,35,27,47,68,8415,20,21,25,27,35,47,68,84則采用的方法是( )。A) 直接選擇排序 (74)B) 希爾排序 C) 堆排序 一組記錄的排序碼為 (46,79,56,38,40,84) ，則利用快速排序的方法， 的第一次劃分結(jié)果為( )。A) 38,40,46,56,79,84B) 40,38,46,79,56,84(75) 快速排序在最壞情況下的時間復(fù)雜度是(22A) O(n 2log2n)B) O(n 2)(76) 下列排序算法中不穩(wěn)定的是( )。A) 直接選擇排序 B) 折半插入排序(77) 對待排序的元素序列進行劃分，

24、 將其分為左、C) 40,38,46,56,79,84)C) O(nlog 2n)C) 冒泡排序右兩個子序列，D) 快速排序以第一個記錄為基準(zhǔn)得到D) 40,38,46,84,56,79D) O(log 2n)D) 快速排序再對兩個子序列進行同樣的排序操作，直到子序列為空或只剩下一個元素為止。這樣的排序方法是( )。A) 直接選擇排序B) 直接插入排序C) 快速排序D) 冒泡排序(78) 將 5 個不同的數(shù)據(jù)進行排序，至多需要比較( )次。A) 8B) 9C) 10D) 25(79) 排序算法中，第一趟排序后，任一元素都不能確定其最終位置的算法是( )。D) 插入排序D) 選擇排序A)選擇排序

25、B)快速排序C)冒泡排序(80) 排序算法中，不穩(wěn)定的排序是()。A)直接插入排序B)冒泡排序C)堆排序(81) 排序方法中， 從未排序序列中依次取出元素與已排序序列 (初始時為空) 中的元素進行比較， 將其放入已排序序列的正確位置上的方法，稱為() .(82)(83)(84)(85)(86)(87)(88)(89)(90)(91)(92)(93)A) 希爾排序B) 冒泡排序C) 插入排序D)選擇排序從未排序序列中挑選元素，并將其依次插入已排序序列(初始時為空)的一端的方法， 稱為)。A) 希爾排序B) 歸并排序C) 插入排序D)選擇排序?qū)個不同的排序碼進行冒泡排序，在下列哪種情況下比較的次

26、數(shù)最多。A) 從小到大排列好的B) 從大到小排列好的C) 元素?zé)o序D) 元素基本有序?qū)個不同的排序碼進行冒泡排序，在元素?zé)o序的情況下比較的次數(shù)為()。A) n+1B) nC) n-1D)n(n-1)/2快速排序在下列哪種情況下最易發(fā)揮其長處。A)被排序的數(shù)據(jù)中含有多個相同排序碼B)被排序的數(shù)據(jù)已基本有序C)被排序的數(shù)據(jù)完全無序D)被排序的數(shù)據(jù)中的最大值和最小值相差懸殊對有 n 個記錄的表作快速排序，在最壞情況下，2B) O(n2)算法的時間復(fù)雜度是(A) O(n)C) O(nlog 2n)。3D) O(n 3)若一組記錄的排序碼為 (46, 79, 56, 38, 40, 84)， 準(zhǔn)得到的

27、一次劃分結(jié)果為()。則利用快速排序的方法， 以第一個記錄為基A) 38, 40, 46, 56,79, 84B)40, 38, 46 , 79, 56, 84C) 40, 38， 46, 56,79, 84D)40, 38, 46, 84, 56, 79列關(guān)鍵字序列中， ()是堆。A)16, 72, 31, 23, 94, 53B)94, 23, 31, 72, 16, 53C) 16, 53, 23, 94 ， 31, 72D)16, 23, 53, 31, 94, 72堆是一種()排序。A) 插入B) 選擇C)交換D) 歸并堆的形狀是一棵()。A) 二叉排序樹B) 滿二叉樹C)完全二叉樹D

28、) 平衡二叉樹)。A) 79, 46, 56, 38, 40, 84B)84, 79, 56, 38, 40, 46C) 84, 79, 56, 46, 40, 38D)84, 56, 79, 40, 46, 38下述幾種排序方法中，要求內(nèi)存最大的是()。A) 插入排序B) 快速排序C)歸并排序D) 選擇排序有一組數(shù)據(jù)( 15， 9， 7， 8， 20， -1，7，4)，用堆排序的篩選方法建立的初始堆為()。A) -1 ， 4， 8， 9， 20， 7， 15， 7B) -1 ， 7， 15， 7， 4， 8， 20， 9若一組記錄的排序碼為 (46, 79, 56, 38, 40, 84)，

29、則利用堆排序的方法建立的初始堆為(C) -1 , 4, 7, 8, 20, 15, 7, 9(94) 51.下列四個序列中，哪一個是堆()。A) 75,65,30,15,25,45,20,10C) 75,45,65,30,15,25,20,10(95) 以下序列不是堆的是()。A) (100,85,98,77,80,60,82,40,20,10,66)C) (10,20,40,60,66,77,80,82,85,98,100)(96)D) A , B, C均不對。B) 75,65,45,10,30,25,20,15D) 75,45,65,10,25,30,20,15B) (100,98,85,

30、82,80,77,66,60,40,20,10)D) (100,85,40,77,80,60,66,98,82,10,20)快速排序方法在()情況下最不利于發(fā)揮其長處。A)要排序的數(shù)據(jù)量太大C)要排序的數(shù)據(jù)個數(shù)為奇數(shù)B) 要排序的數(shù)據(jù)中含有多個相同值D) 要排序的數(shù)據(jù)已基本有序(97) 對關(guān)鍵碼序列28, 16, 32, 12, 60, 2, 5, 72快速排序，從小到大一次劃分結(jié)果為()。A) (2,5,12,16)26(60,32,72)B) (5,16,2,12)28(60,32,72)C) (2,16,12,5)28(60,32,72)D) (5,16,2,12)28(32,60,72

31、)(98) 對下列關(guān)鍵字序列用快速排序法進行排序時，速度最快的情形是()。A) 21,25,5,17,9,23,30C) 21,9,17,30,25,23,5B)25,23,30,17,21,5,9D) 5,9,17,21,23,25,30、填空題(99) 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的操作對象以及它們之間的 關(guān)系和運算等的學(xué)科。(100) 數(shù)據(jù)結(jié)構(gòu)被形式地定義為(D, R)，其中D是 數(shù)據(jù)元素 的有限集合,R是D上的 關(guān)系有限集合。(101) 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的 存儲結(jié)構(gòu)和數(shù)據(jù)的 運算 這三個方面的內(nèi)容。(102) 數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分

32、別是線性結(jié)構(gòu)和非線性結(jié)構(gòu)(103) 線性結(jié)構(gòu)中元素之間存在一對一關(guān)系，樹形結(jié)構(gòu)中元素之間存在一對多關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對多關(guān)系。(104) 在線性結(jié)構(gòu)中，第一個結(jié)點沒有 前驅(qū)結(jié)點，其余每個結(jié)點有且只有1個前驅(qū)結(jié)點；最后一個結(jié)點沒有后續(xù)結(jié)點，其余每個結(jié)點有且只有1個后續(xù)結(jié)點。(105) 在樹形結(jié)構(gòu)中，樹根結(jié)點沒有 前驅(qū) 結(jié)點，其余每個結(jié)點有且只有1個前驅(qū)結(jié)點；葉子結(jié)點沒有后續(xù) 結(jié)點，其余每個結(jié)點的后續(xù)結(jié)點數(shù)可以任意多個。(106) 在圖形結(jié)構(gòu)中，每個結(jié)點的前驅(qū)結(jié)點數(shù)和后續(xù)結(jié)點數(shù)可以任意多個。(107) 數(shù)據(jù)的存儲結(jié)構(gòu)可用四種基本的存儲方法表示，它們分別是順序、鏈?zhǔn)?、索?和散列。(10

33、8) 數(shù)據(jù)的運算最常用的有5種，它們分別是插入、刪除、修改、 查找、排序。(109) 個算法的效率可分為時間 效率和 空間 效率。(110) 對于給定的n個元素，可以構(gòu)造出的邏輯結(jié)構(gòu)有 集合，線性表，樹，圖四種。(111) 順序映象的特點是借助元素在存儲器中的 相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。非順序映象的特點是借助是指示元素存儲地址的 指針表示數(shù)據(jù)元素之間的邏輯關(guān)系。任何一個算法的設(shè)計取決于選定 邏輯結(jié)構(gòu)，而算法的實現(xiàn)依賴于采用的 存儲結(jié)構(gòu)。(112) 數(shù)據(jù)類型是一組 性質(zhì)相同的值集合以及定義在這個值集合上的一組操作的總稱。(113) 數(shù)據(jù)對象是 性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子

34、集。(114) 如果操作不改變原邏輯結(jié)構(gòu)的值”而只是從中提取某些信息作為運算結(jié)果，則稱該類運算為型運算。引用(115) 算法的 健壯特性是指做為一個好的算法，當(dāng)輸入的數(shù)據(jù)非法時，也能適當(dāng)?shù)刈龀稣_反應(yīng)或進行相應(yīng)的處理，而不會產(chǎn)生一些莫名其妙的輸出結(jié)果。(116) 算法分析不是針對實際執(zhí)行時間的精確的算出算法執(zhí)行具體時間的分析，而是針對算法中語句的 執(zhí)行次數(shù)做出估計，從中得到算法執(zhí)行時間的信息。(117) T(n)=O(f(n)，它表示隨問題規(guī)模n的增大算法的執(zhí)行時間的增長率和f(n)的增長率相同，稱作算法的漸進時間復(fù)雜度，簡稱時間復(fù)雜度。(118) 若算法執(zhí)行時所需要的輔助空間相對于輸入數(shù)據(jù)量

35、而言是個常數(shù)，則稱這個算法為原地工作，輔助空間為0(1)。(119) 在帶有頭結(jié)點的單鏈表中L中，第一個元素結(jié)點的指針是 。L->next(120) 在一個帶頭節(jié)點的單循環(huán)鏈表中，p指向尾結(jié)點的直接前驅(qū)，則指向頭結(jié)點的指針 head可用 p 表示為 head=。p->next->next(121) 設(shè)單鏈表的結(jié)點結(jié)構(gòu)為(data,next)，next為指針域，已知指針 px指向單鏈表中data為x 的結(jié)點，指針py指向data為y的新結(jié)點，若將結(jié)點y插入結(jié)點x之后，則需要執(zhí)行以下語句：_ py_>next=px->next; px->next=py 。(12

36、2) 對于棧操作數(shù)據(jù)的原則是 。后進先出(123) 設(shè)以數(shù)組Am存放循環(huán)隊列的元素，其頭尾指針分別為front和rear,則當(dāng)前隊列中的元素個數(shù)為 。(rear-front+m)%m(124) 若已知一個棧的入棧序列是1,2,3,4 ，其輸出序列為 p1,p2,p3,若p1= =n，則pi 為。n-i+1(125) 隊列是被限定為只能在表的一端進行插入運算，在表的另一端進行刪除運算 的線性表。(126) 通常程序在調(diào)用另一個程序時，都需要使用一個棧來保存被調(diào)用程序內(nèi)分配的局部變量。形式參數(shù)的存儲空間以及返回地址。(127) 棧下溢是指在_棧空時進行出棧操作。(128) 用P表示入棧操作，D表示

37、出棧操作，若元素入棧的順序為1234,為了得到1342出棧順序，相應(yīng)的 P和D的操作串為 。 PDPPDPDD(129) 在具有n個單元的循環(huán)隊列中，隊滿共有 n-1個元素。(130) 隊列是被限定為只能在表的一端進行插入運算，在表的另一端進行刪除運算的線性表。(131) 循環(huán)隊列的引入，目的是為了克服 假溢出。(132) 所謂稀疏矩陣指的是 非零元很少(t<<m*n)且分布沒有規(guī)律。(133) 在稀疏矩陣表示所對應(yīng)的三元組線性表中，每個三元組元素按 行為主序，_列號為輔序的次序排列。(134) 二位數(shù)組Am<n按行優(yōu)先順序存儲在內(nèi)存中，元素ago地址為loc(aoo),每個

38、元素在內(nèi)存中占d個字節(jié)，元素 aij的地址計算公式為 loc(aj)= loc(a oo) + (i*n+j)*d 。(135) 樹內(nèi)個結(jié)點的度 最大值稱為樹的度。(136) 一個二叉樹第 5層節(jié)點最多有 16個。(137) 已知完全二叉樹 T的第5層只有7個結(jié)點，則該樹共有 11個葉子結(jié)點。(138) 在一棵二叉樹中，度為零的結(jié)點的個數(shù)為NO,度為2的結(jié)點的個數(shù)為 N2,則有NO=N2+1。(139) 假設(shè)用于通信的電文由8個字母組成，其頻率分別為7,19,2,6,32,3,27,10。設(shè)計哈夫曼編碼，其中字母的編碼長度最大是 5位。(140) 一棵具有257個結(jié)點的完全二叉樹，它的深度為

39、。9(141) 散列法存儲的基本思想是由 關(guān)鍵字的值決定數(shù)據(jù)的存儲地址。(142) 大多數(shù)排序算法都有兩個基本的操作： 。比較和移動(143) 由于查找算法的基本運算是關(guān)鍵字之間的比較操作，所以可用平均查找長度來衡量查找算法的性能。(144) 查找有靜態(tài)查找和動態(tài)查找，當(dāng)查找不成功時動態(tài)查找會 將查找關(guān)鍵字插入在表中。(145) 順序查找法中設(shè)置監(jiān)視哨，可以起到 防止越界的作用。(146) 假設(shè)列表長度為n,那么查找第i個數(shù)據(jù)元素時需進行 n-i+1次比較。(147) 假設(shè)查找每個數(shù)據(jù)元素的概率相等，即Pi=1/n，則順序查找算法的平均查找長度為：_ ASL=(n+1)/2。(148) 折半查

40、找法又稱為二分法查找法，這種方法要求待查找的列表必須是按關(guān)鍵字大小有序排列的順序表。(149) 假定將長度為n的表分成b塊，且每塊含s個元素，則b=n/s。又假定表中每個元素的查找概率相等，(150) 在有序表(12,24,36,48,60,72,84)中二分查找關(guān)鍵字 72時所需進行的關(guān)鍵字比較次數(shù)為2。(151) 折半查找有序表(4,6,12,20,28,38,50,70,88,100)，若查找表中元素 20,它將依次與表中元素 28，6，12，20比較大小。(152) 在各種查找方法中，平均查找長度與結(jié)點個數(shù)n無關(guān)的查找方法是 散列查找。(153) 當(dāng)關(guān)鍵字集合很大時，關(guān)鍵字值不同的元素

41、可能會映象到哈希表的同一地址上，即k1豐k2，但 H ( k1) =H ( k2)，這種現(xiàn)象稱為 沖突(154) 在散列函數(shù) H(key)=key MOD p 中，p應(yīng)取素數(shù)。(155) 設(shè)哈希表長 m=14,哈希函數(shù) H(key)=key MOD11.表中已有4個結(jié)點；addr(15)=4,addr(38)=5, addr(61)=6, addr(84)=7,其余地址為空。如用二次探測再散列處理沖突，關(guān)鍵字為49的結(jié)點的地址是 。9(156) 希爾排序是屬于 插入排序的改進方法。(157) 給出一組關(guān)鍵字 T =( 20,4,34,5,16,33,18,29,2,40,7),要求從下到大進行

42、排序，試給出快速排序(選一個記錄為樞紐)第一趟排序結(jié)果 。7,4,2,85,16,18,20,29,33,40,34(158) 大多數(shù)排序算法都有兩個基本的操作：比較和移動。(159) 在對一組記錄(54,38,96,23,15,72,60,45,83)進行直接插入排序時，當(dāng)把第7個記錄60插入到有序表時，為尋找插入位置至少需比較 次。6。(160) 在插入和選擇排序中，若初始數(shù)據(jù)基本正序，則選用插入;若初始數(shù)據(jù)基本反序，則選用選擇。(161) 在堆排序和快速排序中，若初始記錄接近正序或反序，則選用堆排序;若初始記錄基本無序，則最好選用快速排序。(162) 對于n個記錄的集合進行冒泡排序，在最

43、壞的情況下所需要的時間是0(n2)。若對其進行快速排序，在最壞的情況下所需要的時間是O(n2)(173) 對于n個記錄的集合進行歸并排序，所需要的平均時間是 o(nIog2n)，所需要的附加空間是O( n)。7. 對于n個記錄的表進行 2路歸并排序，整個歸并排序需進行廠Iog2n趟(遍)。8. 設(shè)要將序列(Q, H, C, Y, P, A, M, S, R, D, F, X )中的關(guān)鍵碼按字母序的升序重新排列，則：冒泡排序一趟掃描的結(jié)果是HCQPAMSRDFXY ;初始步長為 4的希爾(shell)排序一趟的結(jié)果是P A C S Q H F X R D M Y ;二路歸并排序一趟掃描的結(jié)果是H

44、QCYAPMSDRFX ;快速排序一趟掃描的結(jié)果是FHCDPAMQRSYX ;堆排序初始建堆的結(jié)果是ADCRFQMSYPHX 。9. 在堆排序、快速排序和歸并排序中，若只從存儲空間考慮，則應(yīng)首先選取 _方法，其次選取_快速排序方法，最后選取歸并排序方法;若只從排序結(jié)果的穩(wěn)定性考慮，則應(yīng)耳取歸并排序方法；若只從平均情況下最快考慮，則應(yīng)選取堆排序、快速排序和歸并排序方法；若只從最壞情況下最快并且要節(jié)省內(nèi)存考慮，則應(yīng)選取_堆排序_方法。三、程序填空題(174) 以下程序的功能是實現(xiàn)帶附加頭結(jié)點的單鏈表數(shù)據(jù)結(jié)點逆序連接，請?zhí)羁胀晟浦oid reverse(po in ter h)/* h為附加頭結(jié)

45、點指針；*/ poin ter p,q;p=h->n ext;h->n ext=NULL;while( )q=p; p=p->n ext; q_>n ext=h->n ext; h_>next=(2);(1) p!=null/鏈表未到尾就一直作(2) q/將當(dāng)前結(jié)點作為頭結(jié)點后的第一元素結(jié)點插入(175) 下列算法在順序表L中依次存放著線性表中的元素，在表中查找與e相等的元素，若L.elemi=e,則找到該元素，并返回i+1，若找不到，則返回“-1 ”，請?zhí)羁胀晟浦?。int Locate(SeqList L , int e)i=0 ;/*i為掃描計數(shù)器，初值

46、為0，即從第一個元素開始比較*/while (i<=L.last)&&(L.elemi!=e) ) i+;/*順序掃描表，直到找到值為key的元素，或掃描到表尾而沒找到*/if ( i<=L.last ) return(i+1);/* 若找到值為 e 的元素，則返回其序號*/elsereturn(-1);/*若沒找到，則返回空序號 */(176)下列算法在順序表 L中第i個數(shù)據(jù)元素之前插入一個元素e。插入前表長n=L->last+1 ,i的合法取值范圍是K i < L->last+2，請?zhí)羁胀晟浦?。voidInsList(SeqList *L, i

47、nt i,int e)int k;if(i<1) | (i>L->last+2)printf(插入位置i值不合法”；if(L->last>=maxsize-1)printf(表已滿無法插入”；for(k=L_>last;k>=i_1;k_)/*為插入元素而移動位置*/L->elemk+1=L->elemk;L->elemi-1=e ;/*在C語言數(shù)組中，第i個元素的下標(biāo)為i-1*/L->last+ ;(177)下列算法是在順序表L中刪除第i個數(shù)據(jù)元素，并用指針參數(shù)e返回其值。i的合法取值為 K i < L.last+1，請?zhí)羁胀晟浦?。int DelList(SeqList *