1、 1 第 1章 绪论 一、 判断题 1. 数据的逻辑结构与数据元素本身的内容和形式无关。 （ ） 2. 一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。 （ ） 3. 数据元素是数据的最小单位。 （ ） 4. 数据的逻辑结构和数据的存储结构是相同的。 （ ） 5. 程序和算法原则上没有区别，所以在讨论数据结 构时可以通用。 （ ） 6. 从逻辑关系上讲，数据结构主要分 为线性结构和非线性结构两类。 （ ） 7. 数据的存储结构是数据的逻辑结构的存储 映象 。 （ ） 8. 数据的物理结构是指数据在计算机内实际的存储形式。 （ ） 9. 数据的逻辑结构是依赖于计算机的。
2、（ ） 10. 算法是对解题方法和步骤的描述。 （ ） 二、填空题 1. 数据有逻辑结构和 存储结构 两种结构。 2. 数据逻辑结构除了集合以外，还包括线性结构、树形结构和 图形结构 。 3. 数据结构按逻辑结构可分为两大类，它们是线性结构和 非线性结构 。 4. 树形结构 和 图形结构 合称为非线性结构。 5. 在树形结构中，除了树根结点以外，其余每个结点只有 1 个前驱结点。 6. 在图形结构中，每个结点的前驱结点数和后继结点数可以 任意多个 。 7. 数据的存储结构又叫 物理结构 。 8. 数据的存储结构形式包括顺序存储、链式存储、索引存储和 散列存储 。 9. 线性结构中的元素之间存在
3、 一对一 的关系。 10. 树形结构中的元素之间存在 一对多 的关系。 11. 图形结构的元素之间存在 多对多 的关系。 12. 数据结构主要研究数据的逻辑结构 、 存储结构和 算法（或运算） 3 个方面的内容。 13. 数据结构被定义为（ D， R），其中 D 是数据的有限集合， R 是 D 上 的 关系 有限集合。 14. 算法是一个 有穷指令 的集合。 15. 算法效率的度量可以分为事先估算法和 事后统计法 。 16. 一个算法的时间复杂 度是算法 输入规模 的函数。 17. 算法 的 空间复杂度是指该算法所耗费的 存储空间 ，它是该算法求解问题规模的 n 的函数。 18. 若一个算法中
4、的语句频度之和为 T(n)=6n+3nlog2n,则算法的时间复杂度为 O（ nlog2n） 。 19. 若一个算法的语句频度之和为 T(n)=3n+nlog2+n2,则算法的时间复杂度为 O（ n2） 。 20. 数据结构是一门研究非数值计算的程序问题中计算机的 操作对象 ， 以及它们之间的关系和运算的学科。 三、选择题 2 1. 数据结构通常是研究数据的（ A）及它们之间的相互关系。 A存储结构和逻辑结构 B存储和抽象 C联系和抽象 D联系与逻辑 2. 在逻辑上可以把数据结构分成（ C）。 A动态结构和静态结构 B 紧凑结构和非紧凑结构 C 线性结构和非线性结构 D 内部结构和外部结构。
5、3. 数据在计算机存储内表示时，物理地址和逻辑地址相同并且是连续的，称之为（ C）。 A存储结构 B 逻辑结构 C 顺序存储结构 D 链式存储结构 4. 非线性结构中的每个结点（ D）。 A无直接前驱结点 B 无直接后继结点 C只有一个直接前驱结 点和一个直接后继结点 D 可能有多个直接前驱结点和多个直接后继结点 5. 链式存储结构所占存储空间（ A）。 A分两部分，一部分存放结点的值，另一个部分存放表示结点间关系的指针。 B只有一部分，存放结点的值。 C 只有一部分，存储表示结点间关系的指针。 D分两部分，一部分存放结点的值，另一部分存放结点所占单元素 6. 算法的计算量大小称为算法的（ C
6、）。 A现实性 B 难度 C 时间复杂性 D 效率 7. 数据的基本单位（ B）。 A数据结构 B 数据元素 C 数据项 D 文件 8. 每个结点只含有一个数据元素，所有存储结点相继存放在一个连续的存储空间里，这种存储结构 称为（ A）结构。 A顺序结构 B 链式结构 C 索引结构 D 散列结构 9. 每一个 存储 结点 不仅 含有一个数据元素，还包含一组指针，该存储方式是（ B）。 A顺序 B 链式 C 索引 D 散列 10. 以下任何两个结点之间都没有逻辑关系的是（ D）。 3 A图形结构 B 线性结构 C 树形结构 D 集合 11. 在数据结构中，与所使用的计算机无关的是（ C）。 A
7、物理 结构 B 存储结构 C 逻辑结构 D 逻辑和存储结构 12. 下列 4 种基本逻辑结构中，数据元素之间关系最弱的是（ A）。 A集合 B 线性结构 C 树形结构 D 图形结构 13. 与数据元素 本身的形式、内容、相对位置、个数无关的是数据 的 （ A）。 A逻辑结构 B 存储结构 C 逻辑实现 D 存储实现 14. 每一个存储结点只含有一个数据元素，存储结点存放在连续的存储空间，另外有一组指明结点存储位置的表，该存储方式是（ C）存储方式。 A顺序 B 链式 C 索引 D 散列 15. 算法能正确的实现预定功能的特性称为算法的（ A）。 A正确性 B 易读性 C 健壮性 D 高效性 1
8、6. 算法在发生非法操作时可以作出相应处理的特性称为算法的（ C）。 A正确性 B 易读性 C 健壮性 D 高效性 17. 下列时间复杂度中最坏的是（ D）。 A O（ 1） B.O（ n） C.O( log2n) D.O(n2) 18. 下列算法的时间复杂度是（ D）。 for(i=0;iprior-next=p-next；p-next-prior=p-prior 20. 在如图所示的链表中，若在指针 P 所在的结点之后插入数据域值为 a 和 b 的两个结点，则可用语句 S-next-next=p-next 和 P- next=S；来实现该操作。 p a b s 三、 选择题 1. 在具有
9、n 个结点的单向链表中，实现（ A）的操作，其算法的时间复杂度都是 O(n). A.遍历链表或求链表的第 i 个结点 B.在地址为 P 的结点之后插入一个结点 C.删除开始结点 D.删除地址为 P 的结点的后继结点 2. 设 a、 b、 c 为 3 个结点， p、 10、 20 分别代表它们的地址，则如下的存储结构称为（ B ）。 p a 10 b 20 c A循环链表 B单向链表 C双向循环链表 D双向链表 3. 单向链表的存储密度（ C ）。 A.大于 1 B.等于 1 C.小于 1 D.不能确定 7 4. 已知一个顺序存储的线性表，设每个结点占 m 个存 储单元，若第一个结点的地址为 B
10、，则第 i 个结点的地址为（ A ）。 A.B+(i-1) m B.B+i m C.B-i m D.B+(i+1) m 5. 在有 n 个结点的顺序表上做插入、删除结点运算的时间复杂度为（ B ）。 A O（ 1） B.O（ n） C. O(n2) D.O( log2n) 6. 设 front、 rear分别为循环双向链表结点的左指针和右指针，则指针 P所指 的元素是双循环链表 L的尾元素的条件是（ D ）。 A.P= =L B.P-front= =L C.P= =NULL D.P-rear= =L 7. 两个指针 P 和 Q，分别指向单向链表的两个元素， P 所指元素是 Q 所指元素前驱的条
11、件是（ B ） A P-next= =Q-next B.P-next= =Q C.Q-next= =P D.P=Q 8. 用链表存储的线性表，其优点是（ C ）。 A便于 随机存取 B花费的存储空间比顺序表少 C便于插入和删除 D数据元素的物理顺序与逻辑顺序 相同 9. 在单链表中，增加头结点的目的是（ C ）。 A使单链表至少有一个结点 B标志表中首结点的位置 C方便运算的实现 D说明该单链表是线性表的链式存储结构 10. 下面关于线性表的叙述中，错误的是（ D ）关系。 A顺序表必须占一片地址连续的存储单元 B顺序表可以随机存取任一元素 C链表不必占用一片地址连续的存储单元 D链表可以随机
12、存取任一元素 11. L是线 性表，已知 LengthList(L)的值是 5，经 DelList(L， 2)运算后， LengthList(L)的值是（ C ）。 A 2 B 3 C 4 D 5 12. 单向链表的示意图如下： L A B C D 8 P Q R 指向链表 Q 结点的前驱的指针是（ B ）。 A L B P C Q D R 13. 设 p 为指向单循环链表上某结点的指针，则 *p 的直接前驱（ C ）。 A找不到 B查找时间复杂度为 O（ 1） C查找时间复杂度为 O（ n） D查找结点的次数约为 n 14. 等概率情况下，在有 n 个结点 的顺序表上做插入结点运算，需平均移
13、动结点的数目为 （ 8 ）。 A n B.(n-1)/2 C.n/2 D.(n+1)/2 15. 在下列链表中不能从当前结点出发访问到其余各结点的是（ C ）。 A.双向链表 B.单循环链表 C.单向链表 D.双向循环链表 16. 在顺序表中，只要知道（ D ），就可以求出任一结点的存储地址。 A.基地址 B.结点大小 C.向量大小 D.基 地址和结点大 小 17. 在双向链表中做插入运算的时间复杂度为（ A ）。 A O（ 1） B.O（ n） C. O(n2) D.O( log2n) 18. 链表不具备的特点是（ A ）。 A随机访问 B.不必事先估计存储空间 C. 插入删除时不需要移动元
14、素 D.所需空间与线性表成正比 19. 以下关于线性表的论述，不正确的为（ C ）。 A.线性表中的元素可以是数字 、字符、记录等不同类型 B.线性顺序表中包含的元素个数不是任意的 C.线性表中的每个结点都有且仅有一个直接前驱和一个直接后继 D.存在这样的线性表，即表中没有任何结点 20. 在（ B ）的运算中，使用顺序表比链表好。 A.插入 B.根据序号查找 C.删除 D.根据元素查找 9 第 3 章 栈 一、 判断题 1. 栈是运算受限制的线性表。 （ ） 2. 在栈空的情况 下，不能作出栈操作，否则产生下溢。 （ ） 3. 栈一定是顺序存储的线性结构。 （ ） 4. 栈的特点是“后进先出
15、”。 （ ） 5. 空栈就是所有元素都为 0 的栈。 （ ） 6. 在 C（或 C+）语言中设顺序栈的长度为 MAXLEN，则 top=MAXLEN 时表示栈满。 （ ） 7. 链栈与顺序栈相比，其特点之一是通常不会出现栈满的情况。 （ ） 8. 一个栈的输入序列为： A， B， C， D，可以得到输出序列： C， A， B， D。 （ ） 9. 递归定义就是循环定义。 （ ） 10. 将十进制数转换为二进制数是栈的典型应用之一。 （ ） 二、填空题 1. 在栈结构中，允许插入、删除的一端称为 栈顶 。 2. 在顺序栈中，当栈顶指针 top=-1 时，表示 栈空 。 3. 在有 n 个元素的栈
16、中，进栈操作时间复杂度为 O（ 1） 。 4. 在栈中，出栈操作时间复杂度为 O（ 1） 。 5. 已知表达式，求它的后缀表达式是 栈 的典型应用。 6. 在一个链栈中，若栈顶指针等于 NULL，则表示 栈空 。 7. 向一个栈顶指针为 top 的链栈插入一个新结点 *p 时，应执行 p-next=top;top=p；操作。 8. 顺序栈 S 存储在数组 S-data0 MAXLEN-1中，进栈操作时要执行的语句有： S-top+。 (或S-top+1) S-dataS-top=x 9. 链栈 LS，指向栈顶元素的指针是 LS-next。 10. 从一个栈删除元素时，首先取出 栈顶元素 ，然后
17、再移动栈顶指针。 11. 由于链栈的操作只在链表的头部进行，所以没有必要设置 头 结点 。 12. 已知顺序栈 S，在对 S 进栈操作之前首先要判断 栈是否满 。 13. 已知顺序栈 S，在对 S 出栈操作之前首先要判断 栈是否空 。 14. 若内在空间充足， 链 栈可以不定义栈满运算。 15. 链栈 LS 为空的条件是 LS-next=NULL 。 16. 链栈 LS 的栈顶元素是链表的 首 元素。 17. 同一栈的各元素的类型 相同 。 18. 若进栈的次序是 A、 B、 C、 D、 E，执行 3 次出栈操作以后，栈顶元素为 B 。 19. A+B/C-D*E 的后缀表达式是 ABC/+D
18、E*- 。 20. 4 个元素 A、 B、 C、 D 顺序进 S 栈，执行两次 Pop(S,x)运算后， x 的值是 C 。 10 三、选择题 1. 插入和删除操作只能在一端进行的线性表，称为（ C ）。 A队列 B循环队列 C栈 D循环栈 2. 设有编号为 1， 2。 3， 4 的 4 辆列车，顺序进入一个栈结构的站台，下列不可能 的 出站顺序为（ D）。 A 1234 B 1243 C 1324 D 1423 3. 如果以链表作 为栈的存储结构，则出栈操作 时 （ B ）。 A必须判别栈是否满 B必须判别栈是否为空 C必须判别栈元素类型 D栈可不做任何判别 4. 元素 A、 B、 C、 D
19、 依次进栈以后，栈顶元素是（ D ） A A B B C C D D 5. 顺序栈存储空间的实现使用（ B ）存储元素。 A链表 B数组 C循环链表 D变量 6. 在 C（或 C+）语言中，一 个顺序栈一旦被声明，其占用空间的大小（ A ）。 A已固定 B不固定 C可以改变 D动态变化 7. 带头结点的链栈 LS 的示意图如下，栈 顶 元素是（ A ） 。 LS H A B C D A A B B C C D D 8. 链栈与顺序 栈 相比，有一个比较明显 的优点是（ B ）。 A. 插入操作更加方便 B.通常不会出现栈满的情况 C.不会出现栈空的情况 D.删除操作更加方便 9. 从一个栈顶指
20、针为 top 的链栈中删除一个结点时，用 x 保存被删除的结点，应执行下列（ d ）命令。 A x=top;top-next; B.top=top-next;x=top-data C.x=top-data; D.x=top-data;top=top-next 10. 在一个栈顶指针 为 HS 的链栈中，将一个 S 指针所指的结点入 栈，应执行下列（ B ）命令。 A.HS-next=S B.S-next=HS-next;HS-next=S; C.S-next=HS-next;HS=S; D.S-next=HS=HS-next 11. 4 元素按 A、 B、 C、 D 顺序进 S 栈，执行两次 Pop(S， x)运算后，栈顶元素的值是（ B ）。 A A B B C C D D 12. 元素 A、 B、 C、 D 依次进栈以后，栈底元素是（ A ）。 A A B B C C D D 13. 经过下列栈的运算后，再执行 ReadTop(s)的值是（ A ）。 InitStack(s);Push(s， a); Push(s， b);Pob(s);
