数据结构Java语言描述孙琳 微课版习题答案+上机实训全书110章.docx

《数据结构Java语言描述孙琳 微课版习题答案+上机实训全书110章.docx》由会员分享，可在线阅读，更多相关《数据结构Java语言描述孙琳 微课版习题答案+上机实训全书110章.docx（56页珍藏版）》请在第一文库网上搜索。

1、第一章绪论习题一、选择题1.B2. C3. (I)C(2)B4. C5. C6. D7. D8. A9. C10. A11. C12. C二、判断题1. X2. X3. X4. X5. 6. 7. X8. X9. X10. X三、填空题1 .集合线性结构树形结构图状结构或网状结构2 .有穷性确定性可行性3 .O(n)四、简答题1 .数据是人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的描述。数据元素是数据的基本单位，在程序中通常把数据元素作为一个整体进行考虑和处理。一个数据元素可由若干数据项组成，数据的最小单位即数据项。2 .(1)数据元素之间的逻辑关系，即数据的逻辑

2、结构；(2)数据元素及其关系在计算机存储中的存储方式，即数据的存储结构，也称为数据的物理结构；(3)施加在该数据上的操作，即数据的运算。3 .参考书本图1-24 .数据类型是一个值的集合和定义在这个集合上的一组操作的总称。抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。5 .(1)顺序存储结构(2)链式存储结构(3)索引存储结构(4)哈希(或散列)存储结构顺序存储结构：67 .评价算法有四个方面。一是算法的正确性；二是算法的易读性；三是算法的健壮性；四是算法的时空效率(运行)。8 .算法基本运算次数T(n)是问题规模n的某个函数f(n),记做：T(n)=O(f(n)记号“O”读作大O

3、(值数量级)，它表示随问题规模n的增大，算法执行时间的增长和f(n)的增长率相同，称为算法的时间复杂度。“0”的形式定义为：若f(n)是正整数n的一个函数，则T(n)=O(f(n)表示存在一个正的常数M,使得当n=no时都满足T(n)=Mf(n),也就是只求出T(n)的最高阶，忽略其低阶项和常数，这样既能简化计算，又可以较为客观地反映当n很大时算法的时间性能。9 .O(Mgn)算法最可取，因时时间效率最高。10 .(1)20,(23)n,(43)%(32)n(2) n2z3,n,n3z2,n!,nn(3) 10g2n,n,n10g2n,n12n第二章线性表习题一、选择题1 .线性表是OA.一个

4、有限序列，可以为空B.一个有限序列，不可以为空C.一个无限序列，可以为空D.一个无限序列，不可以为空2 .在一个长度为n的顺序表中删除第i个元素(O:inext=s;s-prior=p;p-next-prior=s;s-next=p-next;B. s-prior=p;s-next=p-next;p-next=s;p-next-prior=s;C. p-next=s;p-next-prior=s;s-prior=p;s-next=p-next;D. s-prior=p;s-next=p-next;p-next-prior=s;p-next=s;6 .设单链表中指针P指向结点m,若要删除m之后的

5、结点(若存在)，则需修改指针的操作为。A.p-next=p-next-next;B.p=p-next;C.p=p-next-next;D.p-next=p;7 .在一个长度为n的顺序表中向第i个元素(0inext=p-next;p-next=sB.q-next=s;s-next=pC.p-ncxt=s-next;s-next=pD.p-ncxt=s;s-next=q9.以下关于线性表的说法不正确的是oA.线性表中的数据元素可以是数字、字符、记录等不同类型。B.线性表中包含的数据元素个数不是任意的。C.线性表中的每个结点都有且只有一个直接前趋和直接后继。D.存在这样的线性表：表中各结点都没有直接

6、前趋和直接后继。10 .线性表的顺序存储结构是一种的存储结构。.随机存取B.顺序存取C.索引存取D.散列存取11 .在顺序表中，只要知道,就可在相同时间内求出任一结点的存储地址。A.基地址B.结点大小C.向量大小D.基地址和结点大小12 .在等概率情况下，顺序表的插入操作要移动_结点。.全部B.一半C.三分之一D.四分之一13 .在运算中，使用顺序表比链表好。A.插入B.删除C.根据序号查找D.根据元素值查找14 .在一个具有n个结点的有序单链表中插入一个新结点并保持该表有序的时间复杂度是.0(1)B.0(n)C,0(n2)D.0(1og2n)15 .设有一个栈，元素的进栈次序为A,B,C,D

7、,E,下列是不可能的出栈序列J.A,B,C,D,EB.B,C,D,E,AC.E,B,C,DD.E,D,C,B,A16 .在一个具有n个单元的顺序栈中，假定以地址低端(即0单元)作为栈底，以top作为栈顶指针，当做出栈处理时，t。P变化为O.top不变B.top=0C.top-D.top+17 .向一个栈顶指针为hs的链栈中插入一个S结点时，应执行。.hs-next=s;B.s-next=hs;hs=s;C.s-next=hs-next;hs-next=s;D.s-next=hs;hs=hs-next;18.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，

8、则判断队满的条件为O.rearn=frontB.(front+1)%n=rearC.rearn-1=frontD.(rear+1)%n=front19 .在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为O.rear%n=frontB.front+1=rearC.rear=frontD.(rear+1)%n=front20 .在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为。.front=front-nextB.rear=rear-nextC.rear=front-nextD.front=rear-ne

9、xt二、填空题1.线性表是一种典型的结构。2.在一个长度为n的顺序表的第i个元素之前插入一个元素，需要后移个元素。3.顺序表中逻辑上相邻的元素的物理位置o4 .要从一个顺序表删除一个元素时，被删除元素之后的所有元素均需个位置，移动过程是从向_依次移动每一个元素。5 .在线性表的顺序存储中，元素之间的逻辑关系是通过决定的；在线性表的链接存储中，元素之间的逻辑关系是通过决定的。6 .在双向链表中，每个结点含有两个指针域，一个指向结点，另一个指向结点。7 .当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用存储结构为宜。8 .

10、顺序表中逻辑上相邻的元素，物理位置相邻，单链表中逻辑上相邻的元素，物理位置相邻。9 .根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为和：而根据指针的联接方式，链表乂可分为_和_10 .在单链表中设置头结点的作用是_三、简答题1 .描述以下三个概念的区别：头指针，头结点，表头结点。2 .线性表的两种存储结构各有哪些优缺点？3 .对于线性表的两种存储结构，如果有n个线性表同时并存，而且在处理过程中各表的长度会动态发生变化，线性表的总数也会自动改变，在此情况下，应选用哪一种存储结构？为什么？4 .对于线性表的两种存储结构，若线性表的总数基本稳定，且很少进行插入和删除操作，但要求以最快的

11、速度存取线性表中的元素，应选用何种存储结构？试说明理由。5 .在单循环链表中设置尾指针比设置头指针好吗？为什么？参考答案：一、选择题1. 2. A3. D4. C5. D6. A7. B8. B9. C10. A11. D12. B13. C14. B15. C16. C17. B18. D19. C20. A二、填空题1 .线性2 .n-i+13 .相邻4 .前移，前,后5 .物理存储位置，链域的指针值6 .前趋，后继7 .顺序，链接8 .一定，不一定9 .单链表，双链表，非循环链表，循环链表10 .使空表和非空表统一；算法处理一致三、简答题1 .头指针是指向链表中第一个结点(即表头结点)的

12、指针；在表头结点之前附设的结点称为头结点；表头结点为链表中存储线性表中第一个数据元素的结点。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空，否则表示空表的链表的头指针为空。2 .线性表具有两种存储结构即顺序存储结构和链接存储结构。线性表的顺序存储结构可以直接存取数据元素，方便灵活、效率高，但插入、删除操作时将会引起元素的大量移动，因而降低效率：而在链接存储结构中内存采用动态分配，利用率高，但需增设指示结点之间关系的指针域，存取数据元素不如顺序存储方便，但结点的插入、删除操作较简单。3 .应选用链接存储结构，因为链式存储结构是用一组任意的存储单元依次存储线性表中的各元素，这里存储单元

13、可以是连续的，也可以是不连续的：这种存储结构对于元素的删除或插入运算是不需要移动元素的，只需修改指针即可，所以很容易实现表的容量的扩充。4 .应选用顺序存储结构，因为每个数据元素的存储位置和线性表的起始位置相差一个和数据元素在线性表中的序号成正比的常数。因此，只要确定了其起始位置，线性表中的任一个数据元素都可随机存取，因此，线性表的顺序存储结构是一种随机存取的存储结构，而链表则是一种顺序存取的存储结构。5 .设尾指针比设头指针好。尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear,则开始结点和终端结点的位置分别是rear-next-next和rear,查找时间都是0(1)。若用头指针来表示该链表，则查找终端结点的时间为0(n)。第三章栈和队列习题一、选择题1. B2. B3. C4. D5. C6. A7. A二、填空题1 .SXSSXSXX2 .牺牲一个存储单元设标记3. 154. 23三、简答题1 .共有14中可能的出栈序列，分别为：ABCD,ABDC,ACBD,ACDB,BACD,DCB,BADC,BCAD,BCDA,BDCA,CBAD,CBDA,CDBA,DCBAo2 .循环队列解决一般顺序队列“假溢出”的办法是把数组的头指针和尾指针连接起来，基