計(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í)的無窮大階數(shù)，最大的是 D 。A. lognB. nlognC. 2n/2D. n!spnextnextnext6.將下圖所示的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. 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 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(n>0)指明循環(huán)鏈表的結(jié)點(diǎn)個(gè)數(shù)，參數(shù)I(1In)指明起始結(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è)語句。#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(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(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=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=(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;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->elemI<>L->elemj) (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和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語言中”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)無左孩子的二叉樹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)語句在下面的空格內(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*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. 元素按值有序，且采用順序存儲(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;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<n) && (listchild<listchild+1) (2) ;if(rootkey > 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) 語言編制而成的的系統(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 <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;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(“%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 <stdio.h>#include <malloc.h>typedef struct nodeint 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) ;/*釋放空間*/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í)語言和機(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. 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;i<n;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;i<=n;i+)s=a+b;b=a;a=s;供選答案：A. O(1)B. O(n)C. O(log2n)D. O(n2)52.數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中，計(jì)算機(jī)的 A 以及它們之間的關(guān)系和運(yùn)算等的學(xué)科。A.操作對(duì)象B. 計(jì)算方法C. 邏輯存儲(chǔ)D. 數(shù)據(jù)映象53.在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成 C 。A. 動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B. 緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C. 線性結(jié)構(gòu)和非線性結(jié)構(gòu)D. 內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)54.算法分析的目的是 C 。A. 找出數(shù)據(jù)結(jié)構(gòu)的合理性B. 研究算法中輸入和輸出的關(guān)系C. 分析算法的效率以求改進(jìn)D. 分析算法的易懂性和文檔性55.算法分析的兩個(gè)主要方面是 (4) 。A. 間復(fù)雜性和時(shí)間復(fù)雜性B. 正確性和簡(jiǎn)明性C. 可讀性和文檔性D. 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性56.一個(gè)線性順序表第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長(zhǎng)度為2，則第5個(gè)元素的地址為 B 。A. 110B. 108C. 100D. 12057.若已知一個(gè)棧的入棧序列是1,2,3,n，其輸出序列為P1,P2,P3,Pn，若P1=n，則Pi為 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 *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(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->top<>0B. ST->top=0C. st->top<>moD. 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. m·nm84.如下圖所示的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)換而來的二叉樹，則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. 樹最適合用來表示 。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+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ù)與記錄的初始排列次序無關(guān)的是 D 。A. 希爾排序B. 冒泡排序C. 直接插入排序D. 直接選擇排序100.在歸并排序過程中，需歸并的趟數(shù)為 。A. nB. C. D. 101.一組記錄的排序代碼為46,79,56,38,40,84，則利用堆排序的方法建立的初始堆為 B 。A. 79,46,