在线作业一：
一、单选题（共16 道试题，共48 分。）
1. 已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为（）。
A. q->next=s->next；s->next=p
B. s->next=p；q->next=s->next
C. p->next=s->next；s->next=q
D. s->next=q；p->next=s->next
正确答案：A
2. 高度为5的完全二叉树中含有的结点数至少为（）。
A. 16
B. 17
C. 31
D. 32
正确答案：A
3. 设有两个串T和P，求P在T中首次出现的位置的串运算称作（）。
A. 联接
B. 求子串
C. 字符定位
D. 子串定位
正确答案：  D
4. 对于哈希函数H(key)=key%13，被称为同义词的关键字是（）。
A. 35和41
B. 23和39
C. 15和44
D. 25和51
正确答案：D
5. 算法分析的目的是（）。
A. 辨别数据结构的合理性
B. 评价算法的效率
C. 研究算法中输入与输出的关系
D. 鉴别算法的可读性
正确答案：B
6. 在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若
p->next->next=head，则（）。
A. p 指向头结点
B. p 指向尾结点
C. *p 的直接后继是头结点
D. *P 的直接后继是尾结点
正确答案：D
7. 数据结构是（）
A. 一种数据类型
B. 数据的存储结构
C. 一组性质相同的数据元素的集合
D. 相互之间存在一种或多种特定关系的数据元素的集合
正确答案：D
8.采用两类不同存储结构的字符串可分别简称为（）。
A. 主串和子串
B. 顺序串和链串
C. 目标串和模式串
D. 变量串和常量串
正确答案：B
9.已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t到s。若字符串S=″SCIENCESTUDY″，则调用函数Scopy(P,Sub(S,1,7))后得到（）。
A. P=″SCIENCE″
B. P=″STUDY″
C. S=″SCIENCE″
D. S=″STUDY″
正确答案：A
10.在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若
p->next->next= head，则（）。
A. p 指向头结点
B. p 指向尾结点
C. *p 的直接后继是头结点
D. *P 的直接后继是尾结点
正确答案：D
11.若一棵二叉树有11个叶子结点，则该二叉树中度为2的结点个数是（）。
A. 10
B. 11
C. 12
D. 不确定的
正确答案：A
12.下面程序段的时间复杂度是（）。for(i=0;i<n;i++) for(j=1;j<m;j++) A[i][j]=0；
A. O(n)
B. O(m+n+1)
C. O(m+n)
D. O(m*n)
正确答案：D
13.在线性表的下列运算中，不改变数据元素之间结构关系的运算是（）。
A. 插入
B. 删除
C. 排序
D. 定位
正确答案：  D
14. 在计算机内实现递归算法时所需的辅助数据结构是（）。
A. 栈
B. 队列
C. 树
D. 图
正确答案：A
15. 在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用（）。
A. 数据元素的相邻地址表示
B. 数据元素在表中的序号表示
C. 指向后继元素的指针表示
D. 数据元素的值表示
正确答案：  C
16. 对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为（）。
A. 顺序表
B. 用头指针表示的单循环链表
C. 用尾指针表示的单循环链表
D. 单链表
正确答案：C
二、多选题（共  2 道试题，共8 分。）
1. 算法以下几种特性（）。
A. 有穷性
B. 确定性
C. 可行性
D. 输入和输出
正确答案：ABCD
2. 一个好的算法有（ABCD ）设计要求。
A. 正确性
B. 可读性
C. 健壮性
D. 效率与低存储量要求
正确答案：ABCD
三、判断题（共22 道试题，共44 分。）
1. 二叉树中的叶子结点就是二叉树中没有左右子树的结点。A. 错误B. 正确
正确答案：B字符串长度17模式串长度
2. 在队列中，允许进行删除操作的一端称为队尾。A. 错误B. 正确
正确答案：  B
3. 假设以S和X分别表示进栈和退栈操作，则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为a b b c c d d e d c。
A. 错误
B. 正确
正确答案：A
4. 空串的长度是0 A. 错误B. 正确
正确答案：B
5. 数据的逻辑结构在计算机存储器内的表示，称为数据的逻辑结构。A. 错误B. 正确
正确答案：  A
6. 深度为15的满二叉树上，第11层有2^11个结点。
A. 错误
B. 正确
正确答案：A
7. 如果入栈序列是1，3，5，…，97，99，且出栈序列的第一个元素为99，则出栈序列中第30 个元素为47。A. 错误B. 正确
正确答案：B
8. 字符串“sgabacbadfgbacst” 中存在有6个与字符串“ba”相同的子串  A. 错误B. 正确
正确答案：A
9. 假设以行优先顺序存储三维数组A[5][6][7]，其中元素A[0][0][0]的地址为1100，并且每个元素占2个存储单元，则A[4][3][2]的地址是1264。  A. 错误  B. 正确
正确答案：A
10. 当问题的规模n趋向无穷大时，算法执行时间T(n)的数量级被称为算法的时间复杂度。
A. 错误
B. 正确
正确答案：B
11. 一棵含999个结点的完全二叉树的深度为12    A. 错误B. 正确
正确答案：A
12. 在队列中，允许进行插入操作的一端称为队头。
A. 错误
B. 正确
正确答案：B
13.若一棵满三叉树中含有121个结点，则该树的深度为6。A. 错误B. 正确
正确答案：  A
14. 产生冲突现象的两个关键字称为该散列函数的同义字。A. 错误B. 正确
正确答案：B
15. 在二叉树的第i层上至多可以有2i个结点。A. 错误B. 正确
正确答案：A
16. 给出不同的输入序列建造二叉排序树，一定得到不同的二叉排序树。A. 错误B. 正确
正确答案：A
17. 已知指针p指向某单链表中的一个结点，则判别该结点有且仅有一个后继结点的条件是
p->next->next==null。A. 错误B. 正确
正确答案：B
18. 若进栈序列为a，b，c，且进栈和出栈可以穿插进行，则可能出现6个不同的出栈序列。。
A. 错误
B. 正确
正确答案：A
19. 在一个长度为n的循环链表中，删除其元素值为x的结点的时间复杂度为O(n)。
A. 错误
B. 正确
正确答案：B
20. 在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是堆排序。
A. 错误
B. 正确
正确答案：  A
21. 二叉树中最多只有两棵子树，并且有左右之分。A. 错误B. 正确
正确答案：  B
22. 不含任何字符的串称为空串。A. 错误B. 正确
正确答案：B
在线作业二：
一、单选题（共16 道试题，共48 分。）
1. 高度为5 的完全二叉树中含有的结点数至少为（）。
A. 16
B. 17
C. 31
D. 32
正确答案：A
2. 二叉树中第5 层上的结点个数最多为（）。
A. 8
B. 15
C. 16
D. 32
正确答案：C
3. 在一个具有n 个顶点的有向图中，所有顶点的出度之和为Dout ，则所有顶点的入度之和为（）。
A. Dout
B. Dout-1
C. Dout+1
D. n
正确答案：A
4. 在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用（）。
A. 数据元素的相邻地址表示
B. 数据元素在表中的序号表示
C. 指向后继元素的指针表示
D. 数据元素的值表示
正确答案：C
5. 已知栈的最大容量为4。若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行, 则可能出现的出栈序列为（）。
A. 5，4，3，2，1，6
B. 2，3，5，6，1，4
C. 3，2，5，4，1，6
D. 1，4，6，5，2，3
正确答案：C
6. 若算法中语句的最大频度为T(n)=2006n+6n ㏒n+29 ㏒2n，则其时间复杂度为（）。
A. O(㏒n)
B. O(n)
C. O(n ㏒n)
D. O(㏒2n)
正确答案：C
7. 下面程序段的时间复杂度为（）。for (i=0; i<m; i++) for (j=0; j<n; j++) A[i][j]=i*j;
A. O (m2)
B. O (n2)
C. O (m*n)
D. O (m+n)
正确答案：C
8.采用两类不同存储结构的字符串可分别简称为（）。
A. 主串和子串
B. 顺序串和链串
C. 目标串和模式串
D. 变量串和常量串
正确答案：B
9.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为（）。
A. 顺序表
B. 用头指针表示的单循环链表
C. 用尾指针表示的单循环链表
D. 单链表
正确答案：C
10.一棵含18个结点的二叉树的高度至少为（）。
A. 3
B. 4
C. 5
D. 6
正确答案：C
11.判断两个串大小的基本准则是（）。
A. 两个串长度的大小
B. 两个串中首字符的大小
C. 两个串中大写字母的多少
D. 对应的第一个不等字符的大小
正确答案：B
12.已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为（）。
A. 0
B.1
C. 48
D. 49
正确答案：D
13.在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若
p->next->next= head，则（）。
A. p 指向头结点
B. p 指向尾结点
C. *p 的直接后继是头结点
D. *P 的直接后继是尾结点
正确答案：D
14. 与线性表相比，串的插入和删除操作的特点是（）。
A. 通常以串整体作为操作对象
B. 需要更多的辅助空间
C. 算法的时间复杂度较高
D. 涉及移动的元素更多
正确答案：A
15. 抽象数据类型的三个组成部分分别为（）。
A. 数据对象、数据关系和基本操作
B. 数据元素、逻辑结构和存储结构
C. 数据项、数据元素和数据类型
D. 数据元素、数据结构和数据类型
正确答案：A
16. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（）。
A. 3，2，6，1，4，5
B. 3，4，2，1，6，5
C. 1，2，5，3，4，6
D. 5，6，4，2，3，1
正确答案：B
二、多选题（共  2 道试题，共8 分。）
1. 构造最小生成树的两个基本算法是（）。
A. 普里姆算法
B. 克鲁斯卡尔算法
C. 迪杰斯特拉算法
D. 哈希算法
正确答案：AB
2. 由于排序过程中涉及的存储器不同，可以将排序方法分为（）。
A. 稳定排序
B. 不稳定排序
C. 内部排序
D. 外部排序
正确答案：CD
三、判断题（共22 道试题，共44 分。）
1. 含n 个顶点的无向连通图中至少含有n 条边。A. 错误B. 正确
正确答案：A
2. 一棵含999 个结点的完全二叉树的深度为6。A. 错误B. 正确
正确答案：A
3. 在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是基数排序。
A. 错误
B. 正确
正确答案：A
4. 在含100 个结点的完全二叉树中，叶子结点的个数为36。A. 错误B. 正确
正确答案：A
5. 二叉树中的叶子结点就是二叉树中没有左右子树的结点。A. 错误B. 正确
正确答案：B
6. 设S1="good"S2=" "S3="book"，则S1，S2 和S3 依次联接后的结果是”good book” 。
A. 错误
B. 正确
正确答案：B
7. 假设以行优先顺序存储三维数组A[5][6][7]，其中元素A[0][0][0]的地址为1100，并且每个元素占  2 个存储单元，则A[4][3][2]的地址是1264。  A. 错误  B. 正确
正确答案：A
8. 如果入栈序列是1，3，5，…，97，99，且出栈序列的第一个元素为99，则出栈序列中第30 个元素为47。A. 错误B. 正确
正确答案：B
9. 二叉树是度为2 的有序树。A. 错误B. 正确
正确答案：A
10. 队列的队尾位置通常是随着入队操作而变化的。A. 错误B. 正确
正确答案：B
11. 串S=”I am a worker″的长度是10。A. 错误B. 正确
正确答案：A
12. 在文本编辑程序中查某一特定单词在文本中出现的位置，可以利用串的定位操作。
A. 错误
B. 正确
正确答案：B
13. 队列的修改是按先进先出的原则进行的。A. 错误B. 正确
正确答案：B
14. 两个串相等的充分必要条件是两个串的长度相等且字母相同。A. 错误B. 正确
正确答案：B
15. 栈下溢是指在栈空时进行出栈操作A. 错误B. 正确
正确答案：B
16. 给出不同的输入序列建造二叉排序树，一定得到不同的二叉排序树。A. 错误B. 正确
正确答案：A
17. 若链串结点中的指针占4 个字节，每个字符占1 个字节，则结点大小为2 的链串的存储密度为2/6。  A. 错误  B. 正确
正确答案：B
18. 一个具有4 个顶点的无向完全图有6条边。A. 错误B. 正确
正确答案：B
19. 数据的逻辑结构描述数据元素之间的逻辑关系，与存储方式无关。A. 错误B. 正确
正确答案：B
20. 产生冲突现象的两个关键字称为该散列函数的同义字。A. 错误B. 正确
正确答案：B
21. 已知指针p 指向某单链表中的一个结点，则判别该结点有且仅有一个后继结点的条件是p->next->next==null。A. 错误B. 正确
正确答案：B
22. 假设三维数组A[10][9][8]按行优先顺序存储，若每个元素占3 个存储单元，并且首地址为100，则元素A[9][8][7]的存储地址是501。A. 错误B. 正确
正确答案：A

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。