南邮通达数据结构B期中模拟试卷及答案.doc

南京邮电大学通达学院 2014/2015学年第一学期数据结构A期中模拟试卷 本试卷共 4 页； 考试时间 100 分钟； 院(系) 班级 学号 姓名 题号一二三四五六七八总 分得分一、 填空题（每题4分，共5题）1. 四种基本的数据逻辑结构是:_、_、_、_2. 在数据结构中，数据的逻辑结构分线性结构和_ 。3. 对于栈只能在_插入和删除元素。4. 数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放的存储器内，该数组按行存放，元素A58的地址为 。5. 若一课二叉树的前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为_二、 选择题（每题4分，共5题）1设有一个栈，元素的进栈次序为A，B，C，D，E，下列_是不可能的出栈序列。 A. E，A，B，C，DB. B，C，D，E，A C. A，B，C，D，ED. E，D，C，B，A2.在深度为5的满二叉树中，叶子节点的个数为_ A.32 B.31C.16D.15 3.已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为.ACBEFDA B FEDCBA C CBEDFA D不定 4.已知中缀表达式为a*(b+c)-d/e，请问下列哪个为正确的后缀表达式_A.abc+*de/- B. bc+a*de/-C. bc+*a/de- D.abc+*de/- 5. 一棵具有 n个结点的完全二叉树的树高度（深度）是（ ）Alogn+1 Blogn+1 Clogn Dlogn-1 三、简答题（每题10分，共6题） 1.下图所示的森林:(1)求树(a)的先根序列和后根序列;(2)求森林先序序列和中序序列;(3)将此森林转换为相应的二叉树; 2. 设有正文AADBAACACCDACACAAD,字符集为A,B,C,D,设计一套二进制编码，使得上述正文的编码最短。3设对一棵二叉树进行中序遍历和后序遍历的结果分别如下：前序：ABCDEFIGJH中序：BDCAIFJGHE 画出该二叉树4.将图中的森林转化为二叉树。NPGHJMOLIK5.设有字符串集S=A,B,C,D,E,F,W为各字符的使用频率，W=2,3,5,7,9,12,对字符集合进行哈夫曼编码。（1）画出哈夫曼树；（2）计算加权路径长度；（3）求各字符的编码。6.给出图中所示的稀疏矩阵顺序表示的行三元组表和列三元组表，并求快速转置算法中所得的数组num和k的值。南京邮电大学通达学院 2014/2015学年第一学期数据结构B期中模拟试卷答案 本试卷共 4 页； 考试时间 100 分钟； 院(系) 班级 学号 姓名 题号一二三四五六七八总 分得分三、 填空题（每题4分，共5题）6. 四种基本的数据逻辑结构是集合、线性、树、图7. 在数据结构中，数据的逻辑结构分线性结构和非线性结构 。8. 对于栈只能在栈顶插入和删除元素。9. 数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放的存储器内，该数组按行存放，元素A58的地址为 LOCsa+(48*3)。10. 若一课二叉树的前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为DGEBHFCA四、 选择题（每题4分，共5题）ABAAA三、简答题（每题10分，共6题） 1.下图所示的森林:(1)求树(a)的先根序列和后根序列;(2)求森林先序序列和中序序列;(3)将此森林转换为相应的二叉树; (1) ABCDEF; BDEFCA；(2) ABCDEFGHIJK; BDEFCAIJKHG林转换为相应的二叉树；2. 设有正文AADBAACACCDACACAAD,字符集为A,B,C,D,设计一套二进制编码，使得上述正文的编码最短。答：字符A，B，C，D出现的次数为9,1,5,3。其哈夫曼编码如下A:1，B:000，C:01，D:00113590001113设对一棵二叉树进行中序遍历和后序遍历的结果分别如下：前序：ABCDEFIGJH中序：BDCAIFJGHE 画出该二叉树ABEDCGJIFH5.设有字符串集S=A,B,C,D,E,F,W为各字符的使用频率，W=2,3,5,7,9,12,对字符集合进行哈夫曼编码。（1）画出哈夫曼树；（2）计算加