《2017年北京市培养单位空间应用工程与技术中心863计算机学科综合(专业)之数据结构考研强化模拟题.doc》由会员分享，可在线阅读，更多相关《2017年北京市培养单位空间应用工程与技术中心863计算机学科综合(专业)之数据结构考研强化模拟题.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年北京市培养单位空间应用工程与技术中心863计算机学科综合(专业)之数据结构考研强化模拟题一、填空题1 对n 个记录的表rl.n进行简单选择排序，所需进行的关键字间的比较次数为_。【答案】n （n-1）/2【解析】第一次需要n-1次比较，第i 此需要n-i 此比较，所以共需要、n-l+n-2+.+l=n（n-l ）/2。 2 棵有个结点的满二叉树有_个度为1的结点、有_个分支（非终端）结点和_个叶子，该满二叉树的深度为_。 【答案】或【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。 3 在下面的程序段中，对X 的赋值语句的时间复杂度为_（表示为n 的函数）。 【
2、答案】1（12）（123）?（l 2. n ）=n（n 1）（n 2）/6，即【解析】当i=l时，赋值语句就被执行了一次。当i=2时，赋值语句被执行了12次。当i=3时，赋值语句被执行了123次。可以推出赋值语句总共被执行了1（12）（123）（l 2. n ）=n（n 1）（n 2）/6次。 4 在双向循环链表中，向P 所指的结点之后插入指针f 所指的结点，其操作是_、_、_、_。 【答案】 5 在循环队列中，队列长度为n ，存储位置从0到，【答案】 编号，以rear 指示实际的队尾元素，现要在此队列中插入一个新元素，新元素的位置是（ ）。6 二叉树由_，_，_三个基本单元组成。【答案】根结
3、点；左子树；右子树 7求REPLACE （S ，V , m ）=_。 已知【答案】 8 在一个具有n 个单元的顺序栈中，假定以地址高端（即下标为n 的单元）作为栈底，以top 作为栈顶指针，则当向栈中压入一个元素时，top 的变化是top=_。 【答案】【解析】由于栈底在地址高端，栈中压入一个元素时，栈顶向地址底端移动一个单位，所以 9 一个有2001个结点的完全二叉树的高度是_。【答案】11【解析】完全二叉树的高度 10对于给定的元素，可以构造出的逻辑结构有_，_，_，_四种。【答案】集合；线性结构；树形结构；图状结构（网状结构） 二、判断题11线性表采用链表存储时，结点和结点内部的存储空间
4、可以是不连续的。（ ） 【答案】【解析】对于链式存储，数据元素之间的存储地址不一定是相邻的，即结点的存储空间可以是不连续的。而结点内部的存储空间需要是连续的，因为它是一个完整的数据。 12数据结构的抽象操作的定义与具体实现有关。（ ） 【答案】【解析】数据结构的抽象操作定义取决于客观存在的一组逻辑特性，与其在计算机内具体表示和实现无关。 13在伙伴系统中的伙伴是指任意两块大小相同、位置相邻的内存块。（ ）【答案】【解析】伙伴系统的伙伴不一定是位置相邻的内存块。起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下： 只要符合公式的内存块都是伙伴。 14数据元素是数据的最小单位。（ ）
5、【答案】【解析】数据项是数据的不可分割的最小单位，而数据元素是数据的基本单位。 15设栈采用顺序存储结构。若已有个元素入栈，则将第i 个元素入栈时，入栈算法的时间复杂性为（ ） 【答案】【解析】由于该栈采用顺序存储结构，时间复杂度应该为0（1）。 16二叉树中序线索化后，不存在空指针域。（ ）【答案】【解析】非空二叉树中序遍历第一个结点无前驱，最后一个结点无后继，这两个结点的前驱线索和后继线索为空指针。 17归并排序辅助存储为【答案】【解析】归并排序的辅助存储是 18稀疏矩阵压缩存储后，必会失去随机存取功能。（ ）【答案】【解析】稀疏矩阵在压缩存储后，必回失去随机存储的功能。因为在这个矩阵中，
6、非零元素的分布是没有规律的，为了压缩存储，就将每一个非零元素的值和它所在的行、列号做为一个结点存放在一起，这样的结点组成的线性表中叫三元组表，它已不是简单的向量，所以无法用下标直接存取矩阵中的元素。 19数据的逻辑结构是指数据的各数据项之间的逻辑关系。（ ） 【答案】【解析】数据的逻辑结构是指数据元素之间的逻辑关系。 20在一个设有头指针和尾指针的单链表中，执行删除该单链表中最后一个元素的操作与链表的长度无关。（ ） 【答案】【解析】必须从头指针开始，查找到尾指针所指结点的前驱结点的指针。（ ）三、算法设计题21已知二叉树T ，试写出复制该二叉树的算法（t T ）。【答案】算法如下：一、填空题考研试题
