数据结构题集答案..pdf
《数据结构题集答案..pdf》由会员分享,可在线阅读,更多相关《数据结构题集答案..pdf(25页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、数据结构题集第一章第一章 绪论绪论一、单选题1.在数据结构中,从逻辑上可以把数据结构分成【 C 】 。A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构2.数据结构在计算机内存中的表示是指【 A 】 。A.数据的存储结构B.数据结构C.数据结构的逻辑结构D.数据元素之间的关系3. 【 A 】是数据的最小单位, 【 B 】是数据的基本单位。A.数据项B.数据元素C.信息项D.表元素4. 计算机所处理数据一般具有某种内在联系,这是指【 B 】 。A.数据与数据之间存在某种关系B.数据元素与数据元素之间存在某种关系C.元素内部存在某种结构D.数据项与数据项之
2、间存在某种关系5.算法分析的目的是【 C 】 。A.找出数据结构的合理性B.研究输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性6.在存储数据时,不仅要考虑存储各数据元素的值,而且还要存储【 C 】 。A.数据处理的方法B.数据元素的类型C.数据元素之间的关系D.数据的存储方法7.算法分析的主要任务是分析【 D】 。A.算法是否具有较好的可读性B.算法中是否存储语法错误和逻辑错误C.算法的功能是否符合设计要求D.算法的执行时间与问题规模之间的关系。8.数据的运算【 A 】 。A.效率与采用何种存储结构有关B.是根据存储结构来定义的C.有算术运算和关系运算两大类D.必须用程序设计语
3、言来描述9.算法的计算量的大小称为算法的【 B 】 。A.效率B.时间复杂度C.现实性D.难度10.连续存储分配时,存储单元的地址【A】 。A.一定连续B.一定不连续C.不一定连续D.部分连续,部分不连续二、判断题1.数据元素是数据结构的最小单位【. 】 。2.数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的存储结构【.】 。3.数据的逻辑结构指数据元素的各数据项之间的逻辑关系【.】 。4.算法的优劣与算法的描述语言无关,但与使用的计算机有关【. 】 。5.数据结构的抽象操作的定义与具体实现有关【. 】 。三、填空题1.数据的逻辑结构指数据元素之间的逻辑关系。2.一个数据结构在计算机
4、中的表示称为存储结构。3.数据的物理结构主要包括 顺序存储结构的表示和链式存储结构的表示。4.数据逻辑结构包括集合、线性结构、树和图四种,树结构和图结构统称为非线性结构。5.顺序存储方法把逻辑上逻辑上相邻的元素存储在物理位置相邻的存储单元里;链式存储方法中结点间的逻辑关系是由指针域表示的。6、 数据结构研究的是逻辑结构和 物理结构以及它们之间的相互关系, 并对于这种结构定义相应的运算,设计出相应的 算法。7.算法的执行时间是问题规模 n的函数。8.以下是 4 个算法所有语句频度之和的表达式,其中的复杂度相同的是A 和 B。A.TA(n)=2n3+3n2+1000B.TB(n)=n3-n2log
5、2n-1000C.TC(n)=n2log2n+n2D.TD(n)=n2+1000四、解答题1.简述数据的逻辑结构和存储结构的关系。答:在数据结构中,逻辑结构和存储结构是密切相关的,存储结构不仅将数据元素存储到计算机中,而且还要表示各数据元素之间的逻辑关系。 逻辑结构与计算机无关, 存储结构是数据元素之间的关系在计算机中的表示。 通常情况下, 一种逻辑结构可以有多种存储结构,例如,线性结构可以采取顺序存储结构或链式存粗结构表示。2.数据结构和数据类型有什么区别?答: 数据结构是相互间存在一种或多种特定关系的数据元素的集合, 一般包括三个方面的内容:数据的逻辑结构、存储结构和多数据的运算。 数据类
6、型是一个值得集合和定义在这个值集上的一组操作的总称。 数据结构重点考虑元素之间的关系, 数据类型重点考虑数据的个体特征。3.当为解决某一问题已经选定其数据的逻辑结构后,选择数据的存储结构时,应从哪些方面考虑?答:通常从两个方面考虑:第一是算法实现的存储空间复杂度;第二是算法执行的时间复杂度。若存储空间难以确定,宜选择链式存储结构,否则选择顺序存储结构。若插入、删除操作频繁,则选链式存储结构,否则选择顺序存储结构。第二章第二章 线性表线性表一、单选题1.链表不具备的特点是【 A 】 。A.可随机访问任一结点B.插入删除不需要移动元素C.不必事先估算存储空间D.所需空间与其长度成正比2.设线性表有
7、 n 个元素,以下操作中, 【 A 】在顺序表上实现比在链表上实现效率更高。A.输出第 i(1in)个元素的值B.顺序输出这 n 个元素C.交换第 1 个与第 2 个元素的值D.输出与给定值 x 相等的元素在线性表中的序号3.如果最常用的操作是取第i 个结点及其前驱,则采用【 D 】存储方法最节省时间。A.单链表B.双链表C.线性链表D.顺序表4.线性表是具有 n 个【 C 】的有限序列(n0) 。A.表元素B.字符C.数据元素D.数据项5.下面关于线性表的叙述中,错误的是【 B 】 。A.线性表采用顺序存储,则必须占用一片连续的存储单元B.线性表采用顺序存储,则便于插入和删除操作C.线性表采
8、用链式存储,则不必占用一片连续的存储单元D.线性表采用链式存储,则便于插入和删除操作6. 线性表的顺序存储结构是一种【 A 】 。A.随机存取的存储结构B.顺序存取的存储结构C.索引存取的存储结构D.Hash 存取的存储结构7.单链表中增加一个头结点的目的是为了【 C 】 。A.使单链表至少有一个结点B.标识表首结点的位置C.方便运算的实现D.说明单链表是线性表的链式存储8.不带头结点的单链表(头指针为h)为空的条件是【 A 】 。A.h=NULLB.h-next=NULLC.h-next=hD.h!=NULL9. 带头结点的单链表(头指针为h)为空的条件是【 B 】 。A.h=NULLB.h
9、-next=NULLC.h-next=hD.h!=NULL10.带头结点的循环双向链表(头指针为L)为空的条件是【 D 】 。A.L=NULLB.L-next-prior=NULLC.L-prior=NULLD.L-next=L11.非空的循环单链表(头指针为head)的尾结点(由 p 指向)满足【 C 】 。A.p-next=NULLB.p=NULLC.p-next=headD.p=head12.设一个链表最常用的操作是在末尾插入结点和删除尾结点,则选用【 A 】最节省时间。A.带头结点的双循环链表B.单循环链表C.带尾指针的单循环链表D.单链表13.若某线性表最常用的操作存取任意指定序号的
10、元素和在表尾进行插入和删除,则选用【 A 】的存储方式最节省时间。A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表14.在 n 个结点的线性表的顺序实现中,算法的时间复杂度为O(1)的操作是【 A】 。A.访问第 i 个结点和求第 i 个结点的直接前驱B.在第 i 个结点后插入一个新结点C.删除第 i 个结点D.以上都不对15.若长度为 n 的线性表采用顺序存储结构, 在第 i 个位置插入一个新元素的算法的时间复杂度为【 C 】 。A.O(0)B.O(1)C.O(n)D.O(n2)16.对于顺序存储的线性表,访问结点和增加、删除结点的时间复杂度为【 C 】 。A.O(n)O(n)B.
11、O(n)O(1)C.O(1)O(n)D.O(1)O(1)17. 线性表以链式方式存储,访问第i 个结点的时间复杂度为【 C 】 。A.O(i)B.O(1)C.O(n)D.O(i-1)18.循环链表 H 尾结点 p 的特点是【 A 】 。A.p-next=HB.p-next=H-nextC.p=HD.p=H-next二、判断题【 】1.取线性表的第 i 个元素的时间同 i 的大小有关。【 】2.线性表中每个元素都有一个直接前驱和一个直接后继。【 】3.顺序存储方式只能用于存储线性结构。【 】4.线性表采用链式存储时,结点和结点内部的存储空间可以不连续。【 】5.在一个设有头指针和尾指针的单链表中
12、,执行删除单链表最后一个结点的操作与链表的长度无关。三、填空题1.向一个长度为 n 的顺序表中的第 i 个元素之前插入一个元素时,需要向后移动 n-i+1个元素。2. 在一个长度为 n 的顺序表中删除第 i 个元素时,需要向前移动n-i个元素。3.在单链表中设置头结点的作用是简化插入、删除算法。4.在单链中要删除某一指定结点,必须找到该结点的 直接前驱结点。5. 访问单链表中的结点,必须沿着指针域依次进行。6.在双链表中每个结点有两个指针域,一个指向 直接前驱结点,一个指向 直接后继结点。7.在双向循环链表中,删除最后一个结点的算法时间复杂度为O(1)。8.访问一个线性表中具有给定值的时间复杂
13、度的数量级是O(n)。9.由 n 个数据元素生成一个顺序表,若每次都调用插入算法把一个元素插入到表头,则整个算法的时间复杂度为O(n),若每次都调用插入算法把一个元素插入到表尾,则整个算法的时间复杂度为O(n2)。10. 在双向链表中,可以用表尾指针代替表头指针。11.根据 n 个数据元素建立对应的顺序表和单链表存储结构, 其算法的时间复杂度最好的情况是O(n),最坏的情况是O(n2)。12.求线性表的顺序存储和链式存储的长度的算法时间复杂度分别是O(1)和O(n)。13.在一个带头结点的单链表中,在表头插入或删除与在其他位置插入或删除,其操作过程是否相同?相同。14.在一个不带头结点的单链表
14、中,在表头插入或删除与在其他位置插入或删除,其操作过程是否相同?不相同。四、简答题1.阐述顺序表和链表存储方式的特点。答: 顺序表存储方式为数据分配连续的存储单元, 数据元素按逻辑顺序依次存储到相应存储单元中, 使得逻辑相邻的数据元素物理也相邻, 因此可以实现随机访问线性表的数据元素,即数据访问的时间复杂度为O(1)。链表存储方式分配的存储单元可以不连续, 通过每个结点的指针域来表示数据元素之间的逻辑关系,只能顺序访问线性表中的数据元素。2. 若频繁地对一个线性表进行插入和删除操作,则该线性表宜采用何种存储结构,为什么?答:若频繁地对一个线性表进行插入和删除操作,则该线性表宜采用链式存储结构。
15、因为链式存储结构在插入和删除数据元素时不需要移动数据元素, 只需要修改结点的指针域就可以改变数据元素之间的逻辑关系。3.在单链表、双向循环链表和单循环链表中,若仅知道指针 p 指向某结点,不知道头指针,能否将结点 p 从相应的链表中删除?若可以,时间复杂度各为多少。答:要实现删除 p 结点的操作,必须找到其前驱结点,修改其指针域的值使其指向 p的后继结点,以实现删除结点p。单链表不行,因为不知道头指针就无法找到结点p 的前驱结点。 双向循环链表和单循环链表可以可以实现删除p 结点。 单循环链表删除 p 结点的时间复杂度为 O(n),双循环链表删除P 结点的时间复杂度为O(1)。4.对链表设置头
16、结点的作用是什么?答:对带头结点的链表, 在表的任何结点之前插入结点或删除任何位置的结点, 所要做的都是修改前一个结点的指针域, 因为在带头结点的链表中任何元素结点都有前驱结点。 如果没有头结点, 在首元结点前插入结点或删除首元结点都要修改头指针, 其算法要比带头结点的算法复杂些。其次,带头结点的链表结构,初始化后的头指针就固定了,除撤销算法外, 所有算法都不会修改头指针,可以减少出错的可能性。五、算法设计题1.已知一个线性表用含头结点的单链表做存储结构,写一个算法求单链表的长度。解:算法基本思想: 从头结点的下一个结点开发,遍历单链表的每个结点,每遇到一个结点,结点计算器加 1。int li
17、stlenght(linklist L) int length=0;P=L-next;while(p) length+;p=p-next;return(length);2. 已知一个顺序表 L,其中的元素按值递增有序排列,设计一个算法插入一个值为 x的元素后保持该顺序表仍然递增有序,且空间复杂度为0(1) 。void insertsq(sqlist L,elemtype x) n=L.length-1;while(n=0<(x,L.elemn) L.elemn+1=L.elemn;n-;L.elemn+1=x;L.lenght+;return;3.写一个算法,从顺序表中删除值为x 的所有元
18、素。void delallsq(Sqlist &L) int i=0,j=0;while(jnext=Q.rear。10.如果栈的最大长度难以估计,最好使用链栈。四、简答题1.为什么说栈是一种后进先出表?答: 因为栈是限定在表的一端进行插入和删除操作, 所以后入栈的数据元素总是先出栈,所以说栈是一种后进先出表。2.对于一个栈,其输入序列是A,B,C,试给出全部可能的输出序列。答:可能的出栈序列是:ABC、ACB、BAC、BCA、CBA。3.何谓队列上溢?何为假溢出现象?有哪些解决假溢出问题的方法, 并分别阐述其工作原理。答:队列上溢指在队列的顺序存储分配中, 所有单元中已有元素, 再进行插入操
19、作时称为队列上溢。假溢出指在队列的顺序存储分配中, 分配给队列的存储空间有存储单元未被占用, 但按照操作规则而使进队的数据元素无法进队的现象。解决假溢出问题的方法是在队列的顺序存储分配中, 分配给队列的存储空间可以循环使用,其进本原理是用表示队头和队尾指针与分配给队列的存储空间长度进行取模运算。即:入队操作:Q.rear=(Q.rear+1)%MSize出队操作:Q.front=(Q.front+1)%MSize4.队列可以用单循环链表来实现, 故可以只设一个头指针或只设一个尾指针, 请分析用哪种方案最合适。答:使用循环链表来表示队列,设置尾指针比较合适,因为入队操作可以直接在尾结点后进行插入
20、操作, 出队操作时可以根据尾指针很容易找到链表的头结点, 入队出队操作的算法时间复杂度均为 O(1)。若只设头指针,则出队操作的算法时间复杂度为 O(1),入队操作的算法时间复杂度为O(n)。5.简述线性表、栈和队列的异同?答:栈和队列都是操作位置受限的线性表,即对插入和删除操作的位置加以限制。栈是仅允许在表的一端进行插入和删除操作的线性表, 因而是后进先出表。 队列是允许在表的一端进行插入,在表的另一端进行删除的线性表, 因而是先进先出表。线性表可以在任何位置进行插入和删除操作。五、算法设计题1.设计一个算法,利用栈和队列的基本运算将指定栈中的元素顺序逆转。解:算法基本思想:先将栈中元素出栈
21、运算移至队列中,再将队列中元素出队列移至栈中。void reverse(Stack &st) Queue sq;ElemType x;InitQueue(sq)while(!StackEmpty(st) pop(st,x)EnQueue(sq,x);while(!QueueEmpty(sq) DeQueue(sq,x);Push(st,x);DestroyQueue(sq);2.设计一个算法,利用栈的基本运算返回指定栈中栈底元素。解:先将栈中元素依次移至另一个临时栈中,最后一个元素即为栈底元素,设为x.。再将临时栈中元素移至原栈中,即恢复栈内容。ElemType bottom(Stack &s
22、t) ElemType x,y;Stack tmpst;InitStack(tmpst)while(!StackEmpty(st) pop(st,x)push(tmpst,x);while(!QueueStack(temst) pop(tmpst,y);/此时必须用另一个变量y,才能保留栈底元素在 x 中Push(st,y);DestroyStack(tmpst);return(x);3.设计一个算法,利用栈来实现带头结点的单链表h 的逆序。解:算法基本思想:将单链表结点依次放入链栈中,链栈本身就是一个单链表,即实现了原单链表的逆序。假设链栈不带头结点, 再加上原来的头结点,就完成了原单链表的
23、逆序。Void revert(SNode *h) SNode *st=NULL,*p=h-next,q;While(p) q=p-next;p-next=st;st=p;p=q;h-next=st;第四章串一、单选题1.串是任意有限个【 D 】 。A.符号构成的集合B.符号构成的序列C.字符构成的集合D.字符构成的序列2.串是一种特殊的线性表,其特殊性体现在【 B 】 。A.可以顺序存储B.数据元素是一个字符C.数据元素可以使多个字符D.可以链接存储3.两个串相等必有串长度相等且【 B 】 。A.串的各位置字符任意B.串中各位置字符均对应相等C.两个串含有相同的字符D.两个串所含字符任意4.设
24、有两个串 p 和 q,求 q 在 p 中首次出现的位置的运算称着【 B 】 。A.连接B.模式匹配C.求子串D.求串长二、填空1.空串是长度为 0 的串。2.一个串中任意连续字符组成的子序列称为该串的子串。3.设 s=“abcd” ,则执行语句 s2=Substr(s,2,2)后,s2=“bc”。4.空白串是由一个或多个空格字符组成的串, 其长度等于其所包含的空格字符的个数。第五章 数组一、单选题1.一维数组与线性表的区别是【 A 】 。A.前者长度固定,后者长度可变B.后进长度固定,前者长度可变C.两者长度均固定D.两者长度均可变2.多维数组的数组元素之间的关系, 【 A 】 。A.是线性的
25、B.是树型的C.既是线性的,又是树型的D.既不是线性的,也不是树型的3.设有数组 A810,每个元素占 3 个存储单元,存放该数组的存储单元数为【 C 】 。A.80B.100C.240D.2704.设有数组 A810,每个元素占 3 个存储单元,首地址为 SA,则元素75的起始地址是【 D 】 。A.SA+141B.SA+144C.SA+222D.SA+2255.设有一个 n*n 的对称矩阵,采用压缩存储,则存入内存的元素个数为【 C 】 。A.n*nB.n*n/2C.n*(n+1)/2D.(n+1)2/26.设 A 是一个 n*n 的对称矩阵,压缩存储到一个一维数组B0.n(n+1)/2-
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 答案
限制150内