温 州 师 范 学 院 期 末 考 试 纸 《数据结构》试题3 一．选择题（每个2 分，共10 分） 1． 下列关于数据结构的叙述中，正确的是 （ ） A）数组是同类型值的集合 B）递归算法的程序结构比迭代算法的程序结构更为精炼 C）树是一种线性结构 D）用一维数组存储二叉树，总是以先序遍历的顺序存储各结点 2． 用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是（ ） A）94、32、40、90、80、46、21、69 B）32、40、21、46、69、94、90、80 C）21、32、46、40、80、69、90、94 C）90、69、80、46、21、32、94、40 3． 如果要求一个线性表既能较快地查找，又能适应动态变化的要求，则可采用的方法是（ ） A）分块法 B）顺序法 C）二分法 D）散列法 4． 以下关于广义表的叙述中,正确的是 （ ） A) 广义表是0 个或多个单元素或子表组成的有限序列 B) 广义表至少有一个元素是子表 C) 广义表不可以是自身的子表 D) 广义表不能为空表 5． 在顺序表(3,6,8,10,12,15,16,18,21,25,30)中,用二分法查找关键码值11,所需的关键码比较次数为（ ） A) 2 B) 3 C) 4 D) 5 二．填空题（每格1 分，共20 分） 1. 结点在物理上的存储结构有四种，分别为顺序存储结构、__ __、_____ __和________________。 2. 数据结构是指数据的组织形式，它一般包括三个方面，它们是____________、___ _____和_________________。 3. 有一个链 表，头 结点为head，现 在已 建 立 一个新 结点q,把 q 插入到最前 面的二句 语 句 为代码为_________________和_________________。 4. 数据的逻 辑 结构被 分为______ _____、__________ __、____ ______和___ ______四种。 5. 高 度 为4 的二叉树中，结点数最多为___ ______，最少为_______________。 温 州 师 范 学 院 期 末 考 试 纸 6. 在一个具有n 个顶点的无向图中，要连通所有顶点则至少需要____________条边。 7. 假定一个图具有n 个顶点和e 条边，则采用邻接矩阵、邻接表数组表示时，其应的空间复杂度分别为_______________和__________。 8. 快速排序在平均情况下的时间复杂度为_______________，在最坏情况下的时间复杂度为________________，该排序方法为____________(稳定/不稳定)。 三．分析题（每题 5 分，共 30 分） 1. 有一棵二叉树，如下图所示，分别写出三种编...
