数据结构导论里的几道题目

Question

我刚学这个，所以想请教下这些问题的答案是什么，请高手赐教

1.从逻辑上可以把数据结构分为( )
A.动态结构、静态结构 B.顺序结构、链式结构
C.线性结构、非线性结构 D.初等结构、构造型结构

2.关于算法的描述，不正确的是( )
A.算法最终必须由计算机程序实现
B.所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界
C.健壮的算法不会因非法的输入数据而出现莫名其妙的状态
D.算法的优劣与算法描述语言无关

4.将两个各有n个元素的有序表合并成一个有序表，其最少的比较次数为( )
A.n B.2n-1
C.2n D.n2 （这题最好带个解释，谢谢）

7.数组A〔0..5〕〔0..5〕的每个元素占5个字节，将其以列为主序存储在起始地址为1000的内存单元中，则元素A〔5〕〔5〕的地址是( )
A.1175 B.1180
C.1205 D.1210 （这题也最好带个解释，谢谢）

9.在一棵深度为H的完全二叉树中，所含结点的个数不少于( )
A.2H-1-1 B.2H-1
C.2H-1 D.2H

10.一个具有n个顶点的无向连通图，它所包含的连通分量数为( )
A.0 B.1
C.n D.不确定

11.下列说法中不正确的是( )
A.无向图的极大连通子图称为连通分量
B.连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点
C.连通图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点
D.有向图的遍历不可采用广度优先搜索算法

12.对一棵二叉排序树采用中根遍历进行输出的数据一定是( )
A.递增或递减序列 B.递减序列
C.无序序列 D.递增序列
再追加一题
22.一棵具有n个结点的树，所有非终端结点的度均为k，则该树中叶子结点个数为________。

Answer 1

第一题:C
数据的逻辑结构分为：线性结构和非线性结构
数据的存储结构分为：顺序存储结构和链式存储结构

第二题：B

第四题：C我个人可以利用二路归并的排序方法，利用特殊情况L1(low1,high1),L2(low2,high2),且low2>hign1。

第七题：A
若A是一个m*n的二维数组，数组下标从零开始，以列为主序存储，则address(A[i,j])=adderss(A[0,0])+(j*n+i)*L其中L为一个元素所占的存储空间
则在此题目中address(A[5,5])=1000+(5*6+5)*5=1000+175=1175

若以行为主序存储，则adderss(A[i,j])=adderss(A[0,0])+(i*m+j)*L
在此题目中address(A[5,5])=1000+(5*6+5)*5=1000+175=1175
即在此题目中以行为主序存储和以列为主序存储，最终结果相同。

第九题：B
完全二叉树是指除最后一层外，每一层上的结点数都达到最大值，在最后一层上指缺少右边的若干结点。根据定义可以先求出深度为H-1的满二叉树的结点个数为2^（H-1）-1,则继而可以得到深度为H的满二叉树的结点最少为2^(H-1)。

第十题：D
无向图的极大连通子图就叫做连通分量。问题关键在于n个结点的无向图有很多种，所以连通分量数不能确定。

第十一题：D

第十二题：D
二叉排序树的定义为：左子树上的所有结点值均小于根节点的值，右子数上的值均不小于根结点的值。
又因为中序遍历的循序是：先访问左结点，再访问根结点，最后访问右结点。
根据以上两个原则可以得到.对一棵二叉排序树采用中根遍历进行输出的数据一定是递增序列。

第二十二题：
一棵具有n个结点的树，所有非终端结点的度均为k，则此二叉树为K叉树，这棵树只右度为K和度为0的结点，设度为K的结点数为a，度为0的结点数为b，则n=a+b。又设二叉树的所有分支为m,则m=k*a,同样可以得到n=m+1。
综上可以得到b=[(n-1)*(k-1)/k-1]。

以上是我自己对以上题目的解答，如果有什么不妥之处请与我联系继续探讨。

Answer 2

1.C 2.D 4.A(其中一个有序表的最小的元素大于另外一个表的最大元素的情况)
7.A（1000+5*（6*j+i），则i=5，j=5,带入可得）
9.2^(H-1)
10.B
11.D
12.D
22.n-(n-1)/k