数据结构(习题一)

《数据结构(习题一)》由会员分享，可在线阅读，更多相关《数据结构(习题一)（40页珍藏版）》请在金锄头文库上搜索。

1、数 据 结 构,习 题 一,第一章 绪 论,考点一 数据的逻辑结构、存储结构,本考点主要考查： 1、集合结构、线性结构、 树结构和图结构的特点。 2、抽象数据类型的定义和表示方法。 3、注意区分什么是数据的逻辑结构，什么是数据的存储结构。,第一部分 绪 论,在数据结构的讨论中把数据结构从逻辑上分为 （ ） A. 内部结构与外部结构 B. 静态结构与动态结构 C. 线性结构与非线性结构 D. 紧凑结构与非紧凑结构,考点一 数据的逻辑结构、存储结构,我们常见的顺序表，就是线性结构，而树形结构和图形结构是非线性结构。 线性结构中元素之间存在一对一关系， 非线性结构中元素之间存在一对多关系或者多对多关

2、系。,C,第一部分 绪 论,考点一 数据的逻辑结构、存储结构,2. 在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 （ ） 数据的处理方法 B. 数据元素的类型 C. 数据元素之间的关系 D. 数据的存储方法,顺序存储方法把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。链式存储方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系由附加的指针表示。,C,第一部分 绪 论,考点一 数据的逻辑结构、存储结构,3. 数据结构 DS(Data Struct)可以被形式地定义为 DS=（ D， R），其中 D是( )的有限集合， R 是 D

3、 上的关系有限集合。 算法 B. 数据元素 C. 数据操作 D. 数据对象,B,第一部分 绪 论,考点二 算法以及算法的时间复杂度和空间复杂度,主要考查算法的时间复杂度和空间复杂度的概念，计算方法，数量级表示。学会通过 for 循环或者 while 循环来计算算法的时间复杂度。,第一部分 绪 论,考点二 算法以及算法的时间复杂度和空间复杂度,算法分析的目的是 （ ） A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性,C,对算法的讨论不能只研究它是否能在有穷步内终止，还应对算法的运行效率作出分析，判断算法的好坏，以便在已

4、有的资源条件下作出最佳的决策。,第一部分 绪 论,考点二 算法以及算法的时间复杂度和空间复杂度,2. 设语句 x+的时间是单位时间，则以下语句的时间复杂度为 （ ） for(i=1; i=n; i+) for(j=i; j=n; j+) x+; A. O(1) B. O(n2) C. O(n) D. O(n3),B,我们常说的分析算法的时间复杂度，就是分析算法的规模 n 的函数 f(n)。本题中存在着两层 for 循环，当 i=1 时，内层循环执行 n 次，当 i=2 时内层循环执行 n-1 次，分析可知，总共执行了近O(n2)。 要特别注意，在分析时间复杂度时，我们通常采用抓取大端的办法，进

5、行粗略估计，不会进行详细计算。,第一部分 绪 论,考点二 算法以及算法的时间复杂度和空间复杂度,3. 下面程序段的时间复杂度是 （ ） for(i=0;im;i+) for(j=0;jn;j+) aij=i*j; A. O(m2) B. O(n2) C. O(m*n) D. O(m+n),C,题中的程序有两层 for 循环，外层循环执行 m 次，而每执行一次外层循环，内层循环需要执行 n 次，故而总共执行 mn次，算法的时间复杂度为O(mn)。,第二部分 线性表,考点一 线性表的定义和基本操作,本考点主要考查线性表的定义及判别和抽象数据类型的描述，线性表中每一种操作的功能，对应的函数名、返回值

6、类型和参数表中每个参数的作用。 请同学们掌握线性表的基本概念和相关操作。,第二部分 线性表,考点一 线性表的定义和基本操作,下面关于线性表的叙述中，错误的是 （ ） A. 线性表采用顺序存储，必须占用一片连续的存储单元 B. 线性表采用顺序存储，便于进行插入和删除操作。 C. 线性表采用链式存储，不必占用一片连续的存储单元 D. 线性表采用链式存储，便于进行插入和删除操作,B,关于线性表，我们常接触到的存储结构有顺序存储和链式存储。 顺序存储结构的地址是连续的（即必须占用一片连续的存储空间）， 所以可以通过计算地址实现随机存取。 链式存储结构的存储地址不一定连续，只能通过每一个结点的指针顺序存

7、取。 采用顺序存储结构时，插入和删除元素都需要移动大量元素，不便于插入和删除操作。采用链式存储结构便于插入和删除操作，但是查找只能顺序进行,第二部分 线性表,考点一 线性表的定义和基本操作,2. 以下关于线性表的说法不正确的是 （ ） A. 线性表中的数据元素可以是数字、字符、记录等不同类型 B. 线性表中包含的数据元素个数不是任意的 C. 线性表中的每个结点都有且只有一个直接前趋和直接后继 D. 存在这样的线性表：表中各结点都没有直接前趋和直接后继,C,线性表中的数据元素具有抽象（即不确定）的数据类型， 可以是数字、字符、记录等不同类型， 在设计具体的应用程序时，数据元素的抽象类型将被具体的

8、数据类型所取代。 线性表中包含的数据元素个数不是任意的，必须是有限的。 在一个非空表 L=（ a1， a2,an）中，任意一对相邻的数据元素 ai-1 和 ai 之间(1in)存在序偶关系(ai-1,ai)，且 ai-1 称为 ai 的前驱， ai 称为 ai-1 的后继。在这个序列中， a1 无前驱，an 无后继，其他每个元素有且仅有一个前驱和一个后继。 若为空表，或者表中只有一个元素，则该元素没有直接前驱结点，也没有直接后继结点,第二部分 线性表,考点二 线性表的顺序存储,本考点主要考查： 1、 线性表的顺序存储结构的类型定义； 2、 线性表在顺序存储结构上的算法实现，及相应的时间复杂度。

9、,第二部分 线性表,考点二 线性表的顺序存储,1. 在 n 个结点的线性表的数组实现中，算法的时间复杂度是 O(1)的操作是 （ ） A. 访问第 i（ 1=i=n）个结点和求第 i 个结点的直接前驱（ 1i=n） B. 在第 i（ 1=i=n）个结点后插入一个新结点 C. 删除第 i（ 1=i=n）个结点 D. 以上都不对,对顺序表的读取操作，时间复杂度为 O(1)，故而 A 答案正确。 假设 i 是随机的，则在第 i 个位置之后插入一个新结点平均需要移动近一半表长的元素，时间复杂度为 O(n)。同理，删除第 i 个元素的时间复杂度也是 O(n)。 所以，B、C 答案错误。,A,第二部分 线

10、性表,考点二 线性表的顺序存储,2. 在一个长度为 n 的顺序表中删除第 i 个元素，需要向前移动 （ ）个元素。 A. n-i B. n-i+1 C. n-i-1 D. i+1,A,本题考查顺序表删除元素时表的元素移动情况。在一个长度为 n 的顺序表中删除第 i 个元素，第 i+1 个位置的元素移到第原第 i 个位置，第 i+2 个位置的元素移动到第i+1 个位置， ，第 n 个位置的元素移动到第 n-1 个位置，共需移动 n-i 个元素。,第二部分 线性表,考点二 线性表的顺序存储,3. 顺序表中， 在任何一个位置插入元素的概率相等，则插入一个元素所需移动的元素平均数是（ ）。 A. (n

11、-1)/2 B. n C. n+1 D. n/2,D,4. 在表长为 n 的顺序表中，当在任何位置删除一个元素的概率相同时，删除一个元素所需移动的平均个数为（ ）。 A. (n-1)/2 B. n/2 C. (n+1)/2 D. n,A,具体分析见教材P25,第二部分 线性表,考点三 线性表的链式存储,本考点主要考查： 1、链接存储的概念； 2、单链表、双链表和循环链表的相关概念和基本操作； 3、线性表在链式存储上的算法实现，以及相应的时间复杂度。,第二部分 线性表,考点三 线性表的链式存储,在一个长度为n（n1）的单链表上，设有头和尾两个 指针，分别指向该链表的第一个结点和最后一个结点，则执

12、行（ ）操作与链表的长度有关。 A. 删除单链表中的第一个元素 B. 删除单链表中的最后一个元素 C. 在单链表第一个元素前插入一个新元素 D. 在单链表最后一个元素后插入一个新元素,B,第二部分 线性表,考点三 线性表的链式存储,2. 在循环双链表的p所指的结点之前插入s所指结点的操作是 （ ） p-prior = s；s-next = p；p-prior-next = s；s-prior = p-prior B. p-prior = s；p-prior-next = s；s-next = p；s-prior = p-prior C. s-next = p；s-prior = p-prior

13、；p-prior = s；p-prior-next = s D. s-next = p；s-prior = p-prior；p-prior-next = s；p-prior = s,总结方法： (1). 先解决待插入结点s的两个指针域（s的两个指针域的调整，可以交换顺序）； (2). 再解决s结点的前驱结点p和后继结点q的指针域（p和q的指针域调整，也可以交换顺序，但是当题目只告知p和q当中的一个时，另作考虑。如本题只告诉p，则只能先让p的前驱结点的后继指针指向s，再调整p的前驱指针指向s）。,D,第二部分 线性表,考点三 线性表的链式存储,3. 已知指针p和q分别指向某单链表中第一个结点和最

14、后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为 （ ） A. q-next=s-next；s-next=p； B. s-next=p；q-next=s-next； C. p-next=s-next；s-next=q； D. s-next=q；p-next=s-next；,在指针s指向的某一个结点之后插入一段以p和q分别指向第一个结点和最后一个结点的链表，只需要令q的指针域指向s的后继结点（q-next=s-next），再调整s的指针域，使其指向新的后继结点p即可(s-next=p)，如下图所示。,A,第三部分 栈、队列和数组,考点一 栈和队列的概

15、念和基本操作,本部分考查栈和队列的概念，以及基本操作。请注意栈和队列的性质，并掌握二者的基本操作。,第三部分 栈、队列和数组,考点一 栈和队列的概念和基本操作,设有一个栈，元素依次进栈的顺序为A、B、C、D、E。 下列（ ）是不可能的出栈序列。 A. A,B,C,D,E B. B,C,D,E,A C. E,A,B,C,D D. E,D,C,B,A,对于A答案，A元素进栈出栈、B元素进栈出栈、C元素进栈出栈、D元素进栈出栈、E元素进栈出栈，即可得到出栈序列A、B、C、D、E。 对于B答案，将A压入栈底，然后B元素进栈出栈、C元素进栈出栈、D元素进栈出栈、E元素进栈出栈，即可得到出栈序列B、C、D、E、A。 对于D答案，将A、B、C、D、E五个元素依次压栈，再出栈，即可得到序列E、D、C、B、A。 对于C答案，要保证E先出栈，那么A、B、C、D四个元素只能压栈而不能出栈。也就是说，若出栈序列以E开头，则只有一个序列E、D、C、B、A，故而该答案错误。,C,第三部分 栈、队列和数组,考点一 栈和队列的概念和基本操作,2.