上海大学排名2017-上海大学排名2017
声明
此文件为参加
2015
年考研 华北电力大学
844
数据结构初试的考生，
根据回忆总结的题目。
相关题目可能与实际考试中的题目有出入，
但是难度相当，
可以作为备考华电计算机技术专硕
的考生做为练习习题使用。第一题选择，
道题
20
分，很简单，比王道上的题要简单的多把
王道的题做了，选择基本没问题。第二题填空题
10
空
20
分，也很简单。第
3
题简答
15
分
5
问，
第
4
题算法题
55
分
4
道题< /p>
5
小问。第
5
题
40
分两道大题都很简单。
最后给大家些建议：卷子中除了算法题外，其他
都很简单。建议大家多看算法，主要是键
表，树，图（主要是深度优先和广度优先遍历算
法）
。
另外考试大纲上没有写哈西表，
但实际会考。
今年有两小题共
5
分考哈西表。
最后 说一句：
考研的路很漫长，如果选择了，希望大家坚持到底，尤其到了
1 0
份以后更要坚持。祝学弟们
考研成功！
华电
2015
年初试考生
2015
年
4
月
17
日
欢迎关
注新浪微博
@lover_true
，交流题目经验
华北电力大学（北京）
2015
年硕士研究生入学模拟试题
考试科目：
844
数据结构
（闭卷考试，时间
120
分钟 ，总分
150
分）
I
选择填空部分（考生注意：答案必须写在答题纸上）
得
分
阅卷人
一、
单项选择题
（<
/p>
每小题
2
分，共
20
分
)
1.
数据结构中，与所使用的计算机无关的是数据的（
）结构；
A
、存储
B
、物理
C
、逻辑
D
、物理和存储
2.
在
n
个结点的顺序表中，算法的时间复杂度是
O
（
1
）的操作是（
）
A
、访问第
i
个结点（
1
≤< /p>
i
≤
n
）和求第
i
个 结点的直接前驱（
2
≤
i
≤
n
）
B
、在第
i
< p>个结点后插入一个新结点（1
≤
i
≤
n
）
C
、删除第
i
个结点（
1
≤
i
≤
n
）
D
、将
n
个结点从小到大排序
3.
有
1 27
个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（
）个元素。
A
、
8 B
、
63.5 C
、
63 D
、
7
4.
线性表
L
在（
）情况下适用于使用链式结构实现。
5.A
L
中的结点值
B
、需不断对
L
进行删除插入
C
、
L
中含有大量的结点
D
、
L
中结点结构复杂
5.
不含任何结点的空树
( )
A
、是一棵树
; B
、是一棵二叉树
;
C
、是一棵树也是一棵二叉树
; D
、既不是树也不是二叉树
6.
从未排 序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为（
）
A
、希尔排序
B
、归并排序
C
、插入排序
D
、选择排序
7.
已知图的邻接矩阵， 根据算法，则从顶点
0
出发，按广度优先遍历的结点序列是
( )
A
、
0 2 4 3 1 6 5 B
、
0 1 3 5 6 4 2
?
0
1
1
1
1
< br>C
、
0 1 2 3 4 6 5 D
、
0 1 2 3 4 5 6
?
1
0
0
1
0
8
.
已知完全二叉树有
28
个结点，则整个二叉树有
( )
个度为
1
的结点。
< p>
?
?
1
0
0
0
1
A
、
0; B
、
1; C
、
2; D
、
不确定
?
9.
设输入序列为
1,2,3,4,5
借助一 个栈不可能得到的输出序列是
( )
?
1
1
0
0
1
?
1
0
1
1
0
A
、
1,2,3,4,5 B
、
5,4,3,2,1
?
C
、
4,3,1,2,5 D
、
1,3,2,5,4
?
0
0
0
1
1
?
10.
任何一个无向连通图的最小生成树
( )
?
1
1
0
0
< p>0
A
、只有一棵
B
、
一棵或多棵
C
、一定有多棵
D
、可能不存在
0
1
?
0
1
?
?
0
0
?
?
1
0
?
1
0
?
?
0
1
?
1
0
?
?
得
分
阅卷人
二、
填空题
（
每空
2
分，共
20
分
< p>）
1.
数据结构是一门研究非数 值计算的程序设计问题中计算机的
以及它们之间的
和运
算等的学科。
欢迎关注新
浪微博
@lover_true
，交流题目经验
2.
在顺序表中插 入或删除一个元素，
需要平均移动
元素，
具体移动的元素个数与
有
关。
4.
顺 序栈
S,
栈顶指针为
top,
则栈置空操作是
.
5.
在如下一维数组
A< /p>
中折半查找
36
和
85
时
< p>,所需比较的次数分别为
和
.
25,36,40,45,48,56,60,68,72,85
6.
在有
N(N>0)
个结点的二叉链表中，空链域 的个数是：
。
7.
设数组
a[1
…
60,
1
…
70]
的基地址为
2048
，
每 个元素占
2
个存储单元，
若以列序为主序顺序存储，
则元素
a[32,58]
的存储地址为
。
8.n
个顶点
e
条边的图，若采用邻接矩阵存储，则空间复杂度为
。
Ⅱ
主观题部分
得
分
阅卷人
三、简答题
（
每题
3
分，共
15
分
）
1.
散列的基本思想是什么
?
举出五种常用的散列函数的构造方法
.
2.
什么 是冲突
?
处理冲突的方法是什么
?
3.
一个深度为
L
的满
K
叉树有如下性 质
:
第
L
层上的结点是叶子结点
, ?
其余各层上每个结点都有
K
棵非空子树
,
如果按层次顺序从
1
开始对全部结点编号
,
问
:
(1)
各层的结点的数目是多少
?
(2)
编 号为
n
的结点的双亲结点
(
若存在
)
编号是多少
?
(3)
编号为
n
的结点的第
i
个孩子
(
若存在
)
编号是多少
?
4.
说明线性表、栈与队的异同点。
< br>5.
对分
（折半）
查找适不适合链表结构的序列，
为什么？用二分查找的查找速度必然比线性查找的
速度快，这种说法对吗？
得
分
阅卷人
四、算法题
（
共
55
< p>分
）
1.
试基于图的深度 优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点
v
i
到顶点
v
j
的路
径（
i
≠
j
）
。注意：算法中涉及 的图的基本操作必须在此存储结构上实现。
（
15
分）
< p>
2.
用两种方法编写按层次顺序（同一层自左至右）遍历二叉树的 算法。
（
20
分）
3.
试编写算法
,
将数组
int
A[ n]
中的所有奇数移到所有偶数之前
.
要求时间复杂度为
O(n).
（
10
分）
< br>4.
从循环单链表中查找出最大值的算法
.
（
10
分）
得
分
阅卷人
五、综合题
（每题
1 0
分，
共
40
分
）
1.
试利用
Dijkstra
算法求图中从顶点
a
到其他各顶点间的最短路径，写出执行算法过程中各 步的状态。
（
20
分）
欢迎关注新浪微博
@lover_true< /p>
，交流题目经验
2.
已知如下所示长度为
12
的表：
（
Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec
）
(1)
试按表中元素的顺序依次插入一棵初始为空的二 叉排序树，
画出插入完成之后的二叉排序树，
并求其在
等
概率的情况下查找成功的平均查找长度。
(2)
若对表中元素先进行排序构成有序表，
求在等概率的情况下对此有序表进行折半查找时 查找成功的平均
查找长度。
(3)
按表中元素顺序构造一棵平衡二叉排序树，并求 其在等概率的情况下查找成功的平均查找长度。
欢迎关注新浪微博
@lover_true< /p>
，交流题目经验