2數(shù)據(jù)結(jié)構(gòu)-復(fù)習(xí)習(xí)題

1、一、填空題1數(shù)據(jù)結(jié)構(gòu)是彼此具有一定關(guān)系的數(shù)據(jù)元素的集合。可分為邏輯結(jié)構(gòu)和物理結(jié)構(gòu)兩個(gè)方面。2算法的效率包括兩方面，即時(shí)間復(fù)雜度和空間復(fù)雜度。所謂時(shí)間復(fù)雜度是指一個(gè)算法所需運(yùn)算次數(shù)的多少，所謂空間復(fù)雜度是指一個(gè)算法所需輔助內(nèi)存空間的大小。3對(duì)于兩個(gè)n階矩陣相乘,用C語(yǔ)言描述算法,則相應(yīng)的時(shí)間復(fù)雜度是O（n3）。4線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)結(jié)點(diǎn)中存儲(chǔ)數(shù)據(jù)元素本身的域稱為數(shù)據(jù)域，存儲(chǔ)直接后繼元素存儲(chǔ)位置的域稱為指針域。線性表是n個(gè)同類型數(shù)據(jù)元素的有限序列。5在單鏈表中,指針p所指結(jié)點(diǎn)為最后一個(gè)結(jié)點(diǎn)的條件是p->next=null。在單向鏈表結(jié)構(gòu)中，空表的條件為hanext=NULL,而在循環(huán)鏈表結(jié)構(gòu)

2、中，空表的條件是hanext=ha.6棧的操作原則是后進(jìn)先出(LIFO)，隊(duì)列的操作原則是先進(jìn)先出（FIFO）。棧是只能在表的一端進(jìn)行插入和刪除運(yùn)算的線性表。隊(duì)列是中能在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除的線性表。能進(jìn)行插入的這一端稱為隊(duì)列的尾，能進(jìn)行刪除的一端稱為隊(duì)列的頭。7結(jié)點(diǎn)所擁有的子樹(shù)的個(gè)數(shù)稱為結(jié)點(diǎn)的度，樹(shù)中結(jié)點(diǎn)的最大層數(shù)稱為樹(shù)的深度。8樹(shù)有三種常用的存儲(chǔ)結(jié)構(gòu)，即_孩子鏈表法、孩子兄弟鏈表法和雙親表示法。9設(shè)r指向單鏈表的最后一個(gè)結(jié)點(diǎn)，要在最后一個(gè)結(jié)點(diǎn)之后插入s所指的結(jié)點(diǎn)，需執(zhí)行的三條語(yǔ)句是r->next=s；r=s；r->next=null。10哈夫曼樹(shù)是帶權(quán)路徑度最短

3、的樹(shù)，通常權(quán)值較大的結(jié)點(diǎn)離根較近。11.字符串“beijing”的長(zhǎng)度為8。字符串“X123”的長(zhǎng)度4。12.樹(shù)中結(jié)點(diǎn)所擁有的子樹(shù)的個(gè)數(shù)稱為結(jié)點(diǎn)的度，樹(shù)中結(jié)點(diǎn)的最大層數(shù)稱為樹(shù)的深度。二、選擇題1數(shù)據(jù)結(jié)構(gòu)是（ D ）。（A）一種數(shù)據(jù)類型（B）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) （C）一組性質(zhì)相同的數(shù)據(jù)元素的集合 （D）相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合2算法分析的目的是（ B ）。（A）辨別數(shù)據(jù)結(jié)構(gòu)的合理性（B）評(píng)價(jià)算法的效率（C）研究算法中輸入與輸出的（D）段鑒別算法的可讀性3在線性表的下列運(yùn)算中，不改變數(shù)據(jù)元素之間結(jié)構(gòu)關(guān)系的運(yùn)算是（ D ）。（A）插入 （B）刪除 （C）排序 （D）定位4設(shè)串s1

4、=”data structures with java”,s2=“it”,則子串定位函數(shù)index(s1,s2)的值為（ D ）。(A) 15(B)16(C)17(D)185在任意一棵二叉樹(shù)的前序序列和后序序列中，各葉子之間的相對(duì)次序關(guān)系（ B ）。（A）不一定相同 （B）都相同（C）都不相同 （D）互為逆序6. 樹(shù)最適合用來(lái)表示 ( C ).(A) 有序數(shù)據(jù)元素 (B) 無(wú)序數(shù)據(jù)元素 (C) 元素之間具有分支層次關(guān)系的數(shù)據(jù)(D) 元素之間無(wú)聯(lián)系的數(shù)據(jù)7.深度為6(根的層次為1)的二叉樹(shù)至多有（ D ）個(gè)結(jié)點(diǎn)。(A) 64 (B)32 (C)31 (D)638.串是任意有限個(gè)（ C ）。(A)

5、 符號(hào)構(gòu)成的序列 (B)符號(hào)構(gòu)成的集合 (C) 字符構(gòu)成的序列(D) 字符構(gòu)成的集合9若某線性表中最常用的操作是取第i個(gè)元素和找第i個(gè)元素的前趨元素,則采用（ D ）存儲(chǔ)方式最節(jié)省時(shí)間。(A) 單鏈表 (B) 雙鏈表 (C)單向循環(huán)(D)順序表10將含100個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從根這一層開(kāi)始,每層上從左到右依次對(duì)結(jié)點(diǎn)編號(hào),根結(jié)點(diǎn)的編號(hào)為1,編號(hào)為49的結(jié)點(diǎn)X的雙親編號(hào)為（ A ）。(A) 24(B) 25 (C)23 (D) 2611.設(shè)有字符串S=“thisisastring”則下列哪一個(gè)不是S的子串（ C ）。（A）t=“this” （B）u=“isa” （C） v=“astin” （D）w

6、=“string”12設(shè)串s1 =”data structures with java”,s2=“ture”,則子串定位函數(shù)index(s1,s2)的值為（ C ）。(A) 11(B)12(C)10(D)1813. 設(shè)串s1 =”data structures with java”,s2=“java”,則子串判斷函數(shù)equal(s1,s2)的值為（ A）。(A) 0(B)1 (C)2 (D)314. 設(shè)串s1 =”data structures with java”,s2=“with”,則子串判斷函數(shù)equal(s1,s2)的值為（ A ）。(A) 0(B)1 (C)2 (D)315. 設(shè)串s

7、1 =”data structures with java”,則求子串判斷函數(shù)substr(s1,5,4)的值為（ C ）。(A) with(B)data(C)stru (D)truc16. 設(shè)串s1 =”data structures with java”,則求子串判斷函數(shù)substr(s1,10,4)的值為（ D ）。(A) with(B)data(C)stru (D)ture17設(shè)串s1 =”123”,s2=“ture”,則執(zhí)行函數(shù)concat(s1,s2)的值為（ A ）。(A)123ture(B)true123(C)1 (D)018設(shè)串s1 =”bei”,s2=“jing” ,則執(zhí)行

8、函數(shù)concat(s1,s2)的值為（ C ）。(A) 1(B)0 (C)beijing(D)jingbei19.在二叉樹(shù)的第i層上最多有（ A ）個(gè)結(jié)點(diǎn)。(A) 2i-1(B)2i-1 (C)2i(D) 2i+120.深度為k的二叉樹(shù)至多有（ B ）個(gè)結(jié)點(diǎn)。(A) 2k-1(B)2k-1 (C)2k(D) 2k+1三、判斷題 1.數(shù)據(jù)是能輸入到計(jì)算機(jī)中并能被計(jì)算機(jī)處理的一切對(duì)象。只能是整數(shù)或?qū)崝?shù)。（×）2.線性表強(qiáng)調(diào)兩個(gè)特性。一個(gè)是強(qiáng)調(diào)每個(gè)數(shù)據(jù)元素須是同類型的數(shù)據(jù)，另一個(gè)是強(qiáng)調(diào)數(shù)據(jù)元素的有序性。（）3.中綴表達(dá)式轉(zhuǎn)換為相應(yīng)的后綴表達(dá)式的原則是：先乘除后加減，先括號(hào)內(nèi)后括號(hào)外，同級(jí)運(yùn)

9、算先左后右的運(yùn)算次序。（）4.在程序設(shè)計(jì)語(yǔ)言中，一個(gè)能直接或間接調(diào)用自身的過(guò)程（或函數(shù)）稱為遞歸過(guò)程（或函數(shù)）。（）5隊(duì)列在現(xiàn)實(shí)社會(huì)中的應(yīng)用有：多任務(wù)操作系統(tǒng)、等待CPU的處理等。（）6在稀疏矩陣中，非零元素一個(gè)挨一個(gè)存儲(chǔ)的同時(shí)，必須同是將它的行號(hào)和列號(hào)存儲(chǔ)起來(lái)形成三元組結(jié)合存儲(chǔ)。（）7在很多實(shí)用的串處理系統(tǒng)中，采用一種“堆”結(jié)構(gòu)進(jìn)行動(dòng)態(tài)存儲(chǔ)分配的方法。（）8樹(shù)中度為0的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)。（）9同為一個(gè)雙親結(jié)點(diǎn)的孩子彼此稱為兄弟結(jié)點(diǎn)。（）10二叉樹(shù)的遍歷就是對(duì)樹(shù)中每個(gè)結(jié)點(diǎn)都訪問(wèn)到且只訪問(wèn)一次。（）四、問(wèn)答題 （共25分）1.數(shù)據(jù)結(jié)構(gòu)怎樣定義及其研究范圍是什么答：數(shù)據(jù)結(jié)構(gòu)是彼此具有一定關(guān)系的數(shù)據(jù)元

10、素的集合。數(shù)據(jù)結(jié)構(gòu)研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，并在這種結(jié)構(gòu)上定義相關(guān)的運(yùn)算，設(shè)計(jì)并實(shí)現(xiàn)相應(yīng)的算法，分析算法的效率。2.將中綴表達(dá)式（8+3*6）/（2+3*5-4）轉(zhuǎn)化為相應(yīng)的后綴表達(dá)式。答：836*+235*+4-/3編程實(shí)現(xiàn)求子串位置的定位函數(shù)。答：int index(s,t)Struct string s ,t ;i=1;j=1;while(i<=&&j<=Ifi=j)i=i+1;J=j+1;Else i=i-j+2;j1;If(j>Return;ElseReturn(0);4. 編程實(shí)現(xiàn)判斷兩個(gè)函數(shù)是否相等的函數(shù)，若相等則返回函數(shù)值為1，否則為0答：int equal(s,t)Struct string s,t;If!=Return(0);ElseFor(i=0;i&