数据结构作业二.doc

《数据结构作业二.doc》由会员分享，可在线阅读，更多相关《数据结构作业二.doc（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、)位置。A. 前一个 B. 后一个 C. 当前 D. 后面5. 假定一个顺序存储的循环队列的队头和队尾指针分别为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-l

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

4、 (a)，其表尾为（ C ）。Aa 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+1 C. 2i-1 D. 2n二、填空题1. 链表与顺序表、索引表、散列表等都是数据逻辑

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

6、义表括号的（重数）。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+1-1）个结点。假定树根结点的高度为0。三、判断题（对/错）1在用单链表表示的链式队列Q中，队头指针为Q-front，队尾指针为Q-rear，则队空条件为Q-front = Q-rear。

7、错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. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同

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

9、c d e f g h i j k-1 0 1 1 3 0 5 6 6 0 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

11、,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.

12、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; _(1)_; if(p-lLink=q) _(2)_; else _(3)_; return 1; (1) q = q-lLink

13、(2) return 1 (3) return 03. 设有一个求解汉诺塔（Hanoi）的递归算法如下：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(

14、BT-right,BT,X) (3) return NULL或return 0六、算法设计题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试编写

15、一个递归函数，计算这样的多项式的值。float poly ( float x, 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分别为指向左、右子女结点的指针域。根据下面函数声明编写出求一棵

16、二叉树高度的算法，该高度由函数返回。假定树根的层次为0，参数BT初始指向这棵二叉树的根结点。 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可

17、以没有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=N

18、ULL & BT-right=NULL) return 1; else return 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 )结点。

19、A. 兄弟 B. 父子 C. 祖先 D. 子孙3. 已知一棵树的边集表示为, , , , , , , ，则该树的深度为(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的顺序存储的有序表，

20、若采用折半搜索，则对所有元素的搜索长度中最大的为( A )的值向上取整。 A. 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

21、. 510. 设G1=（V1，E1）和G2=（V2，E2）为两个图，如果V1Í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在一

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

23、连通无向图各顶点的度之和最少为（2(n-1)）。8. 设图G = (V, E)，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

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

25、3,4,5,6; E=,6,5; 假定该图采用邻接表表示，每个顶点邻接表中的边结点都是按照终点序号（即数值域的值）从大到小的次序链接的，试按照遍历算法写出： (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; 试根据迪

26、克斯特拉(Dijkstra)算法求出从顶点0到其余各顶点的最短路径，在下面填写对应的路径长度。 顶点： 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,

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

28、80，根据归并趟数计算公式S = logkm = logk80 = 3得：k380。由此解得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分别为指

29、向左、右子女结点的指针域。根据下面函数的定义指出函数的功能。算法中参数BT指向一棵二叉树。 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定义为: st

30、ruct BinTreeNode char data; BinTreeNode *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) s

31、tatic char max=0; if(BT!=NULL) char k1,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) ce

32、rrnull!endl; exit(1); int temp=HBT0; n-; 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

33、*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-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为分别指向这两棵二叉树根结点的指针。当两棵树的结构完全相同并且对应结