計(jì)算機(jī)軟件基礎(chǔ)復(fù)習(xí)試題

PAGEPAGE3628、已知一組關(guān)鍵字{49,31,12,68,27}，要求對(duì)其按升序排序，寫出使用直接選擇排序的每趟結(jié)果。29、某大學(xué)圖書館對(duì)讀者借閱圖書制定有關(guān)規(guī)定如下：（1）本科學(xué)生可以借閱5本；（2）研究生：碩士研究生可以借閱7本，博士研究生可以借閱10本；（3）教職工：教授、副教授職稱的教師可以借閱15本，其他教職工可以借閱12本。用判定樹(shù)表示上述算法。五、程序設(shè)計(jì)題（本大題共2小題，每小題9分，共18分）34、編寫C語(yǔ)言函數(shù)f(floatx)，并用主函數(shù)調(diào)用該函數(shù)，輸出計(jì)算結(jié)果。35、已知下面鏈表節(jié)點(diǎn)類型，設(shè)計(jì)一個(gè)算法dellinklist，刪除以head為頭指針的單鏈表（帶頭節(jié)點(diǎn)）中數(shù)據(jù)域值為x的節(jié)點(diǎn)。Structnode{Intdata;Structnode*next;};做試題,沒(méi)答案?上自考365,網(wǎng)校名師為你詳細(xì)解答!一、l．C2．A3．D4．A5．C6．C7．B8．D9．Al0．D11．Cl2．Cl3．Bl4．Dl5．B2008年4月自考計(jì)算機(jī)軟件基礎(chǔ)(一)試卷第一部分選擇題一、單項(xiàng)選擇題(本大題共l5小題，每小題2分，共30分)在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的。請(qǐng)將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無(wú)分。1．下列與k=n++完全等價(jià)的表達(dá)式是()A．k=++nB．k+=n+lC．k=n，n=n+1D．n=n+1，k=n2．已知inta=5，b=3，*P=&b，*q=&a；下列賦值語(yǔ)句中與b=a；等價(jià)的語(yǔ)句是()A．*P=*q；B．P=q；C．*P=&q；D．P=*b；3．已知C語(yǔ)言函數(shù)fun()的定義形式為voidfun(charch，floatx){...}則正確調(diào)用函數(shù)fun()的語(yǔ)句是()A．fun(“a”，3．0)；B．fun('ab'，19．5)；C．t=fun('z'，3．6)；D．fun(65，32)；4．已知charsr[20]；inti；從鍵盤向數(shù)組sr輸入一字符串的正確語(yǔ)句是()A．gets(sr)；B．gets(sr[20])；C．for(i=0；i<20；i++)scanf(sr)；D．for(i=0；i<20；i++)gets(&sr)；5．執(zhí)行下列c語(yǔ)言程序段，循環(huán)結(jié)束的條件是()intn=0，P，sum=0；do{scanf(“％d”，&p)；n++；sum+=p；}while(sum!：126&&n<5)；A．sum的值不等于126或n的值小于5B．sum的值不等于126且n的值小于5C．sum的值等于l26或n的值大于等于5D．sum的值不等于126且n的值大于等于56.下列C語(yǔ)言程序的輸出結(jié)果是()main(){inta=13，m=0；switch(a％3){case0：m++：case1:m--；case2：m++；default：m++；}prinff(“％d”，m)；}A．-1B．0C．1D．27．已知C語(yǔ)言程序段如下：structsa{intnum：charname[10]；floatf；}stu[3]={{5，“l(fā)iming”，85．0}，{6，“l(fā)iuliaing”，91．5}，{7，“wangxin”，100}}；structsa*P；P=stu；則值為91.5的表達(dá)式是()A.(*p)·fB．(*++p)．fC.(*P++)．fD．(p++)->f8.下列程序是計(jì)算兩個(gè)矩陣的乘積，其算法的時(shí)間復(fù)雜度是()Voidmul—matrix(intn，int[][5]，intb[][5]，intc[][5]){inti，j，k，x；for(i=0；i<n；i++){for(j=0；j<n；j++){X=0；for(k=0；k<n；k++)X+=a[i][k]*b[k][j]；e[i][j]=X；}}}A．O(n)B．O(log3N)C．O(n2)D．O(n3)9．若不帶頭節(jié)點(diǎn)的單鏈表的頭指針為head，則判定該鏈表為空的條件是()A．head==NULLB．head!=NULLC．head->next==headD．head->next==NULL10．一個(gè)棧的進(jìn)棧數(shù)據(jù)元素序列為l、2、3、4、5，則不可能為棧的出棧序列的是()A．2、3、4、1、5B．1、5、4、3、2C．2、3、1、4、5D．5、4、1、3、211．一棵二叉樹(shù)的先序遍歷序列為ABCD，中序遍歷序列為CBAD，則后序遍歷序列是()A．BCDAB．BCADC．CBDAD．ABDC12．在具有n個(gè)頂點(diǎn)、e條邊的無(wú)向圖的鄰接表中，所有邊的鏈表中邊節(jié)點(diǎn)的總數(shù)是()A．e／2B．eC．2eD．2e+n13．已知一個(gè)有序表為(12，18，24，35，47，50，62，83，90，115，134)，用折半查找法查找值為90的元素時(shí)，查找成功所使用的比較次數(shù)是()A．1B．2C．3D．414．當(dāng)待排序序列中記錄的關(guān)鍵字基本有序或記錄個(gè)數(shù)較少時(shí)，則最好的排序方法是()A．基數(shù)排序B．冒泡排序C．直接選擇排序D．直接插入排序15.在瀑布模型中，將軟件劃分為若干個(gè)階段，軟件項(xiàng)目的需求分析一般屬于()A．維護(hù)階段B．開(kāi)發(fā)階段C．運(yùn)行階段D．計(jì)劃階段第二部分非選擇題二、填空題(本大題共l0小題，每小題2分，共20分)請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無(wú)分。16．?dāng)?shù)學(xué)式“30<Y<50”對(duì)應(yīng)的c語(yǔ)言表達(dá)式是：17.已知intk，x；則語(yǔ)句for(k=0，x=0；k<=9&&x!=10；k++)x+=2；執(zhí)行后k的值是()18．已知inta[10]={1，2，3，5，6)；則a[a[1]]=。19．下列C語(yǔ)言程序段的輸出結(jié)果是。intx=2，b[10]={5，6，7，8}，*P=b；printf(“％d，％d＼n”，b[6]，P[x])；20.數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容包括數(shù)據(jù)的邏輯結(jié)構(gòu)、以及他們之間的相互運(yùn)算。21．循環(huán)雙鏈表節(jié)點(diǎn)結(jié)構(gòu)為priordatanext在指針q所指節(jié)點(diǎn)前面插入一個(gè)節(jié)點(diǎn)t的操作是：t->prior=q->prior；t->next=q：___________，q->-prior=t;22.設(shè)有一個(gè)10×10的對(duì)稱矩陣A，采用下三角壓縮存儲(chǔ)方式，以行序?yàn)橹?，A[0][0]的存儲(chǔ)地址為100，每個(gè)元素占一個(gè)地址空間，則A[3][2]的地址是。23．在有向圖中，以頂點(diǎn)V為終點(diǎn)的邊的數(shù)目稱為v的。24.將一棵有100個(gè)節(jié)點(diǎn)的完全二叉樹(shù)從根這一層開(kāi)始，每一層從左到右依次對(duì)節(jié)點(diǎn)進(jìn)行編號(hào)，根節(jié)點(diǎn)的編號(hào)為1，則編號(hào)為49的節(jié)點(diǎn)的左孩子的編號(hào)是。25.軟件工程包括三個(gè)要素，分別為方法、和過(guò)程。三、解答題(本大題共4小題，每小題4分，共16分)26．用盒圖(N—s圖)畫出結(jié)構(gòu)化程序設(shè)計(jì)的三種基本結(jié)構(gòu)。27．對(duì)于圖G一1(1)從頂點(diǎn)1出發(fā)，按鄰接頂點(diǎn)序號(hào)由小到大順序給出廣度優(yōu)先遍歷的頂點(diǎn)序列。(2)給出用克魯斯卡爾法構(gòu)造的最小生成樹(shù)。

28．假設(shè)字符a，b，c，d，e，f使用頻率分別是0．07，0．09，0．13，0．21，0．23，0．27，構(gòu)造哈夫曼編碼樹(shù)(權(quán)值小的為左子樹(shù)，權(quán)值大的為右子樹(shù))，并根據(jù)哈夫曼編碼樹(shù)寫出a，b，c，d，e，f的哈夫曼編碼。29．已知一數(shù)值序列為{33，61，12，75，8，54，41}，請(qǐng)分別寫出按升序進(jìn)行排序時(shí)，直接選擇排序、直接插入排序第一趟結(jié)束后的數(shù)值序列。四、程序分析題(本大題共4小題，每小題4分，共16分)30．寫出下列程序的運(yùn)行結(jié)果。main(){intj，a[5]={10，11，12，13，14}，*P=&a[1]；for(j=1；j<5；j++)}if(j％2)printf(”％5d”，a[j])；elsecontinue；printf(”％5d／n”，*P++)；}}31．寫出下列程序的運(yùn)行結(jié)果。fun(inta){staticintX=5；intY=0，t；X++；Y++；t=a+X+Y：return(t)；}main(){inta=2，b=3；prinff(”％d＼n”，fun(a))；printf(”％d＼n”，fun(b))；}32．下面程序的功能是：將有l(wèi)5個(gè)數(shù)據(jù)元素的整型數(shù)組的最大值與末元素對(duì)調(diào)后輸出，填空完成程序。main(){intX[15]，max，n，i；for(i=0；i<15；i++)scanf(“％d”，＆x[i])；max=x[O]；n=0；for(i=1；i<15；i++)if(①){max=X[i]；n=i：}X[n]=x[14]；②；for(i=0；i<15；i++)printf(“％d”，X[i])；}33．下列算法的功能是：將循環(huán)隊(duì)列隊(duì)首元素的值放入變量e后刪除隊(duì)首元素，操作成功返回1，否則返回0；QUEUE表示循環(huán)隊(duì)列的數(shù)據(jù)結(jié)構(gòu)。填空完成算法。typedefstruct{intdata[100]；inthead；／*隊(duì)首元素的下標(biāo)*／inttail；／*等于隊(duì)尾元素的下標(biāo)加1*／}QUEUE；Leavequeue(QUEUE*Q，int*e){if(①；return0；*e=Q->data[Q->head]；Q->head=②；Retum1；}五、程序設(shè)計(jì)題(本大題共2小題，每小題9分。共l8分)34．編寫c語(yǔ)言程序?qū)崿F(xiàn)：從鍵盤上輸入10個(gè)學(xué)生某門課的成績(jī)，計(jì)算平均成績(jī)，統(tǒng)計(jì)并輸出所有高于平均分的學(xué)生成績(jī)及人數(shù)。35．設(shè)一棵二叉樹(shù)以二叉鏈表赤存儲(chǔ)，節(jié)點(diǎn)結(jié)構(gòu)為：LchilddataRchild定義此存儲(chǔ)結(jié)構(gòu)的數(shù)據(jù)類型，用C語(yǔ)言編寫一個(gè)遞歸函數(shù)，計(jì)算此二叉樹(shù)上度為l的節(jié)點(diǎn)個(gè)數(shù)做試題,沒(méi)答案?上自考365,網(wǎng)校名師為你詳細(xì)解答!2008年4月計(jì)算機(jī)軟件基礎(chǔ)(一)試卷參考答案一、l．C2．A3．D4．A5．C6．C7．B8．D9．Al0．D11．Cl2．Cl3．Bl4．Dl5．B二、l6．y>30&&y<5017．518．319．0．720．物理結(jié)構(gòu)(或存儲(chǔ)結(jié)構(gòu))21．Q->prior->next=t22．10823．入度24．9825．工具三、26．

27．(1)廣度優(yōu)先遍歷的頂點(diǎn)序列：l256734(2分)(2)最小生成樹(shù)：(2分)分)

28．(1)哈夫曼編碼樹(shù)：(2分)

(2)哈夫曼編碼：a：1110b：llllc：110d：00e：01f：10(2分)29．(1)直接選擇排序8，61，12，75，33，54,41(2分)(2)直接插人排序33，61，l2，75，8，54，41(2分)四、30．1111(2分)1312(2分)31．9(2分)．11(2分)32．①max<x[i](或x[i]>max)(2分)②x[14]=maX(2分)33．①Q(mào)->head==Q->tail(2分)②(Q->head+1)％100(2分)五、【說(shuō)明】下述答案僅供參考，若采用其他方法答題，只要正確實(shí)現(xiàn)題目要求，仍可獲滿分。若程序不完整，可酌情給分。34．main(){inti，n=0；floatx[10]，av=0；for(i=0；i<10；i++){scanf(“％f"，&x[i])；av=av+x[i]；}av=av／l0；for(i=0；i<10；i++)if(X[i]>av){n++；printf(“％7．2f＼n”v[i])；}printf(“％d＼n”，n)；}【評(píng)分參考】定義正確3分，輸入正確l分、平均值計(jì)算正確2分，輸出正確3分。35．參考答案一：typedefstructnode{intdata；structnode％Lchild．*Rchild；}NODE；voidleaf(NODE*root){if(root!=NULL){if((root->Lehild!=NULL&&root->Rchild==NULL)!!(root->Lehild==．NULL&&root->RchildI=NULL))n=n+1：leaf(root->Lchild)；leaf(root->Rehild)；}}

參考答案二：structnode{intdata