：码号证考 准题 写 要 不 内 线 封 密 ：业专考报 ：名姓生考
2024年全国硕士研究生招生考试初试自命题试题 （ B 卷) 科目代码： 855 科目名称： 数据结构与数据库技术
注意：所有答题内容必须写在答题纸上，写在试题或草稿纸上的一律无效；考完后试题随答题纸交回。 一、选择题(共 15 小题，每小题 2 分，共 30 分) 1、关于算法的时间复杂度，下列说法错误的是（ ）。 A）算法中语句执行的最大次数作为算法的时间复杂度 B）一个算法的执行时间等于其所有语句执行时间的量度 C）任一语句的执行时间为该语句执行一次所需的时间与执行次数的乘积 D）一般认为，随问题规模n的增大，算法执行时间的增长速度较快的算法最优。 2、在一个单链表中，若要删除指针p指向结点的后继结点，则执行（ ）。 A）p->next = p->next->next; B）p = p->next; p->next->next; C）free（p->next）; D）p = p->next->next； 3、链栈与顺序栈相比，有一个比较明显的优点是（ ）。 A）插入操作更加方便 B）通常不会出现栈满的情况 C）不会出现栈空的情况 D）删除操作更加方便 4、设有下三角矩阵用数组A[0..10,0..10]表示，按行优先顺序存放其非零元素，每个非零元素占2个字节，存放的基址为100，则元素A[5,5]的存放地址为（ ）。 A）110 B）120 C）130 D）140 5、将森林F转换为对应的二叉树T，F中叶子结点个数等于（ ）。 A）T中叶子结点的个数 B）T中度为1的结点数 C）T中左孩子指针为空的结点数 D）T中右孩子指针为空的结点数 6、已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点,则完全二叉树的结点个数最多是( )。 A）39 B）52 C）110 D）111 7、若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑第 1 页 共 6 页
序列的结论是（ ）。 A）存在，且唯一 B）存在，且不唯一 C）存在，可能不唯一 D）无法确定是否存在 8、对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是（ ）。 A）95 22 91 24 94 71 B）12 25 71 68 33 34 C）21 89 77 29 36 38 D）92 20 91 34 88 35 9、已知序列25，13，10，12，9为一大根堆，在序列尾部插入新元素18后，将其调整为大根堆的过程中需要进行的比较次数是（ ）。 A） 1 B） 2 C） 4 D） 5 10、数据库系统的数据独立性是指（ ）。 A）不会因为数据的变化而影响应用程序 B）不会因为系统数据存储结构与数据逻辑结构的变化而影响应用程序 C）不会因为数据存储策略的变化而影响数据存储结构 D）不会因为某些数据逻辑结构的变化而影响应用程序 11、设有关系R（A，B，C）和S（B，C，D），下列关系代数表达式中不成立的是（ ）。 A）ΠA（R）×ΠD（S） C）ΠC（R）∩ΠC（S） B）R∪S D）R×S 12、设有如下图所示的关系R，经操作?A,B(?B='b'(R))÷?B(?B='b'(R)) 的运算结果是（ ）。 R A B C A. A B B. B C. A D. A 13、对被参照关系进行（ ）操作时，关系数据库管理系统不需要进行参照完整性 检查。 A）删除一个元组 B） 修改一个元组 C）插入一个元组 D） 修改一个元组中主码的值 14、设有关系模式R（X，Y，Z）上的函数依赖集F=｛Y→Z，XZ→Y｝，则R 最高属于（ ）。 A） 2NF B） 3NF C）BCNF D） 4NF 第 2 页 共 6 页
a b c d a f c b d a c b b a c a c d c
15、给定关系模式SL（Sno，Sdept，Mname），其元组的语义是学生Sno在Sdept系学习，其系主任是Mname，并且一个学生只在一个系，一个系只有一名系主任。则SL的一个分解SS（Sno，Sdept），SM（Sno，Mname）（ ）。 A. 是既具有无损连接性，又保持了函数依赖 B. 是具有无损连接性，但不保持函数依赖 C. 不具有无损连接性，但保持了函数依赖 D. 既不具有无损连接性，也不保持函数依赖 二、填空题(共 10 小题，每小题 2 分，共 20 分) 1、线性表L＝（a1，a2，…an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是（ ）。 2、已知一颗树有2024个结点，包含120个叶子结点，该树对应的二叉树中无右孩子的结点个数是（ ）。 3、n个叶子结点的哈夫曼树中，总结点数为（ ）。 4、6个结点的无向图至少应有（ ）条边才能确保是一个连通图。 5、对22个记录的有序表折半查找，查找失败时至少需要比较（ ）次。 6、对n个关键字作快速排序，在最坏情况下，算法的时间复杂度是（ ）。 7、若关系模式R中的属性全部是主属性，则R的最高范式必定是（ ）。 8、设有关系模式R（U，F），其中，U＝（A，B，C，D，E，P），定义在其上的函数 依赖为F＝｛A→B，C→D，E→A，CE→P｝，模式R的候选键为（ ）。 9、在SQL语言中，如果要对结果进行分组，则SELECT子句后面只能出现（ ） 和聚集函数。 10、关系代数中，连接是由（ ）操作与选择操作组合而成的。 三、判断题(共 10 小题，每小题 2 分，共 20 分，对的打√，错的打×) 1、带头结点的单链表Head为空的判定条件是Head->next= =NULL。 2、栈S最多能容纳4个元素。现有6个元素按A、B、C、D、E、F的顺序进栈，则序列ADEBCF是可能的出栈序列。 3、树的后根遍历序列等同于该树对应的二叉树的后序遍历序列。 4、将森林转换为对应的二叉树,若在二叉树中,结点u是结点v的父结点的父结点,第 3 页 共 6 页
武汉科技大学2024年《855数据结构与数据库技术》考研专业课真题试卷【含参考答案】
