国家开放大学电大《数据结构》期末题库及答案.docx

最新国家开放大学电大《数据结构》期末题库及答案
考试说明：本人针对该科精心汇总了历年题库及答案，形成一个完整的题库，并旦每年都在更新。该题库 对考生的复习、作业和考试起着非常重要的作用，会给您节省大量的时间。做考题时，利用本文档中的查 找工具，把考题中的关键字输到查找工具的查找内容框内，就可迅速查找到该题答案。本文库还有其他网 核及教学考一体化答案，敬请查看。
《数据结构》题库及答案一
一、单项选择题
1. 给定有n个元素的向量，建立一个有序单链表的时间复杂度是（C ）o
A. 0（1） B. 0（n）
C. 0（n2） D. 0（nlog2n）
2. 带表头的双向循环链表的空表满足（B ）o
A. first =NULL; B. first->rLink==first
C. first->lLink==NULL D. first->rLink~NULL
3. 栈的插入和删除操作在（A ）进行。
A.栈顶B.栈底C.任意位置D.指定位置
4. 在一个顺序存储的循环队列中，队头指针指向队头元素的（A ）位置。
A.前一个B.后一个C.当前D.后面
5. 假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear,则判断队空的条件为（D）。
A. front+1 = rear B. rear+1 二二 front
C. front = 0 D. front == rear
6. 设链式栈中结点的结构为（data, link）,旦top是指向栈顶的指针。若想摘除链式栈的栈顶结点，并 将被摘除结点的值保存到x中，则应执行（A ）操作。
A. x=top->data; top=top->link; B. top=top->link; x=top->data;
C. x=top; top=top->link; D. x=top->data;
7. 为增加内存空间的利用率和减少溢出的可能性，由两个栈共享一块连续的内存空间时，应将两栈的
（D ）分别设在这块内存空间的两端。
A.长度B.深度C.栈顶D.栈底
8. 在系统实现递归调用时需利用递归工作记录保存（C ）,当递归调用程序执行结束时通过它将控制转 到上层调用程序。
A.调用地址B.递归入口 C.返回地址D.递归出口
9. 如果一个递归函数过程中只有一个递归语句，而且它是过程体的最后语句，则这种递归属于(D ), 它很容易被改写为非递归过程。
A.单向递归B.回溯递归C.间接递归D.尾递归
10. 设有一个广义表A (a),其表尾为(C )o
A. a B. ( ( ) ) C. () D. (a)
11. 对于一组广义表 A( ), B(a, b), C(c, (e,f,g)), D(B, A, C), E (B, D),其中的 E 是(D )。
A.线性表B.纯表C.递归表D.再入表
12. 在一棵树中，(C )没有前驱结点。
A.树枝结点B.叶子结点C.树根结点D.空结点
13. 在一棵具有n个结点的二叉树的第i层上(假定根结点为第0层，i大于等于0而小于等于树的高度)， 最多具有(A )个结点。
A. 2i B. 2i+l C. 2i-l D. 2n
二、 填空题
1. 链表与顺序表、索引表、散列表等都是数据逻辑结构的(存储)表示。
2. 队列是一种限定在表的一端插入，在另一端删除的线性表，它又被称为(先进先出)表。
3. 向一个顺序栈插入一个元素时，首先使(栈顶指针)后移一个位置，然后把待插入元素写入到这个位 置上。
4. 向一个循环队列中插入元素时，需要首先移动(队尾)指针，然后再向所指位置写入新元素。
5. 在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列至多有(1)个结点。
6. 递归工作栈起到两个作用，其一是将递归调用时的实际参数和返回地址传递给下一层递归；其二是保 存本层的形式参数和(局部变量)。
7. 非空广义表的除第一个元素外其他元素组成的表称为广义表的(表尾)。
8. 广义表的深度定义为广义表括号的(重数)。
9. 一棵树的广义表表示为a(b(c, d(e, f), g(h)), i (j, k(x, y))),结点f的层数为(3)。假定树根结点的层 数为0。
10. 在一棵三叉树中，度为3的结点数有2个，度为2的结点数有1个，度为1的结点数为2个，那么度 为0的结点数有(6)个。
11. 一棵二叉树中，假定双分支结点数为5个，单分支结点数为6个，则叶子结点数为(6)个。
12. 在一棵高度为h的理想平衡二叉树中，最多含有(2h+l-l)个结点。假定树根结点的高度为0。
三、 判断题(对/错)
1. 在用单链表表示的链式队列Q中，队头指针为Q->front,队尾指针为Q->rear,则队空条件为Q->front =Q->rearo 错
2递归调用算法与相同功能的非递归算法相比，主要问题在于重复计算太多，而且调用本身需要分配额外 的空间和传递数据和控制，所以时间与空间开销通常都比较大。对
3将f = 1 + 1/2 + 1/3+…+ 1/n转化为递归函数时，递归部分为f (n) = f (n-1) + 1/n,递归结束 条件为f (1) = 1。对
4. 一个广义表((a), ( (b), c), (((d))))的长度为3,深度为4。对
5. 当从一个最小堆中删除一个元素时，需要把堆尾元素填补到堆顶位置完成删除操作。错
6. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具 有相同的结果。对
.在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有 相同的结果。对
7. 在树的存储中，若使每个结点带有指向双亲结点的指针，这为在算法中寻找双亲结点带来方便。对
8. 于一棵具有n个结点的任何二叉树，进行前序、中序或后序的任一种次序遍历的空间复杂度为0(log2n)。
错
9. 对具有n个结点的堆进行插入一个元素运算的时间复杂度为0(n)。对
四、运算题
1. 已知一棵树的静态双亲表示如下，其中用-1表示空指针，树根结点存于0号单元，分别求出该树的叶 子结点数、单分支结点数、两分支结点数和三分支结点数。
序号：0123456789 10
abcdefghijk
-10113056609
data:
parent:
叶子结点数：5
单分支结点数：3
两分支结点数：2
三分支结点数：1
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
2 13 4 4
兀素
比较次数
3. 假定一个线性序列为(38,42, 55,15,23,44, 30, 74, 48, 26),根据此线性序列中元素的排列次序生成一 棵二叉搜索树，求出该二叉搜索树中左子树为空的所有单支结点和右子树为空的所有单支结点，请按照结 点值从小到大的次序写出。
左子树为空的所有单支结点：15, 23, 42, 44
右子树为空的所有单支结点：30
4. 假定一组记录为(40, 28, 16, 56, 50, 32, 30, 63, 44, 38),按次序插入每个记录生成一棵AVL树，请回答插 入时造成不平衡的结点个数。
插入时造成不平衡的结点个数：4
5. 已知图G=(V,E),其中V={a,b,c,d,e}, E={,,,,,, },请写出各结点的出度和入度。
结点a b c d e
出度112 12
入度2 2 1 1 1
6. 已知一个图的顶点集V和边集G分别为：
V={1,2, 3, 4, 5, 6);
E=(<1, 2>, <1, 3>, <2, 4>, <2, 5>, <3, 4>, <4, 5>, <4, 6>, <5, 1>, <5, 3>, 6, 5>};
假定该图采用邻接表表示，每个顶点邻接表中的边结点都是按照终点序号(即数值域的值)从小到 大的次序链接的，试写出：
(1) 从顶点1出发进行深度优先搜索所得到的顶点序列；
(2) 从顶点1出发进行广度优先搜索所得到的顶点序列。
答(1)： 1, 2, 4, 5, 3, 6
(2)： 1,2, 3, 4, 5,6
五、算法分析题
1. 请写出下面算法的功能.
void unknown(Queue &Q) (
Stack S; int d;
S.InitStack();
while(!Q. IsEmpty( )) {
Q. DeQueue (d); S. Push (d);
)
while(!S. IsEmpty( )) {
S. Pop (d); Q. EnQueue (d);
)
)
利用〃栈〃作为辅助存储,将队列中的元素逆置(即相反次序放置)。
2. 下而是判断一个带表头结点的双向循环链表L其前后结点值是否对称相等的算法，若相等则返回1,否 则返回0。请按标号补充合适的内容。
int symmetry ( DoublelList* DL ) {
DoublelNode * p = DL->rLink, *q = DL->lLink;
while (p != q)
if ( p->data = q->data ) (
p = p->rLink;
if(p->lLink=q) —(2)—;
)
else (3);
return 1;
)
(1) q = q->lLink (2) return 1 (3) return 0
3. 设有一个求解汉诺塔(Hanoi)的递归算法如下：
void HANOI ( int n, int pegl, int peg2, int peg3 ) {
if(n=l) cout«PEGK, <<PEG3<<ENDL;
else (
HANOI (n-1, pegl, peg3, peg2);
cout«PEGK, <<PEG3<<ENDL;
HANOI (n-1, peg2, pegl, peg3);
}
当使用HANOI ( 3, 1, 2, 3)进行调用时，执行过程中else子句的cout语句得到的结果为：
1 一2
1 一3
2—3
4. 已知二叉树中的结点类型BinTreeNode定义为：
struct BinTreeNode {ElemType data; BinTreeNode *left, bright;};
其中data为结点值域，left和right分别为指向左、右子女结点的指针域。下面函数的功能是：从二叉 树BT中查找值为X的结点，返回指向其父结点的指针。若该结点不存在或为树根结点则返回空。算法中 参数PT的初值为NULLo请在划有横线的地方填写合适内容。
BinTreeNode* ParentPtr(BinTreeNode* BT, BinTreeNode* PT, ElemType& X)
(
if(BT=NULL) return NULL;
else if(BT~>data==X) return PT;
else {
if (PT=ParentPtr (BT->left, BT, X)) _(1);
if (2) return PT;
else (3);
)
}
(1) return PT
(2) (PT=ParentPtr (BT->right, BT, X))
(3) return NULL 或 return 0
六、算法设计题
1. 计算多项式Pn (x) = aO xn + al xn~l + a2 xn-2 + + an-1 x + an通常使用的方法是一种递
推的方法。它可以描述为如下的递推形式：
pn (x) = x * pn-1 (x) + an (n>0)
此处
+ an-2 x + an-1
Pn~l (x) = aO xn-1 + al xn-2 +
P0二an
这也是问题的递归形式。多项式的递归求解形式为：
poly(x, 0) = A[0]
poly (x, n) = x * poly (x, n-1) + A[n], n > 0
试编写一个递归函数，计算这样的多项式的值。
float poly ( float x, float A[], int n ) (
}
答：
float poly ( float x, float A[ ], int n ) (
if ( ! n ) return A[0];
else return x * poly( x, A, n~l ) + A[n];
)
2. 已知二叉树中的结点类型BinTreeNode定义为：
struct BinTreeNode (char data; BinTreeNode *left, *right;};
其中data为结点值域，left和right分别为指向左、右子女结点的指针域。根据下而函数声明编写出求
一棵二叉树高度的算法，该高度由函数返回。假定树根的层次为0,参数BT初始指向这棵二叉树的根结点。
int BTreeHeight(BinTreeNode* BT);
答：
int BTreeHeight(BinTreeNode* BT)
(
if(BT=NULL)
〃对于空树，返回-1并结束递归
return - 1;
else
(
〃计算左子树的高度
int hl=BTreeHeight(BT->left);
〃计算右子树的高度
int h2=BTreeHeight(BT->right);
//返回树的高度
if (hl>h2) return hl+1;
else return h2+l;
)
}
说明：函数体中的两个else可以没有
3. 已知二叉树中的结点类型BinTreeNode定义为：
struct BinTreeNode (char data; BinTreeNode *left, *right;};
其中data为结点值域，left和right分别为指向左、右子女结点的指针域，根据下而函数声明编写出求
一棵二叉树中叶子结点总数的算法，该总数值由函数返回。假定参数BT初始指向这棵二叉树的根结点。
int BTreeLeafCount(BinTreeNode* BT);
答：
int BTreeLeafCount(BinTreeNode* BT)
(
if(BT=NULL) return 0;
else if (BT->left==NULL && BT->right=NULL) return 1;
else return BTreeLeafCount(BT->left)+BTreeLeafCount(BT->right);
}
说明：函数体中的两个else可以没有
《数据结构》题库及答案二
一、单项选择题
1. 在一棵具有n个结点的完全二叉树中，树枝结点的最大编号为(D )。假定树根结点的编号为0。
A. e(n-l)/2u B. en/2u C. en/2u D. en/2u~l
2. 在一棵树的左子女-右兄弟表示法中，一个结点的右子女是该结点的(A)结点。
A.兄弟B.父子C.祖先D.子孙
3. 已知一棵树的边集表示为则该树的深度为(B )。假定树根结点的高度为0。
A. 2 B. 3 C. 4 D. 5
4. 一棵树的广义表表示为a(b,c(e,f(g)),d),当用左子女-右兄弟链表表示时，右指针域非空的结点个数 为(C )o
5. 对长度为10的顺序表进行搜索，若搜索前面5个元素的概率相同，均为1/8,搜索后而5个元素的概 率相同，均为3/40,则搜索任一元素的平均搜索长度为(C )o
A. 5.5 B. 5 C. 39/8 D. 19/4
6. 对于长度为n的顺序存储的有序表，若采用折半搜索，则对所有元素的搜索长度中最大的为(A)的值 向上取整。
A. Iog2 (n+1) B. Iog2n C. n/2 D. (n+l)/2
7. 对于长度为18的顺序存储的有序表，若采用折半搜索，则搜索第15个元素的搜索长度为(B)。
A. 3 B. 4 C. 5 D. 6
8. 从具有n个结点的二叉搜索树中搜索一个元素时，在等概率情况下进行成功搜索的时间复杂度大致为 (C )。
A. 0(n) B. 0(1) C. 0(log2n) D. 0(n2)
9. 向一棵AVL树插入元素时，可能引起对最小不平衡子树的调整过程，此调整分为(C)种旋转类型。
A. 2 B. 3 C. 4 D. 5
10 .设 Gl= (VI, El)和 G2= (V2, E2)为两个图，如果 V11V2, E1IE2,则称(A )。
A. G1是G2的子图B. G2是G1的子图
C. G1是G2的连通分量D. G2是G1的连通分量
11. n个顶点的连通图中至少含有(A )。
A. nT条边B. n条边C. n(n-l)/2条边D・n(nT)条边
12. 对于具有e条边的无向图，它的邻接表中有(D)个边结点。
A. e~l B. e C. 2 (e~l) D. 2e
13. 在n个顶点的有向无环图的邻接矩阵中至少有(C)个零元素。
A. n B. n(n-l)/2 C. n(n+l)/2 D. n(n~l)
二、填空题
1. 在一个堆的顺序存储中，若一个元素的下标为i(OWiWnT),则它的左子女元素的下标为(2i+l)。
2. 在一个最大堆中，堆顶结点的值是所有结点中的(最大值)。
3. 假定一个顺序表的长度为40,并假定顺序搜索每个元素的概率都相同，则在搜索成功情况下的平均搜
索长度为(20. 5) o
4. 从一棵二叉搜索树中搜索一个元素时，若给定值大于根结点的值，则需要向(右子树)继续搜索。
5. 在一棵AVL树中，每个结点的左子树高度与右子树高度之差的绝对值不超过(Do
6. 根据一组记录(56, 42, 38, 64, 48)依次插入结点生成一棵AVL树时，当插入到值为38的结点时需要进行 (右单旋转)调整。
7. n (n>0)个顶点的连通无向图各顶点的度之和最少为(2(n-1))。
8. 设图 G = (V, E), V = (1, 2, 3, 4), E = (<1, 2>, <1, 3>, <2, 4>, <3, 4>},从顶点 1 出发，对 图G进行广度优先搜索的序列有(2)种。
9. n个顶点的连通无向图的生成树含有(n-l)条边。
10. 一般来说，深度优先生成树的高度比广度优先生成树的高度要(高)。
11. 第i (i = 1, 2,…，n-l)趟从参加排序的序列中取出第i个元素，把它插入到由第0个至第i-1个 元素组成的有序表中适当的位置，此种排序方法叫做(直接插入)排序。
三、 判断题(对/错)
1. 能够在链接存储的有序表上进行折半搜索，其时间复杂度与在顺序存储的有序表上相同。错
2. 折半搜索所对应的判定树，既是一棵二叉搜索树，又是一棵理想平衡二叉树。对
3. 对于两棵具有相同记录集合而具有不同形态的二叉搜索树，按中序遍历得到的结点序列是相同的。对
4. 用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有 关，而与图的边数无关。对
5. 存储有向图的邻接矩阵是对称的，因此可以只存储邻接矩阵的下(上)三角部分。错
6. 有回路的有向图不能完成拓扑排序。对
7. 对于AOE网络，加速任一关键活动就能使整个工程提前完成。错
8. 对一个连通图进行一次深度优先搜索可以遍访图中的所有顶点。对
四、 运算题
1. 已知一个图的顶点集V和边集G分别为：
V={1,2, 3, 4, 5, 6);
E=(<1, 2>, <1, 3>, <2, 4>, <2, 5>, <3, 4>, <4, 5>, <4, 6>, <5,1>, <5, 3>, 6, 5>};
假定该图采用邻接表表示，每个顶点邻接表中的边结点都是按照终点序号(即数值域的值)从大到 小的次序链接的，试按照遍历算法写出：
(1) 从顶点1出发进行深度优先搜索所得到的顶点序列；
(2) 从顶点1出发进行广度优先搜索所得到的顶点序列。
答(1)： 1, 3, 4, 6, 5, 2
(2)： 1, 3, 2, 4, 5, 6
2. 已知一个带权图的顶点集V和边集G分别为：
V= {0,1,2, 3, 4, 5, 6);
E={(0,1)19, (0, 2) 10, (0, 3) 14, (1,2)6, (1,5)5, (2, 3)26, (2, 4)15, (3, 4) 18, (4, 5)6, (4, 6)6, (5, 6) 12};
试根据迪克斯特拉(Dijkstra)算法求出从顶点0到其余各顶点的最短路径，在下而填写对应的路径
长度。
顶点：0 1 2 3 4 5 6
路径长度：0 16 10 14 25 21 31
3. 已知一个AOV网络的顶点集V和边集G分别为：
V= {0,1,2, 3, 4, 5, 6, 7);
E=(<0, 2>, <1, 3>, <1, 4>, <2, 4>, <2, 5>, <3, 6>, <3, 7>, <4, 7>, <5, 7>, <6, 7>);
若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号(即dest域的值)从小到大 的次序链接的，则按主教材中介绍的进行拓扑排序的算法，写出得到的拓扑序列(提示：先画出对应的图 形，然后再运算)。
拓扑序列：1,3, 6, 0,2, 5, 4, 7
4. 已知一个A0E网络的顶点集V和边集G分别为：
V= {0,1,2, 3, 4, 5);
E={<0, 1>5, <0, 2>8, <1, 2>7, <1, 3>10, <1, 4>6, <2, 4>3, <3, 4>9, <3, 5>15, <4, 5>12};
若存储它采用邻接表，则按主教材中介绍的求关键路径的方法，依次写出所有的关键活动(用边表 示)，并求出关键路径长度(提示：先画出对应的图形，然后再运算)。
所有关键活动：<0, 1>5, <1, 3>10, <3, 4>9, <4, 5>12
关键路径长度：36
5. 如果某个文件经内排序得到80个初始归并段，试问
(1) 若使用多路归并执行3趟完成排序，那么应取的归并路数至少应为多少？
(2) 如果操作系统要求一个程序同时可用的输入/输出文件的总数不超过15个，则按多路归并至少 需要几趟可以完成排序？
答(1)归并路数：5 (2)需要归并躺数：2
答案解释：
(1) 设归并路数为k,初始归并段个数m = 80,根据归并趟数计算公式S二elogkmu = elogk80u = 3 得：k3》80。由此解得kN5,即应取的归并路数至少为5。
(2) 设多路归并的归并路数为k,需要k个输入缓冲区和1个输出缓冲区。1个缓冲区对应1个文件, 有k +1 = 15,因此k = 14,可做14路归并。由S = elogkmu = 61ogl480u = 2。即至少需2趟归并可完 成排序。
五、算法分析题
1.已知二叉树中的结点类型BinTreeNode定义为：

struct BinTreeNode {ElemType data; BinTreeNode *left, bright;};
其中data为结点值域，left和right分别为指向左、右子女结点的指针域。根据下面函数的定义指出函 数的功能。算法中参数BT指向一棵二叉树。
void BTC(BinTreeNode* BT)
{
if(BT!二NULL) {
if( BT->left!=NULL && BT->right!=NULL)
if(BT->1eft->data>BT~>right->data) (
BinTreeNode* t=BT~>left;
BT->1eft=BT->r i ght;
BT->right=t;
)
BTC(BT->left);
BTC(BT->right);
)
)
算法功能：当BT中每个结点的左子女的值大于右子女的值则交换左右子树。
2. 已知二叉树中的结点类型BinTreeNode定义为：
struct BinTreeNode (char data; BinTreeNode *left, bright;};
其中data为结点值域，left和right分别为指向左、右子女结点的指针域。假定一棵二叉树采用链接存 储，它的广义表表示为r(b(, d(f, g)), t (e)), rt, bt, dt和et指针变量分别保存指向r, b, d和e结点的指 针值,则：
执行BTM(rt)调用后，得到的函数值为—⑴;
执行BTM(bt)调用后，得到的函数值为—⑵;
执行BTM(dt)调用后,
得到的函数值为—⑶

执行BTM (et)调用后,
得到的函数值为—⑷

char BTM(BinTreeNode* BT)
static char max=O;
if(BT!二NULL) {
char kl,k2;
kl=BTM(BT->left);
k2=BTM(BT->right);
if(kl>max) max=kl;
else if(k2>max) max=k2;
else if(BT->data>max) max=BT->data;
)
return max;
}
⑴'
⑵'g，
⑶'g，
⑷'e，
3. 在a[10]数组中数据{16, 35, 42, 73, 54, 58, 80}为一个最小堆，n为整型变量,其值为7,则执行DH(a, n) 调用下面算法后数组a中的数据变为。
int DH(int HBT[], int& n)
(
if(n=0) {cerT«〃null!〃〈
int temp=HBT[0];
n—;
int x=HBT[n];
int i=0;
int j=2*i+l;
while(j<=n~l) (
if(jHBT[j+l]) j++;
if(x<=HBT[j]) break;
HBT=HBT[j];
i=j； j=2*i+l;
)
HBT二x;
return temp;
}
{35, 54, 42, 73, 80, 58)
4. 假定pl和p2是两个单链表的表头指针，用来表示两个集合，单链表中的结点包括值域data和指向后 继结点的指针域link,试根据下面算法指出算法功能。
int SS(ListNode* pl, ListNode* p2)
(
while(p2!=NULL) (
ListNode* r=pl;
While(r!=NULL) {
if (p2-〉data=r-〉data) break;
r=r->link;
)
if(r=NULL) return 0;
p2=p2->link;
)
return 1;
}
判断p2单链表所代表的集合是否为pl单链表所代表的集合的子集合，若是则返回1否则返回0。
5. 已知二叉树中的结点类型BinTreeNode定义为：
struct BinTreeNode {ElemType data; BinTreeNode *left, *right;};
其中data为结点值域，left和right分别为指向左、右子女结点的指针域。参数bt指向一棵二叉树，引 用参数x一开始具有的值小于树中所有结点的值。试根据下面的函数定义指出此算法的功能。
int JB(BinTreeNode* bt, ElemType& x)
(
if(bt=NULL) return 1;
else {
if(JB(bt->left, x)==0) return 0;
if(bt->data
x=bt~>data;
if(JB(bt->right,x)=O) return 0;
else return 1;
)
)
算法功能：判断二叉树bt是否为一棵二叉搜索树，若是则返回1否则返回0。
六、算法设计题
1. 已知二叉树中的结点类型BinTreeNode定义为：
struct BinTreeNode {char data; BinTreeNode *left, bright;};
其中data为结点值域，left和right分别为指向左、右子女结点的指针域，根据下而函数声明编写出判 断两棵二叉树是否相等的算法，若相等则返回1否则返回0。算法中参数T1和T2为分别指向这两棵二叉 树根结点的指针。当两棵树的结构完全相同并旦对应结点的值也相同时才被认为相等。
int BTreeEqual(BinTreeNode* Tl, BinTreeNode* T2);
答：
int BTreeEqual(BinTreeNode* Tl,BinTreeNode* T2)
(
〃若两棵树均为空则返回1表示相等
if(Tl=NULL && T2=NULL) return 1;
〃若一棵为空一棵不为空则返回0表示不等
else if (T1=NULL i | T2=NULL) return 0;
//若根结点值相等并且左、右子树对应相等则两棵树相等
else if(Tl->data==T2~>data && BTreeEqual(Tl~>left, T2->left)
BTreeEqual(Tl~>right, T2~>right))
return 1;
〃若根结点值不等或左、右子树对应不等则两棵树不等
else
return 0;
}
2. 已知二叉树中的结点类型用BinTreeNode表示，被定义为：
struct BinTreeNode (char data; BinTreeNode *left, bright;};
其中data为结点值域，left和right分别为指向左、右子女结点的指针域，根据下而函数声明编写 出复制一棵二叉树的算法，并返回复制得到的二叉树的根结点指针。算法中参数BT初始指向待复制二叉 树的根结点。
BinTreeNode* BTreeCopy(BinTreeNode* BT);
答：
BinTreeNode* BTreeCopy(BinTreeNode* BT)
(
if(BT=NULL) return NULL;
else (
〃得到新结点
BinTreeNode* pt=new BinTreeNode;
//复制根结点值
pt->data=BT->data;
〃复制左子树
pt->left=BTreeCopy(BT->left);
〃复制右子树
pt->right=BTreeCopy(BT->right);
//返回新树的树根指针
return pt;
)
}
说明：函数体中的else可以没有
3. 假定元素类型为ElemType的一维数组R[n]中保存着按关键码升序排列的n个记录，记录的关键码域 key的类型为KeyType,试按照下面的函数声明编写一个非递归算法，从一维数组R[n]中折半搜索出关键 码等于K的记录，若搜索成功则返回记录位置(即元素下标)，否则返回-1。
int BinSearch(ElemType R[], int n, KeyType K);
答：
int BinSearch(ElemType R[], int n, KeyType K)
int low=0, high=nT;
while(low<=high) int mid=(low+high)/2;
if(K==R[mid].key) return mid;
else if(K
else low=mid+l;
)
return -1;
)
说明：函数体中第一个else可以没有.
《数据结构》题库及答案三
一、单项选择题
1. 一个数组元素a与(A )的表示等价。
A. *(a+i) B. a+i C. *a+i D. &a+I
2. 执行下面程序段时，执行S语句的次数为(D )o
for(int i=l; i〈=n; i++)
for(int j=l; j<=i; j++) S;
A. n2 B. n2/2 C. n(n+l) D. n(n+l)/2
3. 当一个作为实际传递的对象占用的存储空间较大并可能被修改时，应最好说明为(B),以节省参数值 的传输时间和存储参数的空间。
A.基本类型B.引用型C.指针型D.常值引用型
4. 输出一个二维数组b[m] [n]中所有元素值的时间复杂度为(D )。
A. 0(n) B. 0 (m+n) C. 0(n2) D. 0(m*n)
5. 某算法仅含程序段1和程序段2,程序段1的执行次数3n2,程序段2的执行次数为0. 01n3,则该算法
的时间复杂度为(C )o
A. 0(n) B. 0(n2) C. 0(n3) D. 0(1)
6. 多维数组实际上是由嵌套的(A )实现的。
A. 一维数组B.多项式C.三元组表D.简单变量
7. 在一个长度为n的顺序表中删除第i个元素(OWiWn-1)时，需要从前向后依次前移(C )个元素。
A. n-i B. n-i+1 C. n~i~l D. i
8. 在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（A ）o
A. 0（n） B. 0（n/2） C. 0（1） D. 0（n2）
9. 设有一个n'n的对称矩阵A,将其上三角部分按行存放在一个一维数组B中，A[0] [0]存放于B[0]中， 那么第i行的对角元素A存放于B中（C ）处。
A. （i+3）*i/2 B. （i+l）*i/2 C. （2n-i+l）*i/2 D. （2n-i—l）*i/2
10. 不带头结点的单链表first为空的判定条件是（A ）o
A. first == NULL; B. first->link = NULL;
C. first->link = first; D. first != NULL;
11 .设单链表中结点的结构为（data, link）o已知指针p所指结点不是尾结点，若在*p之后插入结点*s, 则应执行的操作是（D ）。
A.s->link=p; p-〉link=s; B. p->link=s; s-〉link=p;
C.s->link=p->link; p=s; D. s->link=p->link; p->link=s;
12.设单循环链表中结点的结构为（data, link）, K rear是指向非空的带表头结点的单循环链表的尾结 点的指针。若想删除链表第一个结点，则应执行的操作是（D ）o
A. s = rear; rear = rear->link; delete s;
B. rear = rear->link; delete rear;
C. rear = rear->1ink->1ink; delete rear;
D. s = rear->link->link; rear->link->link = s->link; delete s;
二、填空题
1. 数据结构包括逻辑结构、（存储结构）和数据的运算三个方面。
2. 基本数据类型是计算机已经实现了的（数据结构）。
3. 而向对象的特征应包括对象、类、（继承）、消息通信。
4