《計(jì)算機(jī)軟件技術(shù)基礎(chǔ)》試題及答案.doc
《《計(jì)算機(jī)軟件技術(shù)基礎(chǔ)》試題及答案.doc》由會(huì)員分享,可在線閱讀,更多相關(guān)《《計(jì)算機(jī)軟件技術(shù)基礎(chǔ)》試題及答案.doc(37頁(yè)珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
計(jì)算機(jī)軟件技術(shù)基礎(chǔ)試題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è) C 的有限序列。A. 表元素B. 字符C. 數(shù)據(jù)元素D. 數(shù)據(jù)項(xiàng)E. 信息項(xiàng)3.若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu),在其第I個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為 C 。(1In+1)A. O(0)B. O(1)C. O(n)D. O(n2)4.設(shè)A是一個(gè)線性表(a1,a2,an),采用順序存儲(chǔ)結(jié)構(gòu),則在等概率的前提下,平均每插入一個(gè)元素需要移動(dòng)的元素個(gè)數(shù)為 B ,平均每刪除一個(gè)元素需要移動(dòng)的元素個(gè)數(shù)為 A ;若元素插在ai與ai+1之間(0In-1)的概率為,則平均每插入一個(gè)元素所要移動(dòng)的元素個(gè)數(shù)為 C ;A. B. C. D. 5.下列函數(shù)中,按它們?cè)跁r(shí)的無(wú)窮大階數(shù),最大的是 D 。A. lognB. nlognC. 2n/2D. n!spnextnextnext6.將下圖所示的s所指結(jié)點(diǎn)加到p所指的結(jié)點(diǎn)之后,其語(yǔ)句應(yīng)為: D 。A. s-next=p+1; p-next=s;B. (*p).next=s; (*s).next=(*p).next;C. s-next=p-next; p-next=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è)無(wú)頭結(jié)點(diǎn)鏈表(ha和 hb)為一個(gè)無(wú)頭結(jié)點(diǎn)鏈表ha的過程,作為參數(shù)的兩個(gè)鏈表都是按結(jié)點(diǎn)的data域由大到小鏈接的。合并后新鏈表的結(jié)點(diǎn)仍按此方式鏈接。請(qǐng)?zhí)顚懴率隹湛?,使程序能正確運(yùn)行。#define NULL 0typedef struct nodeint data;struct node *next;node, linklisttype;void combine(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 = (2) ; (3) ;elsep-next = (4) ;p = (5) ; (6) ;if(ha=NULL) (7) ;if(hb=NULL) (8) ;ha = h-next;free(h);參考答案:(1) ha(2) p-next(3) ha=ha-next(4) hb(5) p-next(6) hb=hb-next(7) p-next=hb(8) p-next=ha9.如果表A中所有元素(a1,a2,an)與表B的一個(gè)順序子表(bk,bk+1,bk+n-1)完全相同(即a1=bk,a2=bk+1,an=bk+n-1),則稱表A包含在表B中。設(shè)ha,hb為帶頭結(jié)點(diǎn)的單鏈表,分別表示有序表A和B,下面的函數(shù)用于判別表A是否包含在表B中,若是,則返回true,否則返回false。(提示:用遞歸實(shí)現(xiàn))#define true 1#define false 0#define NULL 0typedef struct nodeint data;struct node *next;node, linklisttype;int inclusion(linklisttype *ha, linklisttype *hb)linklisttype *pa, *pb;pa = ha-next;pb = hb-next; (1) ;while( (2) )if(pa-data=pb-data) (3) ;else (4) ; (5) ;參考答案:(1) if(pa=NULL) return(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(n0)指明循環(huán)鏈表的結(jié)點(diǎn)個(gè)數(shù),參數(shù)I(1In)指明起始結(jié)點(diǎn),參數(shù)m(m0是步長(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 = NULL;if(n0)head = (linklisttype *)malloc(sizeof(linklisttype);p = head;for(I=1;Idata = I;q = (linklisttype *)malloc(sizeof(linklistttype); (1) ; (2) ;p-data = n; (3) ;/*建立從尾鏈到首的環(huán)形結(jié)構(gòu)*/return(head);void Josephus(int n, int j, int m)linklisttype *p, *q;int j;p = create_link_list(n);for(;I1;I-)p = p-next; (4) ;while(jn)for(I=1;Inext; (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=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 #define NULL 0typedef struct nodeint data;struct node *next;NODE;NODE *append(NODE *last, int x)last-next=(NODE *)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( (1) )if(A-data data)last=append(last,A-data);A=A-next;elseif( (2) )A=A-next;B=B-next;else (3) ;while( (4) )last=append(last,A-data);A=A-next; (5) ;last=C;C=C-next;free(last);return(C);參考答案:(1) A!=NULL & B!=NULL(2) A-data=B-data(3) B=B-next;(4) A!=NULL(5) last-next=NULL;12.閱讀以下算法,填充空格,使其成為完整的算法。其功能是在一個(gè)非遞減的順序存儲(chǔ)線性表中(從下標(biāo)1處開始存儲(chǔ)),刪除所有值相等的多余元素。#define MAXSIZE 30typedef structint elemMAXSIZE;int length;/*表長(zhǎng)*/sqlisttype;void exam21(sqlisttype *L)int I,j;I=2,j=1;while( (1) )if(L-elemIL-elemj) (2) ; (3) ;I+; (4) ;參考答案:(1) ilength(2) (3) j+;(4)13.用單鏈表表示的鏈?zhǔn)疥?duì)列的隊(duì)頭在鏈表的 A 位置。A. 鏈頭B. 鏈尾C. 鏈中14.若用單鏈表表示隊(duì)列,則應(yīng)該選用 B 。A. 帶尾指針的非循環(huán)鏈表B. 帶尾指針的循環(huán)鏈表C. 帶頭指針的非循環(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ù)組來(lái)實(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,若a5=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. “abcABC”D. “21AB”20.若串S=”software”,其子串的數(shù)目是 C 。A. 8B. 37C. 36D. 921.將一個(gè)A1:100,1:100的三對(duì)角矩陣,按行優(yōu)先存入一維數(shù)組B1:298中,A中元素A66,65(即該元素的下標(biāo))在B數(shù)組中位置k為 B 。A. 198B. 195C. 197D. 19622.設(shè)高為h的二叉樹只有度為0和2的結(jié)點(diǎn),則此類二叉樹的結(jié)點(diǎn)數(shù)至少為 B ,至多為 F 。高為h的完全二叉樹的結(jié)點(diǎn)數(shù)至少為 E ,至多為 F 。A 2hB. 2h-1C. 2h+1D.h+1E. 2h-1F. 2h-1G. 2h+1-1H. 2h+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é)點(diǎn)的二叉樹C. 根結(jié)點(diǎn)無(wú)左孩子的二叉樹D. 根結(jié)點(diǎn)無(wú)右孩子的二叉樹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) (1) ;p-data=AI;if( (2) ) (3) ;elsep-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*Ilchild,A,2*I,n)(4) 2*I+1rchild,A,2*I+1,n27.若在線性表中采用折半查找法查找元素,該線性表應(yīng)該 C 。A. 元素按值有序B. 采用順序存儲(chǔ)結(jié)構(gòu)C. 元素按值有序,且采用順序存儲(chǔ)結(jié)構(gòu)D. 元素按值有序,且采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)28.在分塊檢索中,對(duì)256個(gè)元素的線性表分成 16 塊最好,每塊的最佳長(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ù)是。31.Hash技術(shù)廣泛應(yīng)用于查找過程,選擇Hash函數(shù)的標(biāo)準(zhǔn)是 和 。處理沖突的技術(shù)有優(yōu)有劣,其共同標(biāo)準(zhǔn)是 。32.在下述排序算法中,所需輔助存儲(chǔ)空間最多的是 B ,所需輔助存儲(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 方法最快。A. 冒泡排序B. 快速排序C. 希爾排序D. 堆排序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)選 C 。A. 快速排序B. 堆排序C. 歸并排序D. 希爾排序39.從未排序序列中依次取出一個(gè)元素與已排序序列中的元素依次進(jìn)行比較,然后將其放在已排序序列的合適位置,該排序方法稱為 A 排序法。A. 插入排序B. 交換排序C. 選擇排序D. 歸并排序40.直接插入排序在最好情況下的時(shí)間復(fù)雜度為 B 。A. O(logn)B. O(n)C. O(nlogn)D. O(n2)41.下面函數(shù)是將任意序列調(diào)整為最大堆的算法,請(qǐng)將空白部分填上:將任意序列調(diào)整為最大堆通過不斷調(diào)用adjust函數(shù),即for(i=n/2;i0;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 = (1) ;child = 2*root;while(child n)if(childn) & (listchild listchild)break;elselist (3) =listchild; (4) ;list (5) =rootkey;參考答案:(1) listroot(2) child+;(3) child/2(4) child *= 2;(5) 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)棧、出棧的操作,則此操作完成后,棧S的棧頂元素為 (4) ,棧底元素為 (5) 。供選答案:(1):A. 非順序存儲(chǔ)線性表B. 非順序存儲(chǔ)非線性表C. 順序存儲(chǔ)線性表D. 順序存儲(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. cC. aD. d答案:ABCBC42.操作系統(tǒng)主要是對(duì)計(jì)算機(jī)系統(tǒng)全部 (1) 進(jìn)行管理,以方便用戶、提高計(jì)算機(jī)使用效率的一種系統(tǒng)軟件。它的主要功能有:處理機(jī)管理、存儲(chǔ)管理、文件管理、 (2) 管理和設(shè)備管理等。Windows和Unix是最常用的兩類操作系統(tǒng)。前者是一個(gè)具有圖形界面的窗口式的 (3) 系統(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ù)值。主函數(shù)每讀入一個(gè)整數(shù),就調(diào)用函數(shù)insert(),函數(shù)insert()將還未出現(xiàn)在鏈表上的整數(shù)按從大到小的順序插入到鏈表中。為了插入方便,鏈表在表首有一個(gè)輔助表元。閱讀下列C代碼,在 (n) 處填入相應(yīng)的字句以完成上述功能。#include #include #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;while( (1) & x val)/*尋找插入位置*/u=v;v=u-next;if(v=NULL | (2) )/*判斷是否要插入表元*/p = (NODE *)malloc(sizeof(NODE);p-val = x;/*生成新表元*/ (3) = v; (4) = p;/*插入新表元*/main()int x;NODE *head, *p;/*首先建立只有輔助表元的空鏈表*/head = (NODE *)malloc(sizeof(NODE); (5) =NULL;printf(“Enter Integers:n”);while(scanf(“%d”,&x) = 1)/*反復(fù)讀入整數(shù)插入鏈表*/insert(head,x);for(p=head-next;p!=NULL;p=p-next)/*輸出鏈表*/printf(“%dt”,p-val);printf(“n”);答案:(1) 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) ,可以引用的最小命名數(shù)據(jù)單位是 (2) 。線性表是最簡(jiǎn)單的一種數(shù)據(jù)結(jié)構(gòu),有順序和鏈接兩種存儲(chǔ)方式。線性表按鏈接方式存儲(chǔ)時(shí),每個(gè)結(jié)點(diǎn)的包括 (3) 兩部分。線性表的查找有 (4) 和 (5) 兩種,但 (5) 只能用于順序存儲(chǔ)的情況。供選答案:(1):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)填入 (n) 處的字名寫在答卷的對(duì)應(yīng)欄內(nèi)。#include #include typedef struct nodeint val;struct node * next;NODE;NODE * ins(NODE *list, int x)/*將x按從小到大的次序插入鏈表*/NODE *u, *v=list, *p;for(; v != NULL & x val ; v = v-next);/*尋找插入位置*/if(v != NULL & x = v-val) return(list); /*已有,被忽略*/p = (NODE *)malloc(sizeof(NODE);p-val=x; /*生成新表元*/if(v = list) list = p;else (1) ; (2) ;return list;NODE * del(NODE * list, int x)/*從鏈表中刪除值為x的表元*/NODE *u, *v;for(v = list; v != NULL & x valu; u=v;v=v-next);if(v != NULL & x = v-val)/*找到值為x的表元*/if(v = list)list = list-next;else (3) ; (4) ;/*釋放空間*/elseprintf(“沒有找到!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(“%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) 排序。從未排序的序列中,挑選出元素,放在已排序序列的某一端位置,這是 (2) 排序。逐次將待排序的序列中的相鄰元素兩兩比較,凡是逆序則進(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)軟件,是 (2) 的接口。在處理機(jī)管理中,進(jìn)程是一個(gè)重要的概念,它由程序塊、 (3) 和數(shù)據(jù)塊三部分組成,它有3種基本狀態(tài),不可能發(fā)生的狀態(tài)轉(zhuǎn)換是 (4) 。虛擬存儲(chǔ)器的作用是允許程序直接訪問比內(nèi)存更大的地址空間,它通常使用 (5) 作為它的一個(gè)主要組成部分。供選答案:(1):A. 輸入和輸出B. 鍵盤操作C. 管理和控制D. 匯編和執(zhí)行(2):A. 軟件和硬件B. 主機(jī)和外設(shè)C. 高級(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. 寄存器答案: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;in;i+)y=y+1;for(j=0;j=(2*n);j+)x+;供選答案:A. O(n-1)B. O(2n)C. O(n2)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(log2n)51.下面程序段的時(shí)間復(fù)雜度為 B 。a=0;b=1;for(i=2;inext & jnext;j+;if(i=j)return(p);elsereturn(NULL);供選答案:A. O(n2)B. O(2n)C. O(n3)D. O(logn)60.二維數(shù)組Amn按行序?yàn)橹黜樞虼娣旁趦?nèi)存中,每個(gè)數(shù)組元素占1個(gè)存儲(chǔ)單元,則元素aij的地址計(jì)算公式是 C 。A. LOC(aij) = LOC(a11)+(i-1)*m+(j-1)B. LOC(aij) = LOC(a11)+(j-1)*m+(i-1)C. LOC(aij) = LOC(a11)+(i-1)*n+(j-1)D. LOC(aij) = LOC(a11)+(j-1)*n+(i-1)61.以下哪一個(gè)不是隊(duì)列的基本運(yùn)算 C 。A. 從隊(duì)尾插入一個(gè)新元素B. 從隊(duì)列中刪除第i個(gè)元素C. 判斷一個(gè)隊(duì)列是否為空D. 讀取隊(duì)頭元素的值62.在一個(gè)長(zhǎng)度為n的順序表中,向第i個(gè)元素之前插入一個(gè)新元素,需向后移動(dòng) B 個(gè)元素。A. n-iB. n-i+1C. n-i-1D. i63.從一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素時(shí),需向前移動(dòng) A 個(gè)元素。A. n-iB. n-i+1C. n-i-1D. i64.在具有n個(gè)單元的順序存儲(chǔ)的循環(huán)隊(duì)列中,假定front和rear分別為隊(duì)首指針和隊(duì)尾指針,則判斷隊(duì)空的條件是 B 。A. front=rear+1B. front=rearC. front+1=rearD. front=065.從一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x的結(jié)點(diǎn)時(shí),在查找成功的情況下,需平均比較 D 個(gè)結(jié)點(diǎn)。A. nB. n/2C. (n-1)/2D. (n+1)/266.一個(gè)棧的入棧序列是a,b,c,d,e,則棧不可能的輸出序列是 C 。A. edcbaB. decbaC. dceabD. abcde67.棧結(jié)構(gòu)通常采用的兩種存儲(chǔ)結(jié)構(gòu)是 A 。A. 順序存儲(chǔ)結(jié)構(gòu)和鏈表存儲(chǔ)結(jié)構(gòu)B. 散列方式和索引方式C. 鏈表存儲(chǔ)結(jié)構(gòu)和數(shù)組D. 線性存儲(chǔ)結(jié)構(gòu)和非線性存儲(chǔ)結(jié)構(gòu)68.判斷一個(gè)順序棧ST(最多元素為mo)為空的條件是 B 。A. ST-top0B. ST-top=0C. st-topmoD. st-top=mo69.不帶頭結(jié)點(diǎn)的單鏈表head為空表的判定條件是 A 。A. head=NILLB. head-next=NULLC. head-next=headD. head != NULL70.在一個(gè)單鏈表中,已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn),若在p和q之間插入s結(jié)點(diǎn),則應(yīng)執(zhí)行 C 。A. s-next = p-next; p-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;/*前驅(qū)結(jié)點(diǎn)指針*/struct Linknode *rLink;/*后繼結(jié)點(diǎn)指針*/下面給出的算法是要把一個(gè)q所指新結(jié)點(diǎn),作為非空雙向鏈表中的p所指的結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn)插入到該雙向鏈表中,能正確完成要求的算法段是 C 。Aq-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)在 B 。A. 可以順序存儲(chǔ)B. 數(shù)據(jù)元素是一個(gè)字符C. 可以鏈接存儲(chǔ)D. 數(shù)據(jù)元素可以是多個(gè)字符73.設(shè)有兩個(gè)串p和q,求q在p中首次出現(xiàn)的位置的運(yùn)算稱作 B 。A. 連接B. 模式匹配C. 求子串D. 求串長(zhǎng)74.設(shè)串s1=”ABCDEFG”,s2=”PQRST”,函數(shù)con(x,y)返回x和y串的連接串,subs(s,I,j)返回串s的從序號(hào)i的字符開始的j個(gè)字符組成的子串,len(s)返回串s的長(zhǎng)度,則con(sub(s1,2,len(s2),sub(s1,len(s2),2)的結(jié)果是 D 。A. BCDEFB. BCDEFGC. BCPQRSTD. BCDEFEF75.常對(duì)數(shù)組進(jìn)行的兩種基本操作是 C 。A. 建立和刪除B. 索引和修改C. 查找和修改D. 索引和查找76.稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種,即 。A. 二維數(shù)組和三維數(shù)組B. 三元組和散列C. 三元組和十字鏈表D. 散列和十字鏈表77.對(duì)下圖所示的二叉表,按先根次序遍歷得到的結(jié)點(diǎn)序列為 B 。A. ABCDHEIFGB. ABDHIECFGC. HDIBRAFCGD. HIDBEFGAC78.在一棵二叉樹上,度為0的結(jié)點(diǎn)個(gè)數(shù)為n0,度為2的結(jié)點(diǎn)數(shù)為n2,則n0= A 。A. n2+1B. n2-1C. n2D. n2/279.某二叉樹前序遍歷結(jié)點(diǎn)的訪問順序是ABCDEFG,中序遍歷結(jié)點(diǎn)的訪問順序是CBDAFGE,則其后序遍歷結(jié)點(diǎn)的訪問順序是 A 。ACDBGFEAB. CDGFEABC. CDBAGFED. CDBFAGE80.在下列存儲(chǔ)形式中, D 不是樹的存儲(chǔ)形式。A. 雙親表示法B. 孩子鏈表表示法C. 孩子兄弟表示法D. 順序存儲(chǔ)表示法81. 已知一棵二叉樹的中序序列為cbedahgijf,后序序列為cedbhjigfa,則該二叉樹為 B 。82. 已知一棵權(quán)集W=2,3,4,7,8,9的哈夫曼樹,其加權(quán)路徑長(zhǎng)度WPL為 。A. 20B. 40C. 80D. 16083.已知一棵度為m的樹中有n1個(gè)度為1的結(jié)點(diǎn),n2個(gè)度為2的結(jié)點(diǎn),nm個(gè)度為m的結(jié)點(diǎn),問這棵樹中葉子結(jié)點(diǎn)為 。A. 1+ni(I-1)B. 1+ni(I+1)C. n1+n2+nmD. mnm84.如下圖所示的4棵二叉樹中, 不是完全二叉樹。85.設(shè)高度為h的二叉樹上只有度為0或度為2的結(jié)點(diǎn),則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為 B 。A. 2hB. 2h-1C. 2h+1D. h+186.如下圖所示的二叉樹的中序遍歷序列是 。A. abcdgefB. dfebagcC. dbaefcgD. defbagc87.已知某二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac,則其前序遍歷序列為 D 。A. acbedB. decabC. deabcD. cedba88.如果T2是由有序樹T轉(zhuǎn)換而來(lái)的二叉樹,則T中結(jié)點(diǎn)的前序就是T2中結(jié)點(diǎn)的 A 。A. 前序B. 中序C. 后序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的二叉樹至多有 個(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)92. 樹最適合用來(lái)表示 。A. 有序數(shù)據(jù)元素B. 無(wú)序數(shù)據(jù)元素C. 元素之間具有分支層次關(guān)系的數(shù)據(jù)D. 元素之間無(wú)聯(lián)系的數(shù)據(jù)93. 設(shè)n,m為一棵二叉樹上的兩個(gè)結(jié)點(diǎn),在中序遍歷時(shí),n在m前的條件是 C 。A. n在m的右方B. n是m的祖先C. n在m的左方D. n是m的子孫94.對(duì)一個(gè)滿二叉樹,m個(gè)樹葉,n個(gè)結(jié)點(diǎn),深度為h,則 D 。A. n=h+mB. h+m=2nC. m=h-1D. n=2h-195.如果某二叉樹的前序?yàn)閟tuwv,中序?yàn)閡wtvs,則該二叉樹后序?yàn)?。A. uwvtsB. vwutsC. wuvtsD. wutsv96.設(shè)待排序的記錄為(20,16,13,14,19),經(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 序列。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.用快速排序的方法對(duì)包含幾個(gè)關(guān)鍵字的序列進(jìn)行排序,最壞情況下,執(zhí)行的時(shí)間為 D 。A. O(n)B. O(log2n)C.O(nlog2n)D. O(n2)99.在所有排序方法中,關(guān)鍵碼(即關(guān)鍵字)比較的次數(shù)與記錄的初始排列次序無(wú)關(guān)的是 D 。A. 希爾排序B. 冒泡排序C. 直接插入排序D. 直接選擇排序100.在歸并排序過程中,需歸并的趟數(shù)為 。A. nB. C. D. 101.一組記錄的排序代碼為46,79,56,38,40,84,則利用堆排序的方法建立的初始堆為 B 。A. 79,46,- 1.請(qǐng)仔細(xì)閱讀文檔,確保文檔完整性,對(duì)于不預(yù)覽、不比對(duì)內(nèi)容而直接下載帶來(lái)的問題本站不予受理。
- 2.下載的文檔,不會(huì)出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請(qǐng)點(diǎn)此認(rèn)領(lǐng)!既往收益都?xì)w您。
下載文檔到電腦,查找使用更方便
32 積分
下載 |
- 配套講稿:
如PPT文件的首頁(yè)顯示word圖標(biāo),表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制:
部分文檔作品中含有的國(guó)旗、國(guó)徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計(jì)者僅對(duì)作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 計(jì)算機(jī)軟件技術(shù)基礎(chǔ) 計(jì)算機(jī) 軟件技術(shù) 基礎(chǔ) 試題 答案
鏈接地址:http://www.szxfmmzy.com/p-1545223.html