国际学院07级数据结构补考试题.docVIP

内蒙古科技大学2009/2010学年第二学期 《数据结构》补考试题 课程号 考试方式：闭卷 使用专业、年级：国际学院计算机07-3、4、5、6班 任课教师：兰孝文、康懿 考试时间： 备 注： 一、选择题（每题2分，共2*13=26分） 1.数据的不可分割的基本单位是____。 A.元素 B.结点 C.数据类型 D.数据项 2. 将递归算法转换成对应的非递归算法时，通常需要使用 。 A．栈 B．队列 C．链表 D．树 3.____又称为FIFO表。 A.队列 B.散列表 C.栈 D.哈希表 4.广义表(a,((b,( )),c),(d,(e)))的深度是____。 A.5 B.4 C.3 D.2 5.有n(n0)个结点的完全二叉树的深度是____。 A.(log2(n)( B.(log2(n)( +1 C.(log2(n+1)( D.(log2(n)( +1 6. 链表不具有的特点是 。 A．插入、删除不需要移动元素 B．可随机访问任一元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比 7.对长度为10的表作2_路归并排序,共需移动____次(个)记录。 A.20 B.45 C.40 D.30 8.当需要随机查找线性表的元素时,宜采用____作存储结构。 A.双向链表 B.循环链表 C.顺序表 D.单链表 9.____是Yu**Jia**Shan的子串。 A.Yu B.jia C.**shan D.YuJiaShan 10.无向完全图的邻接矩阵是____矩阵。 A.对称 B.上三角 C.下三角 D.稀疏 11.查找哈希(Hash)表,解决冲突的的方法有____。 A.除留余数法 B.线性探测再散列法 C.直接地址法 D.链地址法 12.深度为k的满二叉树有____个分枝结点。 A.2k-1 B.2k-1-1 C.2k+1 D.2k-1+1 13.设依次进入一个栈的元素序列为c,a,b,d,不可得到出栈的元素序列有_____。 A. a,b,c,d B. c,a,b,d C. b,a,d,c D. c,d,a,b 二、填空(每空2分,共2*12=24分) 1.数据结构在计算机中的表示(映象)称为 ________________。 2.线性表中 ____________________________ 称为表的长度。 3.设数组A[10][8]的基地址为2000,每个元素占2个存储单元,若以行序为主序顺序存储,则元素A[4][5]的存储地址为_____；若以列序为主序顺序存储,则元素A[4][5]的存储地址为______。 4.一棵深度为6的满二叉树有______个非终端结点。 5.若一棵二叉树中有8个度为2的结点,则它有_____个叶子。 6.顺序查找n个元素的顺序表,当使用监视哨时,若查找成功,比较关键字的次数至少为____次, 最多为____次；若查找失败,比较关键字的次数为____次。 7.设长度为n的线性表顺序存储,若在它的第i-1和第i个元素之间插入一个元素, 共需移动 _________ 个元素(1i≤n)。 8.树中结点A的 ____________________ 称为结点A的度。 9.具有10个顶点的无向图,边的总数最多为 _____________ 。 三、试画出下列存储结构图(每小题4分,共8分) 1.二叉树的顺序存储结构（图1）: 图1 2.图的邻接矩阵（图2）: 图2 四、求解下列问题 (共34分) 1.给定30个字符组成的电文: D D D D D A A A B E E A A F C D A A C A B B C C C B A A D D 试为字符 A、B、C、D、E、F 设计哈夫曼(Huffman)编码。 (1)画出相应的哈夫曼树；（4分） (2)分别列出 A、B、C、D、E、F 的哈夫曼码；（3分） (3)计算该树的带权路径长度WPL。（3分） 2.试将 ( 10,8,9,12,20,5,6,15,19,25 )表中所有元素插入一棵初始为空的二叉排序树中, 使之仍是一棵二叉