数据结构复习题及答案教材

1、、选择题。 (每小题 2 分，共 40分)(1) 计算机识别 . 存储和加工处理的对象被统称为 AA. 数据 B. 数据元素C. 数据结构 D. 数据类型(2)数据结构通常是研究数据的及它们之间的联系。A. 存储和逻辑结构B.存储和抽象C.理想和抽象D.理想与逻辑(3)不是数据的逻辑结构是A. 散列结构B.线性结构C. 树结构D.图结构B. 静态结构与动态结构D. 紧凑结构与非紧凑结构 B 方面的内容。并行性时空复杂度_。B. 正确性和简明性数据复杂性和程序复杂性的有限序列(nz 0)B.字符D. 数据项 数据结构被形式地定义为D,R,其中D是B的有限集，R是C的有限集。A. 算法B.数据元素

2、C. 数据操作D.逻辑结构(5) 组成数据的基本单位是 A 。A. 数据项B.数据类型C. 数据元素D.数据变量 设数据结构 A=(D，R)，其中 D=1，2，3，4，R=r，r=1，2，2，3，3，4，4，1，则数据结构 A 是 A 。A. 线性结构B.树型结构C. 图型结构D.集合(7) 数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为_ CA. 存储结构B.逻辑结构C. 顺序存储结构D.链式存储结构(8) 在数据结构的讨论中把数据结构从逻辑上分为 _ AA. 内部结构与外部结构C.线性结构与非线性结构(9) 对一个算法的评价，不包括如下A. 健壮性和可读性B.C.

3、正确性D.(10) 算法分析的两个方面是 _ AA. 空间复杂性和时间复杂性C. 可读性和文档性D.(11) 线性表是具有 n 个_ C _A. 表元素C. 数据元素(12) 线性表的存储结构是一种 B 的存储结构。A. 随机存取B.顺序存取C. 索引存取D.HASH存取A.n-iB.n-i+1C.n-i-1D.i链表是一种采用A. 顺序 B 存储结构存储的线性表；B.链式C. 星式D.网状(14)(15)(16) 结点(17)(18)(19)(20)(21)(22)(23)(13) 在一个长度为个元素。的顺序表中，向第i个元素(K i next=p-next ； p-next=-s ；B.

4、q-next=s ； s-next=p ；C. p-next=s-next； s-next=p ；D. p-next=s ；s-next=q ；设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为_ AA. p-n ext=p-n ext- nextB. p=p-nextC. p=p-next-nextD. p-next=p下列说法哪个正确？ D _A. 堆栈是在两端操作、先进后出的线性表B. 堆栈是在一端操作、先进先出的线性表C. 队列是在一端操作、先进先出的线性表D. 队列是在两端操作、先进先出的线性表栈和队列的共同点是 C 。A. 都是先进后出B.都是先进先出pl, p2,

5、 p3,pn，若 p1=n，则 pi 为C. 只允许在端点处插入和删除元素 D. 没有共同点A、兀素个数B、兀素类型C 、逻辑结构D、插入、删除元素的位置链栈与顺序栈相比,比较明显的优点是D。A、插入操作更加方便B删除操作更加方便C不会出现下溢的情况D不会出现上溢的情况以下数据结构中哪一个是非线性结构_ D 。A. 队列B. 栈C. 线性表D. 二叉树栈与一般线性表的区别主要在 D若已知一个栈的入栈序列是1, 2, 3,，n,其输出序列为A. iB. B. n=iC. n-i+1D.不确定(24) 当利用大小为 N 的一维数组顺序存储一个栈时，假定用top=N 表示栈空,则向这个栈插入一个元素

6、时,首先应执行语句修改 top 指针。A. top+B. top-C. top=0D. top(25)A. AB. BC. CD. D4 个元素进 S 栈的顺序是 A,B,C,D ，经运算 POP(S) 后，栈顶元素是(26)A. edcbaB. decbaC. dceabD. abcde(27)设输入序列是1、2、3、n,经过栈的作用后输出序列的第一个元素是n,则输出序列中第i个输出元素A. n-iB. n-1-iC. n+1-iD. 不能确定(28) 字符 A 、B、 字符串？C、D 依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成B _个不同的A. 15B. 14C. 16

7、D. 21(29) 设指针变量top 指向当前链式栈的栈顶，则删除栈顶元素的操作序列为A. top=top+1;B. top=top-1;C. top-next=top;D. top=top-next;一个栈的输入序列是a,b,c,d,e,则栈的不可能的输出序列是(30)设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是 C。A. 6B. 4C. 3D. 2(31) 若用一个大小为6 的数组来实现循环队列,且当前rear和front的值分别为0和3。当从队列

8、中删除一个兀素,再加入两个元素后,rear和front的值分别为_ B _。A. 1 和 5B. 2 和 4C. 4 和 2D. 5 和 1(32) 设顺序循环队列Q0 : M-1的头指针和尾指针分别为F和R,头指针F总是指向队头兀素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为C。A. R-FB. F-RC. (R-F+M)%MD. (F-R+M)%M(33) 设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为_A. front-next=s ； front=s ；C. rea

9、r-next=s ； rear=s ；(34) 如下陈述中正确的是 _ A A. 串是一种特殊的线性表C. 串中元素只能是字母(35) 下列关于串的叙述中,正确的是 _A. 串长度是指串中不同字符的个数_ C 。B. s-next=rear ； rear=s ；D. s-next=front；front=s ；B. 串的长度必须大于零D. 空串就是空白串D 。B. 串是 n 个字母的有限序列C. 如果两个串含有相同的字符,则它们相等D. 只有当两个串的长度相等,并且各个对应位置的字符都相符时才相等(36) 字符串的长度是指 _ C 。A. 串中不同字符的个数C. 串中所含字符的个数B. 串中不

10、同字母的个数D. 串中不同数字的个数(37) 两个字符串相等的充要条件是A. 两个字符串的长度相等 C 。B. 两个字符串中对应位置上的字符相等C. 同时具备 (A) 和 (B) 两个条件D. 以上答案都不对(38) 串是一种特殊的线性表，其特殊性体现在 B A. 可以顺序存储B. 数据元素是一个字符C. 可以链接存储D. 数据元素可以是多个字符(39) 设有两个串p和q,求q在p中首次出现的位置的运算称作 B。A. 连接B. 模式匹配C. 求子串D. 求串长(40) 设串sl=ABCDEFG,s2=PQRST,函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i

11、的字符开始的j个字符组成的子串，len(s)返回串s的长度，贝U con(subs(s1,2,1en(s2)，subs(sl,len(s2)，2)的结果串是 _DA. BCDEFB. BCDEFGC. BCPQRSTD. BCDEFEF(41) 函数 substr(“DATASTRUCTURE ”, 5, 9)的返回值为 _ A 。A. “ STRUCTUR”EB. “ DATA”C. “ASTRUCTU”RD. “DATASTRUCTU”RE(42) 设串 S=”l AM A TEACHER! ”,其长度是 D 。A. 16B. 11C. 14D. 15(43) 假定在一棵二叉树中,双分支结

12、点数为 15 个,单分支结点数为 32 个,贝叶子结点数为 B 。A. 15 B. 16 C. 17 D. 47(44) 假定一棵二叉树的结点数为 18个,贝它的最小高度 B 。A. 4 B. 5 C. 6 D. 18(45) 在一棵二叉树中第五层上的结点数最多为 C 。A. 8 B. 15 C. 16 D. 32(46) 在一棵具有五层的满二叉树中,结点总数为 A 。A. 31 B. 32 C. 33 D. 16(47) 已知 8 个数据元素为 (34、76、45、18、26、54、92、65),按照依次插入结点的方法生成一棵二叉排序树后,最后两层上的结点总数为 B 。A. 1B. 2 C.

13、 D. 4(48) 由分别带权为 9、2、5、7 的四个叶子结点构造一棵哈夫曼树,该树的带权路径长度为 C 。A. 23 B. 37 C. 44 D. 46(49) 在树中除根结点外，其余结点分成 m (m 0)个A的集合T1,T2,T3.Tm,每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点(K i m)。A. 互不相交B.可以相交C. 叶结点可以相交D.树枝结点可以相交(50) 如果结点 A 有三个兄弟,而且 B 是 A 的双亲,贝 B 的出度是 B 。A. 3 B. 4 C. 5 D. 1(51) 在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的B 倍。A. 1

14、/2 B. 1 C. 2 D. 4(52) 具有 n 个顶点的无向完全图，边的总数为 D条。A. n-1B. nC. n+1D. n*(n-1)/2(53) 在无向图 G 的邻接矩阵 A 中，若 Ai,j 等于 1，则 Aj,i 等于C 。A. i+jB. i-jC. 1D. 0(54) 图的深度优先或广度优先遍历的空间复杂性均为 A 。 (访问标志位数组空间 )A. O(n) B. O(e) C. O(n-e) D. O(n+e)(55) 请指出在顺序表 2 、 5、 7、10、 14、15、 18、23、 35、 41、 52中，用折半法查找关键码 12需做 C次关键码比较。A.2 B.3

15、 C.4 D.5(56) 对线性表进行折半查找时，必须要求线性表 C 。A. 以顺序方式存储 B. 以链接方式存储C. 以顺序方式存储，且结点按关键字有序排列D. 以链接方式存储，且结点按关键字有序排列(57) 设二叉排序树中有 n 个结点，则在二叉排序树的平均查找长度为_ B 。2A. O(1)B. O(log 2n)C. O(n) D. O(n 2)(58) 依次插入序列 (50，72，43，85，75，20，35，45，65，30)后建立的二叉搜索树中， 查找元素 35 要进行 _A 元素间的比较。A.4 次B.5 次C.7(59)设散列表中有m 个存储单元，散列函数H(key)=A.小

16、于等于B.小于等于m的最大奇数C.小于等于m的最大偶数D.小于等于(60)_ D 是 HASH 查找的冲突处理方法。A.求余法 B. 平方取中法C. 二分法 D.(61)当a的值较小时，散列存储通常比其他存储方式具有A.较慢B. 较快C. 相同m的最大素数m的最大合数开放地址法对线性表进行折半查找最方便的存储结构是(62)次D. 不确定key % p ，则 p 最好选择 _ BD.10 次的查找速度。A.顺序表有序的顺序表C.链表.有序的链表(63) 如果要求一个线性表既能较快的查找，又能适应动态变化的要求，可以采用 D 查找方法。A分块 B .顺序 C .折半 D .散列(64) 散列函数有

17、一个共同性质，即函数值应按 _ C 取其值域的每一个值。A.最大概率 B .最小概率C .同等概率D .平均概率(65) 下述排序算法中，稳定的是 _ B 。A.直接选择排序B.直接插入排序C.快速排序 D.堆排序(66) 下列排序算法中， A 需要的辅助存储空间最大。A. 快速排序 B. 插入排序C. 希尔排序D. 基数排序(67) 下列各种排序算法中平均时间复杂度为0( n2)是_ D。A. 快速排序B. 堆排序C. 归并排序 D. 冒泡排序(68)在基于关键码比较的排序算法中,.算法在最坏情况下，关键码比较次数不高于O(nlog2n)。(69)(70)(71)(72)(73)A.起泡排序

18、B.直接插入排序C.二路归并排序D.快速排序一组记录为46， 79,A. 46,79,56,38,40,84C. 38,40,46,56,84,7956 , 38, 84, 40，则采用冒泡排序法按升序排列时第一趟排序结果是B. 46,56,38,79,40,84D. 38,46,79,56,40,84每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做A.插入 B.堆 C. 快速D. 归并排序。每次从无序表中挑选出一个最小或最大元素,把它交换到有序表的一端，此种排序方法叫做排序。A.插入 B.C. 快速D. 归并设一组初始记录关键字序列A. 2 ， 3， 5,C. 3，

19、 2， 5,F列排序方法中,8，66，8(5，2，6,B. 3，D. 2，8)，以第一个记录关键字 5为基准进行一趟快速排序的结果为5，8，66，5，8哪一种方法的比较次数与纪录的初始排列状态无关A.直接插入排序B.起泡排序c快速排序D.直接选择排序(74)是采用C.以第一元素为分界元素的快速排序D .基数排序设有关键码初始序列Q , H , C, Y , P, A,M,S,R,D,F,X，新序列F , H , C, D, P, A , M , Q, R, S, Y,X 方法对初始序列进行第一趟扫描的结果。二路归并排序A.直接插入排序(75)A.直接插入排序B.直接选择排序在待排序文件已基本有

20、序的前提下，下述排序方法中效率最咼的是归并排序C. 快速排序(76)若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选排序方法是A.快速排序B . 堆排序C.归并排序D直接插入排序(77)(78)A.n B2n-1 C2n Dn-1F列排序算法中,算法可能会出现下面情况：初始数据有序时，花费的间反而最多。A. 堆排序B.冒泡排序C.快速排序D . SHELL 排序将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是二、填空题。(每空1分，共10分)(1) 数据结构是一门研究非数值计算的程序设计问题中计算机的 数据以及它们之间的关系和运算等的学科。(2) 数据

21、结构包括数据的 逻辑结构 结构和 物理结构 结构。(3)数据结构从逻辑上划分为三种基本类型:线性数据结构树型结构图结构(4)数据的物理结构被分为 存储顺序存储链式存储索引存储.散列表(Hash)四种。(5) 一种抽象数据类型包括变量的取值范围和操作的类别两个部分。(6)数据的逻辑结构是指数据元素间的逻辑关系，数据的存储结构是指数据元素存储方式或者数据元素的物理关系(7)数据结构是指数据及其相互之间的关系。当结点之间存在 M对N (M : N )的联系时，称这种结构为网状结构。当结点之间存在1对N( 1 :N)的联系时，称这种结构为树结构(8)对算法从时间和空间两方面进行度量，分别称为空间复杂度

22、和时间复杂度分析。(9)算法的效率可分为空间效率和时间效率。(10) for(i=1 , t=1 , s=0; i1)的各棵树中，高度最小的树的高度是多少 ？它有多少个叶结点？多少个分支结点？高度最大的 树的高度是多少？它有多少个叶结点？多少个分支结点？答：结点个数为n时，高度最小的树的高度为1,有两层，它有n-1个叶结点，1个分支结点；高度最大的树的高度为n-I ,有n层，它有1个叶结点，n-1个分支结点。24. 什么是内部排序？什么是排序方法的稳定性 ？答：假定给定含有 n个记录的文件(r1 , r2，rn)，其相应的关键字为(k1 , k2，kn)，则排序就是确定文件 的一个序列r1 ,

23、 r2，rn，使得k1 k2kn，从而使得文件中 n个记录按其对应关键字有序排列。如果整 个排序过程在内存中进行，则排序叫内部排序。假设在待排序的文件中存在两个或两个以上的记录具有相同的关键字，若采用某种排序方法后，使得这些具有相同 关键字的记录在排序前后相对次序依然保持不变，则认为该排序方法是稳定的，否则就认为排序方法是不稳定的。五、分析题。 （每小题 4 分，共 8分）1. 分析下面语句段执行的时间复杂度。(1) for(i= 1 ； i = n；i+)for(j= 1 ； j = n； j+)s+(2) for(i= 1 ；i = n；i+)for(j= i ； j = n； j+)s+；(3) for(i= 1 ；i = n；