2013年四川师范大学硕士考研专业课真题832C语言程序设计与数据结构.pdf

1、四 川 师 范 大 学13年攻读硕士学位研究生入 学 考 试 试 题专业代码:%迎12型卫835迎迎5211,085212专业名称:计算机应用技术,信启 、安全,软件工程计算机技术、软件工程(专业学位)考试科 目代码:考试科 目名称: C语言程序设讠(本试卷共 七 大题 30 小题,满分150 分)(1)试题和答卷分离,所有答题内容须写在答题纸上,写在试题或草稿纸上的内容无效;(2)答题时,可不抄题,但须写明所答试题序号;(3)答题时,严禁使用红色笔或铅笔答题。第一部分C语言程序设计(共75分)一、填空题(本大题共5小题,每小题1分,共5分)l ,一个C程序一股由若干个函数构成,其中至少应包含

2、一个函数。程序中调用Go s O,14)函数时,需要包含的头文件是有枚举类型定义如下c n u m (a ,b =3,G,d =7);贝刂 枚举值c 相当于数值设i n t F8,y ;,则执行y =x =Q饭:;后y 的值是5,设 山盯s 20=”My ”;则执行 哎r c a t l s ,”SLl l l ;后s 的内容是 。二、单项选择题(本大题共5小题i 每小题2分,共10分 。在每小题列出的四个备选项中只有一个是符合题目要求的。错选、多选或未选均无分)1.执行下列程序后输出的结果是:( )i n t a 313=(1),(2),(3);i n t b 33=(1,2,3);#i n

3、 c l u d c s t d j o ,h ”v o i d m 加n ()(p n t “%d Xn ,盯l l O+b 0l O);)A) 01 C)2 D)3是否为小写字母的正确表达式为:( )2.判断c l l 盯型变量c 1A) a :=c 1【z B) Ca )=c l )(Z=c 1)D) l Gl )=a )&o 1=a l &01Zl3.当运行 以下程序时,从键盘输入:A陀MA回车),则输出为:( )#i n Gl u d e s t d i o h ”v o i d m a i n ()(Gh a r c h ;w h i l c (c h =g Ct Ch a r (

4、)!=n )(i RCh )=A&c h =r &c h =z ) c h =c h -32;p r 双“%G,G;)p r i n t f t n D;)A) a h AMa B) a HAm a C) a h a MA D) a h a m a4,语句i n t (*q )();的含义是( )。A) q 是一个指向函数的指针变量,该函数的返回值是一个整型数据B) q 是指针变量,指向一个整型数据C) q 是一个指向一维数据的指针变量D) q 是指针函数5.设#d e f l n e S(r ) 314苄r *r , 贝 刂 S是( )A) 函数名 B) 函数调用C) 无参的宏名 D) 带参

5、的宏名三、程序填空题(请根据每小题前的说明及要求9参照程序中的相应注释,在划线部分填上适当的C语言的表达式或语旬,完成程序,本大题共2小题,每空3分,共15分。)1,根据对n 的输入,求卜2+3十+n 的和。#i n c l u d e s t d i o 。 h ”f l o 荻s u m (i n t x )(i n t i ;n 。a t s ;s =0;Rr (i =l ;i (=x ;i +)s +=i ;)o i d m 耐n o(i n t n ;s c a n 叉%d 1p n t K%n ,s u m );)2,使用二维数组形成一个五行的杨辉三角形并输出。11 11 2 11

6、33114641#d e f l n e N5#i n c l u d e “s t d i o 。 h ”l a i n ()(i n t l ,n ,a l N1Nl ;m =0;n N;m +町l l l l l Ol =丬l m l l m l =f o r (n =1;n m ;n +)a l l l n l =盯l m 1n 刂+)f o r (m =0;m (N;m +)(f o r (n =0;n =m ;n +) p o n t f l %4d ,a m In );_;)四、程序设计题(本大题共3小题,每小题15分,共45分)1,求1到 1000之间的奇数之和及偶数之和,并将

7、二者输出。(15分)2,编程求s =a +a a +a a a +a a a (共n 个 a )的值,其中a 是一个数字。例如,当F3,n =5时,F3+33+333+3333+33333,a 和n 由键盘输入。(15分)3,用指针作函数参数,编程求一维数组中的最大和最小的元素值。下面已将主函数和求最大最小值函数m a x m i n l )的原型给出,要求编写求最大最小值函数m a x m 以)的定义实现部分。(15分)#d e f l n e N10Ia i n ()ro i d m a x m i n (i n t a r r ,i n t *p t 1,i n t 米p 佗,i n t

8、 n );i n t a r r a y N= 10,7,19,29,4,0,7,35,6,21),沐p l ,米p 2,a ,b ;p l =&钆p 2=&b ;m a Xl u i 盯r a y ,p 1,N);p l l t “m a x =%d ,m i n =%d ”,a ,;)第二部分 数据结构(共%分)五、填空题(每 j 、题2分,共分)1,当线性表的元素总数基本稳定,且很少进行插入和删除操作,但要求以最快的速度存取线性表中的元素时,应采用 存储结构。2.如果输入序列为123,利用栈结构,不能得到的输出序列是 。3,通常设置一个_结构作为数据缓冲区来解决计算机主机与外部设备之间速

9、度不匹配问题。4,在有m 个单元的循环队列Q中,假定Q,o n t 和Q,r e a r 分别为队头指针和队尾指针,则判断队满的条件5,两个串相等的充分必要条件是6.对出现次数分别是1,2,3,5的4个字符构造一棵h u f f l l l a n 树的带权路径长度是_。7.一稞具有n 个结点的完全二叉树的树的深度是 。8.求解单源点最短路径的D刂l c s t r a 算法的时间复杂度为 。9.对线性表进行二分查找时,要求线性表必须采用顺序存储结构,且数据元素_。10,序列(6,刀,13,97,76,65,36,1Q0) (填:是/不是)一个小根堆。为诋六、简答与应用题(每小题10分,共30

10、分)1,对图I所示的二叉树T,要求:(10分)(1)画出该二叉树的顺序存储表示。(2)画出该二叉树的二叉链表表示。(3)写出该二叉树的先序、中序和后序遍历序列。2己知一个有向图G的邻接表存储表示如图2所示:(10分)要求: 图2(1)计算每个顶点的入度和出度。(2)写出从顶点 出发进行深度优先遍历得到的顶点序列。(3)判断是否该有向图是否有环?如果没有,请写出一个拓扑序列。3.设关键字集合(19,14,23,I,42,84,27,55,79),哈希地址空间为HT0 14,要求:(10分)(1)写出采用除留余数法的哈希函数H(k y )的函数形式。(2)列出每个关键字的直接哈希地址(即哈希函数值

11、)。(3)拟选用二次探测再散列的方法处理冲突,请构造该哈希表。(4) 计算在等概率情况下查找成功时的平均查找长度ASL。七、算法设计与分析题(l 题15分,2题10分,共25分)1 己知线性表的单链表存储定义如下:(15分)t y p e d c f i n t El e m /p e ;t y p e d e f s t r u c t LNo d e (El e m Ty p e d 狨%s t r u Gt LNo d e 米n e Xt ;)LNo d e ,米Li n k Li s t ;设计算法 o i d De l e t e m a x (Li n k Li 哎&D删除一个带头

12、结点的非空单链表L中数据值最大的结点(若有多个,只需删除一个)的尽可能高效的算法,并分析算法的时间复杂度。2 己知二叉树的二叉链表存储表示如下:(10分)t y p c d c f i n t TEl e m Tv p e ;t y p e d e f s t r u c t Bi TNo d e (TEl e m /p e d a t a ;u c t Bi o d c *l c l l i l d ,*r c h i l d 左右指针标志)Bi TN0d e ,衤Bi Tr e e 设计算法v o i d c h a n g e l e R g l l t (B汀r e e &D将二叉链表表示的二叉树T的左右子树进行交换。q | 、|