北航軟院2012年數(shù)據(jù)結(jié)構(gòu)與C語言程序設(shè)計(jì)試題原版

1、北京航空航天大學(xué)2012年碩士研究生入學(xué)考試試題數(shù)據(jù)結(jié)構(gòu)與C語言程序設(shè)計(jì)”(科目代碼：991)一、填空題(本題共20分，每小題各2分)1 .從總體上說，數(shù)據(jù)結(jié)構(gòu)”課程主要研究三個(gè)方面的內(nèi)容。2 .若對(duì)某線性表最常用的操作是在表中插入元素或者刪除表中元素，則對(duì)于順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)這兩種存儲(chǔ)結(jié)構(gòu)而言，線性表應(yīng)該采用。3 .在長(zhǎng)度為n的非空隊(duì)列中進(jìn)行插入或者刪除操作的時(shí)間復(fù)雜度用大O符號(hào)表示為。4 .若一棵度為4的樹中度為1、2、3和4的結(jié)點(diǎn)個(gè)數(shù)分別為4、2、1和1,則該樹中葉結(jié)點(diǎn)的個(gè)數(shù)為。5 .若某二叉樹的中序遍歷序列為B,A,F,D,G,C,E,按層次遍歷序列為A,B,C,D,E,F,G

2、,則該二叉樹的后序遍歷序列為。6 .將一棵結(jié)點(diǎn)總數(shù)為n、且具有m個(gè)葉結(jié)點(diǎn)的樹轉(zhuǎn)換為一棵二叉樹以后，該二叉樹中右子樹為空的結(jié)點(diǎn)有個(gè)。7 .對(duì)于圖G=(V,E)與GA=(VA,EA),若有W包含于V,EA包含于巳則稱G是G的8 .在順序表(6,15,30,37,65,68,70,72,89,99)中采用折半查找法查找元素37,與表中進(jìn)行過比較的元素依次是。9 .若已知n個(gè)關(guān)鍵字值具有相同的散列函數(shù)值，并且采用線性探測(cè)再散列法處理沖突，那么，將這n個(gè)關(guān)鍵字值全部散列到初始為空的地址空間中，發(fā)生散列沖突的次數(shù)是10 .若長(zhǎng)度為n的序列K=(k1,k2,kn當(dāng)且僅當(dāng)滿足kiwk2并且kiwk2i+1(1

3、illink=q;/*第1條語句*/p-rlink=qrlink;/*第2條語句*/q-rlink=p;/*第3條語句*/q-rlink-llink=p;/*第4條語句*/2 .已知某完全二叉樹的第7層有10個(gè)葉結(jié)點(diǎn)，請(qǐng)求出該完全二叉樹的結(jié)點(diǎn)總數(shù)的最大值。（要求寫出結(jié)論的求解過程）3 .證明：具有n個(gè)頂點(diǎn)的無向圖最多有n（n-1）/2條邊。4 .請(qǐng)分別寫出對(duì)數(shù)據(jù)元素序列（80,30,50,10,90,20）按值從大到小進(jìn)行選擇排序時(shí)每一趟的排序結(jié)果。四、算法設(shè)計(jì)題（本題15分）已知某具有n個(gè)頂點(diǎn)的有向圖采用鄰接表方法存儲(chǔ)，其中，用以存儲(chǔ)有向邊信息的邊結(jié)點(diǎn)類型為typedefst

4、ructedgeintadjvex;/*某有向邊的終止頂點(diǎn)在頂點(diǎn)結(jié)點(diǎn)中的位置*/structedge*next;/*指向下一個(gè)邊結(jié)點(diǎn)*/ELink;用以存儲(chǔ)頂點(diǎn)信息的頂點(diǎn)結(jié)點(diǎn)類型為typedefstructverintindegree;/*某頂點(diǎn)的入度*/vertypevertex;/*某頂點(diǎn)的數(shù)據(jù)信息*/ELink*link;/*指向以該頂點(diǎn)為出發(fā)點(diǎn)的第一個(gè)邊結(jié)點(diǎn)*/VLink;并且n個(gè)頂點(diǎn)結(jié)點(diǎn)構(gòu)成一個(gè)數(shù)組結(jié)構(gòu)G0.n-1。請(qǐng)寫一個(gè)算法，該算法判斷給定的頂點(diǎn)序列V0.n-1=v1,v2,v3,vi#否是該有向圖的一個(gè)拓?fù)湫蛄?，若是該有向圖的一個(gè)拓?fù)湫蛄校惴ǚ祷?,否則，算法返回0。五、單項(xiàng)

5、選擇題（本題共20分，每小題各2分）1 .在C語言中，標(biāo)識(shí)符只能由字母、數(shù)字和下劃線三種字符組成，并且第一個(gè)字符A.必須是字母B,必須是下劃線C.必須是字母或者下劃線D.可以是字母、數(shù)字和下劃線之一2 .若整型變量x的初值為6,則計(jì)算表達(dá)式“x+=x=x*x”之后，x的值是A.50B.60C.-50D.-603 .下列4個(gè)程序段中，不是無限循環(huán)的是。A.for(b=0,a=1;a+b;a=k+)k=a;B.for(;a+=k);C.while(1)a+;D.for(k=10;k-)total+=k;4.說明“double(*ptr)N;中的標(biāo)識(shí)符ptr是。A.N個(gè)指向double類型變量的指針

6、B.指向N個(gè)double類型變量的函數(shù)指針C.一個(gè)指向由N個(gè)double類型元素組成的一維數(shù)組的指針D.具有N個(gè)指針元素的一維指針數(shù)組，其每一個(gè)元素都只能指向double類型變量5 .下列4個(gè)敘述中，正確的是。A. char*r=chin罅價(jià)于char*r;*r=china”；B. char*ptr=chin等價(jià)于char*ptr;ptr=china”；C. charstring10=china價(jià)于；charstring10;string=china;D. charstr4=abc,temp4=等lyobccharstr4=temp4=abc；6 .在C程序中，語句char*func(intx

7、,inty);表示。A.對(duì)函數(shù)func的定義B.對(duì)函數(shù)func的調(diào)用C.對(duì)函數(shù)func返回值類型的說明D.對(duì)函數(shù)func的原型說明7 .對(duì)于下列程序，若從鍵盤上輸入：abc6卜回車，則輸出結(jié)果是。#include#includemain()char*p,*q;p=(char*)malloc(sizeof(char)*20);q=p;scanf(s%S,p,q);printf(%s%s,p,q);A.defdefB.abcdefC.abcdD.dd8.當(dāng)說明一個(gè)結(jié)構(gòu)體變量時(shí)系統(tǒng)分配給它的內(nèi)存是。A.結(jié)構(gòu)中最后一個(gè)成員所需的內(nèi)存量B.結(jié)構(gòu)中第一個(gè)成員所需的內(nèi)存量C.成員中占內(nèi)存量最大者所需的容量D

8、.各成員所需內(nèi)存量的總和9.下列程序的輸出結(jié)果為。#defineABC(x)x*xmain()inta,k=3;a=+ABC(k+1);printf(%d,a);A.8B.9C.14D.1710.若要以a+方式打開一個(gè)已經(jīng)存在的文件，則下列敘述中，正確的是。A.文件被打開時(shí)，原有的文件內(nèi)容不被刪除，位置指針移動(dòng)到文件的末尾，可進(jìn)行添加和讀操作B.文件被打開時(shí)，原有的文件內(nèi)容不被刪除，位置指針移動(dòng)到文件的開頭，可進(jìn)行重寫和讀操作C.文件被打開時(shí)，原有的文件內(nèi)容被刪除，只能進(jìn)行寫操作D.以上三種說法都不正確六、簡(jiǎn)答題(本題共20分，每小題各5分)1 .在C語言中，頭文件白作用是什么？2 .在C語言

9、中，#includeafilenameh#include的區(qū)別是什么？3 .在C語言中，全局變量和局部變量的主要區(qū)別是什么？4 .字符指針、浮點(diǎn)數(shù)指針、以及函數(shù)指針這三種類型的變量哪個(gè)占用的內(nèi)存最大？為什么？七、填空題(本題共20分，每小題各2分)(說明：由于一些符號(hào)無法在本網(wǎng)站顯示，本大題中的填空處用(i)表示第i個(gè)空-答疑”)1.下列代碼的功能包括：定義一個(gè)x數(shù)組，說明一個(gè)結(jié)構(gòu)體，同時(shí)對(duì)變量t進(jìn)行初始化，使得t的a成員的值為50,b成員的值為x數(shù)組的首地址。請(qǐng)?jiān)诳瞻滋?方框內(nèi))填入合適的內(nèi)容，以完成上述功能。intx5=1,2,3,4,5);structinta,int*b?t(1),(2

10、);2.下列函數(shù)的功能是根據(jù)公式s=1-1/3+1/5-1/7+1/(2n+1計(jì)算s的值，其中，n通過形參傳入(nn0)計(jì)算結(jié)果通過形參指針傳回。請(qǐng)?jiān)诤瘮?shù)的空白處填入合適的內(nèi)容，使函數(shù)完整。voidfun(float*sn,intn)floats=0,w,f=-1;inti;for(i=0;i=n;i+)f=(1);w=f/(2);s+=w;*sn=s;3 .下列程序?qū)崿F(xiàn)將輸入的一個(gè)小寫字母循環(huán)后移5個(gè)位置后輸出。例如，若輸入字母，a?,則輸出字母，f?,若輸入字母，w?,則輸出字母,b?o請(qǐng)?jiān)诔绦虻目瞻滋幪钊牒线m的內(nèi)容，使程序完整。#includemain()charc;c=getchar(

11、);if(c=,a?&c=,v?&c=,z?)(2);putchar(c);4 .下列自定義函數(shù)的功能是實(shí)現(xiàn)兩個(gè)字符串的比較。請(qǐng)?jiān)诤瘮?shù)的空白處填入合適的內(nèi)容，使函數(shù)完整。intsstrcmp(char*s,char*t)while(*s&*t&*s=(1)s+;t+;return(2);5 .下列程序的功能是將已經(jīng)按升序排好序的兩個(gè)字符串str1和str2中的字符再按升序歸并到字符串str3中。請(qǐng)?jiān)诔绦虻目瞻滋幪钊牒线m的內(nèi)容，使程序完整。#includemain()charstr1=acegikm”；charstr2=bdfhjlnpq”；charstr3,*p;inti=0,j=0,k=0;

12、while(str1i!=,0?&str2j!=,0?)if(str1istr2j)str3k=str1i+;else；k+;str3k=,0?;if(2)p=str2+j;elsep=str1+i;strcat(str3,p);puts(str3);6 .對(duì)于下列main函數(shù)，經(jīng)過編譯、連接后得到的可執(zhí)行文件名為file.exe,并且已知在系統(tǒng)的命令狀態(tài)下輸入命令行fileBeijingShanghai”后得到的輸出結(jié)果是BeijingShanghai請(qǐng)?jiān)诤瘮?shù)的空白處填入合適的內(nèi)容，使函數(shù)完整。main(intargc,char*argv)while(1)+argv;printf(%s,(2

13、);-argc;7 .下列程序的功能是打開兩個(gè)已存在的文件file1和file2,并將file2拼接到file1的后面。請(qǐng)?jiān)诔绦虻目瞻滋幪钊牒线m的內(nèi)容，使程序完整。#includeintmain()FILE*fp1,*fp2;if(fp1=fopen(file1”,“(1)=NULL)printf(Cannotopenfileif!);return0;if(fp2=fopen(file2,(2)=NULL)printf(Cannotopenfile2!);return0;while(!feof(3)fputc(4),fp1);fclose(fp1);fclose(fp2);8 .設(shè)n0。下列函

14、數(shù)的功能是。intfun(intn)intcount=0;while(n)count+;n=n/10;returncount;9 .下列程序的功能是#include#includemain()charstr81,*pt1*ptintn;gets(str);n=strlen(str);ptr1=str;ptr2=str+n-1;while(ptr1ptr2)if(*ptr1!=*ptr2)break;elseptr1+;ptr2-;if(ptr1ptr2)printf(elseprintf(e!n”10.下列程序的功能是）；#includevoidmain()FILE*fp;longposition;fp=fopen(file.texfprintf(fp,“data);”“*IINo!（提示：ftell（*FILE）返回long類型的文件指針位置）Xa);position=ftell(fp);