旧数据结构导论试卷一.doc

数据结构导论试题一（课程代码：2142）一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1算法指的是 【 A 】A对特定问题求解步骤的一种描述。 B计算机程序C排序方法 D数据处理2在数据结构课程里决定选取何种存储结构时，一般不考虑 【 A 】A各结点的值如何 B结点个数的多少C对数据有哪些运算 D所用编程语言实现这种结构是否方便3线性表采用链接存储时，其地址 【 D 】A必须是连续的 B部分地址必须是连续的C一定是不连续的 D连续与否均可以4设线性表有n个元素，在顺序表上实现比在链表上实现效率高的算法是 【 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. 2和4 C. 4和2 D. 5和1 7若一个栈的输入序列是1，2，3，n，输出序列的第一个元素是n，则第i个输出元素是 【 D 】A不确定 Bn-i Cn-i-1 Dn-i+18对特殊矩阵采用压缩存储的目的主要是为了 【 D 】A表达变得简单 B对矩阵元素的存取变得简单C去掉矩阵中的多余元素 D减少不必要的存储空间9设二叉树有n个结点，则其深度为 【 D 】An一1 Bn C D不能确定10按照二叉树的定义，具有3个结点的二叉树有 【 C 】A3种 B4种 C5种 D6种11对具有n个结点的完全二叉树按层次顺序编号，则编号为i的结点（2in）的左孩子结点的编号是 【 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 】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一个具有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假设根结点的层数为，具有个结点的二叉树的最大高度是_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个元素进行冒泡排序，在所有元素有序的情况下比较的次数为 n(n-1)/2 。三、应用题（本大题共5小题，每小题5分，共25分）1若频繁地对一个线性表进行插入和删除操作，则该线性表宜采用何种存储结构，为什么?链式存储结构。因为插入和删除操作需要从头结点起查找被插入或删除结点的前驱结点，并修改这些结点的指针域，查找过程平均移动指针域为表长的一半；而采用顺序结构存储线性表，插入和删除操作需要平均移动表中的一半元素。但移动指针域操作比移动元素操作花费的时间少得多。2设有编号为1，2，3，4，5，6的六辆列车，顺序进入一个栈式结构的站台，问：能否得到编号序列为435612不能和135426能的出站顺序，并说明为什么不能得到或者如何得到。（进栈操作用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,27,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设二叉树的结点类型定义