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

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

C程序設(shè)計一、單項選擇題（本六題共10小題，每小題1分，共計10分。）1.

C語言中的變量名只能由字母數(shù)字和下劃線三種字符組成，且第一個字符（C）A.必須為宇母

B.必須為下劃線C.必須為字母或下劃線

D.可以是字母數(shù)字或下劃線中的任意一種2.下列數(shù)據(jù)中屬于“字符串常量”的是（B）A.‘A’

B.

"ABC"C.ABCD.’ABC’3.若intx=10,y=10,則以下程序段的輸出結(jié)果是（D）printf(“%d%d\n”,x--,--y)A.10

10

B.9

9C.910D.1094.表達式5!=3的值是（D）A.

TB.非零值C.0D.15.若in

x=2,y=3,x=4,則表達式x<z?y:z的結(jié)果是（C）A.0B.2C.3D.46.以下程序段（A）x=-1;do{x=x+x;}while(!x);A.循環(huán)執(zhí)行一次B.循環(huán)執(zhí)行兩次C.是死循環(huán)D.有語法錯誤7.下面合法的數(shù)組定義是（D）A.inta[6]={“string”};B.inta[5]={0,1,2,3,4,5};C.chara={"string"};D.chara[]={‘0’,‘1’,’2’,’3’,’4’,’5’};8.若有說明：inta[][3]={{1,2,3},{4,5},{6,7}};則數(shù)組a的第一維的大小為（B）A.2

B.3

C.4

D.不確定9.在以下敘述中，不正確的是（B）A.C語言程序總是從main(

)函數(shù)開始執(zhí)行B.在C語言程序中，被調(diào)用的函數(shù)必須在main(

)函數(shù)中定義C.程序是函數(shù)的集合，在這個函數(shù)集中包括標(biāo)準(zhǔn)函數(shù)和用戶自定義函數(shù)D.在C語言程序中，函數(shù)的定義不能嵌套，但函數(shù)的調(diào)用可以嵌套10.調(diào)用函數(shù)時，當(dāng)實參和形參都是簡單變量時，它們之間數(shù)據(jù)傳遞的過程是（D）A.實參將其地址傳遞給形參并釋放原先占用的存儲單元B.實參將其地址傳遞給形參，調(diào)用結(jié)束時形參再將其地址回傳給實參C.實參將其值傳遞給形參，調(diào)用結(jié)束時形參再將其值回傳給實參D.實參將其值傳遞給形參，調(diào)用結(jié)束時形參并不將其值回傳給實參

二、填空題(本大題共4小題，每空2分,共計12分。)1.

C語言是一種結(jié)構(gòu)化程序設(shè)計語言，程序的三種基本結(jié)構(gòu)是(順序)結(jié)構(gòu)、（選擇）結(jié)構(gòu)、（循環(huán)）結(jié)構(gòu)。2.條件“x≥y≥z”可用邏輯表達式表示為(x>=y&(y>=z)。3.設(shè)x的值為15，n的值為2，則表達式x%=(n+=3)運算后x的值是(0)。4.若有定義chars[]=”anapple”;則strlen(s)的值為(8)。三、程序填空題(本大題共3小題，每空4分，共計28分)1.下面程序是計算n個數(shù)的平均值，請?zhí)羁?。main(){inti,n;floatx,avg=0.0;scanf（“%d",&n）；for(i=0;i<n;i++)

{

scanf("%f“,&x);avg=avg+x;}

avg=avg/n;printf(“avg=%f\n",avg);}2.以下程序的功能是從鍵盤上輸人若干個學(xué)生的成績,統(tǒng)計并輸出最高成績和最低成績，當(dāng)輸入負(fù)數(shù)時結(jié)束輸入。請?zhí)羁?。main()

{

floatx,max,min;scanf("%f",&x)；max=x;min=x;while(x>=0)

{

if(x>max)max=x

if(x<min)min=x;scanf("%f",&x);}

printf("\nmax=%f\nmin=%f\n",max,min);}3.打印出1至1000中滿足其個位數(shù)字的立方等于其本身的所有整數(shù)。(本題的結(jié)果為:164125216729)。請?zhí)羁?。main()

{

inti,g;

for(i=1;<1000;i++)

{

g=i%10;if(i==g*g*g)print("%4d",i)

printf("\n");}四、閱讀程序，寫出程序的運行結(jié)果(本大題共4小題，每小題5分，共計20分}1.main(){int

a=1,b=3,c=5;if(c==a+b)printf(“yes\n”);elseprintf("

no\n");}程序的運行結(jié)果是no2.

main(){int

i,s=0;for

(i=1;i<50;i++)if

(!(%5)&&(i%3))

s=s+i;printf(“%d\n”,s);}程序的運行結(jié)果是903.main(){int

s=0,i=1;while(s<=10){s=s+i*i;i++;

}printf("%d\n",--i)}程序的運行結(jié)果是34.main()

{

charstr{]="1a2b3c";inti;

for(i=0;str[i]=‘\0’;i++)

if(str[i]>=’0’&&str[i]<=‘9’)printf("%c",str[i]);printf(“\n”);}程序的運行結(jié)果是123五、編程題(本大題共2小題，毎小題15分,共計30分)1.輸入兩個正整數(shù)m和n，求其最大公約數(shù)和最小公倍數(shù)。#include<stdio.h>main(){intm.n，r，gys，gbs;scanf("%d%d",&m,&m);//數(shù)據(jù)正確讀入，得3分gbs=m*n;r=m%n;while(r!=0)//輾轉(zhuǎn)相除法求最大公約數(shù),得6分{m=n;n=r,r=m%n;}gys=n;//最大公約數(shù)計算正確,得3分gbs=gbs/gys;//最小公倍數(shù)計算正確，得3分printf("gys=%d,gbs=%d",gys,gbs);}2．輸出以下的楊輝三角形(要求輸出10行)。1111211331146 4 11 5 10 10 5 1………#include

<stdio.h>main(

){inti,j,a[15][15];for(i=1;i<=10;++)//左右邊界賦初值正確,得5分{a[i][1]=1;a[i][i]=i;}for(i=3;i<=10;i++)for(j=2;j<=i-1;j++)//楊輝三角形計算正確,得5分a[i][j]=a[i-1][j-1]+a[i-1][j];for(i=1;i<=10;i++){for(j=1;j<=i;j++)//最終結(jié)果輸出正確,得5分print(“%4d",a[i][j]);printf("\n");}}第二部分?jǐn)?shù)據(jù)結(jié)構(gòu)(C語言版)六、單項選擇題(本大題共10小題，每小題2分，共計20分)1.以下數(shù)據(jù)結(jié)構(gòu)中，不屬于非線性結(jié)構(gòu)的是(B)A.棧

B.二叉樹C.線性表D.隊列2.算法分析的兩個主要方面是(B)A.正確性和簡明性B.時間復(fù)雜度和空間復(fù)雜度C.可讀性和文檔性

D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性3.一個順序表的第一個元素的地址是110，每個元素的長度是3，則第5個元素的地址是(C)A.113

B.119

C.122

D.1254.在一個單鏈表中，若p所指結(jié)點不是最后結(jié)點，在p之后插入s所指結(jié)點，則執(zhí)行(A)A.s->next=p->next:

P->next=s:B.s->next=p;

p->next=s;C.s->next=p->next;

p=s;D.p->next=s;

s->next=p:5.數(shù)據(jù)進出棧要遵循的原則是(D)A.棧空則進

B.棧滿則出C.先進先出D.后進先出6.有六個元素FEDCBA從左到右依次順序進棧，在進棧過程中會有元素被彈出棧。同下列哪一個不可能是合法的出棧序列(C)A.EDCFAB

B.DECABFC.CDFEBAD.BCDAEF7.二叉樹的第k層的結(jié)點數(shù)最多為(D)A.2k-1

B.2k+1C.2k-1D.2k-18.一個有n個頂點的無向圖最多有(D)條邊。A.n

B.2n

C.n(n-1)D.n(n-1)/29.采用鄰接表存儲的圖的廣度優(yōu)先搜索算法類似于二叉樹的(D)A.先序遍歷

B.中序遍歷C.后序遍歷D.按層遍歷10.在最好和最壞情況下的間復(fù)雜度均為O(nlog2n)且穩(wěn)定的排序方法是(A)A.歸并排序B.選擇排序

C.堆排序

D.快速排序七、填空題(本大題共6小題，每空2分，共計20分。)1.算法是對特定問題求解步驟的一種描述，具有5個重要特性:有窮性、確定性、可行性、輸入和輸出。2.線性鏈表的每個結(jié)點包括兩個域:其中存儲數(shù)據(jù)元素信息的域稱為_數(shù)據(jù)域_____；存儲直接后繼存儲位置的域稱為_指針域_。3.數(shù)據(jù)按“1，2，3，4"

的順序入隊，則出隊時的順序為__1，2，3，4____。4.表達式a*(b+c)-d的后綴表達式是__abc+*d-5__。5.常見的圖的存儲結(jié)構(gòu)有_鄰接矩陣_，_鄰接表__和邊集數(shù)組這三種方式。6.設(shè)有6個結(jié)點的無向圖，該圖至少應(yīng)該有__5_條邊才能確保是一個連通圖。八、名詞解釋(本大題共3小題，每小題6分，共計18分)1.雙向鏈表：在雙向鏈表的結(jié)點中有兩個指針域，其一指向直接后繼(2分)，另指向直接前趨(2分)。雙向鏈表克服了單鏈表在查找結(jié)點時只能順指針往后但不能往前查找的缺點(2分)。2.循環(huán)隊列:以列是“先進先出”表(2分),隨著入隊出隊的進行，會使整個隊列整體向后移動，當(dāng)隊尾指針移到最后，若再有元素入隊就會出現(xiàn)“假溢出”，因為此時隊頭部分還有空間可用(2分)。循環(huán)隊列是將隊列的數(shù)據(jù)區(qū)看成頭尾相接的循環(huán)結(jié)構(gòu)，可解決“假溢出”現(xiàn)象(2分)。3.二叉樹:二叉樹的每個結(jié)點至多只有兩棵子樹(3分)。并且，二叉樹的子樹有左右之分，不能隨意調(diào)換順序(3分)。九、簡答題(本大題共5小題，共計28分)1.簡述線性結(jié)構(gòu)的特點。(4分)線性結(jié)構(gòu)的特點是:在數(shù)據(jù)元素的非空有限集中，(1)存在惟一的一個被稱做“第一個”的數(shù)據(jù)元素(1分);(2)存在惟一的一個被稱做“最后一個”的數(shù)據(jù)元素(1分);(3)除第一個之外，集合中的每個數(shù)據(jù)元素均只有個前驅(qū)(1分);(4)除最后一個之外，集合中的每個數(shù)據(jù)元素均只有一個后繼(1分）2.簡述空串與空格串的區(qū)別。(6分)零個字符的串稱為“空串”（3分）由一個或多個空格組空格組成的串稱為“空格串”（3分）3.請寫出對下圖所示的二叉樹進行先序、中序、后序遍歷的結(jié)點序列。(6

分)先序:ABDGCEFH(2分)中序:DGBAECHF(2分)后序:GDBEHFCA(2分)AACCBBFEFEDDHGHG4.某二叉樹的先序序列為:ABDGECF,中序序列為:DCBEAFC，請畫出該二叉樹，并寫出其后序序列。(6分)后序序列：GDEBFCA5.請寫出下面有向圖的拓?fù)渑判蛐蛄小?6分)5523104拓?fù)湫蛄校?14253十、論述題(14分)什么是圖的最小生成樹?

(4分)針對下面的圖，請畫出用普里姆(Prim)算法構(gòu)造最小