數(shù)據(jù)結(jié)構(gòu)導(dǎo)論自考 數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題

1、數(shù)據(jù)結(jié)構(gòu)導(dǎo)論自考 數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題 全國2004年10月高等教育自學(xué)考試 1.要將現(xiàn)實生活中的數(shù)據(jù)轉(zhuǎn)化為計算機(jī)所能表示的形式，其轉(zhuǎn)化過程依次為（ ） A.邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、機(jī)外表示 B.存儲結(jié)構(gòu)、邏輯結(jié)構(gòu)、機(jī)外表示 C.機(jī)外表示、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu) D.機(jī)外表示、存儲結(jié)構(gòu)、邏輯結(jié)構(gòu) 2.若評價算法的時間復(fù)雜性，比較對數(shù)階量級與線性階量級，通常（ ） A.對數(shù)階量級復(fù)雜性大于線性階量級 B.對數(shù)階量級復(fù)雜性小于線性階量級 C.對數(shù)階量級復(fù)雜性等于線性階量級 D.兩者之間無法比較 3.下列關(guān)于線性表的基本操作中，屬于加工型的操作是（ ） A.初始化、求表長度、插入操作 B.初始化、插入、刪除操作

2、 C.求表長度、讀元素、定位操作 D.定位、插入、刪除操作 4.在一個單鏈表中，若p所指結(jié)點不是最后結(jié)點，s指向已生成的新結(jié)點，則在p之后插入s所指結(jié)點的正確操作是（ ） A.s>next=p>next; p>next=s; B.p>next=s>next; s>next=p; C.s>next=p; p>next=s; D.s>next=p>next; p=s; 5.若有三個字符的字符串序列執(zhí)行入棧操作，則其所有可能的輸出排列共有（ ） A.3種 B.4種 C.5種 D.6種 6.C語言對數(shù)組元素的存放方式通常采用（ ） A.按行為

3、主的存儲結(jié)構(gòu) B.按列為主的存儲結(jié)構(gòu) C.按行或列為主的存儲結(jié)構(gòu) D.具體存儲結(jié)構(gòu)無法確定 7.根據(jù)定義，樹的葉子結(jié)點其度數(shù)（ ） A.必大于 0 B.必等于0 C.必等于1 D.必等于2 8.二叉樹若采用二叉鏈表結(jié)構(gòu)表示，則對于n個結(jié)點的二叉樹一定有（ ） A.2n個指針域其中n個指針為NULL B.2n個指針域其中n+1個指針為NULL C.2n-1個指針域其中n個指針為NULL D.2n-1個指針域其中n+1個指針為NULL 9.在一個無向圖中，所有頂點的度數(shù)之和等于邊數(shù)的（ ） A.1倍 B.2倍 C.3倍 D.4倍 10.若采用鄰接表存儲結(jié)構(gòu)，則圖的廣度優(yōu)先搜索類似于二叉樹的（ ）

4、A.先根遍歷 B.中根遍歷 C.后根遍歷 D.層次遍歷 11.采用順序查找法，若在表頭設(shè)置崗哨，則正確的查找方式通常為（ ） A.從第0個元素開始往后查找該數(shù)據(jù)元素 B.從第1個元素開始往后查找該數(shù)據(jù)元素 C.從第n個元素開始往前查找該數(shù)據(jù)元素 D.從第n+1個元素開始往前查找該數(shù)據(jù)元素 12.下列查找中，效率最高的查找方法是（ ） 第 1 頁 A.順序查找 B.折半查找 C.索引順序查找 D.分塊查找 13.索引文件通常由索引表和主文件兩部分構(gòu)成，其中（ ） A.索引表和主文件均必須是有序文件 B.索引表和主文件均可以是無序文件 C.索引表必須是有序文件 D.主文件必須是有序文件 14.直接

5、插入排序算法，其時間復(fù)雜性為（ ） A.O(1) B.O(n) C.O(nlog2n) D.O(n2) 15.下列排序方法中，屬于穩(wěn)定的排序方法是（ ） A.直接插入排序法 B.快速排序法 C.冒泡排序法 D.堆排序法 16.從數(shù)據(jù)結(jié)構(gòu)的觀點，數(shù)據(jù)通?？煞譃槿齻€層次，即：數(shù)據(jù)、數(shù)據(jù)元素和_。 17.用程序設(shè)計語言、偽程序設(shè)計語言并混合自然語言描述的算法稱為_算法。 18.對順序表執(zhí)行插入操作，其插入算法的平均時間復(fù)雜性為_。 19.在具有n個單元、且采用順序存儲的循環(huán)隊列中，隊滿時共有_個元素。 20.若front和rear分別表示循環(huán)隊列Q的頭指針和尾指針，m0表示該隊列的最大容量，則循環(huán)隊

6、列為空的條件是_。 21.二維數(shù)組A1020采用按行為主序的存儲方式，每個元素占4個存儲單元，若A00的存儲地址為300，則A1010的地址為_。 22.樹的遍歷主要有先根遍歷、后根遍歷和_三種。 23.深度為k的完全二叉樹至少有_個結(jié)點。 24.若圖的鄰接矩陣是一個對稱矩陣，則該圖一定是一個_。 25.對于具有n個元素的數(shù)據(jù)序列，采用二叉排序樹查找，其平均查找長度為_。 26.要完全避免散列所產(chǎn)生的“堆積”現(xiàn)象，通常采用_法。 27.ISAM其中文含義為_方法。 28.在最好的情況下，對于具有n個元素的有序序列，若采用冒泡排序，所需的比較次數(shù)為_次。 29.已知某二叉樹如下圖所示，試給出其二

7、叉鏈表及順序存儲結(jié)構(gòu)表示。 30.若某無向圖G的鄰接表如圖所示，試給出以頂點V1為出發(fā)點，按廣度優(yōu)先搜索所產(chǎn)生的一棵生成樹。 第 2 頁 31.已知某二叉排序樹10個結(jié)點的值依次為110，其結(jié)構(gòu)如圖所示，試標(biāo)出該二叉樹各結(jié)點所對應(yīng)的具體值。 32.已知一組鍵值序列（28，47，35，42，53，60，34，22），試給出采用直接插入排序法對該組序列作升序排序的每一趟結(jié)果。 33.已知一組鍵值序列（3，6，8，9，2，7，4，3），試采用快速排序法對該組序列作升序排序，并給出每一趟的排序結(jié)果。 34.設(shè)某單鏈表中，存在多個結(jié)點其數(shù)據(jù)值均為D，試編寫一算法統(tǒng)計該類結(jié)點的個數(shù)。 35.若二叉樹存儲結(jié)

8、構(gòu)采用二叉鏈表表示，試編寫一算法，計算一棵二叉樹的所有結(jié)點數(shù)。 全國2005年10月高等教育自學(xué)考試 1.若要描述數(shù)據(jù)處理的變化過程，其正確的次序應(yīng)為( ) A.處理要求、基本運算和運算、算法 B.處理要求、算法、基本運算和運算 C.基本運算和運算、處理要求、算法 D.算法、處理要求、基本運算和運算 2.從運算類型角度考慮，屬于引用型的運算是( ) A.插入、刪除 B.刪除、修改 C.查找、讀取 D.查找、刪除 3.若在長度為n的順序表中插入一個結(jié)點，則其結(jié)點的移動次數(shù)( ) A.最少為0，最多為n B.最少為1，最多為n C.最少為0，最多為n+1 D.最少為1，最多為n+1 第 3 頁 4

9、.在一個單鏈表中，若p所指結(jié)點是q所指結(jié)點的前驅(qū)結(jié)點，則在結(jié)點p、q之間插入結(jié)點s的正確操作是( ) A.s->next=q；p->next=s->next B.p->next=q；p->next=s C.s->next=q->next；p->next=s D.s->next=q->next；p->next=s->next 5.若有一串?dāng)?shù)字5、6、7、8入棧，則其不可能的輸出序列為( ) A.5、6、7、8 B.8、7、6、5 C.8、7、5、6 D.5、6、8、7 6.FORTRAN語言對數(shù)組元素的存放方式通常采用( )

10、 A.按行為主的存儲結(jié)構(gòu) B.按列為主的存儲結(jié)構(gòu) C.按行或列為主的存儲結(jié)構(gòu) D.按行和列為主的存儲結(jié)構(gòu) 7.樹是n個結(jié)點的有窮集合，( ) A.樹的結(jié)點個數(shù)可以為0，此時稱該樹為空樹 B.樹至少含有一個根結(jié)點，不能為空 C.樹至少含有一個根結(jié)點和一個葉子結(jié)點 D.樹至少含有一個根結(jié)點和兩個葉子結(jié)點 8.深度為k的二叉樹至多有( ) A.2k個葉子 B.2k-1個葉子 C.2k-1個葉子 D.2k-1-1個葉子 9.具有10個頂點的有向完全圖應(yīng)具有( ) A.20條弧 B.50條弧 C.90條弧 D.100條弧 10.從V1出發(fā)，對題10圖按廣度優(yōu)先搜索遍歷，則可能得到的一種頂點序列為( ) A.V1V2V3V5V4V6 B.V1V2V3V5V6V4 C.V1V5V2V3V6V4 D.V1V3V6V4V5V2 11.適用于靜態(tài)的查找方法為( ) A.二分查找、二叉排序樹查找 B.二分查找、索引順序表查找 C.二叉排序樹查找、索引順序表查找 D.二叉排序樹查找、散列法查找 12.采用二分查找法，若當(dāng)前取得的中間位置MID的元素值小于被查找值，則表明待查元素可能在表的后