【正文】 2．編寫順序查找算法。 （3） 。 for(i=1。 for(j=1。a[j].key){ a[j+1]=__ _②__ ________③______} a[j+1]=____④____。i++){ temp=a[i]。void disort (NODE a[ ], int n) { int I,j。7． (1) 設有查找表{8,17,5,9,21,10,7,19,6},依次取表中數(shù)據，構造一棵二叉排序樹.（2）說明如何通過序列的二叉排序樹得到相應序列的排序結果，對上述二叉排序給出中序遍歷的結果.四、程序填空題1．以下直接輸入排序算法對存放在a[0],a[1],2．已知序列（10，18，4，3，6，12，1，9，15，8），請寫出對此序列采用歸并排序法進行升序排序時各趟的結果。20．按某關鍵字對記錄序列排序， 若在排序前和排序后仍保持它們的前后關系，則排序算法是穩(wěn)定的，否則是不穩(wěn)定的。16．在對一組記錄（50，40，95，20，15，70，60，45，80）進行直接插入排序時，當把第7個記錄60插入到有序表時，為尋找插入位置需要比較 次。12．哈希表是用來存放查找表中記錄序列的表，每一個記錄的存儲位置是以該記錄得到關鍵字為 ，由相應哈希函數(shù)計算所得到的 。10．分塊查找又稱為 ，它是一種介于 和折半查找之間的查找方法。7． 查找是一種最簡單的查找方法。3．如果在查找表中進行查詢的過程中，同時插入查找表中不存在的數(shù)據元素，或者從查找表中刪除已存在的某個數(shù)據元素，則稱此類查找表為 。 A．16，25，35，48，23，40，79，82，36，72 B．16，25，35，48，79，82，23，36，40，72C．16，25，48，35，79，82，23，36，40，72 D．16，25，35，48，79，23，36，40，82，72 37．已知10個數(shù)據元素為（54，28，16，34，73，62，95，60，26，43），對該數(shù)列從小到到大排序，經過一趟冒泡排序后的序列為（ ）。A. 3 B. 4 C. 5 D. 6，（　　）是一種穩(wěn)定性排序方法。A. n/2 B. n C. (n+1)/2 D. n+1 （49，72，68，13，38，50，97，27）進行排序，前三趟排序結果時的結果依次為第一趟：49，72，68，13，38，50，97，27；第二趟：49，68，72，13，38，50，97，27；第三趟：13，49，68，72，38，50，97，27。A. 插入排序 B. 交換排序 C. 選擇排序 D. 歸并排序 ，關鍵字比較的次數(shù)與記錄的初始排列秩序無關的是（ ）。 A. O(log2n) B. O(n) C. O(n log2n) D. O(n2) ，冒泡排序的時間復雜度為（ ）。 A. 插入排序 B. 交換排序 C. 選擇排序 D. 歸并排序 （ ）。 B. 3 C. 4 （ ）。A．3 B．4 C．5 D．610．順序查找法與二分查找法對存儲結構的要求是（ ）。A．n B．n/2 C．(n+1)/2 D．(n1)/2 6．采用折半查找方法查找長度為n的線性表時，每個元素的平均查找長度為（ ）。A．散列存儲 B．索引存儲 C．散列存儲或索引存儲 D．順序存儲或鏈接存儲2．對線性表進行二分查找時，要求線性表必須（ ）。3．已知有n個頂點的有向圖鄰接表，設計算法分別實現(xiàn)下列功能：（1）求出圖G中每個頂點的出度、入度。 (2) } }五、算法設計題1．寫一個將一棵二叉樹復制給另一棵二叉樹的算法。amp。 } }2. 下面函數(shù)的功能是按照圖的深度優(yōu)先搜索遍歷的方法，輸出得到該圖的生成樹中的各條邊，請在劃有橫線的地方填寫合適內容。 if(c1=1) ___(1)___________。8．回答下列問題：⑴對于存儲結構采用鄰接矩陣的無向圖，如何判斷下列有關問題？①圖中有多少條邊？②任意兩頂點間是否有邊相連？③任意一個頂點的度是多少？⑵對于存儲結構采用鄰接表的有向圖，如何判斷下列有關問題？①圖中有多少條邊？②圖中是否存在從Vi到Vj的邊？③如何求頂點Vi的入度和出度？四、程序填空題1. 下面函數(shù)的功能是返回二叉樹BT中值為X的結點所在的層號，請在劃有橫線的地方填寫合適內容。（1）先序和中序相同（2）中序和后序相同（3）先序和后序相同5．假設通信用的報文由9個字母A、B、C、D、E、F、G、H和I組成，它們出現(xiàn)的頻率分別是：17和30。36．為了實現(xiàn)圖的深度優(yōu)先搜索遍歷，其非遞歸的算法中需要使用的一個輔助數(shù)據結構為 。即不應該帶有回路，否則回路上的所有活動都 。30．具有n個頂點的有向圖的鄰接矩陣，其元素個數(shù)為 。26．鄰接表是圖中的每個頂點建立一個鄰接關系的 。22．若以4，5，6，7，8作為葉子結點的權值構造哈夫曼樹，則其帶權路徑長度是 。18．后序遍歷二叉樹的的操作定義為；若二叉樹為空，則為空操作，否則進行如下操作，后序遍歷二叉樹的 ；后序遍歷二叉樹的 ，訪問而叉樹的 。14．在一棵二叉樹中，如果樹中的每一層都是滿的，則稱此樹為 ；但如果出最后一層外，其余層都是滿的，并且最后一層是滿的，或者是在缺少若干連續(xù)個結點，則稱此二叉樹為 。11．m(m179。7．具有 的結點互稱為兄弟結點，簡稱為兄弟。3．度大于0的結點稱作 或 。 A．對稱矩陣 B． 零矩陣 C．上三角矩陣 D．對角矩陣35．圖的深度優(yōu)先遍歷算法類似于二叉樹的（ ）遍歷。 A．入邊 B．出邊 C．入邊和出邊 D．不是入邊也不是出邊31．鄰接表是圖的一種（ ）。 A．n B．n2 C．n1 D．（n1）227．對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表表示，則表頭向量的大小為（ ）。 A．鄰接矩陣表示法 B．鄰接表表示法 C．逆鄰接表表示法 D．鄰接表和逆鄰接表 23．在圖的存儲結構表示中，表示形式唯一的是（ ）。 A．n B．n1 C．n+1 D．2n19．設一棵有n個葉結點的二叉樹，除葉結點外每個結點度數(shù)都為2，則該樹共有（ ）個結點。 A. n B. n1 C. n+1 D. 2*n1 15. 利用12這四個值作為葉子結點的權，生成一棵哈夫曼樹，該樹中所有葉子的最長帶權路徑長度為( )。A．二叉樹中度為0的結點的個數(shù)等于度為2的結點的個數(shù)加1B．二叉樹中結點個數(shù)必大于0C．完全二叉樹中，任何一個結點的度，或者為0或者為2 D．二叉樹的度是211．在一棵度為3的樹中，度為3的結點個數(shù)為2，度為2的結點個數(shù)為1，則度為0的結點個數(shù)為（ ）。A．a在b上方 B．a在b下方 C．a在b左方 D．a在b右方7．權值為{1，2，6，8}的四個結點構成的哈夫曼樹的帶權路徑長度是（ ）。 A．2k B．2k1 C．2k1 D．2k1 3．二叉樹的深度為k,則二叉樹最多有（ ）個結點。（6）顯示隊列中元素：dispqueue(Q)。（2）入隊列enqueue(Q,x):將元素x插入到隊列Q中。} while (qfrontnext != NULL) {p=qfrontnext。 }} /*del_cqueue*/ ，以使下面的鏈式隊列取出元素的算法完整。return(FALSE)。 int front,rear。define FALSE 0。（2）如果輸入序列由A，B，C，D組成，試給出全部可能的輸出序列和不可能的輸出序列。（數(shù)組元素的下標從1開始）28．對稀疏矩陣進行壓縮存儲，矩陣中每個非零元素對應的三元組包括該元素的_______、_______和_______三項信息。25．廣義表A（（a,b,c）,(d,e,f)）的表尾為 。21．串的兩種最基本的存儲方式是 和 。和________。12．在將中綴表達式轉換成后綴表達式和計算后綴表達式的算法中，都需要使用棧，對于前者，進入棧中的元素為表達式中的 ，而對于后者，進入棧的元素為 ，中綴表達式(a+b)/c(fd/c)所對應的后綴表達式是 。第二步是把 ；第三步 。5．循環(huán)隊列隊頭指針在隊尾指針 位置，隊列是“滿”狀態(tài)6．在隊列的順序存儲結構中，當插入一個新的隊列元素時，尾指針 ，當刪除一個元素隊列時，頭指針 。A．不可能是子表 B．只能是子表 C．只能是原子 D．可以是子表或原子二、填空題1．棧是限定在表的一端進行插入和刪除操作的線性表，又稱為 。 A．不可能是原子 B．只能是子表 C．只能是原子 D．可以是子表或原子 32．常對數(shù)組進行的兩種基本操作是（ ）。則應該采用（ ）存儲比較合適（ ）。A．串是字符的有限序列 B．空串是由空格構成的串 C．模式匹配是串的一種重要運算 D．串即可以采用順序存儲，也可以采用鏈式存儲 25．串與普通的線性表相比較，它的特殊性體現(xiàn)在（ ）。A．求子串 B．連接 C．匹配 D．求串長 21．串是（ ）。 D．snext=f。 B．rnext=s。 D．f=rnext。17．在一個鏈隊中，假設f和r分別為隊頭和隊尾指針，則刪除一個結點的運算為（ ）。 C．top=topnext。A．遞歸部分 B．終止條件和遞歸部分 C．迭代部分 D．終止條件和迭代部分16．從一個棧頂指針為top的鏈棧中刪除一個結點時，用變量x保存被刪結點的值，則執(zhí)行（ ）。 A．stop==0 B．stop!=0 C．stop==n1 D．stop!=n1 12．一個隊列的入隊順序是a,b,c,d，則離隊的順序是（ ）。 A．abcd*+ B．abc+*d C．abc*++d D．+*abcd8．判斷一個順序隊列sq（最多元素為m0）為空的條件是（ ）。 D．x