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

《計(jì)算機(jī)軟件技術(shù)基礎(chǔ)》試題.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)與順序存儲結(jié)構(gòu)相比優(yōu)點(diǎn)是〇A,所有的操作算法實(shí)現(xiàn)簡單 B.便于隨機(jī)存取C.便于插入和刪除 D,便于利用零散的存儲器空間.線性表是具有n個(gè)的有限序列。A,表元素 B,字符C,數(shù)據(jù)元素D.數(shù)據(jù)項(xiàng) E.信息項(xiàng).若長度為n的線性表采用順序存儲結(jié)構(gòu),在其第I個(gè)位置插入ー個(gè)新元素的算法的時(shí)間復(fù)雜度為〇(1くIくn+1)A.0(0) B.0(1)C.0(n) D.0(n2).設(shè)A是ー個(gè)線性表(ai,a2,…,a),采用順序存儲結(jié)構(gòu),則在等概率的前提下,平均每插入ー個(gè)元素需要移動的元素個(gè)數(shù)為,平均每刪除ー個(gè)元素需要移動的元素個(gè)數(shù)為 ;若元素插在ル與ai+1之間(O^I^n-1)的概率為亞色,n(n+1)則平均每插入ー個(gè)元素所要移動的元素個(gè)數(shù)為;C.2 D.即里.下列函數(shù)中,按它們在〃f〇〇時(shí)的無窮大階數(shù),最大的是〇A.logn B.nlog/7C.2n/2 D.n!nextnextnextnextnext.將下圖所示的s所指結(jié)點(diǎn)加到p所指的結(jié)點(diǎn)之后,其語句應(yīng)為:〇s->next=p+l;p->next=s;(*p).next=s;(*s).next=(*p).next;s->next=pー〉next;pー〉next=s->next;s-〉next=pー〉next;p-〉next=s;.將兩個(gè)各有n個(gè)元素的有序表歸并為ー個(gè)有序表時(shí),其最少的比較次數(shù)是〇A.n B.2n-lC.n-l D.2n8.下面的程序段是合并兩個(gè)無頭結(jié)點(diǎn)鏈表(ha和hb)為ー個(gè)無頭結(jié)點(diǎn)鏈表ha的過程,作為參數(shù)的兩個(gè)鏈表都是按結(jié)點(diǎn)的data域由大到小鏈接的。合并后新鏈表的結(jié)點(diǎn)仍按此方式鏈接。請?zhí)顚懴率隹湛?使程序能正確運(yùn)行。ttdefineNULL0typedefstructnode{structnode*next;}node,linklisttype;voidcombine(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){ /?較大的元素先插入?/TOC\o"1-5"\h\zp->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);9.如果表A中所有元素⑸,a2,…,a)與表B的ー個(gè)順序子表(bk,bk+i,…bk+z)完全相同(即a尸bk,a2=bk+i,???an=bk+n-l)?貝稱表A包含在表B中。設(shè)ha,hb為帶頭結(jié)點(diǎn)的單鏈表,分別表示有序表A和B,下面的函數(shù)用于判別表A是否包含在表B中,若是,則返回true,否則返回false。(提示:用遞歸實(shí)現(xiàn))definetrue1definefalse0defineNULL0typedefstructnode{intdata;structnode*next;}node,linklisttype;intinclusion(linklisttype*ha,linklisttype*hb){linklisttype*pa,*pb;pa=haー〉next;pb=hb->next;while((2))if(pa->data=pbー〉data) (3)10.在本題的程序中,函數(shù)create_link_list(n)建立一個(gè)具有n個(gè)結(jié)點(diǎn)的循環(huán)鏈表;函數(shù)josephus(n,I,m)對由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ù)1(1くIくn)指明起始結(jié)點(diǎn),參數(shù)m(m>0是步長),指明從起始結(jié)點(diǎn)或前次被刪除并輸出的結(jié)點(diǎn)之后的第m個(gè)結(jié)點(diǎn)作為本次被輸出并刪除的結(jié)點(diǎn)。例如,對于下圖所示的具有6個(gè)結(jié)點(diǎn)的循環(huán)鏈表,在調(diào)用josephus(6,3,2)后,將輸出5,1,3,6,4,2。請?jiān)诳湛蛱幪钌线m當(dāng)內(nèi)容,每框只填ー個(gè)語句。ttdefineNULL0typedefstructnode{intdata;structnode*next;}node,linklisttype;linklisttype*create_linklist(intn){linklisttype*head,*p,*q;head=NULL;if(n>0){head=(linklisttype*)malloc(sizeof(linklisttype));p=head;￡〇「(1=1;1く』ー1;1++){/?此循環(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);)voidJosephus(intn,intj,intm){linklisttype*p,*q;intj;p=createlinklist(n);for(;I>1;I-)p=p->next;⑷；while(j<n){for(1=1;I<=m-1;1++)p=p->next;⑸；printf("/8d”,qー>data); (6) ;free(q);j=j+l；).在下列程序中,函數(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)。ttinclude<stdio.h>ttdefineNULL0typedefstructnode{intdata;structnode*next;}NODE;NODE*append(NODE*last,intx){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;while((4)){last=append(last,A->data);A=Aー〉next;)⑸；last=C;C=C->next;free(last);return(C);).閱讀以下算法,填充空格,使其成為完整的算法。其功能是在ー個(gè)非遞減的順序存儲線性表中(從下標(biāo)1處開始存儲),刪除所有值相等的多余元素。ttdefineMAXSIZE30typedefstruct(intelem[MAXSIZE];intlength;/?表長?/}sqlisttype;voidexam21(sqlisttype*L){intI,j;1=2,j=l;while(QJ){if(L->elem[I]<>L->elem[j]){1++;)(4).用單鏈表表示的鏈?zhǔn)疥?duì)列的隊(duì)頭在鏈表的位置。A.鏈頭B.鏈尾C.鏈中.若用單鏈表表示隊(duì)列,則應(yīng)該選用〇A.帶尾指針的非循環(huán)鏈表 B.帶尾指針的循環(huán)鏈表C.帶頭指針的非循環(huán)鏈表 D.帶頭指針的循環(huán)鏈表.在解決計(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è)結(jié)構(gòu)。A.堆棧 B.隊(duì)列C.數(shù)組 D.線性表.若用ー個(gè)大小為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列,且當(dāng)前rear和front

的值分別為0和3。當(dāng)從隊(duì)列中刪除ー個(gè)元素,再加入兩個(gè)元素后,rear和front的值分別為〇A.1和5 B.2和4C.4和2 D.5和1.設(shè)棧的輸入序列為!,2,???,10,輸出序列為a,,a2,aw,若a5=10,貝リa7為〇A.4 B.8 C.不確定 D.7.設(shè)棧的輸入序列是1,2,3,4,則不可能是其出棧序列。A.1243B,2134C.1432 D.4312.以下是C語言中"abcd321ABCD”的子串。A.abed B.321AB C.“abcABC”D.“21AB”.若串S="softwaren,其子串的數(shù)目是〇A.8 B.37C.36 D.9.將一個(gè)A[l:100,1:100]的三對角矩陣,按行優(yōu)先存入ー維數(shù)組B[l:298]中,A中元素A66,65（即該元素的下標(biāo)）在B數(shù)組中位置k為〇A.198 B.195 C.197 D.196.設(shè)高為h的ニ叉樹只有度為0和2的結(jié)點(diǎn),則此類ニ叉樹的結(jié)點(diǎn)數(shù)至少為，至多為F。高為h的完全ニ叉樹的結(jié)點(diǎn)數(shù)至少為 E,至多為F〇A.2hB.2h-lC.2h+lD.h+1A.2hB.2h-lC.2h+lD.h+1E.2h1E.2h1 F.2-1 G.2hu-lH.2h+l.ー棵有124個(gè)葉結(jié)點(diǎn)的完全ニ叉樹,最多有個(gè)結(jié)點(diǎn)。A.247 B.248 C.249 D.251.若從ニ叉樹的任一結(jié)點(diǎn)出發(fā)到根的路徑上所經(jīng)過的結(jié)點(diǎn)序列按其關(guān)鍵字有序,則該ニ叉樹是〇A.滿ニ叉樹 B.哈夫曼樹C.堆 D.ニ叉查找樹.前序遍歷和中序遍歷結(jié)果相同的ニ叉樹為 F;前序遍歷和后序遍歷結(jié)果相同的ニ叉樹為。A,一般ニ叉樹 B.只有根結(jié)點(diǎn)的ニ叉樹C.根結(jié)點(diǎn)無左孩子的ニ叉樹 D.根結(jié)點(diǎn)無右孩子的ニ叉樹E.所有結(jié)點(diǎn)只有左孩子的ニ叉樹 F.所有結(jié)點(diǎn)只有右孩子的二叉樹.具有n個(gè)結(jié)點(diǎn)的完全ニ叉樹,已經(jīng)順序存儲在一維數(shù)組A[l..n]中,下面的算法是將A中順序存儲變?yōu)楗瞬骀湵泶鎯Φ耐耆瞬鏄?。請?zhí)顚戇m當(dāng)語句在下面的空格內(nèi),完成上述算法。ttdefineMAXSIZE30typedefstructbtnode{intdata;structbtnode*lchild,*rchiId;}BTN;voidcreatetree(BTN*p,intA[],intI,intn){p->data=A[I];if((2) )⑶；elsep->lchild=NULL;if((4) )createtree((5));elsep->rchild=NULL;)voidbtree(BTN*p,intA[],intn){createtree(p,A,1,n);).若在線性表中采用折半查找法查找元素,該線性表應(yīng)該〇A,元素按值有序 B.采用順序存儲結(jié)構(gòu)C,元素按值有序,且采用順序存儲結(jié)構(gòu)D.元素按值有序,且采用鏈?zhǔn)酱鎯Y(jié)構(gòu).在分塊檢索中,對256個(gè)元素的線性表分成塊最好,每塊的最佳長度是;若每塊的長度為8,其平均檢索長度為〇29.假定有K個(gè)關(guān)鍵字互為同義詞,若用線性探測法把這K個(gè)關(guān)鍵字存入散列表中,至少要進(jìn)行次探測。A.K-1次 B.K次C.K+1次 D.K(K+l)/2次.在n個(gè)記錄的有序順序表中進(jìn)行折半查找,最大的比較次數(shù)疋〇.Hash技術(shù)廣泛應(yīng)用于查找過程,選擇Hash函數(shù)的標(biāo)準(zhǔn)是和〇處理沖突的技術(shù)有優(yōu)有劣,其共同標(biāo)準(zhǔn)疋〇.在下述排序算法中,所需輔助存儲空間最多的是,所需輔助存儲空間最小的是,平均速度最快的疋〇A.快速排序 B.歸并排序 C.堆排序.在文件局部有序或文件長度較小的情況下,最佳內(nèi)部排序的方法疋〇A.直接插入排序 B.冒泡排序 C.簡單選擇排序.快速排序在最壞情況下時(shí)間復(fù)雜度是。(ボ),比的性能差。A.堆排序 B,冒泡排序 C.簡單選擇排序.若需在。(nlogn)的時(shí)間內(nèi)完成對數(shù)組的排序,且要求排序是穩(wěn)定的,則可選擇的排序方法是〇A.快速排序 B.堆排序C.歸并排序 D.希爾排序.如果只想得到1000個(gè)元素組成的序列中第5個(gè)最小元素之前的部分排序的序列,用 方法最快。A.冒泡排序 B.快速排序C.希爾排序 D.堆排序 E.簡單選擇排序.以下結(jié)點(diǎn)序列是堆的為。100,90,80,60,85,75,20,25,10,70,65,50100,70,50,20,90,75,60,25,10,85,65,80.若要盡可能快地完成對實(shí)數(shù)數(shù)組的排序,且要求排序是穩(wěn)定的,則應(yīng)選〇A.快速排序 B.堆排序C.歸并排序 D.希爾排序.從未排序序列中依次取出ー個(gè)元素與已排序序列中的元素依次進(jìn)行比較,然后將其放在已排序序列的合適位置,該排序方法稱為排序法。A.插入排序 B,交換排序.直接插入排序在最好情況下的時(shí)間復(fù)雜度為〇A.0(logn) B.0(n)O(nlogn) D.0(n2)41.下面函數(shù)是將任意序列調(diào)整為最大堆的算法,請將空白部分填上:將任意序列調(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ù)。voidadjust(intlist[],introot,intn){/?將以root為下標(biāo)的對應(yīng)元素作為待調(diào)整堆的根,待調(diào)整元素放在list數(shù)組中,最大元素下標(biāo)為n*/intchild,rootkey;rootkey= (1) ;child=2*root;while(child<n){if((child<n)&&(list[child]<list[child+1]))⑵；if(rootkey>list[child])break;else{list「(3)]=list[child];

list[(5)]=rootkey;).表是ー種數(shù)據(jù)結(jié)構(gòu),鏈表是ー種 ⑴ 。隊(duì)列和棧都是線性表,棧的操作特性是 (2) ,隊(duì)列的操作特性是(3)〇今有一空棧S,對下列待進(jìn)棧的數(shù)據(jù)元素序列a,b,c,d,e,f依次進(jìn)棧、進(jìn)棧、出棧、進(jìn)棧、進(jìn)棧、出棧的操作,則此操作完成后,棧S棧S的棧頂元素為⑷供選答案:(1)：A,非順序存儲線性表表C.順序存儲線性表(2):A.隨機(jī)進(jìn)出C,先進(jìn)先出(3):A.隨機(jī)進(jìn)出C,后進(jìn)后出:A.fC.a:A.ba,棧底兀素為(5)〇B.非順序存儲非線性D.順序存儲非線性表B.先進(jìn)后出D.出優(yōu)于進(jìn)B.先進(jìn)后出D.進(jìn)優(yōu)于出B.cbB.cD.d.操作系統(tǒng)主要是對計(jì)算機(jī)系統(tǒng)全部 （1） 進(jìn)行管理,以方便用戶、提高計(jì)算機(jī)使用效率的ー種系統(tǒng)軟件。它的主要功能有:處理機(jī)管理、存儲管理、文件管理、 （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í)6.多任務(wù)C.多用戶D.實(shí)時(shí)(4):A.PASCALB.宏C.匯編D.C(5):A.網(wǎng)絡(luò)B.分時(shí)C.批處理D.實(shí)時(shí).本程序從鍵盤讀入整數(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>ttinclude<malloc.h>ttdefineNULL0typedefstructnode{intval;structnode*next;}N0DE;voidinsert(NODE*list,intx){NODE*u,*v,*p;u=list;v=u->next;while((1)&&xくv->val){ /?尋找插入位置*/u=v;v=uー〉next;)if((v==NULLII(2)){ /?判斷是否要插入表兀*/p=(NODE*)malloc(sizeof(NODE));p->val=x; /?生成新表元?/(3)=v;一⑷ =p;/*插入新表元?/main(){intx;NODE*head,*p;/?首先建立只有輔助表元的空鏈表?/head=(NODE*)malloc(sizeof(NODE));(5)-NULL;printf(uEnterIntegers:\nv);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(u\n");)44.計(jì)算機(jī)數(shù)據(jù)處理的對象是具有不同結(jié)構(gòu)的各種數(shù)據(jù),可以訪問的最小數(shù)據(jù)信息單位是⑴ ,可以引用的最小命名數(shù)據(jù)單位是 (2) 。線性表是最簡單的ー種數(shù)據(jù)結(jié)構(gòu),有順序和鏈接兩種存儲方式。線性表按鏈接方式存儲時(shí),每個(gè)結(jié)點(diǎn)的包括 (3) 兩部分。線性表的查找有 ⑷和(5)兩種,但(5)只能用于順序存儲的情況。供選答案:(1)：A,數(shù)字C.數(shù)據(jù)元素(2):A.結(jié)點(diǎn)C.數(shù)據(jù)元素(3):A.數(shù)據(jù)值與符號C,數(shù)據(jù)與表名(4):A.隨機(jī)查找C,二分法查找(5):A.隨機(jī)查找C,二分法查找45.本程序用于從鏈盤讀入整數(shù),數(shù)。閱讀下面的C代碼,將應(yīng)填入ー應(yīng)欄內(nèi)。ttinclude<stdio.h>B,字符D.數(shù)據(jù)項(xiàng)B.記錄D.數(shù)據(jù)項(xiàng)B,數(shù)據(jù)與指針D.頭地址與尾地址B.順序查找D.瀏覽B.順序查找D.瀏覽插入到鏈表,或從鏈表刪除ー個(gè)整(n) 處的字名寫在答卷的對#include<malloc.h>typedefstructnode{intval;structnode*next;}N0DE;NODE*ins(NODE*list,intx){ /?將x按從小到大的次序插入鏈表?/NODE*u,*v=list,*p;for(;v!=NULL&&x<v->val;v=v->next);/?尋找插入位置?/if(v!=NULL&&x==v->val)return(1ist); /?已有,被忽略?/p=(NODE*)malloc(sizeof(NODE));p->val=x;/?生成新表元?/if(v==list)list=p;else⑴ ;⑵；returnlist;)NODE*del(NODE*list,intx){/?從鏈表中刪除值為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(){intx,ans;NODE*list=NULL,*p;while(1){printf("\n輸入1:將整數(shù)插入到鏈表。'n輸入2:從鏈表刪除ー個(gè)整數(shù)。、n”)；printf("其它整數(shù),結(jié)束程序。、n\t請輸入選擇!”)；scanf(%d,&ans);if((5))return;printf("輸入整數(shù):");scanf("%d",&x);if(ans==l)list=ins(list,x);elselist=del(list,x);elselist=del(list,x);for(p=list;p!=NULL;p=pー〉next)

printf("%4d”,pー＞val);}).從未排序的序列中,依次取出元素,與已排序序列的元素比較后,放入已排序序列中的恰當(dāng)位置上,這是 ⑴ 排序。從未排序的序列中,挑選出元素,放在已排序序列的某一端位置,這是(2)排序。逐次將待排序的序列中的相鄰元素兩兩比較,凡是逆序則進(jìn)行交換,這是 ⑶ 排序。如果整個(gè)排序過程都在內(nèi)存中進(jìn)行,稱為⑷排序。排序算法的復(fù)雜性與排序算法的⑸有關(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)算量大小與占用存儲多少

B.運(yùn)算量大小與處理的數(shù)據(jù)量大小C.并行處理能力和占用存儲多少D.占用存儲多少和處理的數(shù)據(jù)量大小.操作系統(tǒng)是對計(jì)算機(jī)資源進(jìn)行的 (1) 系統(tǒng)軟件,是(2)的接口。在處理機(jī)管理中,進(jìn)程是ー個(gè)重要的概念,它由程序塊、⑶和數(shù)據(jù)塊三部分組成,它有3種基本狀態(tài),不可能發(fā)生的狀態(tài)轉(zhuǎn)換是虛擬存儲器的作用是允許程序直接訪問比內(nèi)存更大的地址空間,它通常使用 (5) 作為它的ー個(gè)主要組成部分。供選答案:(1)：A.(1)：A.輸入和輸出C.管理和控制(2):A.軟件和硬件C,高級語言和機(jī)器語言(3):A.進(jìn)程控制塊C.文件控制塊(4):A.運(yùn)行態(tài)轉(zhuǎn)換為就緒態(tài)C.運(yùn)行態(tài)轉(zhuǎn)換為等待態(tài)(5):A.軟盤B.鍵盤操作D.匯編和執(zhí)行B,主機(jī)和外設(shè)D,用戶和計(jì)算機(jī)B.作業(yè)控制塊D.設(shè)備控制塊B,就緒態(tài)轉(zhuǎn)換為運(yùn)行態(tài)D,等待態(tài)轉(zhuǎn)換為運(yùn)行態(tài)B.硬盤C.CDROM D.寄存器.是信息的載體,它能夠被計(jì)算機(jī)識別、存儲和加工處理。A,數(shù)據(jù) B,數(shù)據(jù)元素C.結(jié)點(diǎn) D,數(shù)據(jù)項(xiàng).下列程序段的時(shí)間復(fù)雜度為〇for(i=l;i<n;i++){y=y+l；for(j=0;j<=(2*n);j++) x++;)供選答案:A.O(n-l) B.0(2n)C.0(n2)D,0(2n+l).下面程序段的時(shí)間復(fù)雜度為〇i=l；while(i<=n)i=i*2;供選答案:A.0(1) B.0(n) C.0(n2)D.0(log2n).下面程序段的時(shí)間復(fù)雜度為〇a=0;b=l;for(i=2;i<=n;i++){s=a+b;b=a;供選答案:A.0(1) B.0(n) C.0(log2n)D.0(n2).數(shù)據(jù)結(jié)構(gòu)是ー門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中,計(jì)算機(jī)的以及它們之間的關(guān)系和運(yùn)算等的學(xué)科。A.操作對象 B,計(jì)算方法 C.邏輯存儲 D,數(shù)據(jù)映象53.在數(shù)據(jù)結(jié)構(gòu)中,從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成0A.動態(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.算法分析的目的是。A.找出數(shù)據(jù)結(jié)構(gòu)的合理性B.研究算法中輸入和輸出的關(guān)系C.分析算法的效率以求改進(jìn)D.分析算法的易懂性和文檔性.算法分析的兩個(gè)主要方面是。A.間復(fù)雜性和時(shí)間復(fù)雜性 B.正確性和簡明性C.可讀性和文檔性 D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性.一個(gè)線性順序表第一個(gè)元素的存儲地址是100,每個(gè)元素的長度為2,則第5個(gè)元素的地址為。A.110 B.108 C.100 D.120.若已知一個(gè)棧的入棧序列是1,2,3,…,n,其輸出序列為Pi,P2,P”…,P.,若巳=n,則ヒ為。A.i B.n-i C.n-i+lD,不確定.對于一個(gè)棧,給出輸入項(xiàng)A,B,C。如果輸入項(xiàng)序列由A,B,C所組成,則不可能產(chǎn)生的輸出序列是。A.CAB B.CBA C.ABC D.ACB.設(shè)有如下的單鏈表的按序號查找的算法,其時(shí)間復(fù)雜度為〇LinkNode*GetNode(Linklisthead,inti){intj;ListNode*p;P=head;j=0;while(p->next&&j<i){p=pー〉next;j++；)if(i==j)return(p);elsereturn(NULL);

供選答案:A.0(ボ) B.0(2n)C.。(が) D.0(logn).二維數(shù)組ん加按行序?yàn)橹黜樞虼娣旁趦?nèi)存中,每個(gè)數(shù)組元素占1個(gè)存儲單元,則元素呪的地址計(jì)算公式是〇LOC(aij)=LOC(au)+[(i-l)*m+(j-l)]LOC(aiJ)=LOC(ail)+[(j-l)*m+(i-l)]LOC(aij)=LOC(ail)+[(i-l)*n+(j-l)]LOC(aij)=LOC(au)+[(j-l)*n+(i-l)].以下哪ー個(gè)不是隊(duì)列的基本運(yùn)算。A.從隊(duì)尾插入一個(gè)新元素 B.從隊(duì)列中刪除第i個(gè)元素C.判斷一個(gè)隊(duì)列是否為空 D.讀取隊(duì)頭元素的值.在一個(gè)長度為n的順序表中,向第i個(gè)元素之前插入ー個(gè)新元素,需向后移動個(gè)元素。A.n-i B.n-i+1C.n-i-1D.i.從ー個(gè)長度為n的順序表中刪除第i個(gè)元素時(shí),需向前移動個(gè)元素。A.n-i B.n-i+1C.n-i-1D.i.在具有n個(gè)單元的順序存儲的循環(huán)隊(duì)列中,假定front和rear分別為隊(duì)首指針和隊(duì)尾指針,則判斷隊(duì)空的條件是〇A.front=rear+lA.front=rear+lB.front=rearC.front+l=reeirD.front=0.從ー個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x的結(jié)點(diǎn)時(shí),在查找成功的情況下,需平均比較個(gè)結(jié)點(diǎn)。A.n B.n/2 C.(n-l)/2D.(n+l)/2.ー個(gè)棧的入棧序列是a,b,c,d,e,則棧不可能的輸出序列是〇A.edcbaB.decbaC.dceabD.abcde.棧結(jié)構(gòu)通常采用的兩種存儲結(jié)構(gòu)是0A.順序存儲結(jié)構(gòu)和鏈表存儲結(jié)構(gòu) B.散列方式和索引方式C.鏈表存儲結(jié)構(gòu)和數(shù)組 D.線性存儲結(jié)構(gòu)和非線性存儲結(jié)構(gòu).判斷ー個(gè)順序棧ST(最多元素為mo)為空的條件是〇A.STー>top?〇 B.ST->top=0C.st->top<>moD.st->top==mo.不帶頭結(jié)點(diǎn)的單鏈表head為空表的判定條件是〇A.head—NILLB.head->next==NULLC. headー>next==headD.head!=NULL.在ー個(gè)單鏈表中,已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn),若在P和q之間插入s結(jié)點(diǎn),則應(yīng)執(zhí)行0sー〉next=p->next;pー〉next=s;p->next=s->next;sー〉next=p;q->next=s;s->next=p;p->next=s;sー〉next=q;.假設(shè)雙向鏈表結(jié)點(diǎn)的類型如下:typedefstructLinknode（intdata;structLinknode*lLink; /?前驅(qū)結(jié)點(diǎn)指針?/structLinknode*rLink; /?后繼結(jié)點(diǎn)指針?/）下面給出的算法是要把ー個(gè)q所指新結(jié)點(diǎn),作為非空雙向鏈表中的P所指的結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn)插入到該雙向鏈表中,能正確完成要求的算法段疋〇A.q->rLink=p; q->lLink=p->lLink; pー〉lLink=q;p->lLink->rLink=q;pー〉lLink=q, qー〉rLink=p; pー〉ILink-〉rLink=q;q->lLink=p->lLink;q->lLink=p->lLink;q->rLink=p;p->!Link->rLink=q;p->lLink=q;D.以上均不對.串是ー種特殊的線性表,其特殊性體現(xiàn)在0A.可以順序存儲 B.數(shù)據(jù)元素是ー個(gè)字符C.可以鏈接存儲 D.數(shù)據(jù)元素可以是多個(gè)字符.設(shè)有兩個(gè)串p和q,求q在p中首次出現(xiàn)的位置的運(yùn)算稱

作〇A.連接 B.模式匹配 C,求子串 D.求串長.設(shè)串sl="ABCDEFG"，s2="PQRST”，函數(shù)con(x,y)返回x和y串的連接串,subs(s,I,j)返回串s的從序號i的字符開始的j個(gè)字符組成的子串,len(s)返回串s的長度,則con(sub(si,2,len(s2)),sub(si,len(s2),2))的結(jié)果是〇BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF.常對數(shù)組進(jìn)行的兩種基本操作是0A,建立和刪除B.索引和修改C.查找和修改 D.索引和查找.稀疏矩陣一般的壓縮存儲方法有兩種,即。A,二維數(shù)組和三A,二維數(shù)組和三維數(shù)組C.三元組和十字鏈表77.對下圖所示的ニ叉表,為〇A.ABCDHEIFGD.散列和十字鏈表按先根次序遍歷得到的結(jié)點(diǎn)序列ABDHIECFGC.HDIBRAFCGD.HIDBEFGACC.HDIBRAFCGD.HIDBEFGAC78.在ー棵ニ叉樹上,度為O的結(jié)點(diǎn)個(gè)數(shù)為n0,度為2的結(jié)點(diǎn)數(shù)為n2,貝リn0=〇A.ル+1B.A.ル+1n2 D.n2/279.某ニ叉樹前序遍歷結(jié)點(diǎn)的訪問順序是ABCDEFG,中序遍歷結(jié)點(diǎn)的訪問順序是CBDAFGE,則其后序遍歷結(jié)點(diǎn)的訪問順序是0A. CDBGFEA B. CDGFEABC. CDBAGFE D. CDBFAGE.在下列存儲形式中,不是樹的存儲形式。A.雙親表示法 B,孩子鏈表表示法C,孩子兄弟表示法 D.順序存儲表示法.已知一棵ニ叉樹的中序序列為cbedahgijf,后序序列為cedbhjigfa,則該ニ叉樹為.已知一棵權(quán)集W={2,3,4,7,8,9}的哈夫曼樹,其加權(quán)路徑長度WPし為0A.20 B.40C.80D.16083.已知一棵度為m的樹中有ル個(gè)度為1的結(jié)點(diǎn),ル個(gè)度為2的結(jié)點(diǎn),…，“個(gè)度為m的結(jié)點(diǎn),問這棵樹中葉子結(jié)點(diǎn)為〇A.1+n；(1-1)B.l+rij(1+1)C.必+&+…+へD.m,n?,84.如下圖所示的4棵ニ叉樹中,不是完全ニ叉樹。.設(shè)高度為h的ニ叉樹上只有度為0或度為2的結(jié)點(diǎn),則此類ニ叉樹中所包含的結(jié)點(diǎn)數(shù)至少為。A.2h B.2h-lC.2h+lD.h+1.如下圖所示的ニ叉樹的中序遍歷序列是〇

A.abcdgefB.dfebagcC.dbaefcgD.defbagcA.abcdgefB.dfebagcC.dbaefcgD.defbagc.已知某ニ叉樹的后序遍歷序列是dabec,中序遍歷序列是debac,則其前序遍歷序列為A.acbedB.decabC.deabcD.cedba88,如果T2是由有序樹T轉(zhuǎn)換而來的ニ叉樹,則T中結(jié)點(diǎn)的前序就是T2中結(jié)點(diǎn)的〇A.前序 B.中序C.后序 D.層次序.樹的基本遍歷策略可分為先根遍歷和后根遍歷;ニ叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。這里,我們把由樹轉(zhuǎn)化得到的ニ叉樹叫做這棵樹對應(yīng)的ニ叉樹。下面結(jié)論正確的是〇A.樹的先根遍歷序列與其對應(yīng)的ニ叉樹的先序遍歷序列相同B.樹的先根遍歷序列與其對應(yīng)的ニ叉樹的后序遍歷序列相同C.樹的先根遍歷序列與其對應(yīng)的ニ叉樹的中序遍歷序列相同D.以上均不對.深度為5的ニ叉樹至多有個(gè)結(jié)點(diǎn)。A.16 B.32C.31D.10.在一非空ニ叉樹的中序遍序序列中,根結(jié)點(diǎn)的右邊 〇A.只有右子樹的所有結(jié)點(diǎn)A.只有右子樹的所有結(jié)點(diǎn)C,只有左子樹的部分結(jié)點(diǎn)B.只有右子樹的部分D.只有左子樹的所有結(jié)點(diǎn).樹最適合用來表示。A.有序數(shù)據(jù)元素 B.無序數(shù)據(jù)元素C,元素之間具有分支層次關(guān)系的數(shù)據(jù)D.元素之間無聯(lián)系的數(shù)據(jù)93.設(shè)n,in為ー棵ニ叉樹上的兩個(gè)結(jié)點(diǎn),在中序遍歷時(shí),n在m前的條件是0A.n在m的右方 B.n是m的祖先C.n在m的左方 D.n是m的子孫94.對ー個(gè)滿ニ叉樹,m個(gè)樹葉,n個(gè)結(jié)點(diǎn),深度為h,則。A.n=h+m B.h+m=2nC.m=h-1 D.n=2h-l95.如果某ニ叉樹的前序?yàn)閟tuwv,中序?yàn)閡wtvs,則該ニ叉樹后序?yàn)?A.uwvts B.vwutsC.wuvts D.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,直接插入排序 B,冒泡排序C.希爾排序 D.堆排序97.對下列4個(gè)序列用快速排序的方法進(jìn)行排序,以序列的第一個(gè)元素為基礎(chǔ)進(jìn)行劃分,在第一趟劃分過程中,元素移動次數(shù)最多的是序列。70,75,82,90,23,16,10,6870,75,68,23,10,16,90,8282,75,70,16,10,90,68,2323,10,16,70,82,75,68,90.用快速排序的方法對包含幾個(gè)關(guān)鍵字的序列進(jìn)行排序,最壞情況下,執(zhí)行的時(shí)間為A.O(n) B.0(log2n)C.0(nlog2n)D.O(nう.在所有排序方法中,關(guān)鍵碼(即關(guān)鍵字)比較的次數(shù)與記錄的初始排列次序無關(guān)的是A.希爾排序 B.冒泡排序 C.直接插入排序 D.直接選擇排序.在歸并排序過程中,需歸并的趟數(shù)為〇A.n B. C.[“l(fā)og?”」D.[log,〃丨.ー組記錄的排序代碼為{46,79,56,38,40,84},則利用堆排序的方法建立的初始堆為A.{79,46,56,38,40,80} B.{84,79,56,38,40,46}C.{84,79,56,46,40,38} D.{84,56,79,40,46,38}.ー組記錄的排序代碼為{46,79,56,38,40,84},則利用快速排序的方法,以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為〇A.{38,40,46,56,79,84} B.{40,38,46,79,56,84}C.{40,38,46,56,79,84} D.{40,38,46,84,56,79}每次把待排序的區(qū)間劃分為左、右兩個(gè)子區(qū)間,其中左區(qū)間中元素的排序碼均小于等于基準(zhǔn)元素的排序碼,右區(qū)間中元素的排序碼均大于等于基準(zhǔn)元素的排序碼,此種排序方法叫做〇A.堆排序 B.快速排序C.冒泡排序 D.希爾排序ー組記錄的排序碼為ー個(gè)字母序列{Q,D,F,X,A,P,N,B,Y,M,C,W},按歸并排序方法對該序列進(jìn)行ー趟歸并后的結(jié)果為。D,F, Q,X, A,B, N,P, C,M, W,YTOC\o"1-5"\h\zD,F, Q,A, P,X, B,N, Y,C, M,W/