《《計(jì)算機(jī)軟件技術(shù)基礎(chǔ)》試題及答案.doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《《計(jì)算機(jī)軟件技術(shù)基礎(chǔ)》試題及答案.doc（37頁珍藏版）》請(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)簡單 B. 便于隨機(jī)存取 C. 便于插入和刪除 D. 便于利用零散的存儲(chǔ)器空間 2.線性表是具有n個(gè) C 的有限序列。 A. 表元素 B. 字符 C. 數(shù)據(jù)元素 D. 數(shù)據(jù)項(xiàng) E. 信息項(xiàng) 3.若長度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第I個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為 C 。（1≤I≤n+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之間(0≤I≤n-1)的概率為，則平均每插入一個(gè)元素所要移動(dòng)的元素個(gè)數(shù)為 C ； A. B. C. D. 5.下列函數(shù)中，按它們?cè)跁r(shí)的無窮大階數(shù)，最大的是 D 。 A. logn B. nlogn C. 2n/2 D. n! s p next next next 6.將下圖所示的s所指結(jié)點(diǎn)加到p所指的結(jié)點(diǎn)之后，其語句應(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. n B. 2n-1 C. n-1 D. 2n 8.下面的程序段是合并兩個(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 node{ int 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) ; } else{ p->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=ha 9.如果表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 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; (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(n>0)指明循環(huán)鏈表的結(jié)點(diǎn)個(gè)數(shù)，參數(shù)I(1≤I≤n)指明起始結(jié)點(diǎn)，參數(shù)m（m>0是步長），指明從起始結(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è)語句。 #define NULL 0 typedef struct node{ int data; struct node *next; }node, linklisttype; linklisttype *create_link_list(int n){ linklisttype *head, *p, *q; int I; head = NULL; 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)); (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(;I>1;I--) p = p->next; (4) ; while(jnext; (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->next 11.在下列程序中，函數(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 0 typedef struct node{ int 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 < B->data){ last=append(last,A->data); A=A->next; } else if( (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 30 typedef struct{ int elem[MAXSIZE]; int length;/*表長*/ }sqlisttype; void exam21(sqlisttype *L){ int I,j; I=2,j=1; while( (1) ){ if(L->elem[I]<>L->elem[j]){ (2) ; (3) ; } I++; } (4) ; } 參考答案： (1) i<=L->length (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ù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3。當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為 B 。 A. 1和5 B. 2和4 C. 4和2 D. 5和1 17.設(shè)棧的輸入序列為1,2，…,10，輸出序列為a1,a2,…,a10，若a5=10，則a7為 C 。 A. 4 B. 8 C.不確定 D.7 18.設(shè)棧的輸入序列是1,2,3,4，則 D 不可能是其出棧序列。 A． 1243 B. 2134 C. 1432 D. 4312 19.以下 D 是C語言中”abcd321ABCD”的子串。 A. abcd B. 321AB C. “abcABC” D. “21AB” 20.若串S=”software”，其子串的數(shù)目是 C 。 A. 8 B. 37 C. 36 D. 9 21.將一個(gè)A[1:100,1:100]的三對(duì)角矩陣，按行優(yōu)先存入一維數(shù)組B[1:298]中，A中元素A66,65(即該元素的下標(biāo))在B數(shù)組中位置k為 B 。 A. 198 B. 195 C. 197 D. 196 22.設(shè)高為h的二叉樹只有度為0和2的結(jié)點(diǎn)，則此類二叉樹的結(jié)點(diǎn)數(shù)至少為 B ，至多為 F 。高為h的完全二叉樹的結(jié)點(diǎn)數(shù)至少為 E ，至多為 F 。 A． 2h B. 2h-1 C. 2h+1 D.h+1 E. 2h-1 F. 2h-1 G. 2h+1-1 H. 2h+1 23.一棵有124個(gè)葉結(jié)點(diǎn)的完全二叉樹，最多有 B 個(gè)結(jié)點(diǎn)。 A. 247 B. 248 C. 249 D. 251 24.若從二叉樹的任一結(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)無左孩子的二叉樹 D. 根結(jié)點(diǎn)無右孩子的二叉樹 E. 所有結(jié)點(diǎn)只有左孩子的二叉樹 F. 所有結(jié)點(diǎn)只有右孩子的二叉樹 26.具有n個(gè)結(jié)點(diǎn)的完全二叉樹，已經(jīng)順序存儲(chǔ)在一維數(shù)組A[1..n]中，下面的算法是將A中順序存儲(chǔ)變?yōu)槎骀湵泶鎯?chǔ)的完全二叉樹。請(qǐng)?zhí)顚戇m當(dāng)語句在下面的空格內(nèi)，完成上述算法。 #define MAXSIZE 30 typedef struct btnode{ int data; struct btnode *lchild, *rchild; }BTN; void createtree(BTN *p,int A[], int I,int n){ (1) ; p->data=A[I]; if( (2) ) (3) ; else p->lchild=NULL; if( (4) ) createtree( (5) ); else p->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,n 27.若在線性表中采用折半查找法查找元素，該線性表應(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 塊最好，每塊的最佳長度是 16 ；若每塊的長度為8，其平均檢索長度為 21 。 29.假定有K個(gè)關(guān)鍵字互為同義詞，若用線性探測法把這K個(gè)關(guān)鍵字存入散列表中，至少要進(jìn)行 D 次探測。 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.在文件局部有序或文件長度較小的情況下，最佳內(nèi)部排序的方法是 A 。 A. 直接插入排序 B. 冒泡排序 C. 簡單選擇排序 34.快速排序在最壞情況下時(shí)間復(fù)雜度是O(n2)，比 A 的性能差。 A. 堆排序 B. 冒泡排序 C. 簡單選擇排序 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. 簡單選擇排序 37.以下結(jié)點(diǎn)序列是堆的為 A 。 A. 100,90,80,60,85,75,20,25,10,70,65,50 B. 100,70,50,20,90,75,60,25,10,85,65,80 38.若要盡可能快地完成對(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;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 = (1) ; child = 2*root; while(child < n){ if((child list[child]) break; else{ list[ (3) ]=list[child]; (4) ; } } list[ (5) ]=rootkey; } 參考答案： (1) list[root] (2) child++; (3) child/2 (4) child *= 2; (5) child/2 41.表是一種數(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. f B. c C. a D. b (5): A. b B. c C. a D. d 答案：ABCBC 42.操作系統(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) 語言編制而成的的系統(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. PASCAL B. 宏 C. 匯編 D. C (5): A. 網(wǎng)絡(luò) B. 分時(shí) C. 批處理 D. 實(shí)時(shí) 答案：CBBDD 43.本程序從鍵盤讀入整數(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 0 typedef struct node{ int val; struct node *next; }NODE; void insert(NODE *list,int x){ NODE *u, *v, *p; u = list; v = u->next; while( (1) && x < v->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(“%d\t”,p->val); printf(“\n”); } 答案： (1) v != NULL或v (2) x > v->val 或 x != v->val (3) p->next (4) u->next (5) head->next 44.計(jì)算機(jī)數(shù)據(jù)處理的對(duì)象是具有不同結(jié)構(gòu)的各種數(shù)據(jù)，可以訪問的最小數(shù)據(jù)信息單位是 (1) ，可以引用的最小命名數(shù)據(jù)單位是 (2) 。 線性表是最簡單的一種數(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. 瀏覽 答案：CDBBC 45.本程序用于從鏈盤讀入整數(shù)，插入到鏈表，或從鏈表刪除一個(gè)整數(shù)。 閱讀下面的C代碼，將應(yīng)填入 (n) 處的字名寫在答卷的對(duì)應(yīng)欄內(nèi)。 #include #include 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) 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 < v->valu; u=v;v=v->next); if(v != NULL && x == v->val){ /*找到值為x的表元*/ if(v == list) list = list->next; else (3) ; (4) ; /*釋放空間*/ } 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é)束程序。\n\t請(qǐng)輸入選擇！”); scanf(%d,&ans); if( (5) ) return; printf(“輸入整數(shù)：”);scanf(“%d”,&x); if(ans==1) list=ins(list,x); else list=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 != 2 46. 從未排序的序列中，依次取出元素，與已排序序列的元素比較后，放入已排序序列中的恰當(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ù)量大小 答案：BAABA 47.操作系統(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í)語言和機(jī)器語言 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. CDROM D. 寄存器 答案：CDADB 48. 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;inext && jnext; j++; } if(i==j) return(p); else return(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è)長度為n的順序表中，向第i個(gè)元素之前插入一個(gè)新元素，需向后移動(dòng) B 個(gè)元素。 A. n-i B. n-i+1 C. n-i-1 D. i 63.從一個(gè)長度為n的順序表中刪除第i個(gè)元素時(shí)，需向前移動(dòng) A 個(gè)元素。 A. n-i B. n-i+1 C. n-i-1 D. i 64.在具有n個(gè)單元的順序存儲(chǔ)的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)首指針和隊(duì)尾指針，則判斷隊(duì)空的條件是 B 。 A. front=rear+1 B. front=rear C. front+1=rear D. front=0 65.從一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x的結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平均比較 D 個(gè)結(jié)點(diǎn)。 A. n B. n/2 C. (n-1)/2 D. (n+1)/2 66.一個(gè)棧的入棧序列是a,b,c,d,e，則棧不可能的輸出序列是 C 。 A. edcba B. decba C. dceab D. abcde 67.棧結(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->top<>0 B. ST->top=0 C. st->top<>mo D. st->top==mo 69.不帶頭結(jié)點(diǎn)的單鏈表head為空表的判定條件是 A 。 A. head==NILL B. head->next==NULL C. head->next==head D. head != NULL 70.在一個(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 Linknode{ int 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 。 A．q->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. 求串長 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的長度，則con(sub(s1,2,len(s2)),sub(s1,len(s2),2))的結(jié)果是 D 。 A. BCDEF B. BCDEFG C. BCPQRST D. BCDEFEF 75.常對(duì)數(shù)組進(jìn)行的兩種基本操作是 C 。 A. 建立和刪除 B. 索引和修改 C. 查找和修改 D. 索引和查找 76.稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即 Ｃ 。 A. 二維數(shù)組和三維數(shù)組 B. 三元組和散列 C. 三元組和十字鏈表 D. 散列和十字鏈表 77.對(duì)下圖所示的二叉表，按先根次序遍歷得到的結(jié)點(diǎn)序列為 B 。 A. ABCDHEIFG B. ABDHIECFG C. HDIBRAFCG D. HIDBEFGAC 78.在一棵二叉樹上，度為0的結(jié)點(diǎn)個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0= A 。 A. n2+1 B. n2-1 C. n2 D. n2/2 79.某二叉樹前序遍歷結(jié)點(diǎn)的訪問順序是ABCDEFG，中序遍歷結(jié)點(diǎn)的訪問順序是CBDAFGE，則其后序遍歷結(jié)點(diǎn)的訪問順序是 A 。 A．CDBGFEA B. CDGFEAB C. CDBAGFE D. CDBFAGE 80.在下列存儲(chǔ)形式中， D 不是樹的存儲(chǔ)形式。 A. 雙親表示法 B. 孩子鏈表表示法 C. 孩子兄弟表示法 D. 順序存儲(chǔ)表示法 81. 已知一棵二叉樹的中序序列為cbedahgijf，后序序列為cedbhjigfa，則該二叉樹為 B 。 82. 已知一棵權(quán)集W={2,3,4,7,8,9}的哈夫曼樹，其加權(quán)路徑長度WPL為 Ｃ 。 A. 20 B. 40 C. 80 D. 160 83.已知一棵度為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+…+nm D. m·nm 84.如下圖所示的4棵二叉樹中， Ｃ 不是完全二叉樹。 85.設(shè)高度為h的二叉樹上只有度為0或度為2的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為 B 。 A. 2h B. 2h-1 C. 2h+1 D. h+1 86.如下圖所示的二叉樹的中序遍歷序列是 Ｃ 。 A. abcdgef B. dfebagc C. dbaefcg D. defbagc 87.已知某二叉樹的后序遍歷序列是dabec，中序遍歷序列是debac，則其前序遍歷序列為 D 。 A. acbed B. decab C. deabc D. cedba 88.如果T2是由有序樹T轉(zhuǎn)換而來的二叉樹，則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. 16 B. 32 C. 31 D. 10 91. 在一非空二叉樹的中序遍序序列中，根結(jié)點(diǎn)的右邊 A 。 A. 只有右子樹的所有結(jié)點(diǎn) B. 只有右子樹的部分 C. 只有左子樹的部分結(jié)點(diǎn) D. 只有左子樹的所有結(jié)點(diǎn) 92. 樹最適合用來表示 Ｃ 。 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前的條件是 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+m B. h+m=2n C. m=h-1 D. n=2h-1 95.如果某二叉樹的前序?yàn)閟tuwv，中序?yàn)閡wtvs，則該二叉樹后序?yàn)? Ｃ 。 A. uwvts B. vwuts C. wuvts D. wutsv 96.設(shè)待排序的記錄為(20,16,13,14,19)，經(jīng)過下列過程將這些記錄排序。 20,16,13,14,19 16,20,13,14,19 13,16,20,14,19 13,14,16,20,19 13,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,68 B. 70,75,68,23,10,16,90,82 C. 82,75,70,16,10,90,68,23 D. 23,10,16,70,82,75,68,90 98.用快速排序的方法對(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ù)與記錄的初始排列次序無關(guān)的是 D 。 A. 希爾排序 B. 冒泡排序 C. 直接插入排序 D. 直接選擇排序 100.在歸并排序過程中，需歸并的趟數(shù)為 Ｃ 。 A. n B. C. D. 101.一組記錄的排序代碼為{46,79,56,38,40,84}，則利用堆排序的方法建立的初始堆為 B 。 A. {79,46,