(总分：78.00，做题时间：90分钟)
一、}选择题}(总题数：28，分数：56.00)
1.计算机算法指的是 __它必须具备输入、输出，可执行性、确定性和有穷性。
分数：2.00）
a.计算方法。
b.排序方法。
c.解决问题的有限运算序列√
d.调度方法。
解析：2.设计一个“判别在表达式中左、右括号是否配对出现”的算法，采用 __数据结构最佳。
分数：2.00）
a.线性表的顺序存储结构。
b.栈√c.队列。
d.线性表的链式存储结构。
解析：3.若对一棵二叉树进行中序遍历得到的结果是(b，d，a，g，h，e，c，f)，进行后序遍历的结果是dbhgefca，那么这棵二叉树进行前序遍历得到的结果是 __
分数：2.00）
a.(a， b， d， c， e， g， h，√
b.(a， b， d， c， e， h， g，c.(d，b，a，c，e，g，h，d.无法确定。
解析：4.一个队列的入列序号是1，2，3，4，则队列的输出系列是 __
分数：2.00）
a.4，3，2，1
b.1，2，3，4√
c.1，4，3，2
d.3，2，4，1
解析：5.对关键字序列(11，12，13，14，15)采用对半查找算法查找关键字11，则关键字之间比较次数为 __
分数：2.00）
a.1b.2√
c.3d.4
解析：6.如果以链表为栈的存储结构，则出栈操作是 __
分数：2.00）
a.必须判别栈是否为满。
b.必须判别栈是否为空√
c.判别栈元素的类型。
d.对栈不作任何判别。
解析：7.在算法设计基本方法中， _是从初始条件出发，逐次推出所需求的结果。
分数：2.00）
a.递推√b.递归。
c.列举法。
d.归纳法。
解析：8.分析算法的目的是 __
分数：2.00）
a.找出数据结构的合理性。
b.研究算法中的输入和输出的关系。
c.分析算法的效率以求改进√
d.分析算法的易懂性和文档。
解析：9.若完全二叉树共有n个结点，且从根结点开始，按层序(每层从左到右)用正整数 0，1，2，…，n-1，从小到大对结点编号，则对于编号为k的结点，错误的是 __
分数：2.00）
a.若k＞0，则该结点的父结点编号为[k/2]([表示取整)
b.若2k＞n-1，则编号为k的结点无右子树，但可能有左子树√
c.若2k+1＜=n-1，则编号为k的结点的右子结点编号为2k+1
d.若k=0，则该结点肯定没有父结点。
解析：10.用数组a[0…m-1]存放循环队列的元素值，若其头尾指针分别为front和rear，则循环队列中当前元素的个数为 __
分数：2.00）
a.(rear-front+rmod m√
b.(rear-front+m+1)mod m
c.(rear-front+m-1)mod m
d.(rear-front-m-1)mod m
解析：11.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为 __
分数：2.00）
c.(n+1)/2√
d.(n-1)/2
解析：12.设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用 __排序法。
分数：2.00）
a.希尔排序。
b.冒泡排序。
c.堆排序√
d.快速排序。
解析：13.链栈与顺序栈相比，有一个比较明显的优点是 __
分数：2.00）
a.插入操作更加方便。
b.通常不会出现栈满情况√
c.不会出现栈空的情况。
d.删除操作更加方便。
解析：14.对线性表进行二分法检索。其前提条件是 __
分数：2.00）
a.线性表以顺序方式存储，并且按关键码值排好序√
b.线性表以顺序方式存储，并且按关键码的检索频率排好序。
c.线性表以链接方式存储，并且按关键码值排好序。
d.线性表以链接方式存储，并且按关键码的检索频率排好序。
解析：15.下列关于数据结构的叙述中，正确的是 __
分数：2.00）
a.实际应用中，队列的顺序存储结构一般采用循环队列的形式√
b.递推算法结构程序一般比递归算法结构程序更精练。
c.树是一种线性结构。
d.用一维数组存储二叉树，总是以先序遍历的顺序存储各结点。
解析：16.完全二叉树中，若一个结点是叶结点，则它没有 __
分数：2.00）
a.左子结点。
b.右子结点。
c.左子结点和左子结点√
d.左子结点、右子结点和兄弟结点。
解析：17.下面关于数据结构的叙述中，正确的是 __
分数：2.00）
a.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
b.链表中的每一个结点都包含恰好一个指针。
c.包含n个结点的二叉排序树的最大检索长度为log2n
d.将一棵树转换为二叉树后，根结点没有右子树√
解析：18.一组记录的排序码为(46，79，56，38，40，84)，则利用堆排序的方法建立的初始堆为 __
分数：2.00）
a.79，46，56，38，40，84
b.84，79，56，38，40，46√
c.84，79，56，46，40，38
d.84，56，79，40，46，38
解析：19.下述几种排序方法中， _是最简单的交换类排序方法。
分数：2.00）
a.冒泡排序√
b.插入排序。
c.快速排序。
d.选择排序。
解析：20.在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是 __
分数：2.00）
a.希尔排序。
b.冒泡排序。
c.插入排序。
d.选择排序√
解析：21.二分法查找 __存储结构。
分数：2.00）
a.只适合于链式。
b.只适合于顺序√
c.既适合于顺序也适合于链式。
d.既不适合于顺序也不适合于链式。
解析：22.对含有n个关键词的序列进行冒泡法排序，最少的比较次数是 __
分数：2.00）
解析：23.下面关于二叉树的叙述中正确的是 __
分数：2.00）
a.度为2的树称为二叉树。
b.二叉树的度肯定是2
c.二叉树中所有结点的度都是2
d.由3个结点可以构造出5种不同的二叉树√
解析：24.对给定的整数序列(541，132，984，746，518，181，946，314，205，827)进行从小到大的排序时，采用快速排序(以中间元素518为基准)的第一趟扫描结果是 __
分数：2.00）
a.(181，132，314，205，541，518，946，827，746，984)
b.(541，132，827，746，518，181，946，314，205，984)
c.(205，132，314，181，518，746，946，984，541，827)√
d.(541，132，984，746，827，181，946，314，205，518)
解析：25.设栈s和队列q的初始状态为空，元素e1，e2，e3，e4，e5，e6依次通过栈s，一个元素出栈后即进入栈队列q，若6个元素出队的顺序是e2，e4，e3，e6，e5，e1，则栈s的容量至少应该是 __
分数：2.00）
a.6b.4
c.3√d.2
解析：26.按照二叉树的定义，深度为5的二叉树至多有 __个结点。
分数：2.00）
a.16b.32
c.10d.31√
解析：27.采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为 __
分数：2.00）
解析：28.以下叙述正确的是 __
分数：2.00）
a.线性表的线性存储结构优于链表存储结构。
b.在树形结构中，树根结点没有前驱结点√
c.栈的操作方式是先进先出。
d.队列的操作方式是先进后出。
解析：二、}填空题}(总题数：11，分数：22.00)
29.一个算法通常由对数据对象的运算和操作以及算法的} 【1】 }两种基本要素组成。
分数：2.00）
填空项1正确答案：控制结构）
解析：30.算法复杂度包括时间复杂度和空间复杂度。对空间复杂度一般可以用平均态和最坏情况复杂性来衡量：而对于空间复杂度，一般指执行该算法所需要的} 【2】 }
分数：2.00）
填空项1正确答案：内存空间）
解析：31.在数据结构的图形结构中，每个结点的前驱结点数和后续结点数可以} 【3】 }个。
分数：2.00）
填空项1正确答案：任意多）
解析：32.在树中，一个结点的直接子结点的个数称为该结点的} 【4】 }
分数：2.00）
填空项1正确答案：一次数/度）
解析：33.设只包含根结点的二叉树的高度为0，则高度为k的二叉树的最小结点数为} 【5】 }
分数：2.00）
填空项1正确答案：k+1）
解析：34.已知一棵二叉树前序序列和中序序列分别为a，b，d，e，g，c，f，h和d，b， g，e，a，c，h，f，则该二叉树的后序序列为} 【6】 }
分数：2.00）
填空项1正确答案：d，g，e，b，h，p，c，a）
解析：35.从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素进行比较，将其放入已排序序列正确位置上的方法，称为} 【7】 }
分数：2.00）
数据结构与算法
本章知识要点 算法的基本概念 数据结构的定义 线性表的定义和存储 树 二叉树的定义和存储 查找与排序算法。算法 algorithm 是一组有穷的规则，规定了解决某一特定类型问题的一系列运算，是对解题方 与完整的描述。算法是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。在计算机科学中...
算法与数据结构
学院专业姓名学号。实验1 线性表的操作 12学时 问题描述 假设一个班级内有n个学生，定义一个学生类和一个班级类。学生类中包括学号 姓名 性别 年龄 专业等属性 班级类包括一个学生对象链表。定义如下 class student class myclass student stu head 链表表头指...
算法与数据结构
1 简述算法的概念及其五个重要特性。2 下图是用邻接表存储的图，请画出此图，写出其邻接矩阵以及从c点开始分别按广度优先搜索和深度优先搜索遍历该图的结果。给定一棵用二叉链表表示的二叉树，其根指针为root，编写求此二叉树叶结点个数的算法，要求先写出二叉链表的类型定义。2.编写简单选择排序的算法。1 用...