2015年第二炮兵工程大学843数据结构考研真题.pdf

1、2015 年第二炮兵大学 843 数据结构 考研真题 科目代码： 843 科目名称： 数据结构 适用学科：计算机科学与技术、计算机技术（专业学位） 一、填空题（ 110题，每空 2 分，共 20分） 1数据的逻辑结构可用二元组 B=(D, R)表示，其中 D是数据的有穷集合， R是（ ）。 2与中缀表达式 a-(b+c)*(d-e)等价的前缀表达式为（ ）。 3按后根次序遍历森林正好等于按（ ）遍历对应的二叉树。 4衡量一个查找算法效率的主要标准是（ ）。 5快速排序的时间复杂度是（ ）。 6两个串相等的充分必要条件是两个串的长度相等且（ ）。 7已知广义表 LS为空表，则其深度为（ ）。 8

2、如果排序过程不改变（ ）之间的相对次序，则称该排序方法是稳定的。 9能够成功完全拓扑排序的图一定是一个（ ）。 10在含 100个结点的完全二叉树中，叶子结点的个数为（ ）。 二、单项选择题（ 1130题，每题 2分，共 40分） 11如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（ ） A栈 B队列 C树 D图 12算法指的是（ ） A计算机程序 B解决问题的计算方法 C排序算法 D解决问题的有限运算序列 13在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（ ） A队列 B栈 C线性表 D有序表 14算术表达式 a+b*(c+d/e)转为后缀表达式后

3、为（ ） A ab+cde/* B abcde/+*+ C abcde/*+ D abcde*/+ 15折半查找的时间复杂性为（ ） A O(n2) B O(n) C O(nlogn) D O(logn) 16下面关于线性表的叙述中，错误的是哪一个？（ ） A线性表采用顺序存储，必须占用一片连续的存储单元。 B线性表采用顺序存储，便于进行插入和删除操作。 C线性表采用链接存储，不必占用一片连续的存储单元。 D线性表采用链接存储，便于插入和删除操作。 17 n个结点的完全有向图含有边的数目（ ） A n/2 B n*(n+1) C n*(n-1) D n*n 18在一个非空二叉树的中序遍历序列中

4、，根结点的右边（ ） A只有 右子树上的所有结点 B只有右子树上部分结点 C只有左子树上的部分结点 D只有左子树上的所有结点 19在待排序的元素序列基本有序的前提下，效率最高的排序方法是（ ） A选择排序 B插入排序 C快速排序 D归并排序 20一个栈的入栈序列是 1,2,3,4,5，则栈的不可能的输出序列是（ ） A 43512 B 54321 C 12345 D 45321 21在具有 n 个结点的有序单链表中插入一个新结点并使链表任然有序的时间复杂度是（ ） A O(1) B O(n) C O(nlogn) D O(n2) 22已知广义表 L=(x,y,z)， a， (u， t， w)，

5、从 L表中取出原子项 t的运算是（ ） A head(tail(head(tail(tail(L) B tail(head(head(tail(L) C head(tail(head(tail(L) D head(tail(tail(L) 23下列编码中属前缀编码的是（ ） A 1， 01， 000， 001 B 0， 1， 00， 11 C 0， 10， 110， 11 D 1， 01， 011， 010 24将森林转换为对应的二叉树，若在二叉树中，结点 u是结点 v的父结点的父结点，则在原来的森林中， u和 v 可能具有的关系是（ ） i. 父子关系 ii. 兄弟关系 iii. u的父结点

6、与 v的父结点是兄弟关系 A只有 ii B i和 iii C i和 ii D i、 ii和 iii 25以下序列不是堆的是（ ） A 100,85,40,77,80,60,66,98,82,10,20 B 100,85,98,77,80,60,82,66,40,20,10 C 100,98,85,82,80,77,66,60,40,20,10 D 10,20,40,60,66,77,80,82,85,98,100 26 3. 已知一棵含 30 个结点的二叉树中只有一个叶子结点，则该树中度为 1 的结点个数为（ ） A 0 B 1 C 28 D 29 27 如下图所示的有向无环图可以得到的拓扑序

7、列的个数是（ ） A 6 B 5 C 4 D 3 28下列二叉树中， 不 平衡的二叉树是（ ） 29为便于判别有向图中是否存在回路，可借助于（ ） A广度优先搜索算法 B最小生成树算法 C最短路径算法 D拓扑排序算法 30在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（ ） A都相同 B都不相同 C不一定相同 D互为逆序 三、简答题（ 3135题，共 50 分） 31（ 10 分）设有一个关键码的输入序列 55， 31， 11， 37， 46， 73， 63， 2， 7 。 （ 1）从空树开始构造二叉搜索树。 （ 2）从空树开始构造平衡二叉搜索树，若发生不平衡，指明需做的平衡

8、旋转的类型及平衡旋转的结果。 （ 3）在二叉搜索树和平衡二叉树中查找这些数据，分别计算在等概率条件下的搜索成功的平均搜索长度。 说明：第（ 1）问 2分，第（ 2）问 6分，第（ 3）问 2分。 32（ 10 分）设一棵二叉树的先序序列为 ABECDFGHIJ，中序序列为 EBCDAFHIGJ。 （ 1）画出这棵二叉树示意图，要求有中间步骤； （ 2）说明建立这棵二叉树的原理。 说明：第（ 1）问 6分，第（ 2）问 4分。 33（ 10 分）对于下图所示的带权无向网，从结点 a 出发，采用 PRIM 算法得到最小代价生成树，请画出所有可能的最小代价生成树，至少要求给出一个结果的中间步骤。 3

9、4（ 10 分）请回答下列关于堆（ Heap）的一些问题。 （ 1）堆的存储表示是顺序的，还是链接的？ （ 2）设有一个最小堆，即堆中任意节点的关键码均小于它的左子女和右子女的关键码。其具有最小值的元素在什么地方？具有最大值的元素可能在什么地方？ （ 3）对 n 个元素进行初始建堆的过程中，最少需要多少次数据比较？最多需要多少次数据比较（不用大 O表示法）？ 说明：第（ 1）问 2分，第（ 2）问 4分，第（ 3）问 4分。 35（ 10 分）将关键字序列（ 7、 8、 30、 11、 18、 9、 14）散列存储到散列列表中，散列表的存储空间是一个下标从 0开始的一个一维数组，散列函数为：

10、H(key)=(key*3) MOD 7，处理冲突采用线性探测再散列法，要求装填（载）因子为 0.7。 问题： （ 1）请画出所构造的散列表； （ 2）分别计算等概率情况下，查找成功和查找不成功的平均查找长度。 说明：第（ 1）问 5分，第（ 2）问 5分。 四、综合应用题（ 3639题，共 40分。 36、 37为必答题， 38、 39可任选一道） 36（ 15 分） 假设以带双亲指针的二叉链表作为二叉树的存储结构，其结点结构的类型说明如下所示： typedef char DataType; typedef struct node DataType data; struct node *lc

11、hild, *rchild; /*左右孩子指针 */ struct node *parent; /*指向双亲的指针 */ BinTNode; typedef BinTNode *BinTree; 若 root 指向根结点， px 为指向非空二叉树中某个结点的指针，可借助该结构求得 px 所指结点在二叉树的 中序序列 中的 后继 。 （ 1）就 中序序列后继 的不同情况，简要叙述实现求后继操作的方法。 （ 2）编写算法求 px所指结点的 中序序列后继 ，并在算法语句中加注注释。 37（ 15分） 设将 n（ n1）个整数存放到一维数组 R中，试设计一个 在时间和空间 两方面 尽可能有效 的算法，

12、将 R中的序列循环左移 p（ 0 p n）个位置，即将 R中的数据由（ X0, X1, , Xn-1）变换为（ Xp, Xp+1, , Xn-1, X0, X1, , Xp-1）。要求： （ 1）给出算法的基本设计思想。 （ 2）根据设计思想，采用 C或 C+或 JAVA语言表述算法，关键之处给出注释。 （ 3）说明你所设计算法的时间复杂度和空间复杂度。 38（ 10分，自选题） 假设以带头结点的单链表表示严格单调递增有序表（序列中没有相等的元素），单链表的类型定义如下： typedef struct node DataType data; struct node *next LinkNode

13、, *LinkList; 编写算法，从有序表 A（假设有 n个元素） la 中删除所有和有序表 B（假设有 m个元素） lb中元素相同的结点，并分析算法的时间复杂度。 39.（ 10分，自选题） 我国的高等院校虽然管理体制各具特色，但就其图书馆信息管理来说，一般都包括工作人员、读者、图书和出版社为客体，现请根据数据库设计方法设计反映一所大学的图书信息管理情况的数据库。（ 10 分） 具体信息可描述如下： （ 1）大学图书馆有多个工作人员，这些工作人员有两个职责，一个职责是负责图书借阅工作；另一个职责是负责图书信息、读者信息的更新维护，每个工作人员用唯一的 帐号和帐号类型、姓名、电话标识； （

14、2）每个工作人员可 管理 多个读者信息，读者也可被多个具有权限的工作人员管理； （ 3）每个工作人员可负责多本图书的入库登记，图书也可由任一工作人员进行登记，图书编号具有唯一性； （ 4）一个读者可借阅若干本图书，任何一种书也可为多个读者所借，但不同读者类型可借阅的书本数量以及时间有所不同，借书证号具有唯一性； （ 5）一个出版社可出版多种书籍，同一种书仅为一个出版社出版。 请根据现实情况，进一步分析大学图书管理信息系统中的各个实体集应具有的基本属性的基础上，完成以下任务： 1、进行数据库的概念结构设计，画出 E-R图（各实体集及联系集的属性请参照现实情况下，自拟）； 2、进行数据库的逻辑结构设计，给出该数据库的关系模型。