《电子科大秋《数据结构》在线作业》由会员分享,可在线阅读,更多相关《电子科大秋《数据结构》在线作业(6页珍藏版)》请在金锄头文库上搜索。
1、电子科技大学电子科大 16 秋数据结构在线作业 3一、单选题(共 16 道试题,共 48 分。 )1. 抽象数据类型的三个组成部分分别为( ) 。 A. 数据对象、数据关系和基本操作 B. 数据元素、逻辑结构和存储结构 C. 数据项、数据元素和数据类型 D. 数据元素、数据结构和数据类型 正确答案: 2. 已知一棵完全二叉树有 64 个叶子结点,则该树可能达到的最大深度为( ) 。 A. 7 B. 8 C. 9 D. 10 正确答案: 3. 已知在一棵度为 3 的树中,度为 2 的结点数为 4,度为 3 的结点数为 3,则该树中的叶 子结点数为( ) 。 A. 5 B. 8 C. 11 D.
2、18 正确答案: 4. 已知指针 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 正确答案: 5. 下面程序段的时间复杂度为( ) 。 for (i=0; inext B. p-next=p-next-next C. p-next=p D. p=p-next-next; 正确答案
3、: 8. 采用两类不同存储结构的字符串可分别简称为( ) 。 A. 主串和子串 B. 顺序串和链串 C. 目标串和模式串 D. 变量串和常量串 正确答案: 9. 高度为 5 的完全二叉树中含有的结点数至少为( ) 。 A. 16 B. 17 C. 31 D. 32 正确答案: 10. 设串 sl=Data Structures with Java,s2=it,则子串定位函数 index(s1,s2)的值为( ) 。 A. 15 B. 16 C. 17 D. 18 正确答案: 11. 在目标串 T0.n-1=xwxxyxy中,对模式串 P0.m-1=xy进行子串定位 操作的结果是( ) 。 A.
4、 0 B. 2 C. 3 D. 5 正确答案: 12. 对于有向图,其邻接矩阵表示相比邻接表表示更易于进行的操作为( ) 。 A. 求一个顶点的邻接点 B. 求一个顶点的度 C. 深度优先遍历 D. 广度优先遍历 正确答案: 13. 已知一棵含 50 个结点的二叉树中只有一个叶子结点,则该树中度为 1 的结点个数为 ( ) 。 A. 0 B. 1 C. 48 D. 49正确答案: 14. 在头指针为 head 且表长大于 1 的单循环链表中,指针 p 指向表中某个结点,若 p- next-next= head,则( ) 。 A. p 指向头结点 B. p 指向尾结点 C. *p 的直接后继是头
5、结点 D. *P 的直接后继是尾结点 正确答案: 15. 二叉树中第 5 层上的结点个数最多为( ) 。 A. 8 B. 15 C. 16 D. 32 正确答案: 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 正确答案:16 秋数据结构在线作业 3二、多选题(共 2 道试题,共 8 分。 )1. 一个好的算法有( )设计要求。 A. 正确性 B. 可读性 C. 健壮性 D. 效率与低存储量要求 正确答案: 2. 数
6、据类型按其值能否分解,通常可分为( )和( )两种类型。 A. 抽象数据类型 B. 原子类型 C. 结构类型 D. 聚合类型 正确答案:16 秋数据结构在线作业 3三、判断题(共 22 道试题,共 44 分。 )1. 已知完全二叉树 T 的第 5 层只有 7 个结点,则该树共有 15 个叶子结点。 A. 错误 B. 正确 正确答案: 2. 设 S1=“good“,S2=“ “,S3=“book“,则 S1,S2 和 S3 依次联接后的结果是”good book” 。 A. 错误 B. 正确 正确答案: 3. 栈下溢是指在栈空时进行出栈操作 A. 错误 B. 正确 正确答案: 4. 假设三维数组
7、 A1098按行优先顺序存储,若每个元素占 3 个存储单元,且首地址 为 100,则元素 A987的存储地址是 501。 A. 错误 B. 正确 正确答案: 5. 一棵含 999 个结点的完全二叉树的深度为 6。 A. 错误 B. 正确 正确答案: 6. 已知指针 p 指向某单链表中的一个结点,则判别该结点有且仅有一个后继结点的条件 是 p-next-next=null。 A. 错误 B. 正确 正确答案: 7. 假设以行优先顺序存储三维数组 A567,其中元素 A000的地址为 1100,且每 个元素占 2 个存储单元,则 A432的地址是 1264。 A. 错误 B. 正确 正确答案: 8
8、. 假设三维数组 A1098按行优先顺序存储,若每个元素占 3 个存储单元,并且首地 址为 100,则元素 A987的存储地址是 501。 A. 错误B. 正确 正确答案: 9. 在最好和最坏情况下的时间复杂度均为 O(nlogn)且稳定的排序方法是归并排序。 A. 错误 B. 正确 正确答案: 10. 删除二叉排序树中一个结点,再重新插入上去,一定能得到原来的二叉排序树。 A. 错误 B. 正确 正确答案: 11. 一棵含 999 个结点的完全二叉树的深度为 12。 A. 错误 B. 正确 正确答案: 12. 数据的逻辑结构描述数据元素之间的逻辑关系,与存储方式无关。 A. 错误 B. 正确
9、 正确答案: 13. 空格串的长度是空格的个数。 A. 错误 B. 正确 正确答案: 14. 若一棵满三叉树中含有 121 个结点,则该树的深度为 6。 A. 错误 B. 正确 正确答案: 15. 假设为循环队列分配的向量空间为 Q20,若队列的长度和队头指针值分别为 13 和 17,则当前尾指针的值为 15。 A. 错误 B. 正确 正确答案: 16. 二叉树中的叶子结点就是二叉树中没有左右子树的结点。 A. 错误 B. 正确 正确答案: 17. 假设一棵完全二叉树含 1000 个结点,则其中度为 2 的结点数为 512 个。 A. 错误 B. 正确 正确答案: 18. 深度为 k 的二叉树
10、至多有 2k-1 个结点。 A. 错误 B. 正确 正确答案: 19. 假设以 S 和 X 分别表示进栈和退栈操作,则对输入序列 a,b,c,d,e 进行一系列栈操作SSXSXSSXXX 之后,得到的输出序列为 a b b c c d d e d c 。 A. 错误 B. 正确 正确答案: 20. 在文本编辑程序中查找某一特定单词在文本中出现的位置,可以利用串的定位操作。 A. 错误 B. 正确 正确答案: 21. 若一个算法中的语句频度之和为 T(n)=3720n+4nlogn,则算法的时间复杂度为 O(n)。 A. 错误 B. 正确 正确答案: 22. 有向图用邻接矩阵表示后,顶点 i 的入度等于邻接矩阵中第 i 列的元素个数。 A. 错误 B. 正确 正确答案: