数据结构练习题与答案.docx

1、第 1 章 绪 论一、判断题1. 数据的逻辑结构与数据元素本身的内容和形式无关。（）2. 一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。（）3. 数据元素是数据的最小单位。（）4. 数据的逻辑结构和数据的存储结构是相同的。（）5. 程序和算法原则上没有区别，所以在讨论数据结构时可以通用。（）6. 从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。（）7. 数据的存储结构是数据的逻辑结构的存储映象。（）8. 数据的物理结构是指数据在计算机内实际的存储形式。（）9. 数据的逻辑结构是依赖于计算机的。（）10. 算法是对解题方法和步骤的描述。（）二、填空题1. 数据

2、有逻辑结构和 存储结构两种结构。2. 数据逻辑结构除了集合以外，还包括线性结构、树形结构和图形结构。3. 数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。4. 树形结构和图形结构合称为非线性结构。5. 在树形结构中，除了树根结点以外，其余每个结点只有 1 个前驱结点。6. 在图形结构中，每个结点的前驱结点数和后继结点数可以任意多个。7. 数据的存储结构又叫物理结构。8. 数据的存储结构形式包括顺序存储、链式存储、索引存储和散列存储。9. 线性结构中的元素之间存在一对一的关系。10. 树形结构中的元素之间存在一对多的关系。11. 图形结构的元素之间存在多对多的关系。12. 数据结构主

3、要研究数据的逻辑结构、存储结构和算法（或运算）3 个方面的内容。13. 数据结构被定义为（D，R），其中 D 是数据的有限集合，R 是 D 上的关系有限集合。14. 算法是一个有穷指令的集合。15. 算法效率的度量可以分为事先估算法和事后统计法。16. 一个算法的时间复杂度是算法 输入规模的函数。17. 算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题规模的 n 的函数。18. 若一个算法中的语句频度之和为 T(n)=6n+3nlog2n,则算法的时间复杂度为 O（ nlog2n）。19. 若一个算法的语句频度之和为 T(n)=3n+nlog2+n2,则算法的时间复杂度为 O（n

4、2）。20. 数据结构是一门研究非数值计算的程序问题中计算机的操作对象，以及它们之间的关系和运算的学科。三、选择题1. 数据结构通常是研究数据的（A）及它们之间的相互关系。A存储结构和逻辑结构B存储和抽象C联系和抽象D联系与逻辑2. 在逻辑上可以把数据结构分成（C）。 A动态结构和静态结构B紧凑结构和非紧凑结构C线性结构和非线性结构 D内部结构和外部结构。3. 数据在计算机存储内表示时，物理地址和逻辑地址相同并且是连续的，称之为（C）。A存储结构B逻辑结构C顺序存储结构D链式存储结构4. 非线性结构中的每个结点（D）。A无直接前驱结点B无直接后继结点38C只有一个直接前驱结点和一个直接后继结点

5、 D可能有多个直接前驱结点和多个直接后继结点5. 链式存储结构所占存储空间（A）。 A分两部分，一部分存放结点的值，另一个部分存放表示结点间关系的指针。 B只有一部分，存放结点的值。C只有一部分，存储表示结点间关系的指针。D分两部分，一部分存放结点的值，另一部分存放结点所占单元素6. 算法的计算量大小称为算法的（C）。A现实性B难度C时间复杂性D效率7. 数据的基本单位（B）。A数据结构B数据元素C数据项D文件8. 每个结点只含有一个数据元素，所有存储结点相继存放在一个连续的存储空间里，这种存储结构称为（A）结构。A顺序结构B链式结构C索引结构D散列结构9. 每一个存储结点不仅含有一个数据元素

6、，还包含一组指针，该存储方式是（B）。A顺序B链式C索引D散列10. 以下任何两个结点之间都没有逻辑关系的是（D）。A图形结构B线性结构C树形结构D集合11. 在数据结构中，与所使用的计算机无关的是（C）。A物理结构B存储结构C逻辑结构D逻辑和存储结构12. 下列 4 种基本逻辑结构中，数据元素之间关系最弱的是（A）。A集合B线性结构C树形结构D图形结构13. 与数据元素本身的形式、内容、相对位置、个数无关的是数据的（A）。A逻辑结构B存储结构C逻辑实现D存储实现14. 每一个存储结点只含有一个数据元素，存储结点存放在连续的存储空间，另外有一组指明结点存储位置的表，该存储方式是（C）存储方式。

7、A顺序B链式C索引D散列15. 算法能正确的实现预定功能的特性称为算法的（A）。A正确性B易读性C健壮性D高效性16. 算法在发生非法操作时可以作出相应处理的特性称为算法的（C）。A正确性B易读性C健壮性D高效性17. 下列时间复杂度中最坏的是（D）。AO（1）B.O（n）C.O( log2n)D.O(n2)18. 下列算法的时间复杂度是（D）。 for(i=0;in;i+) for(j=o;iprior-next=p-next；p-next-prior=p-prior20. 在如图所示的链表中，若在指针 P 所在的结点之后插入数据域值为 a 和 b 的两个结点，则可用语句 S-next-ne

8、xt=p-next 和 P- next=S；来实现该操作。LDCBApbas三、选择题1. 在具有 n 个结点的单向链表中，实现（ A）的操作，其算法的时间复杂度都是 O(n).A.遍历链表或求链表的第 i 个结点B.在地址为 P 的结点之后插入一个结点C.删除开始结点D.删除地址为 P 的结点的后继结点c20b10a2. 设 a、b、c 为 3 个结点，p、10、20 分别代表它们的地址，则如下的存储结构称为（ B ）。pA循环链表3.单向链表的存储密度（B单向链表C ）。C双向循环链表D双向链表A.大于 1B.等于 1C.小于 1D.不能确定4. 已知一个顺序存储的线性表，设每个结点占 m

9、 个存储单元，若第一个结点的地址为 B，则第 i 个结点的地址为（ A ）。A.B+(i-1)mB.B+imC.B-imD.B+(i+1)m5. 在有 n 个结点的顺序表上做插入、删除结点运算的时间复杂度为（B ）。AO（1）B.O（n）C. O(n2)D.O( log2n)6. 设 front、rear 分别为循环双向链表结点的左指针和右指针，则指针 P 所指的元素是双循环链表 L的尾元素的条件是（ D ）。A.P= =LB.P-front= =LC.P= =NULLD.P-rear= =L7. 两个指针 P 和 Q，分别指向单向链表的两个元素，P 所指元素是 Q 所指元素前驱的条件是（B

10、）AP-next= =Q-nextB.P-next= =QC.Q-next= =PD.P=Q8. 用链表存储的线性表，其优点是（C ）。 A 便 于 随机存取B花费的存储空间比顺序表少C便于插入和删除D数据元素的物理顺序与逻辑顺序相同9. 在单链表中，增加头结点的目的是（ C ）。A使单链表至少有一个结点 B标志表中首结点的位置C方便运算的实现D说明该单链表是线性表的链式存储结构10. 下面关于线性表的叙述中，错误的是（ D ）关系。A顺序表必须占一片地址连续的存储单元 B顺序表可以随机存取任一元素C链表不必占用一片地址连续的存储单元 D链表可以随机存取任一元素11. L 是线性表，已知 Le

11、ngthList(L)的值是 5，经 DelList(L，2)运算后，LengthList(L)的值是（ C ）。A2B3C4D512. 单向链表的示意图如下：PQR指向链表 Q 结点的前驱的指针是（ B ）。ALBPCQDR13. 设 p 为指向单循环链表上某结点的指针，则*p 的直接前驱（ C ）。A找不到B查找时间复杂度为 O（1） C查找时间复杂度为 O（n）D查找结点的次数约为 n14. 等概率情况下，在有 n 个结点的顺序表上做插入结点运算，需平均移动结点的数目为（ 8 ）。AnB.(n-1)/2C.n/2D.(n+1)/215. 在下列链表中不能从当前结点出发访问到其余各结点的是

12、（ C ）。A.双向链表B.单循环链表C.单向链表D.双向循环链表16. 在顺序表中，只要知道（ D ），就可以求出任一结点的存储地址。A.基地址B.结点大小C.向量大小D.基地址和结点大小17. 在双向链表中做插入运算的时间复杂度为（ A ）。AO（1）B.O（n）C. O(n2)D.O( log2n)18. 链表不具备的特点是（ A ）。A随机访问B.不必事先估计存储空间 C. 插入删除时不需要移动元素 D.所需空间与线性表成正比19. 以下关于线性表的论述，不正确的为（ C ）。A.线性表中的元素可以是数字、字符、记录等不同类型 B.线性顺序表中包含的元素个数不是任意的C. 线性表中的每

13、个结点都有且仅有一个直接前驱和一个直接后继D. 存在这样的线性表，即表中没有任何结点20. 在（ B ）的运算中，使用顺序表比链表好。A.插入B.根据序号查找C.删除D.根据元素查找第 3 章 栈一、判断题1. 栈是运算受限制的线性表。（）2. 在栈空的情况下，不能作出栈操作，否则产生下溢。（）3. 栈一定是顺序存储的线性结构。（）4. 栈的特点是“后进先出”。（）5. 空栈就是所有元素都为 0 的栈。（）6. 在 C（或 C+）语言中设顺序栈的长度为 MAXLEN，则 top=MAXLEN 时表示栈满。（）7. 链栈与顺序栈相比，其特点之一是通常不会出现栈满的情况。（）8. 一个栈的输入序列

14、为：A，B，C，D，可以得到输出序列：C，A，B，D。（）9. 递归定义就是循环定义。（）10. 将十进制数转换为二进制数是栈的典型应用之一。（）二、填空题1. 在栈结构中，允许插入、删除的一端称为 栈顶。2. 在顺序栈中，当栈顶指针 top=-1 时，表示 栈空。3. 在有 n 个元素的栈中，进栈操作时间复杂度为 O（1）。4. 在栈中，出栈操作时间复杂度为 O（1）。5. 已知表达式，求它的后缀表达式是 栈的典型应用。6. 在一个链栈中，若栈顶指针等于 NULL，则表示 栈空。7. 向一个栈顶指针为 top 的链栈插入一个新结点*p 时，应执行 p-next=top;top=p；操作。8.

15、 顺序栈 S 存储在数组 S-data0MAXLEN-1中，进栈操作时要执行的语句有：S-top+。(或 S-top+1)S-dataS-top=x9. 链栈 LS，指向栈顶元素的指针是 LS-next。10. 从一个栈删除元素时，首先取出 栈顶元素，然后再移动栈顶指针。11. 由于链栈的操作只在链表的头部进行，所以没有必要设置 头结点。12. 已知顺序栈 S，在对 S 进栈操作之前首先要判断 栈是否满。13. 已知顺序栈 S，在对 S 出栈操作之前首先要判断 栈是否空。14. 若内在空间充足， 链栈可以不定义栈满运算。15. 链栈 LS 为空的条件是 LS-next=NULL。16. 链栈

16、LS 的栈顶元素是链表的 首元素。17. 同一栈的各元素的类型 相同。18. 若进栈的次序是 A、B、C、D、E，执行 3 次出栈操作以后，栈顶元素为 B。19. A+B/C-D*E 的后缀表达式是 ABC/+DE*-。20. 4 个元素 A、B、C、D 顺序进 S 栈，执行两次 Pop(S,x)运算后，x 的值是 C。三、选择题1. 插入和删除操作只能在一端进行的线性表，称为（ C ）。A队列B循环队列C栈D循环栈2. 设有编号为 1，2。3，4 的 4 辆列车，顺序进入一个栈结构的站台，下列不可能的出站顺序为（ D）。A1234B1243C1324D14233. 如果以链表作为栈的存储结构

17、，则出栈操作时（ B ）。A必须判别栈是否满B必须判别栈是否为空C必须判别栈元素类型D栈可不做任何判别4. 元素 A、B、C、D 依次进栈以后，栈顶元素是（ D ）AABBCCDD5. 顺序栈存储空间的实现使用（ B ）存储元素。A链表B数组C循环链表D变量6. 在 C（或 C+）语言中，一个顺序栈一旦被声明，其占用空间的大小（ A ）。A已固定B不固定C可以改变D动态变化DCBAH7. 带头结点的链栈 LS 的示意图如下，栈顶元素是（A ）。LSAABBCCDD8. 链栈与顺序栈相比，有一个比较明显的优点是（B ）。A. 插入操作更加方便B.通常不会出现栈满的情况C.不会出现栈空的情况D.删

18、除操作更加方便9. 从一个栈顶指针为 top 的链栈中删除一个结点时，用 x 保存被删除的结点，应执行下列（d）命令。Ax=top;top-next;B.top=top-next;x=top-data C.x=top-data;D.x=top-data;top=top-next10. 在一个栈顶指针为 HS 的链栈中，将一个 S 指针所指的结点入栈，应执行下列（B ）命令。A.HS-next=SB.S-next=HS-next;HS-next=S; C.S-next=HS-next;HS=S;D.S-next=HS=HS-next11. 4 元素按 A、B、C、D 顺序进 S 栈，执行两次 P

19、op(S，x)运算后，栈顶元素的值是（B ）。AABBCCDD12. 元素 A、B、C、D 依次进栈以后，栈底元素是（ A ）。A.A BBCCDD13. 经过下列栈的运算后，再执行 ReadTop(s)的值是（A ）。InitStack(s);Push(s，a); Push(s，b);Pob(s);A. aB.bC.1D.014. 经过下列栈的运算后，x 的值是（ B ）。InitStack(s)（初始化栈）; Push(s，a); Push(s，b); ReadTop(s) ；Pob(s，x);A. aB.bC.1D.015. 经过下列栈的运算后，x 的值是（B ）。InitStack(s

20、)（初始化栈）; Push(s,a); Pob(s，x); Push(s,b); Pob(s，x);A.aB.bC.1D.016. 经过下列栈的运算后,SEmpty(s)的值是（C ）。InitStack(s)（初始化栈）; Push(s,a); Push(s,b); Pob(s，x); Pob(s，x);A.aB.bC.1D.017. 向顺序栈中输入元素时（ B ）。A先存入元素，后移动栈顶指针B先移动栈顶指针，后存入元素C谁先谁后无关紧要D同时进行18. 初始化一个空间大小为 5 的顺序栈 S 后，S-top 的值是（ B ）。A0B-1C不再改变D动态变化19. 设有一个入栈的次序 A、

21、B、C、D、E，则栈不可能的输出序列是（C ）。AEDCBABDECBACDCEABDABCDE20. 设有一个顺序栈 S，元素 A、B、C、D、E、F 依次进栈，如果 6 个元素出栈的顺序是B、D、C、F、E、A，则栈的容量至少应是（ A ）。A3B4C5D6第 4 章 队 列一、判断题1. 队列是限制在两端进行操作的线性表。（）2. 判断顺序队列为空的标准是头指针和尾指针都指向同一个结点。（）3. 在链队列上做出队操作时，会改变 front 指针的值。（）4. 在循环队列中，若尾指针 rear 大于头指针 front，其元素个数为 rear-front。（）5. 在单向循环链表中，若头指针

22、为 h，那么 p 所指结点为尾结点的条件是 p=h。（）6. 链队列在一定范围内不会出现队满的情况。（）7. 在循环链队列中无溢出现象。（）8. 栈和队列都是顺序存储的线性结构。（）9. 在队列中允许删除的一端称为队尾。（）10. 顺序队和循环队关于队满和队空的判断条件是一样的。（）二、填空题1. 在队列中存取数据应遵循的原则是 先进先出。2. 队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算线性表。3. 在队列中，允许插入的一端称为 队尾。4. 在队列中，允许删除的一端称为 队首（或队头） 。5. 队列在进行出队操作时，首先要判断队列是否为 空。6. 顺序队列在进行入队操作

23、时，首先在判断队列是否为 满。7. 顺序队列初始化后，初始化后，front=rear= -1。8. 解决顺序队列“假溢出”的方法是采用 循环队列。9. 循环队列的队指针为 front，队尾指针为 rear，则队空的条件为 front= =rear。10. 链队列 LQ 为空时，LQ-front-next= NULL。11. 设长度为 n 的链队列用单循环表表示，若只设头指针，则入队操作的时间复杂度为 O(n)。12. 设长度为 n 的链队列用单循环表表示，若只设尾指针，则入队操作的时间复杂度为 O(1)。13. 在一个链队列中，若队首指针与队尾指针的值相同，则表示该队列为 空。14. 设循环队

24、列的头指针 front 指向队首元素，尾指针 rear 指向队尾元素后的一个空闲元素，队列的最大空间为 MAXLEN，则队满标志为 front= =(rear+1)%MAXLEN 。15. 在一个链队列中，若队首指针为 front，队尾指针为 rear，则判断队列只有一个结点的条件为front= =rear 或 front!。16. 向一个循环队列中插入元素时，首先要判断 队尾指针 ，然后再向指针所指的位置写入新的数据。17. 读队首元素的操作 不改变或不影响队列元素的个数。18. 设循环队列的容量为 40（序号 039），现经过一系列的入队和出队的运算后， front=11，rear=19，则循环队列中还有 8个元素。19. 队列 Q，经过下列运算：InitQueue(Q)(初始化队列)；InQueue(Q,a)；InQueue(Q,b)；OutQueue(Q,x)； ReadFront(Q,x)；QEmpty(Q)；后的值是 8。20. 队列 Q 经过 InitQueue(Q)(初始化队列)；InQueue(Q,a)；InQueue(Q,b)；ReadFront(Q,x)后，x 的值是 a。三、选择题1. 队列是限定在（