数据结构题集答案解析.doc

《数据结构题集答案解析.doc》由会员分享，可在线阅读，更多相关《数据结构题集答案解析.doc（26页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

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.有算术运

3、算和关系运算两大类 D.必须用程序设计语言来描述9.算法的计算量的大小称为算法的【 B 】。 A.效率 B.时间复杂度 C.现实性 D.难度10.连续存储分配时，存储单元的地址【A 】。 A.一定连续 B.一定不连续 C.不一定连续 D.部分连续，部分不连续二、判断题1.数据元素是数据结构的最小单位【. 】。 2.数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的存储结构【.】。 3.数据的逻辑结构指数据元素的各数据项之间的逻辑关系【.】。 4.算法的优劣与算法的描述语言无关，但与使用的计算机有关【. 】。 5.数据结构的抽象操作的定义与具体实现有关【. 】。三、填空题1.数据的逻辑结

4、构指 数据元素之间的逻辑关系 。2.一个数据结构在计算机中的 表示 称为存储结构。3.数据的物理结构主要包括 顺序存储结构 的表示和 链式存储结构 的表示。 4.数据逻辑结构包括 集合 、 线性结构 、 树 和 图 四种，树结构和图结构统称为 非线性结构 。 5.顺序存储方法把逻辑上 逻辑上相邻的元素 存储在物理位置 相邻的存储单元里；链式存储方法中结点间的逻辑关系是由 指针域 表示的。 6、数据结构研究的是 逻辑结构 和 物理结构 以及它们之间的相互关系，并对于这种结构定义相应的 运算 ，设计出相应的 算法 。 7.算法的执行时间是 问题规模n 的函数。 8.以下是4个算法所有语句频度之和的

5、表达式，其中的复杂度相同的是 A和B 。 A.TA(n)=2n3+3n2+1000 B.TB(n)=n3-n2log2n-1000 C.TC(n)=n2log2n+n2 D.TD(n)=n2+1000四、解答题 1.简述数据的逻辑结构和存储结构的关系。 答：在数据结构中，逻辑结构和存储结构是密切相关的，存储结构不仅将数据元素存储到计算机中，而且还要表示各数据元素之间的逻辑关系。逻辑结构与计算机无关，存储结构是数据元素之间的关系在计算机中的表示。通常情况下，一种逻辑结构可以有多种存储结构，例如，线性结构可以采取顺序存储结构或链式存粗结构表示。 2.数据结构和数据类型有什么区别？ 答：数据结构是相

6、互间存在一种或多种特定关系的数据元素的集合，一般包括三个方面的内容：数据的逻辑结构、存储结构和多数据的运算。数据类型是一个值得集合和定义在这个值集上的一组操作的总称。数据结构重点考虑元素之间的关系，数据类型重点考虑数据的个体特征。 3.当为解决某一问题已经选定其数据的逻辑结构后，选择数据的存储结构时，应从哪些方面考虑？ 答：通常从两个方面考虑：第一是算法实现的存储空间复杂度；第二是算法执行的时间复杂度。若存储空间难以确定，宜选择链式存储结构，否则选择顺序存储结构。若插入、删除操作频繁，则选链式存储结构，否则选择顺序存储结构。第二章 线性表一、单选题1.链表不具备的特点是【 A 】。 A.可随机

7、访问任一结点 B.插入删除不需要移动元素 C.不必事先估算存储空间 D.所需空间与其长度成正比2.设线性表有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.线性

8、表采用顺序存储，则必须占用一片连续的存储单元 B.线性表采用顺序存储，则便于插入和删除操作 C.线性表采用链式存储，则不必占用一片连续的存储单元 D.线性表采用链式存储，则便于插入和删除操作 6. 线性表的顺序存储结构是一种【 A 】。 A.随机存取的存储结构 B.顺序存取的存储结构 C.索引存取的存储结构 D.Hash存取的存储结构7.单链表中增加一个头结点的目的是为了【 C 】。 A.使单链表至少有一个结点 B.标识表首结点的位置 C.方便运算的实现 D.说明单链表是线性表的链式存储8.不带头结点的单链表（头指针为h）为空的条件是【 A 】。 A.h=NULL B.h-next=NULL

9、C.h-next=h D.h!=NULL9. 带头结点的单链表（头指针为h）为空的条件是【 B 】。 A.h=NULL B.h-next=NULL C.h-next=h D.h!=NULL10.带头结点的循环双向链表（头指针为L）为空的条件是【 D 】。 A.L=NULL B.L-next-prior=NULL C.L-prior=NULL D.L-next=L11.非空的循环单链表（头指针为head）的尾结点（由p指向）满足【 C 】。 A.p-next=NULL B.p=NULL C.p-next=head D.p=head12.设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用【

10、 A 】最节省时间。 A.带头结点的双循环链表 B.单循环链表 C.带尾指针的单循环链表 D.单链表13.若某线性表最常用的操作存取任意指定序号的元素和在表尾进行插入和删除，则选用【 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

11、) C.O(n) D.O(n2)16.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为【 C 】。 A.O(n)O(n) B.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=H B.p-next=H-next C.p=H D.p=H-next二、判断题【 】1.取线性表的第i个元素的时间同i的大小有关。 【 】2.线性表中每个元素都有一个直接前驱和一个直接后继。【 】3.顺序存储

12、方式只能用于存储线性结构。【 】4.线性表采用链式存储时，结点和结点内部的存储空间可以不连续。【 】5.在一个设有头指针和尾指针的单链表中，执行删除单链表最后一个结点的操作与链表的长度无关。三、填空题1.向一个长度为n的顺序表中的第i个元素之前插入一个元素时，需要向后移动 n-i+1 个元素。 2. 在一个长度为n的顺序表中删除第i个元素时，需要向前移动 n-i 个元素。 3.在单链表中设置头结点的作用是 简化插入、删除算法 。 4.在单链中要删除某一指定结点，必须找到该结点的 直接前驱 结点。 5. 访问单链表中的结点，必须沿着 指针域 依次进行。 6.在双链表中每个结点有两个指针域，一个指

13、向 直接前驱结点 ，一个指向 直接后继结点 。 7.在 双向循环 链表中，删除最后一个结点的算法时间复杂度为O(1)。 8.访问一个线性表中具有给定值的时间复杂度的数量级是 O(n) 。 9.由n个数据元素生成一个顺序表，若每次都调用插入算法把一个元素插入到表头，则整个算法的时间复杂度为 O(n) ，若每次都调用插入算法把一个元素插入到表尾，则整个算法的时间复杂度为 O(n2) 。 10. 在 双向 链表中，可以用表尾指针代替表头指针。 11.根据n个数据元素建立对应的顺序表和单链表存储结构，其算法的时间复杂度最好的情况是 O(n) ，最坏的情况是 O(n2) 。 12.求线性表的顺序存储和链

14、式存储的长度的算法时间复杂度分别是 O(1) 和 O(n) 。 13.在一个带头结点的单链表中，在表头插入或删除与在其他位置插入或删除，其操作过程是否相同？ 相同 。14.在一个不带头结点的单链表中，在表头插入或删除与在其他位置插入或删除，其操作过程是否相同？ 不相同 。四、简答题1.阐述顺序表和链表存储方式的特点。 答：顺序表存储方式为数据分配连续的存储单元，数据元素按逻辑顺序依次存储到相应存储单元中，使得逻辑相邻的数据元素物理也相邻，因此可以实现随机访问线性表的数据元素，即数据访问的时间复杂度为O(1)。链表存储方式分配的存储单元可以不连续，通过每个结点的指针域来表示数据元素之间的逻辑关系

15、，只能顺序访问线性表中的数据元素。2. 若频繁地对一个线性表进行插入和删除操作，则该线性表宜采用何种存储结构，为什么？答：若频繁地对一个线性表进行插入和删除操作，则该线性表宜采用链式存储结构。因为链式存储结构在插入和删除数据元素时不需要移动数据元素，只需要修改结点的指针域就可以改变数据元素之间的逻辑关系。 3.在单链表、双向循环链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点p从相应的链表中删除？若可以，时间复杂度各为多少。答：要实现删除p结点的操作，必须找到其前驱结点，修改其指针域的值使其指向p的后继结点，以实现删除结点p。单链表不行，因为不知道头指针就无法找到结点p的

16、前驱结点。双向循环链表和单循环链表可以可以实现删除p结点。单循环链表删除p结点的时间复杂度为O(n)，双循环链表删除P结点的时间复杂度为O(1)。4.对链表设置头结点的作用是什么？答：对带头结点的链表，在表的任何结点之前插入结点或删除任何位置的结点，所要做的都是修改前一个结点的指针域，因为在带头结点的链表中任何元素结点都有前驱结点。如果没有头结点，在首元结点前插入结点或删除首元结点都要修改头指针，其算法要比带头结点的算法复杂些。其次，带头结点的链表结构，初始化后的头指针就固定了，除撤销算法外，所有算法都不会修改头指针，可以减少出错的可能性。五、算法设计题1.已知一个线性表用含头结点的单链表做存

17、储结构，写一个算法求单链表的长度。 解：算法基本思想：从头结点的下一个结点开发，遍历单链表的每个结点，每遇到一个结点，结点计算器加1。 int listlenght(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.ele

18、mn) L.elemn+1=L.elemn; n-; L.elemn+1=x;L.lenght+;return; 3.写一个算法，从顺序表中删除值为x的所有元素。 void delallsq(Sqlist &L) int i=0,j=0; while(jnext=Q.rear 。10.如果栈的最大长度难以估计，最好使用 链栈 。四、简答题1.为什么说栈是一种后进先出表？答：因为栈是限定在表的一端进行插入和删除操作，所以后入栈的数据元素总是先出栈，所以说栈是一种后进先出表。2.对于一个栈，其输入序列是A,B,C,试给出全部可能的输出序列。答：可能的出栈序列是：ABC、ACB、BAC、BCA、CB

19、A。3.何谓队列上溢？何为假溢出现象？有哪些解决假溢出问题的方法，并分别阐述其工作原理。答：队列上溢指在队列的顺序存储分配中，所有单元中已有元素，再进行插入操作时称为队列上溢。假溢出指在队列的顺序存储分配中，分配给队列的存储空间有存储单元未被占用，但按照操作规则而使进队的数据元素无法进队的现象。解决假溢出问题的方法是在队列的顺序存储分配中，分配给队列的存储空间可以循环使用，其进本原理是用表示队头和队尾指针与分配给队列的存储空间长度进行取模运算。即：入队操作：Q.rear=(Q.rear+1)%MSize出队操作：Q.front=(Q.front+1)%MSize4.队列可以用单循环链表来实现，

20、故可以只设一个头指针或只设一个尾指针，请分析用哪种方案最合适。答：使用循环链表来表示队列，设置尾指针比较合适，因为入队操作可以直接在尾结点后进行插入操作，出队操作时可以根据尾指针很容易找到链表的头结点，入队出队操作的算法时间复杂度均为O(1)。若只设头指针，则出队操作的算法时间复杂度为O(1)，入队操作的算法时间复杂度为O(n)。5.简述线性表、栈和队列的异同？答：栈和队列都是操作位置受限的线性表，即对插入和删除操作的位置加以限制。栈是仅允许在表的一端进行插入和删除操作的线性表，因而是后进先出表。队列是允许在表的一端进行插入，在表的另一端进行删除的线性表，因而是先进先出表。线性表可以在任何位置

21、进行插入和删除操作。五、算法设计题 1.设计一个算法，利用栈和队列的基本运算将指定栈中的元素顺序逆转。解：算法基本思想：先将栈中元素出栈运算移至队列中，再将队列中元素出队列移至栈中。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.设计一个算法，利用栈的基本运算返回指定栈中栈底元素。 解：先将栈中

22、元素依次移至另一个临时栈中，最后一个元素即为栈底元素，设为x.。再将临时栈中元素移至原栈中，即恢复栈内容。ElemType bottom(Stack &st) 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.设计一个算法，利用栈来实现带头结点的单

23、链表h的逆序。解：算法基本思想：将单链表结点依次放入链栈中，链栈本身就是一个单链表，即实现了原单链表的逆序。假设链栈不带头结点，再加上原来的头结点，就完成了原单链表的逆序。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.数据元素是一个字

24、符C.数据元素可以使多个字符 D.可以链接存储3.两个串相等必有串长度相等且【 B 】。 A.串的各位置字符任意 B.串中各位置字符均对应相等C.两个串含有相同的字符 D.两个串所含字符任意4.设有两个串p和q，求q在p中首次出现的位置的运算称着【 B 】。 A.连接 B.模式匹配C.求子串 D.求串长二、填空 1.空串是 长度为0的串 。 2.一个串中 任意连续字符组成的子序列 称为该串的子串。 3.设s=“abcd”，则执行语句s2=Substr(s,2,2)后，s2= “bc” 。 4.空白串是 由一个或多个空格字符组成的串 ，其长度等于 其所包含的空格字符的个数 。第五章 数组一、单选

25、题1.一维数组与线性表的区别是【 A 】。 A.前者长度固定，后者长度可变 B.后进长度固定，前者长度可变 C.两者长度均固定 D.两者长度均可变2.多维数组的数组元素之间的关系，【 A 】。 A.是线性的 B.是树型的 C.既是线性的，又是树型的 D.既不是线性的，也不是树型的3.设有数组A810，每个元素占3个存储单元，存放该数组的存储单元数为【 C 】。 A.80 B.100 C.240 D.2704.设有数组A810，每个元素占3个存储单元，首地址为SA，则元素75的起始地址是【 D 】。 A.SA+141 B.SA+144 C.SA+222 D.SA+2255.设有一个n*n的对称矩

26、阵，采用压缩存储，则存入内存的元素个数为【 C 】。 A.n*n B.n*n/2 C.n*(n+1)/2 D.(n+1)2/26.设A是一个n*n的对称矩阵，压缩存储到一个一维数组B0.n(n+1)/2-1中，则下三角部分元素ai,j在B中的位置是【 A 】。 A. i(i-1)/2+j-1 B. i(i-1)/2+j C. i(i+1)/2+j-1 D. i(i+1)/2+j7.稀疏矩阵一般的压缩方法有两种，即【 C 】。 A.二维数组和三维数组 B.三元组和散列 C.三元组和十字链表 D.散列和十字链表8.设有一个10*10的对称矩阵A，以行主次序进行压缩存储，每个元素占一个存储单元，a1

27、,1的地址是1，则A8,5的起始地址是【 B 】。 A.13 B.33 C.18 D.40二、解答题 1.设数组A5080，其基地址为2000，每个元素占2个存储单元，以行序位主序顺序存储，回答下列问题： （1）该数据组由多少元素？ （2）该数组占用多少存储单元？ （3）数组元素a3030的存储地址是多少？ 答： （1）该数组有：50*80=4000个元素 （2）该数组占用4000*4=8000个存储单元 （3）loc(30,30)=2000+(30*80+30)*2=2000+4860=6860第六章 树与二叉树一、单选题1.有关二叉树下列说法正确的是【 B 】。 A.二叉树的度为2 B.一

28、棵二叉树的度可以小于2 C.一棵二叉树至少有一个结点的度为2 D.二叉树中任何一个结点的度为22.利用二叉链表存储树，则根结点的右指针是【 C 】。 A.指向最左孩子 B.指向最右孩子 C.空 D.非空3.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数为【 B 】。 A.9 B.11 C.15 D.不确定4.一棵二叉树有1001个结点，其中叶结点的个数为【 D 】。 A.250 B.490 C.254 D.不确定5.一棵完全二叉树有1001个结点，其中叶结点的个数为【 D 】。 A.250 B.500 C.254 D.以上答案均不对6.一棵具有1025个结点的二叉树的

29、高h为【 C 】。 A.11 B.11 C.11至1025之间 D.10至1024之间7.一棵124个叶结点的完全树，最多具有【 B 】个结点。 A.247 B.248 C.249 D.2518.一棵具有10个叶结点的二叉树具有【 B 】度为2的结点。 A.8 B.9 C.10 D.119.已知一棵完全二叉树有625个结点，叶结点的个数为【 C 】。 A.311 B.312 C.313 D.其它10.一棵具有n个结点的完全二叉树的高h为【 AB】。 A.log2n+1 B.log2n+1 C.log2n+1 D.log2n-111.由8个权值构造一棵哈夫曼树，该哈夫曼树有【 A 】个结点。 A

30、.15 B.16 C.17 D.1412.由3个结点可以构造【 D 】种不同的二叉树。 A.2 B.3 C.4 D.513.树最适合用来表示【 C 】。 A.有序数据元素 B.无序数据元素 C.元素间具有分支层次关系的数据 D.元素间无联系的数据14.下图中4棵二叉树中，【 C 】不是完全二叉树。 A. B. C. D. 15.某二叉树的先序遍历序列和后序便利序列正好相反，则该二叉树一定是【 A 】。 A.空或只有一个结点 B.完全二叉树 C.二叉排序树 D.高度等于其结点数 16.在一棵非空二叉树的中序遍历序列中，根结点的右边【 A 】。 A.只有右子树上的所有结点 B.只有右子树上的部分结

31、点 C.只有左子树上的部分结点 D.只有左子树上的所有结点 17.任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序【 A 】。 A.不发生上改变 B.发生改变 C.不能确定 D.以上都不对 18.一棵满二叉树，m个叶结点，n个结点，深度为h，则【 D 】。 A.n=h+m B.h+m=2n C.m=h-1 D.n=2 h-1 19.设n，m是二叉树上的两个结点，在中序遍历时，n在m之前的条件是【 C 】。 A.n在m右方 B.n是m的祖先 C.n在m左方 D.n是m的子孙20.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中包含的结点数最少为【 B 】。 A.2h B

32、.2h-1 C.2h+1 D.h+1二、判断题【 】1.二叉树是一般树的特殊树型。【 】2.树与二叉树是两种不同的树形结构。【 】3.对于有n个结点的二叉树，其高度为log2n。【 】4.完全二叉树中，若一个没有左孩子，则它必定是叶结点。【 】5.一棵具有n个结点的完全二叉树，从上到下、从左到右用自然数对结点进行编号，结点为i的结点的左孩子的编号为2i(2in)。【 】6.一棵树中的叶结点数一定等于与其对应的二叉树的叶结点数。【 】7.哈夫曼树是带权路径长度最短的树，路经上权值较大的结点离根最近。【 】8.哈夫曼树的结点个数不偶数。三、填空题1.深度为k的完全二叉树至少有 2K-1 个结点，至多有 2K-1 个结点。 2.在一棵二叉树中，度为0的结点个数为n0，度为2的结点个数为n2,则有n0= n2+1 。 3.一棵二叉树第i层最多有 2i-1 个结点，一棵有n个结点的满二叉树共有 2K-1 个结点，共有 2K-