2019年山东烟台大学数据结构考研真题.doc

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的拓扑序列是()。
A.V1,V3,V4,V6,V2,V5,v7B.V1,V3,V2,V6,V4,V5,V7
C.V1,V3,V4,V5,V2,V6,v7D.V1,v2,V5,V3,V4,V6,V7
12.设单链表中指针p指向结点A,若要删除A的直接后继，则所需修改指针的操作为()。
A.p->next=p->next->nextB.p=p->nextC.p=p->next->nextD.p->next=p
13.数据表A中每个元素距其最终位置较近，则最省时间的排序算法是()。
A.插入排序B.堆排序C.直接选择排序D.快速排序
14.一棵二叉树的中根遍历序列为debac,后根逸历序列为dabec,,则先根遍历序列为()。
A.acbedB.cedbaC.deabcD.becab
15.在一个有向图中，所有顶点的度数之和与图的边数的比是()。
A.1:2B.1:1C.2:1D.4:1
16.含有n个结点的二叉树用二叉链表表示时，空指针域个数为()。
A.n-1B.nC.n+1D.n+2
17.对称矩阵A[N]N],A[1I[]为首元素，将下三角(包括对角线)元素以行优先顺序存储到一维
数组元素T[1]至T[N(N+1)/2]中，则任一下三角元素A[J[6]存于Tk]中，下标k为()。
A.i*(i-1)/2+jB.jG-1)/2+1C.iG-i)/2+1D.j(-1)/2+1
18.设有数组A[i,j],数组的每个元素长度为3字节，i的值为1到8,j的值为1到10,数
组从内存首地址adr开始顺序存放，当用以列为主存放时，元素A[5,8]的存储首地址为()。
A.adr+141B.adr+180C.adr+222D.adr+225
19.链表不具有的特点是()
A、插入/删除不需要移动元素B、可随机访问任一元素
C、不必事先估计存储空间D、所需空间与线性长度成正比
20.已知二叉树中叶子数为40,仅有一个孩子的结点数为20,则总结点数为()。
A、91B、92C、98D、99
二、填空题(本大题共30个空项，每个空项1分，计30分)
1.数据结构是一门研究程序设计中数据的(1)_以及他们之间的(2)和运算等的学科。
2.在数据结构中，从逻辑上可以把数据结构分为_(3)_和(4)_两类。
3.数据的存储结构是一个数据结构在计算机中的(5)。
4.顺序存储结构是逻辑上(6)的节点存储在(7)_中。
5.算法的五个特性是(8)、(9)、(10)、输入和输出。
6.在线性表的链式存储中，元素之间的逻辑关系是通过(11)决定的；在线性表的顺序存储
中，元素之间的逻辑关系是通过_(12)决定的。
7.从数据结构定义看，栈和队列都是(13)_的线性表；栈具有_(14)_的特性。
8.栈和队列的共同特点是只允许在端点处进行(15)和(16)。
9.用带头节点的单链表表示栈，则栈空的标志是(17)_
10.根据串的定义，串