数据结构练习题（一）

数据结构练习题（一）习题1 绪论1.1 单项选择题1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的 C 、数据信息在计算机中的 A 以及一组相关的运算等的课程。 A操作对象计算方法逻辑结构数据映象 A存储结构 关系 运算 算法2. 在数据结构中，从逻辑上可以把数据结构分成 C 。A动态结构和静态结构 紧凑结构和非紧凑结构 线性结构和非线性结构 内部结构和外部结构3. 算法分析的目的是 C ，算法分析的两个主要方面是 A 。 A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 A. 空间复杂性和时间复杂性 B. 正确性和简明性C. 可读性和文档性 D. 数据复杂性和程序复杂性4. 计算机算法指的是 C ，它必具备输入、输出和 B 等五个特性。 A. 计算方法 B. 排序方法C. 解决问题的有限运算序列 D. 调度方法 A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性5. 数据结构主要研究数据的（B ） 。 A 逻辑结构 B 存储结构 C 逻辑结构和存储结构 D 逻辑结构和存储结构及起运算的实现6. 为了描述 n 个人之间的同学关系，可用 _( C)_ 结构表示。 A 线性表 B 树 C 图 D 队列7. 数据表示是指数据 (B ) 。 A 书写在纸上 B 从机外转为机内C 磁盘中的数据 D 光盘中的数据 8. 数据元素是数据的基本单位，其内 ( C) 数据项。A 只能包括一个 B 不包含 C 可以包含多个 D 必须包含多个 9. 逻辑关系是指数据元素间的 ( C) 。A 类型 B 存储方式 C 结构 D 数据项 10. 逻辑结构是 (A ) 关系的整体A 数据元素之间逻辑 B 数据项之间逻辑 C 数据类型之间 D 存储结构之间 11.下列四种基本的逻辑结构中，数据元素之间关系最弱的是 ( A) 。A 集合 B 线性结构 C 树形结构 D 图状结构 12. 一个存储结点存放一个 ( B) 。A 数据项 B 数据元素 C 数据结构 D 数据类型 13. 用类 C 语言描写的算法 ( B) 。A 可以直接在计算机上运行 B 可以描述解题思想和基本框架C 不能改写成 C 语言程序 D 与 C 语言无关 14. 算法能正确地实现预定功能的特性称为 ( A) 。A 正确性 B 易读性 C 健壮 D 高效率 15. 下列时间复杂度中最坏的是 ( D) 。A O(1) B O(n) C O(log2n) D O(n2) 16.下列时间复杂度中最好的是 ( A) 。A O(1) B O(n) C O(log2n) D O(n2) 17. 下列算法的时间复杂度是 ( D) 。 for （ i=0 ； in ； i+ ） for （ j=0 ； jn ； j+ ） cij=i+j A O(1) B O(n) C O(log2n) D O(n2) 18. 下列算法的时间复杂度是 (B ) 。 for （ i=0 ； inext= =NULLC. head-next= =head D. head!=NULL8. 带头结点的单链表head为空的判定条件是_ B _。A. head= =NULL B. head-next= =NULLC. head-next= =head D. head!=NULL9. 非空的循环单链表head的尾结点（由p所指向）满足_ C _。A. p-next= =NULL B. p= =NULLC. p-next= =head D. p= =head 10. 在一个单链表中，已知q 所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行_ B _。A. s-next=p-next; p-next=s; B. p-next=s-next; s-next=p;B. q-next=s; s-next=p; C. p-next=s; s-next=q;11. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行_ B _。A. s-next=p; p-next=s; B. s-next=p-next; p-next=s;C. s-next=p-next; p=s; C. p-next=s; s-next=p;12. 在一个单链表中，若删除p所指结点的后续结点，则执行_ A _。A. p-next= p-next-next； B. p= p-next; p-next= p-next-next；C. p-next= p-next; D. p= p-next-next； 13. 下列说法正确的是 (B ) 。 A 线性表的逻辑顺序与存储顺序总是一致的 B 线性表链式存储结构中，内存中可用的存储单元可以是连续的，也可以不连续 C 线性表顺序存储结构优于链式存储结构 D 每种数据结构都具有插入、删除和查找三种基本运算 14.L 是线性表，已知 ListLength(L) 的值是 5 ，运算 DeleteList （ L ， 2 ）后 ListLength （ L ）的值是 ( C) 。 A 5 B 0 C 4 D 6 15. 线性表中哪些元素只有一个直接前驱和一个直接后继 ( C) 。A 首元素 B 尾元素 C 中间元素 D 所有的元素 16. 线性表中各元素之间的关系是 ( C) 关系。A 层次 B 网状 C 有序 D 集合 17. 在单链表的一个结点中有 ( A) 个指针。A 1 B 2 C 3 D 4 18. 在双向链表的一个结点中有 ( B) 个指针。A 1 B 2 C 0 D 3 19.P 和 q 两个指针分别指向双向循环链表 L 两个元素， p 所指元素是 q 所指元素的后继的条件是 ( B) 。 A p =q B q-next=p C p-next=q D q-next=p-next 20. 两指针 p 和 q ，分别指向单链表的两个元素， p 所指元素是 q 所指元素的前驱的条件是 ( A) 。 A p -next=q B q-next=p C p=q D p-next=null 21.在长度为 n 的顺序表的第 i （ 1 i n+1 ）各位置上插入一个元素，元素的移动次数为 ( A) 。 A n-i+1 B n-i C i D i-1 22.设非空单链表的数据字段为 data ，指针字段为 next ，指针 p 指向单链表中第 i 个结点， s 指向已生成的新结点，现将 s 结点插入到单链表中，使其成为第 i+1 个结点，下列算法段能正确完成上述要求的是 (A ) 。A s-next=p-next；p-next =s ；B p-next=s ； s-next=p-next ；C s-next=p-next ； p-next=s ；交换 p-data 和 s-data ；D p=s ； s-next=p 23. 线性表压缩存储的主要目的是 ( B ) 。A 方便运算 B 节省存储空间 C 降低计算复杂度 D 提高运算速度24. 链表不具备的特点是 ( A )。A 可随机访问任何一个元素 B 插入、删除操作不需要移动元素C 无需事先估计存储空间大小 D 所需存储空间与线性表长度成正比 25.向一个长度为n的线性表的第i个元素（1in+1）之前插入一个元素时，需向后移动( B )个元素。A n-i B n-i+1 C n-i-1 D n-(i+1)2.2 填空题（将正确的答案填在相应的空中）1. 在双链表中，每个结点有两个指针域，一个指向_前驱结点_ _，另一个指向 后继结点_ _。2. 在一个单链表中删除p所指结点的后继结点时，应执行以下操作：q= p-next;p-next= _q-next _; /填空free（ q ） ; /填空3. 向一个长度为n的线性表中删除第i个元素（1in）时，需向前移动_ n-i _个元素。习题3 栈和队列3.1 单项选择题1. 一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是_ C _。 A. edcba B. decba C. dceab D. abcde 2. 若已知一个栈的入栈序列是1，2，3，n，其输出序列为p1，p2，p3，pn，若p1=n，则pi为_ C _。 A. i B. n=i C. n-i+1 D. 不确定3. 栈结构通常采用的两种存储结构是_ A _。A. 顺序存储结构和链式存储结构散列方式和索引方式链表存储结构和数组线性存储结构和非线性存储结构4. 判定一个顺序栈ST（最多元素为m0）为空的条件是_ B _。A. top !=0 B. top= =0 C. top !=m0 D. top= =m0-15. 判定一个顺序栈ST（最多元素为m0）为栈满的条件是_ D _。A. top！=0 B. top= =0 C. top！=m0 D. top= =m0-16. PUSH 和 POP 命令常用于（ C）操作。 A 队列 B 数组 C 栈 D 记录 7. 向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行_ C _。(不带空的头结点)HSnext=s;B. snext= HSnext; HSnext=s;C. snext= HS; HS=s;D. snext= HS; HS= HSnext;8. 从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行_ B _ _。(不带空的头结点) A. x=HS; HS= HSnext; B. x=HSdata;C. HS= HSnext; x=HSdata; D. x=HSdata; HS= HSnext;9. 一个队列的数据入队序列是1，2，3，4，则队列出队时的输出序列是_ B _ 。 A. 4，3，2，1 B. 1，2，3，4 C. 1，4，3，2 D. 3，2，4，110. 判定一个循环队列QU（最多元素为m0）为空的条件是_ C _。A. rear - front= =m0 B. rear-front-1= =m0C. front= = rear D. front= = rear+111. 栈和队列的共同点是_ C _。A. 都是先进后出 B. 都是先进先出C. 只允许在端点处插入和删除元素 D. 没有共同点12. 栈是将插入或删除操作限定在( )处进行的线性表 (C )。 A 端点 B 栈底 C 栈顶 D 中间 13. 在栈顶一端可进行的全部操作是( C)。A 插入 B 删除 C 插入和删除 D 进栈 14. 4个元素按A、B、C、D、顺序连续进S栈，进行Pop（S，x）元素后，x的值是 ( D) 。A A B B C C D D 15. 栈的特点是( B) 。A 先进先出 B 后进先出 C 后进后出 D 不进不出 16.栈结构的元素个数是( B)。A 不变的 B 可变的 C 任意的 D 0 17. 4个元素进S栈的顺序是A、B、C、D，进行两次Pop（S，x）操作后，栈顶元素的值是( B) 。A A B B C C D D 18. 同一个栈内各元素的类型 ( A）。A 必须一致 B 可以不一致 C 不能一致 D 不必不一致 19. 顺序栈存储空间的实现使用 (B ）。A 链表 B 数组 C 循环链表 D 变量 20.一个顺序栈一旦说明，其占用空间的大小 ( A）。A 已固定 B 可以改变 C 不能固定 D 动态变化 21.栈是一个线性表结构 ( B）。A 不加限制的 B 加了限制的 C 推广了的 D 非 22. 栈与一般线性表区别主要在方面 ( D) 。A 元素个数 B 元素类型 C 逻辑结构 D 插入、删除元素的位置 23.顺序栈是空栈的条件是 ( C）。A top=0 B top=1 C top=-1 D top=m 24. 元素A、B、C、D依次进顺序栈后，栈顶元素是 ( D）。A A B B C C D D 25.队列的特点是。(A)A 先进先出 B 后进先出 C 先进后出 D 不进不出3.2 填空题（将正确的答案填在相应的空中）1. 线性表、栈和队列都是_线性_结构，可以在线性表的_任何_位置插入和删除元素；对于栈只能在_栈顶_插入和删除元素；对于队列只能在_队