1、习题 1 一、单项选择题 1. 数据结构是指（ ）。 A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义 2. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（ ）。 A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构 3. 树形结构是数据元素之间存在一种（ ）。 A.一对一关系 B.多对多关系 C.多对一关系 D.一对多关系 4. 设语句 x+的时间是单位时间，则以下语句的时间复杂度为（ ）。 for(i=1; i=0) return (i); 5. fact(n) if(nnext=s; s-prior=p; p-next-prior=s; s
2、-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 之后的结点（若存在），则需修改指针的操作为 _。 A p-next=p-next-next; B p=p-next; C p=p-next-next; D p-next=p; 7. 在一个长度为
3、 n 的顺序表中 向第 i 个元素 (0next=p-next; p-next=s B q-next=s; s-next=p C p-next=s-next; s-next=p -6- D p-next=s; s-next=q 9. 以下关于线性表的说法不正确的是 _。 A 线性表中的数据元素可以是数字、字符、记录等不同类型。 B 线性表中包含的数据元素个数不是任意的。 C 线性表中的每个结点都有且只有一个直接前趋和直接后继。 D 存在这样的线性表：表中各结点都没有直接前趋和直接后继。 10. 线性表的顺序存储结构是一种 _的存储结构。 A 随机存取 B顺序存取 C 索引存取 D散列存取 11
4、. 在顺序表中，只要知道 _，就可在相同时间内求出任一结点的存储地址。 A 基地址 B结点大小 C 向量大小 D 基地址和结点大小 12. 在等概率情况下，顺序表的插入操作要移动 _结点。 A 全部 B一半 C 三分之一 D 四分之一 13. 在 _运算中，使用顺序表比链表好。 A 插入 B 删除 C 根据序号查找 D 根据元素值查找 14. 在一个具有 n 个结点的有序单链表中插入一个新结点并 保持该表 有序的时间复杂度是 _。 A O(1) B O(n) C O(n2) D O(log2n) 15. 设有一个栈，元素的进栈次序为 A, B, C, D, E,下列是不可能的出栈序列_。 A
5、A, B, C, D, E B B, C, D, E, A C E, A, B, C, D D E, D, C, B, A 16. 在一个具有 n 个单元的顺序栈中，假定以地址低端（即 0 单元）作为栈底，以 top作为栈顶指针，当做出栈处理时， top 变化为 _。 A top 不变 B top=0 C top- D top+ 17. 向一个栈顶指针为 hs 的链栈中插入一个 s 结点时，应执行 _。 A 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 个
6、单元的顺序存储的循环队列中，假定 front 和 rear 分别为队头指针和队尾指针，则判断队满的条件为 _。 A rear n= = front B（ front+l） n= = rear C rear n -1= = front D (rear+l) n= = front 19. 在具有 n 个单元的顺序存储的循环队列中，假定 front 和 rear 分别为队头指针和队-7- 尾指针，则判断队空的条件为 _。 A rear n= = front B front+l= rear C rear= = front D (rear+l) n= front 20. 在一个链队列中，假定 front
7、 和 rear 分别为队首和队尾指针，则删除一个结点的操作为 _。 A front=front-next B rear=rear-next C rear=front-next D front=rear-next 二、填空题 1. 线性表是一种典型的 _结构。 2. 在一个长度为 n 的顺序表 的 第 i 个元素 之 前插入一个元素， 需 要后移 _个元素。 3. 顺序表中逻辑上相邻的元素的物理位置 _。 4. 要从一个顺序表删除一个元素时，被删除元素之后的所有元素 均需 _一个位置，移动过程是从 _向 _依次移动每一个元素。 5. 在线性表的顺序存储中，元素之间的逻辑关系是通过 _决定的；在线
8、性表的链接存储中，元素之间的逻辑关系是通过 _决定的。 6. 在双向链表中，每个结点含有两个指针域，一个指向 _结点，另一个指向_结点。 7. 当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用 _存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用 _存储结构为宜。 8. 顺序表中逻辑上相邻的元素，物理位置 _相邻，单链表中逻辑上相邻的元素，物理位置 _相邻。 9. 线性表、栈和队列都是 _结构，可以在线性表的 _位置插入和删除元素；对于栈只能在 _位置插入和删除元素；对于队列只能在 _位置插入元素和在_位置删除元素。 10. 根据线性表的链式存储结构中每个结点所含指针
9、的个数，链表可分为 _和 _；而根据指针的联接方式，链表又可分为 _和 _。 11. 在单链表中设置头结点的作用是 _。 12. 对于一个具有 n 个结点的单链表，在已知的结点 p 后插入一个新结点的时间复杂度为 _，在给定值为 x 的结点后插入一个新结点的时间复杂度为 _。 13. 对于一个栈作进栈运算时，应先判别栈是否为 _，作退栈运算时，应先判别栈是否为 _，当栈中元素为 m 时，作进栈运算时发生上溢，则说明栈的可用最大容量为 _。为了增加内存空间的利用率和减少发生上溢的可能性，由两个栈共享一片连续的内存空间时，应将两栈的 _分别设在这片内存空间的两端，这样只有当 _时才产生上溢。 14
10、. 设有一空栈，现有输入序列 1， 2， 3， 4， 5，经过 push, push, pop, push, pop, push, push 后，输出序列是 _。 15. 无论对于顺序存储还是链式存储的栈和队列来说，进行插入或删除运算的时间复杂度均相同为 _。 -8- 三、简答题 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=L-next; p=L; while (p-next) p=p-next; p-next=q;
12、 q-next=NULL; return (L); 四、算法设计题 1. 设计在无头结点的单链表中删除第 i 个结点的算法。 2. 在单链表上实现线性表的 求表长 ListLength(L)运算。 3. 设计将带表头的链表逆置算法。 4. 假设有一个带表头结点的链表，表头指针为 head，每个结点含三个域： data, next和 prior。其中 data 为整型数域， next 和 prior 均为指针域。现在所有结点已经由 next 域连接起来，试编一个算法，利用 prior 域（此域初值为 NULL）把所有结点按照其值从小到大的顺序链接起来。 5. 已知线性表的元素按递增顺序排列，并以
13、带头结点的单链表作存储结构。试编写一个删除表中所有值大于 min 且小于 max 的元素（若表中存在这样的元素）的算法。 6. 已知线性表 的元素是无序的，且以带头结点的单链表作为存储结构。设计一 个删除表中所有值小于 max 但大于 min 的元素的算法。 7. 假定用一个单循环链表来表示队列（也称为循环队列），该队列只设一个队尾指针，-9- 不设队首指针，试编写下列各种运算的算法： （ 1）向循环链队列插入一个元素值为 x 的结点； （ 2）从循环链队列中删除一个结点。 8. 设顺序表 L 是一个递减有序表，试写一算法，将 x 插入其后仍保持 L 的有序性。 习题 2 参考答案 一、单项选
14、择题 1 A 2 A 3 D 4 C 5 D 6 A 7 B 8 B 9 C 10 A 11 D 12 B 13 C 14 B 15 C 16 C 17 B 18 D 19 C 20 A 二、填空题 1 线性 2 n-i+1 3 相邻 4前移，前，后 5物理存储位置，链域的指针值 6前趋，后继 7顺序，链接 8一定，不一定 9线性，任何，栈顶，队尾，队头 10单链表，双链表，非循环链表，循环链表 11使空表和非空表统一；算法处理一致 12 O(1)， O(n) 13栈满，栈空， m，栈底，两个栈的栈顶在栈空间的某一位置相遇 14 2、 3 15 O(1) 三、简答题 1 头指针是指向链表中第一
15、个结点（即表头结点）的指针；在表头结点之前附设的结点称为头结点；表头结点为链表中存储线性表中第一个数据元素的结点。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空，否则表示空表的链表的头指针为空。 2线性表具有两种存储结构即顺序存储结构和链接存储结构。线性表的顺序存储结构可以直接存取数据元素，方便灵活、效率高，但插入、删除操作时将会引起元素的大量移动，因而降低效率 ：而在链接存储结构中内存采用动态分配，利用率高，但需增设指示结点之间关系的指针域，存取数据元素不如顺序存储方便，但结点的插入、删除操作较简单。 3应选用链接存储结构，因为链式存储结构是用一组任意的存储单元依次存储线性表-1
16、0- 中的各元素，这里存储单元可以是连续的，也可以是不连续的：这种存储结构对于元素的删除或插入运算是不需要移动元素的，只需修改指针即可，所以很容易实现表的容量的扩充。 4应选用顺序存储结构，因为每个数据元素的存储位置和线性表的起始位置相差一个和数据元素在线性表中的序号成正比的常数。因此，只要确定 了其起始位置，线性表中的任一个数据元素都可随机存取，因此，线性表的顺序存储结构是一种随机存取的存储结构，而链表则是一种顺序存取的存储结构。 5设尾指针比设头指针好。 尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为 re
17、ar，则开始结点和终端结点的位置分别是 rear-next-next 和 rear, 查找时间都是 O(1)。若用头指针来表示该链表，则查找终端结点的时间为 O(n)。 6共有 14 种可能的出栈序列，即为： ABCD, ABDC， ACBD, ACDB， BACD， ADCB， BADC， BCAD, BCDA， BDCA,CBAD, CBDA， CDBA, DCBA 7在队列的顺序存储结构中，设队头指针为 front，队尾指针为 rear，队列的容量（即存储的空间大小）为 maxnum。当有元素要加入队列（即入队）时，若 rear=maxnum，则会发生队列的上溢现象，此时就不能将该元素加
18、入队列。对于队列，还有一种“假溢出”现象，队列中尚余有足够的空间，但元素却不能入队，一般是由于队列的存储结构或操作方式的选择不当所致，可以用循环队列 解决。 一般地，要解决队列的上溢现象可有以下几种方法： （ 1）可建立一个足够大的存储空间以避免溢出，但这样做往往会造成空间使用率低，浪费存储空间。 （ 2）要避免出现“假溢出”现象可用以下方法解决： 第一种：采用移动元素的方法。每当有一个新元素入队，就将队列中已有的元素向队头移动一个位置，假定空余空间足够。 第二种：每当删去一个队头元素，则可依次移动队列中的元素总是使 front 指针指向队列中的第一个位置。 第三种：采用循环队列方式。将队头、队尾看作是一个首尾相接的循环队列，即用 循环数组实现，此时队首仍在队尾之前，作插入和删除运算时仍遵循“先进先出”的原则。 8 该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。 四、算法设计题 1算法思想为： （ 1）应判断删除位置的合法性，当 in-1 时，不允许进行删除操作； （ 2）当 i=0 时，删除第一个结点： （ 3）当 in 时，允许进行删除操作，但在查找被删除结点时，须用指针记住该结点的前趋结点。算法描述如下： delete(LinkList *q,int i)
