1、1第 1 章 绪论一、 判断题1. 数据的逻辑结构与数据元素本身的内容和形式无关。 （）2. 一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。 （）3. 数据元素是数据的最小单位。 （）4. 数据的逻辑结构和数据的存储结构是相同的。 （）5. 程序和算法原则上没有区别，所以在讨论数据结构时可以通用。 （）6. 从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。 （）7. 数据的存储结构是数据的逻辑结构的存储映象。 （）8. 数据的物理结构是指数据在计算机内实际的存储形式。 （）9. 数据的逻辑结构是依赖于计算机的。 （）10. 算法是对解题方法和步骤的描述。 （
2、）二、填空题1. 数据有逻辑结构和 存储结构 两种结构。2. 数据逻辑结构除了集合以外，还包括线性结构、树形结构和图形结构 。3. 数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构 。4. 树形结构 和图形结构 合称为非线性结构。5. 在树形结构中，除了树根结点以外，其余每个结点只有 1 个前驱结点。6. 在图形结构中，每个结点的前驱结点数和后继结点数可以任意多个 。7. 数据的存储结构又叫物理结构 。8. 数据的存储结构形式包括顺序存储、链式存储、索引存储和散列存储 。9. 线性结构中的元素之间存在一对一 的关系。10. 树形结构中的元素之间存在一对多 的关系。11. 图形结构的元
3、素之间存在多对多 的关系。12. 数据结构主要研究数据的逻辑结构、存储结构和算法（或运算） 3 个方面的内容。13. 数据结构被定义为（D，R） ，其中 D 是数据的有限集合，R 是 D 上的关系 有限集合。14. 算法是一个有穷指令 的集合。15. 算法效率的度量可以分为事先估算法和事后统计法 。16. 一个算法的时间复杂度是算法 输入规模 的函数。17. 算法的空间复杂度是指该算法所耗费的存储空间 ，它是该算法求解问题规模的 n 的函数。18. 若一个算法中的语句频度之和为 T(n)=6n+3nlog2n,则算法的时间复杂度为 O（ nlog 2n） 。19. 若一个算法的语句频度之和为
4、T(n)=3n+nlog2+n2,则算法的时间复杂度为 O（n 2） 。20. 数据结构是一门研究非数值计算的程序问题中计算机的操作对象，以及它们之间的关系和运算的学科。三、选择题1. 数据结构通常是研究数据的（A）及它们之间的相互关系。A存储结构和逻辑结构 B存储和抽象 C联系和抽象 D联系与逻辑2. 在逻辑上可以把数据结构分成（C） 。A动态结构和静态结构 B紧凑结构和非紧凑结构C线性结构和非线性结构 D内部结构和外部结构。3. 数据在计算机存储内表示时，物理地址和逻辑地址相同并且是连续的，称之为（C） 。A存储结构 B逻辑结构 C顺序存储结构 D链式存储结构4. 非线性结构中的每个结点（
5、D） 。A无直接前驱结点 B无直接后继结点2C只有一个直接前驱结点和一个直接后继结点 D可能有多个直接前驱结点和多个直接后继结点5. 链式存储结构所占存储空间（A） 。A分两部分，一部分存放结点的值，另一个部分存放表示结点间关系的指针。B只有一部分，存放结点的值。 C只有一部分，存储表示结点间关系的指针。D分两部分，一部分存放结点的值，另一部分存放结点所占单元素6. 算法的计算量大小称为算法的（C） 。A现实性 B难度 C时间复杂性 D效率7. 数据的基本单位（B） 。A数据结构 B数据元素 C数据项 D文件8. 每个结点只含有一个数据元素，所有存储结点相继存放在一个连续的存储空间里，这种存储
6、结构称为（A）结构。A顺序结构 B链式结构 C索引结构 D散列结构9. 每一个存储结点不仅含有一个数据元素，还包含一组指针，该存储方式是（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逻辑实
7、现 D存储实现14. 每一个存储结点只含有一个数据元素，存储结点存放在连续的存储空间，另外有一组指明结点存储位置的表，该存储方式是（C）存储方式。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( log 2n) D.O(n2)18. 下列算法的时间复杂度是（D） 。for(i=0;iprior-next=p-next；p-next-p
8、rior=p-prior 20. 在如图所示的链表中，若在指针 P 所在的结点之后插入数据域值为 a 和 b 的两个结点，则可用语句 S-next-next=p-next 和 P- next=S；来实现该操作。4pa b s三、 选择题1. 在具有 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循
9、环链表 B单向链表 C双向循环链表 D双向链表3. 单向链表的存储密度（ C ） 。A.大于 1 B.等于 1 C.小于 1 D.不能确定4. 已知一个顺序存储的线性表，设每个结点占 m 个存储单元，若第一个结点的地址为 B，则第 i 个结点的地址为（ A ） 。A.B+(i-1)m B.B+im C.B-im D.B+(i+1)m5. 在有 n 个结点的顺序表上做插入、删除结点运算的时间复杂度为（ B ） 。AO（1） B.O（n） C. O(n 2) D.O( log2n)6. 设 front、rear 分别为循环双向链表结点的左指针和右指针，则指针 P 所指的元素是双循环链表 L的尾元素
10、的条件是（ D ） 。A.P= =L B.P-front= =L C.P= =NULL D.P-rear= =L7. 两个指针 P 和 Q，分别指向单向链表的两个元素，P 所指元素是 Q 所指元素前驱的条件是（ B ） AP-next= =Q-next B.P-next= =Q C.Q-next= =P D.P=Q8. 用链表存储的线性表，其优点是（ C ） 。A便于随机存取 B花费的存储空间比顺序表少C便于插入和删除 D数据元素的物理顺序与逻辑顺序相同9. 在单链表中，增加头结点的目的是（ C ） 。A使单链表至少有一个结点 B标志表中首结点的位置C方便运算的实现 D说明该单链表是线性表的链
11、式存储结构10. 下面关于线性表的叙述中，错误的是（ D ）关系。A顺序表必须占一片地址连续的存储单元 B顺序表可以随机存取任一元素C链表不必占用一片地址连续的存储单元 D链表可以随机存取任一元素11. L 是线性表，已知 LengthList(L)的值是 5，经 DelList(L，2)运算后，LengthList(L)的值是（ C ） 。A2 B3 C4 D512. 单向链表的示意图如下：LA B C D 5P Q R指向链表 Q 结点的前驱的指针是（ B ） 。AL BP CQ DR13. 设 p 为指向单循环链表上某结点的指针，则*p 的直接前驱（ C ） 。A找不到 B查找时间复杂度
12、为 O（1） C查找时间复杂度为 O（n）D查找结点的次数约为 n14. 等概率情况下，在有 n 个结点的顺序表上做插入结点运算，需平均移动结点的数目为（ 8 ） 。An B.(n-1)/2 C.n/2 D.(n+1)/215. 在下列链表中不能从当前结点出发访问到其余各结点的是（ C ） 。A.双向链表 B.单循环链表 C.单向链表 D.双向循环链表16. 在顺序表中，只要知道（ D ） ，就可以求出任一结点的存储地址。A.基地址 B.结点大小 C.向量大小 D.基地址和结点大小17. 在双向链表中做插入运算的时间复杂度为（ A ） 。AO（1） B.O（n） C. O(n 2) D.O(
13、log2n)18. 链表不具备的特点是（ A ） 。A随机访问 B.不必事先估计存储空间 C. 插入删除时不需要移动元素 D.所需空间与线性表成正比19. 以下关于线性表的论述，不正确的为（ C ） 。A.线性表中的元素可以是数字、字符、记录等不同类型 B.线性顺序表中包含的元素个数不是任意的C.线性表中的每个结点都有且仅有一个直接前驱和一个直接后继D.存在这样的线性表，即表中没有任何结点20. 在（ B ）的运算中，使用顺序表比链表好。A.插入 B.根据序号查找 C.删除 D.根据元素查找6第 3 章 栈一、 判断题1. 栈是运算受限制的线性表。 （）2. 在栈空的情况下，不能作出栈操作，否
14、则产生下溢。 （）3. 栈一定是顺序存储的线性结构。 （）4. 栈的特点是“后进先出” 。 （）5. 空栈就是所有元素都为 0 的栈。 （）6. 在 C（或 C+）语言中设顺序栈的长度为 MAXLEN，则 top=MAXLEN 时表示栈满。 （）7. 链栈与顺序栈相比，其特点之一是通常不会出现栈满的情况。 （）8. 一个栈的输入序列为：A，B，C，D，可以得到输出序列：C，A，B，D。 （）9. 递归定义就是循环定义。 （）10. 将十进制数转换为二进制数是栈的典型应用之一。 （）二、填空题1. 在栈结构中，允许插入、删除的一端称为 栈顶 。2. 在顺序栈中，当栈顶指针 top=-1 时，表示
15、 栈空 。3. 在有 n 个元素的栈中，进栈操作时间复杂度为 O（1） 。4. 在栈中，出栈操作时间复杂度为 O（1） 。5. 已知表达式，求它的后缀表达式是 栈 的典型应用。6. 在一个链栈中，若栈顶指针等于 NULL，则表示 栈空 。7. 向一个栈顶指针为 top 的链栈插入一个新结点*p 时，应执行 p-next=top;top=p；操作。8. 顺序栈 S 存储在数组 S-data0MAXLEN-1中，进栈操作时要执行的语句有：S-top+。(或 S-top+1)S-dataS-top=x9. 链栈 LS，指向栈顶元素的指针是 LS-next。10. 从一个栈删除元素时，首先取出 栈顶元
16、素 ，然后再移动栈顶指针。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/+DE*- 。20.
17、4 个元素 A、B、C、D 顺序进 S 栈，执行两次 Pop(S,x)运算后，x 的值是 C 。三、选择题1. 插入和删除操作只能在一端进行的线性表，称为（ C ） 。A队列 B循环队列 C栈 D循环栈2. 设有编号为 1，2。3，4 的 4 辆列车，顺序进入一个栈结构的站台，下列不可能的出站顺序为（ D） 。A1234 B1243 C1324 D14233. 如果以链表作为栈的存储结构，则出栈操作时（ B ） 。A必须判别栈是否满 B必须判别栈是否为空 C必须判别栈元素类型 D栈可不做任何判别4. 元素 A、B、C、D 依次进栈以后，栈顶元素是（ D ）7AA BB CC DD5. 顺序栈存
18、储空间的实现使用（ B ）存储元素。A链表 B数组 C循环链表 D变量6. 在 C（或 C+）语言中，一个顺序栈一旦被声明，其占用空间的大小（ A ） 。A已固定 B不固定 C可以改变 D动态变化7. 带头结点的链栈 LS 的示意图如下，栈顶元素是（ A ） 。LSH A B C D AA BB CC DD8. 链栈与顺序栈相比，有一个比较明显的优点是（ B ） 。A. 插入操作更加方便 B.通常不会出现栈满的情况 C.不会出现栈空的情况 D.删除操作更加方便9. 从一个栈顶指针为 top 的链栈中删除一个结点时，用 x 保存被删除的结点，应执行下列（d ）命令。Ax=top;top-next
19、; B.top=top-next;x=top-dataC.x=top-data; D.x=top-data;top=top-next10. 在一个栈顶指针为 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-next11. 4 元素按 A、B、C、D 顺序进 S 栈，执行两次 Pop(S，x)运算后，栈顶元素的值是（ B ） 。AA BB CC DD12. 元素 A、B、C、D 依次进栈以后，栈底元素是（ A ） 。A
20、A BB CC DD13. 经过下列栈的运算后，再执行 ReadTop(s)的值是（ A ） 。InitStack(s);Push(s，a); Push(s，b);Pob(s);A. a B.b C.1 D.014. 经过下列栈的运算后，x 的值是（ B ） 。InitStack(s)（初始化栈）; Push(s，a); Push(s，b); ReadTop(s) ；Pob(s，x);A. a B.b C.1 D.015. 经过下列栈的运算后，x 的值是（ B ） 。InitStack(s)（初始化栈）; Push(s,a); Pob(s，x); Push(s,b); Pob(s，x);A.a
21、 B.b C.1 D.016. 经过下列栈的运算后,SEmpty(s)的值是（ C ） 。InitStack(s)（初始化栈）; Push(s,a); Push(s,b); Pob(s，x); Pob(s，x);A.a B.b C.1 D.017. 向顺序栈中输入元素时（ B ） 。A先存入元素，后移动栈顶指针 B先移动栈顶指针，后存入元素C谁先谁后无关紧要 D同时进行18. 初始化一个空间大小为 5 的顺序栈 S 后，S-top 的值是（ B ） 。A0 B-1 C不再改变 D动态变化19. 设有一个入栈的次序 A、B、C、D、E，则栈不可能的输出序列是（ C ） 。AEDCBA BDECB
22、A CDCEAB DABCDE20. 设有一个顺序栈 S，元素 A、B、C、D、E、F 依次进栈，如果 6 个元素出栈的顺序是8B、D、C、F、E、A，则栈的容量至少应是（ A ） 。A3 B4 C5 D69第 4 章 队列一、判断题1. 队列是限制在两端进行操作的线性表。 （）2. 判断顺序队列为空的标准是头指针和尾指针都指向同一个结点。 （）3. 在链队列上做出队操作时，会改变 front 指针的值。 （）4. 在循环队列中，若尾指针 rear 大于头指针 front，其元素个数为 rear-front。 （）5. 在单向循环链表中，若头指针为 h，那么 p 所指结点为尾结点的条件是 p=
23、h。 （）6. 链队列在一定范围内不会出现队满的情况。 （）7. 在循环链队列中无溢出现象。 （）8. 栈和队列都是顺序存储的线性结构。 （）9. 在队列中允许删除的一端称为队尾。 （）10. 顺序队和循环队关于队满和队空的判断条件是一样的。 （）二、填空题1. 在队列中存取数据应遵循的原则是 先进先出 。2. 队列 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算线性表。3. 在队列中，允许插入的一端称为 队尾 。4. 在队列中，允许删除的一端称为 队首（或队头） 。5. 队列在进行出队操作时，首先要判断队列是否为 空 。6. 顺序队列在进行入队操作时，首先在判断队列是否为 满
24、 。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. 设循环队列的头指针
25、front 指向队首元素，尾指针 rear 指向队尾元素后的一个空闲元素，队列的最大空间为 MAXLEN，则队满标志为 front= =(rear+1)%MAXLEN 。15. 在一个链队列中，若队首指针为 front，队尾指针为 rear，则判断队列只有一个结点的条件为front= =rear 或 front!。16. 向一个循环队列中插入元素时，首先要判断 队尾指针 ，然后再向指针所指的位置写入新的数据。17. 读队首元素的操作 不改变或不影响队列元素的个数。18. 设循环队列的容量为 40（序号 039） ，现经过一系列的入队和出队的运算后，front=11，rear=19，则循环队列中
26、还有 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. 队列是限定在（D）进行操作的线性表。A中间者 B.队首 C.队尾 D.端点2. 队列中的元素个数是（B） 。A不变的 B.可变的 C.任意的 D.0103. 同一队列内的各元素的类型
27、（A） 。A.必须一致 B.不能一致 C.可以不一致 D.不限制4. 队列是一个（C）线性表结构。A.不加限制的 B.推广了的 C.加了限制的 D.非5. 当利用大小为 n 的数组顺序存储一个队列时，该队列的最后一个元素的下标为（B） 。A.n-2 B.n-1 C.n D.n+16. 一个循环队列一旦说明，其占用空间的大小（A） 。A.已固定 B.可以变动 C.不能固定 D.动态变化7. 循环队列占用的空间（A） 。A.必须连续 B.不必连续 C.不能连续 D.可以不连续8. 存放循环队列元素的数组 data 有 10 个元素，则 data 数组的下标范围是（B） 。A.010 B.09 C.
28、19 D.1109. 若进队的序列为 A、B、C、D，则出队的序列是（C） 。A.B、C、D、A B.A、C、B、D C.A、B、C、D D.C、B、D、A10. 4 个元素按 A、B、C、D 顺序连续进队 Q，则队尾元素是（D）AA BB CC DD11. 4 个元素按 A、B、C、D 顺序连续进队 Q，执行一次 QutQueue(Q)操作后，队头元素是（B） 。A.A B.B C.C D.D12. 4 个元素按 A、B、C、D 顺序连续进队 Q，执行 4 次 QutQueue(Q)操作后，再执行 QEmpty(Q)；后的值是（B） 。A.0 B.1 C.2 D.313. 队列 Q，经过下列
29、运算后，x 的值是（B） 。InitQueue(Q)(初始化队列)；InQueue(Q,a)；InQueue(Q,b)；OutQueue(Q,x)；ReadFront(Q,x)；A.a B.b C.0 D.114. 循环队列 SQ 队满的条件是（B） 。A.SQ-rear= =SQ-front B.(SQ-rear+1)%MAXLEN= =SQ-frontC.SQ-rear= =0 D.SQ-front= =015. 设链栈中结点的结构：data 为数据域，next 为指针域，且 top 是栈顶指针，若想在链栈的栈顶插入一个由指针 s 所指的结点，则应执行下列（A）操作。A.s-next=top-next;top-next=s; B.top-next=s;C.s-next=top;top-next; D.s-next=top;top=s;16. 带头结点的链队 LQ 示意图如下，链队列的队头元素是（A） 。LQ-frontH A B C D LQ-rearAA BB CC DD 17. 带头结点的链队列 LQ 示意图如下，指向链队列的队头指针是（C） 。LQ-frontH A B C D
