南开大学 南开 1998年数据结构 考研真题及答案解析

南开大学C语言与数据结构考研大纲及考题真题资料南开大学C语言与数据结构考研复习都是有依据可循的,考研学子关注事项流程为：考研大纲-参考书-真题资料-复习经验-辅导-复试-导师，缺一不可。

咱们今日分享南开大学C语言与数据结构考研大纲及考题真题资料，帮助大家找到报考学校的命题规律、题型考点、分值分布、难易程度、重点章节、重要知识点等，从而使我们的复习备考更具有针对性和侧重点，提高复习备考效率。

下面是南开大学C语言与数据结构考研考试大纲815C语言与数据结构《C语言与数据结构》之C语言部分考试大纲一、考试目的本考试是全日制软件工程硕士专业学位研究生的入学资格考试之专业基础课，各语种考生统一用汉语答题。

招生院校根据考生参加本考试的成绩和其他三门考试的成绩总分来选择参加第二轮，即复试的考生。

二、考试的范围以下是本科目的考试范围。

1．数据类型，不同类型数据之间的转换和混合运算，类型定义，运算符的运算规则和优先级，表达式；2.程序结构，包括循环，嵌套，和递归；3.函数的定义，调用，和传参数；4.标准函数库中定义的常用函数，包括输入输出函数，数学计算函数，内存操作函数，字符串操作函数等；5.数组和字符串的定义和操作；6.指针的各种用法，包括对字符串指针，数组指针，函数指针等的定义和操作，将指针用作函数参数，以及使用指针进行动态内存管理；7.宏定义和头文件；8.结构体的定义和操作；9.文件操作；10.程序调试技术。

三、考试基本要求1.掌握C语言的基本语法知识。

2.熟练运用C语言进行程序设计的能力。

四、考试形式本考试包括5道编程题考试要求该部分包含5道编程题，要求考生综合运用C语言知识解决面向应用的问题。

编程题不涉及复杂的数据结构、算法，代码行数在100行以内，编程中会用到C标准库中定义的常用函数。

答题和计分要求考生用钢笔或圆珠笔做在答题卷上。

《C语言与数据结构》之数据结构部分考试大纲一、考试目的本考试是全日制软件工程硕士专业学位研究生的入学资格考试之专业基础课，各语种考生统一用汉语答题。

数据结构考研真题和答案数据结构是计算机科学中的重要基础课程，对于计算机专业的学生而言，掌握好数据结构非常关键。

考研阶段，数据结构也是一个必考科目。

本文将介绍一些常见的数据结构考研真题以及详细的答案解析，希望能帮助同学们更好地备考。

1. 简述线性表的定义，举例说明线性表的应用场景。

线性表是数据结构中最基本的一种结构，它是由相同数据类型的有限个数据元素组成的序列。

线性表的特点是存储结构唯一，数据元素之间是一对一的关系。

在实际应用中，线性表常用来表示一组某种类型的数据集合，例如存储学生的学号信息、存储职工的工号信息等。

2. 解释栈的特点及其应用场景。

栈是一种特殊的线性表，它的特点是只能在表的一端进行插入和删除操作，表的另一端称为栈顶。

栈的插入操作称为入栈，删除操作称为出栈。

栈的特点是后进先出（LIFO），即最后插入的元素最先被删除。

栈在实际应用中有很多场景，例如函数调用栈、表达式求值、撤销操作等。

3. 什么是队列？请给出队列的一个实际应用案例。

队列也是一种特殊的线性表，它的特点是只允许在表的一端进行插入操作，而在另一端进行删除操作。

队列的插入操作称为入队，删除操作称为出队。

队列的特点是先进先出（FIFO），即最先插入的元素最先被删除。

队列在实际应用中有很多场景，例如排队、任务调度、消息队列等。

4. 什么是树结构？请简要介绍树结构的一些应用。

树是一种非线性的数据结构，它由n（n>=1）个有限节点组成一个具有层次关系的集合。

树的特点是一个节点可以有多个子节点，但是只能有一个父节点，除根节点外，每个节点可以有多个子节点。

树结构在实际应用中广泛存在，例如文件系统、组织结构、网络拓扑等。

5. 解释二叉树的定义，并给出一种常见的二叉树结构。

二叉树是一种特殊的树结构，它的每个节点最多有两个子节点，分别称为左子节点和右子节点。

二叉树的定义为一个有限的节点集合，该集合可以为空，如果非空则必须满足：（1）有且仅有一个称为根的节点；（2）该节点的左子树和右子树也是二叉树。

计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编13(总分：66.00，做题时间：90分钟)一、综合题(总题数：4，分数：12.00)1.已知下列字符A、B、C、D、E、F、G的权值分别为3、12、7、4、2、8，11，试填写出其对应哈夫曼树HT的存储结构的初态和终态。

【北京工业大学1998五(10分)】__________________________________________________________________________________________正确答案：(设T是一棵二叉树，除叶子结点外，其他结点的度数皆为2，若T中有6个叶结点，试问：（分数：6.00）(1).T树的最大可能深度Kmax=?最小可能深度Kmin=?__________________________________________________________________________________________ 正确答案：(正确答案：(1)T树的最大深度：Kmax=6(除根外，每层均是两个结点)。

T树的最小深度Kmin=4(具有6个叶子的完全二叉树是其中的一种形态)。

)(2).T树中共有多少非叶结点?__________________________________________________________________________________________ 正确答案：(正确答案：非叶子结点数是5(n2=n0—1)。

)(3).若叶结点的权值分别为1，2，3，4，5，6。

请构造一棵哈曼夫树，并计算该哈曼夫树的带权路径长度wp1。

【北京邮电大学1992一、3(15／3分)】__________________________________________________________________________________________正确答案：(正确答案：哈夫曼树见右图，其带权路径长度wp1=51。

计算机专业基础综合数据结构（图）历年真题试卷汇编4(总分：58.00，做题时间：90分钟)一、综合题(总题数：7，分数：14.00)1.已知一图如下图所示：(1)写出全部拓扑排序；(2)以V1为源点，以V8为终点，给出所有事件允许发生的最早时间和最晚时间，并给出关键路径；(3)求V1结点到各点的最短距离。

【北京邮电大学2000五(15分)】__________________________________________________________________________________________正确答案：(正确答案：关键路径有3条，长17。

各事件允许发生的最早时间和最晚时间略。

V1→V2→V6→V8，V1→V3→V5→V7→V8，V1→V7→V8→V1→V4→V5→V8 (3)V1结点到其他各结点的最短距离为：2，3，6，12，10，15，16。

)2.(1)对于有向无环图，叙述求拓扑有序序列的步骤；(2)对于以下的图，写出它的四个不同的拓扑有序序列。

【南开大学1998二(12分)】__________________________________________________________________________________________ 正确答案：(正确答案：(1)对有向图，求拓扑序列步骤为： 1)在有向图中选一个没有前驱(即入度为零)的顶点并输出。

2)在图中删除该顶点及所有以它为尾的弧。

3)重复1)和2)，直至全部顶点输出，这时拓扑排序完成；否则，图中存在环，拓扑排序失败。

(2)这里使用形式化描述方法，当有多个顶点可以输出时，将其按序从上往下排列，这样不会丢掉拓扑序列。

这里只画出从顶点1开始的所有可能的拓扑序列，从顶点3开始的拓扑序列可类似画出。

)3.有向图的拓扑排序能否用图的深度搜索模式来查找?若能，请简述方法；若不能，请简述原因。

【西北大学2000二、8(5分)】__________________________________________________________________________________________ 正确答案：(正确答案：图的深度优先遍历可用于拓扑排序。

一、选择题1. 算法的计算量的大小称为计算的（ B ）。

【北京邮电大学2000 二、 3（ 20/8 分）】A．效率 B.复杂性 C.现实性 D.难度2.算法的时间复杂度取决于（ C ）【中科院计算所1998二、1（2分）】A．问题的规模 B.待处理数据的初态 C. A 和 B3.计算机算法指的是（ C），它必须具备（ B）这三个特性。

(1) A ．计算方法 B.排序方法 C. 解决问题的步骤序列D. 调度方法(2) A ．可执行性、可移植性、可扩充性 B .可执行性、确定性、有穷性C. 确定性、有穷性、稳定性D.易读性、稳定性、安全性【南京理工大学1999一、1（2分）【武汉交通科技大学1996一、1（ 4 分）】4．一个算法应该是（B）。

【中山大学1998二、1（2分）】A ．程序B．问题求解步骤的描述C．要满足五个基本特性D．A 和 C.5.下面关于算法说法错误的是（D）【南京理工大学2000一、1（1.5分）】A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D.以上几个都是错误的6.下面说法错误的是（C）【南京理工大学2000一、2（1.5分）】(1）算法原地工作的含义是指不需要任何额外的辅助空间（ 2）在相同的规模n 下，复杂度O(n) 的算法在时间上总是优于复杂度nO(2 ) 的算法（ 3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（ 4）同一个算法，实现语言的级别越高，执行效率就越低4A ． (1) B.(1),(2) C.(1),(4) D.(3)7．从逻辑上可以把数据结构分为（C）两大类。

【武汉交通科技大学1996一、4（2 分）】A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构8．以下与数据的存储结构无关的术语是（D）【。

北方交通大学2000二、1（ 2 分）】A．循环队列 B.链表 C.哈希表 D.栈9．以下数据结构中，哪一个是线性结构（D）？【北方交通大学2001一、 1（ 2 分）】A．广义表 B.二叉树 C.稀疏矩阵 D.串10．以下那一个术语与数据的存储结构无关？（ A 【）北方交通大学 2001 一、2（ 2 分）】A．栈 B.哈希表 C.线索树 D.双向链表11．在下面的程序段中，对x 的赋值语句的频度为（C）【北京工商大学2001 一、 10（ 3 分）】FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1;A． O(2n)B． O(n)C2Dn ．O(n )． O(log 2 )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 为正整数，则最后一行的语句频度在最坏情况下是（D）A. O （ n）B. O(nlogn)C. O(n3)D.O(n 2)【南京理工大学 1998 一、 1(2 分 ) 】13．以下哪个数据结构不是多型数据类型（D）【中山大学1999一、 3（1 分）】A．栈B．广义表C．有向图D．字符串14．以下数据结构中，（ A）是非线性数据结构【中山大学1999一、4】A．树B．字符串C．队D．栈15.下列数据中，（ C ）是非线性数据结构。

共2页 第1页南开大学1998硕士入学数据结构试题
1 （8分）
给出数组A ：ARRAY[3…8，2…6]OF INTEGER ；当它在内存中按行存放和按列存放时，分别写出数组元素A[i,j]的地址计算公式（设每个元素占两个存储单元）。

2（12分）
对于有向无环图
① 叙述求拓朴有序序列的步骤；
② 对于图1，写出它的四个不同的拓朴有序序列。

图1 题2图
3 （10分）
已知一棵二叉树按中序遍历时各结点被访问的次序和这棵二叉树按中序遍历时各结点被访问的次序能否唯一确定这棵二叉树的结构？为什么？若已知一棵二叉树按光序遍历时各结点被访问的次序和这棵二叉树按后序遍历时各结点被访问的次序，能否唯一确定这棵二叉树的结构？为什么？
4 （16分）
写出从图的邻接表表示转换成邻接矩阵表示的算法，用类PASCAL 语言（或C 语言）写成过程形式。

5 （16分）。

第3章栈和队列一选择题1. 对于栈操作数据的原则是（）。

【青岛大学2001 五、2（2分）】A. 先进先出B. 后进先出C. 后进后出D. 不分顺序2. 在作进栈运算时,应先判别栈是否( ①),在作退栈运算时应先判别栈是否( ②)。

当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( ③)。

为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的( ④)分别设在这片内存空间的两端,这样,当( ⑤)时，才产生上溢。

①, ②: A. 空 B. 满 C. 上溢 D. 下溢③: A. n-1 B. n C. n+1 D. n/2④: A. 长度 B. 深度 C. 栈顶 D. 栈底⑤: A. 两个栈的栈顶同时到达栈空间的中心点.B. 其中一个栈的栈顶到达栈空间的中心点.C. 两个栈的栈顶在栈空间的某一位置相遇.D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底.【上海海运学院1997 二、1（5分）】【上海海运学院1999 二、1（5分）】3. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（）。

A. 不确定B. n-i+1C. iD. n-i【中山大学1999 一、9(1分)】4. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（）。

A. i-j-1B. i-jC. j-i+1D. 不确定的【武汉大学2000 二、3】5. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，p N,若p N是n，则p i是( )。

A. iB. n-iC. n-i+1D. 不确定【南京理工大学2001 一、1（1.5分）】6. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（）A. 5 4 3 6 1 2B. 4 5 3 1 2 6C. 3 4 6 5 2 1D. 2 34 15 6【北方交通大学2001 一、3（2分）】7. 设栈的输入序列是1，2，3，4,则（）不可能是其出栈序列。

研考数据结构真题答案解析数据结构是计算机科学中重要的一门课程，它探索了在计算机内部存储、组织和操作数据的方法和技术。

研究数据结构的目的是设计出高效、稳定和可扩展的算法和数据存储方案。

在研究生招考中，数据结构也是一个常见的考点。

今天，我们将对一道数据结构的真题进行解析，帮助大家更好地理解和应用数据结构。

考题如下：给定一个整数数组nums，我们需要将数组中所有的零元素移动到数组的末尾，同时保持非零元素的相对顺序不变。

例如，给定输入数组nums=[0, 1, 0, 3, 12]，函数应该在不返回任何东西的情况下，修改输入数组为[1, 3, 12, 0, 0]。

要求：只能对输入数组进行直接的操作，不能使用额外的数组。

解析：这是一道经典的数组操作题，目标是将数组中的零移到末尾，同时保持非零元素的相对顺序不变。

题目要求不能使用额外的数组，因此我们需要在原数组上进行操作。

最简单的方法是遍历整个数组，在遇到零元素时，将其后面的所有元素向前移动一位，然后将零元素放在最后。

这个方法的时间复杂度为O(n^2)，其中n是数组长度。

但是这个方法显然不是最优解。

我们可以通过使用两个指针来解决这个问题，一个指针用来遍历整个数组，另一个指针用来指向下一个非零元素应该放置的位置。

我们可以称这两个指针为“当前指针”和“插入指针”。

我们从头开始遍历数组，如果遇到非零元素，则将其插入到插入指针的位置，并将插入指针右移一位。

遍历完整个数组后，我们将插入指针后面的位置都置零。

为了更好地理解这个过程，我们来模拟一下。

将输入数组nums=[0, 1, 0, 3, 12]分解为当前指针和插入指针两个变量，初始时都指向第一个元素0：当前指针：0 -> 1 -> 0 -> 3 -> 12插入指针：0 -> 0 -> 0 -> 0 -> 0遍历过程中，遇到第一个非零元素1，将其插入到插入指针的位置，同时插入指针右移一位：当前指针：0 -> 1 -> 0 -> 3 -> 12插入指针：1 -> 0 -> 0 -> 0 -> 0继续遍历，遇到第二个非零元素3，将其插入到插入指针的位置，插入指针右移一位：当前指针：0 -> 1 -> 0 -> 3 -> 12插入指针：1 -> 3 -> 0 -> 0 -> 0遍历完所有的元素后，将插入指针后面的位置都置零：当前指针：0 -> 1 -> 0 -> 3 -> 12插入指针：1 -> 3 -> 12 -> 0 -> 0最终得到的数组为[1, 3, 12, 0, 0]，与题目要求相符。

第2章线性表一选择题1．下述哪一条是顺序存储结构的优点？（）【北方交通大学 2001 一、4（2分）】A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示2．下面关于线性表的叙述中，错误的是哪一个？（）【北方交通大学 2001 一、14（2分）】A．线性表采用顺序存储，必须占用一片连续的存储单元。

B．线性表采用顺序存储，便于进行插入和删除操作。

C．线性表采用链接存储，不必占用一片连续的存储单元。

D．线性表采用链接存储，便于插入和删除操作。

3．线性表是具有n个（）的有限序列（n>0）。

【清华大学 1998 一、4（2分）】A．表元素 B．字符 C．数据元素 D．数据项 E．信息项4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。

【哈尔滨工业大学 2001 二、1（2分）】A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。

【南开大学 2000 一、3】A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表6．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。

A. 单链表B.单循环链表C. 带尾指针的单循环链表D.带头结点的双循环链表【合肥工业大学 2000 一、1（2分）】7．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。

则采用（）存储方式最节省运算时间。

【北京理工大学 2000 一、1（2分）】A．单链表 B．双链表 C．单循环链表 D．带头结点的双循环链表8. 静态链表中指针表示的是（）. 【北京理工大学 2001 六、2（2分）】A．内存地址 B．数组下标 C．下一元素地址 D．左、右孩子地址9. 链表不具有的特点是（）【福州大学 1998 一、8 (2分)】A．插入、删除不需要移动元素 B．可随机访问任一元素C．不必事先估计存储空间 D．所需空间与线性长度成正比10. 下面的叙述不正确的是（）【南京理工大学 1996 一、10（2分）】A．线性表在链式存储时，查找第i个元素的时间同i的值成正比B. 线性表在链式存储时，查找第i个元素的时间同i的值无关C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关11. 线性表的表元存储方式有(（1）)和链接两种。

第10章 排序排序排序一、选择题 1．某内排序方法的稳定性是指．某内排序方法的稳定性是指( )( )( )。

【南京理工大学【南京理工大学 1997 1997 1997 一、一、一、101010（（2分）】 A ．该排序算法不允许有相同的关键字记录该排序算法不允许有相同的关键字记录 B B B．．该排序算法允许有相同的关键字记录记录C ．平均时间为0（n log n n log n）的排序方法）的排序方法）的排序方法D D D．以上都不对．以上都不对．以上都不对2．下面给出的四种排序法中下面给出的四种排序法中( )( )( )排序法是不稳定性排序法。

排序法是不稳定性排序法。

【北京航空航天大学北京航空航天大学 1999 1999 1999 一、一、10 10 （（2分）】 A. A. 插入插入插入 B. B. B. 冒泡冒泡冒泡 C. C. C. 二路归并二路归并二路归并 D. D. D. 堆积堆积堆积 3．下列排序算法中，其中（．下列排序算法中，其中（ ）是稳定的。

）是稳定的。

）是稳定的。

【福州大学【福州大学 1998 1998 1998 一、一、一、3 (23 (2分)】A. A. 堆排序，冒泡排序堆排序，冒泡排序堆排序，冒泡排序B. B. B. 快速排序，堆排序快速排序，堆排序快速排序，堆排序C. C. 直接选择排序，归并排序直接选择排序，归并排序直接选择排序，归并排序D. D. D. 归并排序，冒泡排序归并排序，冒泡排序归并排序，冒泡排序4．稳定的排序方法是（．稳定的排序方法是（ ）） 【北方交通大学【北方交通大学【北方交通大学 2000 2000 2000 二、二、二、33（2分）】 A ．直接插入排序和快速排序．直接插入排序和快速排序 B B B．折半插入排序和起泡排序．折半插入排序和起泡排序．折半插入排序和起泡排序C ．简单选择排序和四路归并排序．简单选择排序和四路归并排序D D D．树形选择排序和．树形选择排序和shell 排序排序5．下列排序方法中，哪一个是稳定的排序方法？（．下列排序方法中，哪一个是稳定的排序方法？（ ） 【北方交通大学【北方交通大学【北方交通大学 2001 2001 2001 一、一、一、88（2分）】A ．直接选择排序．直接选择排序B B B．二分法插入排序．二分法插入排序．二分法插入排序C C C．希尔排序．希尔排序．希尔排序D D D．快速排序．快速排序．快速排序6．若要求尽可能快地对序列进行稳定的排序，则应选（．若要求尽可能快地对序列进行稳定的排序，则应选（A A ．快速排序．快速排序 B B B．归并排序．归并排序．归并排序 C C C．冒．冒泡排序）。