17春秋华师《数据结构》在线作业.doc

华师《数据结构》在线作业 一、单选题（共 30 道试题，共 60 分。） 1. 算法分析的两个主要方面是（）。 A. 空间复杂度和时间复杂度 B. 正确性和简单性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 正确答案： 2. 一个具有n个顶点的有向图最多有()条边。 A. nx(n-1)／2 B. nx(n-1) C. nx(n+1)／2 D. nxn 正确答案： 3. 若删除非空线性链表中由p所指链结点的直接后继结点的过程是依次执行() A. r=p-next; p-next=r;call RET? B. r=p-next; p-next=r-next; call RET? C. r=p-next; p-next=r-next; call RET(p) D. p-next=p-next-next; call RET(p) 正确答案： 4. 任何一个带权无向连通图的最小生成树( )。 A. 是唯一的 B. 是不唯一的 C. 有可能不惟一 D. 有可能不存在 正确答案： 5. 广义表的深度是指() A. 广义表中元素的个数 B. 广义表中原子元素甜个数 C. 广义表中表元素的个数 D. 广义表中括号嵌套的层数 正确答案： 6. 若将对称矩阵A按照行序为主序方式将包括主对角线元素在内的下三角形的所有元素依次存放在一个一维数组B中，那么，A中某元素ai(i0)在B中的位置是() A. (i*(i-1))／2+j B. (i*(i-1))／2-j C. (j*(j-1))／2+i D. (j*(j-1))/ 2-i 正确答案： 7. 对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为( )。 A. n B. n+1 C. n-l D. n十e 正确答案： 8. 若长度为n的线性表采用顺序存储结构，在表的第i个位置插入一个元素的算法的时间复杂度是（） A. O(n) B. O(n*n) C. O(nlog2n) D. O(log2n) 正确答案： 9. 一个栈的人栈序列是a，b，c，d，e，则栈的不可能的输出序列是() A. edcba B. decba C. dceab D. abcde 正确答案： 10. 对于一组结点，从空树开始，把它们插入到二叉排序树中，就建立了一棵二叉排序树。这时，整个二叉排序树的形状取决于()。 A. 结点的输入顺序 B. 结点的存储结构 C. 结点的取值范围 D. 计算机的硬件 正确答案： 11. 依次将待排序膨0中的元素和有序子序列合并为一个新的有序子序列的是( )。 A. 插入排序 B. 冒泡排序 C. 快速排序 D. 堆排序 正确答案： 12. 线性表的链式存储结构是一种（ ）的存储结构。 A. 随机存取 B. 顺序存取 C. 索引存取 D. HASH存取 正确答案： 13. 若频繁地对线性表进行插入和删除操作，该线性表应该采用（ ）存储结构。 A. 散列 B. 顺序 C. 链式 D. 任意 正确答案： 14. 判定一个循环队列QU(最多元素为m0)为满队列的条件是() A. QU-front==QU-rear B. QU-front!=QU-rear C. QU-front==(QU-rear+1)％m0 D. QU-front!=(QU-rear+1)％m0 正确答案： 15. 线性表采用链式存储时，其地址() A. 必须是连续的 B. 部分地址必须是连续的 C. 一定是不连续的 D. 连续与否均可以。 正确答案： 16. 广义表的长度是指() A. 广义表中元素的个数 B. 广义表中原子元素的个数 C. 广义表中表元素的个数 D. 广义表中括号嵌套的层数 正确答案： 17. 快速排序在最好的情况下的时间复杂度是( )。 A. O(n) B. 0(nlog2n) C. O(n2) D. 0(10g2n) 正确答案： 18. 在一个双链表中结点p之后插入一个结点s的操作是( )。 A. s-right=p;s-left=p-right;p-right-left=s;p-right=s B. s-right=p-right;p-right-left=s;s-right=p;p-left=s C. s-right=p-right;s-left=p;p-left-left=s;p-right=s D. s-right=p;p-left-left=s;p-right=s;s-right=p-right 正确答案： 19. 若将n阶对称矩阵A按照行序为主序方式将包括主对角线元素在内的下三角形的所有元素依次存放在一个一维数组B中，则该对称矩阵在B中占用了()个数组元素。 A. n/2 B. n*(n-1) C. n*(n+1)／2 D. n