來源：我是碼農，轉載請保留出處和鏈接！
本文鏈接：數據結構習題解析二
一、選擇題
1、數組的數據元素類型DataType可根據實際需要而定義。以下說法完全正確的是（ ）
A．數組的讀運算可以讀取一個數據元素整體,寫運算只能修改一個數據元素的一部分
B．數組的讀、寫運算可以讀取或修改一個數據元素的一部分或一個整體
C．數組的讀、寫運算只能讀取或修改一個數據元素的一部分
D．數組的讀、寫運算只能讀取或修改一個數據元素整體

數據結構練習題解析解析：本題考點是數組的數據元素類型的定義。 數組的讀、寫運算可以讀取或修改一個數據元素的一部分或一個整體，當數據元素本身不是原子項時，我們可以修改一個數據元素的一部分。因此，本題參考答案是B。
2、在以下棧的基本運算中，不是加工型運算的是（ ）
A．lnitStack(S)
B．Push(S,X)
C．Pop(S)
D．Empty(S)
數據結構練習題解析解析：本題考點是加工型運算的判別。 清空棧不是加工型運算。因此，本題參考答案是D。
3、以下不穩定的排序方法是（ ）
A．直接插入排序
B．冒泡排序
C．直接選擇排序
D．二路歸并排序
數據結構練習題解析解析：本題考點是不穩定的排序方法的判別。 假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，則稱這種排序算法是穩定的；否則稱為不穩定的。直接選擇排序是不穩定的排序方法。因此，本題參考答案是C。
4、在一個長度為n的順序線性表中順序查找值為x的元素時，查找成功時的平均查找長度（即x與元素的平均比較次數，假定查找每個元素的概率都相等）為 ( )。
A．n
B．n/2
C．(n+1)/2
D．(n-1)/2
數據結構練習題解析解析：本題考點是平均查找長度的計算方法。 為確定記錄在查找表中的位置，需和給定值進行比較的關鍵字個數的期望值稱為查找算法在查找成功時的平均查找長度。按照此方法計算可得，本題參考答案是C。
5、以下說法錯誤的是（ ）
A．數據的物理結構是指數據在計算機內實際的存儲形式
B．算法和程序沒有區別，所以在數據結構中二者是通用的
C．對鏈表進行插人和刪除操作時，不必移動結點
D．雙鏈表中至多只有一個結點的后繼指針為空
數據結構練習題解析解析：本題考點是數據結構中相關基本概念。 算法是解決問題的步驟；程序是算法的代碼實現。算法要依靠程序來完成功能；程序需要算法作為靈魂。因此，本題參考答案是B。
6、順序隊列的出隊操作為（ ）
A．sq.front=(sq.front+1)% maxsize
B．sq.front=sq.front+1
C．sq.rear=(sq.rear+1)% maxsize
D．sq.rear=sq.rear+1
數據結構練習題解析解析：本題考點是隊列的基本操作。 隊列是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進行刪除操作，而在表的后端（rear）進行插入操作，和棧一樣，隊列是一種操作受限制的線性表。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。順序隊列的出隊操作為sq.front=sq.front+1。因此，本題參考答案是B。
7、對于線性表（7，34，55，25，64，46，20，10）進行散列存儲時，若選用 H（K）=K %9作為散列函數，則散列地址為1的元素有（ ）個。
A．1
B．2
C．3
D．4
數據結構練習題解析解析：本題考點是線性表散列存儲的特點。 散列函數即哈希函數，哈希表中元素是由哈希函數確定的。將數據元素的關鍵字K作為自變量，通過一定的函數關系（稱為哈希函數），計算出的值，即為該元素的存儲地址。表示為：Addr = H（key）。線性表中的值就是函數中的自變量，代入函數可知，55,64,46和10散列地址都為1。因此，本題參考答案是D。
8、在以下隊列的基本運算中，不是加工型運算的是（ ）
A．InitQueue(Q)
B．EnQueue(Q,X)
C．OutQueu(Q,X)
D．GetHead(Q,x)
數據結構練習題解析解析：本題考點是隊列的基本運算。 獲取隊頭元素不是加工型運算。因此，本題參考答案是D。
9、設連通圖G中的邊集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點a出發可以得到一種深度優先遍歷的頂點序列為（ ）。
A．abedfc
B．acfebd
C．aebdfc
D．aedfcb
數據結構練習題解析解析：本題考點是圖的深度優先遍歷。 假設給定圖G的初態是所有頂點均未曾訪問過。在G中任選一頂點v為初始出發點(源點)，則深度優先遍歷可定義如下：首先訪問出發點v，并將其標記為已訪問過；然后依次從v出發搜索v的每個鄰接點w。若w未曾訪問過，則以w為新的出發點繼續進行深度優先遍歷，直至圖中所有和源點v有路徑相通的頂點(亦稱為從源點可達的頂點)均已被訪問為止。若此時圖中仍有未訪問的頂點，則另選一個尚未訪問的頂點作為新的源點重復上述過程，直至圖中所有頂點均已被訪問為止。因此，本題參考答案是C。
10、根據操作的效果，可將運算分成加工型運算、引用型運算兩種基本類型。對于表格處理中的五種功能以下解釋錯誤的是（ ）
A．查找引用型運算，功能是找出滿足某種條件的結點在s(線形結構)中的位置
B．讀取引用型運算 功能是讀出s(線形結構)中某指定位置結點的內容
C．插入引用型運算，功能是在s(線形結構)的某指定位置上增加一個新結點
D．刪除加工型運算，功能是撤消s(線形結構)某指定位置上的結點
數據結構練習題解析解析：本題考點是加工型運算、引用型運算的功能。 插入是加工型運算。因此，本題參考答案是C。
二、判斷題
1、快速排序是排序算法中平均性能最好的一種排序。( )
A正確
B錯誤
數據結構練習題解析解析：本題考點是快速排序的性能。 快速排序的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。快速排序是排序算法中平均性能最好的一種排序。因此，本題參考答案是A。
2、在一個順序存儲的循環隊列中, 隊頭指針指向隊頭元素的后一個位置。（ ）
A正確
B錯誤
數據結構練習題解析解析：本題考點是循環隊列的特性。 循環隊列中，由于入隊時尾指針向前追趕頭指針；出隊時頭指針向前追趕尾指針，造成隊空和隊滿時頭尾指針均相等。在一個順序存儲的循環隊列中, 隊頭指針指向隊頭元素的前一個位置。因此，本題參考答案是B。
3、散列法存儲的基本思想是由關鍵碼的值決定數據的存儲地址。( )
A正確
B錯誤
數據結構練習題解析解析：本題考點是散列法存儲的基本思想。 散列存儲，又稱hash存儲，是一種力圖將數據元素的存儲位置與關鍵碼之間建立確定對應關系的查找技術。散列法存儲的基本思想是：由節點的關鍵碼值決定節點的存儲地址。散列技術除了可以用于查找外，還可以用于存儲。因此，本題參考答案是A。
4、在使用后綴表示實現計算器類時用到一個棧的實例, 它的作用是暫存運算器對象。（ ）
A正確
B錯誤
數據結構練習題解析解析：本題考點是后綴表示的應用。 棧（stack）又名堆棧，它是一種運算受限的線性表。其限制是僅允許在表的一端進行插入和刪除運算。這一端被稱為棧頂，相對地，把另一端稱為棧底。向一個棧插入新元素又稱作進棧、入棧或壓棧，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個棧刪除元素又稱作出棧或退棧，它是把棧頂元素刪除掉，使其相鄰的元素成為新的棧頂元素。在使用后綴表示實現計算器類時用到一個棧的實例, 它的作用是暫存運算器對象。因此，本題參考答案是A。
5、在用循環單鏈表表示的鏈式隊列中，可以不設隊頭指針，僅在鏈尾設置隊尾指針。（ ）
A正確
B錯誤
數據結構練習題解析解析：本題考點是循環單鏈表的應用。 在用循環單鏈表表示的鏈式隊列中，可以不設隊頭指針，僅在鏈尾設置隊尾指針，由于是循環隊列，通過隊尾移動指針即可找到隊頭。因此，本題參考答案是A。
6、冒泡排序在初始關鍵字序列為逆序的情況下執行的交換次數最多。( )
A正確
B錯誤
數據結構練習題解析解析：本題考點是冒泡排序的特點。 冒泡排序，是一種計算機科學領域的較簡單的排序算法。它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。冒泡排序在初始關鍵字序列為有序的情況下執行的交換次數最少。冒泡排序在初始關鍵字序列為逆序的情況下執行的交換次數最多。因此，本題參考答案是A。
7、在用單鏈表表示的鏈式隊列Q中，隊頭指針為Q->front，隊尾指針為Q->rear，則隊空條件為Q->front == Q->rear。（ ）
A正確
B錯誤
數據結構練習題解析解析：本題考點是單鏈表表示鏈式隊列的特點。 隊列是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進行刪除操作，而在表的后端（rear）進行插入操作，和棧一樣，隊列是一種操作受限制的線性表。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。在用單鏈表表示的鏈式隊列Q中，隊頭指針為Q->front，隊尾指針為Q->rear，則隊空條件為Q->front == Q->rear+1。因此，本題參考答案是B。
8、遞歸定義的數據結構通常用遞歸算法來實現對它的操作。（ ）
A正確
B錯誤
數據結構練習題解析解析：本題考點是遞歸定義數據結構的特點。 程序調用自身的編程技巧稱為遞歸（ recursion）。遞歸做為一種算法在程序設計語言中廣泛應用。 一個過程或函數在其定義或說明中有直接或間接調用自身的一種方法，它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復計算，大大地減少了程序的代碼量。遞歸的能力在于用有限的語句來定義對象的無限集合。一般來說，遞歸需要有邊界條件、遞歸前進段和遞歸返回段。當邊界條件不滿足時，遞歸前進；當邊界條件滿足時，遞歸返回。遞歸定義的數據結構通常用遞歸算法來實現對它的操作。因此，本題參考答案是A。
9、二叉樹中有雙子女的父結點，在中序遍歷中后繼一定是其中一個子女結點( )
A正確
B錯誤
數據結構練習題解析解析：本題考點是二叉樹的基本特性。 二叉樹是每個節點最多有兩個子樹的樹結構。通常子樹被稱作"左子樹"和"右子樹"。二叉樹中有雙子女的父結點，在中序遍歷中后繼不一定是其中一個子女結點。因此，本題參考答案是B。
10、遞歸調用算法與相同功能的非遞歸算法相比，主要問題在于重復計算太多，而且調用本身需要分配額外的空間和傳遞數據和控制，所以時間與空間開銷通常都比較大。（ ）
A正確
B錯誤
數據結構練習題解析解析：本題考點是遞歸調用算法的缺點。 遞歸算法解題相對常用的算法如普通循環等，運行效率較低。因此，應該盡量避免使用遞歸，除非沒有更好的算法或者某種特定情況，遞歸更為適合的時候。在遞歸調用的過程當中系統為每一層的返回點、局部量等開辟了棧來存儲。遞歸次數過多容易造成棧溢出等。因此，本題參考答案是A。
三、分析題
1、給定表（45,36,56,6,64,78,8,96），按數據元素在表中的次序構造一棵二叉排序樹。
數據結構練習題解析解析：本題考點是二叉排序樹的構造方法。
二叉排序樹或者是一棵空樹，或者是具有下列性質的二叉樹：
（1）若左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；
（2）若右子樹不空，則右子樹上所有結點的值均大于或等于它的根結點的值；
（3）左、右子樹也分別為二叉排序樹；
（4）沒有鍵值相等的節點。
根據二叉排序樹的定義即可根據給定表構造出出二叉排序樹。 因此，本題答題要點如下：
二叉排序樹為：

2、判斷序列（16，19，10，15，4，23，36，20）是否為（小頂）堆？為什么？如果不是，請按照建立堆的思想把它調整為堆，并用圖表示建堆的過程。
數據結構練習題解析解析：本題考點是堆的定義和建立方法。
n個關鍵字序列Kl，K2，…，Kn稱為堆，當且僅當該序列滿足如下性質(簡稱為堆性質)： (1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ n/2 ) 若將此序列所存儲的向量R[1…n]看做是一棵完全二叉樹的存儲結構，則堆實質上是滿足如下性質的完全二叉樹：樹中任一非葉結點的關鍵字均不大于(或不小于)其左右孩子(若存在)結點的關鍵字。根結點(亦稱為堆頂)的關鍵字是堆里所有結點關鍵字中最小者的堆稱為小根堆。根結點(亦稱為堆頂)的關鍵字是堆里所有結點關鍵字中最大者，稱為大根堆。
因此，本題答題要點如下：
因為不滿足（ai<a2i 和ai<a2i+1）如a1=16,a3=10，所以不是小頂堆。 可以調整為堆：（4，15，10，16，19，23，36，20）

3、簡述順序隊列、循環隊列的類型定義。
數據結構練習題解析解析：本題考點是順序隊列、循環隊列的定義。
順序隊列的類型定義如下：
該類型變量有三個域：data,front,rear。其中data存儲隊中元素的一維數組。隊頭指針front和隊尾指針rear定義為整型變量，實際取值范圍為0~maxsize－1。 循環隊列的類型定義如下：

4、給定有序表D={006,087,155,188,220,465,505,508,511,586,656,670,700,766,897,908}，用二分查找法在D中查找586，試用圖示法表示出查找過程。
數據結構練習題解析解析：本題考點是二分查找算法的定義及過程。
二分查找又稱折半查找，優點是比較次數少，查找速度快，平均性能好；其缺點是要求待查表為有序表，且插入刪除困難。因此，折半查找方法適用于不經常變動而查找頻繁的有序列表。首先，假設表中元素是按升序排列，將表中間位置記錄的關鍵字與查找關鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、后兩個子表，如果中間位置記錄的關鍵字大于查找關鍵字，則進一步查找前一子表，否則進一步查找后一子表。重復以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。
因此，本題答題要點如下：

總結

以上是生活随笔為你收集整理的数据结构习题及解析二的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。