數據結構網試題

數據結構試題第一章緒論、選擇題:1在數據結構中，從邏輯上可以把數據結構分成（A、動態(tài)結構和靜態(tài)結構

緊湊結構和非緊湊結構C、線性結構和非線性結構內部結構和外部結構2、算法分析的兩個主要方面是（A、空間復雜性和時間復雜性正確性和簡明性C、A、空間復雜性和時間復雜性正確性和簡明性C、可讀性和文檔性數據復雜性和程序復雜性3、以下與數據的存儲結構無關的術語是（循環(huán)隊列 B、鏈表C3、4、以下數據結構中，哪一個是線性結構（A.廣義表B、二叉樹 C稀疏矩陣54、以下數據結構中，哪一個是線性結構（A.廣義表B、二叉樹 C稀疏矩陣5、在下面的程序段中，對x的賦值語句的頻度為（FORi:=1TOnDOFORj:=1TOnDOx:=x+1;O(2n)B、O(n)2CO(2n)B、O(n)2C、O(n)D、O(log2n)6、以下哪個數據結構不是多型數據類型（C有向圖C有向圖字符串7、以下數據結構中，（

樹 7、以下數據結構中，（

樹 B字符串是非線性數據結構。以下屬于邏輯結構的是（9、順序表B.哈希表9、順序表B.哈希表C有序表單鏈表F列程序段的時間復雜度為s=0;for(i=1;i<n;i++)for(j=1;j<n;j++)s+=ij;A、O(1)

B、O(n)

C、O(2n)

2D、O(n)AA、一種數據類型10、數據結構是（B、相互之間存在一種或多種特定關系的數據元素的集合C、一組性質相同的數據元素的集合D、數據的存儲結構11、算法分析的目的是（B、評價算法的效率B、評價算法的效率D、鑒別算法的可讀性）。C、研究算法中輸入與輸出的關系12、下面程序段的時間復雜度為（for（inti=0;i<m;i++）for（intj=0;j<n;j++）a[i][j]=ij；22A、O（m） B、O（n）C、O（mn） D、O（m+n）13、執(zhí)行下面程序段時，執(zhí)行 S語句的次數為（ ）。for(inti=1;i<=n;i++)for(intj=1;j<=i;j++)S;A、n2 B、n2/2 C、n（n+1） D、n（n+1）/214、 算法的可讀性是指（ ）。A、 算法所含語句數較少B、 算法較簡單，計算機容易編譯C、 算法較簡單，人們很容易看出它的執(zhí)行結果D、 算法結構清晰，容易被算法設計者及其同行看懂15、 算法分析的主要任務是分析（ ）。A、算法是否具有較好的可讀性 B、算法中是否存在語法錯誤C、算法的功能是否符合設計要求 D、算法的執(zhí)行時間和問題規(guī)模之間的關系二、填空題：1、在數據邏輯結構的二元組 S=（D，R）表示中，D是（），R是（）。TOC\o"1-5"\h\z2、 沒有前驅的結點稱為（ ），沒有后繼的結點稱為（ ）。3、 數據的邏輯結構可以分為（ ）和（）兩大類。4、 在樹形結構中，每個結點最多只有一個（ ）。5、 為了實現隨機訪問，線性結構應該采用（ ）存儲。6、 邏輯上相鄰的結點在存儲器中也相鄰，這是（ ）存儲結構的特點。7、數據的運算是在（ ）上定義的，運算的具體實現與（ ）結構有關。8、 用數量級形式表示的算法執(zhí)行時間稱為算法的（ ）。9、 算法的執(zhí)行時間是（）的函數。10、在高級語言程序中，表示一組連續(xù)的存儲單元，通常用（ ）。11、數據的物理結構包括（ ）的表示和（ ）的表示。12、 對于給定的n個元素，可以構造出的邏輯結構有（ ），（），（），（）四種。13、 一個算法具有5個特性：（）、（）、（）、有零個或多個輸入、有一個或多個輸出。14、一個算法的時間復雜度為 （3n2+2nlog2n+4n-7）/（5n），其數量級表示為（ ）。15、 在線性結構、樹形結構和圖形結構中，前驅和后繼結點之間分另【J存在著（ ）、（）和（）的聯系。三、判斷題:TOC\o"1-5"\h\z1計算機程序處理的對象可分為數據和非數據兩大類。 （）2、構成數據的最小單位是數據項。 （）3、數據元素和結點是同一個概念。 （）4、每個結點一般包含若干個字段。 （）5、同一個結點中的各個字段類型可以不相同。 （）6、數據是由一些類型相同的數據元素構成的。 （）7、數據的邏輯結構與各數據元素在計算機中如何存儲有關。 （）8、如果數據元素值的大小改變了，則數據的邏輯結構也隨之改變。 （）9、邏輯結構相同的數據，結點類型也一定相同。 （）10、邏輯結構相同的數據，可以有多種不同的存儲方法。 （）11、邏輯結構不相同的數據，要采用不同的存儲方法來存儲。 （）12、線性結構的特征之一是：開始結點和終端結點都是唯一的。 （）13、在線性結構中，每個結點都有一個前驅、一個后繼。 （）14、線性結構可以看成是樹形結構的一個簡單特例。 （）15、樹型結構可以看成是圖狀結構的一個簡單特例。 （）16、判斷某個算法是否容易閱讀是算法分析的任務之一。 （）17、算法容易閱讀是好算法的主要標志之一。 （）18、算法必須用程序設計語言來書寫。 （）19、為了實現隨機訪問，線性結構只能用順序方法存儲。 （）20、問題的規(guī)模越大，其算法也就越長。 （）21、數據元素是數據的最小單位。 （ ）22、記錄是數據處理的最小單位。 （ ）23、數據的邏輯結構是指數據的各數據項之間的邏輯關系； （）24、算法的優(yōu)劣與算法描述語言無關，但與所用計算機有關。 （ ）25、健壯的算法不會因非法的輸入數據而出現莫名其妙的狀態(tài)。 （ ）26、算法可以用不同的語言描述，如果用 C語言或PASCAL語言等高級語言來描述，則算法實際上就是程序了。（ ）27、 程序一定是算法。（ ）28、數據的物理結構是指數據在計算機內的實際存儲形式。 （）29、在順序存儲結構中，有時也存儲數據結構中元素之間的關系。 （ ）30、順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。 （ ）四、應用題:1、評價一個好的算法，您是從哪幾方面來考慮的?

2、若有100個學生，每個學生有學號，姓名，平均成績，采用什么樣的數據結構最方便，寫出這些結構?3、在編制管理通訊錄的程序時，什么樣的數據結構合適 ？為什么？,、 3 2(3),、 3 2(3)T3(n)=3n+100n+n+1;賬號、姓名、開戶年月日、儲蓄類型、存入累2(1)Ti(n)=1000; (2)T2(n)=n+1000n;分別寫出相應的大O表示的運算時間。五、綜合題:1、設計一數據結構，用來表示某一銀行儲戶的基本信息:加數、利息、帳面總數。2、調用下列C函數f(n)或PASACAL函數f(n)，回答下列問題：試指出f(n)值的大小，并寫出f(n)值的推導過程；假定n=5，試指出f(5)值的大小和執(zhí)行f(5)時的輸出結果。C函數：intf(int n){inti,j，k,sum=0;for(i=l;i<n+1;i++){for(j=n;j>i-1;j--)for(k=1;k<j+1;k++)sum++;printf("sum=%d\n",sum);}return(sum);}

第二章線性表第二章線性表、選擇題:1、一個順序表所占存儲空間的大小與（ ）無關。A、順序表長度B、結點類型 C、結點中各字段的類型 DA、順序表長度5個內存單元，則該25個內存單元，則該結點的地址，通常是指5個內存單元中（A、第3個單元的地址B、地址值最小的那個單元的地址C、地址的一個升序序列D、地址的一個降序序列。3、順序表的長度與（ ）有關。A、線性表中有多少個結點 B、每個結點有多少個字段C、每個結點中各字段的類型 D、存儲順序表的數組類型TOC\o"1-5"\h\z4、與單向鏈表相比，雙向鏈表的優(yōu)點之一是（ ）。A、插入、刪除操作更簡單 B、可以進行隨機訪問C、可以省略表頭指針或表尾指針 D、順序訪問相鄰結點更靈活5、 動態(tài)鏈表所占用的內存單元地址一定是（ ）。A、無序的 B、連續(xù)的C、不連續(xù)的 D、部分連續(xù)的6、 與動態(tài)鏈表相比，靜態(tài)鏈表的缺點之一是（ ）。A、插入、刪除操作有時不方便 B、存儲空間有時得不到充分利用C、要求各結點具有相同的類型 D、鏈表中各結點的值只能讀取，不能更改7、如果對線性表的運算只有2種：刪除第一個元素；在最后一個元素的后面插入新元素， 則最好使用（）。A、只有表頭指針沒有表尾指針的循環(huán)單向鏈表 B、只有表尾指針沒有表頭指針的循環(huán)單向鏈表C、非循環(huán)雙向鏈表 D、循環(huán)雙向鏈表8、設H是帶表頭結點循環(huán)單向鏈表的表頭指針。當這種鏈表成為空鏈表時， （）。A、 表頭結點指針字段的值為空B、 H的值為空C、 表頭結點指針字段的值與H的值相等D、表頭結點指針字段的值與 H的地址相等9?設H是帶表頭結點循環(huán)單向鏈表的表頭指針， p是和H同類型的變量。當p指向鏈表的最后一個結點時，（）。A、 該結點指針字段的值為空B、 p為空C、 p的值與表頭結點指針字段的值相等D、 該結點指針字段的值與H的值相等10?在長度為n的（）上，刪除第一個元素，其算法的時間復雜度是 O（I）。A、只有表頭指針的不帶表頭結點的循環(huán)單向鏈表B、 只有表尾指針的不帶表頭結點的循環(huán)單向鏈表C、 只有表尾指針的帶表頭結點的循環(huán)單向鏈表D、 只有表頭指針的帶表頭結點的循環(huán)單向鏈表11?在長度為n的（）上，刪除最后一個元素，其算法的時間復雜度是 O（n）。A、只有表頭指針的循環(huán)雙向鏈表 B、只有表頭指針的非循環(huán)雙向鏈表C、只有表尾指針的非循環(huán)雙向鏈表 D、只有表尾指針的循環(huán)雙向鏈表TOC\o"1-5"\h\z12、假設某個帶頭結點的單鏈表的頭指針為 head，則判定該表為空表的條件是（ ）。A、head==NULL； B、head-〉next==NULL；C、head!=NULL； D、head->next==head；13、已知指針p和q分別指向某單鏈表中第一個結點和最后一個結點。假設指針 s指向另一個單鏈表中某個結點，則在s所指結點之后插入上述鏈表應執(zhí)行的語句為（ ）。A、q->next=s->next；s->next=p； B、s->next=p；q->next=s->next；C、p->next=s->next；s->next=q； D、s->next=q；p->next=s->next；14、 在線性表的下列運算中，不改變數據元素之間結構關系的運算是（ ）。A、插入B、刪除 C、排序 D、定位15、 下列有關線性表的敘述中，正確的是（ ）。A、 一個線性表是n個數據元素的有限序列B、 線性表中任何一個元素有且僅有一個直接前驅C、 線性表中任何一個元素有且僅有一個直接后繼D、 以上說法都不正確16、從一個長度為n的順序表中刪除第i個元素（1<i<n）時，需向前移動（）個元素。TOC\o"1-5"\h\zA、n-i B、n-i+1 C、n-i-1 D、i17、在一個單鏈表HL中，若要向表頭插入一個由指針 p指向的結點，則執(zhí)行（ ）。A、HL=p;p->next=HL; B、p->next=HL;HL=p;C、p->next=HL;p=HL;D、p->next=HL->next;HL->next=p;18、下述哪一條是順序存儲結構的優(yōu)點？（ ）A、存儲密度大 B、插入運算方便 C、刪除運算方便 D、可方便地用于各種邏輯結構的存儲表示19、 關于線性表的敘述中，錯誤的是哪一個？（ ）A、 線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。B、 線性表采用順序存儲，便于進行插入和刪除操作。C、 線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。D、 線性表采用鏈接存儲，便于插入和刪除操作。20、 線性表是具有門個（）的有限序列（n>0）。A、表元素 B、字符 C、數據元素 D、數據項21?若某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和刪除運算，則利用（ ）存儲方式最節(jié)省時間。A、順序表 B、雙鏈表 C、帶頭結點的雙循環(huán)鏈表 D、單循環(huán)鏈表

22、某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（儲方式最節(jié)省運算時間。A、單鏈表 B、僅有頭指針的單循環(huán)鏈表 C、雙鏈表 D、僅有尾指針的單循環(huán)鏈表23、設一個鏈表最常用的操作是在末尾插入結點和刪除尾結點，則選用（ ）最節(jié)省時間。A、單鏈表 B、單循環(huán)鏈表 C、帶尾指針的單循環(huán)鏈表 D、帶頭結點的雙循環(huán)鏈表24、若某表最常用的操作是在最后一個結點之后插入一個結點或刪除最后一個結點。則采用（ ）方式最節(jié)省運算時間。）存存儲A、單鏈表 B、雙鏈表 C、單循環(huán)鏈表 D、帶頭結點的雙循環(huán)鏈表）存存儲B、數組下標 C、下一元素地址D、左、右孩子地址26B、數組下標 C、下一元素地址D、左、右孩子地址26、 鏈表不具有的特點是（A、插入、刪除不需要移動元素C、不必事先估計存儲空間 D、27、 下面的敘述不正確的是（A、 線性表在鏈式存儲時，查找第B、 線性表在鏈式存儲時，查找第C、 線性表在順序存儲時，查找第D、 線性表在順序存儲時，查找第）。B、可隨機訪問任一元素所需空間與線性長度成正比）。i個兀素的時間冋i的值成正比i個兀素的時間冋i的值無關i個兀素的時間冋i的值成反比i個兀素的時間冋i的值無關TOC\o"1-5"\h\z28、若長度為n的線性表采用順序存儲結構，在其第i個位置插入一個新元素的算法的時間復雜度為 （C.O(n)2D.O(n)(1<=i<=n+1)C.O(n)2D.O(n)A.0(0) B.0(1)29、 對于順序存儲的線性表，訪問結點和增加、刪除結點的時間復雜度為（ ）。A、O（n）O（n） B、O（n）O（1） C、O（1）O（n） D、O（1）O（1）30、在單鏈表指針為p的結點之后插入指針為 s的結點，正確的操作是（ ）。A、p->next=s;s->next=p->next; B、s->next=p->next;p->next=s;C、p->next=s;p->next=s->next; D、p->next=s->next;p->next=s;二、填空題：1、順序表是一種（ ）線性表。2、往長度為n的順序表中插入一個元素，最多要移動（ ）個元素。3、在（）情況下，從順序表中刪除一個元素平均要移動近一半的元素。4、在程序中，實現動態(tài)鏈表要用到（ ）類型的變量。5、 用數組實現的鏈表，通常稱為（ ）鏈表。6、若用帶表頭結點的單向鏈表來表示長度為 n的線性表，則需要為鏈表分配（ ）個結點的內存空間7、在循環(huán)單向鏈表中，可以用（ ）代替表頭指針。8、在長度為n的順序表上實現定位操作，其算法的時間復雜度是（ 數據結構7亠9、在長度為n的單向鏈表上實現定位操作，其算法的時間復雜度是（10、在順序表（）后面插人新元素，不需要移動任何元素。11、在（）循環(huán)單向鏈表上，刪除第一個結點，其算法的時間復雜度為 0（I）。12、 根據（）多少，線性鏈表可分為單向鏈表和雙向鏈表兩大類。13、在單向鏈表中，增加一個表頭結點的目的是（ ）。14、 用數組實現單向鏈表時，通常將數組中那些空單元組織成一個（ ）。15、 往順序表中插入新元素，除了要判斷是否有空單元以外，還要判斷（ ）是否正確。16、 在非循環(huán)的（）鏈表中，可以用表尾指針代替表頭指針。17、在一個長度為100的順序表中刪除第10個元素時，需移動（ ）個元素。鏈表為空的條件分別為 （）和（）。18、在以HL為表頭指針的帶表頭附加結點的單鏈表和循環(huán)單鏈表中,鏈表為空的條件分別為 （）和（）。19、當線性表的元素總數基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表中的元素時，應采用（ ）存儲結構。20、線性表L=（a1,a2,…3用數組表示，假定刪除表中任一元素的概率相同，則刪除一個元素平均需要TOC\o"1-5"\h\z移動元素的個數是（ ）。21、設單鏈表的結點結構為（data,next）,next為指針域，已知指針 px指向單鏈表中data為x的結點，指針py指向data為y的新結點，若將結點y插入結點x之后，則需要執(zhí)行以下語句：（）;（）。22、在一個長度為n的順序表中第i個元素（1<=i<=n）之前插入一個元素時，需向后移動（ ）個元素。23?在單鏈表中設置頭結點的作用是（ ）。24.對于一個具有n個結點的單鏈表，在已知的結點p后插入一個新結點的時間復雜度為（ ）,在給定值為x的結點后插入一個新結點的時間復雜度為（ ）。25?根據線性表的鏈式存儲結構中每一個結點包含的指針個數，將線性鏈表分成（ ）和（）；而又根據指針的連接方式，鏈表又可分成（ ）和（）。26、在雙向循環(huán)鏈表中，向p所指的結點之后插入指針 f所指的結點，其操作是（）、（）、（）、（）。27、鏈接存儲的特點是利用（ ）來表示數據元素之間的邏輯關系。28、 順序存儲結構是通過（ ）表示元素之間的關系的；鏈式存儲結構是通過（ ）表示元素之間的關系的。TOC\o"1-5"\h\z29、對于雙向鏈表，在兩個結點之間插入一個新結點需修改的指針共（ ）個，單鏈表為（ ）個。30、循環(huán)單鏈表的最大優(yōu)點是： （）。31、已知指針p指向單鏈表L中的某結點，則刪除其后繼結點的語句是： （）32、帶頭結點的雙循環(huán)鏈表 L中只有一個元素結點的條件是： （）33、在單鏈表L中，指針p所指結點有后繼結點的條件是： （）34、帶頭結點的雙循環(huán)鏈表 L為空表的條件是：（）。35、 在單鏈表p結點之后插入s結點的操作是：（）。三、判斷題:1、線性結構中的結點按前驅、后繼關系可以排成一個線性序列。TOC\o"1-5"\h\z2、存儲一個線性表所需的內存單元數與線性表的元素類型有關。 （）3、空線性表的一個特征是線性表中各結點尚未賦值。 （）4、順序表是一種有序的線性表。 （）5、順序表的長度等于元素個數與每個元素所占內存單元數之乘積。 （）6、分配給順序表的內存單元地址必須是連續(xù)的。 （）7、用一維數組表示順序表時，順序表的第 i個元素必須放在下標為i的數組元素中。（）8、若表示順序表的一維數組各元素尚未賦值， 則創(chuàng)建一個空順序表的操作實際上不需要做任何事情。 （）9、 從長度為n的順序表中刪除一個元素，所需時間都是O（n）。（）10、往順序表中插入一個元素，平均要移動大約一半的元素。 （）11、在動態(tài)單向鏈表中，每個結點總是占用一片連續(xù)的內存空間。 （）12、分配給單向鏈表的內存單元地址必須是連續(xù)的。 （）13、與順序走相比；在鏈表上實現順序訪問，其算法的效率比較低。 （）14、單向鏈表中的結點只有后繼，沒有前驅。 （）15、在任何一種線性鏈表上都無法進行隨機訪問。 （）16、在循環(huán)單向鏈表中；每個結點都有一個后繼。 （）17、在畫單向鏈表示意圖時，表示指針的箭頭必須指向結點的第一個字段。 （）18、凡是空的單向鏈表都是不含任何結點的。 （）19、空的單向鏈表所表示的是長度為零的線性表。 （）20、允許進行插入、刪除操作是動態(tài)鏈表的主要特征。 （）21、一個結點的指針字段為空，說明該字段中沒有存放任何信息。 （）22、不帶表頭結點的空的單向鏈表不占用任何內存空間。 （）23、在描述單向鏈表的結點類型時，必須首先描述數值字段，然后再描述指針字段。 （）24、如果單向鏈表帶有表頭結點，則線性表的插入操作永遠不會改變表頭指針的值。 （）25、在循環(huán)單向鏈表中，任何一個結點的指針字段值都不可能為空。 （）26、雙向鏈表的表頭指針要比單向鏈表的表頭指針占用更多的內存空間。 （）27、在結點個數相同的情況下，雙向鏈表所需的內存空間是單向鏈表的兩倍。 （）28、雙向鏈表的結點，數值字段、前驅指針字段和后繼指針字段的排列順序可以是任意的。 （）29、在雙向鏈表中，每個結點一般至少有 3個字段。（）30、靜態(tài)鏈表的表頭指針是一個指針類型的變量。 （）31、鏈表中的頭結點僅起到標識的作用。 （）32、順序存儲結構的主要缺點是不利于插入或刪除操作。 （）33、線性表采用鏈表存儲時，結點和結點內部的存儲空間可以是不連續(xù)的。 （ ）34、順序存儲方式插入和刪除時效率太低，因此它不如鏈式存儲方式好。 （ ）35、對任何數據結構鏈式存儲結構一定優(yōu)于順序存儲結構。 （）36、順序存儲方式只能用于存儲線性結構。 （ ）37、集合與線性表的區(qū)別在于是否按關鍵字排序。 （ ）38、所謂靜態(tài)鏈表就是一直不發(fā)生變化的鏈表。 （ ）39、線性表的特點是每個元素都有一個前驅和一個后繼。40、取線性表的第i個兀素的時間冋i的大小有關?（)41、循環(huán)鏈表不是線性表?（ ）42、線性表只能用順序存儲結構實現。()43、線性表就是順序存儲的表。 （)44、為了很方便的插入和刪除數據，可以使用雙向鏈表存放數據。 （ ）45、順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。 （ ）四、應用題：1線性表有兩種存儲結構：一是順序表，二是鏈表。試問：（1）如果有n個線性表同時并存，并且在處理過程中各表的長度會動態(tài)變化，線性表的總數也會自動地改變。在此情況下，應選用哪種存儲結構？ 為什么？（2）若線性表的總數基本穩(wěn)定，且很少進行插入和刪除，但要求以最快的速度存取線性表中的元素,那么應采用哪種存儲結構？為什么？2、說明在線性表的鏈式存儲結構中，頭指針與頭結點之間的根本區(qū)別；頭結點與首元結點的關系。3、在單鏈表和雙向鏈表中，能否從當前結點出發(fā)訪問到任何一個結點4、設單鏈表中某指針p所指結點（即p結點）的數據域為data，鏈指針域為next，請寫出在p結點之前插入s結點的操作data,pre和next，試寫出在指針p所指結點data,pre和next，試寫出在指針p所指結點 數據結構 10 五、綜合題:1、假設有兩個按元素值遞增次序排列的線性表，均以單鏈表形式存儲。請編寫算法將這兩個單鏈表歸并為一個按元素值遞減次序排列的單鏈表，并要求利用原來兩個單鏈表的結點存放歸并后的單鏈表。2、已知L1、L2分別為兩循環(huán)單鏈表的頭結點指針， m,n分別為L1、L2表中數據結點個數。要求設計一算法，用最快速度將兩表合并成一個帶頭結點的循環(huán)單鏈表。3、已知不帶頭結點的線性鏈表 list，鏈表中結點構造為（data、link），其中data為數據域，link為指針域。請寫一算法，將該鏈表按結點數據域的值的大小從小到大重新鏈接。要求鏈接過程中不得使用除該鏈表以外的任何鏈結點空間。voiddelete(Linklist&Lvoiddelete(Linklist&L)5、給定（已生成）一個帶表頭結點的單鏈表，設 head為頭指針，結點的結構為（data,next），data為整型元素，next為指針，試寫出算法：按遞增次序輸出單鏈表中各結點的數據元素，并釋放結點所占的存儲空間。 （要求；不允許使用數組作輔助空間 ） 數據結構 11 第三章棧和隊列、選擇題:1棧和隊列的共同點在于（A、都對存儲方法作了限制B、選擇題:1棧和隊列的共同點在于（A、都對存儲方法作了限制B、都是只能進行插入、刪除運算C、都對插入、刪除的位置作了限制D、都對插入、刪除兩種操作的先后順序作了限制2、棧的“先進后出”特性是指（最后插入棧中的元素總是最早被刪除當同時進行插入、刪除操作時，總是插人操作優(yōu)先C、C、每當有刪除操作時，總要先做一次插入操作每次從棧中刪除的總是最早插入的元素3、棧是一種特殊的線性表，其特殊之處在于（A、棧具有普通線性表所沒有的邏輯特性棧的存儲方法比較特殊CA、棧具有普通線性表所沒有的邏輯特性棧的存儲方法比較特殊C、對線性表的使用方法作了限制棧比普通線性表更簡單4、與順序棧相比，鏈接棧（A、優(yōu)點是存儲管理較簡單A、優(yōu)點是存儲管理較簡單優(yōu)點是插入、刪除操作不需要移動其他元素C、C、缺點是不能順序訪問棧中元素缺點是插入、刪除操作效率較低5、最適合用作鏈接棧的鏈表是（A、不帶表頭結點的非循環(huán)單向鏈表帶表尾指針的循環(huán)單向鏈表CA、不帶表頭結點的非循環(huán)單向鏈表帶表尾指針的循環(huán)單向鏈表C、帶表頭指針的循環(huán)單向鏈表D、循環(huán)雙向鏈表6、最不適合用作鏈接棧的鏈表是（A、只有表頭指針沒有表尾指針的循環(huán)雙向鏈表A、只有表頭指針沒有表尾指針的循環(huán)雙向鏈表B、只有表尾指針沒有表頭指針的循環(huán)雙向鏈表C、C、只有表尾指針沒有表頭指針的循環(huán)單向鏈表D、只有表頭指針沒有表尾指針的循環(huán)單向鏈表7、若7、若5個元素的進棧序列是 1,2,3,4,5，則不可能得到出棧序列（A、1，A、1，2，3，4，5B、3，4，2，5，1C、4，2，1，3，55,4,8、若8、若5個元素的出棧序列是1，2，3，4，5,則進棧序列可能是（A、3,1,2,5,4A、3,1,2,5,4B、2,3,1,5,4C、3，I，4，2，54，3,1,59、當4個元素的進棧序列給定以后，由這4個元素構成的可能的出棧序列共有）種。A、14B、16C、17D、2410、鏈接棧和鏈接隊列都可以用只帶表尾指針的循環(huán)單向鏈表來表示。此時的棧和隊列（A、插入運算和刪除運算都相同A、插入運算和刪除運算都相同B、刪除運算相同，插入運算不相同C、C、插入運算相同，刪除運算不相同D、插人運算和刪除運算都不相同11、設n11、設n個元素的進棧序列是 1,3，…，n,出棧序列是P1,P2，…，Pn。若P1=n，則Pi（I=i<n）的值（A、是iA、是iB、是n-iC、是n-i+1D、有多種可能12、設n個元素的進棧序列是1,2,3，…，n,出棧序列是pi,P2，…，Pn。若Pn=n，則Pi（I=i<n）的值（ ）。A、是i B、是n-iC、是n-i+1 D、有多種可能13.設n個元素的進棧序列是p1，P2，…，Pn，出棧序列是1,2，3,…，n,。若p3=|，則p1的值（ ））A、可能是2 B、一定是214、與順序隊列相比，鏈接隊列的（A、可能是2 B、一定是214、與順序隊列相比，鏈接隊列的（A、優(yōu)點是可以實現無限長隊列C、缺點是不能進行順序訪問）。B、優(yōu)點是插人、刪除操作較簡單D、 缺點是不能根據隊首指針和隊尾指針計算隊列的長度15、如果棧和隊列都用只帶表尾指針的循環(huán)單向鏈表來表示。則棧和隊列的（A、刪除算法相同，插入算法不相同 B、插人算法相同，刪除算法不相同C、插入算法相同，刪除算法也相同 D、插人算法不相同，刪除算法也不相同16、循環(huán)順序隊列中是否可以插入下一個元素， （ ）。A、與隊首指針和隊尾指針的值有關B、只與隊尾指針的值有關，與隊首指針的值無關C、只與數組大小有關，與隊首指針和隊尾指針的值無關D、與曾經進行過多少次插入操作有關17、在順序隊列中，元素的排列順序（ ）。A、由元素插入隊列的先后順序決定B、A、由元素插入隊列的先后順序決定B、與元素值的大小有關C、與隊首指針和隊尾指針的取值有關D、與數組大小有關18、假設以數組A[n]存放循環(huán)隊列的元素,其頭、尾指針分別為front和rear18、假設以數組A[n]存放循環(huán)隊列的元素,A、（rear-front-1）%n B、（rear-front）%nC、（front-rear+1）%n D、（rear-front+n）%nTOC\o"1-5"\h\z19、在計算機內實現遞歸算法時所需的輔助數據結構是（ ）。A、棧 B、隊列C、樹 D、圖20、假設以數組A[m]存放循環(huán)隊列的元素。已知隊列的長度為 length，指針rear指向隊尾元素的下一個存儲位置，則隊頭元素所在的存儲位置為（ ）。A、（rear-length+m+1）%m B、（rear-length+m）%mC、（rear-length+m-1）%m D、（rear-length）%m21、當利用大小為n的數組順序存儲一個隊列時，該隊列的最大長度為（ ）。D、n+1D、不分順序A、n-2 BD、n+1D、不分順序22、對于棧操作數據的原則是（ ）。A、先進先出 B、后進先出 C、后進后出23、某堆棧的輸入序列為a,b,c,d23、某堆棧的輸入序列為A、aA、a,c,b,dB、b,c,d,aC、c,d,b,aD、d,c,a,b24、設計一個判別表達式中左，右括號是否配對出現的算法，采用（ ）數據結構最佳。 數據結構 13

A、線性表的順序存儲結構B、隊列A、線性表的順序存儲結構B、隊列C、線性表的鏈式存儲結構D、棧TOC\o"1-5"\h\z25、 用鏈接方式存儲的隊列，在進行刪除運算時（ ）。A、僅修改頭指針 B、僅修改尾指針 C、頭、尾指針都要修改 D、頭、尾指針可能都要修改26、循環(huán)隊列存儲在數組 A[O..m]中，則入隊時的操作為（ ）。A、rear=rear+1 B、rear=（rear+1）mod（m+1）C、rear=（rear+1）modm D、rear=（rear+1）mod（m-1）27、若用一個大小為6的數組來實現循環(huán)隊列， 且當前rear和front的值分別為0和3,當從隊列中刪除一個元素，再加入兩個元素后， rear和front的值分別為多少？（ ）。A、1和5 B、2和428、棧和隊列的共同點是（ ）。B、都是先進后出DB、都是先進后出D、沒有共同點C、只允許在端點處插入和刪除元素29、 最大容量為n的循環(huán)隊列，隊尾指針是A、（rear+1）MODn=front29、 最大容量為n的循環(huán)隊列，隊尾指針是A、（rear+1）MODn=frontC、rear+1=front30、 設棧S和隊列Q的初始狀態(tài)為空，元素隊列Q，若6個元素出隊的序列是e2，e4,A、6 B、4 C、3二、填空題：1、 具有“先進先出”特性的線性表稱為（2、棧是一種具有（ ）特性的線性表。3、 用算法語言描述順序棧時，不但要用（B、rear=frontD、（rear-l）MODn=fronte1，e2，e3，e4,e5和e6依次通過棧S，—個元素出棧后即進e3,e6,e5,e1則棧S的容量至少應該是（ ）。D、2）。）表示其存儲空間，而且還要用一個變量表示（ ）。4、即使知道隊首指針和隊尾指針的值，也無法計算出元素個數的隊列，一定是（ 。隊列。5、如果程序所要處理的數據元素是逐步產生的，而且要求處理數據元素的順序和產生數據元素的順序正好相反，則通常用（ 。暫存待處理的數據。6、順序棧和鏈接錢的區(qū)別僅在于（ 。的不同。TOC\o"1-5"\h\z7、 在編寫程序的時候，如果棧的最大長度難以估計，則最好使用（ ）。8、棧和隊列的區(qū)別僅在于（ ）。9、若用Q[0]~Q[100]作為循環(huán)順序隊列的存儲空間， Q[f]、Q[r]分別表示隊首元素和下一個插人位置，則當f=70,r=20時，隊列中共有（。個元素。10、順序隊列在實現的時候；通常將數組看成是一個首尾相連的環(huán)，這樣做的目的是為避免產生（ ?，F象。11、若用只有隊尾指針沒有隊首指針的循環(huán)單向鏈表來表示鏈接隊列，則在進行刪除操作的過程中，不僅需要判斷（ 。，而且還要判斷（ ）。12、若用Q[0]~Q[m]作為循環(huán)順序隊列的存儲空間， Q[r]表示隊尾元素，Q[f]表示隊首元素的前一個位置,則可以用（ 。作隊空的標志，與此相對應，可用（ 。作隊滿的標志。 數據結構 14 13、隊列的隊尾位置通常是隨著（ ）操作而變化的。14、棧是（ ）的線性表，其運算遵循（ ）的原則。15、 （）是限定僅在表尾進行插入或刪除操作的線性表。16、一個棧的輸入序列是：1,2，3則不可能的棧輸出序列是（ ）。17、 設有一個空棧，棧頂指針為1000H（十六進制），現有輸入序列為1，2，3，4，5，經過PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，輸出序列是（ ），而棧頂指針值是（ ）H。設棧為順序棧，每個元素占4個字節(jié)。18、在作進棧運算時應先判別棧是否 （）；在作退棧運算時應先判別棧是否 （）；當棧中元素為n個，TOC\o"1-5"\h\z作進棧運算時發(fā)生上溢，則說明該棧的最大容量為（ ）。19、多個棧共存時，最好用（ ）作為存儲結構。20、用S表示入棧操作，X表示出棧操作，若元素入棧的順序為 1234，為了得到1342出棧順序，相應的S和X的操作串為（ ）。21、順序棧用data[1..n]存儲數據，棧頂指針是 top,則值為x的元素入棧的操作是（ ）。22、表達式23+（（123-2）/4+345⑺+108/9的后綴表達式是（ ）。23、 循環(huán)隊列的引入，目的是為了克服（ ）。24、 （ ）又稱作先進先出表。25、 隊列的特點是（ ）。26、已知鏈隊列的頭尾指針分別是 f和r，則將值x入隊的操作序列是（ ）。27、區(qū)分循環(huán)隊列的滿與空，只有兩種方法，它們是（ ）和（ ）。28、設循環(huán)隊列存放在向量sq.data[0:M]中，則隊頭指針sq.front在循環(huán)意義下的出隊操作可表示為 （），若用犧牲一個單元的辦法來區(qū)分隊滿和隊空（設隊尾指針 sq.rear）,則隊滿的條件為（ ）。29、表達式求值是（ ）應用的一個典型例子。30、循環(huán)隊列用數組A[0..m-1]存放其元素值，已知其頭尾指針分別是 front和rear，則當前隊列的元素個數是（ ）。三、判斷題：1、棧是一種存儲方法比較特殊的線性表。 （）2、棧底元素是不能刪除的元素。 （）3、順序棧中元素值的大小是有序的。 （）4、進棧越早的元素，出棧越晚。 （）5、在n個元素進棧后，它們的出棧順序和進棧順序一定正好相反。 （）6、順序棧的棧頂指針是一個指針類型的變量。 （）7、順序棧是一種規(guī)定了元素進棧順序的棧。 （）8、對于順序棧來說，棧底元素的下標不能大于棧頂元素的下標。 （）9、對于順序找來說，棧頂指針的類型必須和數組下標的類型相同。 （）10、棧頂元素和棧底元素有可能是同一個元素。（）11、對于非空的棧來說，棧頂元素和棧底元素都是唯一的。 （） 數據結構 15 TOC\o"1-5"\h\z12、對于順序棧來說，棧頂指針的移動方向只與插人、刪除操作有關。 （）13、若用s[1]~s[m]表示順序棧的存儲空間，則對棧的插人、刪除操作最多只推進行 m次。（）14、對順序棧進行插入、刪除操作，不涉及元素的前、后移動問題。 （）15、棧是一種對插入、刪除操作總次數作了限制的線性表。 （）16、棧是一種對插入、刪除操作的次序作了限制的線性表。 （）17、插入、刪除操作比較簡單是鏈接棧的優(yōu)點之一。 （）18、如果兩個順序棧有共同的元素，則可以共用同一個數組。 （）19、棧和隊列都不適合用散列存儲法存儲。 （）20、棧和隊列具有相同的邏輯特性。 （）21、空棧沒有棧頂指針。（）22、空棧是指棧中兀素尚未賦值。 （）23、空棧是指棧項指針尚未賦值。 （）24、n個元素進隊列的順序和出隊列的順序總是一致的。 （）25、順序隊列中有多少元素，可以根據隊首指針的值和隊尾指針的值來計算。 （）26、循環(huán)隊列中每個元素都有后繼。 （）27、循環(huán)隊列沒有開始結點和終端結點。 （）28、 若用“隊首指針的值和隊尾指針的值相等”作為循環(huán)順序隊列為空的標志，則在設置一個空隊列時，只需給隊首指針和隊尾指針賦同一個值，不管什么值都可以。 （）29、無論是順序隊列，還是鏈接隊列，插人、刪除運算的時間復雜度都是 0（1）。（）30、若用不帶表頭結點的非循環(huán)單向鏈表來表示鏈接隊列， 則可以用“隊首指針的值和隊尾指針的位相等”作為隊空的標志。（）四、應用題：1、什么是隊列的假上溢現象，怎么解決？2、有5個元素，其入棧次序為：A,B,C,D,E,在各種可能的出棧次序中，以元素 C,D最先出棧（即C第一個且D第二個出棧）的次序有哪幾個？3、設輸入序列為2,3,4,5,6，利用一個棧能得到序列2,5,3,4,6嗎？?？梢杂脝捂湵韺崿F嗎? 數據結構 16 4、在一個算法中需要建立多個堆棧時可以選用下列三種方案之一，試問：這三種方案之間相比較各有什么優(yōu)缺點？分別用多個順序存儲空間建立多個獨立的堆棧;多個堆棧共享一個順序存儲空間；分別建立多個獨立的鏈接堆棧。5、設一個雙端隊列，元素進入該隊列的次序為 a,b，c,d。求既不能由輸入受限的雙端隊列得到 ，又不能由輸出受限的雙端隊列得到的輸出序列。五、綜合題:1、設從鍵盤輸入一整數的序列： ai,a2,a3,…，a.,試編寫算法實現：用棧結構存儲輸入的整數，當 a乂1時，將可進棧；當ai=-i時，輸出棧頂整數并出棧。算法應對異常情況(入棧滿等)給出相應的信息。2、假設以帶頭結點的循環(huán)鏈表表示隊列，并且只設一個指針指向隊尾結點，但不設頭指針，請寫出相應的入隊列和出隊列算法。3、如果允許在循環(huán)隊列的兩端都可以進行插入和刪除操作。要求:寫出循環(huán)隊列的類型定義；寫出從隊尾刪除”和從隊頭插入”的算法。4、設計算法以求解從集合的所有組合的輸出結果為：{1..n}中選取k(k<=n)個兀素的所有組合。例如，從集合 {1..4}中選取2個兀素1 2,1 3,1 4,23, 24,3 4。 數據結構 17

第四章串第四章串、選擇題:TOC\o"1-5"\h\z1判斷兩個串大小的基本準則是（ ）。A、兩個串長度的大小 B、兩個串中首字符的大小C、兩個串中大寫字母的多少 D、對應的第一個不等字符的大小2、通常將鏈串的結點大小設置為大于 1是為了（ ）。A、提高串匹配效率 B、提高存儲密度C、便于插入操作 D、便于刪除操作3、設串sl="DataStructureswithJava",s2="it"，則子串定位函數 index（s1,s2）的值為（ ）。A、 15 B、16 C、17 D、184、下面關于串的的敘述中，哪一個是不正確的？（ ）。A、串是字符的有限序列 B、空串是由空格構成的串C、C、模式匹配是串的一種重要運算D、串既可以采用順序存儲，也可以采用鏈式存儲5、設有兩個串p和q,其中q是p的子串，求q在p中首次出現的位置的算法稱為（ ）。A、求子串 B、聯接 C、匹配 D、求串長6、若串S=6、若串S='software其子串的數目是（C、36A、8 B、377、串的長度是指（ ）。A、串中所含不同字母的個數C、串中所含不同字符的個數）。D、9B、串中所含字符的個數D、串中所含非空格字符的個數、填空題:TOC\o"1-5"\h\z1、 設S='lamateacher',則其長度為（ ）。2、設s1='goods2='',s3='bye!',貝Us1,s2,s3連接后的結果是（ ）。3、 空格串是指（ 。，其長度等于（ 。。4、 組成串的數據元素只能是（ ）。5、 一個字符串中（。稱為該串的子串。6、INDEX（'DTASTRUCTURE, 'STR'=（ 。。7、設正文串長度為n,模式串長度為m,則串匹配的KMP算法的時間復雜度為（ ）。8、設T和P是兩個給定的串，在T中尋找等于P的子串的過程稱為（ 。，又稱P為（）。9、串是一種特殊的線性表，其特殊性表現在（ ）;串的兩種最基本的存儲方式是（ ）、（ ）。10、 兩個字符串相等的充分必要條件是（ ）。三、判斷題:1、KMP算法的特點是在模式匹配時指示主串的指針不會變小（ ）。 數據結構 18

2、設模式串的長度為m,目標串的長度為n,當n~m且處理只匹配一次的模式時，樸素的匹配（即子串定位函數）算法所花的時間代價可能會更為節(jié)?。?）。3、 串是一種數據對象和操作都特殊的線性表（ ）。四、 應用題：1簡述空格串與空串的區(qū)別。2、如果兩個串含有相等的字符，能否說它們相等？五、 綜合題：1、編寫程序，統(tǒng)計在輸入字符串中各個不同字符出現的頻度并將結果存入文件（字符串中的合法字符為A-Z這26個字母和0-9這10個數字）。第五章數組和廣義表）。B）。B、節(jié)省存儲空間D、便于增加或減少矩陣中的非零元素字鏈表表示，其優(yōu)點在于（1、 用三元組順序表表示稀疏矩陣，目的是為了（A、對非零元素進行隨機訪問C、便于插人或刪除矩陣元素2、 與三元組順序表相比，稀疏矩陣用A、 便于實現增加或減少矩陣中非零元素的操作B、 便于實現增加或減少矩陣元素的操作C、 可以節(jié)省存儲空間）。B、無法根據行列號查找某個矩陣元素）。B、無法根據行列號查找某個矩陣元素D、使矩陣元素之間的邏輯關系更加復雜數據結構193、 對稀疏矩陣采用壓縮存儲，其缺點之一是（A、無法判斷矩陣有多少行多少列C、無法根據行列號計算矩陣元素的存儲地址

4、特殊矩陣用行優(yōu)先順序表表示， （）。A、簡化了矩陣元素之間的邏輯關系 B、便于按行處理矩陣元素C、無法根據行列號計算矩陣元素的存儲地址 D、可以節(jié)省存儲空間5、 所謂特殊矩陣是指（ ）比較特殊。A、矩陣元素之間的關系 B、矩陣的處理方法C、矩陣元素的取值 D、矩陣的存儲方法6、特殊矩陣不同于一般的稀疏矩陣，是因為（ ）。A、特殊矩陣中值相同的元素分布有規(guī)律 B、特殊矩陣中值相同的元素分布比較密集C、特殊矩陣中值相同的元素較少 D、特殊矩陣有特殊的用途7、所謂稀疏矩陣是指（ ）的矩陣。A、零元素較多且分布無規(guī)律 B、非零元素較少C、元素較少 D、不適合用二維數組表示8、10階3對角矩陣用行優(yōu)先順序表表示，矩陣中第 7行第8列元素在順序表中（ ）。A、是第20個元素 B、是第21個元素C、是第22個兀素 D、不存在A、減少矩陣的存儲空間需求量。CA、減少矩陣的存儲空間需求量。C、減少非零元素的存儲空間需求量10、矩陣用行優(yōu)先順序表表示以后，A、減少了存儲空間的需求量C、只能按行優(yōu)先順序訪問矩陣元素B、減少訪問非零元素所需時間D、降低非零元素間邏輯關系的復雜程度（）°B、增加了存儲空間的需求量D、存取矩陣元素所需時間保持不變2個單元，按行優(yōu)先順序存儲，起始地址為1000，第4行第5列的那個2個單元，按行優(yōu)先順序存儲，起始地址為1000，第4行第5列的那個A、 A、 1046 B、1044C、 1048 D、102312、8階方陣，每個元素占1個單元，按行優(yōu)先順序存儲，起始地址為 100,存儲地址為135的那個元素是矩陣中第5行第（ ）列元素。A、2B、3 C、4D、513、對于一個非空的廣義表來說， （）°A、可能不含任何原子元素 B、至少含一個原子元素C、其長度不小于其中任何一個子表的長度 D、至少含一個非空的子表元素14、在表示丿義表L=（（））的鏈接存儲結構中，有（ ）個結點。A、0 B、1C、2 D、315、在一個長度為n,含m個原子的廣義表中，()°A、m和n相等B、m不大于nC、m不小于nD、m和n無關16、下列4個廣義表中，長度為1，深度為4的廣義表是（ ）°A、（（），（（a））） B、（（（（a）,b））,c） C、（（（a,b）,（c））） D、（（（a,（b）,c）））17、空的廣義表，是指廣義表（ ）° 數據結構 20

A、深度為0 B、尚未賦值 C、不含任何原子TOC\o"1-5"\h\z18、對于廣義表((a,b),(()),(a,(b)))來說，其( )。A、長度為4 B、深度為4C、有3個元素19、 設有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲,1,每個元素占一個地址空間，則 a85的地址為( )。D、不含任何元素D、有2個元素an為第—「元素,其存儲地址為A、 13 B、D、不含任何元素D、有2個元素an為第—「元素,其存儲地址為20、假設以行序為主序存儲二維數組 A=array[1..100，1..100]，設每個數據元素占2個存儲單元，基地址為10」LOC[5，5]=( )。A、 808 B、818 C、1010 D、10201000的內存單元中，則21、數組A[0..5,0..6]1000的內存單元中，則A、1175 B、1180C、1205D、A、1175 B、1180C、1205D、1210i=0,1,…列下標j=1,2,…,10右A按行先)的起始地址相同。設每個字符占一個字22、二維數組i=0,1,…列下標j=1,2,…,10右A按行先)的起始地址相同。設每個字符占一個字A、A[8,5] B、A[3,10] C、A[5,8] D、A[0,9]23、A[N,N]是對稱矩陣，將下面三角(包括對角線)以行序存儲到一維數組 T[N(N+1)/2]中，則對任一上三角元素a[i][j]對應T[k]的下標k是()。A、i(i-1)/2+j B、j(j-1)/2+i C、i(j-i)/2+1D、j(i-1)/2+124、有一個10090的稀疏矩陣，非 0元素有10個，設每個整型數占 2字節(jié)，則用三元組表示該矩陣時，TOC\o"1-5"\h\z所需的字節(jié)數是( )。A、60 B、66 C、18000 D、3325、 數組A[0..4,-1..-3,5..7]中含有元素的個數( )。A、55 B、45 C、36 D、1626、已知廣義表L=((x,y,z),a,(u,t,w)),從L表中取出原子項t的運算是()。A、head(tail(tail(L))) B、tail(head(head(tail(L))))C、head(tail(head(tail(L)))) D、head(tail(head(tail(tail(L)))))27、已知廣義表LS=((a,b,c),(d,e,f)),運用head和tail函數取出LS中原子e的運算是( )。A、A、head(tail(LS))B、tail(head(LS))C、C、head(tail(head(tail(LS)))D、head(tail(tail(head(LS)))))。Head(Tail(Head(Tail(Tail(A)))))28、廣義表A=(a,b,(c,d),(e,(f,g))),則下面式子的值為)。Head(Tail(Head(Tail(Tail(A)))))TOC\o"1-5"\h\zA、(g) B、(d) C、c D、d29、 廣義表運算式Tail(((a,b),(c,d)))的操作結果是( )。A、(c,d) B、c,d C、((c,d)) D、d30、 廣義表(a,(b,c),d,e)的表頭為()。A、a B、a,(b,c) C、(a,(b,c)) D、(a)31、設廣義表L=((a,b,c))，貝UL的長度和深度分別為( )。 數據結構 21

A、1和1 B、1和332、下面說法不正確的是（B、廣義表的表尾總是一個廣義表DB、廣義表的表尾總是一個廣義表D、廣義表可以是一個多層次的結構C、廣義表難以用順序存儲結構、填空題:1、矩陣用一維數組表示時，有行優(yōu)先順序和（ ）兩種實現方法。2、m行n列矩陣可以看成是長度為（ ）的線性表，表中的每個元素是長度為 m的線性表。3、10行20列矩陣若用行優(yōu)先順序表來表示，則矩陣中第 8行第7列元素是順序表中的第（ ）個元素。4、10行20列矩陣若用列優(yōu)先順序表來表示，則矩陣中第 7行第8列元素是順序表中的第（ ）個元素。5、10階三對角矩陣若用行優(yōu)先順序表來表示， 則矩陣中第6行第7列元素是順序表中的第（）個元素。6、用行優(yōu)先順序表表示10階對稱矩陣，若存儲主對角線上的元素，則順序表的長度為（ ）；若不存儲TOC\o"1-5"\h\z主對角線上的元素，則順序表的長度為（ ）。7、 用順序方法存儲三元組線性表，通常有兩種實現方法，即（ ）。8、（）是一種常用的表示三元組線性表的鏈接存儲結構。9、 廣義表中的每個兀素可以是（ ），也可以是（ ）。10、 可以將廣義表看成是（）的推廣。11、 廣義表通常用（ ）方法存儲。12、廣義表（（（a,b,（）,c）,d）,e,（（f）,g））的長度是（ ），深度是（ ）。三、判斷題：矩陣每一行的元素個數都是相等的。 （）矩陣的行數和列數可以不相等。 （）用一維數組表示矩陣，可以簡化對矩陣的存取操作。 （）矩陣一般用二維數組表示。（）對稱矩陣的行數和列數一定是相同的。 （）具有特殊用途的矩陣稱為特殊矩陣。 （）對角矩陣的特點是非零元素只出現在矩陣的兩條對角錢上。 （）&在n階三對角矩陣中，每一列都有 3個非零元素。（）9.在n階三對角矩陣中，每一行都有 n個元素。（）10.若用列優(yōu)先順序表來表示 n階三對角矩陣，則該順序表的長度為 3n。（）稀疏矩陣的特點是矩陣中元素較少。 （）12?在表示矩陣的三元組順序表中，各元素的排列順序與矩陣元素值的大小有關。 （）13?十字鏈表是三元組線性表的一種鏈接存儲結構。 （）14?非零元素較少的特殊矩陣最好用三元組順序表或十字鏈表表示。 （）15?在按行優(yōu)先順序存儲的三元組線性表中，各元素的排列順序只與每個元素的行下標有關，與每個元素的列下標無關。（） 數據結構 22 16?用三元組順序表表示稀疏矩陣，其優(yōu)點之一是可以隨機訪問矩陣中每個非零元素。TOC\o"1-5"\h\z17.用一維數組表示特殊矩陣，其目的是為了節(jié)省存儲空間。 （）18?矩陣作為一種特殊的線性表，其長度通常不能為零。 （）19?矩陣用一維數組表示，可以節(jié)省存儲空間。 （）矩陣作為一種特殊的線性表，其長度通常是固定不變的（ ）廣義表的長度與廣義表中含有多少個原子元素有關。 （）廣義表的深度與廣義表中含有多少個子表元素有關。 （）在廣義表中，每個原子的類型都是相同的。 （）在廣義表中，每個子表的結構都是相同的。 （）在廣義表中，每個原子必須是單個字符。 （）“空的廣義表”是指廣義表中不包含原子元素。 （）廣義表的長度不小于其中任何一個子表的長度。 （）若用鏈接方法存儲廣義表，則所需存儲空間大小與廣義表的長度成正比。 （）四、應用題：1、數組A[1..8,-2..6,0..6]以行為主序存儲，設第一個元素的首地址是 78,每個元素的長度為4，試求元素A[4,2,3]的存儲首地址。2、假設按低下標優(yōu)先存儲整型數組 A（-3:8,3:5,-4:0,0:7）時，第一個元素的字節(jié)存儲地址是100,每個整數占4個字節(jié)，問A（0,4,-2,5）的存儲地址是什么？3、三維數組A[1..10,-2..6,2..8]的每個元素的長度為4個字節(jié)，試問該數組要占多少個字節(jié)的存儲空間？如果數組元素以行優(yōu)先的順序存貯，設第一個元素的首地址是 100,試求元素A[5,0,7]的存貯首地址。五、綜合題:1、編寫一個過程，對一個nXi矩陣，通過行變換，使其每行元素的平均值按遞增順序排列。2、給定有m個整數的遞增有序數組 a[1..m]和有n個整數的遞減有序數組 b[1..n]，試寫出算法：將數組a和b歸并為遞增有序數組 c[l..m+n]。要求：算法的時間復雜度為 0（m+n）） 數據結構 23

第六章樹和二叉樹、選擇題:對于一棵具有n個結點、度為4的樹來說，（）。A、樹的高度至多是 n-3 B、樹的高度至多是 n-4C、第i層上至多有4（i-1）個結點 D、至少在某一層上正好有 4個結點2、對于一棵具有n個結點、度為4的樹來說，樹的高度至少是（ ）。A、「logA、「log42n」B、rlog4(3n-1)」C、「log4(3n+1)」D、「log4(2n+1)J3、 度為43、 度為4、高度為h的樹，（A、至少有h+3個結點C、至多有4h個結點4、 用雙親數組表示樹，其優(yōu)點之A、找指定結點的雙親C、找指定結點的兄弟5、 用孩子鏈表表示樹，其優(yōu)點之A、判斷兩個指定結點是不是兄弟C、判斷指定結點在第幾層6、 如果用孩子鏈表來表示樹，則（A、樹的高度等于各鏈表長度的最大值C、樹的度數等于各鏈表長度的最大值A、每個結點都有一個或兩個孩子結點C、至少有一個度為2的結點10、 “二叉樹為空”意味著二叉樹（A、由一些沒有賦值的空結點構成C、不存在11、 在高度為h的完全二叉樹中，（A、度為0的結點都在第h層上）。B、至多有4h-l個結點D、至少有h+4個結點

?是（ ）比較方便。B、找指定結點的孩子D、判斷某結點是不是樹葉）比較方便。B、找指定結點的雙親D、計算指定結點的度數）°B、樹葉的數目和鏈表的數目成反比

D、結點的數目等于各鏈表長度之和7、如果在表示樹的二叉鏈表中有 6個空的左指針域，7個空的右指針域，5個結點左、右指針域都為空,TOC\o"1-5"\h\z則該樹中樹葉的個數（ ）°A、有7個B、有6個 C、有5個 D、不能確定8、如果用二叉鏈表來表示一棵具有 n（n>1）個結點的樹，則在二叉鏈表中（ ）°A、至多有n-1個非空的右指針域B、至少有2個空的右指針域C、至少有2個非空的左指針域 D、至多有n-1個空的右指針域9、二叉樹和度為2的樹的相同之處包括（ ）°B、至少有一個根結點D、每個結點至多只有一個雙親結點）°B、根結點沒有子樹D、沒有結點）°B、第i（1wi<n）層上的結點都是度為 2的結點 數據結構 24

C、第i（1Wi<n）層上有2i1個結點 D、不存在度為1的結點12、每個結點的度或者為 0或者為2的二叉樹稱為正則二叉樹，對于 n個結點的正則二叉樹來說，它的最大高度是（ ）。D、(n+1)/2A、「log2n」B、(n-1)/2C、「log2D、(n+1)/213、若樹中結點的前序序列是 abcdef,后序序列是bdecfa,則（）。A、結點c有兩個孩子 B、樹有兩個度為0的結點C、樹的高度為5 D、不能唯一確定該樹的結構14、若樹中結點的前序序列是 abcdefg，后序序列前面3個結點是bde，則后序序列的后面4個結點有可能是（）。A、gcfaB、gacfC、afgcD、cfgaTOC\o"1-5"\h\z15、 若某棵二叉樹結點的前序序列和中序序列相同，則該二叉樹（ ）。A、只有一個結點 B、每個結點都沒有左孩子C、每個結點都沒有右孩子 D、不存在16、 若某棵二叉樹結點的后序序列和層次序序列正好相反，則該二叉樹（ ）。A、每個結點都沒有右孩子 B、不存在度為2的結點C、每個結點都沒有左孩子 D、不存在17、 若某棵二叉樹結點的前序序列和后序序列相同，則該二叉樹（ ）。A、度為1 B、只有一個結點C、每個結點都沒有左孩子 D、每個結點都沒有右孩子18、在一棵高度小于4的二叉樹中，若結點的前序序列是 abcdef，則結點的中序序列有可能是（ ）。A、dcebafBA、dcebafB、bcdafeC、cbdafeD、fcadbe19、若二叉樹中結點的中序序列是19、若二叉樹中結點的中序序列是abcdef，則結點的前序序列不可能是（A、dbacefBA、dbacefB、 acbedfC、efbacdD、bafdce20、在一棵高度小于5的二叉樹中，若結點的中序序列是 abcdef；則結點的后序序列有可能是（ ）。A、bdfecaBA、bdfecaB、befdcaC、bdefcaD、fedcba21、在任何一棵二叉樹中，如果結點中，（）。21、在任何一棵二叉樹中，如果結點中，（）。a有左孩子b、右孩子c,則在結點的前序序列、中序序列、后序序列A、結點b一定在結點a的前面B、結點a一定在結點c的前面C、結點b一定在結點c的前面D、結點a一定在結點b的前面22、若二叉樹結點的前序序列是 abcd，后序序列是dcba，則該二叉樹（ ）。A、每個分支結點都沒有左孩子 B、每個分支結點都只有一個孩子C、每個分支結點都沒有右孩子 D、高度可能為323、如果二叉樹中結點的前序序列是… a…b…中序序列是…b…a…則（ ）。A.結點a和結點b分別在某結點的左子樹和右子樹中B、結點b在結點a的右子樹中C、結點b在結點a的左子樹中 數據結構 25

D、結點a和結點b分別在某結點的兩棵非空子樹中中序序列和后序序列中，結點a、b的位置都是a在前、b中序序列和后序序列中，結點a、b的位置都是a在前、b在后（即形a、a、b可能是兄弟a可能是b的雙親C、a可能是b的孩子不存在這樣的二叉樹25C、a可能是b的孩子不存在這樣的二叉樹25、如果二叉樹結點的前序序列和中序序列分別是定是cbfgehdaC、不存在abcdefgh和bcafegdh，則后序序列B、可能是cbgefhdaD、有多種可能2626、如果完全二叉樹結點的后序序列是 abcdefgh，則結點的前序序列（A、不能唯一確定A、不能唯一確定B、是hgfedcbaC、C、是abdchegfD、是hdbacgef27二叉樹若用順序方法存儲，則下列四種運算中的（27二叉樹若用順序方法存儲，則下列四種運算中的（）最容易實現。A、前序遍歷二叉樹B、判斷兩個指定結點是不是在同一層上C、A、前序遍歷二叉樹B、判斷兩個指定結點是不是在同一層上C、層次遍歷二叉樹D、根據結點的位查找其存儲位置28.對含有n個結點、高度為h的二叉樹進行非遞歸后序遍歷，所需棧容量（A、大于hB、等于h C、等于nD、小于n29、29、根據使用頻率為五個字符設計的哈夫曼編碼不可能是（110110,10,01,00B、000,001,010,011,lC、100,11,10,D、001C、100,11,10,D、001,000,01,11,1030、用整數1,2,3,4,5作為五個樹葉的權值，可構造一棵帶權路徑長度值為（）的哈夫曼樹。33B、15C、34D、54填空題:填空題:1、在樹形結構中，如果某結點（如果某棵樹（ ），則稱該樹為度為）,則稱該結點為根結點；如果某結點（n1、在樹形結構中，如果某結點（如果某棵樹（ ），則稱該樹為度為）,則稱該結點為根結點；如果某結點（n的樹；如果某棵樹（）,則稱該樹為高度為則稱該結點為樹葉;n的樹。2、高度為h，度為k的樹中至少有（）個結點，至多有（個結點。3、樹的存儲方法主要有（）和（ ）三種。4、在高度為h（h仝0）的二叉樹中至多有（）個結點,至少有（）個結點。5、n個結點的二叉樹最大高度是（）,最小高度是（62、高度為h，度為k的樹中至少有（）個結點，至多有（個結點。3、樹的存儲方法主要有（）和（ ）三種。4、在高度為h（h仝0）的二叉樹中至多有（）個結點,至少有（）個結點。5、n個結點的二叉樹最大高度是（）,最小高度是（6、n個結點的二叉樹中如果有 m個樹葉，則一定有（）個度為1的結點，（）個度為2的結點。7、高度為h的滿二叉樹中有（ ）個結點。高度為h的完全二叉樹中至少有（）個結點，至多有（個結點。9、3個結點可以構成（ ）種不同形狀的樹，可以構成（）種不同形狀的二叉樹。10、若用二叉鏈表來存儲具有 m個樹葉、n個分支結點的樹。則二叉鏈表中有（）個左指針域為空的結點，有（ ）個右指針域為空的結點。

結點，有（ ）個右指針域為空的結點。11、在具有11、在具有n個結點的二叉鏈表中共有（）個空指針域。12、 二叉樹的存儲方法主要有（ ）和（ ）兩種。13、在有n個結點的順序存儲的完全二叉樹中， 若某結點在數組中的下標是 i，且ivn/2,則該結點的雙親、左孩子和右孩子在數組中的下標分別是（ ）、（）和（ ）。14、 二叉樹中結點的前序序列是通過對二叉樹進行（ ）遍歷得到的。15、在任何一棵二叉樹中， 若結點a有左孩子b、右孩子c,則在結點的前序序列、 中序序列、后序序列中,結點（ ）一定在結點（ ）前面。16?根據二叉樹的中序序列和（ ）序列，可以唯一地確定其邏輯結構。17.如果二叉樹A和B共有相同形式的二叉鏈表存儲結構，則 A的（）序列和B的（）序列相同。18?在對二叉樹進行非遞歸前序遍歷過程中，需要用（ ）來暫存所訪問結點的地址。在對二叉樹進行層次遍歷過程中，需要用（ ）來暫存所訪問結點的地址。在（）線索二叉樹中。有可能每個結點的右孩子指針域都不為空。在（ ）線索二叉樹中，有可能每個結點的左孩子指針域都不為空。具有（ ）值的二叉樹稱為哈夫曼樹。用整數1,2,3,4,5作為5個樹葉的權值，可以構造出（ ）棵最優(yōu)二叉樹，每棵最優(yōu)二叉樹TOC\o"1-5"\h\z的帶權路徑長度值都是（ ）。24、具有256個結點的完全二叉樹的深度為（ ）。25、 已知二叉樹有50個葉子結點，則該二叉樹的總結點數至少是（ ）。26、 8層完全二叉樹至少有（ ）個結點，擁有100個結點的完全二叉樹的最大層數為（ ）。27、有一份電文中共使用 6個字符：a,b,c,d,e,f,它們的出現頻率依次為 2,3,4,7,8,9，試構造一棵哈夫曼樹，則其加權路徑長度WPL為（），字符c的編碼是（）。28、 如果結點A有3個兄弟，而且B是A的雙親，貝UB的度是（ ）。29、高度為8的完全二叉樹至少有（）個葉子結點。30、已知一棵度為3的樹有2個度為1的結點，3個度為2的結點，4個度為3的結點，則該樹有（)個葉子結點。三、判斷題：1、樹形結構中的每個結點都有一個前驅。()TOC\o"1-5"\h\z2、樹形結構中的每個結點至多只有一個前驅。 （）3、度為k的樹中至少有一個度為k的結點。（）4、在樹形結構中，處于同一層上的各結點之間都存在兄弟關系。 （）5、 度為k的樹中，每個結點至多有k-1個兄弟。（）6、在用圖示法表示樹形結構時，每一條邊必須畫成一樣長。 （）7、如果樹中有m個分支結點，n個終端結點，則在表示這棵樹的孩子鏈表中共有 m個鏈表。（）8、如果樹用雙親數組表示，則判斷某個結點是不是其他結點的雙親是很方便的。 （）9、如果樹用雙親數組表示，則判斷某個結點是不是其他結點的孩子是很方便的。 （）10、如果樹用左孩子右兄弟鏈表表示，則找任何一個結點的孩子都是很方便的。 （） 數據結構 27

11、如果樹用左孩子右兄弟鏈表表示，則找任何一個結點的兄弟都是很方便的。 （）12、如果樹用二叉鏈表表示，則某個結點是不是樹葉的條件是該結點左、 右兩個指針域的值都為空。（）13、 二叉樹是度為2的樹。（）14、 度為2的樹是二叉樹。（）15、n（n>2）個結點的二叉樹中至少有一個度為 2的結點。（）TOC\o"1-5"\h\z16、二叉樹中結點之間的相互關系可用二元組來表示。 （）17、不存在這樣的二叉樹：它有 n個度為0的結點，n-l個度為1的結點，n-2個度為2的結點。（）18、在任何一棵完全二叉樹中，終端結點或者和分支結點一樣多，或者只比分支結點多一個。 （）19、完全二叉樹中的每個結點或者沒有孩子或者有 2個孩子。（）20、在所有高度相同的二叉樹中，滿二叉樹總是含有最多的結點數。 （）21、滿二叉樹中不存在度為1的結點。（）22、若用順序方法存儲滿二叉樹，則具有前驅、后繼關系的結點將占據相鄰的存儲單元。 （）23、n個結點的二叉鏈表中總是有n+1個空的指針域。（）24、n個結點的二叉鏈表中總是有「n/2」個含有空指針域的結點。 （）25、當樹中結點數多于1個時，不可能根據結點的前序序列和后序序列唯一地確定該樹的邏輯結構。 （）26、當二叉樹中結點數多于1個時，不能根據結點的前序和后序序列唯一地確定該二叉樹的邏輯結構。 （）27、只要知道完全二叉樹中結點的前序序列，就可以唯一地確定它的邏輯結構。 （）28、哈夫曼樹中不存在度為1的結點。（）29、在哈夫曼樹中，權值相同的樹葉結點都在同一層上。 （）30、在哈夫曼樹中，權值較大的樹葉結點一般離根結點較遠。 （）四、應用題：1、已知完全二叉樹的第七層有 10個葉子結點，則整個二叉樹的結點數最多是多少？2、將下列由三棵樹組成的森林轉換為二叉樹。PP