山东师范大学2017年《838数据结构A》考研专业课真题试卷

第1章绪论一、选择题1. 算法的时间复杂度取决于（ C ）A．问题的规模 B. 待处理数据的初态 C. A和B2.计算机算法指的是（C），它必须具备（B）这三个特性。

(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法(2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性D. 易读性、稳定性、安全性3．从逻辑上可以把数据结构分为（ C ）两大类。

A．动态结构、静态结构 B．顺序结构、链式结构C．线性结构、非线性结构 D．初等结构、构造型结构4．以下与数据的存储结构无关的术语是（ D ）。

A．循环队列 B. 链表 C. 哈希表 D. 栈5．在下面的程序段中，对x的赋值语句的频度为（ C ）FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1;A． O(2n) B．O(n) C．O(n2) D．O(log2n)6．连续存储设计时，存储单元的地址（ A ）。

A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续二、判断题1. 数据元素是数据的最小单位。

( F ) （数据项）2. 记录是数据处理的最小单位。

( F )（数据项）3．数据的物理结构是指数据在计算机内的实际存储形式。

( T )【山东师范大学2001 一、2（2分）】4. 在顺序存储结构中，有时也存储数据结构中元素之间的关系。

( F )5. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

( F )三、填空1．数据的物理结构包括的表示和的表示。

（数据元素）（关系）2. 对于给定的n个元素,可以构造出的逻辑结构有（1），（2），（3），_（4）四种。

（数组,栈,线性表,队列）3．数据的逻辑结构是指。

4．一个数据结构在计算机中称为存储结构。

5．数据结构中评价算法的两个重要指标是6．已知如下程序段FOR i:= n DOWNTO 1 DO {语句1}BEGINx:=x+1；{语句2}FOR j:=n DOWNTO i DO {语句3}y:=y+1; {语句4}END；语句1执行的频度为（1）；语句2执行的频度为（2）；语句3执行的频度为（3）；语句4执行的频度为（4）。

教育硕士入学考试教育综合真题山东师范大学2017年(总分：150.00，做题时间：180分钟)一、名词解释(总题数：6，分数：30.00)1. 教学评价（分数：5.00）__________________________________________________________________________________________ 2. 上位学习（分数：5.00）__________________________________________________________________________________________ 3. 成就动机（分数：5.00）__________________________________________________________________________________________ 4. 教育准备说（分数：5.00）__________________________________________________________________________________________ 5. 苏湖教法（分数：5.00）__________________________________________________________________________________________ 6. 平民教育思潮（分数：5.00）__________________________________________________________________________________________ 二、辨析题(总题数：3，分数：30.00)1. 课程内容即教材内容。

（分数：10.00）__________________________________________________________________________________________ 2. 智力水平高的人创造力也高。

（2）如果在第一个时间单元（也就是到达时间为 1.0）期间，CPU 被
设置为空闲，该方法产生的进程调度序列和平均周转时间分别是什
么？（4 分）
3．系统中有 4 个进程P1、P2、P3、P4互斥使用一个包含 1 个单元的缓 冲区。P1 每次产生一个正数并送入缓冲区；P2 每次产生一个负数并 送入缓冲区；P3 每次从该缓冲区中取出一个正数并计数；P4 每次从 该缓冲区中取出一个负数并计数。请用信号量机制实现这四个进程的
①请画出该图； ②给出从顶点 3 开始的深度优先遍历序列； ③给出从顶点 4 开始的广度优先遍历序列。 3、假设有一个 10000*10000 的稀疏矩阵，期中 1%的元素为非零元 素，要求构造一个哈希表，完成以下任务。 ①设计哈希函数（根据给定非零元素的行值和列值确定其在哈
希表的位置）； ②给出处理冲突的方法； ③简要分析该哈希表的查找效率。 4、设待排序的关键字序列为{13，7，16，45，36，27，17，6， 12，56}，试分别完成以下任务： ①建小顶堆； ②给出以 13 为枢轴进行一趟快速排序的过程。 三、算法设计题（20 分，每题 10 分） 1、已知链表 A 和 B 分别表示元素递增的两个集合，试写一算法求 两个集合的交集，结果存放于链表 A 中。 2、已知二叉排序树采用二叉链表存储，试写一高效算法从小到大 输出二叉排序树中所有值小于 X 的结点的数据。
请计算逻辑地址为 0x17C8 和 0x6E37 的物理地址。（8 分）
页 号
块号
装入内存 时刻
上次引用（访问）该页面
时刻
R(读)
M(修 改)
07
10:05
11:33
1
0
34
9:35
10:20

目　录2013年山东师范大学855数据结构A历年考研真题2012年山东师范大学856数据结构A历年考研真题2011年山东师范大学856数据结构A历年考研真题2010年山东师范大学数据结构A历年考研真题2009年山东师范大学数据结构A历年考研真题2008年山东师范大学数据结构A历年考研真题2007年山东师范大学数据结构A历年考研真题2006年山东师范大学数据结构A历年考研真题2005年山东师范大学数据结构A历年考研真题2013年山东师范大学855数据结构人历年考研真题考试科E 注意事窿L 二填空顺席写在即L数却2.没不金具有6.砒＜818.在平A的9.Xf-■把第二、写算法题1.改计2,设ir3,缶.点4.气山东师范大学硕士研究生入学考试试题1名称：数据结构A试题编号；衣试卷尤5道大题《共H18个小题）,满分1知分；本卷风试收卷.答题另肯答飓卷,忤案一律与枇容四卷上,写任该试题卷I-.或单纸卜.均无没妾注意试卷沽洁，不要住试卷卜滁灿四须用瞌、您钢筮或网球堡拎题，*它均无泡.挞由龙许使用悴通计算嚣定•10分”本大尚共9小题，10个空.群空4分，将成埴在卜剧践地的件案，fe 题纸h）靖梅中评价算弁的两个收要指标是⑴和12U-个10X10的耐称矩阵A[10][10J.采取上三甜矩阵核行压缩存储的力式存一个一维数组B[]中，A（0][0）＞.；第一个元为,存放J BW1.AH中旬个数据元B[]中占个位挥顶A圆[5]在敏折BI]中的位置为〔3）：一算术表送式的中貂形式为A+BT-D E，后缀形式为ABC*+DE/-.倏前缓为（4"林F中有二棵树.第、第：，第二棵树聘结点个数分切为Ml. M2HI M3.林F双庇的二又树根结盘的右于树上的姑点个敦是（5）.6个质点的无向图至少W仃f6J条边彳•能确保是个连」也图.邻接表表示的圈进行任一种遍必时.其时间复杂度姑⑺*在肖序茹表AJL-0]上进律二分栗投,她比绞四次卉找成功的鳍点个数为徵.「义柑中而入一个帖点后造成J'不平也，&最低的不平衙结点为A,并已知拦核!■的平衡而J'为0,1,接f的平础于为1,则应作⑼型调整以使耳平衡。