电子科大15春[数据结构]在线作业123与答案

在线作业一： 一、单选题（共 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

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

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

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

在线作业三： 一、单选题（共 16 道试题，共 48 分。 ）

1. 在头指针为 head 且表长大于 1 的单循环链表中，指针 p 指向表中某个结点，若 p->next->next= head,则（ ） 。

A. p 指向头结点 B. p 指向尾结点

C. *p 的直接后继是头结点 D. *P 的直接后继是尾结点

正确答案：D

2. 已知指针 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

3. 对于有向图，其邻接矩阵表示相比邻接表表示更易于进行的操作为（ ） 。

A. 求一个顶点的邻接点 B. 求一个顶点的度 C. 深度优先遍历 D. 广度优先遍历

正确答案：B

4. 若进栈序列为 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

5. 下面程序段的时间复杂度为（ ）。 for (i=0; i

A. O (m2) B. O (n2) C. O (m*n) D. O (m+n)

正确答案：C

6. 执行下列程序段后，串X 的值为（ ）。 S=〞abcdefgh 〞; T=〞xyzw 〞; substr (X,S,2,strlen(T)); substr (Y,S, stelen(T),2); strcat (X,Y);

A. 〞cdefgh 〞 B. 〞cdxyzw 〞 C. 〞cdefxy 〞 D. 〞cdefef 〞

正确答案：D

7. 二叉树中第 5 层上的结点个数最多为（ ） 。

A. 8 B. 15 C. 16 D. 32

正确答案：C

8. 已知一棵含 50 个结点的二叉树中只有一个叶子结点， 则该树中度为 1 的结点个数为 （ ） 。

A. 0 B. 1 C. 48 D. 49

正确答案：D

9. 队和栈的主要区别是（ ） 。

A. 逻辑结构不同 B. 存储结构不同

C. 所包含的运算个数不同 D. 限定插入和删除的位置不同

正确答案：D

10. 判断两个串大小的基本准则是（ ） 。

A. 两个串长度的大小 B. 两个串中首字符的大小

C. 两个串中大写字母的多少 D. 对应的第一个不等字符的大小

正确答案：B

11. 在一个具有 n 个顶点的有向图中， 所有顶点的出度之和为 Dout ， 则所有顶点的入度之 和为（ ） 。

A. Dout B. Dout-1 C. Dout+1 D. n

正确答案：A

12. 如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则 该结构是（ ） 。

A. 栈 B. 队列 C. 树 D. 图

正确答案：C

13. 从顺序表中删除一个元素时，表中所有在被删元素之后的元素均需（ ） 。

A. 前移一个位置 B. 后移一个位置 C. 不动 D. 视情况而定

正确答案：A

14. 与线性表相比，串的插入和删除操作的特点是（ ） 。

A. 通常以串整体作为操作对象 B. 需要更多的辅助空间

C. 算法的时间复杂度较高 D. 涉及移动的元素更多

正确答案：A

15. 若线性表的插入和删除操作频繁地在表头或表尾位置进行，则更适宜采用的存储结构 为（ ） 。

A. 无头结点的双向链表 B. 带尾指针的循环链表

C. 无头结点的单链表 D. 带头指针的循环链表

正确答案：B

16. 已知一棵完全二叉树有 64 个叶子结点，则该树可能达到的最大深度为（ ） 。

A. 7 B. 8 C. 9 D. 10

正确答案：A

二、多选题（共 2 道试题，共 8 分。 ）

1. 一个好的算法有（ ）设计要求。

A. 正确性 B. 可读性 C. 健壮性 D. 效率与低存储量要求

正确答案：ABCD

2. 由于排序过程中涉及的存储器不同，可以将排序方法分为（ ） 。

A. 稳定排序 B. 不稳定排序 C. 内部排序 D. 外部排序

正确答案：CD

三、判断题（共 22 道试题，共 44 分。 ）

1. 给出不同的输入序列建造二叉排序树，一定得到不同的二叉排序树。 A. 错误 B. 正确 正确答案：A

2. 有向图用邻接矩阵表示后，顶点 i 的入度等于邻接矩阵中第 i 列的元素个数。

A. 错误 B. 正确

正确答案：B

3. 抽象数据类型是指数据逻辑结构及与之相关的操作。 A. 错误 B. 正确

正确答案：B

4. 一棵含 999 个结点的完全二叉树的深度为 12。 A. 错误 B. 正确

正确答案：A

5. 在一个长度为 100 的顺序表中删除第 10 个元素时，需移动 90 个元素。

A. 错误 B. 正确

正确答案：B

6. 字符串“sgabacbadfgbacst” 中存在有 6 个与字符串“ba”相同的子串. A. 错误 B. 正确 正确答案：A

7. 若链串结点中的指针占 4 个字节，每个字符占 1 个字节，则结点大小为 2 的链串的存储 密度为 2/6。 A. 错误B. 正确

正确答案：B

8. 二叉树中必有度为 2 的结点。 A. 错误 B. 正确

正确答案：A

9. 队列的修改是按照先进先出的原则进行的。 A. 错误 B. 正确

正确答案：B

10. 在二叉树的第 i 层上至多可以有 2i 个结点。 A. 错误 B. 正确

正确答案：A

11. 假设以行优先顺序存储三维数组 A[5][6][7]，其中元素 A[0][0][0]的地址为 1100，并且 每个元素占 2 个存储单元，则 A[4][3][2]的地址是 1264。 A. 错误 B. 正确

正确答案：A

12. 产生冲突现象的两个关键字称为该散列函数的同义字。 A. 错误 B. 正确

正确答案：B

13. 如果入栈序列是 1，3，5，„，97，99，且出栈序列的第一个元素为 99，则出栈序列 中第 30 个元素为 47。 A. 错误 B. 正确

正确答案：B

14. 当问题的规模 n 趋向无穷大时， 算法执行时间 T(n)的数量级被称为算法的时间复杂度。

A. 错误 B. 正确

正确答案：B

15. 一棵树可以只有 1 个结点。 A. 错误 B. 正确

正确答案：B

16. 串 S=”I am a worker″的长度是 10。 A. 错误 B. 正确

正确答案：A

17. 假设一棵完全二叉树含 1000 个结点, 则其中度为 2 的结点数为 512 个。

A. 错误 B. 正确

正确答案：A

18. 二叉树中的叶子结点就是二叉树中没有左右子树的结点。 A. 错误 B. 正确

正确答案：B

19. 假设为循环队列分配的向量空间为 Q[20]， 若队列的长度和队头指针值分别为 13 和 17， 则当前尾指针的值为 15。 A. 错误 B. 正确

正确答案：A

20. 在队列中，允许进行删除操作的一端称为队尾。 A. 错误 B. 正确

正确答案：B

21. 一棵含 999 个结点的完全二叉树的深度为 6。 A. 错误 B. 正确

正确答案：A

22. 设 S1="good"S2=" "S3="book"，则 S1，S2 和 S3 依次联接后的结果是”good book” 。

A. 错误 B. 正确

正确答案：B