烟台大学2018年《846数据结构》考研专业课真题试卷
- 格式：pdf
- 大小：1.86 MB
- 文档页数：3
下载文档原格式
合集下载
全国硕士研究生入学统一考试计算机专业基础综合真题解析
2018年全国硕士研究生入学统一考试计算机学科专业基础综合试卷一、单项选择题：140小题，每小题2分，共80分。
下列每题给出的四个选项中，只有一个选项符合题目要求。
请在答题卡上将所选项的字母涂黑。
b5E2RGbCAP 1．已知程序如下：ints(int n>{ return (n<=0> ? 0 : s(n-1> +n。
}void main(>{ cout<< s(1>。
}程序运行时使用栈来保存调用过程的信息，自栈底到栈顶保存的信息一次对应的是A．main(>->S(1>->S(0> B．S(0>->S(1>->main(>p1EanqFDPwC．main(>->S(0>->S(1> D．S(1>->S(0>->main(>DXDiTa9E3d【参考答案】 D【考查知识点】栈的基本概念和函数调用的原理。
2．先序序列为a,b,c,d的不同二叉树的个数是A．13B．14C．15D．16【参考答案】 C【考查知识点】二叉树的基本概念。
3．下列选项给出的是从根分别到达两个叶节点路径上的权值序列，能属于同一棵哈夫曼树的是A．24，10，5和 24，10，7B．24，10，5和24，12，7C．24，10，10和 24，14，11 D．24，10，5和 24，14，6【参考答案】 C【考查知识点】哈夫曼树的原理。
4．现在有一颗无重复关键字的平衡二叉树<AVL树）,对其进行中序遍历可得到一个降序序列。
下列关于该平衡二叉树的叙述中，正确的是RTCrpUDGiTA．根节点的度一定为2B．树中最小元素一定是叶节点C．最后插入的元素一定是叶节点D．树中最大元素一定是无左子树【参考答案】 B【考查知识点】树的中序遍历和AVL树的基本概念。
5．设有向图G=(V,E>，顶点集V={V0,V1,V2,V3}，边集E={<v0,v1>,<v0,v2>,<v0,v3>，<v1,v3>},若从顶点V0 开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是5PCzVD7HxAA．2 B．3 C．4 D．5【参考答案】 D【考查知识点】图的深度优先遍历。
上海理工大学848数据结构与操作系统2018考研真题
I。 父 子 关 系
Ⅱ.兄 弟关 系
ⅡI.u的 父 结 点与 Ⅴ的父结 点是 兄弟关系
A。 只有 Ⅱ B。 I不口Ⅱ
C。 I不口ⅡI
D。 I、 Ⅱ和 IⅡ
6、 在具有 6个 顶 点 的无 向图 G至 少应有 多少条边才 能确 保是一个 连通 图 ((6))。
A.8 B。 7 C。 6 D.5
7、 假 设有 一个有 序关键 字序 列为 (05,13,19,21,歹 ,56,“ ,%,80,88,呢 ),
当二分查找 关键字值为 “ 的结 点时 ,查找 成功 的 比较 次数是 ((7))。
A。 1 B。 3 C。 4 D。 6
8、 设散 列 表 长 m=13,散 列 函数顽虍ey)=佬ey%11。 表 中 己有 4个 结 点 :顽 15)=4,汤
(2D=5,顽 3g,〓 6`顽51,〓 7, 其余地址为空,若采用二次探查法处理冲突,则 关键字
三 、解答题 (每道 5分 ,共 15分 ) 1、 己知二维数组 A[5][10]按 “行优先顺序”存储在 内存 中,假 设每个元素 占 3个存储单
元 ,第 一个元素 的存储地址 即 LOCfA[0][0])10OO,计 算 出 LOCrAI3]FD的 值。
2、 用分别 以 8,11,13,5,17,乃 ,21作 为权值的叶结点,构 造一棵哈夫曼树 ,并 求
该二叉树 的带权路径长度 WPL。
·
3.设 散列 函数F(o=庀 m耐 13,散 列表地址空间为 0-12, 对给定的关键字序列 (19, 14,” ,01,68,zO,胼 ,” ,55,11,10,79), 分别 以拉链法和线性探查法解决冲
突构造散列表 ,画 出所构造 的散列表 ,并 指 出在这两个散列表 中查找每一个关键字时进
数据结构考研真题及其答案_研究生入学考试_高等教育_教育专区 数据结
数据结构考研真题及其答案_研究生入学考试_高等教育_教育专区数据结结考研真题及其答案据结构是计算机科学中重要的一门课程，它研究的是如何组织和管理数据的方式。
对于计算机专业的研究生来说，数据结构是必修课程，考研真题的复习和备考对于学生来说是非常重要的。
在本文中，我们将介绍一些数据结构考研真题及其答案，帮助学生更好地复习和备考。
第一题：给出以下数据结构中各个操作的时间复杂度：数组、链表、堆、栈、队列。
答案：数组的插入和删除操作的时间复杂度为O(n)，查找操作的时间复杂度为O(1)；链表的插入和删除操作的时间复杂度为O(1)，查找操作的时间复杂度为O(n)；堆的插入、删除和查找操作的时间复杂度都为O(logn)；栈的插入、删除和查找操作的时间复杂度都为O(1)；队列的插入、删除和查找操作的时间复杂度都为O(1)。
第二题：给出以下数据结构的特点：栈、队列、堆、二叉树、图。
答案：栈是一种后进先出（LIFO）的数据结构，只能在一端进行插入和删除操作；队列是一种先进先出（FIFO）的数据结构，插入操作在一端进行，删除操作在另一端进行；堆是一种完全二叉树，具有父节点的值大于等于子节点的值（大顶堆）或父节点的值小于等于子节点的值（小顶堆）的性质；二叉树是一种每个节点最多有两个子节点的树；图是由节点和连接节点的边组成的数据结构。
第三题：给定一个有序数组，要求在其中查找一个元素的位置并返回，如果找不到则返回-1，设计一个算法实现上述功能。
答案：可以使用二分查找算法来实现上述功能。
首先，将要查找的元素与有序数组的中间元素进行比较，如果相等，则返回中间元素的位置；如果要查找的元素小于中间元素，则在数组的前半部分继续进行二分查找；如果要查找的元素大于中间元素，则在数组的后半部分继续进行二分查找。
重复这个过程，直到找到要查找的元素或者确定元素不存在为止。
第四题：给出以下排序算法的时间复杂度：冒泡排序、插入排序、选择排序、快速排序、归并排序。
2019年山东烟台大学数据结构考研真题
2019年山东烟台大学数据结构考研真题一、单项选择题(本大题共20小题，每小题2分，计40分)1.算法的时间复杂度主要取决于( )。
A.计算的环境B.待处理数据的值C.问题的规模D.数据的类型2.算法应具备( )这三个特性。
A.可执行性、可移植性、可扩充性B.可执行性、确定性、有穷性C.确定性、有穷性、稳定性D.易读性、稳定性、安全性3.以下与数据的存储结构无关的术语是( )。
A.循环队列B.链表C.哈希表D.栈4.以下数据结构中，哪一个是非线性结构( )?A. 串B.队列C.栈D.广义表5.分析下面的程序，算法的时间复杂度为( )。
for(k=1;k<n;k++)for(j=1;j<n;j++) x=x+1;A. 0(2n)B.0(n)C. 0(n)D. 0(logsn)6.以下数据结构中，多型数据类型结构是( )。
A.栈B.广义表C.数组D.字符串7.顺存储设计时，存储单元的地址( )。
A.一定连续B.一定不连续C.不一定连续D.部分连续，部分不连续8.串是一种特殊的线性表，其特殊形表现在( )。
A.可以顺序存储B.数据元素是单个字符C.可以连接存储D.数据元素类型相同9.以下可以用于定义一个完整的数据结构的是( )。
A.数据元素B.数据对象C.数据关系 ID.抽象数据类型10.有关图中路径的定义，表述正确的是( )。
A.路径是顶点和相邻顶点偶对构成的边所形成的序列B.路径是图中相邻顶点的序列C.路径是不同边所形成的序列D.路径是不同顶点和不同边所形成的集合11.已知有向图G=(V,E),其中V=(V1,V2,V3,V4,V5,V6,V7),E={<V1,V2),<V1,V3>,<V1,V4>, <V2,V5>,<V3,V5>,<Y3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},则图G的拓扑序列是()。
2018年计算机考研真题及参考答案
2018年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题：第1～40小题，每小题2分，共80分。
下列每题给出的四个选项中，只有一个选项最符合试题要求。
1．若栈S1中保存整数，栈S2中保存运算符，函数F()依次执行下述各步操作：（1）从S1中依次弹出两个操作数a和b；（2）从S2中弹出一个运算符op；（3）执行相应的运算b op a；（4）将运算结果压人S1中。
假定S1中的操作数依次是5, 8, 3, 2（2在栈顶），S2中的运算符依次是*, - , +（+在栈顶）。
调用3次F()后，S1栈顶保存的值是。
A. -15B. 15C. -20D. 202. 现有队列Q与栈S，初始时Q中的元素依次是1, 2, 3, 4, 5, 6（1在队头），S为空。
若仅允许下列3种操作：①出队并输出出队元素；②出队并将出队元素人栈；③出栈并输出出栈元素，则不能得到的输出序列是。
A. 1, 2, 5, 6, 4, 3B. 2, 3, 4, 5, 6, 1C. 3, 4, 5, 6, 1, 2D. 6, 5, 4, 3, 2, 13. 设有一个12×12的对称矩阵M，将其上三角部分的元素m i, j（1≤i≤j≤12）按行优先存人C 语言的一维数组N中，元素m6, 6在N中的下标是。
A. 50B. 51C. 55D. 664. 设一棵非空完全二叉树T的所有叶结点均位于同一层，且每个非叶结点都有2个子结点。
若T有k个叶结点，则T的结点总数是。
A. 2k-1B. 2kC. k2D. 2k-15. 已知字符集{a, b, c, d, e, f}，若各字符出现的次数分别为6, 3, 8, 2, 10, 4，则对应字符集中各字符的哈夫曼编码可能是。
A. 00, 1011, 01, 1010, 11, 100B. 00, 100, 110, 000, 0010, 01C. 10, 1011, 11, 0011, 00, 010D. 0011, 10, 11, 0010, 01, 0006. 已知二叉排序树如下图所示，元素之间应满足的大小关系是。
河南师范大学846数据结构与C程序设计
五、 阅读程序，写出程序的运行结果(每小题 5 分，共 10 分) 1. 读下列代码，将运行结果填入。
#include<stdio.h> void function(int b) /* 函数 function()定义*/
{ static int a=10; /*注意使用了静态变量*/ printf ("％d\n", a+b); a+=10;
指针为 L,则在它的第一个元素 结前插入 S 所指结点，则执行 O
A. s->next=L->next; L->next=s；
B. L->next=s-〉next-〉next；
C. s->next=L->next~>next； L~>next=s D. s->next=L-〉next； L->next=L;
下面是在带头结点的链队列 Q 的队尾插入一个值等于 e 的结点的类_C 算法，请填空。 void Insert_Q(LinkQueue &Q, QEIemType e ) )// Insert_Q 4. （10 分）设二叉树以二叉链表的形式存储，有关类型定义如下：
typcdef struct BiTNode （ // 结点结构 int data; struct BiTNode *lchild, *rchild; // 左右孩子指针
第一部分 数据结构（80 分）B 卷
一、单项选择题（20 个选题，每选题 2 分，共 40 分）
（备注：答题时每连续的 5 个为一组，组与组之间要留有空隙, 例如，ACCCD ACDAC)
1. 从逻辑结构来说，栈属于
O
A. 结构
树形结构
2018年山东省中国海洋大学计算机基础综合考研真题
2018年山东省中国海洋大学计算机基础综合考研真题第一部分数据结构一、选择题(每题2分，共20分)1.逻辑上通常可以将数据结构分为（）。
A.动态结构和静态结构B.顺序结构和链式结构C.线性结构和非线性结构D.初等结构和组合结构2.线性表是n个具有相同类型（）的有限序列(n>=0)。
A.表元素B.字符C.数据元素D.数据项3.在长度为n的顺序表的第i个位置上插入一个元素(1<=i<=n+1),元素的移动次数为（）。
A.n-i+1B.n-iC.iD.i-14.假设带头结点的单向循环链表的头指针为head,则该链表为空的判定条件是（）。
A.head==NULLB.head->next==NULLC.head!=NULLD.head->next=head5.在计算机内实现递归算法时所需的辅助数据结构是（）。
A.栈1B.队列C.树D.图6.广义表((a.b).c.d)的表头是（）。
A.aB.a,bC.(a,b)D.(a,b),c.d7.二维数组A[8][9]按行优先顺序存储，若数组元素A[2][3]的存储地址为1087,A[4][7]的存储地址为1153,则数组元素A[6][7]的存储地址为（）。
A.1207B.1209C.1211D.12138.下列陈述中正确的是（）。
A.二叉树是度为2的有序树B.二叉树中结点只有一个孩子时无左右之分C.二叉树中必有度为2的结点D.二叉树中最多只有两棵子树，并且有左右之分9.以下查找方法中，查找效率与记录个数n无直接关系的是（）。
A.顺序查找B.折半查找C.哈希查找D.二叉排序树查找10.下列排序算法中，算法（）在进行一趟相应的排序处理结束后不一定能选出一个元素放到其最终位置上。
A.直接选择排序B.冒泡排序C.归并排序D.堆排序二、简答题(每题12分，共36分)1.假设一棵二叉树的层次遍历序列为ABCDEFGHIJ,中序遍历序列为DBGEHJACIF,请画出这棵二叉树。