福師《數據結構概論》在線作業一一、單項選擇題（共25道試題，共50分。）1.以下排序算法中，（）算法可能會出現下面情況：在最終一趟開始之前，全部元素都不在其最終位置上。.堆排序.冒泡排序.快速排序.插入排序正確答案：2.以下數據結構中，（）是非線性數據結構.樹.字符串.隊.棧正確答案：3.線性表（1,2,…,n）以鏈接方式存放時，訪問第i位置元素時間復雜性為（）.O（i）.O（1）.O（n）.O（i-1）正確答案：4.設給定權值總數有n個，其哈夫曼樹結點總數為（）.不確定.2n.2n+1.2n-1正確答案：5.從未排序序列中依次取出一個元素與已排序序列中元素依次進行比較，然后將其放在已排序序列適宜位置，該排序方法稱為（）排序法。.插入.選擇.希爾.二路歸并正確答案：6.就平均性能而言，現在最好內排序方法是()排序法。.冒泡.希爾插入.交換.快速正確答案：7.對關鍵碼序列28，16，32，12，60，2，5，72快速排序，從小到大一次劃分結果為（）。.(2,5,12,16)26(60,32,72).(5,16,2,12)28(60,32,72).(2,16,12,5)28(60,32,72).(5,16,2,12)28(32,60,72)正確答案：8.適適用于折半查找表存放方式及元素排列要求為().鏈接方式存放，元素無序.鏈接方式存放，元素有序.次序方式存放，元素無序.次序方式存放，元素有序正確答案：9.線索二叉樹是一個（）構。.邏輯.邏輯和存放.物理.線性正確答案：10.對于次序存放線性表，訪問結點和增加、刪除結點時間復雜度為（）。.O(n)O(n).O(n)O(1).O(1)O(n).O(1)O(1)正確答案：11.若串S=’softwr’,其子串數目是（）.8.37.36.9正確答案：12.要連通具備n個頂點有向圖，最少需要（）條邊。.n-l.n.n+l.2n正確答案：13.已知串S=‘’,其Nxt數組值為（）.0123.1123.1231.1211正確答案：14.在下面程序段中，對x賦值語句頻度為（）FORi:=1TOnOFORj:=1TOnOx:=x+1;.O(2n).O(n).O(n2).O(log2n)正確答案：15.設森林F對應二叉樹為，它有m個結點，根為p,p右子樹結點個數為n,森林F中第一棵樹結點個數是（）.m-n.m-n-1.n+1.條件不足，無法確定正確答案：16.線索二叉樹是一個（）結構。.邏輯.邏輯和存放.物理.線性正確答案：17.串長度是指（）.串中所含不一樣字母個數.串中所含字符個數.串中所含不一樣字符個數.串中所含非空格字符個數正確答案：18.已知廣義表L=（（x,y,z），，（u，t，w）），從L表中取出原子項t運算是（）.h（til（til（L）））.til（h（h（til（L））））.h（til（h（til（L））））.h（til(h（til（til（L）））)）正確答案：19.一個遞歸算法必須包含（）.遞歸部分.終止條件和遞歸部分.迭代部分.終止條件和迭代部分正確答案：20.若串S=’softwr’,其子串數目是（）。.8.37.36.9正確答案：21.對稀疏矩陣進行壓縮存放目標是（）。.便于進行矩陣運算.便于輸入和輸出.節約存放空間.降低運算時間復雜度正確答案：22.以下排序算法中，占用輔助空間最多是：().歸并排序.快速排序.希爾排序.堆排序正確答案：23.由3個結點能夠結構出多少種不一樣二叉樹（）.2.3.4.5正確答案：24.輸入序列為，能夠變為時，經過棧操作為（）.push,pop,push,pop,push,pop.push,push,push,pop,pop,pop.push,push,pop,pop,push,pop.push,pop,push,push,pop,pop正確答案：25.若長度為n線性表采取次序存放結構，在其第i個位置插入一個新元素算法時間復雜度（）(1<=i<=n+1)。.O(0).O(1).O(n).O(n2)正確答案：福師《數據結構概論》在線作業一二、判斷題（共20道試題，共40分。）1.廣義表取表尾運算，其結果通常是個表，但有時也可是個單元素值（）.錯誤.正確正確答案：2.用樹前序遍歷和中序遍歷能夠導出樹后序遍歷（）.錯誤.正確正確答案：3.隊列和棧都是運算受限線性表，只允許在表兩端進行運算（）。.錯誤.正確正確答案：4.次序存放方式插入和刪除時效率太低，所以它不如鏈式存放方式好（）.錯誤.正確正確答案：5.任一查找樹(二叉分類樹)平均查找時間都小于用次序查找法查找一樣結點線性表平均查找時間..錯誤.正確正確答案：6.數據元素是數據最小單位。.錯誤.正確正確答案：7.數據結構抽象操作定義與詳細實現關于。.錯誤.正確正確答案：8.廣義表中元素或者是一個不可分割原子，或者是一個非空廣義表（）.錯誤.正確正確答案：9.線性表只能用次序存放結構實現（）.錯誤.正確正確答案：10.在次序存放結構中，有時也存放數據結構中元素之間關系（）.錯誤.正確正確答案：11.循環隊列通慣用指針來實現隊列頭尾相接。.錯誤.正確正確答案：12.二叉樹是度為2有序樹.錯誤.正確正確答案：13.在查找樹（二叉樹排序樹）中插入一個新結點，總是插入到葉結點下面（）.錯誤.正確正確答案：14.隊列邏輯上是一個下端和上端既能增加又能降低線性表。.錯誤.正確正確答案：15.鏈表中頭結點僅起到標識作用（）.錯誤.正確正確答案：16.棧和隊列都是限制存取點線性結構（）.錯誤.正確正確答案：17.鏈表中頭結點僅起到標識作用。.錯誤.正確正確答案：18.二叉樹以后序遍歷序列與前序遍歷序列反應一樣信息(他們反應信息不獨立）（）.錯誤.正確正確答案：19.對一棵二叉樹進行層次遍歷時，應借助于一個棧.錯誤.正確正確答案：20.廣義表取表尾運算，其結果通常是個表，但有時也可是個單元素值。.錯誤.正確正確答案：福師《數據結構概論》在線作業一三、多項選擇題（共5道試題，共10分。）1.以下數據結構中，哪些不是線性結構（）.廣義表.二叉樹.稀疏矩陣.串正確答案：2.以下說法正確是（）.圖遍歷是從給定源點出發每一個頂點僅被訪問一次.圖深度遍歷不適適用于有向圖.遍歷基本算法有兩種：深度遍歷和廣度遍歷.圖深度遍歷是一個遞歸過程正確答案：3.下面幾個符號串編碼集合中，是前綴編碼是（）.{0,10,110,1111}.{11,10,001,101,0001}.{00,010,0110,1000}.{,