1、数据结构导论试题一（课程代码：2142）一、单项选择题（本大题共 15 小题，每小题 2 分，共 30 分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1算法指的是 【 A 】A对特定问题求解步骤的一种描述。 B计算机程序C排序方法 D数据处理2在数据结构课程里决定选取何种存储结构时，一般不考虑 【 A 】A各结点的值如何 B结点个数的多少C对数据有哪些运算 D所用编程语言实现这种结构是否方便3线性表采用链接存储时，其地址 【 D 】A必须是连续的 B部分地址必须是连续的C一定是不连续的 D连续与否均可以4设线性表有 n 个元素，在
2、顺序表上实现比在链表上实现效率高的算法是 【 A 】A输出第 i(0in1)个元素值B交换第 0 个元素与第 1 个元素的值 C顺序输出这 n 个元素的值D输出与给定值 x 相等的元素在线性表中的序号5在一个以 head 为头指针的非空循环单链表中，尾结点指针 p 满足 【 A 】A.p-next=head B.p-next=NULL C.p=NULL D.p=head6若用一个大小为 6 的数组来实现循环队列，且队尾指针 rear 和队头指针 front 的值分别为 0 和 3，当从队列中删除一个元素，再加入两个元素后，rear 和 front 的值分别为多少【 B 】A. 1 和 5 B.
3、 2 和 4 C. 4 和 2 D. 5 和 1 7若一个栈的输入序列是 1，2，3，n，输出序列的第一个元素是 n，则第 i 个输出元素是 【 D 】A不确定 Bn-i C n-i-1 Dn-i+18对特殊矩阵采用压缩存储的目的主要是为了 【 D 】A表达变得简单 B对矩阵元素的存取变得简单C去掉矩阵中的多余元素 D减少不必要的存储空间9设二叉树有 n 个结点，则其深度为 【 D 】An 一 1 Bn C D不能确定10按照二叉树的定义，具有 3 个结点的二叉树有 【 C 】A3 种 B4 种 C 5 种 D6 种11对具有 n 个结点的完全二叉树按层次顺序编号，则编号为 i 的结点（2in
4、 ）的左孩子结点的编号是 【 B 】Ai B2i+1 C2i-1 D不存在12对一棵二叉排序树采用中根遍历进行输出的结点序列一定是 【 B 】A递增或递减序列 B递增序列 C无序序列 D递减序列13在一个有序表为（10,13,19,21,32,42,48,65,79, 81,85,99,108） ，当二分查找值为 85 的结点时，要 次查找成功。 【 A 】A2 B3 C4 D514堆的形状是一棵 【 A 】A二叉排序树 B满二叉树 C. 完全二叉树 D判定树15一组关键码序列为46， 79，56，38，40，84 ，则利用快速排序方法，以第 1 个记录为基准得到的第一趟排序序列为 【 A 】
5、A38，40，46，56，79，84 B40，38，46，79，56，84C40，38，46，56，79，84 D40，38，46，84，56，79二、填空题（本大题共 15 小题，每小题 2 分，共 30 分）请在每小题的空格中填上正确答案。错填、不填均无分。1数据元素之间逻辑关系的整体称为数据的 逻辑结构 ，它是数据的组织形式。2对同一个问题可以设计出求解它的不同算法，因此，通常从四个方面来评价算法的质量，它们是： 正确性 、易读性、健壮性和高效率。3在一个长度为 n 的顺序表中删除第 i 个结点时，需要移动 N-I+1 个结点。4线性表的常见链式存储结构有 单链表、循环链表和双链表。5一
6、个具有 n 个结点的单链表，在指针 p 所指结点后插入一个新结点的时间复杂性为O（n） 。6用 push 表示入栈操作，用 pop 表示出栈操作。设有一个空栈，现有输入序列为1、2、3、4、5，经过 push,push,pop,push,pop,push,push 后，输出的序列是 2,3, 。7循环队列用数组 A0.m-1存放其元素值，已知其头尾指针分别是 front 和 rear ，则当前队列的元素个数是_(rear-front+(m-1)%(m-1)_。8一个矩阵 A 中，如果非零元素个数远远小于矩阵的元素个数，并且非零元素的分布没有规律，则称 A 为 稀疏矩阵 。9假设根结点的层数为，
7、具有个结点的二叉树的最大高度是_1_。10拥有 100 个结点的完全二叉树的最大层数为_99_。 11设树 T 的度为 4，其中度为 1，2，3 和 4 的结点个数分别为 4，2，1，1 则 T 中的叶子数为 。12从空树开始，用序列20 , 35 , 40 ,15 , 30 , 25 , 38构造成一棵二叉排序树后值 15 在此树的第_2_层上。13在 8 个结点的有序顺序表中进行二分查找，最大的比较次数是 。14排序的方法有很多种， 直接插入排序 方法是从未排序序列依次取出元素，与已经排序序列中的元素作比较，将其放入已排序序列的正确位置上。15对 n 个元素进行冒泡排序，在所有元素有序的情
8、况下比较的次数为 n(n-1)/2 。三、应用题（本大题共 5 小题，每小题 5 分，共 25 分）1若频繁地对一个线性表进行插入和删除操作，则该线性表宜采用何种存储结构，为什么?链式存储结构。因为插入和删除操作需要从头结点起查找被插入或删除结点的前驱结点，并修改这些结点的指针域，查找过程平均移动指针域为表长的一半；而采用顺序结构存储线性表，插入和删除操作需要平均移动表中的一半元素。但移动指针域操作比移动元素操作花费的时间少得多。2设有编号为 1，2，3，4，5，6 的六辆列车，顺序进入一个栈式结构的站台，问：能否得到编号序列为 435612 不能和 135426 能的出站顺序，并说明为什么不
9、能得到或者如何得到。 （进栈操作用 push 表示,出栈操作用 pop 表示）3对如下图所示的一棵二叉树，试写出它的先根遍历、中根遍历和后根遍历的结果序列。先根：ABDEGCF中根：DBGEACF后根：DGEBFCA4一棵二叉排序树的结构如下图，结点的值为 18 ，请在各结点所在的圆圈内标出合适的值。5有一随机数组(25,84,21,46,13,27,68,35,20),现采用某种方法对它们进行排序,其每趟排序结果如下, 则该排序方法是什么? 该种排序方法的时间复杂性为多少？空间复杂度为多少？初 始:25,84,21,46,13,27,68,35,20 第一趟:20,13,21,25,46,2
10、7,68,35,84第二趟:13,20,21,25,35,27,46,68,84 第三趟:13,20,21,25,27,35,46,68,84四、算法设计题（本大题共 2 小题，第 1 小题 8 分，第 2 小题 7 分，共 15 分）1线性表的删除运算是指将表的第 i（1in）个结点 X 删除，试编写一个算法实现此操作。要求线性表的存储结构使用带表头结点的单链表结构。(假设头指针为 head)2设二叉树的结点类型定义如下：typedef struct btnode *bitreptr;struct btnode datatype data;bitreptr lchild,rchild;bitreptr root;试编写一个二叉树先根遍历的递归算法（void preorder（bitreptr r） ） 。
