东北大学《842计算机专业基础》历年考研真题汇编.pdf

目录1996年东北大学计算机专业基础考研真题1997年东北大学计算机专业基础考研真题1998年东北大学计算机专业基础考研真题1999年东北大学计算机专业基础考研真题2000年东北大学计算机专业基础考研真题2001年东北大学计算机专业基础考研真题2002年东北大学计算机专业基础考研真题2003年东北大学计算机专业基础考研真题2004年东北大学计算机专业基础考研真题2005年东北大学计算机专业基础考研真题2006年东北大学计算机专业基础考研真题2007年东北大学计算机专业基础考研真题（回忆版）2009年东北大学计算机专业基础考研真题（部分）2010年东北大学计算机专业基础考研真题（部分）2011年东北大学计算机专业基础考研真题2013年东北大学计算机专业基础考研真题2014年东北大学计算机专业基础考研真题2015年东北大学计算机专业基础考研真题2016年东北大学计算机专业基础考研真题2017年东北大学计算机专业基础考研真题2018年东北大学计算机专业基础考研真题1996年东北大学计算机专业基础考研真题1997年东北大学计算机专业基础考研真题1998年东北大学计算机专业基础考研真题1999年东北大学计算机专业基础考研真题2000年东北大学计算机专业基础考研真题2001年东北大学计算机专业基础考研真题2002年东北大学计算机专业基础考研真题2003年东北大学计算机专业基础考研真题2004年东北大学计算机专业基础考研真题2005年东北大学计算机专业基础考研真题2006年东北大学计算机专业基础考研真题2007年东北大学计算机专业基础考研真题（回忆版）2009年东北大学计算机专业基础考研真题（部分）2010年东北大学计算机专业基础考研真题（部分）2011年东北大学计算机专业基础考研真题2013年东北大学计算机专业基础考研真题2014年东北大学计算机专业基础考研真题2015年东北大学计算机专业基础考研真题2016年东北大学计算机专业基础考研真题C语言部分（75分）一、简答题1简要说明while语句与do-while语句的异同。2简要说明static局部变量和自动变量的异同。3简要说明定义int*P4与定义int（*P）4的区别。二、阅读程序写出运行结果1234三、编程题1编写程序：求s12*34*5*67*8*9*1011*12*13*14*15求前n项之和，由键盘输入n。2某歌咏比赛中，有8个评委对20位选手进行评分，选手按120号进行编号，每个评委给出一个分数，在统计分数时要除去一个最低分和最高分，计算出其他评委给出分数的平均分作为最后得分。编写程序实现以下功能：评委输入，按评分输出得分最高的3位选手的编号和分数，要求程序执行时间最少。3编写程序，查找给定字符在字符串中首次出现的位置，要求：（1）不得使用有关字符串处理的库函数（2）在主函数中由键盘输入字符串以及要查找的字符，调用子函数（3）子函数完成查找任务，如果字符串中包含所查找的字符，则返回该字符串首次出现的位置，否则返回0。数据结构部分（75分）一、简答题1有两个有序线性表分别有n个和m个元素，先将其归并成一个有序表，求用最少的比较次数。2设有10*10的对称矩阵A采用压缩方式进行存储，按行优先顺序存放其下三角矩阵，假设起始元素a的地址为1，每个数据元素占两个字节，求a62的地址是多少。3设用通信的电文由10个字母组成，字母在电文中出现的频度2，7，15，19，28，39，59，67，88，100，构造哈夫曼树并给出对应字母的哈夫曼编码。4下图是一个无向图：（1）请画出以定点 为根的的广度优先生成树；（2）将该树转换为孩子兄弟链表表示的二叉树。5希尔排序和快速排序是不稳定的排序方法，试举例说明。二、编写算法1实现下述要求的locate运算的函数，设有一个带表头结点的双向链表L，每个结点有4个数据成员：指向前驱节点的指针pre，指向后继节点的指针next，存放数据的成员data和访问频度freq，所有结点的frep初始值都为0。每当在链表上进行一次Locate（L，x）操作时，则元素值为x的结点的访问频度freq加1，同时调整链表中结点间顺序，使链表中所有结点按访问频度递减的顺序排列（1）写出算法的基本思想（2）写出算法的实现2已知二叉树采用二叉链表存储结构，设计算法求二叉树中指定结点所在的层数。（1）写出算法的基本思想（2）写出算法的实现3设计算法，求邻接表存储结构的无向图的连通分量的个数，并输出每个连通分量的顶点集。（1）写出算法的基本思想（2）写出算法的实现2017年东北大学计算机专业基础考研真题C语言部分（75分）一、简答题1指针p指向了数组a，求数组第i个元素的三种表示方式。2函数的形参为指针，求对应的实参的两种表示方法。3函数声明的作用，在什么情况下自定义函数不需要函数声明。二、阅读程序写出运行结果1分别输入：1，2，3234三、编程题1编写乘法口诀。只能用构造的方法，不能用输出语句。例如：1*112*112*243*133*263*399*199*2189*3272一个整数，若从左到右和从右到左读都相同，如：121，则该数叫做“回文”。一个整数与因子之和相等，如6的因子1，2，3，6123，则该数叫做“完数”。在计算机中输入一个正整数，判断这个数是否为“回文完数”。3学生某门课程的成绩数据如下结构体实现定义：（1）建立动态链表储存学生成绩，由键盘输入所有学生的学号、成绩，人数任意，以输入学号0为结束标志。（2）分别统计60以下，6069，7079，8089，90100各分段的人数，并输出统计结果。数据结构部分（75分）一、简答题1求下列两个代码片段的时间复杂度：（1）（2）2对给出二叉树后序线索化，说明如何在后序线索二叉树上找给定结点的前驱。3已知带权有向图的邻接矩阵如下图所示，求V1到V8的关键路径，并给出求解步骤。4设哈希表成13，采用线性探测法解决冲突，哈希函数H（key）key%13（1）画出依次插入关键字25，20，36，15，41，52，29，72，67后的哈希表（2）计算等概率条件下，查找成功和查找失败的平均查找长度。5给出一组关键字序列37，56，15，28，26，61，42，36，写出下列算法从小到大排序时第一趟结果的序列（1）希尔排序（使得操作后的线性表中的元素的值都不相同）（2）快速排序（选第一个记录为轴分隔）二、编写算法1已知线性表中的元素按照递增有序排列，并以单链表做为储存结构。编写算法删除线性表中所有相同的多余元素（使得操作后的线性表中的元素的值都不相同）（1）写出算法的基本思想（2）写出算法的实现2已知一棵树采用孩子兄弟链表储存，编写算法计算该树的度。（1）写出算法的基本思想（2）写出算法的实现3编写算法根据有向图的邻接表构造相应的逆邻接表。（1）写出算法的基本思想（2）写出算法的实现2018年东北大学计算机专业基础考研真题C语言部分（75分）一、简答题1请解释define和typedef的区别并举例说明。2请写出判断字符串结束的两种方法并举例说明。3请写出数组作为形式参数时的两种实参传递方式。二、阅读程序写出运行结果12输入10 ABcdEFmnqU回车，写出输出结果34三、编程题1已知一个10*10大小的二维数组，从键盘输入数据后，请将100个数中的奇数输出到奇数行，偶数输出到偶数行，每行最多10个，考虑奇数偶数的数量不相等的情况。2输入一个长度为3000以内的英文字符，#为结束标志，单词之间可以有多个空格分开，输出最短单词及其长度。3给出某单位员工信息的结构体定义（1）从键盘批量读入员工工资信息，并存入结构体组成的链表中。（2）将员工工资升序排列，并输出该单位员工工资的中位数（中间位置的员工工资，员工数为偶数时，中位数是中间两位工资的平均数）数据结构部分（75分）一、简答题1用栈将表达式a*（bc）/de）f转换为后缀表达式，写出转换后的表达式并画出栈的变化过程。2已知二叉树的层次遍历序列为ABCDEFGHIJ，中序遍历为DGBAHECFJI，画出这棵二叉树，并画出转换后对应的森林。3有向图的顶点集VV1，V2，V3，V4，V5，V6，V7，V8，V9，边集E，（1）画出该图的邻接表（2）给出从V1开始的深度优先遍历序列4将十二个月份的英文单词Jan，Feb，Mar，Apr，May，Jun，Jul，Aug，Sep，Oct，Nov，Dec依次插入到一棵空的二叉排序树中，大小按照英文单词的顺序。写出树的构造的过程，并指明平衡调整时的类型，然后求出在等概率的情况下查找成功的平均查找长度。