《上交大网络教育学院数据结构第三次作业.pdf》由会员分享，可在线阅读，更多相关《上交大网络教育学院数据结构第三次作业.pdf（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、上海交通大学网络教育学院上海交通大学网络教育学院-数据结构数据结构-第三次作业第三次作业-树和图树和图1、下列说法中正确的是A。二叉树的线索化就是对二叉链表中的n 个空链域进行线索化；B。二叉树一定是度为 2 的树;C。一个度为 2 的树一定为二叉树；D。任何一棵树都可以按照孩子兄弟法转化为一棵二叉树，而且这个二叉树的根结点的右孩子一定不存在。2、四组编码中，哪一组是前缀码A。0，1,00，11B。0，10，110，111C。00，01，001，0001D。0,01,10,113、对于图 1 示的二叉树，先根序列和后根序列分别为：A.ACB和 CBAB.ABC和 CBAC.ABC和 BCAD。
2、ACB 和 BCA4、n 个结点的线索二叉树中的线索数目为：A。（n1）个B。（n+1）个C.(n+2）个D.n 个5、哈夫曼树的带权路径长度是指：选择一项：A。所有结点的权值之和B.除根结点之外所有结点权值之和C。所有叶子结点带权路径长度之和D.带权结点的值6、图 2 示的二叉树的带权路径长度为：A。36B。46C。48D。477、具有 4 个顶点的无向完全图有（）条边。A.16B。6C。12D。208、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（)倍。选择一项：A.1/2B.1C。4D.29、一个深度为 4 的完全二叉树,至少有多少个结点：A。15B。7C。8D。1410、
3、在一个具有 n 个顶点的无向图中，要连通全部顶点至少需要（）条边。A.n1B.n+1C。n/2D。n11、有 n 个结点的二叉树的二叉链表存储结构中有（)个空链域。A。2nB.n-1C。nD。n+112、已知图 6 所示的图，若从顶点A 出发按深度优先搜索法进行遍历，则可能得到的遍历序列为:A.A,E,D，F,C,BB。A,C，F,E，B,DC。A，B，E,C,D，FD.A，E,B,C,F，D13、已知如图 3 示的哈夫曼树,那么电文 CDAA 的编码是：A。11111100B.010110111C.11011100D.11010014、一个有 n 个顶点的无向图最多有()条边。选择一项：A.
4、n(n1）B.n（n1）/2C.nD。2n15、对于一个具有 n 个顶点和 e 条边的无向图，若采用邻接表表示，则表头向量的大小为（）选择一项:A。n-1B.nC.n+1D。n+e16、将含有 41 个结点的完全二叉树从根结点开始编号,根为 1 号,后面按从上到下、从左到右的顺序对结点编号，那么编号为21 的双亲结点编号为：选择一项：A。10B.20C。41D.1117、对于一个具有 n 个顶点的无向图，若采用邻接矩阵表示,则该矩阵的大小()选择一项：A.n2B.(n1)2C。n-1D。n18、判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用（)。选择一项：A。求关键路径的方法
5、B。求最短路径的 Dijkstm 方法C.深度优先遍历算法D.宽度优先遍历算法19、下列序列不是图 5 的拓扑有序序列的是：选择一项：A。1 5 6 2 3 4B。1 5 2 3 6 4C。5 6 1 2 3 4D。1 2 5 6 3 420、对含有()个结点的非空二叉树，采用任何一种遍历方式,其结点的访问序列均相同选择一项:A.不存在这样的二叉树B.0C。2D。121、具有 6 个顶点的无向图至少有()条边才可能是一个连通图。选择一项:A.5B.8C.7D。622、采用邻接表存储的图的深度优先遍历算法类似于二叉树的(）。选择一项:A.后序遍历B.先序遍历C。按层遍历D.中序遍历23、一棵深度
6、为 5 的满二叉树，应该有多少个结点（）选择一项:A。32B.31C.17D。1624、采用邻接表存储的图的广度优先遍历算法类似于二叉树的（）。选择一项：A.按层遍历B。先序遍历C.中序遍历D.后序遍历25、没有度为 1 的结点的二叉树，被称之为严格二叉树。下列不是严格二叉树的是：选择一项：A。满二叉树B.哈夫曼树C。所有非终端结点都有非空的左右子树的二叉树D.完全二叉树26、对于一个具有 n 个顶点和 e 条边的无向图,若采用邻接表表示，则所有邻接表中的结点总数是（）选择一项:A。e/2B.n+eC。eD。2e27、一个所有非终端结点都有非空的左右子树的二叉树，叶子结点的个数为 n,那么二叉
7、树上的结点总数为(）选择一项:A。2n1B。2n+1C.2nD。2n228、用 Prim 算法求下列连通的带权图(图 4）的最小代价生成树,在算法执行的某刻,已选取的顶点集合 U1，2，3，边的集合 TE（1，2）,（2，3），要选取下一条权值最小的边，应当从(）组中选取。选择一项:A。（1，4），（3,4）,（3，5），（2,4）B。（3，4），（3，5），(4，5），（1,4）C。（4，5），（1，3）,(3，5)D.(1，2），（2，3），（3,5)29、在一个有向图中，所有顶点的度数之和等于所有边数的（)倍。选择一项：A。1B。2C。1/2D.430、在二叉树的第 i 层上至多有（)个结点选择一项：A.2i1B。i+2C.2iD。2i-2