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

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

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

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

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

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

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

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

9、.在一個單鏈表中，若p所指結點是q所指結點的前驅結點，則在結點p、q之間插入結點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.若有一串數字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語言對數組元素的存放方式通常采用( )

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