【正文】 存儲表示，在進行拓撲排序時，總的計算時間為（ ）。（ ） A． O(log2n) B． O(n) C． O(1) D． O(nlog2n) 標準答案： A 2在一個單鏈表 HL 中，若要在指針 q所指的結點的后面插入一個由指針 p所指的結點，則執(zhí)行（ ）。（ ） A． 8 B． 7 C． 6 D． 5 標準答案： B 2在內部排序中，排序時不穩(wěn)定的有（ ）。（ ） A．選擇 B．冒泡 第 4 頁 共 24 頁 C．歸并 D．堆 標準答案： C 1廣義表 (a,b,c,d)的表尾是（ ）。（ ） A． 24 B． 48 C． 53 D． 72 標準答案： C 1某二叉樹的先序序列和后序序列正好相反，則該二叉樹一定是（ ）的二叉樹。（ ） A．一定相鄰 B．不必相鄰 C．按某種規(guī)律排列 D．無要求 標準答案： A 1數(shù)據(jù)結構是研究數(shù)據(jù)的（ ）以及它們之間的相互關系。（ ） A．串中不同字符的個數(shù) B．串中不同字母的個數(shù) C．串中所含字符的個數(shù)且字符個數(shù)大于 0 D．串中所含字符的個數(shù) 第 3 頁 共 24 頁 標準答案： D 1已知某二叉樹的后序遍歷序列是 dabec，中序遍歷序列是 debac，它的前序遍歷序列是（ ）。編號為 49 的結點 X 的雙親編號為（ ）。（ ） A．有序數(shù)據(jù)元素 B．無序數(shù)據(jù)元素 C．元素之間具有分支層次關系的數(shù)據(jù) D．元素之間無聯(lián)系的數(shù)據(jù) 標準答案： C 設有兩個串 p 和 q，求 p 在 q 中首次出現(xiàn)的位置的運算稱作（ ）。（ ） A． 3 B． 4 C． 5 D． 6 標準答案： C 設有 1000 個元素，用二分法查找時，最大比較次數(shù)是（ ）。下列選項中，（ ）就是不穩(wěn)定的排序方法。（ ） A． HL=p； pnext=HL； B． pnext=HL； HL=p； C． pnext=HL； p=HL； D． pnext=HLnext； HLnext=p； 標準答案： B 一個具有 n 個頂點的無向完全圖的邊數(shù)為（ ）。（ ） A． a B． b C． (a) D． ((a)) 標準答案： C 數(shù)組 A中，每個元素 A的長度為 3個字節(jié)，行下標 i從 1 到 8，列下標 j 從 1 到 10，從首地址 SA開始連續(xù)存放在存儲器內，存放該數(shù)組至少需要的單元數(shù)是（ C ）。第 1 頁 共 24 頁 一、單項選擇題（本大題共 71 小題，每小題 2 分，共 142 分） 一個對象序列的排序碼為 {46， 79， 56， 38， 40， 84}，采用快速排序以位于最左位置的對象為基準而得到的第一次劃分結果為（ C ）。（ ） A． {38， 46， 79， 56， 40， 84} B． {38， 79， 56， 46， 40， 84} C． {40， 38， 46， 56， 79， 84} D． {38， 46， 56， 79， 40， 84} 標準答案： C 廣義表（（ a） ,a）的表頭是（ C ）。（ ） A． 80 B． 100 C． 240 D． 270 標準答案： C 在一個單鏈表 HL中，若要向表頭插入一個由指針 p指向的結點，則執(zhí)行（ ）。（ ） A． (n+1)/2 B． n(n1)/2 C． n(n1) D． n(n+1) 標準答案： B 如果待排序序列中兩個數(shù)據(jù)元素具有相同的值，在排序后它們的位置發(fā)生顛倒，則稱該排序是不穩(wěn)定的。（ ） A．起泡排序 B．歸并排序 C．直接插入法排序 第 2 頁 共 24 頁 D．簡單選擇排序 標準答案： D 按照二叉樹的定義，具有 3 個結點的二叉樹有（ ）種。（ ） A． 1 B． 7 C． 10 D． 25 標準答案： C 樹適合用來表示（ ）。（ ） A．連接 B．模式匹配 C．求子串 D．求串長 標準答案： B 1將含 100 個結點的完全二叉樹從根這一層開始，每層上從左到右依次對結點編號，根結點的編號為 1。（ ） A． 23 B． 24 C． 25 D．無法 確定 標準答案： A 1串的長度是（ ）。（ ） A． acbed B． decab C． deabc D． cedba 標準答案： D 1順序表中邏輯上相鄰的節(jié)點其物理位置也（ ）。（ ） A．理想結構，物理結構 B．理想結構，抽象結構 C．物理結構，邏輯結構 D．抽象結構，邏輯結構 標準答案： C 1由權值分別為 3,8,6,2,5 的葉子結點生成一棵哈夫曼樹，它的帶權路徑長度為（ ）。（ ） A．空或只有一個結點 B．高度等于其結點數(shù) C．任一結點無左孩子 D．任一結點無右孩子 標準答案： B 1下列排序算法中，（ ）排序在每趟結束后不一定能選出一個元素放到其排好序的最終位置上。（ ） A． a B． b C． (a,b) D． (b,c,d) 標準答案： D 具有 65 個結點的完全二叉樹其深度為（ ）。（ ） A．插入排序 B．冒泡排序 C．快速排序 D．歸并排序 標準答案： C 2向堆中插入一個元素的時間復雜度為（ ）。（ ） A． qnext=pnext； pnext=q； B． pnext=qnext； q=p； C． qnext=pnext； pnext=q； D． pnext=qnext； qnext=p； 標準答案： D 2線性表若采用鏈式存儲結構時，要求內存中可 用存儲單元的地址（ ）。（ ） A． O（ nlog2e） B． O（ n+e） C． O(ne) D． O(n2) 標準答案： B 2隊列操作的原則是（ ）。（ ） A．行號 B．列號 C．元素值 D．地址 標準答案： A 2線性鏈表不具有的特點是（ ）。（ ） A．數(shù)據(jù)項 B．數(shù)據(jù)類型 C．數(shù)據(jù)元素 D．數(shù)據(jù)變量 標準答案： C 設循環(huán)隊列 Q[1..N1]的頭尾指針為 F， R，當插入元素時尾指針 R 加 1，頭指針 F 總是指在隊列中第一個元素的前一個位置，則隊列中元素計數(shù)為（ ）。（ ） A． 3 B． 2 C． 1 D． 1/2 標準答案： B 3若線性表最常用的操作是存取第 i 個元素及其前趨的值，則采用（ ）存儲方式節(jié)省時間。（ ） A．直接插入排序 B．快速排序 C．歸并排序 D．直接選擇排序