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

1、山西省 2019 年專升本選拔考試（ C 程序設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)）歷年真題詳解第一部分C程序設(shè)計(jì)一、單項(xiàng)選擇題 （ 本大題共 10 小題， 每小題 3 分，共計(jì)30 分 ）C語(yǔ)言程序的基本結(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. 正確的定義語(yǔ)句是（ C）A double a; b;B. double a=b=7.0;C. double a=7,b=

2、7;D. double,a,b;4. 若有定義語(yǔ)句:int a=1,3,5,7,9,i=4; 則錯(cuò)誤的引用是（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） 個(gè)實(shí)參。A.3B.4C.9D.26. 假設(shè)已指定整型變量i=3,float 型變量 f=25, 則表達(dá)式 10+'a'+i*f的值的類型是（ D）A charB. intC. floatD. doubleA. 下列關(guān)于結(jié)構(gòu)體的定義語(yǔ)句中，錯(cuò)誤的是 （ 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語(yǔ)言文件的敘述正確的是 (C)A.文件由數(shù)據(jù)序列組成，只能構(gòu)成二進(jìn)制文件8 .文件由結(jié)構(gòu)序列組成，只能構(gòu)成文本文件C.文件由數(shù)據(jù)序列組成，可以構(gòu)成二進(jìn)制文件或文本文件D.文件由結(jié)構(gòu)序列組成，可以構(gòu)成二進(jìn)制文件或文本文件9 .指定局部變量為“靜態(tài)局部變量“，可用關(guān)鍵字(C)進(jìn)行聲明。A.

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

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

6、每小題11分，共計(jì)22分)1 .已知一個(gè)函數(shù)：x ； (x<1)y= <2x-1(1<x<10)l3x-11(x >10)編寫函數(shù)Fun1實(shí)現(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,實(shí)現(xiàn)公式求 兀的近似值，直到發(fā)現(xiàn)某一項(xiàng)的 絕對(duì)值小于指定閾值為止（該項(xiàng)不累加），并返回近似值。在main函數(shù)調(diào)用Fun2函數(shù)，并輸出指定閾值為10-6的近似值。用？=1- 1+1- 1+?公式求?的近似值，直到43 5 7最后一項(xiàng)的絕對(duì)值小于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分，共計(jì)24分）1 .已知函數(shù)Fun3的部分代碼如下所示，其功能是將整數(shù)數(shù)組 x中的 元素按相反順序存放，請(qǐng)?jiān)诳崭裉幯a(bǔ)

9、充程序。例如：x=1,2,3,4,則 經(jīng)過(guò)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的部分代碼如下所示，其功能是：計(jì)算如下公式的前 n項(xiàng)和并作為函數(shù)值返回，請(qǐng)?jiān)诳崭裉幯a(bǔ)充程序。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)計(jì)指針變量a所 指的字符串中單詞的個(gè)數(shù)，并存放在指針變量b所指的變量中。其中 單詞之間用空格分隔開(kāi)。例如，若a所指的字符串為"I love you", 則b所指的變量的值應(yīng)為3,請(qǐng)?jiān)诳崭裉幯a(bǔ)充程序。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 語(yǔ)言版 )五、單項(xiàng)選擇題 ( 本大題共 10 小題，每小題 2 分，共計(jì) 20 分 )1. 不帶頭結(jié)點(diǎn)的單鏈表head 為空的判定條件是(A)A. head=NULLB. head->next = NULLC. head->next = headD. head! =NULL2. 一個(gè)隊(duì)列的數(shù)據(jù)入列序列是1, 2, 3, 4, 則隊(duì)列的出隊(duì)時(shí)輸出序列是( B

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

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

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

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

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

17、圖2所示，請(qǐng)寫出森林中各個(gè)樹(shù)所對(duì)應(yīng)的二 叉樹(shù)以及森林對(duì)應(yīng)的二叉樹(shù)。IDH3. (9分)下列代碼實(shí)現(xiàn)比較兩個(gè)線性表的大小，請(qǐng)補(bǔ)充橫線處的代 碼。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, 請(qǐng)應(yīng)用冒泡排序?qū)進(jìn)行升序排序，寫出每趟排序結(jié)果。第一趟9