想练笔的进来一份数据结构与算法的试题,看一下你的水平(A)

1．某二叉树的前序遍历为：abdefc，中序遍历为：bedfac，则后序遍历为（      ）。
A．efdbca      B．befdca       C．edfbca       D．efdbac
2．某无向图G是连通的，则结点数n和边数e一定有如下关系（     ）。
A . e>=n-1          B . e>=n-2        C .  e>=n-3        D . e>=n-4
3．能采用二分查找的数据结构是（      ）
A .线性表        B. 二叉树      C. 有序表       D . 哈希表
4．已知某图G，e 为G中边的总数，则图G中所有顶点的度之和为（      ）。
A . 2e           B . e         C . 2e+1         D . 2e-1
5．下列哪一个不属于算法的性质（      ）。
A．输入性     B．输出性      C．可执行性      D．可修改性
6．一棵有n（n>0）个结点的满二叉树共有(      )个叶子结点。
A. n/2       B. n/2-1       C.  (n+1)/2      D. (n-1)/2
7．顺序表的主要优点是（      ）。
A．不支持随机存取            B．内存空间利用率高
C．时间效率高                D．可方便扩充数组大小
8．假设指针p指向单链表中的某一结点，若在p指针的后面插入一个新结点q，只需修改下列哪个指针值即可（      ）。
A．p=q;q=p.next;                     B．p=q.next;q.next=p.next
C．p.next=q;q.next=p.next;           D．q.next=p.next;p.next=q;
9．若进栈系列为：a，b，c，d，则下列哪一个不可能是出栈系列（      ）。
A．a，b，c，d      B．c，d，b，a     C．a，c，d，b     D．c，a，b，d
10．某二叉树共有1001个结点，其中叶结点的个数为501个，则度为2的结点个数为（    ）。
A．498        B．499      C．500       D．不能确定
二．填空题（每空2分，共20分）
1．若规定二叉树根结点的层次为1，则第4层上最多有（          ）个结点。
2．具有N个结点的无向完全图共有（                ）条边。
3．数据结构课程是研究数据的（             ）、（             ）、（            ）等三个方面的内容。
4．树转换为二叉树，其根结点的（           ）子树一定为空。
5．若串s=“Data Structure”，则执行语句s=s.substring(5, s.length())后,
 s的值为(               )。
6．已知二维数组a[10][8]采用行优先存储方式，每个元素占2个存储单元，第一个元素的存储地址是1012，则元素a[4][5]的存储地址为（             ）。
7．具有N个数据的无序表中，若采用顺序查找算法，且每个数据查找的概率相等，那么查找成功时，平均查找长度ASL=（          ）。
8．画出具有3个结点的二叉树的所有形态：（                                     ）。


三．判断题（正确的请打“√”，错误的请打“×”，每题1分，共10分）
1．堆栈是一种先进先出表。                                  （   ）
2．递归算法是指存在自调用的算法。                          （   ）
6．满二叉树一定是完全二叉树。                              （   ）
4．数据元素之间的相互联系方式称为数据的逻辑结构。          （   ）
5．算法执行的时间越长说明算法的时间效率越高。              （   ）
6．实现顺序存储结构的方法是使用数组。                      （   ）
7．对二叉树和图进行遍历所得的次序都是唯一的。              （   ）
8．含有N（N>1）个结点的二叉树前序和后序遍历次序一定不相同。（   ）
9．二叉排序树中根结点的权值最大。                          （   ）
10．图的最小生成树是惟一的。                               （   ）
四．应用题（38分）
1．对于下列二叉树，请写出： 
（1）前、中、后序遍历次序； 
（2）中序线索二叉链表；（10分） 
2．给定数据元素系列为{47，23，2，15，98，57，22，6，12}，请写出冒泡排序各趟的结果。（6分）

(图弄不出来)
3．给定叶子结点的权值{1，4，6，2，9}，请构造哈夫曼树，并给出叶子结点的哈夫曼编码。
（6分）



4．给定数据元素系列为{47，23，2，15，98，57，22，6，12}，请写出直接选择排序各趟的结果。（6分）

5．画出中序遍历次序为xyz的所有二叉树的形态。（6分）

五．算法设计题（12分）
1．下列程序是二分查找的非递归算法,请填空:
public static int biSeach(int a[],int x)
{ int n=a.length();
int  i=0,j=n-1,mid;
while (                 )
   {mid=                      ;
if (a[mid]==x)  return  mid;
else  if (              )   
                           ;
      else
                           ;
}
rerurn  -1;
}




2．请写出冒泡排序的算法：
public static void bubbleSort(int a[])


===============================================================
根据你所做的题目给分,不够分再加

16 个解决方案

#1

做对一道给几分？

#2

都是基础题哈  呵呵

#3

public static int biSeach(int a[],int x)
{ int n=a.length();
int  i=0,j=n-1,mid;
while (j=1 or j=n)
   {mid=i+j/2;
if (a[mid]==x)  return  mid;
else  if (a[mid]>x)   
i=mid,j=n;
      else
        i=1,j=mid;
}
rerurn  -1;
}

#4

搞错了 是 
public static int biSeach(int a[],int x)        //数组是0~N-1
{ int n=a.length();
int  i=0,j=n-1,mid;
while (i=j AND a[i]<>x)
   {mid=(i+j)/2;                        
if (a[mid]==x)  return  mid;
else  if (a[mid]>x)   
i=mid,j=n-1;                   //确定搜索区间
      else
        i=1,j=mid;                    
}
rerurn  -1;
}

#5

这题目不错的 应用题和算法设计题做得一塌糊涂  ：）

#6

答案呢？？

#7

A  
A
C
A
D
C
B
D
D
C
8
n*(n-1)/2
??
右
Structure
1088
N/2
??
F
T
?
?
F
T
F
T
F
F

#8

public static int biSeach(int a[],int x)
{ int n=a.length();
int  i=0,j=n-1,mid;
while (  i<=j               )
   {mid= (i+j)/2                     ;
if (a[mid]==x)  return  mid;
else  if (  x>a[mid]            )   
          i=mid+1;                 ;
      else
          j=mid-1;                 ;
}
rerurn  -1;
}

#9

public static void bubbleSort(int a[],int n){  //n is the total number to be sorted
int i,j,flag;
for(i=0;i<n-1;i++){
flag=0;
for(j=n-2;j>=i;j++){
if(a[j+1]<a[j]){
swap(a[j+1],a[j]);
flag=1;
}
}
if(flag==0)
break;
}
}

#10

1．某二叉树的前序遍历为：abdefc，中序遍历为：bedfac，则后序遍历为（ ）。
   A．efdbca B．befdca C．edfbca D．efdbac
=======================================================================
   根据题目给出的条件很容易得出这样一棵二叉树：所以可以得出后序为：A
                        a
                       / \
                      b   c
                       \
                        d
                       / \
                      e   f
======================================================================
2．某无向图G是连通的，则结点数n和边数e一定有如下关系（ ）。
   A .e>=n-1   B .e>=n-2 C .e>=n-3 D .e>=n-4
======================================================================
   A
======================================================================
3．能采用二分查找的数据结构是（ ）
   A .线性表 B. 二叉树 C. 有序表 D . 哈希表
======================================================================
   C
======================================================================
4．已知某图G，e 为G中边的总数，则图G中所有顶点的度之和为（ ）。
   A . 2e B . e C . 2e+1 D . 2e-1
======================================================================
   A
======================================================================
5．下列哪一个不属于算法的性质（ ）。
   A．输入性 B．输出性 C．可执行性 D．可修改性
=====================================================================
   D
=====================================================================
6．一棵有n（n>0）个结点的满二叉树共有( )个叶子结点。
   A. n/2 B. n/2-1 C. (n+1)/2 D. (n-1)/2
=====================================================================
   满二叉树表示N1=0
   由公式： n=n0+n2   ;n0=n2+1   很容易可以算出：n0=(n-1)/2   所以选D
=====================================================================
7．顺序表的主要优点是（ ）。
   A．不支持随机存取   B．内存空间利用率高
   C．时间效率高       D．可方便扩充数组大小
========================================================================
   A
========================================================================
8．假设指针p指向单链表中的某一结点，若在p指针的后面插入一个新结点q，只需修改下列哪个指针值即可（ ）。
   A．p=q;q=p.next;               B．p=q.next;q.next=p.next；
   C．p.next=q;q.next=p.next;     D．q.next=p.next;p.next=q;
=========================================================================
   C
=========================================================================
9．若进栈系列为：a，b，c，d，则下列哪一个不可能是出栈系列（ ）。
   A．a，b，c，d        B．c，d，b，a
   C．a，c，d，b        D．c，a，b，d
=========================================================================
   根据栈的特性：先进后出，可以判断D是不可能的。
=========================================================================
10．某二叉树共有1001个结点，其中叶结点的个数为501个，则度为2的结点个数为（ ）。
   A．498 B．499 C．500 D．不能确定
=========================================================================
   由二叉树定义可知n0=n2+1   n=n0+n1+n2(这里n1=0)  得N2=500  选C。
=========================================================================

#11

第6题算错了~~~应该选C

#12

应该可以拿100的

#13

没想到当年最拿手的现在都忘光光了，悲哀啊－
用彪哥的话说就是"我不想知道我是怎么来地，我就想知道我是怎么没地！"

#14

二．填空题（每空2分，共20分）
1．若规定二叉树根结点的层次为1，则第4层上最多有（15 ）个结点。
2．具有N个结点的无向完全图共有（n(n-1)/2 ）条边。
3．数据结构课程是研究数据的（存储结构）、（逻辑结构）、（数据的各种操作）等三个方面的内容。
4．树转换为二叉树，其根结点的（右 ）子树一定为空。
5．若串s=“Data Structure”，则执行语句s=s.substring(5, s.length())后,s的值为( Data_)。
6．已知二维数组a[10][8]采用行优先存储方式，每个元素占2个存储单元，第一个元素的存储地址是1012，则元素a[4][5]的存储地址为（1068 ）。
7．具有N个数据的无序表中，若采用顺序查找算法，且每个数据查找的概率相等，那么查找成功时，平均查找长度ASL=（ (n+1)/2）。
8．画出具有3个结点的二叉树的所有形态：（ ）。
==========================================================================
  如三个节点为1、2、3。
     1      1    1      1         1
    / \    /    /        \       /
   2   3  2    2          2      2
         /      \          \      \
        3        3          3     3

三．判断题（正确的请打“√”，错误的请打“×”，每题1分，共10分）
1．堆栈是一种先进先出表。 （x ）
2．递归算法是指存在自调用的算法。 （ x）
6．满二叉树一定是完全二叉树。 （ √）
4．数据元素之间的相互联系方式称为数据的逻辑结构。 （ √）
5．算法执行的时间越长说明算法的时间效率越高。 （x ）
6．实现顺序存储结构的方法是使用数组。 （x）
7．对二叉树和图进行遍历所得的次序都是唯一的。 （ x）
8．含有N（N>1）个结点的二叉树前序和后序遍历次序一定不相同。（ x）
9．二叉排序树中根结点的权值最大。 （x ）
10．图的最小生成树是惟一的。 （√）

#15

填空第6题是1012+2*（4*8+5）=1086 。

#16

？？？、