数据结构复习题及答案

1、数据结构复习题及参考答案题型说明各章内容符号名称分数答题说明章号内容章号内容章号内容A概念题201绪论07图13B填空题202线性表08查找14C选择题203栈和队列09内部排序15D判断题104串10文件16E问答题505数组和广义表1117F算法题806树和二叉树1218备注：0001 01B1数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间的和运算等的学科。0001操作对象关系0002 01B1数据结构被形式地定义为（D, R ），其中 D 是的有限集合， R 是 D上的有限集合。0002数据元素关系0003 01B2数据结构包括数据的数据的和数据的这三个方面的内容。00

2、03逻辑结构存储结构运算0004 01B1数据结构按逻辑结构可分为两大类，它们分别是和。0004线性结构非线性结构0005 01B1线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。0005一对一一对多多对多0006 01B1在线性结构中， 第一个结点前驱结点， 其余每个结点有且只有1 个前驱结点； 最后一个结点后续结点，其余每个结点有且只有1 个后续结点。0006没有没有0007 01B2在树形结构中， 树根结点没有结点，其余每个结点有且只有个前驱结点； 叶子结点没有结点，其余每个结点的后续结点数可以。0007前驱1后续任意多个0008 01B1在图形结构中

3、，每个结点的前驱结点数和后续结点数可以。0008任意多个0009 01B2数据的存储结构可用四种基本的存储方法表示，它们分别是。0009顺序链式索引散列0010 01B2数据的运算最常用的有5 种，它们分别是。0010插入、 删除、修改、查找、排序0011 01B2一个算法的效率可分为效率和效率。0011时间空间001201C1非线性结构是数据元素之间存在一种：（）A、一对多关系B、多对多关系C、多对一关系D、一对一关系0012B0013 01C1数据结构中，与所使用的计算机无关的是数据的（）结构；A、存储 B、物理C、逻辑D、 物理和存储0013C0014 01C1算法分析的目的是（）A、找

4、出数据结构的合理性B、 研究算法中的输入和输出的关系C、分析算法的效率以求改进D、 分析算法的易懂性和文档性0014C0015 01C1算法分析的两个主要方面是（）A、空间复杂性和时间复杂性B、 正确性和简明性C、可读性和文档性D、 数据复杂性和程序复杂性0015A0016 01C2计算机算法指的是（）A、计算方法B、排序方法C 、 解决问题的有限运算序列D 、 调度方法0016C0017 01C2计算机算法必须具备输入、输出和（）等 5 个特性。A、可行性、可移植性和可扩充性B、 可行性、确定性和有穷性C、 确定性、有穷性和稳定性D、 易读性、稳定性和安全性0017B0018 01A2数据结

5、构和数据类型两个概念之间有区别吗？0018简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。0019 01A1简述线性结构与非线性结构的不同点。0019线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是多对多的。0020 01A2分析下面各程序段的时间复杂度：for (i=0;in; i+)for (j=0; jm; j+)Aij=0;0020O（ m*n）0021 01A2分析下面各程序段的时间复杂度：s=0;for i=0; in; i+)for(j=0; jn; j+)s+=Bij;sum

6、=s;0021O （ n2）0022 01A2分析下面各程序段的时间复杂度：x=0;for(i=1; in; i+)for (j=1; j=n-i; j+)x+;00222因为 x+共执行了n-1+n-2+ 1= n(n-1)/2，所以执行时间为O（ n ）分析下面各程序段的时间复杂度：i=1;while(itop0、 ST-top=0、 ST-topm00026B0027 02B2、 ST-top=m0向一个长度为n 的向量的第i 个元素(1 i n+1) 之前插入一个元素时，需向后移动个元素。0027n-i+10028 02B2向一个长度为n 的向量中删除第i 个元素(1 i n) 时，需

7、向前移动个元素。0028n-i0029 02B1在顺序表中访问任意一结点的时间复杂度均为，因此，顺序表也称为的数据结构。0029O(1)随机存取0030 02B1顺序表中逻辑上相邻的元素的物理位置相邻。单链表中逻辑上相邻的元素的物理位置相邻。0030必定不一定0031 02B1在单链表中，除了首元结点外，任一结点的存储位置由指示。0031其直接前驱结点的链域的值0032 02B2在 n 个结点的单链表中要删除已知结点*p ，需找到它的，其时间复杂度为。0032前驱结点的地址O （ n）0033 02D1链表的每个结点中都恰好包含一个指针。（）0033X0034 02D1链表的物理存储结构具有同

8、链表一样的顺序。（）0034X0035 02D1链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。（）0035X0036 02D1线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。（）0036X0037 02D1顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。（）0037X0038 02D1顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（）0038X0039 02D1线性表在物理存储空间中也一定是连续的。（）0039X0040 02D1线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。（）0040X

9、0041 02D1顺序存储方式只能用于存储线性结构。（）0041X0042 02D1线性表的逻辑顺序与存储顺序总是一致的。（）0042X0043 02C1数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为（）A、存储结构B、逻辑结构C、顺序存储结构D、链式存储结构0043C0044 02C1一个向量第一个元素的存储地址是A、 110B、108C100，每个元素的长度为、 100 D 、1202，则第5 个元素的地址是（）0044B0045 02C1在n 个结点的顺序表中，算法的时间复杂度是 O（ 1）的操作是（ ） A 、 访问第 i 个结点（ 1 i n）和求第 i 个结

10、点的直接前驱（ B 、 在第 i 个结点后插入一个新结点（ 1 i n）C、 删除第 i 个结点（ 1 i n） D 、 将 n 个结点从小到大排序2 i n）0045A0046 02C2个有127 个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（A、 8B、63.5C、63D、7）个元素0046B0047 02C2链接存储的存储结构所占存储空间（）A、 分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B、 只有一部分，存放结点值C、只有一部分，存储表示结点间关系的指针D、 分两部分，一部分存放结点值，另一部分存放结点所占单元数0047A0048 02C1链表是一种采

11、用（）存储结构存储的线性表；A、顺序B、链式C、星式D、网状0048B0049 02C1线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）A、必须是连续的B、部分地址必须是连续的C、一定是不连续的D、连续或不连续都可以0049D0050 02C1线性表在（）情况下适用于使用链式结构实现。A、需经常修改中的结点值B、需不断对进行删除插入C、中含有大量的结点D、中结点结构复杂0050B0051 10B1若索引文件采用稠密索引, 则每个索引项与主文件中的_记录相对应 , 若索引文件采用稀疏索引, 则每个索引项与主文件中的_记录相对应 .0051一个一组 ( 成若干条 )0052 08E2已

12、知一堆数组A 中的数据如下, 试写出在快速排序的过程中每次划分后数据的排序情况.12345678 45 28 64 53 15 3674 30(1)(2)(3)005230283615 455374641528 3036455374 6415 28 30 36 45 53 64 740053 08C1下列排序算法中 ,第一趟排序完毕后 , 其最大或最小元素不一定在其最终位置上的算法是( )A、归并排序B 、直接选择排序C 、树形选择排序 D、冒泡排序0053A0054 08C1直接插入排序的时间复杂度为().2A、 O(n)B、 0(logn) C、 0(nlog2n) D 、 0(n )20

13、054d0055 10B1文件的检索和修改有两种方式_和 _0055实时的批量的0056 10C2对顺序文件的检索方法可以是()A、 顺序存取B 、随机存取 C、按关键字存取 D 、前三种方法都可以0056D0057 10B1在查找索引文件时, 首先要查找 _ ; 然后再查找 _0057索引表主文件0058 08E3利用堆排序的方法给已知数组A 中的数据排序 , 写出在构成初始堆和利用堆排序的过程中, 每次筛运算后数据的排列情况 :12345678A 45 2849 16 37 8256 751. 构成初始堆的过程(1)(2)(3)(4)2. 利用堆排序的过程(1)(2)(3)(4)(5)(6

14、)(7)00581.(1) 45 28 49 75 37 82 56 16(2) 45 28 82 75 37 49 56 16(3) 45 75 82 28 37 49 56 16(4) 82 75 56 28 37 49 45 162.(1) 75 37 56 28 16 49 45 82(2) 56 37 49 28 16 45 75 82(3) 49 37 45 28 16 56 75 82(4) 45 37 16 28 49 56 75 82(5) 37 28 16 45 49 56 75 82(6) 28 16 37 45 49 56 75 82(7) 16 28 37 45 49

15、 56 75 820059 08E2判断以下序列是否为堆, 若不是 , 调整为堆a.12,15,23,35,28,87,49,86b.35,12,28,87,49,86,15,230059a 为堆 b 不是堆b 相应的完全二叉树 :(35)(35)(35)(12)(12)(12) (28)(12)(28) (12) (15)(35) (15)(23) (15)(87)(49) (86)(15) (23)(49) (86)(15) (23)(49) (86)(28)(23)(49) (86)(28)(35)(49) (86)(28)(23)(87)(87)(87)(87)b 调整为堆排序列之后为

16、 12,23,15,35,49,86,28,87 0060 10C1堆排序的最坏时间复杂度为 ( )A、 0(n)B、 0(log 2n) C 、 0(nlog 2n) D 、 0(n 2)0060c0061 10B2设数组long int b46的首地址为s,按行主序方式存贮时元素b24,b34的存贮地址分别为_0061s+64s+880062 10E3设文件有 12 个记录 , 其关键字值分别为 37,23,7,79,9,43,3,19,31,61,23,47, 别给出用下列方法排序时第一 ,? 二趟处理后的结果序列按非递减的次序进行排序试分1. 冒泡排序 2. 选择排序 3. 快速排序0

17、0621. 第一趟 23,7,37,9,43,3,19,31,61,23,47,79 第二趟 7,23,9,37,3,19,31,43,23,47,61,792. 第一趟 37,23,7,47,9,43,3,19,31,61,23,79 第二趟 37,23,7,47,9,43,3,19,31,23,61,793. 第一趟 23,23,7,31,9,3 37 43,61,79,47第二趟 3,23,7,19,9 2331 37,43,61,79,470063 10B1文件按记录的结构可分为两类_和 _,? 按记录中关键字的多少可分为_和_0063定长记录文件不定长记录文件单关键字文件多关键字文件

18、0064 10B2外部分类包括 _和 _0064磁带文件的归并分类磁盘文件的归并分类0065 08B2设一组关键字为23,3,39,9,7,5,16,8,进行线性插入分类, 试写出第一遍分类后关键字的排列次序_006523 339975168第一遍 323 39975168第二遍 32339975168第三遍 39233975168第四遍 3792339 5168第五遍 35792339168第六遍 3579162339 8第七遍 357891623390066 08B2内部分类包括 ( 任写六种 )_0066冒泡分类希尔分类简单选择分类快速分类线性插入分类堆分类折半插入分类归并分类基数分类0

19、067 10B1磁带主要由 _,_,_ 组成 .0067磁带介质读写磁头磁带驱动器0068 08B1分类的目的是 _0068便于查询和处理数据0069 08B2你所学过的排序的方法中, 哪些是稳定的_0069直接插入二分 ( 折半 ) 插入冒泡归并排序枚举0070 08C2? ?下列排序算法中?,? 排序花费的时间不受数据开始排列特性影响的算法是()A 、直接插入排序 B 、冒泡排序 C 、直接选择排序 D 、快速排序0070c0071 08C2下列排序算法中, 最好情况下时间复杂度为0(n) 的算法是 ()A 、选择排序 B 、归并排序 C 、快速排序 D 、冒泡排序0071d0072 08

20、E3利用堆排序的方法给已知数据的排列情况 ( 要求构造大根堆)A 中的数据排序, 写出在构成初始堆和利用堆排序的过程中每次筛运算后数据12345678?A 45 28 49 16 37 8256 7500721:45 28 49 75 37 82 56 162:45 28 82 75 37 49 56 163:45 75 82 28 37 49 56 164:82 75 45 28 37 49 56 165:75 37 45 28 16 49 56 826:56 37 45 28 16 49 75 827:49 37 45 28 16 56 75 828:45 37 16 28 49 56 7

21、5 829:37 28 16 45 49 56 75 8210:28 16 37 45 49 56 75 8211:16 28 37 45 49 56 75 820073 10B1根据排序文件所处的位置不同, 可将排序分为 _和 _两大类 .0073内部外部0074 08D1堆排序是不稳定排序( )0074正确0075 10D1文件中存取数据的基本单位是数据项( )0075错误0076 08E2设文件有10 个记录其关键字值分别为 :37,23,7,79,29,43,73,19,31,61,试给出用冒泡排序法, 按非递减的次序进行排序过程中的每一趟结果序列.00763723 779 29 43

22、 73 19 3161第一趟23 737294373193161|79第二趟7 23293743193161| 73三 7 23 29 37 19 31 43 |61四 72329193137|43五 7 23 19 29 31 |37六 7192329|310077 08D2堆排序与快速排序相比, 堆比快速省时间( )0077错误0078 10D2影响外排序的时间因素主要是内存与外设交换信息的总次数( )0078正确0079 10B1ISAM文件由 _,_,_ 和 _组成 .0079主索引柱面索引磁道索引和主文件0080 10B1顺序文件是指按记录进入文件的先后顺序存放, 其 _顺序和 ?_

23、顺序一致的文件.0080逻辑物理0081 10B1文件的存储结构是指文件在_上的组织形式0081外存0082 10B1常用的文件组织方式有_,_,_和 _.0082顺序文件 . 索引文件 . 散列文件 . 多关键字文件0083 10B1文件是性质相同的_的集合 .0083记录0084 10B1文件中存取的基本单位是_文件中可使用的最小单位是_0084记录数据项0085 10B1文件结构包括 _,_ 以及在 _ 的各种操作0085逻辑.物理 .文件0086 10B1文件上的基本操作主要有两类_和 _0086索引.维护0087 10B1索引表中的每一项称为索引项, 一段索引项都是由_和 _ ? 所

24、在记录的物理地址组成的0087主关键字 .该关键字0088 10B1在排序过程中 , 若整个文件被在内存中处理, 排序时不涉及数据的内外存交换, 则称之为 _.0088内排序0089 10B1在排序过程中 , 若整个文件不完全在内存中处理, 排序时涉及数据的内,? 外存交换 , 则称之为 _0089外排序0090 10B1直接插入排序的时间复杂度是_ .009020(n)快速排序的平均时间复杂度是_.00910(nlog2n)0092 08E2对于给定的一组关键字 :38,64,52,13,47,85写出快速排序的各趟运行结果0092初始关键字 : 38,64,52,13,47,85第一趟13

25、 38 64,52,47,85二133852 47 64 85三133847 526485最后结果13 38 47 52 64 850093 08B2所谓归并是指将若干个_ 的子文件合并成一个有序的文件.0093已排序0094 08B2给定一组关键字91,28,72,63,15,101,79,46,81?将其用二路归并排序的各趟结果.0094初始关键字91 28 72 63 15 101 79 46 81第一趟28,91 63,72 15,101 46,79 81第二趟28,63,72,91 15,46,79,101 81第三趟15,28,46,72,79,91,101 81第四趟15,28,

26、46,63,72,81,91,1010095 08B2n 个关键字序列 k1,k2,.,kn称为堆 , 当且仅当该序列满足特性 _?和_(1=i=n/2)0095k=k2i ktop=-10102 03B2设有一栈 , 结点结构为data next栈顶指针为h. 则执行 ?*?s? 结点入栈操作是_ 和_.0102s-next=h-nexth=s0103 09B1在对有二十个数据有序表作二分查找时有_个结点的查找长度是 4.010340104 09C1用折半查找法的查找速度比用顺序查找法的查找速度_.A必然慢B必然快C 速度相等D快慢不定0104D0105 03D2假定有三个元素abc 进栈

27、, 进栈次序为 abc, 则可能出栈序列为 abc,?acb,bac, bca,cba ( )0105正确0106 09F2从循环单链表中查找出最大值.0106int searchmax(linklist l)int max;int *p;p=l;max=p-data;p=p-next;while (p-nextnil)if (maxdata) max=p-data;p=p-next;return max;0107 09F2从循环单链表中查找出最小值.0107int searchmin(linklist l)int min;int *p;p=l;min=p-data;p=p-next;whil

28、e (p-nextnil)if (minp-data) min=p-data;p=p-next;return min;0108 03B2栈是一种特殊的_, 又称为 _.0108线性表后进先出表0109 03C1设输入序列为A 、 1,2,3,4,51,2,3,4,5B借助一个栈不可能得到的输出序列是、 5,4,3,2,1C、 4,3,1,2,5(D)、1,3,2,5,40109C0110 09C1适合折半查找的表的存贮方式及元素排列要求为 ( A 、 链式存贮 元素无序 B 、 链式存贮 C 、 顺序存贮 元素无序 D 、 顺序存贮 0110)元素有序元素有序D0111 03D1顺序队列和循环

29、队列的队满及队空判断条件是一样的( )0111错误0112 03D1栈和队列都是线性表.( )0112正确0113 03D1排序和查找是两种基本的数据结构.()0113错误0114 09D1队列只能采用链式存储结构.( )0114错误0115 03B1队列是一种特殊的_, 允许插入的一端称为_,? 允许删除的一端称为_, 所以队列又称为_.0115线性表队尾队头先进先出表0116 03B1栈的两个重要应用是_和 _.0116在编译系统运行计算机语言程序的过程中, 利用栈进行语法检查, 实现递归调用 .0117 03A2栈和队列都是运算受到限制的特殊的线性表, 栈和队列有何不同?0117栈是仅允

30、许在一端进行插入和删除的线性表 , 又称为后进先出表 , 队列是允许在一端插入 , 在另一端删除的线性表 , 允许插入的一端的称为队尾 , 允许删除的一端称为队头 , 又称为先进先出表 .0118 09F2写出在有序表 A 上进行递归形式的折半查找的算法 , 其中给定值 K 为待查的关键字 , 若查找成功则返回该元素的下标 , 否则返回零值 .0118int binasearch(Sqlist s;keytype k;int low;int high;)int mid;while(low=high)mid=(low+high)/2;if(k=s.elemmid.key) return mid;

31、if(khigh) return -1;0119 03C1用数组 A 存放循环队列的元素值A、 (rear-front+m) mod mC 、 (rear-front-1+m) mod m, 若其头指针为front,尾指针为B 、 (rear-front+1) mod mD 、(rear-front) mod mrear,则循环队列中当前元素个数为().0119A0120 03A2设循环队列Q头指针为front,尾指针为rear,队列的最大容量为M,写出循环队列队满和队空的判定条件.0120队满条件 : (q.front+1)mod m=q.rear队空条件 : q.front=q.rear0

32、121 09F2对一个链式存贮结构的线性表进行顺序查找算法.0121struct nodeint data;struct node *next;typedef sealink(node *head,x)node *p;p=head-next;while (p!=NULL & p-data!=x)p=p-next;rerurn(p);0122 03F2给出循环队列的入队和出队算法.0122int ENQUEUE(sequeue *sq;datatype x)if(sq-front=(sq-rear+1)%maxsize)printf(queue is full); return NULL;els

33、esq-rear=(sq-rear+1)%maxsize;sq-datasq-rear=x;return(TRUE);datatype DEQUEUE(sequeue *sq)if(EMPTY(sq)printf(queue is empty);elsesq-front=(sq-front+1)%maxsize;return(sq-datasq-front;0123 09C1顺序查找法适用于存储结构为()的线性表.A 、 散列存储 B 、压缩存储 C 、顺序或链式存储D 、索引存储0123C0124 03B2由于查找运算的主要操作是关键字的比较一个查找算法效率优劣的标准., 所以 ,? 通常把

34、查找过程中对关键字需要执行的_作为衡量0124平均比较次数( 或平均查找长度)0125 03F2设计算法判断一个算术表达式的圆括号是否正确配对掉栈顶的 ),表达式被扫描完毕, 栈就为空 .),(提示 :? 对表达式进行扫描, 凡遇 (就进栈 , 遇 )就退0125boolean pair(b)stack s;s.top=0;i=1;ch=bi;while (ch!=)if (ch=() | (ch=)switch(:push(s,ch);break;):if empty(s) pair=false;return; else pop(s)i=i+1;ch=bi;if empty(s) pair=true;else pair=false;0126 09F2编写顺序查找算法, 并求在等概率情况下的平均查找长度ASL.0126typedef structdeytype key;datatype other;table;table rn+1;int SEQSEARCH(R,K)table R;keytype K;int i;Rn.key=K;i=0;while(Ri.key!=K) i+;if(i=n) return(-1);else return i;在等概率情况下的平均查找长度是ASL=(n+1)/20127 03B2程序段的输出结果是_（队列