电子科大《数据结构》在线作业123与答案.pdf

在线作业一： 一、单选题（共 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;inext-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; inext-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. 假设以行优先顺序存储三维数组 A567，其中元素 A000的地址为 1100，并且每 个 元素占 2 个存储单元，则 A432的地址是 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. 假设三维数组 A1098按行优先顺序存储， 若每个元素占 3 个存储单元， 并且首地 址为 100，则元素 A987的存储地址是 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; im; i+) for (j=0; jn; j+) Aij=i*j; 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. 假设以行优先顺序存储三维数组 A567，其中元素 A00