复习题2011春夜大(带答案).doc

复习题(1)一. 填空题1抽象数据型是 数学模式 和 定义在设个模式上的基本操作 的总称。2举出线性表的三种存储结构 顺序表示 、 链式表示 和 游标表示 。3.一个队列的入队序列是a、b、c、d，则队列的输出序列为_abcd_。4.栈结构通常采用的两种存储结构是_顺序结构_和_链式结构_。5对二叉树遍历的三种基本顺序是 先序 顺序、 中序 顺序和 后序 顺序。6举出图的两种存储结构 邻接表 和 邻接矩阵 。7. 采用散列技术实现散列表时，需要考虑的两个主要问题是：构造_散列函数_和解决_解决冲突_。二. 选择题1.带表头的单向链表head为空的判断条件是（B）。Ahead=NULLBhead-next=NULLChead-next=headDHead!=NULL2栈操作的原则是（B ）。A先进先出B后进先出C栈顶插入D栈顶删除3.高度为5的二叉树，最多含有（B）个结点。A16B31C32D634非空二叉树的左右链表示法中，非空链域与空链域之间的数量关系是（A）。A前者比后者少2个B前者比后者多2个C前者比后者少1个D前者比后者多1个5已知一株二叉树的先根遍历顺序和中根遍历顺序分别是a、b、d、e、f、c和d、e、f、b、a、c，则该二叉树的后根遍历顺序是：( C )A.e、f、d、b、c、aB.d、f、b、e、c、a C.f、e、d、b、c、aD.d、f、e、b、c、a6任何一株二叉树的叶结点在先根、中根和后根遍历序列中的相对次序（A）。A.不发生改变B.发生改变C.不能确定D.以上都不对7在无向图的邻接表表示法中，一条边（i，j）在邻接表中出现（C）次。A0B1C2D38关键路径是AOE网中的（D）。A. 最短回路B.最长回路C.从源点到汇点的最短路径D. 从源点到汇点的最长路径9折半查找要求表中的元素必须按照关键字（C）排列。A升序B降序C升序或降序D任意顺序10.一组记录的关键字为（48，83，58，43，45，88），则利用堆排序的方法建立的初始堆为（C）。A（43、45、58、83、88、48）B（45、58、83、48、88、43）C（43、45、48、58、83、88）D（43、48、58、83、45、88）三. 判断题. 正确的在括号内画，错误的在括号内画1所谓数据的逻辑结构指的是数据元素之间的逻辑关系。( 对 )。2线性表的链式存储，表中元素的逻辑顺序与物理顺序一定相同。 （ 错 ）3若BT是一株二叉树，则BT中至少有一个叶结点。 （ 对 ）4若将一株树转换成二叉树，则该二叉树的根结点一定没有右子树。（对 ）5无向图的邻接矩阵中各元素之和与图中边的条数相等。（错 ）6完全二叉树中，若一个结点没有左儿子，则该结点一定是叶。（ 对 ）7哈夫曼树中不存在度为1的结点。（ 对 ）8有向图的邻接矩阵一定不是对称的。（ 错 ）9在堆中，以任何结点为根的子树仍然是堆。（ 对 ）10在AOE网中，关键路径是唯一的。（ 错 ）四. 简答题1 假设某通讯系统在通信联络中只能出现A，B，C，D，E，F六种字符,其出现的概率分别是0.07，0.09，0.12，0.22，0.23，0.27，设计该通讯系统的Huffman编码。要求：(1) 按左子树根结点的权不大于右子树根结点的权的次序画出相应的Huffman树； (2) 给出各字符的相应编码；答案：A:1110; B:1111; C:110; D00; E:01; F:10;(3) 计算编码的平均长度。答案：平均长度=4*0.07+4.0.09+3*0.12+2*0.22+2*0.23+2*0.27=2.442 二叉查找树的问题(1) 画出从空的二叉查找树开始，将下列关键字按下述顺序逐个插入后建立的二叉查找树。 9，14，12，5，18，7，1，15，3，16答案：(2) 写出该二叉查找树的中根顺序遍历结果。答案：1，3，5，7，9，12，14，15，16，18.(3) 在该二叉查找树中，查找给定关键字k=15的过程需将k=15依次与哪些关键字进行比较。答案：9，14，18，15.(4) 画出在该二叉查找树中删除关键字14后得到的二叉查找树。 答案：五算法设计1.设计一个将实数数组An中所有的负数移到所有非负数之前的算法。主要思路：设置两个游标i和j，其中i=1,j=n；当Ai为非负数，Aj为负数，则交换Ai和Aj;否则Ai为负数，i+；Aj为非负数，j-，直到i=j。算法如下：void AdjustA(int A,int n) int i=1,j=n; while(i!=j) while(Ai) = 0) j-; if(ilchild; p-lchild = p-rchild; p-rchild = tmp; LRChange ( p-lchild ); LRChange ( p-rchild ); 复习题(2)一. 填空题1高度为k的二叉树最多结点个数为 2k-1 ，最少的结点个数为 k 。2举出图的两种存储结构 邻接表 和 邻接矩阵 。3设有向图G中顶点数为n，则G中最少有 0 条边，最多有 n(n-1) 条边。4 n个顶点的连通图至少有n- 1 条边，强连通图至少有 n 条边。5对图中各顶点进行搜索的顺序主要有 深度优先搜索 和 广度优先搜索 。5归并排序的时间复杂性为O（nlog2n）；选择排序的时间复杂性为 O(n2) 。6快速排序的最大和最小递归深度分别是 n 和 log2n+1 。 二. 选择题1用单向链表存储的线性表，存储每个结点需要两个域：一个是数据域；另一个是（ B ）。A当前结点所在地址B. 指针域C空指针域D空闲域2某二叉树的先根和后根序列正好相反，则该二叉树一定是（ B ）的二叉树。A空或只有一个结点 B高度等于其结点数C任意一个结点无左孩子D任意一个结点无右孩子3具有35个结点的完全二叉树的高度为（ B ）A5B6C7D84非空二叉树的左右链表示法中，非空链域与空链域之间的数量关系是（A）。A前者比后者少2个B前者比后者多2个C前者比后者少1个D前者比后者多1个5已知一株二叉树的后根遍历顺序和中根遍历顺序分别是d、a、b、e、c和d、e、b、a、c，则该二叉树的先根遍历顺序是：()A.a、c、b、e、dB.d、e、c、a、b C.d、e、a、b、cD.c、e、d、b、a6按照二叉树的定义，具有3个结点的二叉树有( C )种。 A.3 B.4 C.5 D.67有m个叶结点的哈夫曼树所具有的结点数为（D）。AmBm+1C2mD2m-18在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1，则度为0的结点个数为( C ) A4 B5 C6 D79折半查找要求表中的元素必须按照关键字（C）排列。A升序B降序C升序或降序D任意顺序10.一组记录的关键字为（46，79，56，38，40，84），则利用快速排序方法，以第一个记录为基准元素得到的一次划分结果为（C）。A（38、40、46、56、79、84）B（40、38、46、79、56、84）C（40、38、56、79、46、84）D（40、38、46、56、79、84）三. 判断题。正确的在括号内画，错误的在括号内画1程序的时间复杂性是指程序在实际机器上的运行时间。（ 错 ）2线性表的顺序存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。（错）3带表头结点的单循环链表中，任意一个结点的后继结点的指针域均不空。（对）4若将一株树转换成二叉树，则该二叉树的根结点一定没有右子树。（ 对 ）5完全二叉树中，若一个结点没有左儿子，则该结点一定是叶。（ 对 ）6二叉查找树中的每株子树仍然是二叉查找树。 （ 对 ）7折半查找要求表中的元素必须按照关键字从小到大的顺序排列。 （ 错）8在任何情况下，快速排序的效率总是最好的（ 错 ）9折半查找算法与二叉查找树算法的时间复杂性是相同的。（ 对 ）10一个带权的连通无向图的最小生成树是唯一的。（错）四简答题1设有N个结点的完全二叉树，顺序存放在数组的1至N单元中，对任意一个结点i，(1) 若i有父亲结点，问父亲结点是哪个？答案：Ai/2 (2) 若i有左儿子，问左儿子是哪个？答案：Ai*2(3) 若i有右儿子，问右儿子是哪个？答案：A2*i+1(4) 试问下标i值最大的非叶结点是哪一个？答案：AN/23 设有一组关键字19,01,23,14,55,20,84,27,68,11,10,77,采用散列函数：H(key)=key MOD 13, 采用线性探测法解决冲突，试在018的散列地址空间中对该关键字序列构造散列表。答案： 五算法设计1设计一个将整数数组An中所有的奇数移到所有偶数之前的算法。主要思路：设置两个游标i和j，其中i=1,j=n；当Ai为偶数，Aj为奇数，则交换Ai和Aj;否则Ai为奇数，i+；Aj为偶数，j+,直到i=j。算法如下：void AdjustA(int A,int n) int i=1,j=n; while(i!=j) while(Ai)%2!=0) i+; while(Aj%2=0) j-