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