数据结构作业二.doc

《数据结构作业二.doc》由会员分享，可在线阅读，更多相关《数据结构作业二.doc（15页珍藏版）》请在三一文库上搜索。

1、作业二作业二一、单项选择题1. 给定有n个元素的向量，建立一个有序单链表的时间复杂度是（ C ）。A.O(1) B. O(n) C. O(n2) D. O(nlog2n)2. 带表头的双向循环链表的空表满足（ B ）。A. firstNULL; B. first-rLink=firstC. first-lLink=NULL D. first-rLink=NULL3. 栈的插入和删除操作在( A )进行。A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置4. 在一个顺序存储的循环队列中，队头指针指向队头元素的(A )位置。A. 前一个 B. 后一个 C. 当前 D. 后面5. 假定一个顺序存

2、储的循环队列的队头和队尾指针分别为front和rear，则判断队空的条件为(D )。A. front+1 = rear B. rear+1 = frontC. front = 0 D. front = rear6. 设链式栈中结点的结构为（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. 为增加内存空间的利用率和减少溢出的

3、可能性, 由两个栈共享一块连续的内存空间时, 应将两栈的(D )分别设在这块内存空间的两端。 A. 长度 B. 深度 C. 栈顶 D.栈底8. 在系统实现递归调用时需利用递归工作记录保存（ C ），当递归调用程序执行结束时通过它将控制转到上层调用程序。A. 调用地址 B. 递归入口 C. 返回地址 D. 递归出口9. 如果一个递归函数过程中只有一个递归语句，而且它是过程体的最后语句，则这种递归属于（D ），它很容易被改写为非递归过程。A. 单向递归 B. 回溯递归 C. 间接递归 D. 尾递归10. 设有一个广义表A (a)，其表尾为（ C ）。Aa B( ( ) ) C（） D(a)11.

4、对于一组广义表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+1 C. 2i-1 D. 2n二、填空题1. 链表与顺序表、索引表、散列表等都是数据逻辑结构的（存储）表示。2. 队列是一种限定在表的一端插入，在另一端删除的线性表，

5、它又被称为（先进先出）表。3. 向一个顺序栈插入一个元素时，首先使（栈顶指针）后移一个位置，然后把待插入元素写入到这个位置上。4. 向一个循环队列中插入元素时，需要首先移动（队尾）指针，然后再向所指位置写入新元素。5. 在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列至多有（1）个结点。6. 递归工作栈起到两个作用，其一是将递归调用时的实际参数和返回地址传递给下一层递归；其二是保存本层的形式参数和（局部变量）。7. 非空广义表的除第一个元素外其他元素组成的表称为广义表的（表尾）。8. 广义表的深度定义为广义表括号的（重数）。9. 一棵树的广义表表示为a(b(c,d(e,f),g(h

6、),i(j,k(x,y)，结点f的层数为（3）。假定树根结点的层数为0。10. 在一棵三叉树中，度为3的结点数有2个，度为2的结点数有1个，度为1的结点数为2个，那么度为0的结点数有（6）个。11一棵二叉树中，假定双分支结点数为5个，单分支结点数为6个，则叶子结点数为（6）个。12.在一棵高度为h的理想平衡二叉树中，最多含有（2h+1-1）个结点。假定树根结点的高度为0。三、判断题（对/错）1在用单链表表示的链式队列Q中，队头指针为Q-front，队尾指针为Q-rear，则队空条件为Q-front = Q-rear。错2递归调用算法与相同功能的非递归算法相比，主要问题在于重复计算太多，而且调用

7、本身需要分配额外的空间和传递数据和控制，所以时间与空间开销通常都比较大。对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. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的结果。对. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行

8、中序遍历和后序遍历，则具有相同的结果。对7. 在树的存储中，若使每个结点带有指向双亲结点的指针，这为在算法中寻找双亲结点带来方便。对8 于一棵具有n个结点的任何二叉树，进行前序、中序或后序的任一种次序遍历的空间复杂度为O(log2n)。错9对具有n个结点的堆进行插入一个元素运算的时间复杂度为O(n)。对四、运算题1. 已知一棵树的静态双亲表示如下，其中用-1表示空指针，树根结点存于0号单元，分别求出该树的叶子结点数、单分支结点数、两分支结点数和三分支结点数。序号： 0 1 2 3 4 5 6 7 8 9 10a b c d e f g h i j k-1 0 1 1 3 0 5 6 6 0 9

9、 data: parent:叶子结点数：5 单分支结点数：3 两分支结点数：2 三分支结点数：12. 已知一个有序表(15,26,34,39,45,56,58,63,74,76,83,94)顺序存储于一维数组a12中，根据折半搜索过程填写成功搜索下表中所给元素34, 56, 58, 63, 94时的比较次数。34 56 58 63 942 1 3 4 4元素 比较次数3. 假定一个线性序列为 (38,42,55,15,23,44,30,74,48，26)，根据此线性序列中元素的排列次序生成一棵二叉搜索树，求出该二叉搜索树中左子树为空的所有单支结点和右子树为空的所有单支结点，请按照结点值从小到大

10、的次序写出。左子树为空的所有单支结点：15,23,42,44 右子树为空的所有单支结点：304. 假定一组记录为(40,28,16,56,50,32,30,63,44,38)，按次序插入每个记录生成一棵AVL树，请回答插入时造成不平衡的结点个数。插入时造成不平衡的结点个数：45. 已知图G=(V,E)，其中V=a,b,c,d,e，E=，请写出各结点的出度和入度。 结点 a b c d e 出度 1 1 2 1 2入度 2 2 1 1 16. 已知一个图的顶点集V和边集G分别为： V=1,2,3,4,5,6; E=,6,5; 假定该图采用邻接表表示，每个顶点邻接表中的边结点都是按照终点序号（即数

11、值域的值）从小到大的次序链接的，试写出： (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); 利用栈作为辅助存储,将队列中的元素逆置（即相反次序放置

12、）。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; _(1)_; if(p-lLink=q) _(2)_; else _(3)_; return 1; (1) q = q-lLink(2) return 1 (3) return 03. 设有一个求解汉诺塔（H

13、anoi）的递归算法如下：void HANOI ( int n, int peg1, int peg2, int peg3 ) if(n=1) coutpeg1peg3endl;else HANOI(n-1, peg1, peg3, peg2); coutpeg1peg3data=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

14、六、算法设计题1. 计算多项式 Pn (x) = a0 xn + a1 xn-1 + a2 xn-2 + + an-1 x + an通常使用的方法是一种递推的方法。它可以描述为如下的递推形式： pn (x) = x * pn-1 (x) + an(n0)此处 Pn-1 (x) = a0 xn-1 + a1 xn-2 + + an-2 x + an-1 P0=an这也是问题的递归形式。多项式的递归求解形式为：poly(x, 0) = A0poly(x, n) = x * poly(x, n-1) + An,n 0试编写一个递归函数，计算这样的多项式的值。float poly ( float x,

15、 float A, int n ) 答：float poly ( float x, float A , int n ) if ( ! n ) return A0; else return x * poly( x, A, n-1 ) + An; 2. 已知二叉树中的结点类型BinTreeNode定义为: struct BinTreeNode char data; BinTreeNode *left, *right;其中data为结点值域，left和right分别为指向左、右子女结点的指针域。根据下面函数声明编写出求一棵二叉树高度的算法，该高度由函数返回。假定树根的层次为0，参数BT初始指向这棵二

16、叉树的根结点。 int BTreeHeight(BinTreeNode* BT);答：int BTreeHeight(BinTreeNode* BT) if(BT=NULL) /对于空树，返回-1并结束递归 return 1; else /计算左子树的高度 int h1=BTreeHeight(BT-left); /计算右子树的高度 int h2=BTreeHeight(BT-right); /返回树的高度 if(h1h2) return h1+1; else return h2+1; 说明：函数体中的两个else可以没有3. 已知二叉树中的结点类型BinTreeNode定义为: struct

17、 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 ret

18、urn BTreeLeafCount(BT-left)+BTreeLeafCount(BT-right); 说明：函数体中的两个else可以没有ley0 2006-11-17 08:59作业三作业三一、单项选择题1. 在一棵具有n个结点的完全二叉树中，树枝结点的最大编号为(D )。假定树根结点的编号为0。A. ë(n-1)/2ûB.ën/2ûC. n/2D. euml;n/2û-12. 在一棵树的左子女-右兄弟表示法中，一个结点的右子女是该结点的(A )结点。 A. 兄弟 B. 父子 C. 祖先 D. 子孙3. 已知一棵树的边集表示为,

19、, , , , , , ，则该树的深度为(B )。假定树根结点的高度为0。 A. 2 B. 3 C. 4 D. 54. 一棵树的广义表表示为a(b,c(e,f(g),d)，当用左子女-右兄弟链表表示时，右指针域非空的结点个数为(C )。 A 1 B 2 C 3 D 45. 对长度为10的顺序表进行搜索，若搜索前面5个元素的概率相同，均为1/8，搜索后面5个元素的概率相同，均为3/40，则搜索任一元素的平均搜索长度为(C )。 A. 5.5 B. 5 C. 39/8 D. 19/46. 对于长度为n的顺序存储的有序表，若采用折半搜索，则对所有元素的搜索长度中最大的为( A )的值向上取整。 A.

20、 log2(n+1) B. log2n C. n/2 D. (n+1)/27. 对于长度为18的顺序存储的有序表，若采用折半搜索，则搜索第15个元素的搜索长度为(B )。 A. 3 B. 4 C. 5 D. 68. 从具有n个结点的二叉搜索树中搜索一个元素时，在等概率情况下进行成功搜索的时间复杂度大致为(C )。 A. O(n) B. O(1) C. O(log2n) D. O(n2)9. 向一棵AVL树插入元素时，可能引起对最小不平衡子树的调整过程，此调整分为( C )种旋转类型。 A. 2 B. 3 C. 4 D. 510. 设G1=（V1，E1）和G2=（V2，E2）为两个图，如果V1&

21、Iacute;V2，E1ÍE2，则称 ( A )。 AG1是G2的子图 BG2是G1的子图 CG1是G2的连通分量 DG2是G1的连通分量11. n个顶点的连通图中至少含有 (A)。 An-1条边 Bn条边 Cn(n-1)/2条边 Dn(n-1)条边12. 对于具有e条边的无向图，它的邻接表中有 ( D ) 个边结点。 Ae-1 Be C2(e-1) D2e13. 在n个顶点的有向无环图的邻接矩阵中至少有 (C) 个零元素。 An Bn(n-1)/2 Cn(n+1)/2 Dn(n-1) 二、填空题1在一个堆的顺序存储中，若一个元素的下标为i(0in-1)，则它的左子女元素的下标为

22、（2i+1）。2在一个最大堆中，堆顶结点的值是所有结点中的（最大值）。3. 假定一个顺序表的长度为40，并假定顺序搜索每个元素的概率都相同，则在搜索成功情况下的平均搜索长度为(20.5)。4. 从一棵二叉搜索树中搜索一个元素时，若给定值大于根结点的值，则需要向(右子树)继续搜索。5. 在一棵AVL树中，每个结点的左子树高度与右子树高度之差的绝对值不超过（1）。6. 根据一组记录(56,42,38,64,48)依次插入结点生成一棵AVL树时，当插入到值为38的结点时需要进行（右单旋转）调整。7. n (n0) 个顶点的连通无向图各顶点的度之和最少为（2(n-1)）。8. 设图G = (V, E)

23、，V = 1, 2, 3, 4, E = , , , ，从顶点1出发，对图G进行广度优先搜索的序列有（2）种。9. n个顶点的连通无向图的生成树含有(n-1)条边。10. 一般来说,深度优先生成树的高度比广度优先生成树的高度要（高）。11. 第i (i = 1, 2, , n-1) 趟从参加排序的序列中取出第i个元素，把它插入到由第0个至第i-1个元素组成的有序表中适当的位置，此种排序方法叫做（直接插入）排序。三、判断题（对/错）1. 能够在链接存储的有序表上进行折半搜索，其时间复杂度与在顺序存储的有序表上相同。错2. 折半搜索所对应的判定树，既是一棵二叉搜索树，又是一棵理想平衡二叉树。对3.

24、 对于两棵具有相同记录集合而具有不同形态的二叉搜索树，按中序遍历得到的结点序列是相同的。对4.用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。对5. 存储有向图的邻接矩阵是对称的，因此可以只存储邻接矩阵的下（上）三角部分。错6. 有回路的有向图不能完成拓扑排序。对7. 对于AOE网络，加速任一关键活动就能使整个工程提前完成。错8. 对一个连通图进行一次深度优先搜索可以遍访图中的所有顶点。对四、运算题1. 已知一个图的顶点集V和边集G分别为： V=1,2,3,4,5,6; E=,6,5; 假定该图采用邻接表表示，每个顶点邻接表中的边

25、结点都是按照终点序号（即数值域的值）从大到小的次序链接的，试按照遍历算法写出： (1) 从顶点1出发进行深度优先搜索所得到的顶点序列； (2) 从顶点1出发进行广度优先搜索所得到的顶点序列。 答（1）：1,3,4,6,5,2 （2）：1,3,2,4,5,62. 已知一个带权图的顶点集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到其余各顶点的最短路径，在下面填写

26、对应的路径长度。 顶点： 0 1 2 3 4 5 6路径长度： 0 16 10 14 25 21 313. 已知一个AOV网络的顶点集V和边集G分别为： V=0,1,2,3,4,5,6,7; E=,; 若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号(即dest域的值)从小到大的次序链接的，则按主教材中介绍的进行拓扑排序的算法，写出得到的拓扑序列（提示：先画出对应的图形，然后再运算）。 拓扑序列：1,3,6,0,2,5,4,74. 已知一个AOE网络的顶点集V和边集G分别为： V=0,1,2,3,4,5; E=5,8,7,10,6,3,9,15,12; 若存储它采用邻接表，则按

27、主教材中介绍的求关键路径的方法，依次写出所有的关键活动（用边表示），并求出关键路径长度（提示：先画出对应的图形，然后再运算）。所有关键活动：5,10,9,12关键路径长度：365. 如果某个文件经内排序得到80个初始归并段，试问 (1) 若使用多路归并执行3趟完成排序，那么应取的归并路数至少应为多少？ (2) 如果操作系统要求一个程序同时可用的输入/输出文件的总数不超过15个，则按多路归并至少需要几趟可以完成排序？答（1）归并路数： 5 （2）需要归并躺数：2答案解释： (1) 设归并路数为k，初始归并段个数m = 80，根据归并趟数计算公式S = logkm = logk80 = 3得：k3

28、80。由此解得k5，即应取的归并路数至少为5。 (2) 设多路归并的归并路数为k，需要k个输入缓冲区和1个输出缓冲区。1个缓冲区对应1个文件，有k +1 = 15，因此k = 14，可做14路归并。由S = logkm = log1480 = 2。即至少需2趟归并可完成排序。五、算法分析题1. 已知二叉树中的结点类型BinTreeNode定义为: struct BinTreeNode ElemType data; BinTreeNode *left, *right;其中data为结点值域，left和right分别为指向左、右子女结点的指针域。根据下面函数的定义指出函数的功能。算法中参数BT指向

29、一棵二叉树。 void BTC(BinTreeNode* BT) if(BT!=NULL) if( BT-left!=NULL & BT-right!=NULL) if(BT-left-dataBT-right-data) BinTreeNode* t=BT-left; BT-left=BT-right; BT-right=t; BTC(BT-left); BTC(BT-right); 算法功能：当BT中每个结点的左子女的值大于右子女的值则交换左右子树。2. 已知二叉树中的结点类型BinTreeNode定义为: struct BinTreeNode char data; BinTreeNode

30、 *left, *right;其中data为结点值域，left和right分别为指向左、右子女结点的指针域。假定一棵二叉树采用链接存储，它的广义表表示为r(b(,d(f,g),t(e)，rt,bt,dt和et指针变量分别保存指向r,b,d和e结点的指针值，则：执行BTM(rt)调用后，得到的函数值为_(1)_;执行BTM(bt)调用后，得到的函数值为_(2)_;执行BTM(dt)调用后，得到的函数值为_(3)_;执行BTM(et)调用后，得到的函数值为_(4)_;char BTM(BinTreeNode* BT) static char max=0; if(BT!=NULL) char k1,

31、k2; k1=BTM(BT-left); k2=BTM(BT-right); if(k1max) max=k1; else if(k2max) max=k2; else if(BT-datamax) max=BT-data; return max;(1) t (2) g (3) g (4) e 3. 在a10数组中数据16,35,42,73,54,58,80为一个最小堆，n为整型变量，其值为7，则执行DH(a,n)调用下面算法后数组a中的数据变为_。int DH(int HBT, int& n) if(n=0) cerrnull!endl; exit(1); int temp=HBT0; n-

32、; int x=HBTn; int i=0; int j=2*i+1; while(j=n-1) if(jHBTj+1) j+; if(xdata=r-data) break; r=r-link; if(r=NULL) return 0; p2=p2-link; return 1;判断p2单链表所代表的集合是否为p1单链表所代表的集合的子集合，若是则返回1否则返回0。5. 已知二叉树中的结点类型BinTreeNode定义为: struct BinTreeNode ElemType data; BinTreeNode *left, *right;其中data为结点值域，left和right分别为

33、指向左、右子女结点的指针域。参数bt指向一棵二叉树，引用参数x一开始具有的值小于树中所有结点的值。试根据下面的函数定义指出此算法的功能。 int JB(BinTreeNode* bt, ElemType& x) if(bt=NULL) return 1; else if(JB(bt-left,x)=0) return 0; if(bt-datadata; if(JB(bt-right,x)=0) return 0; else return 1; 算法功能：判断二叉树bt是否为一棵二叉搜索树，若是则返回1否则返回0。六、算法设计题1. 已知二叉树中的结点类型BinTreeNode定义为: struct BinTreeNode char data; BinTreeNode *left, *right;其中data为结点值域，left和right分别为指向左、右子女结点的指针域，根据下面函数声明编写出判断两棵二叉树是否相等的算法，若相等则返回1否则返回0。算法中参数T1和T2为分别指向这两棵二叉树根结点的指针。当两棵树的结构完全相同并且对应结点的值也相同时才被认为相等。 int BTreeEqual(BinTreeNode* T1