考试大纲-计算机专业基础-2020

2020年硕士研究生统一入学考试《计算机专业基础》第一部分考试说明一、考试性质计算机专业基础是计算机科学与技术学科（一级学科）、计算机技术工程领域硕士生入学考试的专业基础课。考试对象为参加东北大学计算机科学与工程学院2020年全国硕士研究生入学考试的准考考生。二、考试形式与试卷结构（一）答卷方式：闭卷，笔试（二）答题时间：180分钟（三）考试题型及比例简答题20%综合题80%（四）参考书目《数据结构》，严蔚敏，清华大学出版社，2001年。《C语言程序设计》（第3版），谭浩强，清华大学出版社,2010年。第二部分考查要点（一）数据结构考查要点1绪论1.1数据结构的基本概念和术语1.2抽象数据类型的表示与实现1.3算法和算法分析2线性表2.1线性表类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现3栈和队列3.1栈的类型定义、表示和实现3.2栈的应用3.3队列的类型定义、表示和实现3.4队列的应用4串4.1串的类型定义、表示和实现4.2串操作应用5数组和广义表5.1数组的定义、顺序表示和实现5.2特殊矩阵的压缩存储5.3广义表的定义和存储结构6树和二叉树6.1树的定义和基本术语6.2二叉树的定义、基本性质和存储结构6.3遍历二叉树和线索二叉树6.4树和森林6.5哈夫曼树及哈夫曼编码7图7.1图的定义、基本术语和存储结构7.2图的遍历7.3图的连通性和最小生成树7.4有向无环图、拓扑排序和关键路径。9查找9.1静态查找表9.2动态查找表9.3哈希表10排序10.1插入排序10.2快速排序10.3选择排序10.4归并排序10.5基数排序10.6排序方法的比较（二）C语言考查要点1、算法及其描述方法1.1算法的概念、特点1.2算法的描述方法（流程图、N-S流程图）1.3程序设计的三种基本结构；2、数据类型、运算符和表达式2.1变量和常量2.2预处理命令2.3数据类型（整型、实型、字符型）2.4算术运算符、表达式3、顺序程序设计3.1各种类型数据的格式化输入/输出方法3.2字符数据的非格式化输入/输出方法3.2顺序程序的设计4、选择结构程序设计4.1关系运算符、逻辑运算符和条件运算符if、switch语句；if语句的嵌套。5、循环结构程序设计5.1C语言三种循环结构5.2混合控制结构程序设计6、数组6.1一维数组和二维数组6.2字符串与字符数组6.3字符串函数7、函数7.1函数的定义、原型声明和调用7.2函数的嵌套调用和递归调用；7.3数组作为函数的参数；7.4变量的作用域和存储类别；7.5内部函数和外部函数。8、预处理命令8.1不带参数的宏定义、带参数的宏定义8.2宏替换、文件包含9、指针9.1指针的概念；9.2指针变量的定义与引用方法；9.3动态内存分配和释放的方法；9.4数组指针、函数指针10、结构体、共用体、文件10.1结构体、共用体和枚举数据类型10.2结构数组的定义及其应用10.3文件样题：答案必须写在答题纸上，舌顽豚思无效』-"语言部分（共75分）J,简答题（共15分’3小题）L（5分）若有定义血迎10〕；洲>7；请写出至少3种求数组r第i个元素值的方式<5分）如果想通过-个函数藐得多个返回慎，靖至少写出2神实现方法，并举例说朋$分}举例说明结构钵和共用体的区刖。二、综合题（共2。分，4小题）1、【5分）阅读以下程序，给出程序运行结果。^include<5tdiO.ll>mt{voidRinta）;昭）；return0,voidf（inta）{inti;诚4。）{5；fbr（i=l;i<-a;i++）pnntfC^d1',a）;prinlff',\nri）;L〔5分〉阅读以下程序，给出程序返行结果』^include<stdio.h>intmainf）{mts=0ditj;intMS][3]={M,13,12』L1怯9鼠九&%4,3,41,珥；&皿旬，i<5;ii）{8=0.共4页第]页for<j=0；j<J；j++)(if(i,j%5==3)break;elses=s+a[i][j]；)pr”utr%dm"+s);}return0;}(5分)阐读以下程罪，给出程序运行结果.《其中：口代表空格.)#include<stdioh>voidfunfehjir*s){inti;ft)nE;p+i)!7;i++)此〔5十2)!=W。•(s+i)^B(s+i+2);else*(s+iHzf；)inimain。{charstif}="AgeCJofCAIl”;fun(str);pu坝str};rtturn0;}(5分)闽读以下程.序，给出程序运仃结果.^include<stdio,h>inta^30,b=50;voidfiincfint*pltint*p2){pl=&a;'p2k}intrnainf)finti=lhb=5;fbr(i=l;i<=5ii-H){hinc(&i.&b);pein顷"契d.脸\n)i,b);}retum0;}三、编程题【共40分，，小题｝1、E个数的平方的兄散等了-诿数H身的打然陞被神为ETF散•：例如15*5-25,25-25-625.9376*9376^S7?n9176.茨E&04M以内的所有口守数■:金分）编耳ft遗教mljud^cMfinca[N][N]）»判断给定的矩眸是否符啻上三向斯峰条件.其中N代表N*N矩降”如染符合上三角/降条件则退回】，看可返回肌土二制矩阵伯条件为-个矩阵的f：时珀霞卜-方的元戏敬为0如：I23了05690D4200063、〔14分｝个人小金康的消费记录按如下拓构体定义stnjcecominm(intid;♦流水号unsignedpGd;■7消堂项目编夫蚀中消堂项目有唯一的捣号charp[100].;*消费项li名称.如餐或、满物骞flnatcoH;〃消费金额}靖蝙写函数voidmaxrcstfStruttconsumereccrd[NJ）,统计在始定的消般诧录structcctn&uini:returd[N]中总消费金额祐空的]带曜马泪，*似H点项H答带及点漕野金歆葡要注重的是，每个项目可能震差参质消璟行为，摊次消费行为会形成…个消费记录，数据结枸部分[共75分）一、简答题〈共叫分，4小网）1」8针〉有-个溟倒按层次鞘序存放在一维数蛆中，如下圈所示。试求：（U该例的后序遍历序机1・（2＞画出既村的先序域索二又㈱*]234^6^9010112、M分）一箱权无向图的如接牛阵如下图所示r试西出它的邻接汝利用EE算.沾生成最小生成树的过程E0-i1O'Qi0i20fria003ft02□D11n03141a00]103、18分）始出J组洗键字TH24h19,32；岳.38,I乳祯,网一氏】8；.写出下列算法从小到大择序n寸第一超结束时的序列。ci）希尔排序r第-,挠杵序的地鼠为为<■以）嫌排序f先建成-个堆,耕后从堆顼取卜一个元素后，将雎阚整-次工4、口0分）旨出对美懿字序列｛503,087,MLP512,098,897,275t陌*4拓｝建立-，棵平衡二叉排序树的过看,井写出调整平it时的靛情竞型，皓出在琴栖率-情况下查找成功府膏找灸败的平均查找长度*二、编写算法《共罚分，3小题）1.分）给定一个单链表存储的孔异整数数列.煽写算法，求出所有的域增利递减子序列的数目.例如数列L"2h6、M8.3,5.2,1T可以分为5,2）.（2±6d9）>（&rSr3）,（3,5L（5，2r1）共5个子序列，靖果为5,<1）写出雄法的基本思捆。”分）⑵写出津法实现，