《计算机专业 数据结构习题及参考答案》由会员分享，可在线阅读，更多相关《计算机专业 数据结构习题及参考答案（51页珍藏版）》请在金锄头文库上搜索。
1、习题 1一、单项选择题*1. 数据结构是指（）A。A.数据元素的组织形式 B.数据类型C.数据存储结构 D.数据定义2. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（ C ） 。A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构3. 树形结构是数据元素之间存在一种（ D ） 。A.一对一关系 B.多对多关系 C.多对一关系 D.一对多关系4. 设语句 x+的时间是单位时间，则以下语句的时间复杂度为（B ） 。for(i=1; i=0)&Ai!=k)j-;return (i);5. fact(n) if(nnext=s; s-prior=p;p-next-prio
2、r=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;-5-p-next-prior=s; p-next=s;6. 设单链表中指针 p 指向结点 m，若要删除 m 之后的结点（若存在） ，则需修改指针的操作为_A_。Ap-next=p-next-next; Bp=p-next;Cp=p-next-next; Dp-next=p;7. 在一个长度为 n
3、的顺序表中向第 i 个元素(0next=p-next; p-next=sBq-next=s; s-next=pCp-next=s-next; s-next=pDp-next=s; s-next=q9. 以下关于线性表的说法不正确的是_C_ 。 A线性表中的数据元素可以是数字、字符、记录等不同类型。B线性表中包含的数据元素个数不是任意的。C线性表中的每个结点都有且只有一个直接前趋和直接后继。D存在这样的线性表：表中各结点都没有直接前趋和直接后继。(空表)10. 线性表的顺序存储结构是一种_A_ 的存储结构。 A随机存取 B顺序存取 C索引存取 D散列存取11. 在顺序表中，只要知道_D_ ，就可
4、在相同时间内求出任一结点的存储地址。A基地址 B结点大小 C向量大小 D基地址和结点大小12. 在等概率情况下，顺序表的插入操作要移动_B_结点。 A全部 B一半 C三分之一 D四分之一13. 在_C_运算中，使用顺序表比链表好。 A插入 B删除 C根据序号查找 D根据元素值查找14. 在一个具有 n 个结点的有序单链表中插入一个新结点并保持该表有序的时间复杂度是_B_。 AO(1) BO (n) CO(n 2) DO (log2n)15. 设有一个栈，元素的进栈次序为 A, B, C, D, E,下列是不可能的出栈序列_C_。AA, B, C, D, E BB, C, D, E, ACE,
5、A, B, C, D DE, D, C, B, A Comment w2: 概念问题-6-16. 在一个具有 n个单元的顺序栈中，假定以地址低端（即 0单元）作为栈底，以 top作为栈顶指针，当做出栈处理时，top 变化为_C_ 。Atop 不变 Btop=0 Ctop- Dtop+17. 向一个栈顶指针为 hs的链栈中插入一个 s 结点时，应执行_C_B_ 。Ahs-next=s; Bs-next=hs; hs=s;Cs-next=hs-next;hs-next=s; Ds-next=hs; hs=hs-next;18. 在具有 n个单元的顺序存储的循环队列中，假定 front和 rear分
6、别为队头指针和队尾指针，则判断队满的条件为_D_ 。Arearn= = front B （front+l）n= = rearCrearn -1= = front D(rear+l)n= = front19. 在具有 n个单元的顺序存储的循环队列中，假定 front和 rear分别为队头指针和队尾指针，则判断队空的条件为_C_ 。Arearn= = front Bfront+l= rearCrear= = front D(rear+l)n= front20. 在一个链队列中，假定 front和 rear分别为队首和队尾指针，则删除一个结点的操作为_A_。Afront=front-next Bre
7、ar=rear-nextCrear=front-next Dfront=rear-next二、填空题 1. 线性表是一种典型的_顺序存储_结构。2. 在一个长度为 n的顺序表的第 i 个元素之前插入一个元素，需要后移_个元素。3. 顺序表中逻辑上相邻的元素的物理位置_。4. 要从一个顺序表删除一个元素时，被删除元素之后的所有元素均需_一个位置，移动过程是从_向_依次移动每一个元素。5. 在线性表的顺序存储中，元素之间的逻辑关系是通过_物理存储地址_决定的；在线性表的链接存储中，元素之间的逻辑关系是通过_链域的指针值 _决定的。6. 在双向链表中，每个结点含有两个指针域，一个指向_前驱_结点，另
8、一个指向_后继_结点。7. 当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用_顺序_存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用_链接_存储结构为宜。8. 顺序表中逻辑上相邻的元素，物理位置_一定_相邻，单链表中逻辑上相邻的元素，物理位置_不一定_相邻。9. 线性表、栈和队列都是_线性_结构，可以在线性表的_任何_位置插入和删除元素；对于栈只能在_栈顶_位置插入和删除元素；对于队列只能在_队尾_位-7-置插入元素和在_队首_位置删除元素。10. 根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为_单链表_和双链表_；而根据指针的联接方式，链表又可分为_
9、循环_和_非循环_。11. 在单链表中设置头结点的作用是_利于插入和删除操作_。12. 对于一个具有 n 个结点的单链表，在已知的结点 p 后插入一个新结点的时间复杂度为_O(1)_ ，在给定值为 x 的结点后插入一个新结点的时间复杂度为_O(n)_ 。13. 对于一个栈作进栈运算时，应先判别栈是否为_，作退栈运算时，应先判别栈是否为_，当栈中元素为 m 时，作进栈运算时发生上溢，则说明栈的可用最大容量为_。为了增加内存空间的利用率和减少发生上溢的可能性，由两个栈共享一片连续的内存空间时，应将两栈的_分别设在这片内存空间的两端，这样只有当_时才产生上溢。14. 设有一空栈，现有输入序列 1，2
10、，3，4，5，经过 push, push, pop, push, pop, push, push 后，输出序列是_。15. 无论对于顺序存储还是链式存储的栈和队列来说，进行插入或删除运算的时间复杂度均相同为_。三、简答题 1. 描述以下三个概念的区别：头指针，头结点，表头结点。2. 线性表的两种存储结构各有哪些优缺点？3. 对于线性表的两种存储结构，如果有 n 个线性表同时并存，而且在处理过程中各表的长度会动态发生变化，线性表的总数也会自动改变，在此情况下，应选用哪一种存储结构？为什么？4. 对于线性表的两种存储结构，若线性表的总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性
11、表中的元素，应选用何种存储结构？试说明理由。5. 在单循环链表中设置尾指针比设置头指针好吗？为什么?6. 假定有四个元素 A, B, C, D 依次进栈，进栈过程中允许出栈，试写出所有可能的出栈序列。7. 什么是队列的上溢现象？一般有几种解决方法，试简述之。8. 下述算法的功能是什么?LinkList *Demo(LinkList *L) / L 是无头结点的单链表LinkList *q,*p;if(L&L-next) q=L; L=L-next; p=L;while (p-next) p=p-next;p-next=q; q-next=NULL;return (L);-8-四、算法设计题1.
12、 设计在无头结点的单链表中删除第 i 个结点的算法。2. 在单链表上实现线性表的求表长 ListLength(L)运算。3. 设计将带表头的链表逆置算法。4. 假设有一个带表头结点的链表，表头指针为 head，每个结点含三个域：data, next和 prior。其中 data 为整型数域， next 和 prior 均为指针域。现在所有结点已经由 next 域连接起来，试编一个算法，利用 prior 域（此域初值为 NULL）把所有结点按照其值从小到大的顺序链接起来。5. 已知线性表的元素按递增顺序排列，并以带头结点的单链表作存储结构。试编写一个删除表中所有值大于 min 且小于 max 的
13、元素（若表中存在这样的元素）的算法。6. 已知线性表的元素是无序的，且以带头结点的单链表作为存储结构。设计一个删除表中所有值小于 max 但大于 min 的元素的算法。7. 假定用一个单循环链表来表示队列（也称为循环队列） ，该队列只设一个队尾指针，不设队首指针，试编写下列各种运算的算法：（1）向循环链队列插入一个元素值为 x 的结点；（2）从循环链队列中删除一个结点。8. 设顺序表 L 是一个递减有序表，试写一算法，将 x 插入其后仍保持 L 的有序性。习题 2 参考答案一、单项选择题1A 2A 3D 4C 5D 6A 7B 8B 9C 10A 11D 12B 13C 14B 15C 16C
14、 17B 18D 19C 20A二、填空题1线性 2n-i+1 3相邻 4前移，前，后5物理存储位置，链域的指针值 6前趋，后继7顺序，链接 8一定，不一定9线性，任何，栈顶，队尾，队头10单链表，双链表，非循环链表，循环链表11使空表和非空表统一；算法处理一致-9-12O(1)，O(n)13栈满，栈空，m，栈底，两个栈的栈顶在栈空间的某一位置相遇142、315O(1)三、简答题1头指针是指向链表中第一个结点（即表头结点）的指针；在表头结点之前附设的结点称为头结点；表头结点为链表中存储线性表中第一个数据元素的结点。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空，否则表示空表的链表的头指针为空。2线性表具有两种存储结构即顺序存储结构和链接存储结构。线性表的顺序存储结构可以直接存取数据元素，方便灵活、效率高，但插入、删除操作时将会引起元素的大量移动，因而降低效率：而在链接存储结构中内存采用动态分配，利用率高，但需增设指示结点之间
