5-8章习题-2013

《5-8章习题-2013》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、名词解释1、二叉树：2、哈夫曼树：3、小根堆：4、最小生成树5、拓扑排序6、二叉搜索树7、出度：8、权二、填空1、二叉树的度为：，当深度h=4时，其满二叉树的结点树为：。2、在定义各种数据结构的存储实现时，为增强其数据类型的通用性，应将其定义为类型。如果是定义树的链接存储结构，除了定义数据类型，还应定义链接孩子结点的和。3.一棵二叉树的广义表表示是A（B（C,D）），则对其的中序遍历结果是。4．对一棵完全二叉树的各结点从1开始编号，并按此编号把它顺序存储到一维数组a中，即将根结点编号为1并存储到a[1]中，其余类推，则a[i]元素的左孩子（如果有的话）元素为，右孩子（如果有的话）元素为

2、，双亲元素（如果有的话）为。5.一个大根堆中，值最大的结点是结点。6、同一棵树中的数据元素必须是的。7、一个广义表形式的二叉树A（B,C（，D））此二叉树的深度为8、二叉搜索树是指树上所有结点均大于，同时左右子树又各是一棵排序二叉树。9、哈夫曼树是指此树的带权路径长度（WPL）。10、图由非空顶点集和所组成。无向图某个顶点的度是。11．一个有n个顶点的连通图的最小生成树的边数为。12、对有向图来说，出度是指某个顶点。13、在计算机中若采用索引查找，索引表中的每个索引项应至少包含索引值域和两个域。14、在散列查找中，多个关键字求出的散列地址相同时，若散列地址已被占用，这种现象被称之为。15、

3、在选择排序方法时，在最坏或平均情况下元素移动次数越多，则说明该方法的时间复杂性。三、选择题1、一棵三叉树的结点个数为10，则它的最小深度为？，最大深度为？，正确的是（）。A．5和8B.3和10C.1和10D．2和72.一棵深度为h的二叉树最多有（）个结点。A．2h+1B．2h-1C．2h+1D．2h-13.一棵二叉树的第i层最多有（）个结点。A．2i+1B．2i-1C．2i+1D．2i-14、在计算机领域，磁盘上的目录结构就是一棵树，对于这种数据结构，在查找时采用哪种方法较好？（）A．顺序查找B.二分查找C.索引查找D.散列查找A．1B.2C.3D.45、如果有一棵完全二叉树上的结点数是9

4、，那么这棵二叉树的最大深度是（）A．2B．3C．4D．56、下列算法是二叉树的（）。voidPreorder(structBTreeNode*BT){if(BT!=NULL){printf("%c",BT->data);Preorder(BT->left);Preorder(BT->right);}}A．前序遍历算法B．中序遍历算法C．后序遍历算法D．按层遍历算法7、二叉搜索树的特点是（）。A．后序遍历有序B．按层遍历有序C．前序遍历有序D．中序遍历有序8、哈夫曼编码是（）A．等长编码B．无前缀编码C．有前缀编码D．最短编码9、根据大根堆排序，其排序结果为（）。A．无序B．升序C．降序D．

5、逆序10．一个图的边集形如：E(G)={(0,1),(0,2),(1,4),…},这是一个（）。A．无向无权图B．有向无权图C．无向带权图D．有向带权图11．一个图的边集形如：E(G)={<0,1>,<0,2>,<1,4>,…},这是一个（）。A．无向无权图B．有向无权图C．无向带权图D．有向带权图12．一个图的边集形如：E(G)={<0,1>2,<0,2>3,<1,4>5,…},这是一个（）。A．无向无权图B．有向无权图C．无向带权图D．有向带权图13．一个图的边集形如：E(G)={(0,1)2,(0,2)3,(1,4)5,…},这是一个（）。A．无向无权图B．有向无权图C．无向带权图D

6、．有向带权图14.一个无向带权图的邻接矩阵是一个（）。A．对角矩阵B．对称矩阵C．非对称矩阵D．行、列数不等的矩阵15．对一个有向图作拓扑排序，结果总有若干顶点不能进入序列，这说明（）。A．图中一定没有回路B．图中可能有回路C．图中顶点顺序不对D．图中一定有回路16.以下查找算法是（）算法。intSeqsch(structElemTypeA[],intn,KeyTypeK){inti;A[n].key=K;for(i=0;;i++)if(A[i].key==K)break;if(i

7、eqsch()算法中returni;的含义是（）。A．查到的数据B．查到的数据的地址C．查到的数据的下标D．查到的数据的位置18．如果采用h(K)=K%13计算散列地址，则元素64的初始散列地址为（）。A．8B．12C．13D．1419．对有序表进行二分查找，算法的时间复杂度为（）。A．O（1）B．O(log2n)C．O（n）D．O（n2）20．以下排序算法是（）算法。voidBubbleSort(structElemT