8套题(含答案)数据结构期末复习

《8套题(含答案)数据结构期末复习》由会员分享，可在线阅读，更多相关《8套题(含答案)数据结构期末复习（53页珍藏版）》请在金锄头文库上搜索。

1、习题 1：绪论 一、单项选择题 1. 数据结构是指（ ）。 A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义 2. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（ ）。 A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构 3. 树形结构是数据元素之间存在一种（ ）。 A.一对一关系 B.多对多关系 C.多对一关系 D.一对多关系 4. 设语句 x+的时间是单位时间，则以下语句的时间复杂度为（ ）。 for(i=1; i=0)&Ai!=k) j-; return (i); 5. fact(n) if(nnext=s; s-prior=p; p-n

2、ext-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 之后的结点（若存在），则需修改指针的操作为 _。 A p-next=p-next-next; B p=p-next; C p=p-next-next; D p-nex

3、t=p; 7. 在一个长度为 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顺序存

4、取 C 索引存取 D散列存取 11. 在顺序表中，只要知道 _，就可在相同时间内求出任一结点的存储地址。 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

5、,下列是不可能的出栈序列_。 A 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-n

6、ext; 18. 在具有 n 个单元的顺序存储的循环队列中，假定 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

7、 20. 在一个链队列中，假定 front 和 rear 分别为队首和队尾指针，则删除一个结点的操作为 _。 A front=front-next B rear=rear-next C rear=front-next D front=rear-next 二、填空题 1. 线性表是一种典型的 线性 结构。 2. 在一个长度为 n 的顺序表 的 第 i 个元素 之 前插入一个元素， 需 要后移 n-i+1 个元素。 3. 顺序表中逻辑上相邻的元素的物理位置 相邻 。 4. 要从一个顺序表删除一个元素时，被删除元素之后的所有元素均需 前移 一个位置，移动过程是 从 后 向 前 依次移动每一个元素。

8、5. 在线性表的顺序存储中，元素之间的逻辑关系是通过 物理存储位置 决定的；在线性表的链接存储中，元素之间的逻辑关系是通过 链域的指针值 决定的。 6. 在双向链表中，每个结点含有两个指针域，一个指向 前驱 结点，另一个指向 后继 结点。 7. 当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用 顺序 存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用 链式 存储结构为宜。 8. 顺序表中逻辑上相邻的元素，物理位置 一定 相邻，单链表中逻辑上相邻的元素，物理位置 不一定 相邻。 9. 线性表 、栈和队列都是 线性 结构 ，可以在线性表的 任何 位置插入和删除元素；对于栈

9、只能在 栈顶 位置插入和删除元素；对于队列只能在 队尾 位置插入元素和在 队头 位置删除元素。 10. 根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为 单链表 和 双链表 ；而根据指针的联接方式，链表又可分为 循环链表 和 非循环链表 。 11. 在单链表中设置头结点的作用是 使空表和非空表统一；算法处理一致 。 12. 对于一个具有 n 个结点的单链表，在已知的结点 p 后插入一个新结点的时间复杂度为 O(1)，在给定值为 x 的结点后插入一个新结点的时间复杂度为 O(n)。 13. 对于一个栈作进栈运算时，应先判别栈是否为 栈满 ，作退栈运算时，应先判别栈是否为 栈空 ，当栈

10、中元素为 m 时，作进栈运算时发生上溢，则说明栈的可用最大容量为 m。为了增加内存空间的利用率和减少发生上溢的可能性，由两个栈共享一片连续的内存空间时，应将两栈的 栈底 分别设在这片内存空间的两端，这样只有当 两个栈的栈顶在栈空间的某一位置相遇 时才产生上溢。 14. 设有一空栈，现有输入序列 1， 2， 3， 4， 5，经过 push, push, pop, push, pop, push, push 后，输出序列是 2， 3。 15. 无论对于顺序存储还是链式存储的栈和队列来说，进行插入或删除运算的时间复杂度均相同为 O(1)。 -8- 三、简答题 1. 描述以下三个概念的区别：头指针，头

11、结点，表头结点。 答： 头指针是指向链表中第一个结点（即表头结点）的指针；在表头结点之前附设的结点称为头结点；表头结点为链表中存储线性表中第一个数据元素的结点。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空，否则表示空表的链表的头指针为空。 2. 线性表的两种存储结构各有哪些优缺点？ 答： 线性表具有两种存储结构即顺序存储结构和链接存储结构。线性 表的顺序存储结构可以直接存取数据元素，方便灵活、效率高，但插入、删除操作时将会引起元素的大量移动，因而降低效率：而在链接存储结构中内存采用动态分配，利用率高，但需增设指示结点之间关系的指针域，存取数据元素不如顺序存储方便，但结点的插入、删

12、除操作较简单。 3. 对于线性表的两种存储结构，如果有 n个线性表同时并存，而且在处理过程中各表的长度会动态发生变化，线性表的总数也会自动改变，在此情况下，应选用哪一种存储结构？为什么？ 答： 应选用链接存储结构，因为链式存储结构是用一组任意的存储单元依次存储线性表中的各元素， 这里存储单元可以是连续的，也可以是不连续的：这种存储结构对于元素的删除或插入运算是不需要移动元素的，只需修改指针即可，所以很容易实现表的容量的扩充。 4. 对于线性表的两种存储结构，若线性表的总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素，应选用何种存储结构？试说明理由。 答： 应选用顺序

13、存储结构，因为每个数据元素的存储位置和线性表的起始位置相差一个和数据元素在线性表中的序号成正比的常数。因此，只要确定了其起始位置，线性表中的任一个数据元素都可随机存取，因此，线性表的顺序存储结构 是一种随机存取的存储结构，而链表则是一种顺序存取的存储结构。 5. 在单循环链表中设置尾指针比设置头指针好 吗？ 为什么 ? 答： 设尾指针比设头指针好。尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为 rear，则开始结点和终端结点的位置分别是 rear-next-next 和 rear, 查找时间都是 O(1)。若用

14、头指针来表示该链表，则查找终端结点的时间为 O(n)。 6. 假定有四个元素 A, B, C, D 依次进栈，进栈过程中允许 出栈，试写出所有可能的出栈序列。 答： 共有 14种可能的出栈序列，即为： ABCD, ABDC， ACBD, ACDB， BACD， ADCB， BADC， BCAD, BCDA， BDCA,CBAD, CBDA， CDBA, DCBA 7. 什么是队列的上溢现象？一般有几种解决方法，试简述之。 答： 在队列的顺序存储结构中，设队头指针为 front，队尾指针为 rear，队列的容量（即存储的空间大小）为 maxnum。当有元素要加入队列（即入队）时，若 rear=maxnum，则会发生队列的上溢现象，此时就不能将该元素加入队列。对 于队列，还有一种“假溢出” -9- 现象，队列中尚余有足够的空间，但元素却不能入队，一般是由于队列的存储结构或操作方式的选择不当所致，可以用循环队列解决。 一般地，要解决队列的上溢现象可有以下几种方法： （ 1）可建立一个足够大的存储空间以避免溢出，但这样做往往会造成空间使用率低，浪费存储空间。 （ 2）要避免出现“假溢出”现象可用以下方法解决： 第一种：采用移动元素的方法。每当有一个新元素入队，就将队列中已