1、一、填空： 1顺序存储结构的特点是（ ），链接存储结构的特点是（ ）。 【解答】用元素在存储器中的相对位置来表示数据元素之间的逻辑关系，用指示元素存储地址的指针表示数据元素之间的逻辑关系。 2. 算法在发生非法操作时可以作出处理的特性称为（ ）。 【解答】健壮性 3. 常见的算法时间复杂度用大记号表示为：常数阶 ( )、对数阶 ( )、线性阶 ( )、平方阶 ( )和指数阶 ( )。 【解答】 (1)， (log2n)， (n)， (n2)， (2n) 4将下列函数按它们在 n 时的无穷大阶数，从小到大排列。 n, n-n3+7n5, nlogn, 2n/2, n3, log2n, n1/2+
2、log2n, (3/2)n, n!, n2+log2n 【解答】 log2n, n1/2+log2n, n, nlog2n, n2+log2n, n3, n-n3+7n5, 2n/2, (3/2)n, n! 5 在长度为 n的线性表中查找值为 x的数据元素的时间复杂度为： （ ）。 A O(0) B O(1) C O(n) D O(n2) 【解答】 C 6 在一个长度为 n的顺序表的第 i（ 1 i n+1）个元素之前插入一个元素，需向后 移动（ ）个元素，删除第 i（ 1 i n）个元素时，需向前移动（ ）个元素。 【解答】 n-i+1， n-i 7 在单链表中，除了头结点以外，任一结点的存
3、储位置由（ ）指示。 【解答】其前趋结点的指针域 8 当线性表采用顺序存储结构时，其主要特点是（ ）。 【解答】逻辑结构中相邻的结点在存储结构中仍相邻 9 栈通常采用的两种存储结构是（ ）；其判定栈空的条件分别是（ ），判定栈满的条件分别是（ ）。 【解答】顺序存储结构和链接存储结构（或顺序栈和链栈），栈顶指针 top= -1和 top=NULL，栈顶指针 top等于数组的长度和内存无可用空间 10（ ）可作为实现递归函数调用的一种数据结构。 【解答】栈 【分析】递归函数的调用和返回正好符合后进先出性。 11表达式 a*(b+c)-d的后缀表达式是（ ）。 【解答】 abc+*d- 【分析】将
4、中缀表达式变为后缀表达式有一个技巧：将操作数依次写下来，再将算符插在它的两个操作数的后面。 12 栈和队列是两种特殊的线性表，栈的操作特性是（ ），队列的操作特性是（ ），栈和队列的主要区别在于（ ）。 【解答】后进先出，先进先出，对插入和删除操作限定的位置不同 13数组通常只有两种运算：（ ）和（ ），这决定了数组通常采用（ ）结构来实现存储。 【解答】存取，修改，顺序存储 【分析】数组是一个具有固定格式和数量的数据集合，在数组上一般不能做插入、删除元素的操作。除了初始化和销毁之外，在数组中通常只有存取和修改两种操作。 14二维数组 A中行下标从 10到 20，列下标从 5到 10，按行优先
5、存储，每个元素占 4个存储单元， A105的存储地址是 1000，则元素 A1510的存储地址是（ ）。 【解答】 1140 【分析】数组 A中每行共有 6个元素，元素 A1510的前面共存储了 (15-10) 6+5个元素，每个元素占 4个存储单元，所以，其存储地址是 1000+140=1140。 15设有一个 10阶的对称矩阵 A采用压缩存储， A00为第一个元素，其存储地址为 d，每个元素占 1个存储单元，则元素 A85的存储地址为（ ）。 【解答】 d+41 【分析】元素 A85的前面共存储了 (1+2+ +8)+5=41个元素。 16 稀疏矩阵一般压缩存储方法有两种，分别是（ ）和（
6、 ）。 【解答】三元组顺序表，十字链表 17设高度为 h的二叉树上只有 度为 0和度为 2的结点，该二叉树的结点数可能达到的最大值是（ ），最小值是（ ）。 【解答】 2h -1， 2h-1 【分析】最小结点个数的情况是第 1层有 1个结点，其他层上都只有 2个结点。 18深度为 k的二叉树中，所含叶子的个数最多为（ ）。 【解答】 2k-1 【分析】在满二叉树中叶子结点的个数达到最多。 19具有 100个结点的完全二叉树的叶子结点数为（ ）。 【解答】 50 【分析】 100个结点的完全二叉树中最后一个结点的编号为100，其双亲即最后一个分支结点的编号为 50，也就是说，从编号 51开始 均
7、为叶子。 20 已知一棵度为 3 的树有 2 个度为 1 的结点， 3 个度为 2 的结点， 4 个度为 3 的结点。则该树中有（ ）个叶子结点。 【解答】 12 【分析】根据二叉树性质 3 的证明过程，有 n0=n2+2n3+1（ n0、 n2、 n3 分别为叶子结点、度为 2 的结点和度为 3 的结点的个数）。 21已知一个有向图的邻接矩阵表示，计算第 j个顶点的入度的方法是（ ）。 【解答】求第 j列的所有元素之和 22有向图 G用邻接矩阵 Ann存储，其第 i行的所有元素之和等于顶点 i的（ ）。 【解答】出度 23图的深度优先遍历类似 于树的（ ）遍历，它所用到的数据结构是（ ）；图
8、的广度优先遍历类似于树的（ ）遍历，它所用到的数据结构是（ ）。 【解答】前序，栈，层序，队列 24 对于含有 n 个顶点 e 条边的连通图，利用 Prim 算法求最小生成树的时间复杂度为（ ），利用 Kruskal 算法求最小生成树的时间复杂度为（ ）。 【解答】 (n2)， (elog2e) 【分析】 Prim 算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树； Kruskal 算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。 25顺序查找技术适合于存储结构 为（ ）的线性表，而折半查找技术适用于存储结构为（ ）的线性表，并且表中的元素必须是（ ）。 【解答】顺序存储和链接存
9、储，顺序存储，按关键码有序 26设有一个已按各元素值排好序的线性表，长度为 125，用折半查找与给定值相等的元素，若查找成功，则至少需要比较（ ）次，至多需比较（ ）次。 【解答】 1， 7 【分析】在折半查找判定树中，查找成功的情况下，和根结点的比较次数最少，为 1次，最多不超过判定树的深度。 27对于数列 25， 30， 8， 5， 1， 27， 24， 10， 20， 21， 9，28， 7， 13， 15， 假定每个结点的查找概率相同，若用顺序存储结构组织该数列，则查找一个数的平均比较次数为（ ）。若按二叉排序树组织该数列，则查找一个数的平均比较次数为（ ）。 【解答】 8， 59/1
10、5 【分析】根据数列将二叉排序树画出，将二叉排序树中查找每个结点的比较次数之和除以数列中的元素个数，即为二叉排序树的平均查找长度。 28长度为 20的有序表采用折半查找，共有（ ）个元素的查找长度为 3。 【解答】 4 【分析】在折半查找 判定 树中，第 3层共有 4个结点。 29对 n个元素进行起泡排序，在（ ）情况下比较的次数最少，其比较次 数为（ ）。在（ ）情况下比较次数最多，其比较次数为（ ）。 【解答】正序， n-1，反序， n(n-1)/2 30对一组记录（ 54, 38, 96, 23, 15, 72, 60, 45, 83）进行直接插入排序，当把第 7个记录 60插入到有序表
11、时，为寻找插入位置需比较（ ）次。 【解答】 3 【分析】当把第 7个记录 60插入到有序表时，该有序表中有 2个记录大于 60。 31对一组记录（ 54, 38, 96, 23, 15, 72, 60, 45, 83）进行快速排序，在递归调用中使用的栈所能达到的最大深度 为（ ）。 【解答】 3 32 对 n 个待排序记录序列进行快速排序，所需要的最好时间是（ ），最坏时间是（ ）。 【解答】 O(nlog2n)， O(n2) 二、 选择 1下述排序方法中，比较次数与待排序记录的初始状态无关的是（ ）。 A插入排序和快速排序 B归并排序和快速排序 C选择排序和归并排序 D插入排序和归并排序
12、【解答】 C 【分析】选择排序在最好、最坏、平均情况下的时间性能均为O(n2)，归并排序在最好、最坏、平均情况下的时间性能均为O(nlog2n)。 2 下列序列中，（ ）是执行第一趟快速排 序的结果。 A da， ax， eb， de， bb ff ha， gc B cd， eb， ax， da ff ha， gc， bb 3对初始状态为递增有序的序列进行排序，最省时间的是（ ），最费时间的是（ ）。已知待排序序列中每个元素距其最终位置不远，则采用（ ）方法最节省时间。 A 堆排序 B插入排序 C快速排序 D 直接选择排序 【解答】 B， C， B 【分析】待排序序列中每个元素距其最终位置不远
13、意味着该序列基本有序。 4 堆的形状是一棵（ ）。 A 二叉排序树 B 满二叉树 C 完全二叉树 D 判定 树 【解答】 C 【分析】从逻辑结构的角度来看，堆实际上是一种完全二叉树的结构。 5 静态查找与动态查找的根本区别在于（ ）。 A 它们的逻辑结构不一样 B 施加在其上的操作不同 C 所包含的数据元素的类型不一样 D 存储实现不一样 【解答】 B 【分析】静态查找不涉及插入和删除操作，而动态查找涉及插入和删除操作。 6 设散列表表长 m=14，散列函数 H(k)=k mod 11。表中已有 15、 38、 61、 84四个元素，如果用线性探侧法处理冲突，则元素 49的存储地址是（ ）。
14、A 8 B 3 C 5 D 9 【解答】 A 【分析】元素 15、 38、 61、 84分别存储在 4、 5、 6、 7单元，而元素 49的散列地址为 5，发生冲突，向后探测 3个单元，其存储地址为 8。 7 长度为 12的有序表采用顺序存储结构，采用折半查找技术，在等概率情况下，查找成功时的平均查找长度是（ ），查找失败时的平均查找长度是（ ）。 A 37/12 B 62/13 C 3 9/12 D 49/13 【解答】 A， B 【分析】画出长度为 12的折半查找判定树，判定树中有 12个内结点和 13个外结点。 8 用 n个键值构造一棵 二叉排序树，其最低高度为（ ）。 A n/2 B n C log2n D log2n+1 【解答】 D 【分析】二叉排序树的最低高度与完全二叉树的高度相同。 9 n个顶点的强连通图至少有（ ）条边，其形状是（ ）。 A n B n+1 C n-1 D n (n-1) E 无回路 F 有回路 G 环状 H 树状 【解答】 A， G 10 含 n 个顶点的连通图中的任意一条简单路径，其长度不可能超过（ ）。 A 1 B n/2 C n-1 D n 【解答】 C 【分析】若超过 n-1，则路径中必存在重复的 顶点。
