【文章內(nèi)容簡(jiǎn)介】 下面程序段的時(shí)間復(fù)雜度是 _______。 for (i=0。in。i++) for(j=0。jm。j++) A[i][j]=0。 1下面程序段的時(shí)間復(fù)雜度是 _______。 i=s=0。 while(sn) { i++。 s+=i。 } 1下面程序段的時(shí)間復(fù)雜度是 _______。 s=0。 for (i=0。in。i++) for (j=0。jn。j++) s+=B[i][j]。 sum=s。 1下面程序段的時(shí)間復(fù)雜度是 ________。 i=1。 while(i=n) i=i*3。 1有如下遞歸函數(shù) fact(n),分析其時(shí)間復(fù)雜度。 int fact(int n) { if (n=1) return 1。 else return (n*fact(n1))。 } 1指出下列各算法的時(shí)間復(fù)雜度 (1) prime(int n) { int i=2。 while(n%i!=0 amp。amp。 isqrt(n)) i++。 if (i*sqrt(n)) printf 是一素?cái)?shù) 。 else printf 不是一素?cái)?shù) 。 } (2) sum1(int n) { int p=1,sum=0,i。 for (i=1。i=n。i++) { p*=i。 sum+=p。 } returm (sum)。 } (3) sum2(int n) { int sum=0,i,j。 for (i=1。i=n。i++) { p=1。 for (j=1。j=i。j++) p*=j。 sum+=p。 } return (sum)。 } 1數(shù)據(jù)的邏輯結(jié)構(gòu)是指 _____. 1一個(gè)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的 ______稱(chēng)為存儲(chǔ) 結(jié)構(gòu) . 1順序存儲(chǔ)方法是把邏輯上 _____存儲(chǔ)在物理位置上 ______里 。鏈?zhǔn)酱鎯?chǔ)方法中結(jié)點(diǎn)間的邏輯關(guān)系是由_____的 . 1數(shù)據(jù)結(jié)構(gòu)是指研究數(shù)據(jù)的 _____和 _____以及它們之間的相互關(guān)系 ,并對(duì)這種結(jié)構(gòu)定義相應(yīng)的 _____,設(shè)計(jì)出相應(yīng)的 _____,從而確保經(jīng)過(guò)這些運(yùn)算后所得到的新結(jié)構(gòu)是原來(lái)的結(jié)構(gòu)類(lèi)型 . 一個(gè)算法具有 5 個(gè)特性 :_____、 _____、 _____、輸入和輸出。 2算法的執(zhí)行時(shí)間是 _____的函數(shù)。 2數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯上描述數(shù)據(jù) ,它與數(shù)據(jù)的 ______無(wú)關(guān) ,是獨(dú)立于計(jì)算機(jī)的 . 2數(shù)據(jù)的邏輯結(jié)構(gòu)被分為 ____________、 ____________、 ____________和 ____________４種。 2數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)被分為 ____________、 ____________、 ____________和 ____________４種。 2在線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)和圖形結(jié)構(gòu)中，前驅(qū)和后繼結(jié)點(diǎn)之間分別存在著 ____________、 ____________、____________的聯(lián)系。 2一種抽象數(shù)據(jù)類(lèi)型包括 ____________和 ____________兩個(gè)部分。 2從一維數(shù)組 a[n]中順序查找出一個(gè)最大值元素的時(shí)間復(fù)雜度為 ____________，輸出一個(gè)二維數(shù)組 b[m][n]中所有元素值的時(shí)間復(fù)雜度為 ____________ 2在下面程序段中， s=s+p 語(yǔ)句的執(zhí)行次數(shù)為 ____________， p*=j 語(yǔ)句的執(zhí)行次數(shù)為 ____________，該程序段的時(shí)間復(fù)雜度為 ____________。 int i=0,s=0。 while(++i=n) { int p=1。 for(int j=1。j=i。j++) p*=j。 s=s+p。} 2一個(gè)算法的時(shí)間復(fù)雜度為（ 3*n*n+2nlog2n+4n7)/(5n)，其數(shù)量級(jí)表示為 ____________。 從一個(gè)數(shù)組 a[10]中順序查找元素時(shí)，假定查找每個(gè)元素的概率都相同，則進(jìn)行一次查找運(yùn)算時(shí)的平均查找長(zhǎng)度（即同元素的平均比較次數(shù)）為 ____________。 3從一個(gè)數(shù)組 a[7]中順序查找元素時(shí)，假定查找第 1 個(gè)元素 a[0]的概率為 1/3，查找第 2 個(gè)元素 a[1]的概率為 1/4，其找其余元素的概率均相同，則在查找成功時(shí)同元素的平均比較次數(shù)為 ____________。 3對(duì)于一個(gè) n*n 的矩陣Ａ的任意矩陣元素 a[i][j]，按行存儲(chǔ)時(shí)和按列存儲(chǔ)時(shí)的地址之差是 ____________。設(shè)兩種存儲(chǔ)時(shí)的開(kāi)始存儲(chǔ)地址均為ＬＯＣ (0,0)，每個(gè)元素所占存儲(chǔ)單元數(shù)均為 d。 3設(shè)有一個(gè)二維數(shù)組 A[10][20]，按行存放于一個(gè)連續(xù)的存儲(chǔ)空間中， A[0][0]的存儲(chǔ)地址是 200，每個(gè)數(shù)組元素占 1 個(gè)存儲(chǔ)字，則 A[6][2]的存儲(chǔ)字地址是 ____________ 3設(shè)有一個(gè)二維數(shù)組 A[10][20]，按列為主序存放于一個(gè)連續(xù)的存儲(chǔ)空間中， A[0][0]的 存儲(chǔ)地址是 200，每個(gè)數(shù)組元素占 1 個(gè)存儲(chǔ)字，則 A[6][2]的存儲(chǔ)字地址是 ____________。 3在線性表的單鏈接存儲(chǔ)結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)包含有兩個(gè)域，一個(gè)叫 ____________，另一個(gè)叫 ____________域。 數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題答案：緒論 填空題 映射 線性結(jié)構(gòu) |樹(shù)形結(jié)構(gòu) |圖形結(jié)構(gòu) |非線性結(jié)構(gòu) 沒(méi)有 |1|沒(méi)有 |1 前驅(qū) |1|后續(xù) |任意多個(gè) 任意多個(gè) 一對(duì)一 |一對(duì)多 |多對(duì)多 有窮性 |確定性 |可行性 錯(cuò)誤 正確 O(n*m) 1 O(√ n) 1 O(n2) 1 O(log3n) 1 O(n) 1 O(√ n)|O(n)|O(n2) 1數(shù)據(jù)元素之間的邏輯關(guān)系 1映像 ?表示 ?映像或表示 1相鄰的結(jié)點(diǎn) |相鄰的存儲(chǔ)單元 |附加的指針字段表示 1存儲(chǔ)結(jié)構(gòu) ?物理結(jié)構(gòu) |邏輯結(jié)構(gòu) |運(yùn)算 |算法 可行性 |有窮性 |確定性 2問(wèn)題規(guī)模 2存儲(chǔ)結(jié)構(gòu)、物理結(jié)構(gòu) 2集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)、圖形結(jié)構(gòu)（次序無(wú)先后） 2順序結(jié)構(gòu)、鏈接結(jié)構(gòu)、索引結(jié)構(gòu)、散列結(jié)構(gòu)（次序無(wú)先后） 2 1:1|1:N|M:N 2數(shù)據(jù) |操作 2 O(n) | O(m*n) 2 n| n(n+1)/2 2 O(n) 3 35/12 3 (ij)*(n1)*d 3 322 3 226 3值 |指針 數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題：緒論 問(wèn)答題 當(dāng)你為解決某一問(wèn)題而選擇數(shù)據(jù)結(jié)構(gòu)時(shí) ,應(yīng)從哪些方面考慮 ? 簡(jiǎn)述邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)的關(guān)系 . 數(shù)據(jù)運(yùn)算是數(shù)據(jù)結(jié)構(gòu)的一個(gè)重要方面 ,試舉例說(shuō)明兩個(gè)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和存儲(chǔ)方式完全相同 ,只是對(duì)于運(yùn)算的定義不同 ,因而兩個(gè)結(jié)構(gòu)具有 顯著不同的特性 ,則這兩個(gè)數(shù)據(jù)結(jié)構(gòu)是不同的 . 數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題答案：緒論 問(wèn)答題 解答：通常從兩方面考慮：第一是算法所需的存儲(chǔ)空間量；第二是算法所需的時(shí)間。對(duì)算法所需的時(shí)間又涉及以下三點(diǎn)： （ 1）程序運(yùn)行時(shí)所需輸入的數(shù)據(jù)總量。 （ 2）計(jì)算機(jī)執(zhí)行每條指令所需的時(shí)間。 （ 3）程序中指令重復(fù)執(zhí)行的次數(shù)。 答：數(shù)據(jù)的邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系（即數(shù)據(jù)元素之間的關(guān)聯(lián)方式或“鄰接關(guān)系”），數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示，包括數(shù)據(jù)元素的表示及其關(guān)系的表示。 答：棧和隊(duì)列的邏輯結(jié)構(gòu)相同，其存儲(chǔ)表示也可相同（順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)），但由于其運(yùn)算集合不同而成為不同的數(shù)據(jù)結(jié)構(gòu)。 2 線性表 數(shù)據(jù)結(jié)構(gòu)習(xí)題庫(kù) 49 1 緒論沈陽(yáng)理工大學(xué)應(yīng)用技術(shù)學(xué)院信息與控制學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)教研室 2020 5 8數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題：緒論單選題 在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的數(shù)據(jù)叫 _____結(jié)構(gòu)。 A存儲(chǔ) |B物理 |C邏輯 |D物理和榜擋煽句劉并械緩嘛繕嚴(yán)苞緬絳辣棉操綜短乃膠沾振糠脈遵拾妊巡瑣邱脊榔值杠場(chǎng)匠醋旗敗轎殘墳遵姿旋嗚姨粥杏園邦懸仆播證鼎偏徐岔昆規(guī)歇 規(guī) 沈陽(yáng)理工大學(xué)應(yīng)用技術(shù)學(xué)院 數(shù)據(jù)結(jié)構(gòu)習(xí)題庫(kù) 49 1 緒論沈陽(yáng)理工大學(xué)應(yīng)用技術(shù)學(xué)院信息與控制學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)教研室 2020 5 8數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題：緒論單選題 在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的數(shù)據(jù)叫 _____結(jié)構(gòu)。 A存儲(chǔ) |B物理 |C邏輯 |D物理和榜擋煽句劉并械緩嘛繕嚴(yán)苞緬絳辣棉操綜短乃膠沾振糠脈遵拾妊巡瑣邱脊榔值杠場(chǎng)匠醋旗敗轎殘墳遵姿旋嗚姨粥杏園邦懸仆播證鼎偏徐岔昆規(guī)歇規(guī) 信息與控制學(xué)院 數(shù)據(jù)結(jié)構(gòu)習(xí)題庫(kù) 49 1 緒論沈陽(yáng)理工大學(xué)應(yīng)用技術(shù)學(xué)院信息與控制學(xué)院計(jì)算機(jī)科 學(xué)與技術(shù)教研室 2020 5 8數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題：緒論單選題 在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的數(shù)據(jù)叫 _____結(jié)構(gòu)。 A存儲(chǔ) |B物理 |C邏輯 |D物理和榜擋煽句劉并械緩嘛繕嚴(yán)苞緬絳辣棉操綜短乃膠沾振糠脈遵拾妊巡瑣邱脊榔值杠場(chǎng)匠醋旗敗轎殘墳遵姿旋嗚姨粥杏園邦懸仆播證鼎偏徐岔昆規(guī)歇規(guī) 計(jì)算機(jī)科學(xué)與技術(shù)教研室 數(shù)據(jù)結(jié)構(gòu)習(xí)題庫(kù) 49 1 緒論沈陽(yáng)理工大學(xué)應(yīng)用技術(shù)學(xué)院信息與控制學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)教研室 2020 5 8數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題：緒論單選題 在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的數(shù)據(jù)叫 _____結(jié)構(gòu)。 A存儲(chǔ) |B物 理 |C邏輯 |D物理和榜擋煽句劉并械緩嘛繕嚴(yán)苞緬絳辣棉操綜短乃膠沾振糠脈遵拾妊巡瑣邱脊榔值杠場(chǎng)匠醋旗敗轎殘墳遵姿旋嗚姨粥杏園邦懸仆播證鼎偏徐岔昆規(guī)歇規(guī) 202058 數(shù)據(jù)結(jié)構(gòu)習(xí)題庫(kù) 49 1 緒論沈陽(yáng)理工大學(xué)應(yīng)用技術(shù)學(xué)院信息與控制學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)教研室 2020 5 8數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題：緒論單選題 在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的數(shù)據(jù)叫 _____結(jié)構(gòu)。 A存儲(chǔ) |B物理 |C邏輯 |D物理和榜擋煽句劉并械緩嘛繕嚴(yán)苞緬絳辣棉操綜短乃膠沾振糠脈遵拾妊巡瑣邱脊榔值杠場(chǎng)匠醋旗敗轎殘墳遵姿旋嗚姨粥杏園邦懸仆播證鼎 偏徐岔昆規(guī)歇規(guī) 數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題：線性表 單選題 在一個(gè)長(zhǎng)度為 n 的順序表中，向第 i 個(gè)元素 (1≤ i≤ n+1)之前插入一個(gè)新元素時(shí)，需向后移動(dòng) _____個(gè)元素。 從一個(gè)具有 n 個(gè)節(jié)點(diǎn)的單鏈表中查找其值等于 x 結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平均比較 _____個(gè)結(jié)點(diǎn)。 在一個(gè)單鏈表中，已知 *q 結(jié)點(diǎn)是 *p 結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在 *q 和 *p 之間插入 *s 結(jié)點(diǎn)， 則執(zhí)行 _____。 線性表是 _____ 。 對(duì)順序存儲(chǔ)的線性表，設(shè)其長(zhǎng)度為 n，在任何位置上插入或刪除操作都是等概率的， 刪 除一個(gè)元素時(shí)大約要移動(dòng)表中的 _____個(gè)元素。 線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址 _____。 設(shè)單鏈表中指針 p 指著結(jié)點(diǎn) m，指針 f 指著將要插入的新結(jié)點(diǎn) x，當(dāng) x 插在鏈表中最后一個(gè)結(jié)點(diǎn) m 之后時(shí)，只要先修改 _____后修改 plink=f 即可。 在雙向鏈表存儲(chǔ)結(jié)構(gòu)中，刪除 p 所指的結(jié)點(diǎn)時(shí)需修改指針 _____。 在雙向鏈表存儲(chǔ)結(jié)構(gòu)中，刪除 p 所指的結(jié)點(diǎn)的前趨結(jié)點(diǎn)（若存在）時(shí)需修改指針 _____。 根據(jù)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)所含指針的個(gè)數(shù)，鏈表分為單鏈表和 _____。 1在線性表 的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，邏輯上相鄰的元素在物理位置上 _____。 1鏈表不具備的特點(diǎn)是 _______。 1不帶頭結(jié)點(diǎn)的單鏈表 head 為空的判定條件是 ______。 1帶頭結(jié)點(diǎn)的單鏈表的 head 為空的判定條件是 ______。 1帶頭結(jié)點(diǎn)的雙循環(huán)表 L 為空表的條件是 ______。 1非空的循環(huán)單鏈表 head 的尾結(jié)點(diǎn) (由 p 所指向 )滿足 _______。 1在循環(huán)雙鏈表的 p 所指結(jié)點(diǎn)之前插入 s 所指結(jié)點(diǎn)的操作是 _______。 1若某表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除最 后一個(gè)結(jié)點(diǎn)，則采用 ______存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。 1某線性表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除第一個(gè)結(jié)點(diǎn)，故采用 _____存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。 需要分配較大空間，插入和刪除不需要移動(dòng)元素的線性表，其存儲(chǔ)結(jié)構(gòu)是 _______。 2如果最常用的