《对些特殊矩阵采用压缩存储的目的主要是为了》由会员分享，可在线阅读，更多相关《对些特殊矩阵采用压缩存储的目的主要是为了（4页珍藏版）》请在金锄头文库上搜索。
1、中中国民航飞行学院试卷国民航飞行学院试卷 考试年月_课程名称_ 学生姓名_专业_班级_学号_ 试卷密封线 试卷密封线本试卷共 4 页，该页为第 1 页题 号1 一一2 二二3 三三4 四四5 五五6 六六7 七七8 八八9 九九10 十十11 十一十一12 十二十二总分总分分 数阅卷教 师签名数据结构数据结构期末考试题（期末考试题（A 卷）卷）一、一、 单项选择题（共单项选择题（共 15 小题，每小题小题，每小题 2 分，共分，共 30 分）分）1组成数据的基本单位是 。A数据项 B数据类型 C数据元素 D数据变量2下面程序段的时间复杂度为 。for (int i = 0;ilink=p- l
2、ink - link; Bp=p-link; p-link =p-link -link;Cp-link =p-link; Dp =p-link -link;4栈通常采用的两种存储结构是 。A线性存储结构和链表存储结构 B散列方式和索引方式C链表存储结构和数组 D线性存储结构和非线性存储结构5以数组 Q0.m1存放循环队列中的元素，变量 rear 和 qulen 分别指示循环队列中队尾元素的实际位置和当前队列中元素的个数，队列第一个元素的实际位置是 Arearqulen Brearqulenm Cmqulen D1（rearmqulen）% m6对一些特殊矩阵采用压缩存储的目的主要是为了 。A表
3、达变得简单 B对矩阵元素的存取变得简单C去掉矩阵中的多余元素 D减少不必要的存储空间的开销7两个字符串相等的充分必要条件是 。A两串的长度相等B两串包含的字符相同C两串的长度相等，并且两串包含的字符相同D两串的长度相等，并且对应位置上的字符相同8某栈的输入序列为 1，2，3，4，下面的四个序列中 不可能是它的输出序列。A1，3，2，4 B2，3，4，1C4，3，1，2 D3，4，2，19数组 A810中，每个元素的长度为 3 个字节，从首地址 SA 开始连续存放在存储器内，该数组按列存放时，元素 A47的起始地址为 。ASA+141 BSA+180 CSA+222 DSA+22510稀疏矩阵一
4、般的压缩存储方法有两种，即 。A二维数组和三维数组 B三元组和散列 C三元组和十字链表 D散列和十字链表11若有广义表 A (a)，则表尾为 。AaB( ( ) )C空表D(a)12在一非空二叉树的中序遍历序列中，根结点的右边 。A只有右子树上的所有结点 B只有右子树上的部分结点C只有左子树上的部分结点 D只有左子树上的所有结点中中国民航飞行学院试卷国民航飞行学院试卷 考试年月_课程名称_ 学生姓名_专业_班级_学号_ 试卷密封线 试卷密封线本试卷共 4 页，该页为第 2 页。8. n 个顶点的连通图至少有 条边。9. 在一个图中，所有顶点的度数之和等于所有边数的 倍。三、三、 判断正误题（每
5、题判断正误题（每题 1 分，共分，共 10 分，正确打分，正确打，错误打，错误打）【 】1线性结构的链接存储，表中元素的逻辑顺序与物理顺序一定相同。【 】2算法是一个有穷指令的集合，它为解决某一特定任务规定了一个运算序列。它应当具有正确性、可使用性、可读性和效率以及健壮性等特性。【 】3在单链表中，要访问某个结点，只要知道该结点的指针即可；因此，单链表是一种随机存取结构。【 】4栈和队列的共同点是只允许在端点处插入和删除元素。【 】5一棵哈夫曼树中不存在度为 1 的结点。【 】6二叉树的前序遍历序列中,任意一个结点均处在其子女结点的前面。【 】7二叉树中任何一个结点的度都是 2。【 】8满二叉
6、树一定是完全二叉树。【 】9邻接矩阵只适用于稠密图（边数接近于顶点数的平方） ，邻接表适用于稀疏图（边数远小于顶点数的平方） 。【 】10一个有向图的邻接表和逆邻接表中结点的个数可能不等。四四、应用题（共应用题（共 40 分）分）1数据的逻辑结构分为哪两大类？这两类结构各自的特点是什么? （本小题本小题 4 分分）13在有 n 个叶子结点的霍夫曼树中，其结点总数为_。A不确定 B2n C2n1 D2n114带权有向图 G 用邻接矩阵 A 存储，则顶点 i 的出度等于 A 中 。A第 i 行非的元素之和 B第 i 列非的元素之和C第 i 行非且非 0 的元素个数 D第 i 列非且非 0 的元素个
7、数15在一个具有 n 个顶点的无向图中，要连通全部顶点至少需要 条边。An Bn+1 Cn-1 Dn/2二、二、 填空题（共填空题（共 20 分）分）1. 数据结构的三要素是指 、 和 。2. 一种抽象数据类型包括 和 两个部分。3. 在单链表中，每个结点由两个域组成，一个域存放 ，另一个域存放 ，该域给出下一个结点的开始地址。4. 一维数组的逻辑结构是 ，存储结构是顺序存储表示。对于二维数组，有 和 两种不同的存储方式。5. 栈的插入与删除操作都是在 位置进行的，而队列的插入在 进行，删除在 进行。6. 假定一个顺序存储的循环队列用一维数组 elementmaxSize表示，队头和队尾指针分
8、别为 front 和 rear，则判断队列是否为+空的条件是 ，判断队列是否满的条件是 。7. 对于一棵具有个结点的二叉树，对应二叉链表中指针总数为 个，其中 个用于指向子女结点， 个指针空闲着。中中国民航飞行学院试卷国民航飞行学院试卷 考试年月_课程名称_ 学生姓名_专业_班级_学号_ 试卷密封线 试卷密封线本试卷共 4 页，该页为第 3 页。2下图所示为在带表头结点的单链表中插入一个新结点的情况，其中图 a 是在非 空表中第一个结点前插入一个新结点 newnode，图 b 是在空表中插入一个新结点 newnode。试写出插入语句。 （本小题本小题 4 分分）3请画出下图所示的树所对应的二叉
9、树，并写出对二叉树进行中序遍历和后序遍 历的结果。 （本小题本小题 6 6 分分）2 3 4 5 6 7 8 1 4设某信息由 a、b、c、d、e 五个字符组成，每个字符出现的概率分别为：0.12、0.40、0.15、0.08、0.25，把这些字符编码成二进制的 0、1 序列，采用变长编码的结果如图所示。 （本小题本小题 12 分分）请根据该示例，完成下面的问题：（1）给出电文 CAST CAST SAT AT A TASA ，求出每个字符出现的频率，并根据出现的频率构造 Huffman 树，计算其带权路径长度、每个字符的 Huffman 编码、总码数。 （不考虑空格）（2）如果给出二进制序列
10、 011001011101001001001110，根据你构造的 Huffman 树和 Huffman 编码，将该二进制序列进行译码。中中国民航飞行学院试卷国民航飞行学院试卷 考试年月_课程名称_ 学生姓名_专业_班级_学号_ 试卷密封线 试卷密封线本试卷共 4 页，该页为第 4 页。本试卷共_页，该页为第 6 页。本试卷共_页，该页为第 8 页。本试卷共_页，该页为第 10 页。本试卷共_页，该页为第 14 页。本试卷共_页，该页为第 12 页。本试卷共_页，该页为第 5 页。本试卷共_页，该页为第 9 页。本试卷共_页，该页为第 11 页。本试卷共 4 页，该页为第 4 页。6某个图的邻接矩阵表示如下：（本小题本小题 8 分分）（1） 试根据该邻接矩阵画出对应的图（2） 对图从顶点 V0出发进行深度优先搜索，给出顶点的搜索顺序（3） 画出从顶点 V0出发进行深度优先搜索所得到的深度优先生成（DFS）树。5当输入下列数据 4，2，5，8，3，6，10，14 时，请根据该数据流构造一个最小堆，要求写出每步过程。 （本小题本小题 6 分分）
