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

数据结构 A期中模拟试卷第 1页共 4 页 南京邮电大学通达学院 2014/2015 学年第一学期 数据结构 A期中模拟试卷 本试卷共本试卷共4 4页；页；考试时间考试时间100100分钟；分钟； 院(系)班级学号姓名 题号一二三四五六七八总总 分分 得分 一、一、填空题（每题填空题（每题 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，A 2.在深度为 5 的满二叉树中，叶子节点的个数为_ A.32B.31C.16D.15 3.已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的 结果为. ACBEFDAB FEDCBAC CBEDFAD不定 4.已知中缀表达式为 a*(b+c)-d/e，请问下列哪个为正确的后缀表达式_ A.abc+*de/-B. bc+a*de/-C. bc+*a/de-D.abc+*de/- 5.一棵具有 n 个结点的完全二叉树的树高度（深度）是（） Alogn+1Blogn+1ClognDlogn-1 数据结构 A期中模拟试卷第 2页共 4 页 三、简答题（每题三、简答题（每题 10 分，共分，共 6 题）题） 1.下图所示的森林: (1)求树(a)的先根序列和后根序列; (2)求森林先序序列和中序序列; (3)将此森林转换为相应的二叉树; A BC DE F G H IJ K (a) (b) 2. 设有正文 AADBAACACCDACACAAD,字符集为 A,B,C,D,设计一套二进制编码，使得上述正 文的编码最短。 数据结构 A期中模拟试卷第 3页共 4 页 N P G H J MOL I K 3设对一棵二叉树进行中序遍历和后序遍历的结果分别如下： 前序：ABCDEFIGJH 中序：BDCAIFJGHE 画出该二叉树 4.将图中的森林转化为二叉树。 数据结构 A期中模拟试卷第 4页共 4 页 5.设有字符串集 S=A,B,C,D,E,F,W 为各字符的使用频率，W=2,3,5,7,9,12,对字符集 合进行哈夫曼编码。 （1）画出哈夫曼树； （2）计算加权路径长度； （3）求各字符的编码。 6.给出图中所示的稀疏矩阵顺序表示的行三元组表和列三元组表，并求快速转置算法中所 得的数组 num和 k的值。 数据结构 A期中模拟试卷第 5页共 4 页 南京邮电大学通达学院 2014/2015 学年第一学期 数据结构 B期中模拟试卷答案 本试卷共本试卷共4 4页；页；考试时间考试时间100100分钟；分钟； 院(系)班级学号姓名 题号一二三四五六七八总总 分分 得分 三、三、填空题（每题填空题（每题 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)将此森林转换为相应的二叉树; A BC DE F G H IJ K (a) (b) (1) ABCDEF;BDEFCA；(2) ABCDEFGHIJK;BDEFCAIJKHG 林转换为相应的二 数据结构 A期中模拟试卷第 6页共 4 页 叉树； A G B C D E F H I J K 2. 设有正文 AADBAACACCDACACAAD,字符集为 A,B,C,D,设计一套二进制编码，使得上述正 文的编码最短。 答：字符 A，B，C，D 出现的次数为 9,1,5,3。其哈夫曼编码如下 A:1，B:000，C:01，D:001 3设对一棵二叉树进行中序遍历和后序遍历的结果分别如下： 前序：ABCDEFIGJH 中序：BDCAIFJGHE 画出该二叉树 13 5 9 0 0 0 1 1 1 数据结构 A期中模拟试卷第 7页共 4 页 A BE D C G J I F H 5.设有字符串集 S=A,B,C,D,E,F,W 为各字符的使用频率，W=2,3,5,7,9,12,对字符集 合进行哈夫曼编码。 （1）画出哈夫曼树；