2018年沈阳工业大学808数据结构考研真题试题试卷

精品文档，欢迎下载！精品文档，精品文档，欢迎下载！欢迎下载！沈阳工业大学2018年硕士研究生招生考试题签（请考生将题答在答题册上，答在题签上无效）科目名称：数据结构一.解释下列名词（共20分，每小题4分）1.数据结构2.栈3.二叉树4.査找5.排序填空（共30分，每空3分）1.数据的逻辑结构被分为集合结构、线性结构、和图结构四种。

2.一种数据结构的元素集合K和它的二元关系R为：K=（ a, b, c, d, e, f, g, h }R= {<a, b>, <b, c>, <c, d>, <d, e>, <e, f>, <f, g>, <g, h> } 则该数据结构具有结构。

3.下面程序段的时间复杂度为ofor（int i=0;i〈n;i++）for（int j=0;j<n;j++）a[i] [j]=i*j;4.队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是。

5.在一棵树中，每个结点最多有个直接前驱结点。

6.己知一个无序表为（12, 18, 98, 25, 29, 83 ,40, 62, 20, 90, 95, 32）,要査找90时，采用从头至尾顺序査找时，需要次比较才能查找成功。

7.从一棵二叉排序树中查找一个元素时，若元素的值等于根结点的值，则表明査找成功，若元素的值小于根结点的值，则继续向左子树査找，若元素的值大于根结点的值，则继续向査找。

8.二叉树的中序遍历是先中序遍历它的左子树，然后访问,再中序遍历它的右子树。

9.对一组数据（54, 38, 96, 23, 15, 72, 60, 45, 83）进行直接插入排序时，第一趟排序的结果是10.图的遍历方法有和广度优先遍历。

三.解答下列问题（共50分）1.设元素1, 2, 3, 4, 5依次进栈，要在输出端得到序列3, 4, 2, 5, 1,写出进栈和出栈的过程。

数据结构期末考试题库及答案2018目录第1章绪论 (1)第2章线性表 (4)第3章栈和队列 (8)第4章串、数组和广义表 (12)第5章树和二叉树 (16)第6章图 (20)第7章查找 (22)第8章排序 (28)第1章绪论1．选择题（1）数据结构是指（1. A ）。

A.数据元素的组织形式B.数据类型C.数据存储结构D.数据定义（2）计算机内部数据处理的基本单位是（10. B ）。

A.数据B.数据元素C.数据项D.数据库（3）数据结构中，与所使用的计算机无关的是数据的 C 结构.A) 存储 B) 物理 C) 逻辑 D) 物理和存储【解析】[解析] 数据结构概念一般包括数据的逻辑结构、存储结构及数据上的运算集合等。

数据的逻辑结构只抽象地反映数据元素之间的逻辑关系，而不管它在计算机中的存储形式。

（4）算法分析的目的是____C________A) 找出数据结构的合理性 B) 研究算法中的输入和输出的关系C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性（5）计算机算法必须具备输入、输出和 B 等5个特性。

A) 可行性、可移植性和可扩充性 B) 可行性、确定性和有穷性C) 确定性、有穷性和稳定性 D) 易读性、稳定性和安全性（6）在数据结构中，从逻辑上可以把数据结构分成（）。

A．动态结构和静态结构 B．紧凑结构和非紧凑结构C．线性结构和非线性结构 D．内部结构和外部结构答案：C（7）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。

A．存储结构 B．存储实现C．逻辑结构 D．运算实现答案：C（8）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。

A．数据具有同一特点B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致C．每个数据元素都一样D．数据元素所包含的数据项的个数要相等答案：B（9）以下说法正确的是（）。

A．数据元素是数据的最小单位B．数据项是数据的基本单位C．数据结构是带有结构的各数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构答案：D解释：数据元素是数据的基本单位，数据项是数据的最小单位，数据结构是带有结构的各数据元素的集合。

沈阳工业大《数据结构》考研真题与考研复习笔记沈阳工业大学信息科学与工程学院808数据结构考研真题第1章绪论1.1 知识要点总结一、数据结构的基本概念1．基础概念和术语（1）数据（Data）：数据是客观事物的符号表示。

在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。

（2）数据元素（Data Element）：数据元素是数据的基本单位，在程序中通常作为一个整体来进行考虑和处理。

（3）数据项（Data Item）：数据项是数据的不可分割的最小单位，数据项是对客观事物的某一方面的数据描述。

一个数据元素可由若干个数据项（Data Item）组成。

（4）数据对象（Data Object）：数据对象是性质相同的数据元素的集合，是数据的一个子集。

如字符集合C={‘A’,’B’,’C’,…}（5）数据结构（Data Structure）：数据结构是指相互之间存在一定联系（关系）的数据元素的集合。

元素之间的相互联系（关系）称为逻辑结构。

2．数据结构的形式定义数据结构的形式定义是一个二元组：Data Structure=（D, S）其中D是数据元素的有限集，S是D上关系的有限集。

数据元素之间的关系可以是元素之间本身代表的某种自然关系，也可以是为了处理问题方便而人为定义的关系，这种自然或人为定义的关系称为数据元素之间的逻辑关系，相应的结构称为逻辑结构。

3．数据结构的组成数据结构的三个组成部分：（1）逻辑结构数据元素之间的逻辑关系的描述。

数据元素之间的逻辑结构有四种基本类型：①集合：结构中的数据除了“同属于一个集合”外，没有其它关系。

②线性结构：结构中的数据元素之间存在一对一的关系。

③树形结构：结构中的数据元素之间存在一对多的关系。

④图形结构或网状结构：结构中的数据元素之间存在多对多的关系。

（2）存储结构数据结构在计算机中的实际表达方式，它包括对数据元素的表示和对关系的表示。

存储结构主要有：顺序存储、链式存储、索引存储和散列存储。

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.已知二叉排序树如下图所示，元素之间应满足的大小关系是。

A.x1<x2<x5B.x1<x4<x5C.x3<x5<x4D.x4<x3<x57.下列选项中，不是如下有向图的拓扑序列的是。

数据结构习题集含答案目录目录 (1)选择题 (2)第一章绪论. (2)第二章线性表. (4)第三章栈和队列. (6)第四章串. (7)第五章数组和广义表 (8)第六章树和二叉树 (8)第七章图. (11)第八章查找. (13)第九章排序. (14)简答题 (19)第一章绪论. (19)第二章线性表. (24)第三章栈和队列. (26)第四章串. (28)第五章数组和广义表 (29)第六章树和二叉树 (31)第七章图. (36)第八章查找. (38)第九章排序. (39)编程题 (41)第一章绪论. (41)第二章线性表. (41)第三章栈和队列. (52)第四章串. (52)第五章数组和广义表 (52)第六章树和二叉树 (52)第七章图. (52)第八章查找. (52)第九章排序. (57)选择题第一章绪论1. 数据结构这门学科是针对什么问题而产生的？（ A ）A、针对非数值计算的程序设计问题 B 、针对数值计算的程序设计问题C、数值计算与非数值计算的问题都针对D、两者都不针对2. 数据结构这门学科的研究内容下面选项最准确的是（ D ）A、研究数据对象和数据之间的关系 B 、研究数据对象C、研究数据对象和数据的操作D、研究数据对象、数据之间的关系和操作3. 某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据结构考了90分，那么下面关于数据对象、数据元素、数据项描述正确的是（ C ）A、某班级的学生成绩表是数据元素，90 分是数据项B、某班级的学生成绩表是数据对象，90 分是数据元素C、某班级的学生成绩表是数据对象，90 分是数据项D、某班级的学生成绩表是数据元素，90 分是数据元素4. *数据结构是指（A ）。

A、数据元素的组织形式B、数据类型C、数据存储结构D、数据定义5. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同，称之为（C ）。

A、存储结构B、逻辑结构C、链式存储结构D、顺序存储结构6. 算法分析的目的是（ C ）A、找出数据的合理性B、研究算法中的输入和输出关系C、分析算法效率以求改进D、分析算法的易懂性和文档型性7. 算法分析的主要方法（ A ）。

本文部分内容来自网络整理，本司不为其真实性负责，如有异议或侵权请及时联系，本司将立即删除！== 本文为word格式，下载后可方便编辑和修改！ ==数据结构试卷（三）篇一：数据结构试卷(三)及答案数据结构试卷（三）一、选择题(30分)1．设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，则数据结构A是（）。

(A) 线性结构 (B) 树型结构 (C) 物理结构 (D) 图型结构2．下面程序的时间复杂为（）for（i=1，s=0； i<=n； i++） {t=1；for(j=1；j<=i；j++) t=t*j；s=s+t；}234 (A) O(n) (B) O(n) (C) O(n) (D) O(n)3．设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（）。

(A) q=p->next；p->data=q->data；p->next=q->next；free(q)；(B) q=p->next；q->data=p->data；p->next=q->next；free(q)；(C) q=p->next；p->next=q->next；free(q)；(D) q=p->next；p->data=q->data；free(q)；4．设有n个待排序的记录关键字，则在堆排序中需要（）个辅助记录单元。

2 (A) 1 (B) n (C) nlog2n (D) n5．设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为( )。

哈尔滨工业大学二〇〇八年硕士研究生考试模拟试题（二）考试科目：计算机专业基础适用专业：计算机科学与技术I 数据结构（含高级语言）部分（共75分）一、填空题（每空1分，共8分）1.下列程序段的时间复杂度为。

sum = 1; for(i = 0; sum < n; i++) sum +=1;2.循环单链表的最大优点是。

3.设有元素序列的入栈次序为（a1,a2,…,an），其出栈次序为（ap1,ap2,…,apn），如果已知p1=n，则pi= 。

4.已知二叉树有50个叶结点，则该二叉树的总节点树至少是。

5.在有n个顶点的有向图中，每个顶点的度最大可达。

6.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1，则应该做型调整以使其平衡。

7.对于具有144个记录的文件，若采用分块查找法，且每块长度为8，则平均查找长度为。

8.B直接插入排序用监视哨的作用是。

二、单项选择题（每题1分，共10分）1.线性表的顺序存储结构是一种（）A 随机存取的存储结构B 顺序存取的存储结构C 索引存取的存储结构D Hash存取的存储结构2.执行（）操作时，需要使用队列做辅助存储空间。

C 前序遍历二叉树D DFSA Hash表B BFS3.下列表述中（）是错误的。

A 含有一个或多个空格字符的串为空格串。

B 对n(n>0)个顶点的网，求出权最小的n-1条边便可构成其MST。

C 选择排序算法是不稳定的。

D 平衡二叉树的左右子树的结点数之差的绝对值不超过1.4.一个非空广义表的表尾（）A 不能是子表B 只能是子表C 只能是原子D 是原子或子表5.一棵高度为h的二叉树，所有节点的度为0或者为2，则这棵二叉树最少有（）个节点。

C 2h+1D h+1A 2hB 2h-16.若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为（）A X的双亲B X的右子树中最左的结点C X的左子树中最右的节点D X的左子树中最右的叶结点7.若一个有向图具有拓扑排序序列，则他的邻接矩阵必定为（）A 对称矩阵B 稀疏矩阵C 三角矩阵D 一般矩阵8.既希望查找较快又便于线性表动态变化的查找方法是（）A 顺序查找B 折半查找C 索引顺序查找D Hash查找9.在下列排序方法中，辅助空间为O（n）的是（）A 希尔排序B 堆排序C 选择排序D 归并排序10.下列排序方法中，（）方法可能出现这种情况：在最后一趟开始之前，所有的元素都不在其最终应在的正确位置上。