1、西南大學(xué)網(wǎng)絡(luò)與繼續(xù)教育學(xué)院課程代碼： 0012學(xué)年學(xué)季：20191單項選擇題1、用某種排序方法對關(guān)鍵字序列（25, 84, 21, 47, 15, 27, 68, 35, 20）進(jìn)行排序時，序列的變化情況如下:20 ,15,21,25,47,27,68,35,8415 ,20,21,25,35,27,47,68,8415 ,20,21,25,27,35,47,68,84則所采用的排序方法是（）1.0A.選擇排序2 .希爾排序3 .快速排序 ,4 .歸并排序2、不定長文件是指（）1 .r記錄的長度不固定2 .關(guān)鍵字項的長度不固定3 .字段的長度不固定4 .文件的長度不固定 /3、如下陳述中正確的

2、是(1 .用中元素只能是字母,2 .用是一種特殊的線性表3 .用的長度必須大于零4 .空用就是空白申4、將長度為n的單鏈表鏈接在長度為 m的單鏈表之后的算法的時間復(fù)雜度為()1 .0O(m+r)2 .O(n)3 .O(m4 .O(1)一5、設(shè)數(shù)組datam作為循環(huán)隊列SQ的存儲空間，front為隊頭指針，rear為隊尾指針，則執(zhí)行出隊操作后其頭指1 .F. front=(front+1)%m /2 .front=(front-1)%mr3 .front=front+14 .front=(front+1)%(m-1)6、計算機(jī)算法必須具備輸入、輸出和 等5個特性1 .易讀性、穩(wěn)定性和安全性2 .

3、確定性、有窮性和穩(wěn)定性3 .可行性、可移植性和可擴(kuò)充性4 .可行性、確定性和有窮性一7、有8個結(jié)點(diǎn)的無向圖最多有 條邊1.01122 .563 .28，4 .148、不含任何結(jié)點(diǎn)的空樹1 .是一棵樹2 .是一棵二叉樹3 .是一棵樹也是一棵二叉樹 一4 .既不是樹也不是二叉樹9、一棵深度為6的滿二叉樹有一個分支結(jié)點(diǎn)1.0302.31 W3.0324.03310、把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是2.1. 唯一的 夕有多種3 .有多種，但根結(jié)點(diǎn)都沒有左孩子4 .有多種，但根結(jié)點(diǎn)都沒有右孩子11、在對n個元素的序列進(jìn)行排序時，堆排序所需要的附加存儲空間是：1.O(log2n)2.00(1)引

4、3.0(n)4.0O(nlog2n)12、若需要在 O(nlog2n)的時間內(nèi)完成對數(shù)組的排序，且要求排序是穩(wěn)定的，則可選擇的排序方法是()1 .快速排序2 .堆排序3 .歸并排序/4 .直接插入13、設(shè)哈希表長 m=14，哈希函數(shù) H(key尸key MOD 11。表中已有 4 個結(jié)點(diǎn)：addr(15)=4,addr(38)=5,addr(61)=探測再散列處理沖突，則關(guān)鍵字為49的地址為：1.32.053 .8/4 .914、設(shè)一棵完全二叉樹有300個結(jié)點(diǎn)，則共有 個葉子結(jié)點(diǎn)1.150/2.01523.1544.15615、由3個結(jié)點(diǎn)所構(gòu)成的二叉樹有 種形態(tài).1.022 .33 .44 .

5、5 W16、設(shè)有兩個串p和q,求q在p中首次出現(xiàn)的位置的運(yùn)算稱作:1 .連接2 .模式匹配 U3 .求子用4 .求用長17、棧中元素的進(jìn)出原則是：1 .先進(jìn)先出2 .后進(jìn)先出守3 .棧空則進(jìn)4 .棧滿則出18、鏈表是一種采用 存儲結(jié)構(gòu)存儲的線性表1 .順序2 .星式3 .鏈?zhǔn)?夕4 .網(wǎng)狀19、數(shù)據(jù)在計算機(jī)存儲器內(nèi)表示時，物理地址與邏輯地址相同并且是連續(xù)的，稱之為:1 .存儲結(jié)構(gòu)2 .順序存儲結(jié)構(gòu)引3 .邏輯結(jié)構(gòu)4 .鏈?zhǔn)酱鎯?0、判斷一個循環(huán)隊列 Q (最多n個元素)為滿的條件是1 .Q->front=(Q->rear+1)%n/r2 .Q->rear=Q->fron

6、t+13 .0Q->front=(Q->rear-1)%nr4.Q->rear=Q->front21、在單鏈表中，指針 p指向元素為x的結(jié)點(diǎn)，實(shí)現(xiàn)刪除x的后繼的語句是1. p=p->nextC2. p=p->next->next3. p->next=p4. p->next=p->next->next ，22、在雙向循環(huán)鏈表中，在p指針?biāo)傅慕Y(jié)點(diǎn)后插入一個指針q所指向的新結(jié)點(diǎn)，修改指針的操作是r1. p->next=q;q->prior=p;p->next->prior=q;q->next=q;2.

7、q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;守C3. q->next=p->next;q->prior=p;p->next=q;p->next=q;r4. p->next=q;p->next->prior=q;q->prior=p;q->next=p->next;23、在一棵度為3的樹中，度為3的結(jié)點(diǎn)個數(shù)為2,度為2的結(jié)點(diǎn)個數(shù)為1,則度為0的結(jié)點(diǎn)個數(shù)為(1 .C. 72 .063 .44 .05，24、算法指的是（）1 .0B.排

8、序算法2 .E.解決問題的計算方法3 .計算機(jī)程序4 .解決問題的有限運(yùn)算序列 一25、在含n個頂點(diǎn)和e條邊的無向圖的鄰接矩陣中，零元素的個數(shù)為（）1 .n*n 2e W2 .Ce- r43 .n*n e4 .2e26、線性表采用鏈?zhǔn)酱鎯r，結(jié)點(diǎn)的存儲地址（）1.0D.連續(xù)與否均可2 .必須是連續(xù)的3 .和頭結(jié)點(diǎn)的存儲地址相連續(xù)/4 .必須是不連續(xù)的多項選擇題27、抽象數(shù)據(jù)類型的組成部分分別為：1 .廠數(shù)據(jù)對象/2 .存儲結(jié)構(gòu)3 .數(shù)據(jù)關(guān)系夕4 .基本操作一28、不具有線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)是：1 . 圖 U2 .棧3 . 廣義表 嫡4 .樹 ,29、算法分析的兩個主要方面是（）1 .正確性2 .

9、簡單性3 .空間復(fù)雜度,4 .廠時間復(fù)雜度/判斷題30、樹在實(shí)際應(yīng)用中采用多種不同的形式表示和存儲1 .A.V ，2 .B. X31、完全二叉樹一定是滿二叉樹1 .A.V2 .B. X /32、在完全二叉樹中，葉節(jié)點(diǎn)個數(shù)比分支節(jié)點(diǎn)個數(shù)多11 .A.V2 .B. X/33、任何二叉搜索樹中同一層的結(jié)點(diǎn)從左到右是有序的（從小到大）。1 .A.V，2 .B. X34、棧和隊列邏輯上都是線性表1 .A.V /2 .B. X35、 算法分析的兩個主要方面是時間復(fù)雜度和空間復(fù)雜度的分析。1 .a.v d2 .B. X36、 若用鏈表來表示一個線性表，則表中元素的地址一定是連續(xù)的。1 .A.V2 .B. X

10、 U37、鏈表的每個結(jié)點(diǎn)中都恰好包含一個指針1 .A.V2 .B. X38、如果將所有中國人按照生日來排序，則使用哈希排序算法最快1 .A.V2 .B. X W39、折半查找只適用于有序表，包括有序的順序表和鏈表1 .A.V2 .B. X，40、用循環(huán)單鏈表表示的鏈隊列中，可以不設(shè)隊頭指針，僅在隊尾設(shè)置隊尾指針。1 .A.V，2 .B. X41、在單鏈表中，要訪問某個結(jié)點(diǎn)，只要知道該結(jié)點(diǎn)的地址即可；因此，單鏈表是一種隨機(jī)存取結(jié)構(gòu)。1 .A.V2 .B. X ,42、 一般樹和二叉樹的結(jié)點(diǎn)數(shù)都可以為0；1 .A.V2 .B. X /43、 通過對堆棧 S操作：Push(S,1), Push(S,

11、2), Pop(S), Push(S,3), Pop(S), Pop(S)。輸出的序列為:1 .A.V2 .B. XW44、 不論是入隊列操作還是入棧操作，在順序存儲結(jié)構(gòu)上都需要考慮"溢出"情況。1.A.V02.45、B. X1.2.B. X一棵有124個結(jié)點(diǎn)的完全二叉樹，其葉結(jié)點(diǎn)個數(shù)是確定的主觀題46、中序遍歷二叉排序樹所得到的序列是序列（填有序或無序）。參考答案 有序47、若一個線性表中最常用的操作是取第i個元素和找第i個元素的前趨元素，則采用（ 參考答案：順序表48、設(shè)某無向圖中頂點(diǎn)數(shù)和邊數(shù)分別為n和e,所有頂點(diǎn)的度數(shù)之和為d,則e=49、快速排序的最壞時間復(fù)雜度為,

12、平均時間復(fù)雜度為參考答案：O(n*n) , O(nlog2n)50、;若用二叉鏈表作為該完全二叉樹的存設(shè)一棵完全二叉樹中有 500個結(jié)點(diǎn)，則該二叉樹的深度為參考答案:9, 50151、一個線性表為 B= (12, 23, 45, 57, 20, 03, 78, 31, 15, 36),設(shè)散列表為 HT0.12,散列函數(shù)為 H (ke：查找長度。34578150357452031233612查找成功的平均查找長度：ASL SUCC=14/10= 1.452、 寫出用直接插入排序?qū)㈥P(guān)鍵字序列54,23,89,48,64,50,25,90,34排序過程的每一趟結(jié)果。初始：54，23，89，48，64

13、，50，25，90，341 ：（23， 54），89， 48，2 ：（23， 54， 89），48，3 ：（23，48，54，89），4 ：（23，48，54，64，5 ：（23，48，50，54，6 ：（23，25，48，50，7 ：（23，25，48，50，64，50，25，90，3464，50，25，90，3464，50，25，90，3489)，50，25，90，3464， 89)，25， 90， 3454， 64， 89)，90， 3454， 64， 89， 90)，348：（23，25，48，50，54，64，89，90，34）53、閱讀以下二叉樹操作算法，指出該算法的功能。Temp

14、late <calss type > voidBinTree <Type>unknown (BinTreeNode<Type>*t) BinTreeNode< Type>*p =t, *temp;if (p!=NULL) temp = p f leftchild;pfleftchild = pf rightchild;pfrightchild = temp;unknown(尸 leftchild);undnown(尸 rightchild);該算法的功能是：參考答案：該算法的功能是：交換二叉樹的左右子樹的遞歸算法。54、已知一棵二叉樹的前序遍歷的

15、結(jié)果序列是ABECKFGHIJ中序遍歷的結(jié)果是 EBCDAFHIGJ試寫出這棵二叉參考答案：EDCBIHJGFA55、已知一組記錄的排序碼為(46， 79， 56， 38， 40， 80,95 ， 24)，寫出對其進(jìn)行快速排序的每一次劃分結(jié)果劃分次序 劃分結(jié)果第一次382440 4656809579第二次243840 4656809579第三次24 38404656809579第四次24 38404656809579第五次24 38404656798095第六次24 384046567980955，56、 設(shè)待排序序列為10,18,4,3,6,12,1,9,15,8 請寫出希爾排序每一趟的結(jié)果

16、。增量序列為初始：10，18，4，3，6，12，1，9，15，8d=5：10，1，4，3，6，12，18，9，15，8d=3 ：3，1，4，8，6，12，10，9，15，18d=2 ：3，1，4，8，6，9，10，12，15，18d=1 ：1，3，4，6，8，9，10，12，15，1857、 寫出下列程序的時間復(fù)雜度s=0;for i=0; i<n; i+)for(j=0; j<n; j+)s+=Bij;sum=s;O (nA2)58、 設(shè)循環(huán)隊列的容量為40（序號從0 到 39），現(xiàn)經(jīng)過一系列的入隊和出隊運(yùn)算后，有 front=11 ， rear=19; 參考答案： front=19 ， rear=11 ；問在這兩種情況下，循環(huán)隊列中各有元素多2)L=( 40 11 19) %1