资源描述：
《数据结构第二次作业题及答案》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、第2次作业一、单项选择题（本大题共60分，共20小题，每小题3分）1.设给定权值总数有n个，其赫夫曼树的结点总数为()。A.不确定B.2nC.2n+1D.2n-12.有向图G=(V,E),其中V(G)={0,1,2,3,4,5}，用三元组表示弧及弧上的权d.E(G)为{,}，则顶点0到顶点2,3,4,5的最短路径和为（）。A.140B.150C.160D.1703.孩子兄弟表示法中，若要访问结点x的第i个孩子，则要先从firstchild域找到第1个孩子结点，然后沿着孩子结点的nextsibling域连续
2、走（）步，便可找到x的第i个孩子。A.1B.2C.i-1D.i4.以下四个选项中DAG（有向无环图）是（）。A.[P_26FAD2FCAC4D172D42207]B.[P_F2B9C7D0DE6688B37BAE6D2E7B]C.[P_9EB00D683EAFDAD354]5.由3个结点所构成的二叉树有（）种形态。A.3B.4C.5D.66.对数据元素序列（49，72，68，13，38，50，97，27）进行排序，如果采用起泡排序方法，则第二趟排序结果是(）。A.49，68，13，38，50，72，27，
3、97B.13，38，49，50，27，68，72，97C.49，13，38，50，68，27，72，97D.13，38，49，27，50，68，72，977.基数排序需要以下数据结构的辅助（）。A.栈B.队列C.树D.森林8.下面关于哈希(Hash，杂凑)查找的说法正确的是()。A.哈希函数构造的越复杂越好，因为这样随机性好，冲突小B.除留余数法是所有哈希函数中最好的C.删除运算方便D.不存在特别好与坏的哈希函数，要视情况而定9.下面是求连通网的最小生成树的prim算法：集合VT，ET分别放顶点和边，初始
4、为VT为网中任意一点，ET为空，下面步骤重复n-1次:a：选i属于VT，j不属于VT，且（i，j）上的权最小；b：（）A.顶点i加入VT，（i,j）加入ETB.顶点j加入VT，（i,j）加入ETC.顶点j加入VT，（i,j）从ET中删去D.顶点i,j加入VT，（i,j）加入ET10.快速排序在最坏情况下的时间复杂度是()。A.O(logn)B.O(n)C.O(n*logn)D.O(n2)11.设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结
5、点个数是（）。A.M1B.M1+M2C.M3D.M2+M312.有一份电文中共使用6个字符:a,b,c,d,e,f,它们的出现频率依次为2,3,4,7,8,9，试构造一棵哈夫曼树，字符c的编码是（）。A.001B.101C.010D.10013.二叉树是非线性数据结构，所以（）。A.它不能用顺序存储结构存储B.它不能用链式存储结构存储C.顺序存储结构和链式存储结构都能存储D.顺序存储结构和链式存储结构都不能使用14.判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用（）。A.求关键路径方法
6、 B.求最短路径的Dijkstra方法C.广度优先遍历算法D.深度优先遍历算法15.对于一个具有n个顶点e条边的无向图的邻接表的表示，邻接表的边结点个数为（）。A.2eB.n+eC.n+2eD.n+e+116.下列排序算法中()不能保证每趟排序至少能将一个元素放到其最终的位置上。A.快速排序B.shell排序C.堆排序D.冒泡排序17.堆排序的平均时间复杂度为（）。A.O(logn)B.O(n)C.O(nlogn)D.O(n2)18.有一组数，顺序是“4，7，8，1，9”，用冒泡排序法将这组数从小到大排序
7、，第二趟第二次对比的数据两个数是()。A.1、4B.4、7C.1、7D.1、819.快速排序算法是对什么算法的改进？（）A.直接插入排序B.希尔排序C.起泡排序D.以上答案都不对20.基数排序是（）。A.稳定的B.不稳定的C.看具体情况D.未知二、判断题（本大题共40分，共20小题，每小题2分）1.对无序表用折半查找比顺序查找快。2.对于无向图来说，若深度优先遍历过程中遇到回边（即指向已访问过的顶点的边），则必定存在环。3.根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素的过程，称为
8、查找。4.若二叉排序树非空，则新结点的值和根结点比较，若小于根结点，则插入到右子树；否则插入到左子树。5.克鲁斯卡尔算法适应范围为稀疏图。6.二叉树中每个结点有两棵非空子树或有两棵空子树。7.有n个数存放在一维数组A[1..n]中，在进行顺序查找时，这n个数的排列有序或无序其平均查找长度不同。8.在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要n条弧。9.在散列检索中，“比较”操作一般也是不可避免的。10.图或
