1、西南大學 網(wǎng)絡與繼續(xù)教育學院 歡迎您！ %E6%9D%8E%E8%87%A3%E8%81%AA同學 學號：W004 窗體頂端單項選擇題 1、用某種排序方法對關鍵字序列（25，84，21，47，15，27，68，35，20）進行排序時，序列的變化情況如下： 20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 則所采用的排序方法是（ ）1. A. 選擇排序 2. 希爾排序 3. 快速排序 4. 歸并排序 2、不定長文件是指（ ）1. 記錄的長度不固定 2. 關鍵字項的長度不固定 3. 字段

2、的長度不固定 4. 文件的長度不固定 3、如下陳述中正確的是（ ）1. 串中元素只能是字母 2. 串是一種特殊的線性表 3. 串的長度必須大于零 4. 空串就是空白串 4、將長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法的時間復雜度為（ ）1. O（m+n） 2. O（n） 3. O（m） 4. O（1） 5、設數(shù)組datam作為循環(huán)隊列SQ的存儲空間，front為隊頭指針，rear為隊尾指針，則執(zhí)行出隊操作后其頭指針front值為（ ）1. F. front=(front+1)%m 2. front=(front-1)%m 3. front=front+1 4. front=(front+

3、1)%(m-1) 6、計算機算法必須具備輸入、輸出和 等5個特性1. 易讀性、穩(wěn)定性和安全性 2. 確定性、有窮性和穩(wěn)定性 3. 可行性、可移植性和可擴充性 4. 可行性、確定性和有窮性 7、有8個結點的無向圖最多有 條邊1. 112 2. 56 3. 28 4. 14 8、不含任何結點的空樹1. 是一棵樹 2. 是一棵二叉樹 3. 是一棵樹也是一棵二叉樹 4. 既不是樹也不是二叉樹 9、一棵深度為6的滿二叉樹有 個分支結點1. 30 2. 31 3. 32 4. 33 10、把一棵樹轉換為二叉樹后，這棵二叉樹的形態(tài)是1. 唯一的 2. 有多種 3. 有多種，但根結點都沒有左孩子 4. 有多種

4、，但根結點都沒有右孩子 11、在對n個元素的序列進行排序時，堆排序所需要的附加存儲空間是:1. O(log2n) 2. O(1) 3. O(n) 4. O(nlog2n) 12、若需要在O(nlog2n)的時間內完成對數(shù)組的排序，且要求排序是穩(wěn)定的，則可選擇的排序方法是（ ）1. 快速排序 2. 堆排序 3. 歸并排序 4. 直接插入 13、設哈希表長m=14,哈希函數(shù)H(key)=key MOD 11。表中已有4個結點：addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7 其余地址為空，如用二次探測再散列處理沖突，則關鍵字為49的地址為:1. 3 2. 5

5、3. 8 4. 9 14、設一棵完全二叉樹有300個結點，則共有 個葉子結點1. 150 2. 152 3. 154 4. 156 15、由個結點所構成的二叉樹有 種形態(tài).1. 2 2. 3 3. 4 4. 5 16、設有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱作：1. 連接 2. 模式匹配 3. 求子串 4. 求串長 17、棧中元素的進出原則是:1. 先進先出 2. 后進先出 3. ?？談t進 4. 棧滿則出 18、鏈表是一種采用 存儲結構存儲的線性表.1. 順序 2. 星式 3. 鏈式 4. 網(wǎng)狀 19、數(shù)據(jù)在計算機存儲器內表示時，物理地址與邏輯地址相同并且是連續(xù)的，稱之為：1. 存儲

6、結構 2. 順序存儲結構 3. 邏輯結構 4. 鏈式存儲 20、一個具有n個頂點的有向圖最多有（ ）條邊1. n(n-1)/2 2. n(n+1)/2 3. n(n-1) 4. n2 21、判斷一個循環(huán)隊列Q（最多n個元素）為滿的條件是:1. Q-front=(Q-rear+1)%n 2. Q-rear=Q-front+1 3. Q-front=(Q-rear-1)%n 4. Q-rear=Q-front 22、在單鏈表中，指針p指向元素為x的結點，實現(xiàn)刪除x的后繼的語句是:1. p=p-next 2. p=p-next-next 3. p-next=p 4. p-next=p-next-ne

7、xt 23、在雙向循環(huán)鏈表中，在p指針所指的結點后插入一個指針q所指向的新結點，修改指針的操作是:1. p-next=q;q-prior=p;p-next-prior=q;q-next=q; 2. q-prior=p;q-next=p-next;p-next-prior=q;p-next=q; 3. q-next=p-next;q-prior=p;p-next=q;p-next=q; 4. p-next=q;p-next-prior=q;q-prior=p;q-next=p-next; 24、在一棵度為3的樹中,度為3的結點個數(shù)為2,度為2 的結點個數(shù)為1,則度為0的結點個數(shù)為( )1. C.

8、 7 2. 6 3. 4 4. 5 25、算法指的是（ ）1. B. 排序算法 2. E. 解決問題的計算方法 3. 計算機程序 4. 解決問題的有限運算序列 26、在含n個頂點和e條邊的無向圖的鄰接矩陣中,零元素的個數(shù)為( )1. n*n2e 2. e 3. n*ne 4. 2e 27、線性表采用鏈式存儲時，結點的存儲地址（ ）1. D. 連續(xù)與否均可 2. 必須是連續(xù)的 3. 和頭結點的存儲地址相連續(xù) 4. 必須是不連續(xù)的 多項選擇題 28、抽象數(shù)據(jù)類型的組成部分分別為: 1. 數(shù)據(jù)對象 2. 存儲結構 3. 數(shù)據(jù)關系 4. 基本操作 29、不具有線性結構的數(shù)據(jù)結構是： 1. 圖 2. 棧

9、 3. 廣義表 4. 樹 30、算法分析的兩個主要方面是( ) 1. 正確性 2. 簡單性 3. 空間復雜度 4. 時間復雜度 判斷題 31、鏈表的每個結點中都恰好包含一個指針1. A.2. B.32、如果將所有中國人按照生日來排序，則使用哈希排序算法最快1. A.2. B.33、折半查找只適用于有序表，包括有序的順序表和鏈表1. A.2. B.34、用循環(huán)單鏈表表示的鏈隊列中，可以不設隊頭指針，僅在隊尾設置隊尾指針。1. A.2. B.35、在單鏈表中，要訪問某個結點，只要知道該結點的地址即可；因此，單鏈表是一種隨機存取結構。1. A.2. B.主觀題36、中序遍歷二叉排序樹所得到的序列是_

10、序列（填有序或無序）。參考答案：有序 37、若一個線性表中最常用的操作是取第i個元素和找第i個元素的前趨元素，則采用（ ）存儲方式最節(jié)省時間.參考答案：順序表 38、設某無向圖中頂點數(shù)和邊數(shù)分別為n和e，所有頂點的度數(shù)之和為d，則e=_。參考答案：d/2 39、 快速排序的最壞時間復雜度為_，平均時間復雜度為_。參考答案：O(n*n)，O(nlog2n) 40、 設一棵完全二叉樹中有500個結點，則該二叉樹的深度為_；若用二叉鏈表作為該完全二叉樹的存儲結構，則共有_個空指針域。參考答案：9，501 41、為了能有效地應用HASH查找技術，必須解決的兩個問題是_和_。參考答案：構造一個好的HAS

11、H函數(shù)，確定解決沖突的方法 42、設有向圖G用鄰接矩陣Ann作為存儲結構，則該鄰接矩陣中第i行上所有元素之和等于頂點i的_，第i列上所有元素之和等于頂點i的_。參考答案：出度，入度 43、在一個長度為n的順序表中刪除第i個元素，需要向前移動（ ）個元素.參考答案：n-1 44、 參考答案：（1）Push(S,N%8) （2）!StackEmpty(S)45、帶頭結點的單鏈表head為空的判定條件是（ ）。參考答案：head-next=NULL 46、1.數(shù)據(jù)的存儲結構可用四種基本的存儲方法表示，它們分別是( ).2.在具有n個元素的循環(huán)隊列中，隊滿時具有 個元素.3. 廣義表A=(a),a)的

12、表頭是（ ）。4.稀疏矩陣一般的壓縮存儲方法有( )和（）兩種。5.用順序存儲的方法，將完全二叉樹中所有結點按層逐個從左到右的順序存放在一維數(shù)組R1.N中，若結點Ri有右孩子，則其右孩子是（ ）6. 如果從無向圖的任一頂點出發(fā)進行一次深度優(yōu)先搜索即可訪問所有頂點，則該圖一定是( )7.n個頂點的連通圖至少有 邊。8.已知一個有序表為（11，22，33，44，55，66，77，88，99），則折半查找55需要比較（ ）次。9.對一棵二叉排序樹按（ ）遍歷，可得到結點值從小到大的排列序列。10.一個序列中有10000個元素，若只想得到其中前10個最小元素，則最好采用（ ）方法參考答案：1.順序、鏈

13、式、索引、散列2.n-13.(a)4.三元組 十字鏈表5.R2i+16.連通圖7.n-18.19.中序10.堆排序 47、下面程序段的功能實現(xiàn)數(shù)據(jù)x進棧，要求在下劃線處填上正確的語句。typedef struct int s100; int top; sqstack;void push(sqstack &stack,int x)if (stack.top=m-1) printf(“overflow”);else _;_;參考答案：stack.top+，stack.sstack.top=x 48、一個循環(huán)隊列Q的存儲空間大小為M,其隊頭和隊尾指針分別為front和rear，則循環(huán)隊列中元素的個數(shù)

14、為： 。參考答案：(rear-front+M)%M 49、設串長為n，模式串長為m，則KMP算法所需的附加空間為( )參考答案：O(m) 50、一個線性表為B=（12，23，45，57，20，03，78，31，15，36），設散列表為HT0.12，散列函數(shù)為H（key）= key % 13并用線性探查法解決沖突，請畫出散列表，并計算等概率情況下查找成功的平均查找長度。參考答案： 0 1 2 3 4 5 6 7 8 9 10 11 12 7815 03 57 45 20 31 23 36 12 查找成功的平均查找長度：ASL SUCC=14/10= 1.451、寫出用直接插入排序將關鍵字序列54

15、,23,89,48,64,50,25,90,34排序過程的每一趟結果。參考答案：52、閱讀以下二叉樹操作算法，指出該算法的功能。Template void BinTree ：unknown (BinTreeNode*t) BinTreeNode *p =t, *temp; if (p!=NULL) temp = pleftchild; pleftchild = prightchild; prightchild = temp; unknown(pleftchild); undnown(prightchild); 該算法的功能是：_參考答案：該算法的功能是：交換二叉樹的左右子樹的遞歸算法。 53、

16、已知一棵二叉樹的前序遍歷的結果序列是ABECKFGHIJ，中序遍歷的結果是EBCDAFHIGJ，試寫出這棵二叉樹的后序遍歷結果。參考答案：EDCBIHJGFA 54、已知一組記錄的排序碼為（46，79，56，38，40，80, 95，24），寫出對其進行快速排序的每一次劃分結果。參考答案：劃分次序 劃分結果 第一次 38 24 40 46 56 80 95 79 第二次 24 38 40 46 56 80 95 79 第三次 24 38 40 46 56 80 95 79 第四次 24 38 40 46 56 80 95 79 第五次 24 38 40 46 56 79 80 95 第六次 2

17、4 38 40 46 56 79 80 95 55、設待排序序列為10,18,4,3,6,12,1,9,15,8請寫出希爾排序每一趟的結果。增量序列為5，3，2，1。參考答案：56、寫出下列程序的時間復雜度 s=0; for i=0; in; i+)for(j=0; jn; j+) s+=Bij;sum=s;參考答案：O（n2） 57、設循環(huán)隊列的容量為40（序號從0到39），現(xiàn)經過一系列的入隊和出隊運算后，有 front=11，rear=19; front=19，rear=11；問在這兩種情況下，循環(huán)隊列中各有元素多少個？參考答案：（1）L=（401911）% 40=8（2） L=（401119）% 40=32 58、寫出下列程序的時間復雜度for(i=0; in; i+)for (j=0; jm; j+)Aij=0;參考答案：O（m*n） 59、設給定一個權值集