2002年大连海事大学数据结构与程序设计考研真题-考研真题资料

⼤连海事⼤学2005年硕⼠研究⽣招⽣考试试题（数据结构）⼤连海事⼤学2005年硕⼠研究⽣招⽣考试试题考试科⽬：数据结构适⽤专业：计算机应⽤技术、计算机软件与理论考⽣须知：1、所有答案必须写在答题纸上，写在试题纸上⽆效；2、考⽣不得在答题纸上作与答题内容⽆关的标记，否则试卷作废。

⼀、判断下列叙述是否正确。

请写出题号并⽤“√”“×”回答（共20分，每⼩题1分）1、若（u,v）是连通⽹络的⼀条权值最⼤的边，是不论采⽤何种⽅法构造该⽹络的最⼩⽣成树，所构造出的最⼩⽣成树⼀定不包含（u,v）这条边。

2、算法是具有有穷性、确定性、可⾏性、0个或多个输⼊、1个或多个输出特性的⼀组规则。

操作系统⼀旦被启动后就永远处在⼯作或等待状态，所以，实现“操作系统”的⼀组规则不能称为算法。

3、给定n个不同权值的结点，则依据这n个结点构造的Huffman树的结构是唯⼀的。

4、在线索⼆叉树中，根据线索可以找到树中任何⼀个结点在相应遍历序列中的直接前驱或直接后续。

5、在线性表的顺序存储结构中，每删除⼀个数据元素都必须移动表中的数据元素。

6、在⼀个AOE⽹中，若某⼀尘埃的最早开始时间和最迟开始时间相同，则该活动为关键活动。

7、对有序表⽽⾔，采⽤折半查找⽅法查找表中的数据元素，其查找成功的平均⼯长度⼀定采⽤顺序查找⽅法时的平均查找长度要⼩。

8、在⾮空完全⼆叉树中，若某结点不存在左孩⼦，则该结点⼀定是叶⼦结点。

9、设L是⼴义表，则取表头运算Head（L）的运算结果⼀定是单元素，⽽取表尾运算Tail （L）的运算结果⼀定是⼴义表。

10、将⼀棵树转换成⼆叉树后，根结点没有右⼦树。

11、就平均时间性能⽽⾔，快速排序是最优的。

所以，对于任意的待排序序列，选择快速排序⽅法进⾏排序，其执⾏时间将是最少的。

12、由于希尔排序的最后⼀趟与直接插⼊排序过程相同，因此前者⼀定⽐后者花费的时间多。

13、存在着这样的⾮空⼆叉树，不论采⽤怎样的遍历算法其所得到的遍历序列均相同。

一、选择题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 ）是非线性数据结构。

数据结构考研真题及其答案完整版数据结构是计算机科学与技术领域中的一门重要课程，也是计算机考研中必考的一门科目。

通过研究数据结构，可以帮助我们更好地理解和应用计算机算法，提高计算机程序的效率和性能。

为了帮助考生更好地备考数据结构，本文将分享一些数据结构考研真题及其答案，供考生参考。

一、选择题1. 下列关于栈的叙述中，错误的是（）A. 栈是一种线性数据结构，具有后进先出（LIFO）的特点B. 栈可以用数组实现，也可以用链表实现C. 栈的插入和删除操作都是在同一端进行的D. 栈的插入和删除操作的时间复杂度都是O(1)答案：C解析：栈的插入操作叫做入栈，删除操作叫做出栈。

入栈和出栈操作都是在栈顶进行的，而不是同一端。

2. 假设要对n个整数关键字进行排序，以下排序算法中，平均时间复杂度最小的是（）A. 冒泡排序B. 快速排序C. 归并排序D. 直接插入排序答案：C解析：归并排序的时间复杂度是O(nlogn)，平均时间复杂度最小。

二、填空题1. 下列关于图的遍历顺序的说法中，正确的是：深度优先搜索访问的顺序是________，广度优先搜索访问的顺序是________。

答案：前序遍历，层次遍历解析：深度优先搜索即前序遍历，广度优先搜索即层次遍历。

2. 给定一个最小堆，若删除堆顶元素后，需要对堆进行调整，所采用的操作是________。

答案：下滤解析：删除堆顶元素后，将最后一个叶子节点放到堆顶，然后进行下滤操作。

三、简答题1. 请简要说明动态规划算法的基本思想和应用场景。

答：动态规划算法的基本思想是将问题分解为多个子问题，通过求解子问题的最优解来得到原问题的最优解。

它通常适用于具有重叠子问题和最优子结构性质的问题。

动态规划算法可以大大减少问题的重复计算，提高算法的效率和性能。

它在求解最短路径、最长公共子序列、背包问题等具有广泛的应用。

2. 请简要介绍红黑树的特点和应用场景。

答：红黑树是一种自平衡的二叉查找树，它具有以下特点：1) 每个节点都有一个颜色，红色或黑色；2) 根节点是黑色的；3) 叶子节点（NIL节点）都是黑色的；4) 如果一个节点是红色的，则它的两个子节点都是黑色的；5) 从根节点到叶子节点的路径上，不同路径上黑节点的个数相同。

数据结构考研真题及其答案数据结构是计算机科学与技术专业考研中的重要科目之一，它对于培养学生的程序设计和算法分析能力具有关键作用。

以下将为大家呈现一些典型的数据结构考研真题，并提供详细的答案解析。

一、选择题1、若一个栈的输入序列为 1, 2, 3, 4, 5，不可能得到的输出序列是（）A 2, 3, 4, 1, 5B 5, 4, 3, 2, 1C 1, 5, 4, 3, 2D 3, 4, 2, 5, 1答案：C解析：栈的特点是“后进先出”。

对于选项 C，先输出 1，意味着 2、3、4、5 都已入栈，此时栈顶元素为 5，不可能接着输出 5 之后就输出4。

2、已知一棵二叉树的先序遍历序列为 ABCDEFG，中序遍历序列为 CBDAEGF，则其后序遍历序列为（）A CDBAFGEB CDBGFEAC CDBAGFED BCDAFGE答案：B解析：先根据先序和中序遍历序列构建二叉树。

先序遍历中第一个节点 A 为根节点，在中序遍历中找到 A，其左边的 CBD 为左子树，右边的 EGF 为右子树。

同样的方法确定左子树和右子树的结构。

然后按照“左子树右子树根节点”的顺序得到后序遍历序列 CDBGFEA。

3、对于一个具有 n 个顶点的无向图，若采用邻接矩阵表示，则该矩阵的非零元素个数为（）A n(n 1) ／ 2B n(n ＋ 1) ／ 2C n(n 1)D n(n ＋ 1)答案：A解析：无向图的邻接矩阵是对称的。

对于顶点 i 和 j（i ≠ j），若它们之间有边，则矩阵中对应位置为 1，共有 n(n 1) ／ 2 对不同的顶点对，所以非零元素个数为 n(n 1) ／ 2 。

二、简答题1、简述冒泡排序的基本思想，并分析其时间复杂度和空间复杂度。

答案：冒泡排序的基本思想是通过相邻元素的两两比较和交换，将最大（或最小）的元素逐步“浮”到数组的一端。

时间复杂度：在最坏情况下，即数组完全逆序，需要进行 n 1 轮比较，每轮比较 n i 次（i 为轮数，从 1 到 n 1），所以总的比较次数为n(n 1) ／ 2，时间复杂度为 O(n^2)。

第1章绪论一、选择题1. 算法的计算量的大小称为计算的（）。

【北京邮电大学2000 二、3 （20/8分）】A．效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（）【中科院计算所 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. 下列数据中，（）是非线性数据结构。

大连海事大学2003-2004学年第1学期《数据库原理与语言》试卷（A）大连海事大学2003－2004学年第1学期《数据库原理与语言》试卷（A）一、填空题（20分，每空0.5分）1、数据处理的发展经历了人工管理、文件系统数据库系统三个阶段。

各个阶段有不同的特点。

在人工管理阶段的特点主要包括_________、_________、__________、_________等几个方面；在文件系统阶段的特点主要包括_________、_________、__________、_________；在数据库系统阶段的特点主要包括_________、_________、__________、_________2、数据库管理系统的主要功能有_________、_________、__________以及数据库的建立和维护功能。

3、实际的数据库系统支持的数据模型有_________、_________、__________、_________等。

组成数据模型的基本要素是_________、_________、__________，在数据库系统中是按照___________的类型来命名数据模型的。

数据库系统具有数据的_________、_________、和__________等三级模式结构。

4、关系数据库中，关系语言的特点是_________，关系操作的特点是_________；关系数据库提供了_________、_________和__________等三种完整性。

5、数据库运行过程中可能产生的常见的故障有_________、_________、__________、_________等四种。

6、数据库设计一般都经历_________、_________、__________、_________、_______和数据库的运行维护等六个阶段。

二、选择题（10,每题1分）从下列各题后提供的答案中选择一个正确的答案。

2018年上海海事大学攻读硕士学位研究生入学考试
试题
（重要提示：答案必须做在答题纸上，做在试题上不给分）考试科目代码828 考试科目名称数据结构及程序设计一．判断题（本题10分，每小题1分）
1．线性的数据结构可以顺序存储，也可以链接存储。

非线性的数据结构只能链接存储。

2．单链表从任何一个结点出发，都能访问到所有结点。

3．单链表形式的队列，头指针F指向队列的第一个结点，尾指针R指向队列的最后一个结点。

4．若在采用链式存储结构线性表中，元素按值有序，则该线性表可以采用折半查找法查找元素。

5．一个栈的输入序列为1, 2, 3, …, n，其输出序列的第二个元素为n的输出序列的个数有n-1种。

6．设串S的长度为n，则S的子串个数为n(n+1)/2。

7．若一个广义表的表头为空表，则此广义表亦为空表。

8．二叉树中除叶节点外，任一节点x，其左子树根节点的值小于该节点(x)的值，其右子树根节点的值大于该节点(x)的值，则此二叉树一定是二叉排序树。

9．网络的最小代价生成树是唯一的。

10．（99, 86, 46, 70, 34, 39, 45, 58, 66, 10 ）是堆。

二．填空题（本题20分，每空2分）
1．一个栈的输入序列是：1、2、3，则不可能的栈输出序列是⑴。

- 2018试题1/6 -。

一、选择题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 ）【。