數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)填空集錦

數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)填空集錦填空一個(gè)計(jì)算機(jī)系統(tǒng)包括_硬件系統(tǒng) 和 軟件系統(tǒng) 兩大部分。一臺(tái)計(jì)算機(jī)中全部程序的集合，稱為這臺(tái)計(jì)算機(jī)的軟件資源/（系統(tǒng)）計(jì)算機(jī)軟件可以分為—系統(tǒng)—軟件和應(yīng)用—軟件兩大類?？茖W(xué)計(jì)算程序包屬于.應(yīng)用軟件—，診斷程序?qū)儆凇到y(tǒng)軟件（工具）_一。一種用助憶符號(hào)來(lái)表示機(jī)器指令的操作符和操作數(shù)的語(yǔ)言是—匯編語(yǔ)言 。數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的』作對(duì)象 以及它們之間的關(guān)系 和運(yùn)算等的學(xué)科。數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D,R），其中D是數(shù)據(jù)元素 的有限集合，R是D上的心系有限集合。數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)_、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)—和數(shù)據(jù)的—運(yùn)算_這三個(gè)方面的內(nèi)容。數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是線性結(jié)構(gòu)和非線性結(jié)構(gòu)線性結(jié)構(gòu)中元素之間存在一對(duì)一關(guān)系，樹形結(jié)構(gòu)中元素之間存在一對(duì)多關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對(duì)多關(guān)系。在線性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn)我有_前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)前驅(qū)結(jié)點(diǎn);最后一個(gè)結(jié)點(diǎn)_沒(méi)有—后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)后續(xù)結(jié)點(diǎn)。在樹形結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒(méi)有前驅(qū)一結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有—1—個(gè)前驅(qū)結(jié)點(diǎn);葉子結(jié)點(diǎn)沒(méi)有后續(xù)—結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)數(shù)可以任意多個(gè)_。在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以任意多個(gè)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)可用四種基本的存儲(chǔ)方法表示，它們分別是順序、鏈?zhǔn)?、索引和散列?數(shù)據(jù)的運(yùn)算最常用的有5種，它們分別是插入、刪除、修改、杳找、排序。一個(gè)算法的效率可分為一時(shí)間 效率和空間效率。任何一個(gè)C程序都由 一個(gè)主函數(shù)—和若干個(gè)被調(diào)用的其它函數(shù)組成。變量一經(jīng)說(shuō)明，就確定該變量的取值范圍(即存儲(chǔ)單元)及—確定變量所允許的運(yùn)算 。在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng)表中一半元素，具體移動(dòng)的元素個(gè)數(shù)與表長(zhǎng)和該元素在表中的位置有關(guān)。線性表中結(jié)點(diǎn)的集合是有限—的，結(jié)點(diǎn)間的關(guān)系是一對(duì)一—的。向一個(gè)長(zhǎng)度為n的向量的第i個(gè)元素(1WiWn+1)之前插入一個(gè)元素時(shí)，需向后移動(dòng)n-i+1個(gè)元素。向一個(gè)長(zhǎng)度為n的向量中刪除第i個(gè)元素(1WiWn)時(shí)，需向前移動(dòng)n-i_個(gè)元素。在順序表中訪問(wèn)任意一結(jié)點(diǎn)的時(shí)間復(fù)雜度均為_QW—，因此，順序表也稱為.隨機(jī)存虹的數(shù)據(jù)結(jié)構(gòu)。順序表中邏輯上相鄰的元素的物理位置堅(jiān)定相鄰。單鏈表中邏輯上相鄰的元素的物理位置不一定相鄰。在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲(chǔ)位置由.其宜.接前驅(qū)結(jié)點(diǎn)的鏈域的值指示。在n個(gè)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn)*p，需找到它的前驅(qū)結(jié)點(diǎn)的地址，其時(shí)間復(fù)雜度為O(n)。向量、棧和隊(duì)列都是_線性一結(jié)構(gòu)，可以在向量的任何位置插入和刪除元素；對(duì)于棧只能在棧頂_插入和刪除元素；對(duì)于隊(duì)列只能在—隊(duì)尾—插入和隊(duì)首刪除元素。棧是一種特殊的線性表，允許插入和刪除運(yùn)算的一端稱為棧頂—。不允許插入和刪除運(yùn)算的一端稱為—棧底 。隊(duì)列是被限定為只能在表的一端進(jìn)行插入運(yùn)算，在表的另一端進(jìn)行刪除運(yùn)算的線性表。在一個(gè)循環(huán)隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的前一個(gè) 位置。在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有一n-1個(gè)元素。向棧中壓入元素的操作是先存入元素，后移動(dòng)棧頂指針—從循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，其操作是先取出元素，后移動(dòng)隊(duì)首指針。帶表頭結(jié)點(diǎn)的空循環(huán)雙向鏈表的長(zhǎng)度等于_Q不包含任何字符(長(zhǎng)度為0)的串稱為空串； 中一個(gè)或多個(gè)空格(僅由空格符)組成的串—稱為空白串。設(shè)S="A;/document/Mary.doc”，則strlen(s)= 20 ,“/”的字符定位的位置為—3。子串的定位運(yùn)算稱為串的模式匹配；被匹配的主串稱為目標(biāo)串，.子串 稱為模式。設(shè)目標(biāo)T=”abccdcdccbaa”，模式P="cdcc”，則第.6 次匹配成功。若n為主串長(zhǎng)，m為子串長(zhǎng)，則串的古典(樸素)匹配算法最壞的情況下需要比較字符的總次數(shù)為，(n-m+1)*m。假設(shè)有二維數(shù)組人6彳，每個(gè)元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。已知A的起始存儲(chǔ)位置(基地址)為1000，則數(shù)組A的體積(存儲(chǔ)量)為288B；末尾元素A57的第一個(gè)字節(jié)地址為 1282 ；若按行存儲(chǔ)時(shí)，元素A14的第一個(gè)字節(jié)地址為(8+4)X6+1000=1072 ；若按列存儲(chǔ)時(shí)，元素A47的第一個(gè)字節(jié)地址為(6X7+4)X6+TOC\o"1-5"\h\z1000)=1276 。(注：數(shù)組是從0行0列還是從1行1列計(jì)算起呢？由末單元為A57可知，是從0行0列開始！)設(shè)數(shù)組a[1?60,1?70]的基地址為2048，每個(gè)元素占2個(gè)存儲(chǔ)單元，若以列序?yàn)橹餍蝽樞虼鎯?chǔ)，則元素a[32,58]的存儲(chǔ)地址為—8950 。答：不考慮0行0列，利用列優(yōu)先公式：LOC(aij)=LOC(ac1,c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L得：LOC(a3258)=2048+[(58-1)*(60-1+1)+32-1]]*2=8950 '三元素組表中的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于稀疏矩陣的一個(gè)非零元素，它包含有三個(gè)數(shù)據(jù)項(xiàng)，分別表示該元素的行下標(biāo)、列下標(biāo)和元素佰。求下列廣義表操作的結(jié)果：GetHead【((a,b),(c,d))】===(a,b); 〃頭元素不必加括號(hào)GetHead【GetTail【((a,b),(c,d))】】===(c,d) _;GetHead[GetTail【GetHead【((a,b),(c,d))】】】===b—;GetTail[GetHead[GetTail【((a,b),(c,d))】】】===(d);大多數(shù)排序算法都有兩個(gè)基本的操作：比較(兩個(gè)關(guān)鍵字的大小)__和移動(dòng)(記錄或改變指向記錄的指針)_O44.在對(duì)一組記錄(54,38,96,23，15,72,60，45,83)進(jìn)行直接插入排序時(shí)，當(dāng)把第7個(gè)記錄60插入到有序表時(shí)，為尋找插入位置至少需比較次。(可約定為，從后向前比較)在插入和選擇排序中，若初始數(shù)據(jù)基本正序，則選用插入排序(到尾部)：若初始數(shù)據(jù)基本反序，則選用— 。在堆排序和快速排序中，若初始記錄接近正序或反序，則選用_堆排』：若初始記錄基本無(wú)序，則最好選用一 。對(duì)于n個(gè)記錄的集合進(jìn)行冒泡排序，在最壞的情況下所需要的時(shí)間』On2)_。若對(duì)其進(jìn)行快速排序，在最壞的情況下所需要的時(shí)間是O(n2)。對(duì)于n個(gè)記錄的集合進(jìn)行歸并排序，所需要的平均時(shí)間』O(nlog2n)，所需要的附加空間是O(n)。對(duì)于n個(gè)記錄的表進(jìn)行2路歸并排序，整個(gè)歸并排序需進(jìn)行」ogn一趟(遍)，共計(jì)移動(dòng)nlog2n次記錄。(即移動(dòng)到新表中的總次數(shù)！共log2n趟，每趟都要移動(dòng)n個(gè)元素)設(shè)要將序列(Q,H,C,Y,P,A,M,S,R,D,F,X)中的關(guān)鍵碼按字母序的升序重新排列，則：TOC\o"1-5"\h\z冒泡排序一趟掃描的結(jié)果是 H,C,Q,P,A,M,S,R,D,F,X,Y :初始步長(zhǎng)為4的希爾(shell)排序一趟的結(jié)果是_P,A,C?S,Q?D,F?X,R,H,M,Y :二路歸并排序一趟掃描的結(jié)果是 H,Q,C,Y，A,P,M,S,D,R,F,X:快速排序一趟掃描的結(jié)果是 F,H,C,D,P,A,M,Q,R,S,YX :堆排序初始建堆的結(jié)果是 A,D,C,R,