下载文档原格式
北京工业大学1999年硕士研究生入学考试试题考试科目：数据结构一、（26分）填空、选择（一个或多个）题，1-6题每小题2分：1下面的叙述中，不正确的是（）A关键活动不按期完成就会影响整个工程的完工时间。
B任何一个关键工程提前完成，将使整个工程提前完成。
C所有关键活动都提前完成，则使整个工程提前完成。
D提些关键活动若提前完成，则将使整个工程提前完成。
2 下面的排序算法中，不稳定得是（）A 起泡排序B 折半插入排序C简单选择排序D希尔排序E基数排序F堆排序。
3包含结点A，B，C的二叉树有-----------种不同的状态，---------种不同的二叉树。
4包含结点A，B，C的树有------种不同形态，------种不同的树。
5分块检索中，若索引表和各块内存均用顺序查找，则有900各元素的线性表分成-----块最好：若分成25块；其平均查找长度为--------。
6下面的程序段中，对ｘ的赋值语句的频度为------------（表示为n的函数）ＦＯＲ Ｉ：＝ １ＴＯ Ｎ ＤＯＦＯＲ Ｊ：＝１ ＴＯＩ ＤＯＦＯＲ Ｋ：＝Ｉ ＴＯ Ｊ ＤＯ ｘ：＝ｘ＋ＤＥＬＴＡ；７（８分）设有字符序列Ｑ Ｈ Ｃ Ｙ Ｐ Ａ Ｍ Ｓ Ｒ Ｄ Ｆ Ｘ要求按字符升列排序：采用初是长为４的希尔（３ｂｅｌｌ）排序，一趟扫描的结果是――――――――― 采用以元素为分界元素的快速排序，一躺扫描的结果是------------。
8（6分）已知广义表：A-（0），B-（），C-（a，b，c，d），D-（A，B，C）它们的存储结构图为（接两种结构种的任一种即可）：二（6分）编写递归程序将二叉树逆时针旋转90度打印出来。
如右图：（要求用类PASCAL 语言，并描述结构）。
三 （8分）用依次输入的关键字13，29，41，19，5，1，7和6建一棵三阶B-树，画出建该树的变化过程示意图（每插入一个结点至少用一张图）。
四（共20分）已知顶点1——6和输入边与权值的序列（如右框中）： 2 4 6 每行三个数表示一条边的两个端点和其权值，共11行。
数据结构1800题（答案全）一、选择题1. 算法的计算量的大小称为计算的（B ）。
【北京邮电大学2000二、3 （20/8分）】A．效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（C ）【中科院计算所1998 二、1 （2分）】A．问题的规模 B. 待处理数据的初态 C. A和B3.计算机算法指的是（1），它必须具备（2）这三个特性。
(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法(2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性D. 易读性、稳定性、安全性【南京理工大学1999 一、1（2分）【武汉交通科技大学1996 一、1（4分）】4．一个算法应该是（）。
【中山大学1998 二、1（2分）】A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A 和C.5. 下面关于算法说法错误的是（）【南京理工大学2000 一、1（1.5分）】A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的6. 下面说法错误的是（）【南京理工大学2000 一、2 （1.5分）】(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1) B.(1),(2) C.(1),(4) D.(3)7．从逻辑上可以把数据结构分为（）两大类。
【武汉交通科技大学1996 一、4（2分）】A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构8．以下与数据的存储结构无关的术语是（）。
【北方交通大学2000 二、1（2分）】A．循环队列 B. 链表 C. 哈希表 D. 栈9．以下数据结构中，哪一个是线性结构（）？【北方交通大学2001 一、1（2分）】A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串10．以下那一个术语与数据的存储结构无关？（）【北方交通大学2001 一、2（2分）】A．栈 B. 哈希表 C. 线索树 D. 双向链表11．在下面的程序段中，对x的赋值语句的频度为（）【北京工商大学2001 一、10（3分）】FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1;A．O(2n) B．O(n) C．O(n2) D．O(log2n)12．程序段FOR i:=n-1 DOWNTO 1 DOFOR j:=1 TO i DOIF A[j]>A[j+1]THEN A[j]与A[j+1]对换；其中n为正整数，则最后一行的语句频度在最坏情况下是（）A. O（n）B. O(nlogn)C. O(n3)D. O(n2) 【南京理工大学1998一、1(2分)】13．以下哪个数据结构不是多型数据类型（）【中山大学1999 一、3（1分）】A．栈B．广义表C．有向图D．字符串14．以下数据结构中，（）是非线性数据结构【中山大学1999 一、4】A．树B．字符串C．队D．栈15. 下列数据中，（）是非线性数据结构。
北京工业大学2013回忆版试题首先题型：DS选择10分，一个一分，填空10个一个2分共20分，第三题为解答40分，4个题，第四题2个题一个15分。
C3个程序，读程序写结果，并指出程序的不足之处一个10分空30分算法描述题用文字描述的20分，要求写出程序一、数据结构(100分)选择题10分，10个题考的知识顺序可呢不一样，选项也可能顺序不一样,（忘了，记不清了，都是很基础的，希望其他的人补上吧）1. 下列排序算法那个是稳定的a，简单b快速c堆排序d冒泡（d）记住口诀吧，自己想的（简单希尔快速堆，或者杰西快堆，不稳定）2. 堆排序是急于什么来排序的a插入b选择c归并d3. 抽象数据结构的定义4.填空20分，10个题（其他的网了）1. 算法可行性的定义2. 快速排序的时候为什么需要事先将所有的数重新洗牌打乱顺序3. 迷宫算法为什么用栈保存走过的路径4. 对应的一个二叉树的线序ADBCFGECFMI中序DBCFGEACFIM请问对应的数有几颗，（中序中前边的那些字母顺序网了太多了，但不影响做题，A 右边的那4个字母应该是对的）5. 一个M*N矩阵，用行压缩存储，第一个存在了Loc（0,0），每个站L个单元，求aij的存储位置解答题第一题、某本数据结构的课本的目录是1．XXXXXX1.1XXXXXX1.2XXXXXX2．XXXXXX2.1XXXXXXX2.2XXXXXX……可以写出他的广义表表示为（1（1.1,1.2），2（2.1,2.2），……）（1）广义表的子表个代表目录的什么（2）广义表的广度深度个代表目录的什么（3）为广义表设计数据结构第二题（1）树经常转化为二叉树来进行操作，为什么（2）数的子孙节点转化成二叉树之间是什么关系（用例子说明）（3）数的兄弟节点在转化成二叉树的节点之间是什么关系（用例子说明）第三题对于一个有向图的邻接矩阵，（1）画出对应的有向图（2）写出3条从节点1到节点7的路径，以及路径长度（3）按照dijkstra算法思想，写出节点1到7的最短路径记忆路径长度第四题对于归并排序，当子快长度小于给定一个阙值时，（1）小于给定一个阙值时为什么用直接插入排序更好？（2）对于直接插入排序以及快速排序，从时间复杂度以及空间复杂度角度分析，用那个好？（还是基于归并排序）算法题（30分，一个15分）第一个给定一个二叉排序数，要求将二叉排序数的各个节点的数按从高到底的顺序插入到链表里比如：二叉树的中序序列为（1,2,4,6,8）则对应链表（8,6,4,2,1）题给了二差排序树的结构体，以及链表的结构体，假设链表头结点已给出了Int Convert(Bitree t,LinkList&H)第二个：现在手机GPS越来越普及了，输入对应的起点终点就可以看到从哪到哪的最短路径，以及最短时间（1）.问若对数据进行处理（还是设计来）需要事先知道那些数据（2）请对这设计数据结构二．C语言部分（50分）一．3个程序，根据程序写出结构来，并指出程序的不合理的地方一个10分二．一个算法描述题：（记得不是很清楚了，有个大体思路）大体思路如下：输入若干文本行，保存于line里，并用buf输出相应的行号与内容步骤1.n=0，x=1，i=0；2．Gets（lines）3．n = strlen(lines);4.if(n=0) 执行第7步（这里应该是执行第13步，可能有些小的步骤掉了，凑不出13步了）5.if(n>x)清空buf，X=n；将line里面的内容以及行号保存到buf6if（n=x）将line里面的内容以及行号保存到buf7 将buf里的内容输出1，描述算法的功能2，设计算法风华哥，我也来凑个热闹，提供个版本供大家参考：（2013北工大学硕&部分专硕考题情况）C语言：50分DS数据结构：100分总体来说不太难。
北京工业大学896数据结构目录目录 (1)1.1真题分析 (2)1.2 真题剖析 (2)1.2.1 2016年真题 (2)通过真题的学习和掌握，可以帮助学生把握考试重点。
每年的考点在历年试题中几乎都有重复率，因此，通过对历年真题的把握，可以掌握今年考试的重点。
另外，可以通过对历年真题的学习，把握出题者的思路及方法。
每种考试都有自己的一种固定的模式和结构，而这种模式和结构，通过认真揣摩历年真题，可以找到命题规律和学习规律。
因此，本部分就真题进行详细剖析，以便考生掌握命题规律、知悉命题的重点、难点、高频考点，帮助考生迅速搭建该学科考试的侧重点和命题规则。
1.1真题分析综合来说，896数据结构这几年的题型变化不大，主要有5种题型，包括单项选择题（20分，每题2分），填空题（20分，每题2分），解答题（50分，每题10分），算法阅读题（15分，每题5分），算法设计题（45分，每题15分）。
1.2 真题剖析1.2.1 2016年真题一单项选择题（20分，每题2分）【题目】1【解题】A【题目】2【解题】C【题目】3【解题】A 【题目】4【解题】B 【题目】5【解题】B【题目】6【解题】D【题目】7【解题】C【题目】8【解题】A【题目】9【解题】C【题目】10【解题】A二填空题（20分，每题2分）【题目】1【解题】线性结构、树状结构、图状结构【题目】2【解题】顺序表【题目】3【解题】O（n）【题目】4【解题】存储空间的浪费【题目】5【解题】n-1【题目】6【解题】d【题目】7【解题】n(n-1)【题目】8【解题】n【题目】9【解题】27【题目】10【解题】h+1三解答题（50分，每题10分）【题目】1【解题】【题目】2【解题】【题目】3【解题】【题目】4【解题】【题目】5【解题】四算法阅读题（15分，每题5分）【解题】五算法设计题（45分，每题15分）【题目】1【解题】【题目】2【解题】【题目】3【解题】。
2019 年北京工业大学895《计算机学科专业基础》考试大纲一、考试要求计算机学科专业基础考试大纲适用于北京工业大学信息学部（0812）计算机科学与技术学科、（0839）网络空间安全、北京未来网络科技高精尖创新中心（085211）计算机技术（专业学位）的硕士研究生招生考试。
考试内容主要包括两部分：数据结构与语言程序设计，这两门课程是计算机科学与技术学科的重要基础课程。
数据结构的考试内容主要包括基本数据结构、排序、索引、检索、高级数据结构等内容，从逻辑结构的角度包括线性表、栈、队列、二叉树、树和图等各种基本数据结构；从算法的角度包括各类排序、检索和索引算法。
要求考生对其中的基本概念有很深入的理解，掌握数据结构与算法的基本概念、合理组织数据的基本方法、高效处理数据的基本算法、并具备面对实际问题选择恰当数据结构与相应算法的能力。
C 语言程序设计部分的考试内容主要包括C 语言程序设计的基础概念、方法和技巧。
要求考生熟练掌握高级语言的基本控制结构、数据组织和程序组织形式。
熟练使用C 语言的结构体、指针、文件等。
具有基本的计算思维能力，熟悉简单算法，能够构建实际问题的模块化解决方案。
二、考试内容数据结构部分：1．数据结构的相关概念、算法概念、算法性质及算法分析（时间复杂度与空间复杂度）；2．线性表逻辑结构定义、存储结构的表示，以及在特定存储结构下线性表基本运算的算法实现；3．栈与队列的逻辑结构定义、存储结构的表示，基本操作特点，栈与队列的基本应用；4．串的逻辑结构定义，基本操作的含义与实现；5．数组定义及其顺序存储，矩阵的压缩存储，广义表定义及存储结构；6．树的定义与存储结构，二叉树的定义与性质、存储结构，二叉树遍历算法（三序遍历与按层遍历），赫夫曼树与赫夫曼编码以及二叉树基本算法的实现与应用；7．图的定义与术语，图的存储结构，图的遍历（深度优先搜索与广度优先搜索），最小生成树、拓扑排序以及最短路径的求解；8．查找的相关概念，静态查找表（顺序表的查找与有序表的查找），动态查找表（二叉排序树），B-树，B+树，AVL 树，哈希表的相关概念；9．排序的相关概念，掌握插入排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序算法的执行过程、时空复杂度、稳定性以及使用场合。
北工大考研复试班-北京工业大学信息学部计算机科学与技术考研复试经验分享北京工业大学(Beijing University of Technology)，简称"北工大"，是中国北京市人民政府直属的一所以工为主，理、工、经、管、文、法、艺术等学科门类相结合的全国重点大学，是国家"211工程"重点建设院校，入选"卓越工程师教育培养计划"、"111计划"，设有研究生院和国家大学科技园。
北京工业大学创建于1960年，初设机械、电机、无线电、化工、数理5个系，历经多次整合兼并，逐渐形成了理工、经管、文法相结合的多科性体制;学校于1981年成为第一批硕士学位授予单位，1985年成为博士学位授予单位。
启道考研复式班根据历年辅导经验，编辑整理以下考研复试相关内容，希望对广大考研复试学子有所帮助，提前预祝大家复试金榜题名！专业介绍计算机科学与技术，本专业主要学习计算机科学与技术包括计算机硬件、软件与应用的基本理论、基础知识和基本技能与方法，接受从事计算机应用开发和研究能力的基本训练等。
招生人数与考试科目复试时间地点3月22日各学院（部、所）复试安排（含相关学科/专业调剂系统开通时间、信息公示栏等）各学院（部、所）复试时间如有微调，以学院（部、所）通知为准。
复试内容复试内容包含外语、专业课与综合面试三个方面：外语：所有复试考生均需参加外语听、说能力的测试。
测试均由各学院（部、所）、学科/专业结合专业知识在复试时进行。
专业课：专业笔试科目考生可登录我校研招网查阅。
专业课全面考核考生对本学科（专业）理论知识和应用技能掌握程度，利用所学理论发现、分析和解决实际问题的能力（有条件的可测试考生实验和操作技能）。
综合面试：包括专业素质与综合素质，具体包括大学阶段学习情况及成绩、对本学科发展动态的了解、在本专业领域发展的潜力，以及分析问题能力、实际经验、人文素质、举止及礼仪、心理状况等。
北京市考研计算机科学专业数据结构常考题数据结构是计算机科学专业中的基础课程之一，对于考研的学生来说，掌握数据结构常考题是非常重要的。
本文将介绍一些北京市考研计算机科学专业数据结构常考题，并附上详细的解答过程。
1. 栈和队列相关题目题目一：编写一个函数，判断输入的括号序列是否合法。
括号序列由"( )"、"[ ]"和"{ }"组成，要求括号必须按照正确的顺序闭合。
解答一：我们可以利用栈来解决这个问题。
遍历输入的括号序列，当遇到左括号时，将其压入栈中；当遇到右括号时，判断栈顶的括号是否与之匹配，如果匹配，则将栈顶的左括号弹出，继续检查下一个字符；如果不匹配，则返回false。
最后，如果栈中没有元素，表示所有的括号都匹配，返回true；否则，返回false。
题目二：给定一个字符串，判断其是否为回文字符串。
解答二：同样可以利用栈来解决。
将字符串的每个字符依次压入栈中，然后依次弹出栈顶元素与字符串的字符比较，如果全部相等，则说明是回文字符串；否则，不是回文字符串。
2. 链表相关题目题目三：给定一个链表，判断是否存在环。
解答三：可以使用快慢指针来解决。
定义两个指针，一个慢指针每次移动一步，一个快指针每次移动两步。
如果链表中存在环，那么两个指针最终会相遇；如果链表中不存在环，那么快指针会先到达链表的末尾。
题目四：给定一个链表和一个目标值，删除链表中所有等于给定值的节点。
解答四：遍历链表，如果节点的值等于目标值，删除该节点。
需要注意的是，删除节点时需要更新链表的指针，使得前一个节点指向后一个节点。
3. 树相关题目题目五：给定一个二叉树，求其前序遍历。
解答五：可以使用递归或者非递归的方式实现前序遍历。
递归实现时，先输出当前节点的值，然后递归遍历左子树，最后递归遍历右子树。
非递归实现时，使用栈来辅助遍历，先将根节点压入栈中，在栈不为空的情况下进行循环，每次循环弹出栈顶元素，并输出其值，然后将右子节点压入栈中，最后将左子节点压入栈中。
