数据结构复习题及答案.doc

一、选择题。（每小题2分，共4分)（1) 计算机识别、存储与加工处理得对象被统称为_A_。、数据 B、数据元素 C、数据结构 D、数据类型(2) 数据结构通常就是研究数据得_A _及它们之间得联系。A、存储与逻辑结构 、存储与抽象 、理想与抽象 D、理想与逻辑（3） 不就是数据得逻辑结构就是_ A_。A、散列结构 B、线性结构 C、树结构 D、图结构(4）数据结构被形式地定义为D,R，其中D就是_ B _得有限集，R就是_ C _得有限集。、算法 B、数据元素 、数据操作 D、逻辑结构()组成数据得基本单位就是_ A _.A、数据项 、数据类型C、数据元素 D、数据变量（6） 设数据结构=(D，）,其中D=1，2,，4,R=r，r=，,3，4,nt;pne=-s;、 next=；snxt=p;C、 p-xt=sext；sext=p;D、 pext=s；s-next=q;(7） 设指针变量p指向单链表结点，则删除结点A得后继结点需要得操作为_A_。A、 -extneext B、 p=-nextC、 pp-xtnxt D、 p-ex=p（） 下列说法哪个正确？_D_A、 堆栈就是在两端操作、先进后出得线性表B、堆栈就是在一端操作、先进先出得线性表、队列就是在一端操作、先进先出得线性表、 队列就是在两端操作、先进先出得线性表（1） 栈与队列得共同点就是_ _。A、 都就是先进后出 B、都就是先进先出C、 只允许在端点处插入与删除元素 、没有共同点（20） 栈与一般线性表得区别主要在_D_。、元素个数 、元素类型 C、逻辑结构 D、插入、删除元素得位置（21）链栈与顺序栈相比，比较明显得优点就是_D_。A、插入操作更加方便 B、删除操作更加方便C、不会出现下溢得情况 、不会出现上溢得情况（22) 以下数据结构中哪一个就是非线性结构_D _。A、队列、栈C、线性表D、二叉树（23) 若已知一个栈得入栈序列就是1,2,，n，其输出序列为p1，p2,p3,，pn，若p1=n，则pi为_ _.A、 iB、 B、 n=i C、 i+1D、不确定(2) 当利用大小为得一维数组顺序存储一个栈时,假定用top=N表示栈空，则向这个栈插入一个元素时,首先应执行_B _语句修改o指针。A、top+ B、 tp C、 top=0D、 op（25) 4个元素进栈得顺序就是,B,C，,经运算POP（S）后，栈顶元素就是_ C _。A、A、C、 CD、 D（26） 一个栈得输入序列就是，b,c，d，e,则栈得不可能得输出序列就是_ C _。、 dcba、 decbaC、ceab、 abcde(27）设输入序列就是1、2、n，经过栈得作用后输出序列得第一个元素就是，则输出序列中第i个输出元素就是_ C _。A、niB、 C、n1-iD、不能确定（2） 字符A、依次进入一个栈，按出栈得先后顺序组成不同得字符串，至多可以组成_ _个不同得字符串？A、 B、 1C、 16、 21（） 设指针变量top指向当前链式栈得栈顶，则删除栈顶元素得操作序列为_ D _.A、 top=top+1； B、 op=op-1; C、 topnexto;D、 p=topnx； （3）设栈S与队列得初始状态为空，元素E1、2、E、E4、E5与E6依次通过栈,一个元素出栈后即进入队列Q，若6个元素出列得顺序为E2、E4、E3、E、E5与E1，则栈S得容量至少应该就是_ C_.、 6B、C、 3D、 (1) 若用一个大小为6得数组来实现循环队列，且当前rer与fn得值分别为0与3。当从队列中删除一个元素，再加入两个元素后,re与frot得值分别为_ _。、 1与5、 2与4C、 4与2D、 5与1(3） 设顺序循环队列Q0：-1得头指针与尾指针分别为F与,头指针F总就是指向队头元素得前一位置,尾指针R总就是指向队尾元素得当前位置，则该循环队列中得元素个数为_ C _.A、R-FB、 FRC、（RF+M)、（-M)M(33)设指针变量ont表示链式队列得队头指针，指针变量re表示链式队列得队尾指针,指针变量s指向将要入队列得结点X,则入队列得操作序列为_ _.A、 rntnet=s;ront=s;B、 s-nex=ear；rear=s;C、 ran=s；rars;、 s-next=ont；front=;(34） 如下陈述中正确得就是_ A _。A、 串就是一种特殊得线性表、 串得长度必须大于零、串中元素只能就是字母D、空串就就是空白串（3） 下列关于串得叙述中,正确得就是_ _。A、 串长度就是指串中不同字符得个数B、 串就是n个字母得有限序列C、 如果两个串含有相同得字符,则它们相等D、只有当两个串得长度相等,并且各个对应位置得字符都相符时才相等（36） 字符串得长度就是指_ C _。A、串中不同字符得个数B、 串中不同字母得个数C、 串中所含字符得个数D、 串中不同数字得个数 （37） 两个字符串相等得充要条件就是_ _.A、 两个字符串得长度相等、 两个字符串中对应位置上得字符相等C、 同时具备（A）与(B)两个条件 D、 以上答案都不对(8) 串就是一种特殊得线性表，其特殊性体现在_ _。、 可以顺序存储B、数据元素就是一个字符C、 可以链接存储、数据元素可以就是多个字符（39）设有两个串p与q,求在中首次出现得位置得运算称作_ _。A、连接B、 模式匹配C、 求子串D、 求串长（0) 设串sI=CDEFG”，s=”QST，函数on(x，y）返回与y串得连接串,su（s,i,j）返回串得从序号得字符开始得j个字符组成得子串，le(）返回串s得长度，则con(subs（s1，2,en（s2）,s（sl，len(s2)，2）得结果串就是_ D _。A、 DE、 BCDEFC、BCPQRTD、 CEFF (41) 函数subtr（“DAASTRUCTUE”，5,）得返回值为_A_。A、 “TRRE” 、 “DT C、 “ASUCT” D、 “AASTRUCTUE（42) 设串S=”I AM A TACHR！,其长度就是_D _。、16B、 1C、 4D、 5(4） 假定在一棵二叉树中,双分支结点数为15个，单分支结点数为2个,则叶子结点数为_B_。 A、 15 、 16 C、7 D、 4(44） 假定一棵二叉树得结点数为18个,则它得最小高度_B_。A、 B、 5 C、 D、18(4） 在一棵二叉树中第五层上得结点数最多为_C_。A、 、15 C、 16 、 32(46) 在一棵具有五层得满二叉树中，结点总数为_A_。A、 1 B、 2 C、 3 、 16(） 已知个数据元素为（34、6、5、18、26、54、92、65),按照依次插入结点得方法生成一棵二叉排序树后,最后两层上得结点总数为_B_.A、 1 B、2 、 、4（48） 由分别带权为9、2、7得四个叶子结点构造一棵哈夫曼树，该树得带权路径长度为_C_。 A、23 、 C、 4 D、 46（49） 在树中除根结点外,其余结点分成m (m0)个_A _得集合1，T2，T、m，每个集合又都就是树，此时结点T称为Ti得父结点,Ti称为T得子结点（i）.A、互不相交 B、 可以相交 C、 叶结点可以相交 、 树枝结点可以相交(0） 如果结点A有三个兄弟，而且B就是A得双亲，则B得出度就是_B_.A、 B、 4 C、 5 、 1（51) 在一个有向图中,所有顶点得入度之与等于所有顶点得出度之与得_B_倍。A、 1/2 B、 1 C、 2 D、 4(5) 具有n个顶点得无向完全图,边得总数为_D_条。A、 n-1 B、n 、n+ D、 n（n1）/（3） 在无向图G得邻接矩阵A中，若A，j等于1，则j，i等于_C _。A、i+j B、 i-j C、 D、 0（54） 图得深度优先或广度优先遍历得空间复杂性均为_A_ 。（访问标志位数组空间)A、 O（n） B、O（e） C、 O(ne) D、 O（n+)（55) 请指出在顺序表2、5、7、1、14、1、18、23、35、41、5中，用折半法查找关键码12需做_C _次关键码比较。A、2 、3 C、4 D、 （56） 对线性表进行折半查找时，必须要求线性表_ C _。A、 以顺序方式存储 B、 以链接方式存储、 以顺序方式存储，且结点按关键字有序排列D、 以链接方式存储，且结点按关键字有序排列(57） 设二叉排序树中有n个结点，则在二叉排序树得平均查找长度为_ _。A、 O(1） B、 O（og) C、 （n） D、 O(n)（58) 依次插入序列(0，,4,85，75，0，5，45，65，30）后建立得二叉搜索树中，查找元素3要进行_ A_元素间得比较.A、4次B、次、次D、0次（5） 设散列表中有m个存储单元,散列函数H（key）=ky % p,则p最好选择_ B_.A、 小于等于得最大奇数B、 小于等于m得最大素数C、小于等于m得最大偶数D、小于等于得最大合数（0） _ D _就是HASH查找得冲突处理方法.A、求余法 B、 平方取中法 、 二分法 D、 开放地址法(61) 当得值较小时,散列存储通常比其她存储方式具有_ _得查找速度.A、 较慢、 较快C、相同 、不确定(2) 对线性表进行折半查找最方便得存储结构就是_ B _。A.顺序表 。有序得顺序表C链表 D.有序得链表(6） 如果要求一个线性表既能较快得查找,又能适应动态变化得要求，可以采用_ D _查找方法。分块 B.顺序 C。折半 D.散列(64） 散列函数有一个共同性质，即函数值应按_取其值域得每一个值.A.最大概率 B。最小概率 C同等概率 D.平均概率(5) 下述排序算法中，稳定得就是_ B _。A、直接选择排序 B、 直接插入排序 C、快速排序 D、堆排序 (6)下列排序算法中，_ A_需要得辅助存储空间最大。A、快速排序B、插入排序C、希尔排序D、基数排序（7) 下列各种排序算法中平均时间复杂度为O（n2)就是_ D _。A、 快速排序 B、 堆排序 C、归并排序 D、 冒泡排序(68) 在基于关键码比较得排序算法中,_ C _算法在最坏情况下，关键码比较次数不高于O(nlog2)。A、 起泡排序、 直接插入排序C、 二路归并排序D、 快速排序(69) 一组记录为6，9，56,8，84,40，则采用冒泡排序法按升序排列时第一趟排序结果就是_ _.A、 46，9,56，38,0,84 B、46，56，38，0,4、 8,0,6，56，84,7 D、38,46，79，6，4，84(7）每次从无序表中取出一个元素,把它插入到有序表中得适当位置,此种排序方法叫做_ _ 排序。A、 插入 B、 堆 、快速 D、归并(7)每次从无序表中挑选出一个最小或最大元素，把它交换到有序表得一端,此种排序方法叫做_ B_排序。A、插入 、 堆 、快速 D、归并（7） 设一组初始记录关键字序列(5，,6，3，8）,以第一个记录关键字5为基准进行一趟快速排序得结果为_ _。A、 2,3,5,8，6B、 3,2,5,8，6、 3,，,，8D、2，,6,，(73) 下列排序方法中,哪一种方法得比较次数与纪录得初始排列状态无关_D _.、 直接插入排序 、 起泡排序C、快速排序 、 直接选择排序（7) 设有关键码初始序列，H，C，Y，P，A，M，S，R,D,F，X，新序列F，H,C,D，P,A,M，,，S，Y,X就是采用_ C _ 方法对初始序列进行第一趟扫描得结果.、 直接插入排序 二路归并排序C。以第一元素为分界元素得快速排序 D。基数排序（5） 在待排序文件已基本有序得前提下,下述排序方法中效率最高得就是_ _.A、 直接插入排序 B、直接选择排序C。 快速排序 D。 归并排序（76） 若需在O（nlog2n）得时间内完成对数组得排序，且要求排序就是稳定得,则可选排序方法就是_ C _ 。、 快速排序 B。 堆排序 归并排序 D。 直接插入排序（7） 将两个各有个元素得有序表归并成一个有序表,其最少得比较次数就是_ B _。A。 n B 2n1 C。 n D。 n-1(78） 下列排序算法中，_ C _ 算法可能会出现下面情况：初始数据有序时，花费得间反而最多。A、 堆排序 冒泡排序 C.快速排序 D。 HL排序二、填空题。（每空1分,共0分)（1) 数据结构就是一门研究非数值计算得程序设计问题中计算机得 数据 以及它们之间得 关系 与运算等得学科。(） 数据结构包括数据得逻辑结构结构与物理结构结构.（3) 数据结构从逻辑上划分为三种基本类型：_线性数据结构_、_树型结构_与_图结构_。（) 数据得物理结构被分为_顺序存储_、_链式存储_、_索引存储_与_散列表（Hash)存储_四种。（5） 一种抽象数据类型包括_变量得取值范围_与_操作得类别_两个部分.(6) 数据得逻辑结构就是指 数据元素间得逻辑关系 ，数据得存储结构就是指 数据元素存储方式或者数据元素得物理关系 。（7） 数据结构就是指数据及其相互之间得_关系_。当结点之间存在M对N（M：N）得联系时，称这种结构为_网状结构_。当结点之间存在1对N(1：）得联系时，称这种结构为_树结构_。（8)对算法从时间与空间两方面进行度量，分别称为 空间复杂度与时间复杂度 分析。（9） 算法得效率可分为_空间_效率与_时间_效率。（0)for（=1,=1,s=0;in；i+) tti；s=+t;得时间复杂度为_（)_。(11） 线性表就是n个元素得_有限序列_。（12） 线性表得存储结构有_顺序存储与链式存储_。(13） 设线性表中有n个数据元素,则在顺序存储结构上实现顺序查找得平均时间复杂度为_O（n)_，在链式存储结构上实现顺序查找得平均时间复杂度为_ O(）_。（1） 设顺序线性表中有个数据元素，则第i个位置上插入一个数据元素需要移动表中_ -i_个数据元素;删除第i个位置上得数据元素需要移动表中_ n-i_个元素。（15) 若频繁地对线性表进行插入与删除操作，该线性表应采用_链式_存储结构。()链式存储结构中得结点包含_数据_域与_指针_域.（17） 对于一个长度为n得单链存储得线性表,在表头插入元素得时间复杂度为_(1）_,在表尾插入元素得时间复杂度为_（n)_。（8)栈得插入与删除只能在栈得栈顶进行,后进栈得元素必定先出栈，所以又把栈称为_ O _表;队列得插入与删除运算分别在队列得两端进行,先进队列得元素必定先出队列,所以又把队列称为_IFO _表.（19） s= I aman” 长度为_10_。(20)s1”hell “，2boy,s1，连接后为：_helob_.(21) ”thi sthemin strng，substring,stnex(s，sub）就是:_13_.（22） n a1010，已知a=1000，szeof(int)=2,求3地址:_106_。(3） 设有两个串p与q,求q在p中首次出现得位置得运算称为_模式匹配_。(2) 在树型结构中,树根结点没有_前趋_结点，其余每个结点有且仅有_一_个前驱结点；树叶结点没有_后继_结点,其余每个结点得_后继_结点数不受限制。（25） 在一棵二叉树中,度为0得结点得个数为0 ,度为2得结点得个数为n ,则：0 =_n2 +_.（2) 由分别带权为3,9,6,2，得共五个叶子结点构成一棵哈夫曼树,则带权路径长度为_55_。（27) 在图G得邻接表表示中,每个顶点邻接表中所含得结点数,对于无向图来说等于该 顶点得_度数_,对于有向图来说等于该顶点得_出度数_.（2） 假定一个图具有n个顶点与e条边，则采用邻接矩阵表示得空间复杂性为_O( )_， 采用邻接表表示得空间复杂性为_ O（+e） _。(9) 对于长度为n得线性表，若进行顺序查找，则时间复杂度为_ O(n）_；若采用折半法查找，则时间复杂度为_ O（lo2n)_.(30） 假设在有序线性表A1、2上进行折半查找,则比较一次查找成功得结点数为_1_，则比较二次查找成功得结点数为_，则比较三次查找成功得结点数为_4_，则比较四次查找成功得结点数为_8_，则比较五次查找成功得结点数为_5_，平均查找长度为_lg2(n+)-1_.（3） 在一棵二叉排序树中，每个分支结点得左子树上所有结点得值一定_小于_该结点得值,右子树上所有结点得值一定_大于_该结点得值。 （3) 对一棵二叉排序树进行中序遍历时,得到得结点序列就是一个_增序序列_。（33）对于线性表(0，34，55，23，5,41,0）进行散列存储时，若选用()=K 7作为散列函数,则散列地址为得元素就是_70_,散列地址为6得就是_4，20，55_。(34） 在线性表得散列存储中，装填因子a又称为装填系数，若用表示散列表得长度，n表示待散列存储得元素得个数,则等于_ /m _。（35） 散列表中解决冲突得两种方法就是_开放地址法_与_链地址法_.（36） 在散列存储中,装填因子得值越大，则_产生冲突得可能性就越大_;a得值越小，则_产生冲突得可能性就越小_.(）散列法存储得基本思想就是由_关键码直接_决定数据得存储地址.（8) 构造哈希函数得方法有（写二个)_直接定址法,数字分析法，平方取中法,折叠法，除留余数法,随机数法_。(39） 在分块查找中首先查找 _索引_,然后再查找相应得_块_。(40) 散列表得查找效率主要取决于散列表造表时选择得_哈希函数_ 与_装填因子_。（41） 对两棵具有相同关键字集合而形状不同得二叉排序树,_中序_ 遍历它们得到得序列得顺序就是一样得。（42) 当待排序得记录数较大,排序码较随机且对稳定性不作要求时，宜采用_快速_排序;当待排序得记录数较大，存储空间允许且要求排序就是稳定时，宜采用_归并_排序.(43） 在堆排序得过程中，对任一分支结点进行筛运算得时间复杂度为_ O（log2n）_,整个堆排序过程得时间复杂度为_ (nlon）_。（) 当向一个大根堆插入一个具有最大值得元素时,需要逐层_向上调整，直到被调整到_根结点_位置为止.(5)对一组初始关键字序列(0，0,5，2，1，70,60,45，10）进行冒泡排序,则第一趟需要进行相邻记录得比较得次数为_8_，在整个排序过程中最多需要进行_8_趟排序才可以完成.(4) 在在插入排序、选择排序、快速排序、堆排序、归并排序与基数排序中,平均比较次数最少得排序就是_快速_,需要内存容量最多得就是_归并_。（47) 堆排序就是不稳定,空间复杂度为 _ O（1)_。在最坏情况下，其时间复杂度也为_O(ngn）_。(8） 若待排序得文件中存在多个关键字相同得记录，经过某种排序方法排序后，具有相同关键字得记录间得相对位置保持不变，则这种排序方法就是_稳定_得排序方法.(49) 在对一组记录（50，0，95，0,5，70,6,4，80）进行直接插入排序时，当把第个记录插入到有序表时,为寻找插入位置需比较_次。（0) 二路归并排序得时间复杂度就是_ (nog2n）_.（51) 对于个记录得集合进行归并排序,所需得附加空间消耗就是_ （n)_.（52） 设表中元素得初始状态就是按键值递增得，分别用堆排序、快速排序、冒泡排序与归并排序方法对其仍按递增顺序进行排序,则_冒泡排序_最省时间，_快速排序_最费时间。三、判断题。(每小题1分,共10分）（ )1数据元素就是数据得最小单位。（ ）2。数据项就是数据得基本单位。（ ）3。顺序存储得线性表可以随机存取。()4线性表中得元素可以就是各种各样得，但同一线性表中得数据元素具有相同得特性, 因此,就是属于同一数据对象。（ ）5.在单链表中，任何两个元素得存储位置之间都有固定得联系，因为可以从头结点查找任何一个元素。( ）在单链表中，要取得某个元素,只要知道该元素得指针即可,因此,单链表就是随机存取得存储结构。( )7.链表得每个结点中，都恰好包含一个指针。（ )8。数组就是同类型值得集合. （ ）9。使用三元组表示稀疏矩阵得元素,有时并不能节省存储时间。（ ）10、 线性表可以瞧成就是广义表得特例,如果广义表中得每个元素都就是原子，则广义表便成为线性表。（ )1、 由树转换成二叉树，其根结点得右子树总就是空得。( ）12、 后序遍历树与中序遍历与该树对应得二叉树,其结果不同。( )13、 若有一个结点就是某二叉树子树得中序遍历序列中得最后一个结点,则它必就是该子 树得前序遍历序列中得最后一个结点.（ ）1、若一个树叶就是某子树得中序遍历序列中得最后一个结点，则它必就是该子树得前序遍历序列中得最后一个结点。( ）15、 已知二叉树得前序遍历与后序遍历序列并不能唯一地确定这棵树，因为不知道树得根结点就是哪一个。（ )16、 在哈夫曼编码中，当两个字符出现得频率相同时，其编码也相同,对于这种情况应作特殊处理。（ ）1、 有回路得图不能进行拓扑排序。( )18、 连通分量就是无向图中得极小连通子图。 ( ）19、散列法存储得基本思想就是由关键码得值决定数据得存储地址.( ）20、 散列表得查找效率取决于散列表造表时选取得散列函数与处理冲突得方法.（ ）21、m阶B-树每一个结点得子树个数都小于或等于。( ）2、 中序遍历二叉排序树得结点就可以得到排好序得结点序列。（ )23、 在二叉排序树上插入新得结点时，不必移动其它结点,仅需改动某个结点得指针， 由空变为非空即可。（ )4、当待排序得元素很多时,为了交换元素得位置，移动元素要占用较多得时间，这就是影响时间复杂性得主要因素。( ）25、 对于n个记录得集合进行快速排序，所需要得平均时间就是O(no2 n）。( ）26、对于n个记录得集合进行归并排序，所需要得平均时间就是(nlo2)。( )27、 堆中所有非终端结点得值均小于或等于（大于或等于）左右子树得值。( ）8、 磁盘上得顺序文件中插入新得记录时，必须复制整个文件。（ )29、在索引顺序文件中插入新得记录时，必须复制整个文件.( )30、 索引顺序文件就是一种特殊得顺序文件，因此通常存放在磁带上。四、简答题。(共6小题,每小题约5分,共32分) 1、 简述下列术语：数据、数据项、数据元素、数据逻辑结构、数据存储结构、数据类型与算法。数据：数据就是信息得载体,就是计算机程序加工与处理得对象,包括数值数据与非数值数据。数据项：数据项指不可分割得、具有独立意义得最小数据单位，数据项有时也称为字段或域。数据元素:数据元素就是数据得基本单位，在计算机程序中通常作为一个整体进行考虑与处理,一个数据元素可由若干个数据项组成.数据逻辑结构：数据得逻辑结构就就是指数据元素间得关系。数据存储结构：数据得物理结构表示数据元素得存储方式或者数据元素得物理关系.数据类型：就是指变量得取值范围与所能够进行得操作得总与.算法：就是对特定问题求解步骤得一种描述,就是指令得有限序列。2、 简述栈与线性表得区别.答：一般线性表使用数组来表示得。线性表一般有插入、删除、读取等对于任意元素得操作。而栈只就是一种特殊得线性表.栈只能在线性表得一端插入（称为入栈，push)或者读取栈顶元素或者称为“弹出、出栈”（po）。3、 简述栈与队列这两种数据结构得相同点与不同点。答：相同点：栈与队列都就是特殊得线性表，只在端点处进行插入,删除操作.不同点:栈只在一端（栈顶）