西南大學(xué)網(wǎng)絡(luò)與繼續(xù)教育學(xué)院課程代碼：0012學(xué)年學(xué)季：20201單項(xiàng)選擇題1、用某種排序方法對關(guān)鍵字序列（25，84，21，47，15，27，68，35，20）進(jìn)行排序時(shí)，序列的變化情況如下：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.A.選擇排序2.希爾排序3.快速排序4.歸并排序2、不定長文件是指（）1.記錄的長度不固定2.關(guān)鍵字項(xiàng)的長度不固定3.字段的長度不固定4.文件的長度不固定3、如下陳述中正確的是（）1.串中元素只能是字母2.串是一種特殊的線性表3.串的長度必須大于零4.空串就是空白串4、將長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法的時(shí)間復(fù)雜度為（）1.O（m+n）2.O（n）3.O（m）4.O（1）5、設(shè)數(shù)組data[m]作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則執(zhí)行出隊(duì)操作后其頭指針front值為（）1.F.front=(front+1)%m2.front=(front-1)%m3.front=front+14.front=(front+1)%(m-1)6、計(jì)算機(jī)算法必須具備輸入、輸出和等5個(gè)特性1.易讀性、穩(wěn)定性和安全性2.確定性、有窮性和穩(wěn)定性3.可行性、可移植性和可擴(kuò)充性4.可行性、確定性和有窮性7、有8個(gè)結(jié)點(diǎn)的無向圖最多有條邊1.1122.563.284.148、不含任何結(jié)點(diǎn)的空樹1.是一棵樹2.是一棵二叉樹3.是一棵樹也是一棵二叉樹4.既不是樹也不是二叉樹9、一棵深度為6的滿二叉樹有個(gè)分支結(jié)點(diǎn)1.302.313.324.3310、把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是1.唯一的2.有多種3.有多種，但根結(jié)點(diǎn)都沒有左孩子4.有多種，但根結(jié)點(diǎn)都沒有右孩子11、在對n個(gè)元素的序列進(jìn)行排序時(shí)，堆排序所需要的附加存儲(chǔ)空間是:1.O(log2n)2.O(1)3.O(n)4.O(nlog2n)12、若需要在O(nlog2n)的時(shí)間內(nèi)完成對數(shù)組的排序，且要求排序是穩(wěn)定的，則可選擇的排序方法是（）1.快速排序2.堆排序3.歸并排序4.直接插入13、設(shè)哈希表長m=14,哈希函數(shù)H(key)=keyMOD11。表中已有4個(gè)結(jié)點(diǎn)：addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7其余地址為空，如用二次探測再散列處理沖突，則關(guān)鍵字為49的地址為:1.32.53.84.914、設(shè)一棵完全二叉樹有300個(gè)結(jié)點(diǎn)，則共有個(gè)葉子結(jié)點(diǎn)1.1502.1523.1544.15615、由３個(gè)結(jié)點(diǎn)所構(gòu)成的二叉樹有種形態(tài).1.22.33.416、設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱作：1.連接2.模式匹配3.求子串4.求串長17、棧中元素的進(jìn)出原則是:1.先進(jìn)先出2.后進(jìn)先出3.?？談t進(jìn)4.棧滿則出18、鏈表是一種采用存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的線性表.1.順序2.星式3.鏈?zhǔn)?.網(wǎng)狀19、數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與邏輯地址相同并且是連續(xù)的，稱之為：1.存儲(chǔ)結(jié)構(gòu)2.順序存儲(chǔ)結(jié)構(gòu)3.邏輯結(jié)構(gòu)4.鏈?zhǔn)酱鎯?chǔ)20、一個(gè)具有n個(gè)頂點(diǎn)的有向圖最多有（）條邊1.n×(n-1)/22.n×(n+1)/23.n×(n-1)4.n221、判斷一個(gè)循環(huán)隊(duì)列Q（最多n個(gè)元素）為滿的條件是:1.Q->front==(Q->rear+1)%n2.Q->rear==Q->front+13.Q->front==(Q->rear-1)%n4.Q->rear==Q->front22、在單鏈表中，指針p指向元素為x的結(jié)點(diǎn)，實(shí)現(xiàn)刪除x的后繼的語句是:1.p=p->next2.p=p->next->next3.p->next=p4.p->next=p->next->next23、在雙向循環(huán)鏈表中，在p指針?biāo)傅慕Y(jié)點(diǎn)后插入一個(gè)指針q所指向的新結(jié)點(diǎn)，修改指針的操作是: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;24、在一棵度為3的樹中,度為3的結(jié)點(diǎn)個(gè)數(shù)為2,度為2的結(jié)點(diǎn)個(gè)數(shù)為1,則度為0的結(jié)點(diǎn)個(gè)數(shù)為()1.C.72.63.44.525、算法指的是（）1.B.排序算法2.E.解決問題的計(jì)算方法3.計(jì)算機(jī)程序4.解決問題的有限運(yùn)算序列26、在含n個(gè)頂點(diǎn)和e條邊的無向圖的鄰接矩陣中,零元素的個(gè)數(shù)為()1.n*n－2e2.e3.n*n－e4.2e27、線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，結(jié)點(diǎn)的存儲(chǔ)地址（）1.D.連續(xù)與否均可2.必須是連續(xù)的3.和頭結(jié)點(diǎn)的存儲(chǔ)地址相連續(xù)4.必須是不連續(xù)的多項(xiàng)選擇題28、抽象數(shù)據(jù)類型的組成部分分別為:1.數(shù)據(jù)對象2.存儲(chǔ)結(jié)構(gòu)3.數(shù)據(jù)關(guān)系4.基本操作29、不具有線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)是：1.圖2.棧3.廣義表4.樹30、算法分析的兩個(gè)主要方面是()1.正確性2.簡單性3.空間復(fù)雜度4.時(shí)間復(fù)雜度判斷題31、樹在實(shí)際應(yīng)用中采用多種不同的形式表示和存儲(chǔ)1.A.√32、完全二叉樹一定是滿二叉樹1.A.√2.B.×33、在完全二叉樹中，葉節(jié)點(diǎn)個(gè)數(shù)比分支節(jié)點(diǎn)個(gè)數(shù)多11.A.√2.B.×34、任何二叉搜索樹中同一層的結(jié)點(diǎn)從左到右是有序的（從小到大）。1.A.√2.B.×35、棧和隊(duì)列邏輯上都是線性表1.A.√2.B.×36、算法分析的兩個(gè)主要方面是時(shí)間復(fù)雜度和空間復(fù)雜度的分析。1.A.√2.B.×37、若用鏈表來表示一個(gè)線性表，則表中元素的地址一定是連續(xù)的。1.A.√2.B.×38、鏈表的每個(gè)結(jié)點(diǎn)中都恰好包含一個(gè)指針1.A.√2.B.×39、如果將所有中國人按照生日來排序，則使用哈希排序算法最快1.A.√2.B.×40、折半查找只適用于有序表，包括有序的順序表和鏈表1.A.√2.B.×41、用循環(huán)單鏈表表示的鏈隊(duì)列中，可以不設(shè)隊(duì)頭指針，僅在隊(duì)尾設(shè)置隊(duì)尾指針。1.A.√2.B.×42、在單鏈表中，要訪問某個(gè)結(jié)點(diǎn)，只要知道該結(jié)點(diǎn)的地址即可；因此，單鏈表是一種隨機(jī)存取結(jié)構(gòu)。1.A.√2.B.×43、一般樹和二叉樹的結(jié)點(diǎn)數(shù)都可以為0;1.A.√2.B.×44、通過對堆棧S操作：Push(S,1),Push(S,2),Pop(S),Push(S,3),Pop(S),Pop(S)。輸出的序列為：1231.A.√2.B.×45、不論是入隊(duì)列操作還是入棧操作,在順序存儲(chǔ)結(jié)構(gòu)上都需要考慮"溢出"情況。1.A.√2.B.×46、一棵有124個(gè)結(jié)點(diǎn)的完全二叉樹，其葉結(jié)點(diǎn)個(gè)數(shù)是確定的1.A.√2.B.×主觀題47、中序遍歷二叉排序樹所得到的序列是___________序列（填有序或無序）。參考答案：有序48、在一個(gè)長度為n的順序表中刪除第i個(gè)元素，需要向前移動(dòng)（）個(gè)元素.參考答案：n-149、1、已知棧的基本操作函數(shù)：intInitStack(SqStack*S);//構(gòu)造空棧intStackEmpty(SqStack*S);//判斷棧空intPush(SqStack*S,ElemTypee);//入棧intPop(SqStack*S,ElemType*e);//出棧函數(shù)conversion實(shí)現(xiàn)十進(jìn)制數(shù)轉(zhuǎn)換為八進(jìn)制數(shù)，請將函數(shù)補(bǔ)充完整。voidconversion(){InitStack(S);scanf(“%d”,&N);while(N){（1）N=N/8;};while(（2）){Pop(S,&e);printf(“%d”,e);}}//conversion參考答案：（1）Push(S,N%8)（2）!StackEmpty(S)50、帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是（）。參考答案：head->next==NULL51、1.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)可用四種基本的存儲(chǔ)方法表示，它們分別是().2.在具有n個(gè)元素的循環(huán)隊(duì)列中，隊(duì)滿時(shí)具有個(gè)元素.3.廣義表A=((a),a)的表頭是（）。4.稀疏矩陣一般的壓縮存儲(chǔ)方法有()和（）兩種。5.用順序存儲(chǔ)的方法，將完全二叉樹中所有結(jié)點(diǎn)按層逐個(gè)從左到右的順序存放在一維數(shù)組R[1..N]中，若結(jié)點(diǎn)R[i]有右孩子，則其右孩子是（）6.如果從無向圖的任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索即可訪問所有頂點(diǎn)，則該圖一定是()7.n個(gè)頂點(diǎn)的連通圖至少有邊。8.已知一個(gè)有序表為（11，22，33，44，55，66，77，88，99），則折半查找55需要比較（）次。9.對一棵二叉排序樹按（）遍歷，可得到結(jié)點(diǎn)值從小到大的排列序列。10.一個(gè)序列中有10000個(gè)元素，若只想得到其中前10個(gè)最小元素，則最好采用（）方法參考答案：1<\/font>.順序、鏈?zhǔn)健⑺饕?、散?lt;\/font><\/p>2.n-1<\/font><\/p>3.(a)<\/font><\/p>4.三元組十字鏈表<\/font><\/p>5.R[2i+1]<\/font><\/p>6.連通圖<\/font><\/p>7.n-1<\/font><\/p>8.1<\/font><\/p>9.中序<\/font><\/p>10.堆排序<\/font><\/p><\/font><\/p>52、下面程序段的功能實(shí)現(xiàn)數(shù)據(jù)x進(jìn)棧，要求在下劃線處填上正確的語句。typedefstruct{ints[100];inttop;}sqstack;voidpush(sqstack&stack,intx){if(stack.top==m-1)printf(“overflow”);else{____________________;_________________;}}參考答案：stack.top++，stack.s[stack.top]=x53、一個(gè)循環(huán)隊(duì)列Q的存儲(chǔ)空間大小為M,其隊(duì)頭和隊(duì)尾指針分別為front和rear，則循環(huán)隊(duì)列中元素的個(gè)數(shù)為：。參考答案：(rear-front+M)%M54、設(shè)串長為n，模式串長為m，則KMP算法所需的附加空間為()參考答案：O(m)55、寫出用直接插入排序?qū)㈥P(guān)鍵字序列{54,23,89,48,64,50,25,90,34}排序過程的每一趟結(jié)果。參考答案：初始：54，23，89，48，64，50，25，90，341：（23，54），89，48，64，50，25，90，342：（23，54，89），48，64，50，25，90，343：（23，48，54，89），64，50，25，90，344：（23，48，54，64，89），50，25，90，345：（23，48，50，54，64，89），25，90，346：（23，25，48，50，54，64，89），90，347：（23，25，48，50，54，64，89，90），348：（23，25，48，50，54，64，89，90，34）56、設(shè)待排序序列為{10,18,4,3,6,12,1,9,15,8}請寫出希爾排序每一趟的結(jié)果。增量序列為5，3，2，1。參考答案：初始：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、寫出下列程序的時(shí)間復(fù)雜度s=0;fori=0;i<n;i++)for(j=0;j<n;j++)s+=B[i][j];sum=s;參考答案：O（n^2）58、設(shè)循環(huán)隊(duì)列的容量為40（序號從0到39），現(xiàn)經(jīng)過一系列的入隊(duì)和出隊(duì)運(yùn)算后，有front=11，rear=19;front=19，rear=11；