数据结构与算法(江苏师范大学) 中国大学mooc慕课答案2024版 m109008

第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。

下方是付费阅读内容：本平台商品均为虚拟商品，无法用作二次销售，不支持退换货，请在购买前确认您需要购买的资料准确无误后再购买，望知悉！

完整答案需点击上方按钮支付5元购买,所有答案均为章节测试答案，购买后上方矩形框将出现已付费的隐藏内容。

,

25、 某个循环队列的元素空间为data[0,m—1],队尾指针为rear(指向队尾元素的位置),若已知队中元素个数为n,则队头指针front(指向队首元素的前一位置)为             
答案: (rear一n+m)%m
分析：在循环队列中,队尾指针rear总是跑在队头指针front的前面(由于是循环的,并不总是rear>front),所以已知队中元素个数为n时, front=(rear一n十m)%m。

26、 假设用一个不带头结点的单链表表示队列,进队的操作是                       。
答案: 将结点插入单链表末尾

27、 假设用一个不带头结点的单链表表示队列,出队的操作是                  。
答案: 删除单链表的开始结点

28、 已知链队的头,尾指针分别是f和r,则元素x进队的操作命令是                 （多条语句）。
答案: p=(LiQueue * )malloc(sizeof(LiQueue));
p->data=x;
p->next=r->next ;
r->next=p;
r=p;

第4章 串 第4章 单元测验

1、 串是任意有限个           

答案: 字符构成的序列

2、 串是一种特殊的线性表,其特殊性体现在            

答案: 数据元素是单个字符

3、 以下        是”abcd321ABCD”串的子串。

答案:  “21AB”

4、 两个串相等必有串长度相等且      

答案: 串中各位置对应字符均相等

5、 若串s—”software”,其子串的个数是           

答案: 37

6、 设s=”abcd” ,s1=”123″ ,则执行语句s2=InsStr(s,2,s1)后,s2=            

答案: “a123bcd”

7、 设s=”abcd”,则执行语句s2=DelStr(s,2,2)后,s2=          

答案: “ad”

8、 对于一个链串s ,查找第一个元素值为x的算法的时间复杂度为              

答案: O(n)

9、 对于一个链串s,查找第i个元素的算法的时间复杂度为            

答案: O(n)

10、 串采用结点大小为1的链表作为其存储结构,是指                 

答案: 链表中每个结点的数据域中只存放一个字符

11、 设有两个串p和q,求q在p中首次出现的位置的运算称为          

答案: 模式匹配

12、 已知t=”abcaabbcabcaabdab” ,该模式串的next 数组值为            

答案: -1,0,0,0,1,1,2,0,0,1,2,3,4,5,6,0,1

13、 在BF算法中,模式串位j与目标串位i比较,如果两字符不相等,则j的位移方式是                 。

答案: j=0

14、 在BF算法中,模式串位j与目标串i比较,如果两字符相等,则i的位移方式是___。

答案: i++

15、 在BF算法中,模式串位j与目标串i比较,如果两字符相等,则j的位移方式是             

答案: j++

16、 在KMP 算法中,用next数组存放模式串的部分匹配信息,模式串位j与目标串位i比较,如果两字符不相等,则i的位移方式是          

答案: i不变

17、 在 KMP算法中,用next 数组存放模式串的部分匹配信息,模式串位j与目标串位i比较,如果两字符不相等,则j的位移方式是                  

答案: j=next[j]

18、 在KMP算法中,用next 数组存放模式串的部分匹配信息,模式串位j与目标串i比较,如果两字符相等时,则i的位移方式———

答案: i++

19、 在KMP算法中,用next 数组存放模式串的部分匹配信息﹐模式串位j与目标串i比较,如果两字符相等时,则j的位移方式是             

答案: j++

20、 在KMP算法中,用next数组存放模式串的部分匹配信息,next[j]=-1的含义是___。

答案: 表示下一趟从j=0位置开始比较

21、 目标串为s,模式串为t,在KMP模式匹配中next[4]=2的含义是              

答案: 表示模式串匹配失败的位置是j=2

22、 串是由有限个字符构成的序列,子串是主串中任意字符构成的有限序列。

答案: 错误
分析：错误。子串是主串中任意个连续字符构成的有限序列。

23、 串长度为串中不同字符的个数。

答案: 错误
分析：错误。串长度为串中字符的个数。

24、 串通常有顺序存储和链式存储两种存储结构。

答案: 正确

25、 空串就是由空格构成的串。

答案: 错误
分析：错误。空串中不含有任何字符(包括空格字符)。

26、 一个串中           称为该串的子串。
答案: 任意连续字符组成的子序列。

27、 两个串相等的充分必要条件是                           
答案: 两个串的长度相等且对应位置的字符相同。

28、 对于顺序串s ,将其初始化为空串的操作是。
答案: s.length=0

29、 设s=”abcd”,则执行语句s2=SubStr(s,4,2)后,s2=答:               
答案: 空串或””

30、 对于带头结点的链串s ,串为空的条件是                   
答案: s->next==NULL

31、 若要对串进行高效的模式匹配,在顺序串和链串中应选择             存储结构。
答案: 顺序串
分析：顺序串具有随机存取特性,更适合于进行高效的模式匹配

32、 模式串t=”abaabcac”的next数组值为              
答案: -1,0,0,1,1,2,0,1

33、 模式串t=”abaabcac”的nextval数组值为                
答案: -1,0,-1,1,0,2,-1,1

第5章 数组 第5章 数组 单元测验

1、 设二维数组a[m][n]，每个数组元素占用k个存储单元，第一个数组元素的存储地址是LOC(a[0][0])，求按行优先顺序存放的数组元素a[i]i的存储地址为             

答案: LOC(a[0][0])+[i×n+j]×k

2、 设二维数组a[m][n]，每个数组元素占用k个存储单元，第一个数组元素的存储地址是LOC(a[O][0])，求按列优先顺序存放的数组元素a[i][]（O≤i≤m-1，0≤j≤n-1的存储地址为                      

答案: LOC(a[0][0])+[jxm+i]xk

3、 设二维数组a[6][10]，每个数组元素占用4个存储单元，若按行优先顺序存放数组元素，a[0][0]的存储地址为860，则a[3][5]的存储地址是           

答案: 1000

4、 设二维数组a[6][10]，每个数组元素占用4个存储单元，若按行优先顺序存放数组元素，a[3][5]的存储地址为1000，则a[0][0]的存储地址是              

答案: 860

5、 一个矩阵从a[O][0]开始存放，每个元素占用4个存储单元，若a[7][8]的存储地址为2732，a[13][16]的存储地址为3364，则此矩阵的存储方式是                

答案: 按行优先存储或按列优先存储均可

6、 若将n阶上三角矩阵A按列优先顺序压缩存放在一维数组B[1..n(n+1)/2]中，A中第一个非零元素a[]1[1]存于B数组的b[1]中，则应存放到 b[k]中的非零元素 a[i][j] (1≤i≤n，1≤j≤i)的下标i、j与k的对应关系是             

答案: j(j-1)+i

7、 若将n阶下三角矩阵A按列优先顺序压缩存放在一维数组B[n(n+1)/2]中，A中第一个非零元素a[1][1]存于B数组的b[1]中，则应存放到b中的非零元素a[i]j的下标i、j与k的对应关系是            

答案: (j-1)(2n-j+2)+i-j+1

8、 三维数组R[c1..d1,c2..d2,c3..d3]共含有             个元素。

答案: (d1-c1+1)×(d2-c2+1)×(d3-c3+1)

9、 一维数组A采用顺序存储方式，下标从0开始，每个元素占4个存储单元,A[8]的起始地址为100，则A[11]的起始地址为           

答案: 112

10、 数组A[1..10,-2..6,2..8]以行优先顺序存储，设第一个元素的首地址为100每个元素占3个单元的存储空间，则元素A[5][0][7]的存储地址为       

答案: 913

11、 设A[0..9,0.9]是一个10×10对称矩阵，采用压缩存储方式存储其下三角部分，已知每个元素占用两个存储单元，其第一个元素A[0][0]的存储位置为1000，则A[4][5]的存储地址是             

答案: 1030

12、 设A[0..9,0.9]是一个10×10对称矩阵，采用压缩存储方式存储其下三角部分，已知每个元素占用两个存储单元，其第一个元素A[0][0]的存储位置为1000，则地址为1080的元素下标为          

答案: i=8,j=4

13、 一个nxn的对称矩阵存入内存，在采用压缩存储时所占用的空间大小是           

答案: n(n+1)/2

14、 设数组a[1..50,1..80]的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45][68]的存储地址为               

答案: 9174

15、 设数组a[1..50,1..80]的基地址为2000，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[45][68]的存储地址为               

答案: 8788

16、 设有三对角矩阵Ann(从A[0,0]开始)，将其三对角线上的元素逐行存于数组B[0..m]中，使B[k]=A[i,j]，则用i、j表示k的下标变换公式为         

答案: 2i+j

17、 对稀疏矩阵进行压缩存储的目的是           

答案: 节省存储空间

18、 一个稀疏矩阵采用压缩后，和直接采用二维数组存储相比会失去____特性

答案: 随机存取

19、 稀疏矩阵常用的压缩存储方法有____。

答案: 三元组和十字链表

20、  m行n列的稀疏矩阵采用十字链表表示时，其中单链表的个数为           

答案: m+n+1

21、  m行n列的稀疏矩阵采用十字链表表示时，其中头节点的个数为          

答案: MAX{m,n}+1

22、 所谓稀疏矩阵指的是           的矩阵。

答案: 相对总元素个数而言，非零元素很少且分布没有规律

23、 用十字链表表示一个有k个非零元素的m×n的稀疏矩阵，则其总的节点数为            

答案: MAX(m,n)+k+1

第6章 递归 第6章 递归 单元测试

1、 递归模型为f(1)=1，f(n)=f(n-1)+n (n>1)，其中递归出口是        

答案: f(1)=1

2、 递归模型为f(1)=1，f(n)=f(n-1)+n (n>1)，其中递归体是               。

答案:  f(n)=f(n-1)+n

第7章 树和二叉树 树 单元测验

1、 树最适合用来表示___。

答案: 元素之间具有分支层次关系的数据

2、 现有一“遗传”关系，设x是y的父亲，则x可以把他的属性遗传给y。表示该遗传关系最适合的数据结构为__。

答案: 树

3、 以下存储结构中，不是树的存储结构的是                 

答案: 顺序存储结构

4、 一棵高度为h节点个数为n的m(m≥3）次树中，其分支数是___。

答案: n-1

5、 一棵高度为h的满m次树中，节点总数至多为              

答案: (m^h-1)/(m-1)

6、 假定一棵度为3的树中节点总数为50，则其最小高度为              

答案: 5

7、 若一棵3次树中有2个度为3的节点，1个度为2的节点，2个度为1的节点，该树一共有____个节点。

答案: 11

8、 若一棵3次树中有a个度为1的节点，b个度为2的节点，c个度为3的节点，则该树有___个叶子节点。

答案: 1+b+2c

9、 若一棵度为7的树有7个度为2的节点，有6个度为3的节点，有5个度为4的节点，有4个度为5的节点，有3个度为6的节点，有2个度为7的节点，该树共有___个叶子节点。

答案: 78

10、 若一棵有n个节点的二叉树，其中所有分支节点的度均为k，该树中的叶子节点个数是___。

答案: (nk-n+1)/k

11、 树中任意节点允许有              孩子节点，除根节点外，其余节点有且仅有一个双亲节点。

答案: 有零个或多个

12、 若一棵树的括号表示为A(B(E,F),C(G(H,I,J,K),L),D(M(N)))，则该树的度为             

答案: 4

13、 若一棵树的括号表示为A(B(E,F),C(G(H,I,J,K),L),D(M(N)))，则该树的深度为             

答案: 4

14、 若一棵树的括号表示为A(B(E,F),C(G(H,I,J,K),L),D(M(N)))，则该树中叶子节点个数为             

答案: 8

15、 在有n(n>1)个节点的各棵树中，其中高度最小的那棵树的高度是            

答案: 2

16、 在有n(n>1)个节点的各棵树中，高度最小的那棵树共有             个叶子节点。

答案: n-1

17、 在有n(n>1)个节点的各棵树中，高度最大的那棵树的高度是              

答案: n

18、 在有n(n>1)个节点的各棵树中，高度最大的那棵树的叶子节点个数是              

答案: 1

19、 树中元素之间是多对多的关系。

答案: 错误

20、 树适合表示层次关系。

答案: 正确

21、 树和二叉树是两种不同的树形结构。

答案: 正确

22、 一棵有n个节点的树中，其分支数为n。

答案: 错误

23、 对一棵树进行先根遍历和后根遍历时，其中叶子节点出现的相对次序是相同的。

答案: 正确

第7章 树和二叉树 二叉树单元测验-1

1、 以下关于二叉树的说法中正确的是       

答案: 二叉树中每个节点的度可以小于2

2、 按照二叉树的定义，具有3个节点的二叉树有          种。

答案: 5

3、 若一棵二叉树具有10个度为2的节点，5个度为1的节点，则度为0的节点个数为_____。

答案: 11

4、 具有10个叶子节点的二叉树中有      个度为2的节点。

答案: 9

5、 一棵二叉树中有7个叶子节点和5个单分支节点，其总共有            个节点。

答案: 18

6、 一棵二叉树中有35个节点，其中所有节点的度之和是           

答案: 34

7、 深度为5的二叉树至多有                 个节点。

答案: 31

8、 深度为5的二叉树至少有___个节点。

答案: 5

9、 二叉树第i层上至多有             个节点。

答案: 2^(i-1)

10、 一个具有1025个节点的二叉树的高h为             

答案: 11~1025

11、 设高度为h的二叉树上只有度为0和度为2的节点，则此类二叉树中所包含的节点数至少为          

答案: 2h-1

12、 设高度为h的二叉树上只有度为0和度为2的节点，则此类二叉树中所包含的节点数至多为          

答案: 2^h-1

13、 一棵完全二叉树中有1001个节点，其中叶子节点的个数是         

答案: 501

14、 一棵完全二叉树中有501个叶子节点，则至少有___个节点。

答案: 1001

15、 一棵完全二叉树中有501个叶子节点，则至多有____个节点。

答案: 1002

16、 一棵高度为h的完全二叉树至少有____节点。

答案: 2^(h-1)

17、 一棵高度为8的完全二叉树至少有___叶子节点。

答案: 64

18、 一棵高度为8的完全二叉树至多有              个叶子节点。

答案: 128

19、 一棵满二叉树有m个叶子节点和n个节点，其深度为h，则有    

答案: n=2^h-1

20、 一棵满二叉树中有127个节点，其中叶子节点的个数是          

答案: 64

21、 一棵满二叉树共有64个叶子节点，则其节点个数为                 。

答案: 127

22、 一棵满二叉树共有64个叶子节点，则其深度为             。

答案: 7

23、 具有n个节点的二叉树采用二叉链存储结构，共有           个空指针域。

答案: n+1

24、 具有n个节点的二叉树采用二叉链存储结构，共有           个非空指针域。

答案: n-1

25、 高度为h的完全二叉树至少有             个节点

答案: 2^(h-1)

26、 高度为h的完全二叉树至多有             个节点

答案: 2^h-1

27、 高度为h 的完全二叉树，若按自上而下，从左到右次序给节点编号(从1开始)，则第h层中编号最小的叶子节点的编号是                

答案: 2^(h-1)

28、 高度为h 的完全二叉树，若按自上而下，从左到右次序给节点编号(从1开始)，则第h层中编号最大的叶子节点的编号是                

答案: 2^h-1

29、 在具在n个节点的二叉树中如果有m个叶子节点，则一定有              个度为1的节点。

答案: n-2m+1

30、 在具在n个节点的二叉树中如果有m个叶子节点，则一定有              个度为2的节点。

答案: m-1

第7章 树和二叉树 二叉单元测验-2

1、 如果二叉树T2是由一棵树T,转换而来的二叉树，那么T中节点的先根序列对应T2的            序列。

答案: 先序遍历

2、 如果二叉树T,是由一棵树T转换而来的二叉树，那么T中节点的后根序列对应T2的               序列。

答案: 中序遍历

3、 某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是____。

答案: 高度等于其节点数

4、 在一棵非空二叉树的中序遍历序列中，根节点的右边                

答案: 只有右子树上的所有节点

5、 任何一棵二叉树的叶子节点在先序、中序和后序遍历序列中的相对次序             。

答案: 不发生改变

6、 设n、m为一棵二叉树上的两个节点,在中序序列中n在m前的条件是                

答案: n在m左边

7、 设n、m为一棵二叉树上的两个节点，在先序序列中n在m之前，在后序序列中n在m之后，则n和m的关系是        

答案: n是m的祖先

8、 设n、m为一棵二叉树上的两个节点，应该选择              两个序列来判断n是否是m的祖先。

答案: 前三种选项都可以

9、 对二叉树的节点从1开始连续遍号，要求每个节点的编号大于其左孩子(如果有的话）的编号，而小于其右孩子（如果有的话）的编号，则可以采用           遍历实现二叉树的节点编号。

答案: 中序

10、 若二叉树采用二叉链存储结构，要交换其所有分支节点的左、右子树的位置，不能利用___遍历方法。

答案: 中序

11、 一棵二叉树的先序遍历序列为ABCDEFG，它的中序遍历序列可能是                 。

答案: ABCDEFG

12、 一棵二叉树的先序遍历序列为ABCDEF，中序遍历序列为CBAEDF，则后序遍历序列为             

答案: CBEFDA

13、 一棵二叉树的后序遍历序列为DABEC，中序遍历序列为 DEBAC，则先序遍历序列为               

答案: CEDBA

14、 一棵二叉树的先序遍历序列为EFHIGJK，中序遍历序列月HFIEJKG，该二叉树根节点的右孩子为        

答案: G

15、 在二叉树中，指针p所指节点为叶子节点的条件是           

答案: p->lchild==NULL && p->rchild==NULL

16、 二叉树的先序序列和中序序列相同的条件是            

答案: 任何节点至多只有右孩子节点

第7章 树和二叉树 哈夫曼树 单元测验

1、 以下属于二叉树的是              

答案: 哈夫曼树

2、 根据使用频率为5个字符设计的哈夫曼编码不可能是               。

答案: 100,11,10,1,0

3、 根据使用频率为5个字符设计的哈夫曼编码不可能是            

答案: 00,100,101,110,111

4、 若哈夫曼树中，其叶子节点个数为n，则哈夫曼树中节点的总数为          

答案: 2n-1

5、 设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有____个节点。

答案: 25

6、 一棵哈夫曼树中有20个度为2的节点，则它共有____个叶子节点。

答案: 21

7、 若以{4,5,6,7,8}作为叶子节点的权值构造一棵哈夫曼树，则其带权路径长度是           

答案: 69

8、 若以{4,5,6,7,8}作为叶子节点的权值构造一棵哈夫曼树，各节点对应的哈夫曼编码为             

答案: 010、011、10、11、00

9、 哈夫曼树中不存在度为1的节点。

答案: 正确

10、 在哈夫曼树中，权值相同的叶子节点都在同一层上。

答案: 错误

11、 在哈夫曼树中，权值较大的叶子节点一般离根节点较远。

答案: 错误

12、 哈夫曼树是带权路径长度最小的树，路径上权值较大的节点离根节点较近。

答案: 正确

13、 在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应作特殊处理。

答案: 错误

第8章 图 8.1 单元测试

1、 在一个图中，每个顶点的前驱顶点和后继顶点数可以有___。

答案: 任意多个

2、 在一个无向图中，所有顶点的度之和等于边数的            倍。

答案: 2

3、 一个有n个顶点的无向图最多有___条边。

答案: n(n-1)/2

4、 一个有n个顶点的有向图最多有              条边。

答案: n(n-1)

5、 在一个具有n个顶点的无向连通图中至少有____条边。

答案: n-1

6、 在一个具有n个顶点的有向图中，构成强连通图时至少有__条边。

答案: n

7、 一个有n个顶点的无向图，其中边数大于n-1，则该图必是                

答案: 连通图

8、 一个具有n(n≥1)个顶点的图，最少有                个连通分量。

答案: 1

9、 一个具有n(n≥1)个顶点的图，最多有                个连通分量。

答案: n

10、 一个具有n (n≥1)个顶点的有向图，其强连通分量个数最少有__个。

答案: 1

11、 一条长度大于等于2的简单路径，若起始顶点和终止顶点为同一顶点，称该简单路径为             。

答案: 回路

12、 一个无向图中有16条边，度为4的顶点有3个，度为3的顶点有4个,其余顶点的度均小于3，则该图至少有__个顶点。

答案: 11

13、 一个无向连通图中有16条边，所有顶点的度均小于5，度为4的顶点有3个，度为3的顶点有4个，度为2的顶点有2个，则该图有___个顶点。

答案: 13

14、 一个无向连通图中有13个顶点和16条边，所有顶点的度均小于5，度为3的顶点有4个，度为2的顶点有2个，则该图中度为4的顶点有____个。

答案: 3

第8章 图 8.2 单元测试

1、 无向图的邻接矩阵是一个              

答案: 对称矩阵

2、 一个图的邻接矩阵是对称矩阵，则该图一定是           

答案: 无向图或有向图

3、 一个图的邻接矩阵不是对称矩阵，则该图可能是              

答案: 有向图

4、 一个图的邻接矩阵中非0非无穷大的元素个数为奇数，则该图可能是            

答案: 有向图

5、 对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵大是____。

答案: n^2

6、 对于一个具有n个顶点e条边的不带权无向图，若采用邻接矩阵表示，其中非零元素个数是            

答案: 2e

7、 对于无向图的邻接矩阵来说，___。

答案: 第i行上的非零元素个数和第i列的非零元素个数一定相等

8、 用邻接表存储图所用的空间大小             

答案: 与图的顶点和边数有关

9、 在有向图的邻接表表示中，顶点v的边单链表中节点个数等于          

答案: 顶点v的出度

10、 在有向图的邻接表表示中，顶点v在边单链表中出现的次数是            _

答案: 顶点v的入度

11、 关于邻接表的叙述中，___是正确的。

答案: 求有向图节点的度，必须遍历整个邻接表

第8章 图 8.3 单元测试

1、 如果从无向图的任一顶点出发进行一次深度优先遍历即可访问所有顶点则该图一定是____。

答案: 连通图

2、 采用邻接表存储的图的深度优先遍历算法类似于二叉树的___算法。

答案: 先序遍历

3、 采用邻接表存储的图的广度优先遍历算法类似于二叉树的___算法。

答案: 层次遍历

4、 图的广度优先遍历算法中用到一个队列，每个顶点最多进队___次。

答案: 1

5、 一个有向图G的邻接表存储上图所示，现按深度优先遍历算法遍历,从顶点0出发，所得到的顶点序列是           

答案: 0,1,2,4,3

6、 对如上图5所示的无向图，从顶点0开始进行深度优先遍历，可得到顶点访问序列____。

答案: 0 1 3 2 4 6 5

7、 对如上图所示的无向图，从顶点0开始进行广度优先遍历，可得到顶点访问序列       

答案: 0 2 1 3 4 5 6

8、 以下叙述中错误的是          

答案: 图的深度优先遍历不适合有向图

9、 以下___算法可用于求无向图的所有连通分量。

答案: 广度优先遍历

10、 一个有n个顶点e条边的连通图采用邻接表表示，从某个顶点v出发进行深度优先遍历DFS(G,v)，则最大的递归深度是            。

答案: n

11、 一个有n个顶点e条边的非连通图有m个连通分量，从某个顶点v出发进行深度优先遍历DFS(Gv)，则一共需要调用DFS()            次。

答案: m

第8章 图 8.4 最小生成树 单元测试

1、 一个无向连通图的生成树是含有该连通图的全部顶点的                 

答案: 极小连通子图

2、 n个顶点的连通图的生成树有       个顶点。

答案: n

3、 n个顶点的连通图的生成树有           条边。

答案: n-1

4、 任何一个无向连通图____最小生成树。

答案: 有一棵或多棵

5、 对于有n个顶点的带权连通图，它的最小生成树是指图中任意一个____。

答案: 由n个顶点构成的极小连通子图，且边的权值之和最小

6、 设有无向图G=(VE)和 G’=(V’,E’)，如G’是G的生成树，则以下不正确的说法是______。

答案: G’为G的连通分量

7、 对于如上图所示的无向带权图，用普里姆算法从顶点1开始求最小生成树，按次序产生的边为        

答案: (1,3)，(3,4)，(4,6)，(6,5)，(1,2)

8、 对于如图所示的无向带权图，用克鲁斯卡尔算法产生的边次序是            

答案: (4,6)，(1,3)，(3,4)，(5,6)，(1,2)。

不知道怎么购买？点此查看购买教程！