数据结构作业题及参考答案.doc

东北农业大学网络教育学院
数据结构作业题（一）
一、选择题（每题2分，共20分）
1．在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（ ）。
A、O(n) B、O (n/2) C、O (1) D、O (n2)
2．带头结点的单链表first为空的判定条件是（ ）。
A、first == NULL; B、first->link == NULL;
C、first->link == first; D、first != NULL;
3．在一棵树中，（ ）没有前驱结点。
A、分支结点 B、叶结点 C、树根结点 D、空结点
4．在有向图中每个顶点的度等于该顶点的（ ）。
A、入度 B、出度
C、入度与出度之和 D、入度与出度之差
5．对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（ ）的值除以9。
A、20 B、18 C、25 D、22
6．下列程序段的时间复杂度为（ ）。
s=0；
for(i=1；i<n；i++)
for(j=1；j<n；j++)
s+=i*j；
A、O (1) B、O (n) C、O (2n) D、O (n2)
7．栈是一种操作受限的线性结构，其操作的主要特征是（ ）。
A、先进先出 B、后进先出 C、进优于出 D、出优于进
8．假设以数组A[n]存放循环队列的元素，其头、尾指针分别为front和rear。若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为（ ）。
A、(rear-front-1)％n B、(rear-front)％n
C、(front-rear+1)％n D、(rear-front+n)％n
9．高度为5的完全二叉树中含有的结点数至少为（ ）。
A、16 B、17 C、31 D、32
10．如图所示有向图的一个拓扑序列是( )
A、ABCDEF
B、FCBEAD
C、FEDCBA
D、DAEBCF
二、填空题（每空1分，共20分）
1．n (n﹥0) 个顶点的无向图最多有 条边，最少有 条边。
2．在一棵AVL树中，每个结点的左子树高度与右子树高度之差的绝对值不超过 。
3．已知8个数据元素为（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为 。
4．在二叉树的第i层上至多有 结点。
5．对于一棵具有n个结点的二叉树，若一个结点的编号为i(1≤i≤n)，则它的左孩子结点的编号为 ，右孩子结点的编号为 ，双亲结点的编号为 。
6．数据的存储结构被分为 、 、 和 四种。
7．假定一棵树的广义表表示为A(B(C,D(E,F,G),H(I,J)))，则树中所含的结点数为 个，树的深度为 ，树的度为 。
8．在一个具有n个顶点的无向图中，要连通所有顶点则至少需要 条边。
9．在线性结构、树形结构和图形结构中，前驱和后继结点之间分别存在着 、
和 的联系。
10．一棵含999个结点的完全二叉树的深度为 。
三、运算题（每题5分，共10分）
1．设有一个10´10的对称矩阵A，将其下三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么A[8][5]存放于B中什么位置。

2．已知一个有序表 ( 15, 26, 34, 39, 45, 56, 58, 63, 74, 76, 83, 94 ) 顺序存储于一维数组a[12]中，根据折半搜索过程填写成功搜索下表中所给元素34, 56, 58, 63, 94时的比较次数。
元素值
34
56
58
63
94
比较次数

四、应用题（每题10分，共50分）
1．设待排序的记录共7个，排序码分别为8，3，2，5，9，1，6。
（1）用直接插入排序。试以排序码序列的变化描述形式说明排序全过程（动态过程）要求按递减顺序排序。
（2）用直接选择排序。试以排序码序列的变化描述形式说明排序全过程（动态过程）要求按递减顺序排序。

2．判断下列序列是否是堆（可以是小堆，也可以是大堆，若不是堆，请将它们调整为堆）。
（1）100，85，98，77，80，60，82，40，20，10，66
（2）100，98，85，82，80，77，66，60，40，20，10
（3）100，85，40，77，80，60，66，98，82，10，20
（4）10，20，40，60，66，77，80， 82，85，98，100

3．试找出分别满足下列条件的所有二叉树。
1）先序序列和中序序列相同 2）中序序列和后序序列相同
3）先序序列和后序序列相同 4）中序序列与层次遍历序列相同

4．设T是一棵二叉树，除叶子结点外，其它结点的度数皆为2，若 T中有6个叶结点，试问：
（1）T树的最大深度Kmax=?最小可能深度Kmin=?
（2）T树中共有多少非叶结点？
(3) 若叶结点的权值分别为1,2,3,4,5,6。请构造一棵哈曼夫树，并计算该哈曼夫树的带权路径长度wpl。

5．一棵有n(n>0)个结点的d度树，若用多重链表表示，树中每个结点都有d个链域，则在表示该树的多重链表中有多少个空链域? 为什么?
储，则A[7,1]和A[2,4]的第一个字节的地址是多少？

数据结构作业题（二）
一、选择题（每题2分，共20分）
1．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（ ）。
A、HL=p; p->next=HL; B、p->next=HL; HL=p;
C、p->next=HL; p=HL; D、p->next=HL->next; HL->next=p;
2．由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ ）。
A、24 B、48 C、72 D、53
3．一个数组元素a[i]与（ ）的表示等价。
A、*(a+i) B、a+i C、*a+i D、&a+i
4．下面程序段的时间复杂度为（ ）。
for(int i=0; i<m; i++)
for(int j=0; j<n; j++)
a[i][j]=i*j;
A、O(m2) B、O(n2) C、O(m*n) D、O(m+n)
5．数据结构是（ ）。
A、一种数据类型
B、数据的存储结构
C、一组性质相同的数据元素的集合
D、相互之间存在一种或多种特定关系的数据元素的集合
6．在线性表的下列运算中，不改变数据元素之间结构关系的运算是（ ）。
A、插入 B、删除 C、排序 D、定位
7．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（ ）。
A、3，2，6，1，4，5 B、3，4，2，1，6，5
C、1，2，5，3，4，6 D、5，6，4，2，3，1
8．在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（ ）。
A、不一定相同 B、都相同 C、都不相同 D、互为逆序
9．图的邻接矩阵表示法适用于表示（ ）。
A、无向图 B、有向图 C、稠密图 D、稀疏图
10．若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字b的过程中，先后进行比较的关键字依次为（ ）。
A、f,c,b B、f,d,b C、g,c,b D、g,d,b
二、填空题（每空2分，共40分）
1．含n个顶点的无向连通图中至少含有 条边。
2．若对关键字序列（43，02，80，48，26，57，15，73，21，24，66）进行一趟增量为3的希尔排序，则得到的结果为 。
3．一个算法的时间复杂度为(3n2+2nlog2n+4n-7)/(5n)，其数量级表示为 。
4．在以HL为表头指针的带表头附加结点的单链表和循环单链表中，链表为空的条件分别为 和 。
5．快速排序在平均情况下的时间复杂度为 ，在最坏情况下的时间复杂度为 。
6．假定对长度n=50的有序表进行二分查找，则对应的判定树高度为________，判定树中前5层的结点数为________，最后一层的结点数为________。
7．假定一棵树的广义表表示为A(B(C,D(E,F,G),H(I,J)))，则度为3、2、1、0的结点数分别为 、 、 和 个。
8．在一棵二叉树中，假定双分支结点数为5个，单分支结点数为6个，则叶子结点数为 个。
9．数据的逻辑结构被分为 、 、 和 四种。
10．在一个长度为n的顺序存储线性表中，向第i个元素(1≤i≤n+1)之前插入一个新元素时，需要从后向前依次后移 个元素。
三、应用题（每题10分，共60分）
1．设有5个互不相同的元素a、b、c、d、e，能否通过7次比较就将其排好序？如果能，请列出其比较过程；如果不能，则说明原因。

2．有一随机数组(25,84,21,46,13,27,68,35,20),现采用某种方法对它们进行排序,其每趟排序结果如下, 则该排序方法是什么?
初 始:25,84,21,46,13,27,68,35,20 第一趟:20,13,21,25,46,27,68,35,84
第二趟:13,20,21,25,35,27,46,68,84 第三趟:13,20,21,25,27,35,46,68,84

3．请在（ ）内填入正确的排序方法。
设一数组中原有数据如下：15，13，20，18，12，60。下面是一组由不同排序方法进行一遍排序后的结果。
（ ）排序的结果为：12，13，15，18，20，60
（ ）排序的结果为：13，15，18，12，20，60
（ ）排序的结果为：13，15，20，18，12，60

4．设T是一棵二叉树，除叶子结点外，其它结点的度数皆为2，若 T中有6个叶结点，试问：
（1）T树的最大深度Kmax=?最小可能深度Kmin=?
（2）T树中共有多少非叶结点？
(3) 若叶结点的权值分别为1,2,3,4,5,6。请构造一棵哈曼夫树，并计算该哈曼夫树的带权路径长度wpl。

5．一棵有n(n>0)个结点的d度树，若用多重链表表示，树中每个结点都有d个链域，则在表示该树的多重链表中有多少个空链域? 为什么?

6．有一个二维数组A[0:8,1:5]，每个数组元素用相邻的4个字节存储,存储器按字节编址，假设存储数组元素A[0,1]的第一个字节的地址是0，那么存储数组的最后一个元素的第一个字节的地址是多少？若按行存储,则A[3,5]和A[5,3]的第一个字节的地址是多少？若按列存储，则A[7,1]和A[2,4]的第一个字节的地址是多少？

数据结构作业题（三）
一、单选题（每题2分，共10分）
1、在长度为n的顺序存储的线性表中，删除第i个元素（1≤i≤n）时，需要从前向后依次前移 个元素。
A、n-i B、n-i+1 C、n-i-1 D、i
2、设一个广义表中结点的个数为n，则求广义表深度算法的时间复杂度为 。
A、O(1) B、O(n) C、O(n2) D、O(log 2 n)
3、假定一个顺序队列的队首和队尾指针分别为f和r，则判断队空的条件为 。
A、f+1==r B、r+1==f C、f==0 D、f==r
4、由3 个结点可以构造出多少种不同的二叉树 。
A、2 B、3 C、4 D、5
5、适用于折半查找的表的存储方式及元素排列要求为 。
A、链接方式存储，元素无序 B．链接方式存储，元素有序
C、顺序方式存储，元素无序 D．顺序方式存储，元素有序
二、填空题（每空1分，共25分）
1、在线性结构、树结构和图结构中，前驱和后继结点之间分别存在着 、
和 的联系。
2、在线性表的单链接存储中，若一个元素所在结点的地址为p，则其后继结点的地址为 ，若假定p为一个数组a中的下标，则其后继结点的下标为 。
3、在初始化一个稀疏矩阵的函数定义中，矩阵形参应说明为 参数。
4、栈又称为 表，队列又称为 表。
5、后缀表达式“4 5 + 3 * 2 4 + * ”的值为 。
6、一棵深度为5的满二叉树中的结点数为 个，一棵深度为3的满四叉树中的结点数为 个。
7、对于一棵含有40个结点的理想平衡树，它的高度为 。
8、从一棵二叉搜索树中查找一个元素时，若元素的值等于根结点的值，则表明 ，若元素的值小于根结点的值，则继续向 查找，若元素的值大于根结点的值，则继续向 查找。
9、对于一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵大小为 。
10、对于一个具有n个顶点和e条边的连通图，其生成树中顶点数和边数分别为
和 。
11、二分查找过程所对应的判定树既是一棵 ，又是一棵 。
12、在归并排序中，进行每趟归并的时间复杂度为 ，整个排序过程的时间复杂度为 ，空间复杂度为 。
13、给定一组数据{6，2，7，10，3，12}以它构造一棵哈夫曼树，则树高为__________，带权路径长度WPL的值为__________。
三、运算题（每题6分，共24分）
1、假定一棵普通树的广义表表示为 a(b(e),c(f(h,i,j),g),d)，分别写出先根、后根、按层遍历的结果。
先根： 。
后根： 。
按层： 。
2、已知一个带权图的顶点集V和边集G分别为：
V = { 0，1，2，3，4，5，6，7}；
E = {（0，1）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13，
（3，5）9，（3，6）10，（4，6）4，（5，7）20 }；
则求出该图的最小生成树的权。
最小生成树的权： 。
3、对于线性表（18,25,63,50,42,32,90,66）进行散列存储时，若选用H(K)=K%9作为散列函数，则散列地址为0的元素有 个，散列地址为3的元素有 个，散列地址为5的元素有 个。
4、假定一组记录的排序码为（46，79，56，38，40，80，25，34），在对其进行快速排序的过程中，对应二叉搜索树的深度为 ，分支结点数为 。
四、阅读算法（第一题7分，第二题8分）
1、void AA(LNode * & HL)
{
InitList(HL);
InsertRear(HL,30);
InsertRear(HL,50);
int a[5] = {15,8,9,26,12};
for ( int i=0; i<5; i++ ) InsertFront(HL,a[i]);
}
该算法被调用执行后，得到的以HL为表头指针的单链表中的数据元素依次为： 。

2、void AH(Heap & HBT , const ElemType item)
// HBT为一个小根堆
{
HBT.heap[HBT.size]=item;
HBT.size++;
ElemType x=item
int i=HBT.size-1;
while ( i != 0 ){
int j=(i-1)/2;
if ( x>=HBT.heap[j]) break;
HBT.heap[i]=HBT.heap[j];
i=j;
}
HBT.heap[i]=x;
}
该算法的功能为： 。
五、算法填空，在画有横线的地方填写合适的内容。（12分）
从一维数组A[n]中二分查找关键字为K的元素的递归算法，若查找成功则返回对应元素的下标，否则返回-1。
int Binsch( ElemType A[] , int low , int high , KeyType K )
{
if ( low<=high )
{
int mid = (low+high)/2;
if ( K==A[mid].key) ;
else if (K<A[mid].key ) ;
else ;
}
else return -1;
}
六、编写算法（14分）
编写在以BST为树根指针的二叉搜索树上进行查找值为item的结点的非递归算法，若查找成功则由item带回整个结点的值并返回true，否则返回false。
bool Find( BTreeNode * BST , ElemType & item )

数据结构作业题（四）
一、选择题（每题2分，共20分）
1．从逻辑上可以把数据结构分为（ ）两大类。
A．动态结构、静态结构 B．顺序结构、链式结构
C．线性结构、非线性结构 D．初等结构、构造型结构
2．以下数据结构中，哪一个是线性结构（ ）？
A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串
3．连续存储设计时，存储单元的地址（ ）。
A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续
4．若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ）。
A. O(0) B. O(1) C. O(n) D. O(n2)
5．在双向链表指针p的结点前插入一个指针q的结点操作是（ ）。
A. p->Llink=q;q->Rlink=p;p->Llink->Rlink=q;q->Llink=q；
B. p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink;
C. q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q;
D. q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q;
6．若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（ ）。
A. i-j-1 B. i-j C. j-i+1 D. 不确定的
7．有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ ）
A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6
8．用链接方式存储的队列，在进行删除运算时（ ）。
A. 仅修改头指针 B. 仅修改尾指针
C. 头、尾指针都要修改 D. 头、尾指针可能都要修改
9．若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( )
A. 1和 5 B. 2和4 C. 4和2 D. 5和1
10．栈和队列的共同点是（ ）。
A. 都是先进先出 B. 都是先进后出
C. 只允许在端点处插入和删除元素 D. 没有共同点
二、填空题（每空2分，共30分）
1．数据结构中评价算法的两个重要指标是 和 。
2．一个算法具有5个特性: 、 、 ，有零个或多个输入、有一个或多个输出。
3．在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动________个元素。
4．对于双向链表,在两个结点之间插入一个新结点需修改的指针共 ______个，单链表为_______个。
5．设数组a[1..50,1..80]的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45,68]的存储地址为_ _;若以列序为主序顺序存储，则元素a[45,68]的存储地址为_ _。
6．所谓稀疏矩阵指的是_______。
7．广义表的_______ 定义为广义表中括弧的重数。
8．具有256个结点的完全二叉树的深度为______。
9．已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有______个叶子结点。
10．高度为8的完全二叉树至少有______个叶子结点。
三、计算题（每题6分，共30分）
1．如果输入序列为1 2 3 4 5 6,试问能否通过栈结构得到以下两个序列:4 3 5 6 1 2和1 3 5 4 2 6;请说明为什么不能或如何才能得到。

2．假定一棵二叉树广义表表示为a(b(c),d(e,f))，分别写出对它进行先序、中序、后序、按层遍历的结果。
先序：
中序：
后序：
按层：

3．已知一个图的顶点集V和边集G分别为：V={0,1,2,3,4,5,6,7};
　E={(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(3,6)10, (4,6)4,(5,7)20,(6,7)30};
　　按照普里姆算法从顶点0出发得到最小生成树，试写出在生成最小生成树的过程中依次得到的各条边。
　　________, ________, ________, ________, ________, ________, ________。

4. 已知一个图的顶点集V和边集G分别为：
　V={0,1,2,3,4,5,6,7,8};
　E={<0,2>,<1,3>,<1,4>,<2,4>,<2,5>,<3,6>,<3,7>,<4,7>,<4,8>,<5,7>,<6,7>,<7,8>};
若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，则按主教材中介绍的进行拓扑排序的算法，写出得到的拓扑序列（提示：先画出对应的图形，然后再运算）。
拓扑序列：

5．假定一组记录的排序码为(46,79,56,38,40,80,25,34)，则对其进行快速排序的第一次划分后的结果为________________。

四、算法填空（10分）
1．

五、编程（10分）
1．设计算法以求解从集合{1..n}中选取k（k<=n）个元素的所有组合。例如，从集合{1..4}中选取2个元素的所有组合的输出结果为：1 2，1 3，1 4，2 3， 2 4，3 4。

数据结构作业题（五）
一、选择题（每题2分，共20分）
1．若需要利用形参直接访问实参，则应把形参变量说明为（ ）参数。
A指针 B引用 C值
2．在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行（ ）。
A q一>next=p一>next；p一>next=q；
B p一>next=q一>next；q=p；
C 9一>next=p一>next；p一>next=q；
D p一>next=q一>next；q一>next=p；
3．在一个顺序队列中，队首指针指向队首元素的（ ）位置。
A前一个 B后一个 C当前
4．向二叉搜索树中插入一个元素时，其时间复杂度大致为（ ）。
A O（1） B O（1og2n）
C O（n） D O（nlog2n）
5．假设有两个串A和B，求B在A中首次出现的位置的操作，我们称为（ ）。
A.连接 B.模式匹配 C.求子串 D.求串长
6．我们对记录进行排序的目的是（ ）。
A.分类 B.合并 C.存储 D.查找
7．在最坏的情况下，冒泡排序法的时间复杂度为（ ）。
A.O(lgn) B.O(nlgn) C.O(n2) D.O(n)
8．广义表(A,B,E,F,G)的表尾是（ ）。
A.(B, E , F, G) B.( ) C.（A，B， E，F，G) D.（G）
9．线性表如果采用链式存储结构，要求内存中的存储单元的地址（ ）。
A.必须是连续的
B.部分要求是连续的
C.一定不是连续的
D.可以是连续的，也可以是不连续的
10．在数据结构中，从逻辑结构上，我们可以把数据结构分为（ ）。
A.线性结构和非线性结构
B.内部结构和外部结构
C.顺序结构和链式结构
D.动态结构和静态结构
二、填空题（每空1分，共25分）
1．数据的逻辑结构被分为 、 、 和 四种。
2．对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为 ，在表尾插入元素的时间复杂度为 。
3．在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的 、 和
三项。
4．在广义表的存储结构中，每个结点均包含有 个域。
5．当用长度为N的数组顺序存储一个栈时，假定用top = =N表示栈空，则表示栈满的条件为 。
6．假定一棵三叉树的结点个数为50，则它的最小深度为 ，最大深度为 。
7．在一棵二叉树中，第5层上的结点数最多为 。
8．在一个小根堆中，堆顶结点的值是所有结点中的 ，在一个大根堆中，堆顶结点的值是所有结点中的 。
9．在一个具有n个顶点的无向圄中，要连通所有顶点则至少需要 条边。
10．假定一个图具有n个顶点和e条边，贝采用邻接矩阵、邻接表和边集数组表示时，其相应的空间复杂度分别为 、 和 。
11．以二分查找方法查找一个线性表时，此线性表必须是 存储的 表。
12．在索引表中，若一个索引项对应主表中的一条记录，则称此索引为 表。
13．快速排序在平均情况下的空间复杂度为 ，在最坏情况下的空间复杂度为 。
三、运算题（每题5分，共20分）
1．假定一个大堆为（56，38，42，30，25，40，35，20），则依次从中删除两个元素后得到的堆为 。
2．已知一个图的顶点集V和边集6分别为：
V={0，1，2，3，4，5，6，7}；
E={（04）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13，（3，5）9，（3，6）10，（4，6）4，（5，7）20}；
按照克鲁斯卡尔算法得到最小生成材，拭写出在最小生成树中依次得到的各条边。
， ， ， ， ， ， 。
3．假定一组数据的初始堆为（84，79，56，42，40，46，50，38），请写出在堆排序阶段进行前三次对换和筛运算后数据的排列情况。
数据排列情况： 。
4．假定一组记录的徘序码为（46，79，56，38，40，80，36，40，75，66，84，24），对其进行归并排序的过程中，第三趟归并后的结果为： 。
四、阅读算法，回答问题（每题5分，共10分）
1．void AA （List＆L）
{
InitList（L）；
InsertRear （L，30）；
InsertFront（L，50）；
int a [4]={5，8，12，15}
for（int i=0；1＜4；i＋＋＝ InsertRear（L，a [i]）；
}
该算法被调用执行后，得到的线性表L为： 。
2．void AF（Queue＆Q）
{
InitQueue（Q）：
int a [4]={5，8，12，15}
for（int i一0；i＜4；i斗＋＝ Qlnsert（Q，迁6）；
QInsert（Q，QDelete（Q））；
QInsert（Q，30）；
QInsert（Q，QDelete（Q）＋10）；
whi1e（！QueueEmpty（Q）） cout＜＜QDeleie（Q）＜＜”；
}
该算法被调用后得到的输出结果为： 。

五、算法填空，在画有横线的地方填写合适的内容（10分）
从一维数组A[n]上进行快速排序的递归算法。
void QuickSort（ElemType A [ ]， int s， int t）
{
int i=s j=t十1；
ElemType x=A[s]；
d0｛
do i++； while ；／／填写一个循环条件
do j - - ； while（A [ j ] ．stn＞x．stn）；
if（I<j）
{ ElemType temp = A［i］；A［i］= A［j］；A［j］＝temp；}
} while（i＜j）；
A[s]=A[j]；A[j]=x；
if（s＜i一1） ；
if（j十1＜t） ；
}
六、编写算法（15分）
编写一个递归算法，统计并返回以BT为树根指针的二叉树中的叶子结点的个数。
int Count（BTreeNode*BT）

东北农业大学网络教育学院
数据结构作业题参考答案
习题一参考答案
一、选择题（每题2分，共20分）
1
2
3
4
5
6
7
8
9
10
A
B
C
C
C
D
B
B
A
B
二、填空题（每题1分，共20