《計(jì)算機(jī)軟件技術(shù)基礎(chǔ)》復(fù)習(xí)題(含答案)

1、計(jì)算機(jī)軟件技術(shù)基礎(chǔ)復(fù)習(xí)題1 .線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)相比優(yōu)點(diǎn)是CD 。A.所有的操作算法實(shí)現(xiàn)簡(jiǎn)單B.便于隨機(jī)存取C.便于插入和刪除D.便于利用零散的存儲(chǔ)器空間2 .線性表是具有n個(gè) 一數(shù)據(jù)元素 的有限序列。C.A.表元素B.字符D.數(shù)據(jù)項(xiàng)E.信息項(xiàng)3 .若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第I個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為 C。 ( K I < n+1)A. O(0)B. O(1)C. O(n)D. O(n 2)4.設(shè)A是一個(gè)線性表(ai,a2,a n),采用順序存儲(chǔ)結(jié)構(gòu)，則在等概率的前提下，平均每插入 一個(gè)元素需要移動(dòng)的元素個(gè)數(shù)為 B,平均每刪除一個(gè)元素需要移

2、動(dòng)的元素個(gè)數(shù)為；若兀素插在ai與ai+i之間(0 w I w n-i)的概率為2(n - i),則平均每插入一個(gè)n(n 1)元素所要移動(dòng)的元素個(gè)數(shù)為A.2c 2n 1C.3B.D.n23n 145.下列函數(shù)中，按它們?cè)贏. log nnT笛時(shí)的無窮大階數(shù)，最大的是n/2C. 26.將下圖所示的DnextnextnextB. nlog nD. n!s所指結(jié)點(diǎn)加到p所指的結(jié)點(diǎn)之后，其語(yǔ)句應(yīng)為:A. s->next=p+1; p->next=s;B. (*p).next=s; (*s).next=(*p).next;C. s->next=p->next; p->next

3、=s->next;D. s->next=p->next; p->next=s;7.將兩個(gè)各有n個(gè)元素的有序表歸并為一個(gè)有序表時(shí)，其最少的比較次數(shù)是A 。A. nB. 2n-1C. n-1D. 2n8.下面的程序段是合并兩個(gè)無頭結(jié)點(diǎn)鏈表(ha和hb)為一個(gè)無頭結(jié)點(diǎn)鏈表 ha的過程，作為參數(shù)的兩個(gè)鏈表都是按結(jié)點(diǎn)的data域由大到小鏈接的。合并后新鏈表的結(jié)點(diǎn)仍按此方式鏈接。請(qǐng)?zhí)顚懴率隹湛?，使程序能正確運(yùn)行。#define NULL 0 typedef struct nodeint data;struct node *next;node, linklisttype;void c

4、ombine(linklisttype *ha, linklisttype *hb) linklisttype *h, *p;h = (linklisttype *)malloc(sizeof(linklisttype); h->next = NULL;p = h；/*較大的元素先插入*/while(ha != NULL && hb != NULL) if(ha->data>=hb->data)p->next =(1)P = _(3)(2)elsep->next =(4);(5)；(8) if(ha=NULL) if(hb=NULL) ha

5、= h->next; free(h);參考答案ha(4) hb p->next=hb(2) p->next(5) p->next9.如果表中所有元素(ai,a2,an)與表(3) ha=ha->next(6) hb=hb->next(8) p->next=ha的一個(gè)順序子表(b k,b k+i,b k+n-i)完全相同(即ai=bk,a2=bk+i,a n=bk+n-i),則稱表A包含在表B中。設(shè)ha, hb為帶頭結(jié)點(diǎn)的單鏈表，分別表示有序表A和B,下面的函數(shù)用于判別表 A是否包含在表 B中，若是，則返回true ,否則返 回false 。(提示：用遞

6、歸實(shí)現(xiàn))#define true i #define false 0#define NULL 0 typedef struct node int data;struct node *next;node, linklisttype;int inclusion(linklisttype *ha, linklisttype *hb) linklisttype *pa, *pb;pa = ha->next;pb = hb->next; ； while( (2)if(pa->data=pb->data)(3);else(4);； 參考答案：(1) if(pa=NULL) retu

7、rn(true)(2) pb!=NULL && pa->data>=pb->data (3) return(inclusion(pa, pb)(4) pb = pb->next;(5) return(false)10.在本題的程序中，函數(shù) create_link_list(n) 建立一個(gè)具有 n個(gè)結(jié)點(diǎn)的循環(huán)鏈表；函數(shù) josephus(n,I,m) 對(duì)由create_link_list(n) 所建立的具有 n個(gè)結(jié)點(diǎn)的循環(huán)鏈表按一定的次 序逐個(gè)輸出，并刪除鏈表中的所有結(jié)點(diǎn)。參數(shù) n(n>0)指明循環(huán)鏈表的結(jié)點(diǎn)個(gè)數(shù)，參數(shù) I(1 w I w n)指明起

8、始結(jié)點(diǎn)，參數(shù)m (m>0是步長(zhǎng))，指明從起始結(jié)點(diǎn)或前次被刪除并輸出的結(jié)點(diǎn)之后的第m個(gè)結(jié)點(diǎn)作為本次被輸出并刪除的結(jié)點(diǎn)。 例如，對(duì)于下圖所示的具有 6個(gè)結(jié)點(diǎn)的循 環(huán)鏈表，在調(diào)用josephus(6,3,2) 后，將輸出5,1,3,6,4,2。請(qǐng)?jiān)诳湛蛱幪钌线m當(dāng)內(nèi)容，每框只填一個(gè)語(yǔ)句。#define NULL 0typedef struct nodeint data;struct node *next;node, linklisttype;linklisttype *create_link_list(int n)linklisttype *head, *p, *q;int I;head = N

9、ULL;if(n>0)head = (linklisttype *)malloc(sizeof(linklisttype);p = head;for(I=1;I<=n-1;I+)/*此循環(huán)用于建立一個(gè)鏈表，鏈表的內(nèi)容從1至n-1*/p->data = I; q = (linklisttype *)malloc(sizeof(linklistttype); ；p->data = n;；/*建立從尾鏈到首的環(huán)形結(jié)構(gòu)*/return(head);void Josephus(int n, int j, int m) linklisttype *p, *q;int j；p = c

10、reate_link_list(n);for(;I>1;I-)p = p->next;(4)；while(j<n)for(I=1;I<=m-1;I+) p = p->next;(5);printf("%8d ,q ->data);(6);free(q); j=j+1; 參考答案：(1) p->next = q;(2) p = q;(3) p->next = head(4) j=0(5) q=p->next;(6) p->next = q->next11.在下列程序中，函數(shù)difference(A,B)用于求兩集合之差C

11、=A-B,即當(dāng)且僅當(dāng)e是A中的一個(gè)元素，且不是 B中的元素時(shí)，e是C中的一個(gè)元素。集合用有序鏈表實(shí)現(xiàn)，用一個(gè)空鏈 表表示一個(gè)空集合，表示非空集合的鏈表根據(jù)元素之值按遞增排列，執(zhí)行C=A-B之后，表示集合A和B的鏈表不變，若結(jié)果集合C非空，則表示它的鏈表應(yīng)根據(jù)元素之值按遞增序排列。 函數(shù)append()用于在鏈表中添加結(jié)點(diǎn)。#include <stdio.h>#define NULL 0typedef struct nodeint data;struct node *next;NODE;NODE *append(NODE *last, int x)last->next=(NOD

12、E *)malloc(sizeof(NODE);last->next->data=x;return(last->next);NODE *difference(NODE *A ,NODE *B兒 NODE *C,*last;C=last=(NODE *)malloc(sizeof(NODE); while( )if(A->data < B->data)last=append(last,A->data); A=A->next; else if( (2)A=A->next; B=B->next; else ； while( (4)last=

13、append(last,A->data); A=A->next; ；last=C; C=C->next; free(last); return(C); 參考答案：(1) A!=NULL & B!=NULL(2) A->data=B->data B=B->next;(4) A!=NULL(5) last->next=NULL;12.閱讀以下算法，填充空格，使其成為完整的算法。其功能是在一個(gè)非遞減的順序存儲(chǔ)線 性表中(從下標(biāo)1處開始存儲(chǔ))，刪除所有值相等的多余元素。#define MAXSIZE 30 typedef structint elemM

14、AXSIZE;int length;/* 表長(zhǎng) */ sqlisttype;void exam21(sqlisttype *L) int i,j;i=2,j=1;while()if(L->elemi<>L->elemj)(2)； i+； (4)；參考答案：(1) i<=L->length(2) L->elemj+1=L->elemi j+；(4)L->length=j13 .用單鏈表表示的鏈?zhǔn)疥?duì)列的隊(duì)頭在鏈表的A位置。A.鏈頭B.鏈尾C.鏈中14 .若用單鏈表表示隊(duì)列，則應(yīng)該選用B。A.帶尾指針的非循環(huán)鏈表B.帶尾指針的循環(huán)鏈表C.帶頭指針

15、的非循環(huán)鏈表D.帶頭指針的循環(huán)鏈表15 .在解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問題時(shí)，通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，主 機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)則從該緩沖區(qū)中取出數(shù)據(jù)打印，先放入打印緩沖區(qū)的數(shù)據(jù)先被打印。該緩沖區(qū)應(yīng)該是一個(gè)B 結(jié)構(gòu)。A.堆棧B.隊(duì)列C.數(shù)組D.線性表16 .若用一個(gè)大小為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前 rear和front的值分別為0和3。當(dāng) 從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為 B。A. 1 和 5B. 2 和 4C. 4 和 2D. 5 和 117 .設(shè)棧的輸入序列為1,2 , ,10 ,輸出序列為a1,a2,a10,若a

16、5=10,則a7為C。A. 4B. 8C.不確定D.718 .設(shè)棧的輸入序列是1,2,3,4 ,則 D不可能是其出棧序列。A. 1243B.2134C.1432D.431219.以下 D是C語(yǔ)言中" abcd321ABCD的子串。A. abcdB. 321ABC. "abcABCD.“21AB20.右用S= software ,其子串的數(shù)目是A. 8B. 37C。C. 36D.921.將一個(gè) A1:100,1:100 的三對(duì)角矩陣,A66,65(即該元素的下標(biāo))在B數(shù)組中位置A.198B.195按行優(yōu)先存入一維數(shù)組k 為 B。C. 197D.B1:29819622.設(shè)高為h

17、的二叉樹只有度為 0和2的結(jié)點(diǎn)，則此類二叉樹的結(jié)點(diǎn)數(shù)至少為B至多為 F 。高為h的完全二叉樹的結(jié)點(diǎn)數(shù)至少為 E ,至多為 FA. 2hB. 2h-1C. 2h+1D.h+1E. 2 h-1F. 2 h-1G. 2 h+1-1H. 2 h+123 .一棵有124個(gè)葉結(jié)點(diǎn)的完全二叉樹，最多有 B 個(gè)結(jié)點(diǎn)。A. 247B.248C.249D. 25124 .若從二叉樹的任一結(jié)點(diǎn)出發(fā)到根的路徑上所經(jīng)過的結(jié)點(diǎn)序列按其關(guān)鍵字有序，則該二叉樹是 C。A.滿二叉樹B.哈夫曼樹C.堆D.二叉查找樹25 .前序遍歷和中序遍歷結(jié)果相同的二叉樹為F;前序遍歷和后序遍歷結(jié)果相同的二叉樹為B。A. 一般二叉樹B.只有根結(jié)

18、點(diǎn)的二叉樹C.根結(jié)點(diǎn)無左孩子的二叉樹D.根結(jié)點(diǎn)無右孩子的二叉樹E.所有結(jié)點(diǎn)只有左孩子的二叉樹F.所有結(jié)點(diǎn)只有右孩子的二叉樹26 .具有n個(gè)結(jié)點(diǎn)的完全二叉樹，已經(jīng)順序存儲(chǔ)在一維數(shù)組A1.n中，下面的算法是將A中順序存儲(chǔ)變?yōu)槎骀湵泶鎯?chǔ)的完全二叉樹。請(qǐng)?zhí)顚戇m當(dāng)語(yǔ)句在下面的空格內(nèi)，完成上述算法。#define MAXSIZE 30typedef struct btnodeint data;struct btnode *lchild, *rchild;BTN;void createtree(BTN *p,int A, int I,int n)；p->data=AI; if( (2)；elsep-

19、>lchild=NULL; if( (4) createtree( (5);elsep->rchild=NULL;void btree(BTN * p ,int A,int n) createtree(p,A,1,n);參考答案：(1) p=(BTN *)malloc(sizeof(BTN)(2) 2*I<=n(3) createtree(p->lchild,A,2*I,n)(4) 2*I+1<=n(5) p->rchild,A,2*I+1,n27 .若在線性表中采用折半查找法查找元素，該線性表應(yīng)該C。A.元素按值有序B.采用順序存儲(chǔ)結(jié)構(gòu)C.元素按值有序，且

20、采用順序存儲(chǔ)結(jié)構(gòu)D.元素按值有序，且采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)28 .在分塊檢索中，對(duì) 256個(gè)元素的線性表分成 6 塊最好，每塊的最佳長(zhǎng)度是16;若每塊的長(zhǎng)度為 8,其平均檢索長(zhǎng)度為21。29 .假定有K個(gè)關(guān)鍵字互為同義詞，若用線性探測(cè)法把這K個(gè)關(guān)鍵字存入散列表中，至少要進(jìn)行 D 次探測(cè)。A. K-1 次B. K 次C. K+1 次D. K(K+1)/2 次30 .在n個(gè)記錄的有序順序表中進(jìn)行折半查找，最大的比較次數(shù)是Jog2 n +1。31 .Hash技術(shù)廣泛應(yīng)用于查找過程，選擇 Hash函數(shù)的標(biāo)準(zhǔn)是 和 處理沖突的技術(shù)有優(yōu)有劣，其共同標(biāo)準(zhǔn)是 。32 .在下述排序算法中，所需輔助存儲(chǔ)空間最多的是B,

21、所需輔助存儲(chǔ)空間最小的是 C,平均速度最快的是A。A.快速排序B.歸并排序C.堆排序33 .在文件局部有序或文件長(zhǎng)度較小的情況下，最佳內(nèi)部排序的方法是A。A.直接插入排序B.冒泡排序C.簡(jiǎn)單選擇排序34 .快速排序在最壞情況下時(shí)間復(fù)雜度是O(n2),比 A 的性能差。A.堆排序B.冒泡排序C.簡(jiǎn)單選擇排序35 .若需在O(nlogn)的時(shí)間內(nèi)完成對(duì)數(shù)組的排序，且要求排序是穩(wěn)定的，則可選擇的排序方 法是 C。A.快速排序B.堆排序C.歸并排序D.希爾排序36 .如果只想得到1000個(gè)元素組成的序列中第5個(gè)最小元素之前的部分排序的序列，用B 方法最快oA.冒泡排序B.快速排序C.希爾排序D.堆排序

22、E.簡(jiǎn)單選擇排序37 .以下結(jié)點(diǎn)序列是堆的為A。A. 100,90,80,60,85,75,20,25,10,70,65,50B. 100,70,50,20,90,75,60,25,10,85,65,8038 .若要盡可能快地完成對(duì)實(shí)數(shù)數(shù)組的排序，且要求排序是穩(wěn)定的，則應(yīng)選CA.快速排序B.堆排序C.歸并排序D.希爾排序39 .從未排序序列中依次取出一個(gè)元素與已排序序列中的元素依次進(jìn)行比較，然后將其放在已排序序列的合適位置，該排序方法稱為 A 排序法。A.插入排序B.交換排序C.選擇排序D.歸并排序40 .直接插入排序在最好情況下的時(shí)間復(fù)雜度為B。A. O(logn)B. O(n)C. O(n

23、logn)D. O(n 2)41.下面函數(shù)是將任意序列調(diào)整為最大堆的算法，請(qǐng)將空白部分填上：將任意序列調(diào)整為最大堆通過不斷調(diào)用adjust函數(shù)，即for(i=n/2;i>0;i-) adjust(list, i, n);其中l(wèi)ist為待調(diào)整序列所在數(shù)組(從下標(biāo)1開始)，n為序列元素的個(gè)數(shù)。void adjust(int list, int root, int n)/*將以root為下標(biāo)的對(duì)應(yīng)元素作為待調(diào)整堆的根，待調(diào)整元素放在list數(shù)組中，最大元素下標(biāo)為n*/int child,rootkey;rootkey =;child = 2*root;while(child < n)if

24、(child<n) && (listchild<listchild+1)(2)；if(rootkey > listchild)break;elselist (3) =listchild;(4);list (5) =rootkey;參考答案：(1) listroot(2) child+; child/2(4) child *= 2; child/241 .表是一種數(shù)據(jù)結(jié)構(gòu)，鏈表是一種(1)。隊(duì)列和棧都是線性表，棧的操作特性是 (2),隊(duì)列的操作特性是(3)。今有一空棧 S,對(duì)下列待進(jìn)棧的數(shù)據(jù)元素序列a,b,c,d,e,f依次進(jìn)棧、進(jìn)棧、出棧、進(jìn)棧、進(jìn)棧、出棧的操

25、作，則此操作完成后，棧S的棧頂元素為 (4),棧底元素為(5)。供選答案：(1):A.非順序存儲(chǔ)線性表B.D.非順序存儲(chǔ)非線性表 順序存儲(chǔ)非線性表C.順序存儲(chǔ)線性表(2)：A.隨機(jī)進(jìn)出B.先進(jìn)后出C.先進(jìn)先出D.出優(yōu)于進(jìn)(3)：A.隨機(jī)進(jìn)出B.先進(jìn)后出C.后進(jìn)后出D.進(jìn)優(yōu)于出(4)：A.fB.cC.aD.b(5)：A.bB.c答案：C. aABCBCD.d42 .操作系統(tǒng)主要是對(duì)計(jì)算機(jī)系統(tǒng)全部(1)進(jìn)行管理，以方便用戶、提高計(jì)算機(jī)使用效率的一種系統(tǒng)軟件。它的主要功能有：處理機(jī)管理、存儲(chǔ)管理、文件管理、'理和設(shè)備管理等。 Windows和Unix是最常用的兩類操作系統(tǒng)。前者是一個(gè)具有圖形

26、界面的 窗口式的 系統(tǒng)軟件，后者是一個(gè)基本上采用(4)語(yǔ)言編制而成的的系統(tǒng)軟件。在 (5)操作系統(tǒng)控制下，計(jì)算機(jī)能及時(shí)處理由過程控制反饋的信息 并作出響應(yīng)。 供選答案： (1):A.應(yīng)用軟件B.系統(tǒng)軟硬件C.資源D.設(shè)備(2)：A.數(shù)據(jù)B.作業(yè)C.中斷D.I/O(3)：A.分時(shí)B.多任務(wù)C.多用戶D.實(shí)時(shí)(4)：A.PASCALB.宏C.匯編D.C(5)：A.網(wǎng)絡(luò)B.分時(shí)C.批處理D.實(shí)時(shí)答案：CBBDD43 .本程序從鍵盤讀入整數(shù)，并按從大到小的順序輸出輸入整數(shù)中互不相等的那些整數(shù)。程序一邊讀入整數(shù)，一邊構(gòu)造一個(gè)從大到小順序鏈接的鏈表，直至不能從鍵盤讀入整數(shù)，然后順序輸出鏈表上各表元的整數(shù)值

27、。主函數(shù)每讀入一個(gè)整數(shù)，就調(diào)用函數(shù)insert(),函數(shù)insert() 將還未出現(xiàn)在鏈表上的整數(shù)按從大到小的順序插入到鏈表中。為了插入方便，鏈表在表首有一個(gè)輔助表元。閱讀下列C代碼，在 (n)處填入相應(yīng)的字句以完成上述功能。#include <stdio.h> #include <malloc.h>#define NULL 0typedef struct nodeint val;struct node *next;NODE;void insert(NODE *list,int x)NODE *u, *v, *p;u = list; v = u->next;/*尋

28、找插入位置*/*判斷是否要插入表元*/*生成新表元*/插入新表元*/while( (1)&& x < v->val)u=v;v=u->next;if(v=NULL |(2)p = (NODE *)malloc(sizeof(NODE); p->val = x;=v； (4)= p； /* main()int x;NODE *head, *p;/*首先建立只有輔助表元的空鏈表 */head = (NODE *)malloc(sizeof(NODE);(5) =NULL;printf(Enter Integers:n);while(scanf( "

29、%d ,&x) = 1)/*反復(fù)讀入整數(shù)插入鏈表 */insert(head,x);for(p=head->next;p!=NULL;p=p->next)/* 輸出鏈表 */printf( "%dt" ,p->val);printf( "n ");答案： v != NULL 或 v(2) x > v->val 或 x != v->val(3) p->next(4) u->next(5) head->next44 .計(jì)算機(jī)數(shù)據(jù)處理的對(duì)象是具有不同結(jié)構(gòu)的各種數(shù)據(jù)，可以訪問的最小數(shù)據(jù)信息單位是(1)

30、,可以引用的最小命名數(shù)據(jù)單位是(2)。線性表是最簡(jiǎn)單的一種數(shù)據(jù)結(jié)構(gòu)，有順序和鏈接兩種存儲(chǔ)方式。線性表按鏈接方式存儲(chǔ)時(shí)，每個(gè)結(jié)點(diǎn)的包括(3)兩部分。線性表的查找有(4)和 (5)兩種，但 (5)只能用于順序存儲(chǔ)的情況。供選答案：A.數(shù)字B.字符C.數(shù)據(jù)兀素D.數(shù)據(jù)項(xiàng)(2)：A.結(jié)點(diǎn)B.記錄C.數(shù)據(jù)兀素D.數(shù)據(jù)項(xiàng)(3)：A.數(shù)據(jù)值與符號(hào)B.數(shù)據(jù)與指針C.數(shù)據(jù)與表名D.頭地址與尾地址(4)：A.隨機(jī)查找B.順序查找C.二分法查找D.瀏覽(5)：A.隨機(jī)查找B.順序查找C.二分法查找D.瀏覽答案：CDBBC45 .本程序用于從鏈盤讀入整數(shù)，插入到鏈表，或從鏈表刪除一個(gè)整數(shù)。閱讀下面的C代碼，將應(yīng)填入(

31、n)處的字名寫在答卷的對(duì)應(yīng)欄內(nèi)。#include <stdio.h>#include <malloc.h>typedef struct node int val;struct node * next;NODE;NODE * ins(NODE *list, int x)/*將x按從小到大的次序插入鏈表*/NODE *u, *v=list, *p;for(; v != NULL && x < v->val ; v = v->next);/*尋找插入位置 */if(v != NULL && x = v->val) ret

32、urn(list);/* 已有，被忽略 */p = (NODE *)malloc(sizeof(NODE);p->val=x; /*生成新表元 */if(v = list) list = p; else；(2)； return list;NODE * del(NODE * list, int x) /*從鏈表中刪除值為x的表元*/NODE *u, *v;for(v = list; v != NULL && x < v->valu; u=v;v=v->next);if(v != NULL && x = v->val)/* 找到值為 x

33、 的表元 */if(v = list)list = list->next;else(3);；/*釋放空間*/ else printf( "沒有找到!n ");return(list); main()int x,ans;NODE * list=NULL, *p; while(1)printf( "n輸入1：將整數(shù)插入到鏈表。n輸入2：從鏈表刪除一個(gè)整數(shù)。n ”)； printf("其它整數(shù)，結(jié)束程序。nt請(qǐng)輸入選擇！”);scanf(%d,&ans);if( (5) return;printf("輸入整數(shù)：");scanf

34、("%d ,&x);if(ans=1)list=ins(list,x);elselist=del(list,x);for(p=list;p!=NULL;p=p->next)printf("%4d'，p->val);答案：(1) u->next = p;(2) p->next = v(3) u->next = v->next(4) free(v)(5) ans != 1 && ans != 246 .從未排序的序列中，依次取出元素，與已排序序列的元素比較后，放入已排序序列中的恰當(dāng)位置上，這是 (1)排序。從未

35、排序的序列中，挑選出元素，放在已排序序列 的某一端位置，這是 排序。逐次將待排序的序列中的相鄰元素兩兩比較，凡是逆序則進(jìn)行交換，這是 (3)排序。如果整個(gè)排序過程都在內(nèi)存中進(jìn)行，稱為(4)排序。排序算法的復(fù)雜性與排序算法的(5)有關(guān)。供選答案：(1):A.選擇B.插入C.比較D.歸并(2):A.選擇B.插入C.比較D.歸并(3):A.冒泡B.交換C.比較D.散列(4):A.外部B.內(nèi)部C.外存D.內(nèi)仔(5):A.運(yùn)算量大小與占用存儲(chǔ)多少B.運(yùn)算量大小與處理的數(shù)據(jù)量大小C.并行處理能力和占用存儲(chǔ)多少D.占用存儲(chǔ)多少和處理的數(shù)據(jù)量大小答案：BAABA47 .操作系統(tǒng)是對(duì)計(jì)算機(jī)資源進(jìn)行的(1)系統(tǒng)軟

36、件，是 (2)的接口。在處理機(jī)管理中， 進(jìn)程是一個(gè)重要的概念，它由程序塊、(3)和數(shù)據(jù)塊三部分組成，它有3種基本狀態(tài)，不可能發(fā)生的狀態(tài)轉(zhuǎn)換是(4)。虛擬存儲(chǔ)器的作用是允許程序直接訪問比內(nèi)存更大的地址空間，它通常使用作為它的一個(gè)主要組成部分。供選答案：(1):A.C.輸入和輸出 管理和控制B.D.鍵盤操作匯編和執(zhí)行(2):A.軟件和硬件B.主機(jī)和外設(shè)C.Wj級(jí)語(yǔ)百和機(jī)器語(yǔ)百D.用戶和計(jì)算機(jī)(3):A.進(jìn)程控制塊B.作業(yè)控制塊C.文件控制塊D.設(shè)備控制塊(4):A.運(yùn)行態(tài)轉(zhuǎn)換為就緒態(tài)B.就緒態(tài)轉(zhuǎn)換為運(yùn)行態(tài)C.運(yùn)行態(tài)轉(zhuǎn)換為等待態(tài)D.等待態(tài)轉(zhuǎn)換為運(yùn)行態(tài)(5):A.軟盤B.硬盤C.CDROMD.寄存器答

37、案：CDADB48. A 是信息的載體，它能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理。A.數(shù)據(jù)B.數(shù)據(jù)元素C.結(jié)點(diǎn)D.數(shù)據(jù)項(xiàng)49.下列程序段的時(shí)間復(fù)雜度為 C。for(i=1;i<n;i+)y=y+i;for(j=0;j<=(2*n);j+)x+;供選答案：A. O(n-1)B. O(2n)C. O(n 2)D. O(2n+1)50 .下面程序段的時(shí)間復(fù)雜度為 D。i=1;while(i<=n) i=i*2;供選答案:A. O(1)B. O(n)C. O(n2)D. O(log 2n)51 .下面程序段的時(shí)間復(fù)雜度為B。a=0;b=1;for(i=2;i<=n;i+)s=a+b;

38、b=a;a=s;供選答案：D. O(n 2)A 以及它們之D.數(shù)據(jù)映象A. O(1)B. O(n)C. O(log 2n)52 .數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中，計(jì)算機(jī)的 間的關(guān)系和運(yùn)算等的學(xué)科。A.操作對(duì)象B.計(jì)算方法C.邏輯存儲(chǔ)53 .在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成CA.動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)D.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)B.正確性和簡(jiǎn)明性D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性C.線性結(jié)構(gòu)和非線性結(jié)構(gòu)54 .算法分析的目的是C 。A.找出數(shù)據(jù)結(jié)構(gòu)的合理性B.研究算法中輸入和輸出的關(guān)系C.分析算法的效率以求改進(jìn)D.分析算法的易懂性和文檔性55 .算法分析的兩個(gè)主要方面

39、是 (4)A.間復(fù)雜性和時(shí)間復(fù)雜性C.可讀性和文檔性56 .一個(gè)線性順序表第一個(gè)元素的存儲(chǔ)地址是100,每個(gè)元素的長(zhǎng)度為 2,則第5個(gè)元素的地址為_BA. 110B.108C.100D.12057 .若已知一個(gè)棧的入棧序列是1,2,3, , ,n ,其輸出序列為 P1,P2,P3, , ,Pn,若P1=n,則P為 C。A. iB. n-iC. n-i+1D.不確定58 .對(duì)于一個(gè)棧，乂出輸入項(xiàng)A,B,C。如果輸入項(xiàng)序列由A,B,C所組成，則不可能產(chǎn)生的輸出序列是 A。A. CABB. CBAC. ABCD. ACB59 .設(shè)有如下的單鏈表的按序號(hào)查找的算法，其時(shí)間復(fù)雜度為B。LinkNode

40、*GetNode(Linklist head, int i)int j;ListNode *p;P = head; j=0;while(p->next && j<i)p = p->next; j+;if(i=j)return(p);elsereturn(NULL);供選答案:A. O(n 2)B. O(2n)C. O(n 3)60 .二維數(shù)組Am故行序?yàn)橹黜樞虼娣旁趦?nèi)存中，每個(gè)數(shù)組元素占D. O(logn)個(gè)存儲(chǔ)單元，則元素aj的地址計(jì)算公式是A. LOC(a ij) = LOC(a B. LOC(a ij) = LOC(a C. LOC(a ij) = LO

41、C(a D. LOC(a ij) = LOC(aii)+(i-1)*m+(j-1)ii)+(j-1)*m+(i-1)ii)+(i-1)*n+(j-1)ii)+(j-1)*n+(i-1)61 .以下哪一個(gè)不是隊(duì)列的基本運(yùn)算A.從隊(duì)尾插入一個(gè)新元素C.判斷一個(gè)隊(duì)列是否為空OB.從隊(duì)列中刪除第iD.讀取隊(duì)頭元素的值個(gè)元素62 .在一個(gè)長(zhǎng)度為n的順序表中，向第i個(gè)元素之前插入一個(gè)新元素, 元素。需向后移動(dòng)BA. n-iB. n-i+163 .從一個(gè)長(zhǎng)度為n的順序表中刪除第A. n-iB. n-i+1C. n-i-1i個(gè)兀素時(shí)，需向前移動(dòng)C. n-i-1D. i個(gè)元素。D. i64.在具有n個(gè)單元的順序

42、存儲(chǔ)的循環(huán)隊(duì)列中,假定front和rear分別為隊(duì)首指針和隊(duì)尾指針，則判斷隊(duì)空的條件是A. front=rear+165.從一個(gè)具有 均比較 DA. nB. front=rearn個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于C. front+1=rearx的結(jié)點(diǎn)時(shí),D. front=0在查找成功的情況下，需平個(gè)結(jié)點(diǎn)。B. n/266 . 一個(gè)棧的入棧序列是 a,b,c,d,eA. edcbaB. decbaC. (n-1)/2,則棧不可能的輸出序列是C.dceabD. (n+1)/2D. abcde67 .棧結(jié)構(gòu)通常采用的兩種存儲(chǔ)結(jié)構(gòu)是A.順序存儲(chǔ)結(jié)構(gòu)和鏈表存儲(chǔ)結(jié)構(gòu)C.鏈表存儲(chǔ)結(jié)構(gòu)和數(shù)組68 .判斷一個(gè)順序棧

43、ST (最多元素為B.散列方式和索引方式D.線性存儲(chǔ)結(jié)構(gòu)和非線性存儲(chǔ)結(jié)構(gòu)A. ST->top<>0B. ST->top=0m。為空的條件是 BC. st->top<>moD. st->top=moA. head=NILL69 .不帶頭結(jié)點(diǎn)的單鏈表head為空表的判定條件是B. head->next=NULL C. head->next=head D. head != NULL70 .在一個(gè)單鏈表中，已知 q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在 p和q之間才1入s結(jié)點(diǎn)，則應(yīng)執(zhí)行CA. s->next = p->next; p

44、->next=s;B. p->next = s->next; s->next=p;C. q->next = s; s->next=p;D. p->next = s; s->next=q;71 .假設(shè)雙向鏈表結(jié)點(diǎn)的類型如下:typedef struct Linknodeint data;struct Linknode *lLink;struct Linknode *rLink;/*前驅(qū)結(jié)點(diǎn)指針*/*后繼結(jié)點(diǎn)指針*/下面給出的算法是要把一個(gè)q所指新結(jié)點(diǎn)，作為非空雙向鏈表中的p所指的結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn)插入到該雙向鏈表中，能正確完成要求的算法段是C。A. q-

45、>rLink=p; q->lLink=p->lLink; p->lLink=q; p->lLink->rLink=q;B. p->lLink=q, q->rLink=p; p->lLink->rLink=q; q->lLink=p->lLink;C. q->lLink=p->lLink; q->rLink=p;p->lLink->rLink=q;p->lLink=q;D.以上均不對(duì)72 .串是一種特殊的線性表，其特殊性體現(xiàn)在 BA.可以順序存儲(chǔ)B.數(shù)據(jù)元素是一個(gè)字符C.可以鏈接存儲(chǔ)D.數(shù)

46、據(jù)元素可以是多個(gè)字符73 .設(shè)有兩個(gè)串p和q,求q在p中首次出現(xiàn)的位置的運(yùn)算稱作BA.連接B.模式匹配C.求子串D.求串長(zhǎng)74 .設(shè)串 s1 = " ABCDEFG, s2=" PQRST ,函數(shù) con(x,y)返回 x和 y 串的連接串，subs(s,I,j)len(s)返回串s的長(zhǎng)度，則的結(jié)果是 D返回串s的從序號(hào)i的字符開始的j個(gè)字符組成的子串,con(sub(s1,2,len(s2),sub(s1,len(s2),2)A. BCDEFB. BCDEFGC. BCPQRSTD. BCDEFEF75 .常對(duì)數(shù)組進(jìn)行的兩種基本操作是C。A.建立和刪除B.索引和修改 C.

47、查找和修改D.索引和查找76 .稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即C 。A.二維數(shù)組和三維數(shù)組B.三元組和散列C.三元組和十字鏈表D.散列和十字鏈表77 .對(duì)下圖所示的二叉表，按先根次序遍歷得到的結(jié)點(diǎn)序列為BD. HIDBEFGACA. ABCDHEIFGB. ABDHIECFGC. HDIBRAFCG78 .在一棵二叉樹上，度為 0的結(jié)點(diǎn)個(gè)數(shù)為n0,度為2的結(jié)點(diǎn)數(shù)為n2,則n0= A。A. n 2+1B. n 2-1C. n 2D. n 2/279 .某二叉樹前序遍歷結(jié)點(diǎn)的訪問順序是ABCDEFG中序遍歷結(jié)點(diǎn)的訪問順序是CBDAFGE則其后序遍歷結(jié)點(diǎn)的訪問順序是A。B. CDGFEABD.

48、 CDBFAGEA. CDBGFEAC. CDBAGFE80 .在下列存儲(chǔ)形式中，D 不是樹的存儲(chǔ)形式。A.雙親表示法B.孩子鏈表表示法C.孩子兄弟表示法D.順序存儲(chǔ)表示法81 .已知一棵二叉樹的中序序列為cbedahgijf ,后序序列為cedbhjigfa ,則該二叉樹為B。82.已知一棵權(quán)集 W=2,3,4,7,8,9A.20B.40的哈夫曼樹，其加權(quán)路徑長(zhǎng)度WPL為C. 80D.16083 .已知一棵度為 m的樹中有m個(gè)度為1的結(jié)點(diǎn)，n2個(gè)度為2的結(jié)點(diǎn)，nm個(gè)度為m的結(jié)點(diǎn)，問這棵樹中葉子結(jié)點(diǎn)為 C。A. 1+n i(I-1)B. 1+n i (I+1) C. n 1+n?+, +nmD

49、. m nm84 .如下圖所示的4棵二叉樹中， C不是完全二叉樹。85 .設(shè)高度為h的二叉樹上只有度為 0或度為2的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至 少為 B。A. 2hB. 2h-1C.2h+1D. h+1A.abcdgef86 .如下圖所示的二叉樹的中序遍歷序列是CB. dfebagc C. dbaefcgD. defbagc87.已知某二叉樹的后序遍歷序列是dabec,中序遍歷序列是 debac,則其前序遍歷序列為DA. acbedB. decabC. deabcD. cedba88 .如果T2是由有序樹T轉(zhuǎn)換而來的二叉樹，則T中結(jié)點(diǎn)的前序就是 T2中結(jié)點(diǎn)的A ，A.前序B.中序C.

50、后序D.層次序89 .樹的基本遍歷策略可分為先根遍歷和后根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。這里，我們把由樹轉(zhuǎn)化得到的二叉樹叫做這棵樹對(duì)應(yīng)的二叉樹。下面結(jié)論正確的是A。A.樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的先序遍歷序列相同B.樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的后序遍歷序列相同C.樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的中序遍歷序列相同D.以上均不對(duì)90 .深度為5的二叉樹至多有C個(gè)結(jié)點(diǎn)。A. 16B. 32C. 31D. 1091 .在一非空二叉樹的中序遍序序列中，根結(jié)點(diǎn)的右邊A。A.只有右子樹的所有結(jié)點(diǎn)B.只有右子樹的部分C.只有左子樹的部分結(jié)點(diǎn)D.只有左子樹的所有結(jié)點(diǎn)

51、92.樹取適合用來表小C。A.有序數(shù)據(jù)兀素B.無序數(shù)據(jù)元素C.兀素之間具有分支層次關(guān)系的數(shù)據(jù)D.兀素之間無聯(lián)系的數(shù)據(jù)93.設(shè)n, m為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，n在m前的條件是CA. n 在m的右方B. n 是m的祖先C. n在m的左方D. n 是m的子孫94.對(duì)一個(gè)滿二叉樹，m個(gè)樹葉，n個(gè)結(jié)點(diǎn)，深度為h,貝U D。A. n=h+mB.h+m=2nC. m=h-1D. n=2 h-195.如果某二叉樹的前序?yàn)閟tuwv ,中序?yàn)閡wtvs ,則該二叉樹后序?yàn)?C。A. uwvtsB. vwutsC. wuvtsD. wutsv96 .設(shè)待排序的記錄為(20,16,13,14,19)

52、,經(jīng)過下列過程將這些記錄排序。20,16,13,14,1916,20,13,14,1913,16,20,14,1913,14,16,20,1913,14,16,19,20所用的排序方法是_A。A.直接插入排序B.冒泡排序C.希爾排序D.堆排序97 .對(duì)下列4個(gè)序列用快速排序的方法進(jìn)行排序，以序列的第一個(gè)元素為基礎(chǔ)進(jìn)行劃分，在 第一趟劃分過程中，元素移動(dòng)次數(shù)最多的是 序列。A. 70,75,82,90,23,16,10,68B. 70,75,68,23,10,16,90,82C. 82,75,70,16,10,90,68,23D. 23,10,16,70,82,75,68,9098 .用快速排序

53、的方法對(duì)包含幾個(gè)關(guān)鍵字的序列進(jìn)行排序，最壞情況下，執(zhí)行的時(shí)間為 D。A. O(n)B. O(log 2n)C.O(nlog 2n)D. O(n 2)99 .在所有排序方法中，關(guān)鍵碼(即關(guān)鍵字)比較的次數(shù)與記錄的初始排列次序無關(guān)的是 D。A.希爾排序B.冒泡排序C.直接插入排序D.直接選擇排序100 .在歸并排序過程中，需歸并的趟數(shù)為C 。A. nB. nC. |lnlog2nD.log 2 n101 .一組記錄的排序代碼為46,79,56,38,40,84,則利用堆排序的方法建立的初始堆為 B。A. 79,46,56,38,40,80B. 84,79,56,38,40,46C. 84,79,56,46,40,38D. 84,56,79,40,46,38102 .一組記錄的排序代碼為46,79,56,38,40,84,則利用快速排序的方法，以第一個(gè)記錄 為基準(zhǔn)得到的一次劃分結(jié)果為C 。A. 38,40,46,56,79,84B. 40,38,46,79,56,84C. 40,38,46,56,79,84D. 40,38,46,84,56,79103 .每次把待排序的區(qū)間劃分為左、右兩個(gè)子區(qū)間，其中左區(qū)間中元素的排序碼均