《山西省2019年专升本选拔考试(C程序设计数据结构)历年真题详解.docx》由会员分享，可在线阅读，更多相关《山西省2019年专升本选拔考试(C程序设计数据结构)历年真题详解.docx（11页珍藏版）》请在三一文库上搜索。
1、山西省 2019 年专升本选拔考试（ C 程序设计数据结构）历年真题详 解第一部分 C 程序设计一、单项选择题 （本大题共 10小题， 每小题 3 分，共计 30分）C语言程序的基本结构有（A）A. 顺序结构、选择结构、循环结构B. 算法结构、数据结构、循环结构C. 算法结构、选择结构、循环结构D. 顺序结构、数据结构、循环结构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=
2、7,b=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. 已知函数调用 myFunc（f1（1）,（2,3）,（4,5,6）,（7,max（8,9）中，有（B）个实参。A. 3B. 4C. 9D. 26. 假设已指定整型变量 i=3,float 型变量 f=25, 则表达式 10+'a'+i*f 的值的类型是 （ D）A charB. intC. floatD. double7. 下列关于结构体的定义语句中，错误的是 （B）A. struct
3、xyz int x; int y; int z; struct xyz abc;B. StruCt XyZint x;int y;int z; StruCtXyZ abc;C. StrUCt XyZint x;int y;int z; abe;D. StrUCt int x; int y; int z; abc;8. 下列关于C语言文件的叙述正确的是(C)A. 文件由数据序列组成，只能构成二进制文件B. 文件由结构序列组成，只能构成文本文件C. 文件由数据序列组成，可以构成二进制文件或文本文件D. 文件由结构序列组成，可以构成二进制文件或文本文件9. 指定局部变量为“静态局部变量",
4、可用关键字(C)进行声明。A. autoB. registerC. StatiCD. 以上都不是10. 执行赋值表达式“ a=(b=3*4);"后a的值为(C)A. 3B. 4C. 12D. 以上都不是二、填空題(本大题共8小题，每空3分，共计24分)1. 已知定义：Char c='' int a=-1, b; (C的初值为空格字符)。执行"b=!c&&a;"后b的值为 0_。2. 设变量已正确定义为整数，则表达式n=i=2, +i, i+的值为_ _。3. 若有定义语句:Char str20="123456789000&
5、quot;,贝S StrIen(str)的值是_10。4. 已知语句int X=5;,则表达式X-=X*X的值为_-20_。5. 已知存在int a=0,b=9;语句，则执行完"a+&&b+;"语句后，变量b的值是_9_。6 表达式(int)(double)(72)+3.5)的值为 _6_。7. 一个变量的地址称为该变量的_ “指针” _O8. 已知字符'a'的ASCIl码是97,执行“ Char c1 ='x' ”语句和“Pint f("%dn",c1-2);"语句后，输出结果是 _120_O三
6、、程序设计题(本大题共2小题，每小题11分，共计22分)1. 已知一个函数：X : (x<1)y= 2x-1(1 x<10)13x-11(X 10)编写函数Fun1实现上式，并返回函数值。在main函数调用Fun1 函数，接收输入的X值，并输出函数值，例如：输入3.5,输出6o数调用Fun2函数，并输出指定阈值为10-6的近似值。?III用T 1 - O-+ ? ?公式求？的近似值，直到43 5 7最后一项的绝对值小于10-6为止double FUn2 (double Tnr)（2分）i 1ini ign =；I<iouhl<? Pi =0. 0；（1分）double
7、n = L Ot Ielrm = I. 0；WhileI td>( term J > = rnir)Pi = pi + irrmj（1分）n=n+2;(1分)SiglI = -Sign ；（1分）n = sig ;（I分）I Pi = Pi/4；（1分）,lur esu!；(1 分)1IIint main ()（2分）-IClUubLT re = FUn2( Ir6) ； ( 1 分Ii1Printf (t,%f nttf es)i (】分)Ireturn 0；1f I四、程序填空题（本大题共3小题，每小题8分，共计24分）1. 已知函数Fun3的部分代码如下所示，其功能是将整数数
8、组 X中的 元素按相反顺序存放，请在空格处补充程序。例如：x=1,2,3,4,则 经过Fun3函数后为x=4,3,2,1VoidFun 3（i nt*x,i nt 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 ;retur nresult;2. 已知函数Fun4的部分代码如下所示，其功能是：计算如下公式的前 n项和并作为函数值返回，请在空格处补充程序。1(IlO)n!Il= 1(I n20)0*(>20)Iong Fun4( in
9、t n)int i,j;Iongtemp=1,result=0;if(n= =0) retur n 1;if(n> 20) retur n 0;for(i=1; i<=n ;i+)temp=temp*i;result=result+temp ;retur n result;3. 已知函数Fun5的部分代码如下所示，其功能是:统计指针变量a所 指的字符串中单词的个数，并存放在指针变量b所指的变量中。其中 单词之间用空格分隔开。例如，若a所指的字符串为"I love you", 则b所指的变量的值应为3,请在空格处补充程序。void FUn5(Char *a,int
10、 *b )int i=0,num=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; 第二部分 数据结构 (C 语言版 )五、单项选择题 (本大题共 10小题，每小题 2 分，共计 20分)1. 不带头结点的单链表 head 为空的判定条件是 (A)A. head=NULLB. head->next = NULLC. head->next = headD. head! =NULL2. 一个队列的数据入列序列是 1, 2
11、, 3, 4, 则队列的出队时输出序列是(B)A. 4,3,2,1B. 1,2,3,4C. 1,4,3,2D. 2,3,4,13. 一个 n 阶的对称矩阵 , 如果以行或列为主序存入内存 , 则其容量为(C)A. nXnB. nXn/2C. nX(n+1)/2D. (n+1)X(n+1)/24. 后序遍历的顺序是 (D)A. 根结点，左子树，右子树B. 左子树，根结点，右子树C. 右子树，根结点，左子树D. 左子树，右子树，根结点5. 采用邻接表存储的深度优先搜索算法类似于二叉树的 (A)A. 前序遍历B. 中序遍历C .后序逾历D .按层遍历6. 用顺序查找法对 n 个元素进行查找，等概率情
12、况下 , 其平均查找长 度为(D)A. nB. n/2C. (n-1)/2D. (n+1)/27. 最坏情况，在第i趟直接插入排序中，要进行(C)次关键字的比较。A. i+1B. iC. i-1D. ixi8. 在理想情况下，哈希查找可通过(A)次完成。A. 1B. 2C. n/2D. (n+1)/29. 线索化二叉树中某结点没有孩子的充要条件是(B)A. D.LChiId= NULLB. D. Ltag=IC. D. Ltag=OD. D. RChiId=NULL10. 一个栈的入栈序列abcde,则栈的不可能的输出序列是(C)A. edcbaB. decbaC. dceabD. abcde
13、六、填空題(本大题共10小题，每空2分,共计20分)1. 在双链表中，每个结点有两个指针域，一个指向该结点的直接前驱_另一个指向该结点的直接后继。2. 向栈压入元素的操作是_入栈。3. 矩阵A中有S个非零元素，若S远远小于矩阵元素的总数，则称 A为稀疏矩阵。4. 如果结点A有3个兄弟，而且B是A的双亲，则B的度是_4_O5. 一个有n个顶点的无向图最多有_nx (n-1)/2条边。6. 在二叉排序树上进行查找，若查找不成功，则是从根结点出发走了 一条从根结点到某个叶子_结点的路径。7. 归并排序是一种稳定的排序方法，在最好和最坏情况下的时间复杂 度均为 _0(nlog2n) _。8. 对于一个
14、具有n个顶点和e条边的无向图，若采用邻接表表示，则 邻接表中的结点总数_2e_ o9. 在具有n个单元的循环队列中，队满时共有_n-1个元素。10. 在一个单链表中P所指结点之后插入一个S所指结点时，应执行s->next=_ p->next _ 和 p->next= S 的操作。七、简答题（本大题共2小题，每小题5分,共计10分）1. 简述折半查找法的基本思想。将给定值与有序表中间位置的记录的关键子进行比较：（1）两者相等，说明查找成功，返回该记录的位置；否则从渐近位 置将有序表分为前后两个子表。（1分）（2）若给定值小于该记录的关键字，则说明带查找记录若在表中， -定排在该
15、记录之前，继续在前一-子表中查找记录。（2分）（3）若给定值大于该记录的关键字，则说明带查找记录若在表中，-定排在该记录之后，继续在后-子表中查找记录。（2分）2. 简述广度优先搜索。从图中某个顶点V出发，访问此顶点，然后依次访问V的各个未 被访问的邻接点，（1分）其访问次序可以任意，（1分）然后按照此次 序，访问每-一个顶点的所有为被访问过的邻接点，直到图中所有与 V有路径相同的顶点都被访问到。（1分）若此时图中尚有顶点未被访 问，则选择图中一个未被访问的顶点作为初始点，重复上述过程，直 到图中所有顶点都被访问到为止。（2分）八、解答题（本大题共5小题，共计50分）1.（8分）已知如图1所示
16、,请给出普里姆算法构造最小生成树的过程。112. （9分）已知某森林如图2所示，请写出森林中各个树所对应的二叉树以及森林对应的二叉树。3. (9分)下列代码实现比较两个线性表的大小，请补充横线处的代码。intComPare(i ntA, int B, int m, int n)int i, j, ms, ns;i=0;ms=0; n s=0;WhiIe(Ai=Bi)i+ 或 i=i+1；for(j=i; j<m; j+)ms+;for(j=i; j<n; j+)n s+;if (ms=ns && ms=0 或 ns=0)return 0;if (ms=0 &
17、& ns>0 |_ _ms>0_&& ns>0 && Ai<Bi)return-1;elsereturn1;4. （9分）已知待排序表 A=45 2016 9 36 112815, 请应用冒泡排序对A进行升序排序，写出每趟排序结果。第一趙9 45 20 16 11 36 15 28(I分)第二趙9 11 45 20 16 15 36 28（1分）第三趙9 Ii (5 45 20 16 28 361(1 >第四趟9 11 15 16 45 20 2S 36（1分）第五趟9 Jl 16 20 45 28 36（1分）第六趙9 11 15 16 20 28 45 36(2分第七JeI9 11 15 16 2U 28 36 45(2分5、（ 15 分）设查找的关键字序列为（19,13,18,27,66,6,56,11,83）, 请画出该关键字序列二叉树排序树的生成过程。(2> <2>