〔√〕4. 顺序存储方式的优点是存储密度大，插入、删除效率高 〔×〕5. 线性链表的删除算法简单，因为当删除链中某个结点后，计算时机自动地将后续的各个单元向前移动 〔×〕6. 顺序表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型 〔×〕7. 线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素 〔√〕8. 线性表采用顺序存储，必须占用一片连续的存储单元 〔√〕9. 顺序表结构适宜进行顺序存取，而链表适宜进行随机存取 〔×〕10. 插入和删除操作是数据结构中是最根本的两种操作，所以这两种操作在数组中也经常使用〔×〕二、填空题1. 顺序表中逻辑上相邻的元素在物理位置上必须相邻2. 线性表中结点的集合是有限的，结点间的关系是一对一关系3. 顺序表相对于链表的优点是节省存储和随机存取4. 链表相对于顺序表的优点是插入、删除方便。
5. 当线性表的元素总数根本稳定，且很少进行插入和删除操作，但要求以最快速度存取线性表中的元素时，应采用 顺序 存储结构6. 顺序表中访问任意一个结点的时间复杂度均为O〔1〕7. 链表相对于顺序表的优点是插入、删除方便；缺点是存储密度小8. 在双向链表中要删除结点*P，其时间复杂度为O〔1〕9. 在单向链表中要在结点*P之前插入一个新结点，需找到*P的直接前驱结点的地址，其查找的时间复杂度为O(n)10. 在单向链表中需知道头指针才能遍历整个链表11. 线性表中第一个结点没有直接前驱，称为开始结点12. 在一个长度为n的顺序表中删除第i个元素，要移动 n-i 个元素13. 在一个长度为n的顺序表中，如果要在第i个元素前插入一个元素，要后移 n-i+1 个元素14. 在无头结点的单向链表中，第一个结点的地址存放在头指针中，而其他结点的存储地址存放在 前趋 结点的指针域中15. 线性表的元素总数不确定，且经常需要进行插入和删除操作，应采用 链子 存储结构16. 性表中的链式存储中，元素之间的逻辑关系是通过 指针 决定。
17. 在双向链表中，每个结点都有两个指针域，它们一个指向其 前趋 结点，另一个指向其后继结点18. 对一个需要经常进行插入和删除操作的线性表，采用 链式 存储结构为宜19. 双向链表中，设P是指向其中待删除的结点，那么需要执行的操作为p->prior->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. 在具有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.不能确定4. 一个顺序存储的线性表，设每个结点占m个存储单元，假设第一个结点的地址为B，那么第i个结点的地址为〔 A 〕A.B+(i-1)×m B.B+i×m C.B-i×m D.B+(i+1)×m5. 在有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= =L7. 两个指针P和Q，分别指向单向链表的两个元素，P所指元素是Q所指元素前驱的条件是〔 B 〕 A．P->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．说明该单链表是线性表的链式存储结构10. 下面关于线性表的表达中，错误的选项是〔 D 〕关系 A．顺序表必须占一片地址连续的存储单元B．顺序表可以随机存取任一元素C．链表不必占用一片地址连续的存储单元D．链表可以随机存取任一元素11. L是线性表，LengthList(L)的值是5，经DelList(L，2)运算后，LengthList(L)的值是〔 C 〕。
A．2 B．3 C．4 D．512. 单向链表的示意图如下： L A B C D ∧ P Q R指向链表Q结点的前驱的指针是〔 B 〕A．L B．P C．Q D．R13. 设p为指向单循环链表上某结点的指针，那么*p的直接前驱〔 C 〕A．找不到 B．查找时间复杂度为O〔1〕 C．查找时间复杂度为O〔n〕D．查找结点的次数约为n14. 等概率情况下，在有n个结点的顺序表上做插入结点运算，需平均移动结点的数目为〔 8 〕A．n B.(n-1)/2 C.n/2 D.(n+1)/215. 在以下链表中不能从当前结点出发访问到其余各结点的是〔 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. 插入删除时不需要移动元素 D.所需空间与线性表成正比19. 以下关于线性表的论述，不正确的为〔 C 〕A.线性表中的元素可以是数字、字符、记录等不同类型B.线性顺序表中包含的元素个数不是任意的C.线性表中的每个结点都有且仅有一个直接前驱和一个直接后继D.存在这样的线性表，即表中没有任何结点20. 在〔 B 〕的运算中，使用顺序表比链表好A.插入 B.根据序号查找 C.删除 D.根据元素查找第3章 栈一、 判断题1. 栈是运算受限制的线性表。
〔√〕2. 在栈空的情况下，不能作出栈操作，否那么产生下溢 〔√〕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时，表示 栈空 3. 在有n个元素的栈中，进栈操作时间复杂度为 O〔1〕 4. 在栈中，出栈操作时间复杂度为 O〔1〕 5. 表达式，求它的后缀表达式是 栈 的典型应用6. 在一个链栈中，假设栈顶指针等于NULL，那么表示 栈空 7. 向一个栈顶指针为top的链栈插入一个新结点*p时，应执行p->next=top;top=p；操作8. 顺序栈S存储在数组S->data[0…MAXLEN-1]中，进栈操作时要执行的语句有：S->top++或S->top+1)S->data[S->top]=x9. 链栈LS，指向栈顶元素的指针是LS->next10. 从一个栈删除元素时，首先取出 栈顶元素 ，然后再移动栈顶指针。
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. 4个元素A、B、C、D顺序进S栈，执行两次Pop(S,x)运算后，x的值是 C 三、选择题1. 插入和删除操作只能在一端进行的线性表，称为〔 C 〕A．队列 B．循环队列 C．栈 D．循环栈2. 设有编号为1，23，4的4辆列车，顺序进入一个栈结构的站台，以下不可能的出站顺序为〔 D〕。
A．1234 B．1243 C．1324 D．14233. 如果以链表作为栈的存储结构，那么出栈操作时〔 B 〕A．必须判别栈是否满 B．必须判别栈是否为空 C．必须判别栈元素类型 D．栈可不做任何判别4. 元素A、B、C、D依次进栈以后，栈顶元素是〔 D 〕A．A B．B C．C D．D5. 顺序栈存储空间的实现使用〔 B 〕存储元素A．链表 B．数组 C．循环链表 D．变量6. 在C〔或C++〕语言中，一个顺序栈一旦被声明，其占用空间的大小〔 A 〕A．已固定 B．不固定 C．可以改变 D．动态变化7. 带头结点的链栈LS的示意图如下，栈顶元素是〔 A 〕LSH A B C D ∧A．A B．B C．C D．D8. 链栈与顺序栈相比，有一个比拟明显的优点是〔 B 〕。
A. 插入操作更加方便 B.通常不会出现栈满的情况 C.不会出现栈空的情况 D.删除操作更加方便9. 从一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点，应执行以下〔d 〕命令A．x=top;top->next; 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 〕A．A B．B C．C D．D12. 元素A、B、C、D依次进栈以后，栈底元素是〔 A 〕。
A．A B．B C．C D．D13. 经过以下栈的运算后，再执行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 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 〕A．0 B．-1 C．不再改变 D．动态变化19. 设有一个入栈的次序A、B、C、D、E，那么栈不可能的输出序列是〔 C 〕A．EDCBA B．DECBA C．DCEAB D．ABCDE20. 设有一个顺序栈S，元素A、B、C、D、E、F依次进栈，如果6个元素出栈的顺序是B、D、C、F、E、A，那么栈的容量至少应是〔 A 〕A．3 B．4 C．5 D．6第4章 队列一、判断题1. 队列是限制在两端进行操作的线性表。
〔√〕2. 判断顺序队列为空的标准是头指针和尾指针都指向同一个结点 〔√〕3. 在链队列上做出队操作时，会改变front指针的值 〔×〕4. 在循环队列中，假设尾指针rear大于头指针front，其元素个数为rear-front 〔√〕5. 在单向循环链表中，假设头指针为h，那么p所指结点为尾结点的条件是p=h 〔×〕6. 链队列在一定范围内不会出现队满的情况 〔√〕7. 在循环链队列中无溢出现象 〔×〕8. 栈和队列都是顺序存储的线性结构 〔×〕9. 在队列中允许删除的一端称为队尾 〔×〕10. 顺序队和循环队关于队满和队空的判断条件是一样的。
〔×〕二、填空题1. 在队列中存取数据应遵循的原那么是 先进先出 2. 队列 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算线性表3. 在队列中，允许插入的一端称为 队尾 4. 在队列中，允许删除的一端称为 队首〔或队头〕 5. 队列在进行出队操作时，首先要判断队列是否为 空 6. 顺序队列在进行入队操作时，首先在判断队列是否为 满 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. 设循环队列的头指针front指向队首元素，尾指针rear指向队尾元素后的一个空闲元素，队列的最大空间为MAXLEN，那么队满标志为 front= =(rear+1)%MAXLEN 15. 在一个链队列中，假设队首指针为front，队尾指针为rear，那么判断队列只有一个结点的条件为front= =rear或front!16. 向一个循环队列中插入元素时，首先要判断 队尾指针 ，然后再向指针所指的位置写入新的数据17. 读队首元素的操作 不改变或不影响队列元素的个数18. 设循环队列的容量为40〔序号0～39〕，现经过一系列的入队和出队的运算后，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. 队列是限定在〔D〕进行操作的线性表A．中间者 B.队首 C.队尾 D.端点2. 队列中的元素个数是〔B〕A．不变的 B.可变的 C.任意的 D.03. 同一队列内的各元素的类型〔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.0～10 B.0～9 C.1～9 D.1～109. 假设进队的序列为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〕A．A B．B C．C D．D11. 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，经过以下运算后，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->front H A B C D ∧ LQ->rear A．A B．B C．C D．D 17. 带头结点的链队列LQ示意图如下，指向链队列的队头指针是〔C〕LQ->frontH A B C D ∧LQ->rearA.LQ->front B.LQ->rear C.LQ->front->next D.LQ->rear->next18. 带头结点的链队列LQ示意图如下,在进行进队的运算时指针LQ->frnot(A).LQ->frontH A B C D ∧ LQ->rear A.始终不改变 B.有时改变 C.进队时改变 D.出队时改变19.队列Q，经过以下运算后，再执行QEmpty(Q)的值是〔C〕。
InitQueue(Q)(初始化队列)；InQueue(Q,a)；InQueue(Q,b)；OutQueue(Q,x)；ReadQueue(Q,x)；A.a B.b C.0 D.120.假设用一个大小为6数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再参加两个元素后，front和rear的值分别为〔B〕A.5和1 B.4和2 C.2和4 D.1和5第5章 串一、判断题1. 串是n个字母的有限序列 〔×〕2. 串的数据元素是一个字符 〔√〕3. 串的长度是指串中不同字符的个数 〔×〕4. 如果两个串含有相同的字符，那么说明它们相等。
〔×〕5. 如果一个串中所有的字母均在另一个串中出现，那么说明前者是后者的子串 〔×〕6. 串的堆分配存储是一种动态存储结构 〔√〕7. “DT〞是“DATA〞的子串 〔×〕8. 串中任意个字符组成的子序列称为该串的子串 〔×〕9. 子串的定位运算称为模式匹配 〔√〕10. 在链串中为了提高存储密度，应该增大结点的大小 〔√〕二、填空题1. 由零个或多个字符组成的有限序列称为 字符串〔或串〕 2. 字符串按存储方式可以分为顺序存储、链接存储和 堆分配存储 3. 串的顺序存储结构简称为 顺序串 。
4. 串顺序存储非紧凑格式的缺点是 空间利用率低 5. 串顺序存储紧凑格式的缺点是对串的字符处理 效率低 6. 串链接存储的优点是插入、删除方便，缺点是 空间利用率 7. 在C或C++语言中，以字符 \0 表示串值的终结8. 空格串的长度等于 空格的个数 9. 在空串和空格串中，长度不为0的是 空格串 10. 两个串相等是指两个串长度相等，且对应位置的 字符都相同 11. 设“S=My Music〞，那么LenStr(s)= 8 12. 两个字符串分别为；S1=〞Today is〞、S2=〞30 July，2005〞，ConcatStr(S1，S2)的结果是 Today is 30 July,2005 13. 求子串函数SubStr(“Today is 30 July，2005〞，13，4)的结果是 July 14. 在串的运算中，EqualStr(aaa,aab)的返回值 <0 15. 在串的运算中，EqualStr(aaa,aaa)的返回值 0 16. 在子串的定位运算中，被匹配的主串称为目标串，子串称为 模式 。
17. 模式匹配成功的起始位置称为 有效位移 18. 设S=〞abccdcdccbaa〞，T=〞cdcc〞，那么第 6 次匹配成功19. 设S=〞c:/mydocument/text1.doc〞，T=〞mydont〞，那么字符定位的位置为 0 20. 假设n为主串长度，m为子串长度，n>>m，那么模式匹配算法最坏情况下的时间复杂度为 (n-m+1)*m 三、选择题 1. 串是和种特殊的线性表，其特殊表达在〔B〕A．可能顺序存储 B．数据元素是一个字符C．可以链接存储 D．数据元素可以是多个字符2. 某串的长度小于一常数，那么采用〔B〕存储方式最节省空间A．链式 B．顺序 C．堆结构 D．无法确定3. 以下论述正确的选项是〔C〕A．空串与空格串是相同的B．〞tel〞是〞Teleptone〞的子串C．空串是零个字符的串 D．空串的长度等于14. 以下论述正确的选项是〔B〕A．空串与空格串是相同的B．〞ton〞是〞Teleptone〞的子串C．空格串是有空格的串 D．空串的长度等于15. 以下论断正确的选项是〔A〕。
A．全部由空格组成的串是空格串 B．〞BEUIJING〞是〞BEI JING〞的子串C．〞something〞<〞Something〞 D．〞BIT〞=〞BITE〞6. 设有两个串S1和S2，那么EqualStr〔S1，S2〕运算称作〔D〕A．串连接 B．模式匹配 C．求子串 D．串比拟7. 串的模式匹配是指〔D〕A．判断两个串是否相等 B．对两个串比拟大小C．找某字符在主串中第一次出现的位置D．找某子串在主串中第一次出现的第一个字符位置8. 假设字符串〞ABCDEFG〞采用链式存储，假设每个字符占用1个字节，每个指针占用2个字节那么该字符串的存储密度为〔D〕A．20% B．40% C．50% D．33.3%9. 假设字符串〞ABCDEFG〞采用链式存储，假设每个指针占用2个字节，假设希望存储密度为50%，那么每个结点应存储〔A〕个字符A.2 B.3 C.4 D.510. 设串S1=〞IAM〞，S2=〞A SDUDENT〞，那么ConcatStr(S1，S2)=〔B〕。
A．〞I AM〞 B.〞I AM A SDUDENT〞 C.〞IAMASDUDENT〞 D.〞A SDUDENT〞11. 设S=〞〞，那么LenStr(S)=〔A〕A.0 B.1 C.2 D.312. 设目标串T=〞AABBCCDDE〞，模式P=〞ABCDE〞，那么该模式匹配的有效位移为〔A〕A.0 B.1 C.2 D.313. 设目标串T=〞AABBCCDDEEFF〞，模式P=〞CCD〞，那么该模式匹配的有效位移为〔D〕A.2 B.3 C.4 D.514. 设目标串T=〞aabaababaabaa〞，模式P=〞abab〞，模式匹配算法的外层循环进行了〔D〕次A.1 B.9 C.4 D.515. 模式匹配算法在最坏情况下的时间复杂是〔D〕。
A.O(m) B.O(n) C.O(m+n) D.O(m×n)16. S=〞morning〞,执行求子串函数SubSur(S,2,2)后结果为〔B〕A. 〞mo〞 B. 〞or〞 C. 〞in〞 D. 〞ng〞17. S1=〞good〞，S2〞morning〞，执行串连接函数ConcatStr(S1，S2)后结果为〔A〕A. 〞goodmorning〞 B. 〞good morning〞 C. 〞GOODMORNING〞 D. 〞GOODMORNING〞18. S1=〞good〞, S2=〞morning〞执行函数SubSur(S2,4,LenStr(S1))后的结果为〔B〕A.〞good〞 B.〞ning〞 C.〞go〞 D.〞morn〞19. 设串S1=〞ABCDEFG〞，S2=〞PQRST〞，那么ConcatStr〔SubStr(S1，2，LenStr〔S2〕〕，SubStr(S1，LenStr〔S2〕，2〕〕的结果串为〔D。