山西省2019年專升本選拔考試(C程序設(shè)計數(shù)據(jù)結(jié)構(gòu))歷年真題詳解

1、山西省 2019 年專升本選拔考試（ C 程序設(shè)計數(shù)據(jù)結(jié)構(gòu)）歷年真題詳解第一部分C程序設(shè)計一、單項選擇題 （ 本大題共 10 小題， 每小題 3 分，共計30 分 ）C語言程序的基本結(jié)構(gòu)有（A）A. 順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)B. 算法結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)、循環(huán)結(jié)構(gòu)C. 算法結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)D.順序結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)、循環(huán)結(jié)構(gòu)2. 不能作為合法的常量是（ A）A. 'ab'B. "e"C. ' 0111'D.12e+43. 正確的定義語句是（ C）A double a; b;B. double a=b=7.0;C. double a=7,b=

2、7;D. double,a,b;4. 若有定義語句:int a=1,3,5,7,9,i=4; 則錯誤的引用是（D）A. a-iB. a2*2C. a（ai+1）/2D. aa45. 已知函數(shù)調(diào)用 myFunc（f1（1）,（2,3）,（4,5,6）,（7,max（8,9） 中，有 （ B） 個實參。A.3B.4C.9D.26. 假設(shè)已指定整型變量i=3,float 型變量 f=25, 則表達式 10+'a'+i*f的值的類型是（ D）A charB. intC. floatD. doubleA. 下列關(guān)于結(jié)構(gòu)體的定義語句中，錯誤的是 （ B）A. struct xyz int

3、x; int y; int z; struct xyz abc;B. struct xyzint x;int y;int z; struct xyz abc;C. struct xyzint x;int y;int z; abe;D. struct int x; int y; int z; abc;8.下列關(guān)于C語言文件的敘述正確的是 (C)A.文件由數(shù)據(jù)序列組成，只能構(gòu)成二進制文件8 .文件由結(jié)構(gòu)序列組成，只能構(gòu)成文本文件C.文件由數(shù)據(jù)序列組成，可以構(gòu)成二進制文件或文本文件D.文件由結(jié)構(gòu)序列組成，可以構(gòu)成二進制文件或文本文件9 .指定局部變量為“靜態(tài)局部變量“，可用關(guān)鍵字(C)進行聲明。A.

4、 autoB. registerC. staticD.以上都不是10.執(zhí)行賦值表達式“ a=(b=3*4);"后a的值為(C)A.3B.4C.12D.以上都不是二、填空題(本大題共8小題，每空3分，共計24分)1 .已知定義：char c='' int a=-1, b; (c的初值為空格字符)。 執(zhí)行"b=!c&&a;"后b的值為 0。2 .設(shè)變量已正確定義為整數(shù)，則表達式n=i=2, +i, i+的值為 3 o3 .若有定義語句：char str20="123456789000", 則 strlen(str)

5、的值是 10。4 .已知語句int X=5;,則表達式X-=X*X的值為_-20_。5 .已知存在int a=0,b=9;語句，則執(zhí)行完"a+&&b+;"語句后，變量b的值是_9_。6 表達式(int)(double)(7/2)+3.5) 的值為 _6_。7 .一個變量的地址稱為該變量的_ “指針”。8 .已知字符'a'的ASCII碼是97 ，執(zhí)行“char cl ='x' "語句和 “pint f("%d'n",c1-2);”語句后，輸出結(jié)果是 _120。三、程序設(shè)計題(本大題共2小題，

6、每小題11分，共計22分)1 .已知一個函數(shù)：x ； (x<1)y= <2x-1(1<x<10)l3x-11(x >10)編寫函數(shù)Fun1實現(xiàn)上式，并返回函數(shù)值。在main函數(shù)調(diào)用Fun1 函數(shù)，接收輸入的x值，并輸出函數(shù)值，例如：輸入3.5,輸出6。dmihb Funl （clo<iblib % ）C分）tif （1 ） rcium x j（1分）if （= 1 式農(nóng)工（10 return 2 * x -；（1 分）Iif （n> = 10） n-titm 3 x-11 ；”分）ml majlii （）（1分）即。1加x+rw <1分）血：（1

7、 分）1rrft = Fun）（X）：（2 分）|prinlf（.（1 分）Jrrtum 0 ；2 .編寫函數(shù)Fun2,實現(xiàn)公式求 兀的近似值，直到發(fā)現(xiàn)某一項的 絕對值小于指定閾值為止（該項不累加），并返回近似值。在main函數(shù)調(diào)用Fun2函數(shù)，并輸出指定閾值為10-6的近似值。用？=1- 1+1- 1+?公式求?的近似值，直到43 5 7最后一項的絕對值小于10-6為止dnuble Fun2 （double terror）（2分）ini sign =；1 double pi =0. 0；（1分）double n = L 01 term = I. 0；while.term） : "r

8、rn）pi = pi + irrm；（1分）n 二 】1+2；（1分）sign =-sign；（1 分）_tenn = sign/ n;（1分）1 pi = pi/4；（1分）jflurii iesul!;（1 分）一11int niuin （）（2 分）jJ1Idoubii' res=l;un2（ lc 6） ； （ 1 分）t1printf （d, %f n" , res）; （1 分）return 0；1 i f1四、程序填空題（本大題共3小題，每小題8分，共計24分）1 .已知函數(shù)Fun3的部分代碼如下所示，其功能是將整數(shù)數(shù)組 x中的 元素按相反順序存放，請在空格處補

9、充程序。例如：x=1,2,3,4,則 經(jīng)過Fun3函數(shù)后為x=4,3,2,1void Fun3（int *x,int n） int*p,*i,*j ;inttemp;int midele=（n-1）/2 ;i=x;j=x+n-1 ;p= x+middle;for（; i<=p;i+,j-）temp=*i;*j=temp ;return result;2 .已知函數(shù)Fun4的部分代碼如下所示，其功能是：計算如下公式的前 n項和并作為函數(shù)值返回，請在空格處補充程序。fl(iiO)S£仃！( I Wn<20)n- 1。320)long Fun4( int n) int i,j;

10、long temp=1,result=0;if(n= =0) return 1;if(n>20) return 0;for(i=1; i<=n;i+)temp=temp*i;result=result+temp ;return result;3 .已知函數(shù)Fun5的部分代碼如下所示，其功能是：統(tǒng)計指針變量a所 指的字符串中單詞的個數(shù)，并存放在指針變量b所指的變量中。其中 單詞之間用空格分隔開。例如，若a所指的字符串為"I love you", 則b所指的變量的值應(yīng)為3,請在空格處補充程序。void Fun5(char *a, int *b ) int i=0,n

11、um=0,word=0;char c;for(i=0; c=ai)!= '0' ;i+)if(c=，) word=0;Else if( word=0)word=1;num+;*b=num;第二部分 數(shù)據(jù)結(jié)構(gòu) (C 語言版 )五、單項選擇題 ( 本大題共 10 小題，每小題 2 分，共計 20 分 )1. 不帶頭結(jié)點的單鏈表head 為空的判定條件是(A)A. head=NULLB. head->next = NULLC. head->next = headD. head! =NULL2. 一個隊列的數(shù)據(jù)入列序列是1, 2, 3, 4, 則隊列的出隊時輸出序列是( B

12、)A.4,3,2,1B.1,2,3,4C.1,4,3,2D.2,3,4,13. 一個 n 階的對稱矩陣, 如果以行或列為主序存入內(nèi)存, 則其容量為( C)A.nXnB.nXn/2C.nX(n+1)/2D.(n+1)X(n+1)/24. 后序遍歷的順序是( D)A. 根結(jié)點，左子樹，右子樹B. 左子樹，根結(jié)點，右子樹C. 右子樹，根結(jié)點，左子樹D.左子樹，右子樹，根結(jié)點5. 采用鄰接表存儲的深度優(yōu)先搜索算法類似于二叉樹的 (A)A. 前序遍歷B. 中序遍歷C. 后序逾歷D.按層遍歷6. 用順序查找法對n 個元素進行查找，等概率情況下 , 其平均查找長度為 ( D)A. nB. n/2C.(n-1

13、)/2D. (n+1)/27.最壞情況，在第i趟直接插入排序中，要進行(Q次關(guān)鍵字的比較。A. i+1B. iC. i-1D. ixi8 .在理想情況下，哈希查找可通過(A)次完成。A. 1B. 2C. n/2D. (n+1)/29 .線索化二叉樹中某結(jié)點沒有孩子的充要條件是 (B)A. D.LChild= NULLB. D. Ltag=1C. D. Ltag=0D. D. RChild=NULL10、一個棧的入棧序列abcde,則棧的不可能的輸出序列是(QA. edcbaB. decbaC. dceabD. abcde六、填空題(本大題共10小題，每空2分，共計20分)1 .在雙鏈表中，每個

14、結(jié)點有兩個指針域，一個指向該結(jié)點的直接前驅(qū)另一個指向該結(jié)點的直接后繼。2 .向棧壓入元素的操作是 入棧。3 .矩陣A中有s個非零元素，若s遠遠小于矩陣元素的總數(shù)，則稱 A 為稀疏矩陣 。4 .如果結(jié)點A有3個兄弟，而且B是A的雙親，則B的度是_4_。5 .一個有n個頂點的無向圖最多有 nX(n-1)/2條邊。6 .在二叉排序樹上進行查找，若查找不成功，則是從根結(jié)點出發(fā)走了 一條從根結(jié)點到某個一葉子 結(jié)點的路徑。7 .歸并排序是一種穩(wěn)定的排序方法，在最好和最壞情況下的時間復(fù)雜 度均為 _0(nlog2n) _。8 .對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表表示，則 鄰接表中的結(jié)點總數(shù)

15、2e。9 .在具有n個單元的循環(huán)隊列中，隊滿時共有_n-1個元素。10 .在一個單鏈表中p所指結(jié)點之后插入一個s所指結(jié)點時，應(yīng)執(zhí)行 s->next=_ p->next . 手口 p->next= s 的操作。七、簡答題（本大題共2小題，每小題5分，共計10分） 1.簡述折半查找法的基本思想。將給定值與有序表中間位置的記錄的關(guān)鍵子進行比較 ：（1）兩者相等，說明查找成功，返回該記錄的位置；否則從漸近位 置將有序表分為前后兩個子表。（1分）（2）若給定值小于該記錄的關(guān)鍵字，則說明帶查找記錄若在表中， -定排在該記錄之前，繼續(xù)在前一-子表中查找記錄。（2分）（3）若給定值大于該記錄

16、的關(guān)鍵字，則說明帶查找記錄若在表中， -定排在該記錄之后，繼續(xù)在后-子表中查找記錄。（2分） 2.簡述廣度優(yōu)先搜索。從圖中某個頂點V出發(fā)，訪問此頂點，然后依次訪問V的各個未 被訪問的鄰接點，（1分）其訪問次序可以任意，（1分）然后按照此次 序，訪問每-一個頂點的所有為被訪問過的鄰接點，直到圖中所有與 V有路徑相同的頂點都被訪問到。（1分）若此時圖中尚有頂點未被訪 問，則選擇圖中一個未被訪問的頂點作為初始點，重復(fù)上述過程，直 到圖中所有頂點都被訪問到為止。（2分） 八、解答題（本大題共5小題，共計50分）1.（8分）已知如圖1所示，請給出普里姆算法構(gòu)造最小生成樹的過程。2. （9分）已知某森林如

17、圖2所示，請寫出森林中各個樹所對應(yīng)的二 叉樹以及森林對應(yīng)的二叉樹。IDH3. (9分)下列代碼實現(xiàn)比較兩個線性表的大小，請補充橫線處的代 碼。int compare(int A, int B, int m, int n)(int i, j, ms, ns;i=0;ms=0; ns=0;while(Ai=Bi)i+ 或 i=i+1；for(j=i; j<m; j+)ms+;for(j=i; j<n; j+) ns+;if (ms=ns && ms=0 或 ns=0)return 0;if (ms=0 && ns>0 |_ _ms>0_&& ns>0 && Ai<Bi)return-1;else return1;4. （9分）已知待排序表 A=45 20 16 9 36 1128 15, 請應(yīng)用冒泡排序?qū)進行升序排序，寫出每趟排序結(jié)果。第一趟9