2017年青岛大学考研试题910数据结构

格式：pdf
大小：189.94 KB
文档页数：4

下载文档原格式

青岛大学2015年硕士研究生入学考试初试试题考试科目：910数据结构

青岛大学2015年硕士研究生入学考试试题科目代码： 910 科目名称：数据结构（共 5 页）请考生写明题号，将答案全部答在答题纸上，答在试卷上无效一、单项选择题（本大题共10道小题，每小题2分，共20分）1．数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象，以及它们之间的（）和运算的学科。

A ．逻辑存储B ．关系C ．算法D ．数据映像2．下列函数中渐近时间复杂度T(n)最小的是（）。

A ．T(n) = 2105000n n --B ．T(n) = 230000060n n --C ．T(n) = 10000000D ．T(n) = 2log 1000*2100n n --3．在计算机的存储器中表示时，物理地址和逻辑地址相同并且是连续的，称之为（）。

A ．逻辑结构B ．物理结构C ．顺序存储结构D ．链式存储结构4．有六个元素｛6，5，4，3，2，1｝，依次顺序进栈，下列哪一个不是正确的出栈序列？（）。

A ．5 4 3 6 1 2 B. 4 5 3 2 1 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 65．循环队列存储在数组 Q[MAX]中，则入队列时的操作为（）。

A ．rear=rear+1B ．rear=(rear+1) MOD (MAX-1)C ．rear=(rear+1) MOD MAX D ．rear=(rear+1) MOD (MAX+1)6．若一棵二叉树具有8个度为2的结点，4个度为1的结点，则度为0的结点个数是（）。

A ．8B ．9C ．12D ．137．用顺序存储的方法将完全二叉树中所有结点逐层存放在数组R[1..n]中，结点R[i]若有双亲结点，则双亲结点是（）。

A ．R[i/2]B ．R[2i]C ．R[2i+1]D ．R[2i-1]8．下列哪一种图的邻接矩阵是对称矩阵？（）。

A ．AOV 网B ．AOE 网C ．有向图D ．无向图9．对线性表进行二分查找时，要求线性表必须（）A．以顺序方式存储B．以顺序方式存储，且数据元素有序C．以链接方式存储D．以链式方式存储，且数据元素有序10．内部排序方法的稳定性是指（）。

桂林电子科技大学910数据结构2017年考研真题

（1）请给出构建的大根堆（6分）
（2）请给出前3趟堆排序，每一趟排序后堆的结果。（4分）
六、设一数列的输入顺序为12345，若采用栈结构，并以A和D分别表示入栈和出栈操作，试问：能否得到下面的输出顺序，如果能，给出合法的入栈和出栈的操作顺序；如果不能解释为什么。（共10分）
（1）能否得到输出顺序为32514的序列。（5分）
A．2B．3C．4D．5
5．给定有序表{ 16，23，32，45，51，62，73，79，80 }，若采用二分检索法查找关键码值为62的数据元素，（）次比较后查找成功。
A．1B．2C．3D．4
6.给定一棵具有n个结点的二叉树，在不违背二叉树定义以及不改变根结点的基础上，向二叉树中任意一个可插入结点的位置插入一个新的结点，则生成的新二叉树有（）。种可能。
struct Node{
DataType info;
PNode link;
};
typedef struct Node * LinkList;
int Test(LinkList list, DataType value)
{
LinkList first=list;
while( ( first!=null ) && (first->link!=null))
（1）若采用拉链法解决冲突，请构造哈希表。（6分）
（2）请基于（1）的结果，给出等概率情况下查找成功时的平均查找长度。（4分）
四、请证明：任意一棵具有N个结点的满二叉树（N>0）的叶子结点数目为（N+1）/2。（10分）
五、给出一组排序码：56，32，65，24，16，9，43，39，若对其进行堆排序（按升序排列）：（共已知一棵二叉树的先根序列（A,B,D,E,C,F,G）和中根序列（D,B,E,A,F,G,C）（共10分）

青岛大学333教育综合2017到2010八套考研真题

青岛大学2017年硕士研究生入学考试试题
科目代码：333科目名称：教育综合（共1页）
请考生写明题号，将答案全部答在答题纸上，答在试卷上无效
一、简答题（每小题10分，共计60分）
1.简述教学过程中的几个必然联系。

2新一轮基础教育课程改革的具体目标有哪些？
3简述有关教育目的两个典型的价值取向。

4.根据皮亚杰的观点，教学中如何发展儿童的认知能力？
5.简述陈述性知识获得的机制。

6.简述加德纳的多元智力理论。

二、论述题（每小题30分，共计60分）
1.个体身心发展有哪些规律？针对这些规律你认为应该采取怎样的教育
措施？
2.联系实际，谈谈学校教育中如何培养学生的创造性。

三、案例分析题（30分）
当人们谈到天才，马上就会想到爱因斯坦。

1955年诺贝尔奖获得者爱因斯坦在普林斯顿逝世，享年76岁。

他的儿子授权病理学家托马斯·哈维保存一些爱因斯坦的大脑切片用于科学研究。

随后他将大脑切片分发给了至少18位全球各地的研究者。

后来陆续有几位研究者发表相关研究，试图说明爱因斯坦大脑中某些部分的与众不同是如何转化为爱因斯坦惊
人的思维能力的。

你认为天才来自于何处，从爱因斯坦的大脑中能找到天才的因子吗？
由此分析一个人的发展受哪些因素影响？这些影响因素在人的发展中各
起怎样的作用？对上述的天才研究你作何评价？
1。

青岛大学计算机程序设计考研真题2017年、2009年

(B)它们的运算对象可以是char型变量和int型变量，但不能是float型变量
(C)它们的运算对象可以是int型变量，但不能是double型变量和float型变量
(D)它们的运算对象可以是char型变量、int型变量和float型变量
5、有以下程序
main()
{
int i=1,j=1,k=2;
if((j++||k++)&&i++) printf("%d,%d,%d\n",i,j,k);
(B)for(i=1;i<=5;i++){p=1;p*=i;}
(C)i=1;p=1;while(i<=5){p*=i;i++;} (D)i=1;p=1;do{p*=i;i++;}while(i<=5);
4
18、有以下程序
#include<stdio.h>
void main()
{
int a[10]={1,2,3,4,5,6,7,8,9,10}, *p=&a[3], *q=p+2;
3
case 2+1: printf("**\n");
}
(D) switch(a+b)
{
case 1: printf(*\n");
case c: printf("**\n");
} 15、下列程序的运行结果是（）。
void fun(int *a, int *b)
{
int *k;
k=a; a=b; b=k;
main()
{
char st[20]= "hello\0\t\\";

青岛大学2020年910数据结构考试大纲

硕士入学考试大纲考试科目代码及名称：910数据结构一、考试要求1、掌握数据结构的基本概念、基本原理和基本方法。

2、掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。

3、能够运用数据结构基本原理和方法进行问题的分析与求解，具备采用C或C++语言设计与实现算法的能力。

二、考试内容一、线性表(一) 线性表的定义和基本操作(二) 线性表的实现1、顺序存储2、链式存储3、线性表的应用二、栈、队列和数组(一) 栈和队列的基本概念(二) 栈和队列的顺序存储结构(三) 栈和队列的链式存储结构(四) 栈和队列的应用(五) 特殊矩阵的压缩存储三、树与二叉树(一) 树的基本概念(二) 二叉树1、二叉树的定义及其主要特征2、二叉树的顺序存储结构和链式存储结构3、二叉树的遍历4、线索二叉树的基本概念和构造(三) 树、森林1、树的存储结构2、森林与二叉树的转换3、树和森林的遍历(四) 树与二叉树的应用1、二叉排序树2、平衡二叉树3、哈夫曼(Huffman) 树和哈夫曼编码四、图(一) 图的基本概念(二) 图的存储及基本操作1、邻接矩阵法2、邻接表法3、邻接多重表、十字链表(三) 图的遍历1、深度优先搜索2、广度优先搜索(四) 图的基本应用1、最小(代价) 生成树2、最短路径3、拓扑排序4、关键路径五、查找(一) 查找的基本概念(二) 顺序查找法(三) 分块查找法(四) 折半查找法(五) B-树及其基本操作、B+树的基本概念(六) 散列(Hash) 表(七) 字符串模式匹配(八) 查找算法的分析及应用六、排序(一) 排序的基本概念(二) 插入排序1、直接插入排序2、折半插入排序(三) 冒泡排序(Bubble Sort)(四) 简单选择排序(五) 希尔排序(Shell Sort)(六) 快速排序(七) 堆排序(八) 二路归并排序(Merge Sort)(九) 基数排序(十) 各种排序算法的比较(十一) 排序算法的应用三、试卷结构（题型分值）1.本科目满分为150分，考试时间为180分钟。

青岛大学2016年硕士研究生入学考试试题

青岛大学2016年硕士研究生入学考试试题科目代码： 910 科目名称：数据结构（共 5 页）请考生写明题号，将答案全部答在答题纸上，答在试卷上无效一、单项选择题（本大题共10道小题，每小题2分，共20分） 1．一个算法具有（）等特点。

A ．快速性B ．至少有一个输入量C ．确定性D ．健壮性2．下列函数中渐近时间复杂度T(n)最小的是（）。

A ．T(n) = 73128*64*n n + B ．T(n) = 2256*64*n n -- C ．T(n) = 21024**log n n D ．T(n) = 2log 1024*232*n n --3．在计算机的存储器中表示时，物理地址和逻辑地址相同并且是连续的，称之为（）。

A ．逻辑结构B ．顺序存储结构C ．链式存储结构D ．以上都对4．若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（）种情况。

A ．5，4，3，2，1B ．2，1，5，4，3C ．4，3，1，2，5D ．2，3，5，4，15．设栈S 用顺序存储结构表示，则栈S 为空的条件是（）。

A ．S.top - S.base != 0B ．S.top - S.base == 0C ．S.top - S.base != nD ．S.top - S.base == n6．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。

A ．500B ． 501C ．250D ．251 7．任何一棵二叉树的叶子结点在先序、中序和后序遍历中的相对次序（）。

A ．不发生改变B ．发生改变C．不能确定D．以上都不对8．用邻接表表示图进行广度优先遍历时，通常借助（）来实现算法。

A．栈 B. 队列 C. 树D．图9．折半查找法和二叉排序树的时间性能（）。

A．与处理数据量有关B．相同C．不相同D．不确定10．对n个不同的关键字由小到大进行冒泡排序，在下列（）情况下比较的次数最多。

青岛大学数学分析2009-2017年考研初试真题

, x ( 0, )
条件收敛。
n1 n
八、（满分 15 分）设 fn (x) , n 1,2,, 均在点 x b 连续，数列
{ fn (b)} 发散，求证 0 ，{ fn (x)} 在 (b , b ) 内非一致收敛。

九、（满分 10 分）确定幂级数 n2 xn1 的收敛域，并求其和函数。 n1
S
三、（满分 10 分）设曲线 C 的方程为 x 1 t 2 , y t t 2 ，求曲线 C
上在 t 2 对应的点 P 处的切线方程。四、（满分 10 分）证明 f (x) sin 1 在 ( 0, 1) 内不一致连续。 x 五、（满分 10 分）设 f 在[ a , b ] 上连续，且有 f (a) , f (b) [ a , b ]，
在一点 [a,b], 使得
b f (x)g(x)dx f ( )
b
g(x)dx .
a
a
6. (本题满分15分) 证明:广义积分 cos x dx 收敛,而 | cos x | dx 发散.
1x
1
x
7. (本题满分15分)
(x 1)n
讨论并指出级数
绝对收敛、条件收敛、发散的范围.
2. 计算 I = ∫∫ xdydz + 2 ydzdx + 3zdxdy ，其中 S 是圆柱面 x2 + y2 = 1被平
S
面 z = 0 和 z = 3 所截的部分之外侧.
2
青岛大学 2012 年硕士研究生入学考试试题
科目代码： 605 科目名称：数学分析（共 2 页）请考生写明题号，将答案全部答在答题纸上，答在试卷上无效

青岛大学2019年硕士研究生入学考试试题

青岛大学2019年硕士研究生入学考试试题科目代码：910 科目名称：数据结构（共8 页）请考生写明题号，将答案全部答在答题纸上，答在试卷上无效一、单项选择题（本大题共20道小题，每小题2分，共40分）1．顺序存储表示中,数据元素之间的逻辑关系是由( )表示的。

A.指针B.逻辑顺序C.存储位置D.问题上下文2．计算算法的时间复杂度属于( )。

A.事前统计的方法B.事前分析估算的方法C.事后统计的方法D.事后分析估算的方法3．下列关于线性表的叙述中正确的是( )。

A.每个元素最多有一个直接前趋和一个直接后继B.每个元素最少有一个直接前趋和一个直接后继C.每个元素有且仅有一个直接前趋,有且仅有一个直接后继D.线性表中每个元素都是不可再分解的数据元素,且数据类型须相同4．利用双向链表作线性表的存储结构的优点是( )。

A.便于进行插入和删除的操作B.节省空间C.便于销毁结构释放空间D.提高按关系査找数据元素的速度5．若一个链表最常用的操作是在最后一个结点之后插入一个新结点,或删除最后一个结点,则选用( )最节省运算时间。

A.带头结点的单循环链表B.带头结点的双向循环链表C.不带头结点的单链表D.带头结点的单链表6．对于链式队列,在执行插入操作时( )。

A.仅修改头指针B.仅修改尾指针C.头、尾指针都要修改D.头、尾指针可能都要修改7．—个队列的进队顺序是1,2,3,4,则该队列可能的输出序列是( )。

A.1,2,3,4B.1,3,2,4C.1,4,2,3D.4,3,2,18．执行完下列程序后,i的值为( )。

int f(int x){return((x>0)?x*f(x-1):2);}int i=f(f(1));A.2B.4C.8D.无限递归9．一个广义表(x,(a,b,c))的表尾是( )。

A.xB.(a,b,c)C.(a,b,(c))D.((a,b,c))10．一个二维数组A[10][20]按行存放于一个连续的存储空间中,A[0][0]的存储地址是200,每个数组元素占1个字节,则A[6][2]的地址为( )。

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

青岛大学2017年硕士研究生入学考试试题科目代码：910科目名称：数据结构（共5页）
请考生写明题号，将答案全部答在答题纸上，答在试卷上无效
一、单项选择题（本大题共10道小题，每小题2分，共20分）
1．计算机算法指的是（）。

A．计算方法B.排序方法C.解决问题的步骤序列D.存储结构
2．链表不具有的特点是（）。

A．插入、删除不需要移动元素B．可随机访问任一元素
C．不必事先估计存储空间D．所需空间与线性长度成正比
3．连续存储设计时，存储单元的地址（）。

A．一定连续B．一定不连续
C．不一定连续D．部分连续，部分不连续
4．一个递归算法必须包括（）。

A.递归部分
B.终止条件和递归部分
C.迭代部分
D.终止条件和迭代部分
5．栈和队列的共同点是（）。

A.都是先进先出
B.都是先进后出
C.只允许在端点处插入和删除元素
D.没有共同点
6．任何一棵二叉树的叶子结点在先序、中序和后序遍历中的相对次序（）。

A．不发生改变B．发生改变C．不能确定D．以上都不对
7．由带权为{8，2，5，7}的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（）。

A．23B．37C．46D43
8．若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（）图。

A．非连通B．连通C．强连通D．有向
9．适用于折半查找的表的存储方式及元素排列要求为（）。

A．链接方式存储，元素无序B．链接方式存储，元素有序
C．顺序方式存储，元素无序D．顺序方式存储，元素有序
10．对n个关键字作快速排序，在最坏情况下，算法的时间复杂度是（）。

A．O(n)B．O(n2)C．O(nlog2n)D．O(n3)
二、简答题（本大题共6道小题，每题5分，共30分）
1．如果有n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。

在此情况下，应选用哪种存储结构？为什么？2．有5个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈（即C第一个且D第二个出栈）的次序有哪几个？3．简述树与二叉树的转化方法。

试举一个例子说明。

4．简要说明图的各种遍历方法。

5．简述顺序查找和折半查找的优缺点。

6．简要说明归并排序的基本思想。

三、综合应用题（本大题共4道小题，每题12分，共48分）
1．已知一棵二叉树的中序遍历序列为BCAFEC，后序遍历序列为CBECFA，试画出该二叉树，并给出该二叉树的先序序列。

2．对于下图所示的有向图，试给出：
(1)邻接表；
(2)从顶点v1出发的深度优先遍历序列；
(3)从顶点v3出发的广度优先遍历序到。

3．设将关键字集合Keys=｛2,6,7,5,4,3,1｝中的元素依次插入到一个空的平衡二叉排序树中，画出所得的平衡二叉排序树。

假设查找每一个元素的概率相同，查找此平衡二叉树排序中任一结点的平均查找长度为多少？
4．某设待排序的关键字集合为{12，2，16，30，28，10，16*，20，6，18}，试分别回答下面的问题。

①给出希尔排序（增量选取5，3，1）的结果；
②写出快速排序第一趟之后的状态；
③把关键字集合调整成堆顶元素取最大值的堆。

四、算法分析题（本大题共3道小题，每题10分，共30分）
1．下面的算法是在带头结点的单链表L中，删除第i个元素，并由e返回其值，请在空白处填入正确的语句。

Status ListDelete(LinkList&L,int i,ElemType&e)
{
LinkList p,q;
p=_____①_____;
int j=0;
while(p->next&&______②_____){
p=p->next;
++j;
}
if(!(______③______)||j>i-1)
return ERROR;
q=p->next;
p->next=_____④______;
e=q->data;
_______⑤_______;
return OK;
}
2．阅读下面的代码，试说明算法的功能。

int Unknown(BiTNode*T,BiTNode*s)
{//s为指向二叉排序树中某个结点的指针
int k=0;
BiTNode*p=T;
if(T!=NULL){
k++;
while(p->data!=s->data){
if(p->data<s->data)
p=p->rchild;
else
p=p->lchild;
k++;
}
}
return k;
}
3．下面代码是中序遍历二叉树T的非递归算法。

请在空白处填入正确的语句。

Status InOrderTraverse(BiTree T)
{
SqStack S;
BiTree p;
_____①_______;
Push(S,T);
while(!_______②________)
{
while(GetTop(S,p)&&_____③_______)
Push(S,p->lchild);
Pop(S,p);
if(!StackEmpty(S))
{
_______④________;
printf("%c",T->data);
_______⑤______;
}
}
return OK;
}
五、算法设计题（本大题共2道小题，每题11分，共22分）
1．已知L1、L2分别为两个循环单链表（带头结点）的指针，m,n分别为L1、L2表中数据元素个数。

试设计一算法，用最快速度将两表合并成一个带头结点的循环单链表。

LinkList Union(LinkList&L1,LinkList&L2,int m,int n) {……}
2．试编写算法，统计一棵二叉树中所有非叶子结点的数目。