2018年中国海洋大学807数据结构考研真题试题试卷

中国海洋大学命题专用纸（首页）2006学年第 1 学期试题名称：数据结构 (A卷) 共 2 页第 1 页专业年级：学号姓名授课教师分数一、简答下列术语：（10分）1、算法的时间复杂度2、栈与队列的异同3、完全二叉树、二叉排序树二、填空（10分）1、在双向循环链表L中，删除指针P所指结点的语句序列是，，free(p)。

2、将下三角矩阵A[1..8,1..8]的下三角部分逐行地存储到起始地址为1000的内存单元中.已知每个元素占4个单元，则A(6,4)的地址为。

3、高度为5的三阶B－树至少有个结点。

4、分别采用堆排序、快速排序、插入排序和归并排序算法对初始状态已为递增序列的数据表进行递增排序，最省时间的是算法。

三、（8分）已知一棵二叉树的中序序列是dcbgeahfijk，后序序列是dcegbfhkjia，请构造出该二叉树。

四、（10分）假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别是0.07，0.08，0.13，0.22，0.18，0.23,0.04，0.05。

请设计它们相应的哈夫曼编码。

使用0～7的二进制表示形式是另一种编码方案，请比较两种方案的优缺点。

五、（10分）设散列表地址空间为0..6，散列函数为H(x)=i mod 7，其中i为键值x中第一个字母在字母表中的序号，若键值的输入序列为Jen,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec，用链地址法处理冲突，1)构造散列表；2)求出在等概率情况下，查找成功时的平均查找长度。

六、（15分）（1）对下列数据表，写出采用希尔排序算法排序的每一趟的结果。

（100,12,20,31,1,5,44,66,61,200,30,80,150,4,8）（2）对下列数据表，写出采用快速排序算法排序的第一趟的结果。

（70,12,20,150，44,66,61,200,30,80,28）授课教师张海燕命题教师或命题负责人签字院系负责人签字年月日中国海洋大学命题专用纸（附页）if (!m) return 0;n=Paixu(T→rchild); if (!n) return 0;｝return 1;｝。

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

中国海洋大学数据库概论试卷1、下列选项中（）不是数据库系统的特点。

P321、数据结构化2、数据的共享性高，冗余度低，易扩充3、数据独立性高4、数据由DBMS统一管理和控制 [单选题] *A 、数据加工功能(正确答案)B 、数据共享高C 、数据与程序相互独立D 、数据冗余低2、关系数据表的关键字可由（）字段组成。

[单选题] *A 、一个B 、两个C 、多个D 、一个或多个(正确答案)3、下面（）不是正确的范式表达形式。

P51目前关系数据库有六种范式:第一范式(1NF)、第二范式(2NF)、第三范式(3NF)、巴斯-科德范式(BCNF)、第四范式(4NF)和第五范式(5NF，又称完美范式)。

[单选题] *A 、0NF(正确答案)B 、1NFC 、2NFD 、3NF4、（）不是关系的完整性约束。

P38 [单选题] *A．用户自定义完整性B．实体完整性C．参照完整性D．实数自动取整完整性(正确答案)5、在设计不好的关系模式中，存在的存储异常情况指（）。

P47 [单选题] * A．删除异常B．插入异常C．插入异常、数据冗余、删除异常、更新异常(正确答案)D．查询异常6、设 R 是一个关系模式，如果 R 中的每一个属性值都是不可分解的，则 P50 [单选题] *A．R∈1NF(正确答案)B．R∈2NFC．R∈3NFD．R∈4NF7、设 R 是一个 1NF 的关系模式，如果 R 中的每一个属性都是完全函数依赖于主属性的，则 P51 [单选题] *A．R∈1NFB．R∈2NF(正确答案)C．R∈3NFD．R∈4NF8、设 R 是一个 2NF 的关系模式，如果 R 中的每一个非主属性都不传递依赖于主码，则 P52 [单选题] *A．R∈1NFB．R∈2NFC．R∈3NF(正确答案)D．R∈4NF9、关于 ER 模型，下面描述错误的是（）。

P42 [单选题] *A. ER 模型即实体-联系模型是数据库概念模型的一种√B. 它用图形描述实体与实体之间的关系又叫 ER 图√C.ER 图中，实体、联系、属性分别用矩形、菱形和椭圆表示√D.ER 图中，菱形与矩形之间用箭头线表示联系，线上标注 1 或某个字母(正确答案)10、下面对关系数据库中的表进行的描述，不正确的是（）。

中国海洋大学2007-2008学年第1学期期末考试试卷
共4 页第2 页
共4 页第4 页
考试说明：本课程为闭卷考试，可携带文具(或本课程为开卷考试，可携带文具和资料)，满分为：100 分。

四、选择题(每空2分,共40分)
1．d d a c b
2. c d a d b
3．a b b a b
4．c b a b b
五、算法填空题(每空2分,共20分)
1．(1) la.length+lb.length （2）*pa++ (3) *pb++ (4)*pa++ (5)*pb++
2. (6)EnQueue(Q,P->lchild) （7）EnQueue（Q，P-rchild） (7)P=DeQueue(Q)
3. (9)Q->next=L->next (10)L->next=Q
三、（10分）【证明】
若n为节点总数，ni为度i的节点数，则
n=n0+n1+n2+n3+n4+n5 ①（2分）
令B为分支数目，B=n-1 ②（2分）
所有度分别由度为1，2，3，4，5的节点所提供
故B=n-1= n1+2n2+3n3+4n4+5n5 ③（2分）
由①、②及③知 n0= n2+2n3+3n4+4n5+1
由题意知：n2=2，n3=3，n4=4，n5=5，故
n0=2+2*3+3*4+4*5+1=41 （4分）
授课教师命题教师或
命题负责人签字年月日院系负责人签
字年月日。

2018年山东省中国海洋大学计算机基础综合考研真题第一部分数据结构一、选择题(每题2分，共20分)1.逻辑上通常可以将数据结构分为（）。

A.动态结构和静态结构B.顺序结构和链式结构C.线性结构和非线性结构D.初等结构和组合结构2.线性表是n个具有相同类型（）的有限序列(n>=0)。

A.表元素B.字符C.数据元素D.数据项3.在长度为n的顺序表的第i个位置上插入一个元素(1<=i<=n+1),元素的移动次数为（）。

A.n-i+1B.n-iC.iD.i-14.假设带头结点的单向循环链表的头指针为head,则该链表为空的判定条件是（）。

A.head==NULLB.head->next==NULLC.head!=NULLD.head->next=head5.在计算机内实现递归算法时所需的辅助数据结构是（）。

A.栈1B.队列C.树D.图6.广义表((a.b).c.d)的表头是（）。

A.aB.a,bC.(a,b)D.(a,b),c.d7.二维数组A[8][9]按行优先顺序存储，若数组元素A[2][3]的存储地址为1087,A[4][7]的存储地址为1153,则数组元素A[6][7]的存储地址为（）。

A.1207B.1209C.1211D.12138.下列陈述中正确的是（）。

A.二叉树是度为2的有序树B.二叉树中结点只有一个孩子时无左右之分C.二叉树中必有度为2的结点D.二叉树中最多只有两棵子树，并且有左右之分9.以下查找方法中，查找效率与记录个数n无直接关系的是（）。

A.顺序查找B.折半查找C.哈希查找D.二叉排序树查找10.下列排序算法中，算法（）在进行一趟相应的排序处理结束后不一定能选出一个元素放到其最终位置上。

A.直接选择排序B.冒泡排序C.归并排序D.堆排序二、简答题(每题12分，共36分)1.假设一棵二叉树的层次遍历序列为ABCDEFGHIJ,中序遍历序列为DBGEHJACIF,请画出这棵二叉树。