描涣帝韦椿碳攘围筐活桶沥哪
第1章 绪论 第1章 绪论 测验
1、 ___不是算法的基本特性。
答案: 长度有限
2、 计算机中算法指的是解决某一问题的有限运算序列，它必须具备输入、输出、__。
答案: 可行性、有穷性和确定性
3、 一个算法具有__等设计目标。
答案: 健壮性
4、 以下关于算法的说法正确的是_
答案: 以上几个都是错误的
5、 算法的时间复杂度与__有关。
答案: 问题规模
6、 算法的主要任务之一是分析____。
答案: 算法的执行时间和问题规模之间的关系
7、 某算法的时间复杂度为O(n^2)，表明该算法的_
答案: 执行时间与n^2成正比
8、 算法分析的目的是_
答案: 分析算法的效率以求改进
9、 以下说法中错误的是(1）原地工作算法的含义是指不需要任何额外的辅助空间(2)在相同的问题规模n下，时间复杂度为O(nlogan)的算法在执行时间上总是优于时i复杂度为O(n2)的算法(3）时间复杂度通常是指最坏情况下，估计算法执行时间的一个上限(4)一个算法的时间复杂度与实现算法的语言无关
答案: （1)、(2)
10、 数据结构在计算机内存中的表示是指_
答案: 数据的存储结构
第2章 线性表 第2章 线性表 测验
1、 线性表是() 。
答案: 一个有限序列，可以为空
2、 以下关于顺序表的叙述中，正确的是（) 。
答案: 顺序表和一维数组一样，都可以进行随机存取
3、 顺序表具有随机存取特性，指的是( ) 。
答案: 查找序号为i的元素与顺序表中元素个数n无关
4、 一个顺序表所占用存储空间的大小与()无关。
答案: 顺序表中各元素的存放次序
5、 设一个顺序表L(最多可存放100个元素）目前有20个元素，第i (1≤is20）个元素存放在L.data[i-1]中，现删除L.data[5]的元素而不做元素移动，则()。
答案: L.data[0]~L.data[19]不构成一个顺序表
6、 设一个顺序表L(最多可存放100个元素)目前有3个元素，第i (1si<3）个元素存放在L.data[i-1]中，若把一个新元素存入L.data[5]，则() 。
答案: L.data[0] ~L.data[5]不构成一个顺序表
7、 下面关于线性表的叙述中，错误的是哪一个?( )
答案: 线性表采用顺序存储，便于进行插入和删除操作。
8、 线性表的顺序存储结构是一种() 。
答案: 随机存取的存储结构
9、 线性表是具有n个()的有限序列。
答案: 数据元素
10、 线性表有一个特点( ）。
答案: 若没有开始元素，则一定没有终端元素
11、 关于线性表的正确说法是()。
答案: 除第一个元素和最后一个元素外，其余每个元素有且仅有一个前趋和一个后继元素
12、 在长度为n的顺序表中插入一个元素的时间复杂度为
答案: O(n)
13、 在长度为n的顺序表中删除一个元素的时间复杂度为
答案: O(n)
14、 将两个各有n个元素的递增有序顺序表归并成一个有序顺序表,其最少的比较次数是
答案: n
15、 将两个长度分别为n,m 的递增有序顺序表归并成一个递增有序顺序表,其最少的比较次数是(MIN表示取最小值)。
答案: MIN(m,n)
16、 将两个长度分别为n,m 的递增有序顺序表归并成一个递增有序顺序表,最多的比较次数是
答案: n+m-1
17、 带头结点的单链表L为空的判定条件是
答案: L->next==NULL
18、 对于一个具有n个元素的线性表,建立其单链表的时间复杂度为
答案: O(n)
19、 在单链表中查找指定值的结点的时间复杂度是
答案: O(n)
20、 以下关于单链表的叙述中,不正确的是
答案: 可以通过头结点直接计算第i个结点的存储地址
21、 在单链表中,增加一个头结点的目的是为了
答案: 方便运算的实现
22、 在一个具有n个结点的有序单链表中插人一个新结点并仍然保持有序的时间复杂度是____。
答案: O(n)
23、 将长度为n的单链表链接在长度为m 的单链表之后的算法的时间复杂度是
答案: O(m)
24、 已知一个长度为n的单链表中所有结点值不同并且是递增有序的,以下叙述中正确的是
答案: 找最小值结点的算法的时间复杂度为O(1)
25、 在一个长度为n(n>1)的带头结点的单链表h上,另设有尾指针r(指向尾结点),执行 操作与链表的长度有关。
答案: 删除单链表中的尾结点
26、 在一个双链表中,在结点p(非尾结点)之后插入结点q的操作语句是
答案: q->next=p-> next;p->next-> prior=q; p->next=q;q-> prior=p;
27、 在一个双链表中,删除结点p(非尾结点)的操作语句是
答案: p-> prior->next=p->next; p-> next-> prior=p-> prior
28、 在一个双链表中,删除结点p之后的一个结点(删除的结点为非尾结点)的操作语句是__。
答案: p->next=p->next->next; p->next-> prior= p;
29、 非空的循环单链表L的尾结点(由p所指向)满足
答案: p->next==L
30、 某线性表最常用的操作是在尾元素之后插人一个元素和删除尾元素,采用 存储方式最节省运算时间。
答案: 循环双链表
31、 线性表中每个元素都有一个前驱元素和一个后继元素。
答案: 错误
分析：开始元素没有前驱元素,终端元素没有后继元素。
32、 线性表中所有元素的排列顺序必须由小到大或由大到小。
答案: 错误
分析：线性表中所有元素是一个序列(与位置有关),但元素值并不一定是有序的。
33、 静态链表既有顺序存储结构的优点,又有动态链表的优点,所以,利用它存取表中第i个元素的时间与元素个数n无关。
答案: 错误
分析：由于静态链表具有链表的基本特点,存取表中第i个元素时也是从头开始查找的,所以其时间复杂度为O(n)。
34、 线性表的顺序存储结构优于链式存储结构。
答案: 错误
分析：线性表的顺序存储结构和链式存储结构各有优缺点。
35、 在循环单链表中,从表中任一结点出发都可以通过前后移动操作遍历整个循环链表。
答案: 错误
分析：循环单链表只能向后移动指针,到达尾结点后再回到头结点。
36、 在单链表中,可以从头结点开始查找任何一个结点。
答案: 正确
37、 在双链表中,可以从任一结点开始沿同一方向查找到任何其他结点。
答案: 错误
分析：循环双链表可以,但非循环双链表不能。
38、 顺序存储结构只能用于存放线性表。
答案: 错误
分析：栈和队列等也可以采用顺序存储结构。
39、 线性表的逻辑顺序总与其物理顺序一致。
答案: 错误
分析：当线性表采用链式存储结构时,其逻辑顺序与物理顺序可能不一致。
40、 单链表不具有随机存取特性,而双链表具有随机存取特性。
答案: 错误
分析：单链表和双链表都不具有随机存取特性。
41、 在单链表中,要删除某一指定的结点,必须先找到该结点的 结点
答案: 前驱
42、 求一个单链表长度的算法的时间复杂度为 。
答案: O(n)
43、 删除单链表L中某结点p之后的一个结点,算法时间复杂度为 。
答案: O(1)
44、 为了设置一个空的顺序表L,采用的操作是 。
答案: L.length=0
45、 删除顺序表的 元素,不需要移动任何元素。
答案: 最后一个
46、 删除顺序表的 元素,需要移动的元素最多。
答案: 第一个
47、 在顺序表 元素后面插入一个元素,不需要移动任何元素。
答案: 最后一个
48、 插入顺序表的 元素,需要移动的元素最多。
答案: 第一个
49、 在长度为n的顺序表L中查找指定元素值的元素,其时间复杂度为 。
答案: O(n)
50、 删除双链表L中某结点p之后一个结点,其时间复杂度为 。
答案: O(1)
第3章 栈和队列 单元测试–栈
1、 一个栈的进栈序列是a ,b、c ,d 、e ,则栈不可能输出的序列是
答案: dceab
2、 已知一个栈的进栈序列是(1,2,3,…,n),其输出序列的第一个元素是i(1≤in),则第j(1≤jn)个出栈元素是
答案: 不确定
3、 已知一个栈的进栈序列是(1,2，3，…,n),其输出序列是p1,p2，…, pn,若p1=n,则pi的值为
答案: n-i+1
4、 设n个元素的进栈序列是(p1,p2 , p3 ,…,pn),其输出序列是(1,2,3,… , n)，若pn=1,则pi(1≤in—1)的值是
答案: n-i+1
5、 设n个元素进栈序列是(1,2,3,…,n),其输出序列是( p1, p2，…,pn),若p1=3,则pi的值为
答案: 不可能是1
6、 设n个元素的进栈序列是(p1,p2,p3 ,…, pn),其输出序列是(1,2,3,…, n)，若P3=1,则p1的值
答案: 不可能是2
7、 设n个元素进栈序列是(p1,p2,p3，…,pn),其输出序列是(1,2,3,…, n),若p3=3,则p1的值
答案: 可能是2
8、 设有5个元素的进栈序列是(a,b,c,d,e)，其输出序列是(c,e,d ,b,a),则该栈的容量至少是
答案: 4
9、 判定一个顺序栈st(元素个数最多为MaxSize)为空的条件为
答案: st.top==-1
10、 判定一个顺序栈st(元素个数最多为MaxSize)为栈满的条件是
答案: st.top==MaxSize-1
11、 表达式a(b＋c)-d的后缀表达式是
答案: a b c＋ * d-
12、 表达式(a+a * b) a十c * b/a的后缀表达式是
答案: a a b +a * c b* a/+
13、 若一个栈用数组data[1..n]存储,初始栈顶指针 top为n十1,则元素x进栈的正确操作是
答案: top–; data[top]=x;
14、 若一个栈用数组data[1..n]存储,初始栈顶指针top为n,则元素x进栈的正确操作是
答案: data[top]=x; top–
15、 若一个栈用数组data[1..n]存储,初始栈顶指针top为o,则元素x进栈的正确操作是
答案: top＋+;data[top]=x;
16、 若一个栈用数组data[1..n]存储,初始栈顶指针 top为1,则元素α进栈的正确操作是
答案: data[ top]=x; top+＋;
17、 链栈与顺序栈相比有一个明显的优点,即
答案: 通常不会出现栈满的情况
18、 以下各链表均不带有头结点,其中最不适合用作链栈的存储结构的链表是
答案: 只有表头指针没有表尾指针的循环单链表
19、 如果以链表作为栈的存储结构,则退栈操作时
答案: 必须判断链栈是否空
20、 向一个不带头结点的单链表lst表示的链栈中插入一个s所指结点时,应执行
答案: s->next=lst; lst=s;
21、 从一个不带头结点的单链表 Ist表示的链栈中删除一个结点,用α保存被删结点的值,应执行 。
答案: x=lst-> data; lst=lst->next
22、 从一个不带头结点的单链表Ist表示的链栈中删除一个结点,用α保存被删结点的值,应执行
答案: x=lst->data; lst=lst->next;
23、 栈底元素是不能删除的元素。
答案: 错误
24、 顺序栈中元素值的大小是有序的。
答案: 错误
25、 n个不同元素通过一个栈,它们的出栈顺序和进栈顺序一定正好相反。
答案: 错误
26、 栈顶元素和栈底元素有可能是同一个元素。
答案: 正确
27、 若用s[0,m-1]表示顺序栈的存储空间,则对栈的进栈,出栈操作最多只能进行m次。
答案: 错误
28、 栈是一种对进栈、出栈操作总次数做了限制的线性表。
答案: 错误
29、 栈是一种对进栈﹑出栈操作的次序做了限制的线性表。
答案: 错误
30、 对顺序栈进行进栈、出栈操作,不涉及元素的前、后移动问题。
答案: 正确
31、 空栈没有栈顶指针。
答案: 错误
32、 栈是一种特殊的线性表,其特殊之处在于其存储结构比较特殊。
答案: 错误
分析：答:错误。栈是一种特殊的线性表,其特殊之处是插入和删除操作只能在线性表两端进行。
33、 栈和线性表是两种不同的数据结构,它们的数据元素的逻辑关系也不同。
答案: 错误
分析：错误。栈和线性表是两种不同的数据结构,但它们的数据元素的逻辑关系都是线性关系。
34、 空栈是指栈中元素没有赋值。
答案: 错误
分析：错误。空栈是指栈中没有元素。
35、 栈在算法设计中用于保存临时数据,这些数据具有先进后出的特点。
答案: 正确
36、 有n个不同的元素通过一个栈,产生的所有出栈序列恰好构成这n个元素的全排列。
答案: 错误
37、 n个元素依次连续进栈后,它们的出栈顺序一定与进栈顺序相反。
答案: 正确
38、 顺序栈中元素值的大小是有序的。
答案: 错误
39、 若用s[1..m]表示顺序栈的存储空间,以s[m]为栈底,变量 top指向栈顶元素的位置，当栈未空时,将元素e退栈的操作是“e=sLtop];top–”。
答案: 错误
40、 采用单链表存储链栈时必须带有头结点。
答案: 错误
41、 采用不带头结点的单链表L存储链栈时,链栈为空的条件是L==NULL
答案: 正确
42、 一个栈的输入序列是12345,输出序列为12345,其进栈出栈的操作为：
答案: 1进栈,1出栈,2进栈,2出栈,3进栈,3出栈,4进栈,4出栈,5进栈,5出栈。
43、 设栈采用顺序存储结构,若已进栈i一1个元素,则将第i个元素进栈时,进栈算法的时间复杂度为
答案: O(1)
分析：答:第i个元素直接进栈即可。
44、 两个栈共享一个存储区,利用一维数组data[1..n]表示,栈1在低下标处,栈2在高下标处。两栈顶指针为topl 和 top2,则当栈1空时, topl为 ﹔栈2空时为 ，栈满时为
答案: topl=0 top2=n十1 topl＋1==top2
45、 顺序栈用data[0..n一1]存储数据,栈顶指针为top,其初始值为0,则元素r进栈的操作是
答案: data[ top]=x;top＋+;
分析：答:由于top=0表示空栈,而又存在data[o]的元素,所以进栈时先将x放在 top处,再将top递增,实际上栈顶指针 top指向栈顶元素的前一个位置。
46、 顺序栈用data[0..n一1]存储数据,栈顶指针为top,其初始值为o,则出栈元素工的操作是
答案: top–;x=data[top];
47、 表达式a＋((b * c—d)/e+f * g/h)＋i/j的后缀表达式是
答案: a b c * d—e/f g * h/＋+i j/＋
48、 若用不带头结点的单链表来存储链栈lst,则创建一个空栈所要执行的操作是
答案: lst=NULL
49、 对于链栈lst,进栈操作在 端进行,出栈操作在 端进行。
答案: 链栈头 链栈头
分析：答:链栈的进栈和出栈操作均在表头进行。
第3章 栈和队列 单元测验-队列
1、 循环队列是
答案: 不会产生假溢出
2、 若某循环队列有队头指针front和队尾指针rear,在队不满时进队操作仅会改变__。
答案: rear
3、 循环队列qu的队满条件(front指向队首元素的前一位置, rear指向队尾元素)是
答案: ( qu. rear＋1)%MaxSize==qu. front
4、 循环队列qu的队空条件(front指向队首元素的前一位置, rear指向队尾元素)是
答案: qu.rear==qu. front
5、 设循环队列中数组的下标是0～N一1,其队头,队尾指针分别为f和r(f指向队首元素的前一位置,r指向队尾元素),则其元素个数为
答案: (r-f ＋N)%N
6、 设循环队列的存储空间为a[0..20],且当前队头指针(f指向队首元素的前一位置)和队尾指针(r指向队尾元素)的值分别为8和3,则该队列中元素示I效为 。
答案: 16
7、 假设用qu[0..M]实现循环队列,f ,r分别为队首元素的前一个位置和队尾位置。若用(r＋1)%(M＋1)==f作为队满的标志,则
答案: 可用f==r作为队空的标志
8、 若用一个大小为6的数组来实现循环队列,且当前rear和 front的值分别为0和3,当从队列中删除一个元素,再加入两个元素后,rear和 front的值分别为
答案: 2和4
9、 最适合用做链队的不带头结点的链表是
答案: 只带尾结点指针的循环单链表
10、 最不适合用做链队的不带头结点的链表是
答案: 只带队头结点指针的非循环双链表
11、 假设用一个不带头结点的单链表表示队列,队头和队尾指针分别为front和rear,则判断队空的条件是
答案: front==NULL
12、 假设用一个不带头结点的单链表表示队列,队头在链表的 位置。
答案: 链头
13、 假设用一个不带头结点的单链表表示队列,队尾在链表的 位置。
答案: 链尾
14、 顺序队采用数组存放队中元素,数组具有随机存取的特性,所以顺序队中可以随机存取元素
答案: 错误
分析：错误。顺序队采用数组存放队中元素,尽管数组具有随机存取的特性,但队列的操作特性是顺序存取。需要说明的是,在迷宫问题求解中,当找到出口时,通过队列反推出迷宫路径,此时实际上是将队列作为数组处理的,而不是进行队列的操作。
15、 在队空间大小为n的非循环队列中,最多只能进行n次进队操作。
答案: 正确
16、 在队空间大小为n的循环队列中,最多只能进行n次进队操作。
答案: 错误
分析：错误。在循环队列中,元素出队后,其位置空了出来,可以被其他进队元素覆盖,所以理论上讲可以进队任意次。
17、 若用“队头指针的值和队尾指针的值相等”作为循环队列为空的标志,则在设置一个空队列时,只需给队头指针和队尾指针赋同一个值,不管什么值都可以。
答案: 正确
分析：正确。因为循环队列中无论出队或进队,都要进行求余运算,将队头指针和队尾指针转换为有效的顺序队下标值。
18、 在教科书中设计循环队列时,用数组存放队中元素,通常队头指针front 指向当前队中队头元素的前一个位置,任何循环队列设计必须这样做,别无他法。
答案: 错误
分析：错误。在循环队列中,队头指针 tront指可当刖队P队女]分B队矶L的蛙性,但并种约定。一旦约定后,相关算法设计都遵循这种约定﹐以便设订的昇法徜足队>竺B州不是说必须这样做,也可以让队头指针front 指向当前队中队头元素的位置,此时相关算法做
相应修改。
19、 队列采用链队表示时,只能采用单链表,不能采用其他形式的链表。
答案: 错误
分析：只要能够存放队中元素及其关系,并且进队和出队操作的性能好,即时间复杂度为O(1),都可作为队列的存储结构。
20、 用双链表表示队列比单链表表示队列更好。
答案: 错误
分析：根据队列的操作特性,用单链表或双链表表示队列都可以,但单链表的存储密度更好,所以不能说用双链表表示队列比单链表表示队列更好。
21、 对于链队,可以根据队头、队尾指针的值计算队中元素个数。
答案: 错误
分析：链队不具有随机存取的特性,不能根据队头,队尾指针值计算队中元素个数，需要遍历链队来求元素个数。
22、 在队列中新插入的元素只能插入到
答案: 队尾
23、 循环队列的优点是
答案: 解决了假溢出问题
24、 某个循环队列的元素空间为data[0..m—1],队头指针为front(指向队首元素的前一位置),队尾指针为rear(指向队尾元素的位置),则队列中元素的个数为
答案: (rear一front十m)%m
分析：答:在循环队列中,队尾指针rear总是跑在队头指针front 的前面(由于是循环的,并不总是rear≥>front),所以队中元素个数=(rear—front十m)%m。
上方为免费预览版答案，如需购买完整答案，请点击下方红字
点关注，不迷路，微信扫一扫下方二维码
关注我们的公众号：阿布查查 随时查看答案，网课轻松过
为了方便下次阅读，建议在浏览器添加书签收藏本网页
电脑浏览器添加/查看书签方法
1.按键盘的ctrl键+D键，收藏本页面
2.下次如何查看收藏的网页？
点击浏览器右上角-【工具】或者【收藏夹】查看收藏的网页
手机浏览器添加/查看书签方法
一、百度APP添加/查看书签方法
1.点击底部五角星收藏本网页
2.下次如何查看收藏的网页？
点击右上角【┇】-再点击【收藏中心】查看
二、其他手机浏览器添加/查看书签方法
1.点击【设置】-【添加书签】收藏本网页
2.下次如何查看收藏的网页？
点击【设置】-【书签/历史】查看收藏的网页
熄渤解履潘泻烈逃攘倘厂叛澈