《【在线】电子科大17春《数据结构》在线作业2》由会员分享，可在线阅读，更多相关《【在线】电子科大17春《数据结构》在线作业2（6页珍藏版）》请在金锄头文库上搜索。
1、 谋学网 一、单选题（共 16 道试题，共 48 分。 ） V 1. 在一个具有 n 个顶点的有向图中，所有 顶点的出度之和为 Dout ，则所有顶点的入度之和为（ ） 。A. Dout B. Dout-1 C. Dout+1 D. n2. 对于哈希函数 H(key)=key%13,被称为同义词的关键字是（ ） 。 A. 35 和 41 B. 23 和 39 C. 15 和 44 D. 25 和 513. 在具有 n 个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是（ ） 。A. O(1) B. O(n) C. O(nn) D. O(n2)4. 在线性表的下列运算中，不改变数据
2、元素之间结构关系的运算是（ ） 。 A. 插入 B. 删除 C. 排序 D. 定位5. 已知函数 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=STUDY6. 二叉树中第 5 层上的结点个数最多为（ ） 。A. 8 B. 15 C. 16 D. 327. 若算法中语句的最大频度为 T(n)=2006n+6nn+292n,则
3、其时间复杂度为（ ） 。A. O(n) B. O(n)谋学网 C. O(nn) D. O(2n)8. 采用两类不同存储结构的字符串可分别简称为（ ） 。 A. 主串和子串 B. 顺序串和链串 C. 目标串和模式串 D. 变量串和常量串9. 若一棵二叉树有 11 个叶子结点，则该二叉树中度为 2 的结点个数是（ ） 。A. 10 B. 11 C. 12 D. 不确定的10. 在目标串 T0.n-1=xwxxyxy中，对模式串 P0.m-1=xy进行子串定位 操作的结果是（ ） 。A. 0 B. 2 C. 3 D. 511. 若线性表的插入和删除操作频繁地在表头或表尾位置进行，则更适宜采用的存储结
4、构 为（ ） 。 A. 无头结点的双向链表 B. 带尾指针的循环链表 C. 无头结点的单链表 D. 带头指针的循环链表12. 下面程序段的时间复杂度为（ ） 。 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)13. 高度为 5 的完全二叉树中含有的结点数至少为（ ） 。A. 16 B. 17 C. 31 D. 3214. 已知一棵含 50 个结点的二叉树中只有一个叶子结点，则该树中度为 1 的结点个数为（ 谋学网 ） 。A. 0 B. 1 C. 48 D. 4915.
5、设有两个串 T 和 P，求 P 在 T 中首次出现的位置的串运算称作（ ） 。 A. 联接 B. 求子串 C. 字符定位 D. 子串定位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二、多选题（共 2 道试题，共 8 分。 ） V 1. 由于排序过程中涉及的存储器不同，可以 将排序方法分为（ ） 。 A. 稳定排序 B. 不稳定排序 C. 内部排序 D. 外部排序D 2. 假设按照 12345 的进栈顺序，下面哪些是
6、可能的出栈顺序（ ） 。A. 12345 B. 54321 C. 43215 D. 14325 BCD三、判断题（共 22 道试题，共 44 分。 ） V 1. 在对链队列作出队操作时，不会改变 front 指针的值。 A. 错误 B. 正确2. 如果入栈序列是 1，3，5，97，99，且出栈序列的第一个元素为 99，则出栈序列中 第 30 个元素为 47。谋学网 A. 错误 B. 正确3. 有向图用邻接矩阵表示后，顶点 i 的入度等于邻接矩阵中第 i 列的元素个数。 A. 错误 B. 正确4. 假设为循环队列分配的向量空间为 Q20，若队列的长度和队头指针值分别为 13 和 17，则当前尾指
7、针的值为 15。 A. 错误 B. 正确5. 假设三维数组 A1098按行优先顺序存储，若每个元素占 3 个存储单元，且首地址 为 100，则元素 A987的存储地址是 501。 A. 错误 B. 正确6. 空格串的长度是空格的个数。 A. 错误 B. 正确7. 二叉树中必有度为 2 的结点。 A. 错误 B. 正确8. 一棵含 999 个结点的完全二叉树的深度为 12。 A. 错误 B. 正确9. 在队列中，允许进行插入操作的一端称为队头。 A. 错误 B. 正确10. 在一个长度为 n 的单链表 L 中，删除链表中*p 的前驱结点的时间复杂度为 O(n)。 A. 错误 B. 正确11. 产
8、生冲突现象的两个关键字称为该散列函数的同义字。 A. 错误 B. 正确12. 深度为 15 的满二叉树上，第 11 层有 211 个结点。 A. 错误谋学网 B. 正确13. 一棵树可以只有 1 个结点。 A. 错误 B. 正确14. 队列的修改是按先进先出的原则进行的。 A. 错误 B. 正确15. 删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。 A. 错误 B. 正确16. 含 n 个顶点的无向连通图中至少含有 n 条边。 A. 错误 B. 正确17. 二叉树是度为 2 的有序树。 A. 错误 B. 正确18. 数据的逻辑结构在计算机存储器内的表示，称为数据的逻辑结构。 A. 错误 B. 正确19. 两个串相等的充分必要条件是两个串的长度相等且字母相同。 A. 错误 B. 正确20. 串 S=”I am a worker的长度是 10。 A. 错误 B. 正确21. 二叉树中结点只有一个孩子时无左右之分。 A. 错误 B. 正确22. 栈下溢是指在栈空时进行出栈操作 A. 错误 B. 正确谋学网
