数据结构与算法1（张淼 2021春季学期） 中国大学MOOC答案2024版100分完整版

24、 The element in pointer P refers to the bidirectional cyclic list（P is header），and the tail element of List（L） is()

A:NULL
B:P->Right
C:L
D:P->Left
答案: P->Left

25、 在一个单链表中，已知q所指向结点是p所指结点的前驱节点，若在q和p之间插入结点s，则执行()

A:q->next=s; s->next=p;
B:p->next=s->next; s->next=p;
C:p->next=s; s->next=q;
D:s->next=p->next; p->next=s;
答案: q->next=s; s->next=p;

26、 The characteristic of an algorithm that can be handled when an illegal operation occurs is called （）

A:robustness
B:correctness
C:readability
D:reliability
答案: robustness

27、 下列关于线性表说法正确的是()

A:顺序存储方式只能用于存储线性结构
B:在一个长度为n的有序单链表中插入一个新结点并仍保持有序的时间复杂度是O（n）
C:取线性表第i个元素的时间与i的大小无关
D:静态链表需要分配较大的连续空间，插入和删除不需要移动元素
答案: 在一个长度为n的有序单链表中插入一个新结点并仍保持有序的时间复杂度是O（n）;
静态链表需要分配较大的连续空间，插入和删除不需要移动元素

28、 数据元素是数据的最小单位。

A:正确
B:错误
答案: 错误

29、 一个数据结构是由一个逻辑结构、物理结构和这个逻辑结构上的一个基本运算集构成的整体。

A:正确
B:错误
答案: 正确

30、 算法是对特定问题求解步骤的一种描述，是（）的指令序列
答案: 有限

作业第一课 第一课作业

1、 简述逻辑结构与存储结构的关系。
评分规则:  数据的逻辑结构是从具体问题中抽象出来的数学模型，体现了事物的组成和事物之间的逻辑关系。
数据的存储结构主要用来解决各种逻辑结构在计算机中物理存储表示的问题。

2、 度量一个算法的执行时间通常有几种方法？各有何优缺点？
评分规则:  事前分析和事后统计
事前分析： 优点，程序不必运行，所得结果只依赖于算法本身 缺点，不够精确
事后统计： 优点，精确 缺点，必须运行程序，所得结果依赖于硬件、环境等因素

3、 分析下面函数的时间复杂度。void func(int n) { int i = 1, k = 100; while(i < n)
{ k++; i+=2; } }
评分规则:  考虑赋值、运算操作执行的次数 第 3 行赋值 2 次
第 6 行赋值执行 n 次，加法执行 n 次 所以，总共 2n+2 次操作，算法复杂度为 O(n)

4、
评分规则:  

5、 线性表可以用于顺序表或链表存储，试问：两种存储表示各有哪些主要优缺点？如果有n个表同时并存，并且在处理过程中各表的长度会动态变化，表的总数也可能自动改变，在此情况下，应选用哪种存储表示？为什么？若表的总数基本固定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，应采用哪种存储表示？为什么？
评分规则:  言之有理即可

作业第二课 第二课作业

1、 简述线性表、栈和队列的异同。
评分规则:  

2、
评分规则:  

3、 内存中一片连续空间（不妨假设地址从1到m），提供给两个栈S1和S2使用，怎样分配这部分存储空间，使得对任一个栈，仅当这部分空间全满时才发生上溢。
评分规则:  

第二课 第二课测验

1、 假定利用数据a[n]顺序存储一个栈，用top表示栈顶指针，top==-1表示栈空，并已知栈未满，当元素x进栈时执行的操作是()

A:a[top++]=x
B:a[++top]=x
C:a[top–]=x
D:a[–top]=x
答案: a[++top]=x

2、 用S表示进栈操作，用X表示出栈操作，若元素的进栈顺序是1234，为了得到1342的出栈顺序，相应的操作序列是()

A:SXSSXSXX
B:SXSXSSXX
C:SSSXXSXX
D:SXSSXXSX
答案: SXSSXSXX

3、 用链式存储方式的队列进行删除操作时()

A:头尾指针都要修改
B:头尾指针可能都要修改
C:仅修改头指针
D:仅修改尾指针
答案: 头尾指针可能都要修改

4、 一个队列的入队顺序是1，2，3，4，则出队的顺序是（）

A:3，2，4，1
B:1，2，3，4
C:4，3，2，1
D:1，4，3，2
答案: 1，2，3，4

5、 假设循环单链表表示的队列长度为n，队头固定在链表尾部，若只设置头指针，则进队操作的时间复杂度是()

A:
B:
C:
D:
答案:

6、 ()不是栈的基本操作

A:判断栈是否为空
B:删除栈底元素
C:将栈置为空栈
D:删除栈顶元素
答案: 删除栈底元素

7、 设链表不带头结点且所有操作均在表头进行，则下列最不适合链栈的是()

A:只有表尾结点指针，没有表头指针的双向循环链表
B:只有表头结点指针，没有表尾指针的单向循环链表
C:只有表头结点指针，没有表尾指针的双向循环链表
D:只有表尾结点指针，没有表头指针的单向循环链表
答案: 只有表头结点指针，没有表尾指针的单向循环链表

8、 3个不同元素依次进栈，能得到（）种不同的出栈序列

A:4
B:5
C:6
D:7
答案: 5

9、 栈和队列的主要区别在于()

A:它们的存储结构不一样
B:它们的逻辑结构不一样
C:所包含的元素不一样
D:插入、删除操作的限定不一样
答案: 插入、删除操作的限定不一样

10、 在一个链队列中，假设队头指针是front，队尾指针是rear，x所指向的元素需入队，则执行的操作是()

A:rear->next=x, rear=x
B:front=x, front=front->next
C:rear->next=x, x->next=null, rear=x
D:x->next=front->next, front=x
答案: rear->next=x, x->next=null, rear=x

11、 In general，the recursive algorithm is converted into an equivalent non-recursive algorithm that should be set()

A:set
B:stack
C:array
D:queue
答案: stack

12、 The input sequence of the stack is 1，2，3，4，and （）cannot be its output sequence.

A:1，4，3，2
B:1，2，4，3
C:2，1，3，4
D:4，3，1，2
答案: 4，3，1，2

13、 The circular queue A[0…M-1] stores its elements and uses front and rear to represent the header and queue end respectively，while the condition of the full loop queue is （）

A:Q.rear==Q.front
B:(Q.rear+1)%m==Q.front
C:Q.rear+1==Q.front
D:Q.rear==Q.front+1
答案: (Q.rear+1)%m==Q.front

14、 Both the stack and queue are linear structures that restrict the fetch.

A:正确
B:错误
答案: 正确

15、 Stacks，FIFO queues，double ended queues can be considered as derived classes of a container class. The container represents a sequential access structure that restricts access locations.

A:正确
B:错误
答案: 正确

第三课 第三课测验

1、 串是任意有限个 。

A:符号构成的集合
B:符号构成的序列
C:字符构成的集合
D:字符构成的序列
答案: 字符构成的序列

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

A:可以顺序存储
B:数据元素是一个字符
C:可以链式存储
D:数据元素可以是多个字符
答案: 数据元素是一个字符

3、 两个串相等必有串长度相等且 。

A:串的各位置字符任意
B:串中各位置字符均对应相等
C:两个串含有相同的字符
D:两个串所含字符任意
答案: 串中各位置字符均对应相等

4、 设有数组定义：char array[] = “China”；则数组array所占的存储空间为 。

A:4个字节
B:6个字节
C:5个字节
D:7个字节
答案: 6个字节

5、 设有数组定义：char array[10] = “China”；则数组array所占的存储空间为 。

A:4个字节
B:5个字节
C:6个字节
D:10个字节
答案: 10个字节

6、 数组在存储字符串常量时通常需要在其末尾带一个结束标记 来表示串的结束。

A:’\0′
B:’#’
C:’0′
D:’#’
答案: ‘\0’

7、 已知字符串S为”abaabaabacacaabaabcc”, 模式串t为”abaabc”。采用KMP算法进行匹配，笫一次出现匹配失败时，i=j=5, 则下次开始匹配时，i和j的值分别是 。

A:i=1，j=0
B:i=5，j=0
C:i=5，j=2
D:i=6，j=2
答案: i=5，j=2

8、 已知串S=”abababc”，其特征向量为 。

A:0012340
B:0112340
C:0012341
D:0123400
答案: 0012340

9、 KMP算法的特点是在模式匹配时指示主串的指针 。

A:不会变大
B:不会变小
C:都有可能
D:无法判断
答案: 不会变小

10、 Which of the following is the incorrect way to assign a string value?

A:char *str； str = “string”
B:char str[7]={‘s’,’t’,’r’,’i’,’n’,’g’}
C:char str1[10]； str1 = “string”
D:char str1[]=”string”, str2[] = “1234567”
答案: char str1[10]； str1 = “string” 

11、 Assume that strings s=”abcd”,s1=”123″, then executing s2=InsStr(s,2,s1)，s2= 。

A:”123abcd”
B:”a123bcd”
C:”ab123cd”
D:”abc123d”
答案: “a123bcd”

12、 Assume that string s=”abcd”, then executing s2=DelStr(s,2,2)，s2=

A:”abcd”
B:”abc”
C:”ad”
D:”a”
答案: “ad”

13、 If the length of the main string is n and the length of the substring is m, then the time complexity of the Naive string matching algorithm is 。

A:O(m)
B:O(n)
C:O(mn)
D:O(m+n)
答案: O(mn)

14、 If the length of the main string is n and the length of the substring is m, then the time complexity of the KMP algorithm is 。

A:O(m+n)
B:O(m)
C:O(n)
D:O(m*n)
答案: O(m+n)

15、 设有两个串S1和S2, 求S2在S1中首次出现的位置的运算称作 。

A:求子串
B:判断是否相等
C:模式匹配
D:连接
答案: 模式匹配

作业第三课 第三课作业

1、
评分规则:  

第四课 第四课测验

1、 具有10个叶结点的二叉树中有 个度为2的结点。

A:9
B:8
C:10
D:11
答案: 9

2、 一棵完全二叉树上有1001个结点，其中叶子结点的个数是 。

A:501
B:250
C:505
D:254
答案: 501

3、 一个具有1025个结点的二叉树的高h（只有根结点时的高度为1）为 。

A:11
B:11到1025之间
C:10
D:10到1024之间
答案: 11到1025之间

4、 一棵二叉树高度为h（只有根结点时的高度为1）,所有结点的度或为0，或为2，则这棵二叉树最少有 个结点。

A:2h+1
B:2h-1
C:2h
D:h+1
答案: 2h-1

5、 高度为 K（只有根结点时的高度为1）的二叉树最大的结点数为 。

A:
B:
C:
D:
答案:

6、 A complete binary tree of height “k”(the height is 1 when only the root in the tree) contains nodes at least.

A:
B:
C:
D:
答案:

7、 A full binary tree with 2n+1 nodes contains .

A:n-1 leaf nodes
B:n leaf nodes
C:n-1 non-leaf nodes
D:n non-leaf nodes
答案: n non-leaf nodes

8、 A full binary tree with n leaves contains nodes.

A:
B:
C:n
D:2n-1
答案: 2n-1

9、 A binary tree of depth “d” is an almost complete binary tree if .

A:None of them
B:(i) Each leaf in the tree is either at level “d” or at level “d–1”
C:Both (i) & (ii)
D:(ii) For any node “n” in the tree with a right descendent at level “d” all the left descendents of “n” that are leaves, are also at level “d”
答案: Both (i) & (ii)

10、 二叉树的第k（只有根结点时的层数为1）层上最多含有结点数为 。

A:
B:
C:
D:
答案:

11、 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是 。

A:9
B:不确定
C:11
D:15
答案: 11

12、 The number of leaf nodes in a full binary tree of depth d is .

A:
B:
C:
D:
答案:

13、 )由3个结点所构成的二叉树有 种形态。
答案: 5

14、 一棵深度为6的满二叉树有 个分支结点
答案: 63

15、 设一棵完全二叉树具有1000个结点则此完全二叉树有 个度为2的结点。
答案: 499

作业第四课 第四课作业

1、 具有33个结点的完全二叉树的深度是多少？有多少叶结点？有多少个度为1的结点？
评分规则:  树的深度为5，17个叶结点，度为1的结点为0

2、 某二叉树有20个叶结点，有30个结点仅有一个孩子，求该二叉树的总结点数是多少？
评分规则:  

3、
评分规则:  

4、
评分规则: