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

奥鹏17春16秋华师数据结构在线作业一、单选题（共 30 道试题，共 60 分。）1. 任何一个带权无向连通图的最小生成树( )。A. 是唯一的B. 是不唯一的C. 有可能不惟一D. 有可能不存在正确答案：2. 向一个栈顶指针为HS的链栈中插入个s所指结点时，则执行()A. HS-next=SB. S-next=HS-next；HS-next=SC. S-next=HS；HS=SD. S-next=HS；HS=HS-next；正确答案：3. 已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是( )。A. acbedB. decabC. deabcD. cedba正确答案：4. 某非空二叉树的前序序列和后序序列正好相反，则二叉树-定是( )的二叉树。A. 空或只有一个结点B. 高度等于其结点数C. 任一结点无左孩子D. 任一结点无右孩子正确答案：5. 若频繁地对线性表进行插入和删除操作，该线性表应该采用（ ）存储结构。A. 散列B. 顺序C. 链式D. 任意正确答案：6. 判定一个循环队列QU(最多元素为m0)为满队列的条件是()A. QU-front=QU-rearB. QU-front!=QU-rearC. QU-front=(QU-rear+1)m0D. QU-front!=(QU-rear+1)m0正确答案：7. 对于一组结点，从空树开始，把它们插入到二叉排序树中，就建立了一棵二叉排序树。这时，整个二叉排序树的形状取决于()。A. 结点的输入顺序B. 结点的存储结构C. 结点的取值范围D. 计算机的硬件正确答案：8. 算法分析的两个主要方面是（）。A. 空间复杂度和时间复杂度B. 正确性和简单性C. 可读性和文档性D. 数据复杂性和程序复杂性正确答案：9. 设串sI=ABCDEFG,s2=PQRST,函数con(x,y)返回x和y串的连接串,subs(s，山)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2,1en(s2)，subs(sl,len(s2)，2)的结果串是( )。A. BCDEFB. BCDEFGC. BCPQRSTD. BCDEFEF正确答案：10. 广义表A=()，(a)，(b，(c，d)的深度为( )A. 2B. 3C. 4D. 5正确答案：11. 一个具有n个顶点的有向图最多有()条边。A. nx(n-1)2B. nx(n-1)C. nx(n+1)2D. nxn正确答案：12. 在数据结构中，从逻辑上可以把数据结构分成（）。A. 动态结构和静态结构B. 紧凑结构和非紧凑结构C. 线性结构和非线性结构D. 内部结构和非内部结构正确答案：13. 在计算递归函数时，若不用递归则应借助数据结构( )。A. 数组B. 队列C. 链表D. 栈正确答案：14. 串的长度是()A. 串中不同字母的个数B. 串中不同字符的个数C. 串中所含字符的个数，且大于0D. 串中所含字符的个数正确答案：15. 广义表的深度是指()A. 广义表中元素的个数B. 广义表中原子元素甜个数C. 广义表中表元素的个数D. 广义表中括号嵌套的层数正确答案：16. 稀疏矩阵一般的压缩存储方法有两种，即 ( )。A. 二维数组和三维数组B. 三元组和散列C. 三元组和十字链表D. 散列和十字链表正确答案：17. 中缀表达式A-(B+CD)*E的后缀形式是()A. ABC+D*E-B. ABCD+E*-C. AB-C+DE*D. ABC-+D/E*正确答案：18. 若将对称矩阵A按照行序为主序方式将包括主对角线元素在内的下三角形的所有元素依次存放在一个一维数组B中，那么，A中某元素ai(inext; 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)正确答案：20. 设单循环链表中结点的结构为(date，link)且rear是指向非空的带表头结点的单循环链表的尾结点指针。若想删除链表的第一个结点,则应执行下列哪一个操作?( )A. s=rear;rear=rear-link;delete sB. rear=rear-link;delete rearC. rear=rear-link-link;delete rearD. s=rear-link-link;rear-link-link=s-link;delete s;正确答案：21. 快速排序在最好的情况下的时间复杂度是( )。A. O(n)B. 0(nlog2n)C. O(n2)D. 0(10g2n)正确答案：22. 设串s=ABUBG,len(s)返回串s的长度，则len(s)是()。A. 2B. 4C. 5D. 6正确答案：23. 算法分析的目的是()A. 找出数据结构的合理性B. 研究算法中的输入和输出的关系C. 分析算法的效率以求改进D. 分析算法的易懂性和文档性正确答案：24. 导致图的遍历序列不惟一的因素是()A. 出发点的不同、遍历方法的不同B. 出发点的不同、存储结构的不同C. 遍历方法的不同、存储结构的不同D. 出发点的不同、存储结构的不同、遍历方法的不同正确答案：25. 若长度为n的线性表采用顺序存储结构，在表的第i个位置插入一个元素的算法的时间复杂度是（）A. O(n)B. O(n*n)C. O(nlog2n)D. O(log2n)正确答案：26. 在一个长度为n 的顺序表中，向第i个元素（1 i n）之前插入一个新元素时，需要向后移动（）个元素。A. n-iB. n-i-1C. n-i+1D. i正确答案：27. 在一个双链表中结点p之后插入一个结点s的操作是( )。A. s-right=p;s-left=p-right;p-right-left=s;p-right=sB. s-right=p-right;p-right-left=s;s-right=p;p-left=sC. s-right=p-right;s-left=p;p-left-left=s;p-right=sD. s-right=p;p-left-left=s;p-right=s;s-right=p-right正确答案：28. 一个栈的人栈序列是a，b，c，d，e，则栈的不可能的输出序列是()A. edcbaB. decbaC. dceabD. abcde正确答案：29. 下面的说法中，不正确的是()A. 只须存放对称矩阵中包括主对角线元素在内的下(或上)三角部分的元素即可B. 只须存放对角矩阵中的非零元素即可C. 稀疏矩阵中值为零的元素较多，因此可以采用三元组表方法存储D. 稀疏矩阵中大量值为零的元素分布有规律，因此可以采用三元组表方法存储正确答案：30. 广义表A：(a，b，()的长度为()A. 2B. 3C. 4D. 5正确答案： 华师数据结构在线作业二、判断题（共 20 道试题，共 40 分。）1. 要访问单链表中的第i个结点，必须从表头开始依次访问过该结点之前的所有结点后才能够实现，即只能够采用顺序存取，而不能够随机存取任一个结点A. 错误B. 正确正确答案：2. 若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算。A. 错误B. 正确正确答案：3. 在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。A. 错误B. 正确正确答案：4. 任何一棵二叉树中至少有一个结点的度为2。A. 错误B. 正确正确答案：5. 在二叉树中插入结点则该二叉树便不再是二叉树。A. 错误B. 正确正确答案：6. 快速排序是不稳定的排序算法，希尔排序是稳定的排序算法。A. 错误B. 正确正确答案：7. 在选择排序中，关键字比较的次数与记录的初始排列次序无关。A. 错误B. 正确正确答案：8. 在一个无向图中，所有顶点的度数之和等于所有边数的2倍。A. 错误B. 正确正确答案：9. 循环链表判断表尾结点用的条件是该结点的后继指针是看它是否为空指针。A. 错误B. 正确正确答案：10. 顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。A. 错误B. 正确正确答案：11. 如果某种排序算法是不稳定的，则该方法没有实际的应用价值。A. 错误B. 正确正确答案：12. 当字符集中的各字符使用频率不均匀时，等长编码是最优的前缀码。A. 错误B. 正确正确答案：13. 一颗非空树中，有且仅有一个结点没有前驱。A. 错误B. 正确正确答案：14. 图的最小生成树的形状可能不唯一。A. 错误B. 正确正确答案：15. 最先进入队列的数据元素最先推出队列。A. 错误B. 正确正确答案：16. 键树是一棵度大于2的树。A. 错误B. 正确正确答