第1章  概述
一、简答题
1．简述以下术语的含义并说明它们之间的关系。
数据类型、数据结构、逻辑结构、存储结构
2．简述算法时间效率和空间效率的概念。
3．简述数据结构课程的目的和意义。
二、选择题
1．以下数据结构中，逻辑结构属于线性结构的是
A）有向图 B）链式栈  C）二叉树    D）二叉排序树
2．下列与数据元素有关的叙述中错误的是
A）数据元素是有独立含义的数据最小单位    B）数据元素是描述数据的基本单位
C）数据元素可以称做结点                  D）数据元素可以称做记录
3．设问题的规模为n，分析以下程序段：
a=10;  b=100;
while (b>0)
printf函数的作用是向终端{  a++;
b- -;
}
以上程序段的算法时间复杂度是
A）O(1)  B）O(n)  C）O(n2)  D）O( )
三、填空题
1．数据结构包括的三方面内容分别是：数据的  [1]  、数据的  [2]  和数据的运算。
2．数据元素是数据的基本单位，在某些情况下也可以称为  [1]  、  [2]  和  [3]  。
3．数据逻辑结构的4种基本形态包括集合结构、  [1]  结构、  [2]  结构和  [3]  结构。
4．一个正确的算法应该具有5个特性：[1]  、  [2] 、[3]  、  [4]  和  [5]  。
5．数据的存储结构包括顺序、  [1]  、  [2]  和  [3]  四种。
6．一个数据结构在计算机中的映象称为  [1]  。
7．一个算法的效率主要是指该算法的  [1]  效率和  [2]  效率。
8．以下程序段的时间复杂度T（n）=        。 
sum=0;
for(i=0 ; i<n; i++)
for( j=0; j<n; j++)
sum+=a[i][j];
printf("%d\n",sum);
四、算法及分析
1．写出交换两个整型变量值的算法，并分析算法的时间复杂度。
2．写出求n的阶乘 的算法，并分析算法的时间复杂度。
第2章  线性表
一、简答题
1．在处理某个问题时，需要存储的数据总量不能确定，并经常需要进行数据的添加和删除操作，此时应选用哪种存储结构？为什么？
2、简述头指针、头结点的区别，以及头指针和头结点的作用。
二、选择题
1．以下链表结构中，从当前结点出发能够访问到任一结点的是
A）单向链表和双向链表    B）双向链表和循环链表
C）单向链表和循环链表    D）单向链表、双向链表和循环链表
2．线性表是具有n个        的有限序列。
A）数据项  B）数据元素  C）表元素  D）字符
3．若长度为n的线性表采用链式存储结构，访问其第i个元素的算法时间复杂度为
A）O(1)  B）O(n)    C） O(n2)  D）O(log2n)
4．在长度为n的顺序表中，若要删除第i（1≤i≤n）个元素，则需要向前移动的元素的次数为 
A）i    B）n-i  C）n-i+1    D）n-i-1
5．在长度为n的顺序表中第i（1≤i≤n）个位置上插入一
个元素时，为留出插入位置所需移动元素的次数为
A）n-i    B）i  C）n-i+1    D）n-i-1
6．下述哪一条是顺序存储结构的优点？
A．存储密度大  B．插入运算方便  C．删除运算方便  D．可方便地用于各种逻辑结构的存储表示
7．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（    ）存储方式最节省时间。
A．顺序表      B．双链表        C．带头结点的双循环链表    D．单循环链表
8. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（    ）(1<=i<=n+1)。
A. O(0)      B. O(1)        C. O(n)          D. O(n2)
三、填空题
1．有一单链表结构如下：
              图2-1  填空题1附图
若要删除值为C的结点，应做的操作是        。
2．线性表L=( a1,a2,...an)用数组存储。假定删除表中任一元素的概率相同，则删除一个元素平均需要移
动的元素个数是        。
3．设有结点定义
  　struct node
    {  int  data;
        struct node  *next;
    };
且已建立如图2-2所示的带有头结点的单向链表：
              图2-2  填空题3附图
函数sum的功能是：计算非空的链表中各结点数据域之和，并用函数值返回该结果。请填空。
  　int sum(struct node *head)
  　{  int s=0;
      struct node *p;
    　p=head->next;
      do
      {  s=s+    [1]  ;
          p=p->next;
        }
      while ( p!=    [2]  );
      return s;
  　}
4. 带头结点的双循环链表L中只有一个数据结点的判定条件是：________。
5. 在单链表L中，指针p所指结点有后继结点的判定条件是：__  。
6. 带头结点的单循环链表L为空表的条件是：________。
7. 在单链表p结点之后插入s结点的操作是：_______。
四、算法设计
*1．有序顺序表、单链表的插入算法。
设线性表有序（按由小到大的顺序排列），分别编写顺序表、带有头结点的单链表的插入算法，使插入值为x的元素后线性表仍保持有序的算法。
*2．单链表的输出算法：输出带有头结点的单向链表中各结点的值。
*3．顺序表、单链表的删除算法：分别编写顺序表、带有头结点的单链表中删除所有值为x的结点的算法。
4．顺序表、单链表的逆置算法：分别实现顺序表、带有头结点的单链表的逆置操作。即将线性表（a1,a2,...an）逆置为（an,...a2,a1）。
5．顺序表、单链表的查算法：分别实现顺序表、带有头结点的单链表中查最后一个值为x的结点位置的算法。
6．写出求单链表、循环单链表表长的算法。
7．有序顺序表、有序单链表的归并算法。
分别编写将两个有序顺序表、两个带有头结点的单链表归并成一个有序线性表（按由小到大的顺序排列）的归并算法，要求尽量利用原来的存储空间。
8. 设L为单链表的头结点地址，单链表中数据结点的数据都是正整数且无相同的，试设计利用直接插入的原则把该链表整理成数据递增的有序单链表的算法。
9. 已知线性表（a1 a2 a3 ...an）按顺序存于内存中，每个元素都是整数，试设计用最少时间把所有值为负数的元素移到全部正数值元素前边的算法：例：（x,-x,-x,x,x,-x ...x）变为（-x,-x,-x...x,x,x），其中x>0。
第三章
请设计算法：
利用栈结构和栈的基本运算将一个十进制数转换成指定的k（k=2~9）进制数。
第6章树
例题分析与解答
例6.1 设有一棵树的度为3，其中度为1、2、3的结点个数分别为5、2、1、，则这棵树中叶子结点的个数为
A）4 B）5 C）6 D）7
【解答】
  设这棵树中叶子结点的个数为n0，根据已知，在这棵树中结点的总数n=5+2+1+ n0=8+ n0；此外，从树的性质又可知，度为1的结点有1个分?В任?2的结点有2个分支，度为3的结点则有3个分支，因此这棵树的总的分支数为：1*5+2*2+3*1=12，而一棵有n个结点的树，只允许有n-1个分支存在，所以又有：n-1=12，即n=13，将n代入上式，则n0=5。所以，选项B是正确的。
例6.2 一棵权值为1，2，3，4，5，6的哈夫曼树，如图6-1所示，其中方框为带权的叶子结点，圆圈为非叶子结点。则该哈夫曼树的带权路径长度WPL，及权值为1的叶子结点的高度分别为
A）51；5 B）72；5 C）51；4 D）72；4
图6-1 例6.2附图哈夫曼树
【解答】
其
中n表示叶子结点的数目，wi表示叶结点的权值，li表示根到叶结点之间的路径长度。因此有：
WPL= (1+2)*4+3*3+ (4+5+6)*2=51。权值为1的叶结点的高度很明显为5。所以，本题的答案为选项A。
例6.3 假设已知某二叉树的前序遍历序列和后序遍历序列，则根据已知条件一定能唯一地确定出一棵二叉树。请问这句话对吗？
【解答】错。
  例如某二叉树的前序遍历序列为：AB；后序遍历序列为BA；根据条件可以画出如图6-2所示的两棵不同的二叉树。因此已知前序和后序遍历序列，并不能唯一地确定出一棵二叉树。
图6-2 例6.3附图
6 自测习题
1. 简答题
1. *根据权值（1，2，3，4，5，6），构造哈夫曼树，并计算二叉树的带权路径长度。
2. 请
将下图6-1所示的森林转换成二叉树。
图6-1 简答题2的附图森林
3. *已知一棵二叉树的中序遍历序列为DHBEAIFCGJK，该二叉树的后序遍历序列是HDEBIFJKGCA，现请画出这棵二叉树。
4. *给出图6-2所示的
一棵二叉树的顺序存储结构、二叉链表和三叉链表存储结构。
图6-2 简答题4的附图二叉树
2. 判断题
1. 由树转化为二叉树，其根结点的右子树总是空的。 （ ）
2. 若有一个结点是某二叉树的前序遍历序列中的第一个结点，则它也一定是这棵二叉树的中序遍历序列中的第一个结点。 （ ）
3. 若一个树叶是某二叉树的前序遍历序列中的最后一个结点，则它也一定是这棵二叉树的中序遍历序列中的最后一个结点。 （ ）
4. 若一个树叶是某二叉树的中序遍历序列中的最后一个结点，则它也一定是这棵二叉树的前序遍历序列中的最后一个结点。 （ ）
5. 在二叉树中，具有一个子女的父结点，在中序遍历序列中没有后继结点。而具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有一个子女结点。（ ）
6. 虽然已知二叉树的前序遍历和中序遍历序列，但还不能唯一确定出这棵二叉树，因为并不知道二叉树的根结点是哪一个。 （ ）
7. 在满二叉树中，存在度为1的结点。 （ ）
8. 在任意一棵二叉树中，终端结点的个数等于度为２的结点个数加１。 （ ）
9. 前序遍历序列与中序遍历序列完全相同的二叉树有：空二叉树或任一结点均无左子树的非空二叉树。 （ ）
3.选择题
1. 如果结点A是结点B的双亲，而且结点Ｂ有４个兄弟，则结点A的度是
A）2 B）3 C）4 D）5
2. 设有一棵二叉树，其１度结点有m个，２度结点有n个，则该二叉树的结点总数为
A）m+n B）2*m+n C）m+2*n D）m+2*n+1
3. 设有一棵二叉树，其先序遍历序列是：ABCDEFG，中序遍历序列是：CBDAFEG，则该二叉树的后序遍历序列是
A）CDBFGEA B）CDFGBEA C）CDBAFGE D）CDBFEGA
4. 设有13个值，由它们组成一棵哈夫曼树，则该哈夫曼树中结点个数共有。
A）13 B）12 C）26 D）25
5. 设电文中出现的字母为A、B、C、D和E，每个字母在电文中出现的次数分别为：6，23，3，5和12，按哈夫曼编码，则字母C的编码应是
A）10 B）110 C）1110 D）1111
6. 已知一棵二叉树的先序遍历序列为EFHIGJK，中序遍历序列为HFIEJGK，则该二叉树根的右子树的根是
A）E B）F C）G D）J
7. 设结点A有左孩子结点B，右孩子结点C，则在先序遍历、中序遍历、后序遍历这三种基本遍历序列中B一定是C的
A） 前驱 B）后继 C）相邻结点 D）不相邻结点
4. 填空题
1. 采用二叉链式存储结构，具有n个结点的二叉树中，一共有 [1] 个指针域，其中 [2] 个指针域为空。
2. 一棵非空的二叉树，其第i层上最多有＿＿＿＿＿个结点。
3. 满二叉树是一棵深度为k的且恰好有＿＿＿＿＿个结点的二叉树。
4. 将一棵完全二叉树按层次编号，对任一编号为i的
结点有：如该结点有左孩子，则其编号为 [1] ；如该结点有右孩子，则其编号为 [2] 。
5. 设一棵二叉树中只有叶子结点和左、右子树都非空的结点，如果叶子结点的个数是m，则左、右子树都非空的结点个数是＿＿＿＿＿
6. 设有一棵树（如图6-3所示），请回答下列问题：
根结点是＿[1]＿；叶子结点有＿＿[2] ＿＿；Ｅ的双亲是＿[3]＿；Ｆ的祖先是＿[4]＿；Ｇ的孩子是＿[5]＿；Ｄ的孩子是＿[6]＿；Ｅ的子孙有＿＿[7]＿＿；Ｄ的兄弟是＿[8]＿；Ｂ的兄弟是＿[9]＿；结点Ｈ的层数是＿[10]＿；树的深度是＿[11]＿；Ｅ为根的子树深度是＿[12]＿；这棵树的度是＿[13]＿。
图6-3 填空题6的附图
7. 现有一表达式 ( a+b )*c-d / e，写出该表达式的波兰式＿＿[1]＿＿，以及逆波兰式＿＿[2]＿＿。
4. 算法设计题
*1 试编写一个递归算法，用于计算二叉树的叶子结点数。要求二叉树为链式存储结构。
2 试编写一个求结点P的双亲的算法，要求二叉树为链式存储结构，且该二叉树中的结点值均不相同。
若无结点P，则打印"No Point"；若结点P是根结点，则打印"No Parent"；若有结点P，则输出其双亲结点的值。
3 试编写一个算法，用于出结点数值为x的结点的所有祖先结点的数值。假定这棵二叉树各结点的数值都不相等，二叉树为链式存储结构。
4 试编写一个按层次顺序遍历二叉树的算法，假定二叉树采用链式存储结构。
5 试编写一个非递归的后序遍历算法，并计算该二叉树的所有结点个数。
??
??
??
??