2331数据结构.doc

高等教育自学考试 复习题 （课程代码 ） 一、单项选择题【 】． 【 】 A． B．C． D．) 3．【 】 A． B．C． D．．【 】 A．B． C． D． 5．【 】 A． B．C．D．．【 】 A． B．C．D．．【 】 A． B．C．D．．【 】 A． B．C．D．．【 】 A． B．C．D．．【 】 A． B．C．D．．【 】 A．B．C．D．．“abcdecdedcd”，S2 = “cd”，则S2在S1中的位置是 【 】 A． B．C．D．．A中，每一个数组元素A[ i，j ] 占用3个存储字，行下标i从1到8，列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字数是 【 】 A． B．C． D．【 】 A． B．C．D．【 】A． B．C．D．【 】A． B．C．D．．【 】 A． B．C． D．【 】A． B．C．D．【 】A． B．C．D．．【 】 A．B．C．D．．【 】 A．B．C．D．．【 】 A． B．C． D．．【 】 A． B．C． D．．【 】 A． B．C． D．．【 】 A． B．C． D．．【 】 A． B．C． D．【 】 A． B．C． D．．【 】 A． B．C． D．．【 】 A． B．C．D．．【 】 A． B．C． D．1． 2． 3． 4． 5．6． 7． 8． 9． 10．11． 12． 13． 14． 15．16． 17． 18． 19． 20．1． 22． 23． 24． 25．6． 27． 28． 29． 30． 二、 题 该广义表为C(x,(x,y),((x,y),y,z),(x)) 32．以下面数据作为叶子结点的权值构造一棵哈夫曼树，并计算出其带权路径长度。 17，3，7，8，24，10，16，9，6 哈夫曼树如下所示： WPL ＝ 24×2＋17 ＋ 10 ＋16 ＋ 9）×3＋（3 ＋ 7 ＋ 8 ＋ 6）×4＝300 33．已知一个无向图的顶点集为{a，b，c，d，e，f}，其邻接矩阵如下所示 画出该图的图形； 分别画出从顶点1出发进行深度优先和广度优先遍历所生成的生成树。 答： (1) 该图的图形如下： (2) 深度优先生成树： 广度优先生成树： 34．给定关键字集合（45，28，52，20，10，35，40，70，30，75，63，32）， (1) 从一棵空的二叉排序树开始，按表中元素的次序构造一棵二叉排序树； (2) 画出从该二叉排序树中删除关键码28和52后的结果。 答： (1) 二叉排序树如下： (2) 删除关键码28和52后的二叉排序树如下： 三、题．“x not in L”); if(q = = L) Error(“x is the first node, it has no prior node”); q － data = x; q － next = p － next; free( ③ ); } ① ② ③ 答：① p － next ② p = = NULL ③ p 36．写出下列程序段的输出结果。 void main() { Stack S;