《数据结构》期中试卷.doc

数据结构期中试卷（计算机310(1-2)）班级 姓名 学号 成绩【说明】：1、闭卷考试，时间120分钟； 2、选择题和填空题做在试卷上，综合题做在答题纸上。一、选择题（每个空只有一个正确答案，将其找出来，打上）每题1分，共20分1、数据结构是一门研究非数值计算的程序设计问题中计算机的A以及它们之间的B和运算的学科。A.操作对象B.计算方法C.逻辑存储D.数据映象A.结构B.关系C.运算D.算法2、数据结构被形式地定义为（D，S），其中D是B的有限集，S是D上D的有限集。A.算法B.数据元素C.数据操作D.逻辑结构A.操作B.映象C.存储D.关系3、在数据结构中，从逻辑上可以把数据结构分为C。A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构4、线性表的顺序存储结构是一种A的存储结构，线性表的链式存储结构是一种B的存储结构。A.随机存取B.顺序存取C.索引存取D.HASH存取5、算法分析的目的是C，算法分析的两个主要方面是A。A.找出数据结构的合理性 B.研究算法中的输入和输出关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性A.空间复杂性和时间复杂性 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性6、计算机算法指的是C，它必具备输入、输出和B等五个特性。A.计算方法B.排序方法 C.解决某一问题的有限运算序列D.调度方法A.可执行性、可移植性和可扩充性B.可执行性、确定性和有穷性 C.确定性、有穷性和稳定性D.易读性、稳定性和安全性7、线性表的逻辑顺序与存储顺序总是一致的，这种说法B。A.正确B.不正确8、线性表若采用链表存储结构时，要求内存中可用存储单元的地址D。A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续不连续都可以9、在以下的叙述中，正确的是B。A.线性表的线性存储结构优于链表存储结构B.二维数组是它的每个数据元素为一个线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出10、一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是C。A.edcbaB.decbaC.dceabD.abcde11、一个队列的入队序列是1，2，3，4，则队列的输出序列是B。A.4，3，2，1B.1，2，3，4C.1，4，3，2D.3，2，1，412、栈和队列的共同点是C。A.都是先进后出B.都是先进先出C.只允许在端点处插入和删除元素D.没有共同点13、递归函数f(n)=f(n-1)+n(n1)的递归出口是，递归体是。A.f(1)=0B.f(1)=1C.f(0)=1D.f(n)=nA.f(1)=0B.f(0)=1C.f(n)=f(n-1)+nD.f(n)=n14、将递归算法转换成对应的非递归算法时，通常需要使用。A.栈B.队列C.链表D.树15、树最合适用来表示。CA.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据16、二叉树的前序遍历序列中，任意一个结点均处在其孩子结点的前面，这种说法A。A.正确B.错误17、设高度为h的二叉树只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为B。A.2hB.2h-1C.2h+1D.h+118、任何一棵二叉树的叶结点在先序、中序和后序遍历中的相对次序C。A.不发生改变B.发生改变C.不能确定D.以上都不对19、实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用C存储结构。A.二叉链表B.广义表存储结构C.三叉链表D.顺序存储结构20、对一棵满二叉树，m个树叶，k个分支结点(根结点看作一个分支结点)，n个结点，则。A.n=k+mB.k+m=2nC.m=k-1D.n=2k-1二、填空题（将正确的答案填在相应的空中）每个空0。5分，共10分1、数据逻辑结构包括线性结构、树形结构和图形结构三种类型，树形结构和图形结构合称非线性结构。2、在树形结构中，树根结点没有父结点，其余每个结点有且只有1个前驱结点；叶子结点没有孩子结点，其余每个结点的后续结点可以两个或者一个。3、数据结构在计算机中的表示称作数据的 。4、栈和队列都是线性结构，对于栈只能在栈顶插入和删除元素，对于队列只能在队首插入元素和队尾删除元素。5、向一个长度为n的线性表的第i个元素(1in+1)之前插入一个元素时，需向后移动n-i+1个元素。6、将树转化为二叉树的基本目的是树可采用二叉树的存储结构并利用二叉树的已有算法解决树的有关问题。7、深度为k的完全二叉树至少有个结点，至多有个结点，若按自上而下，从左到右给结点编号（从1开始），则编号最小的叶子结点的编号是。8、根据二叉树的定义，具有三个结点的二叉树有5种不同的形态，它们分别是、。三、简答题 每题6分，共30分1 线性表有两种存储结构：一是顺序表，二是链表。 试问：（1）两种存储表示各有哪些主要优缺点？ （2）如果有n个线性表同时并存，并且在处理过程中各表的长度会动态发生变化，线性表的总数也会自动地变化。在此情况下，应选用哪种存储结？为什么？ （3）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么，应采用哪种存储结构？为什么？2 假设以数组Qm存放循环队列中的元素, 同时以rear和length分别指示循环队列中的队尾位置和队列中所含元素的个数。试给出该循环队列的队空条件和队满条件。3 分析以下部分代码的时间复杂度，用大O表示法。 int i=1; while(i=n) i=i*9;4、设二叉树bt的存储结构如下： 12 3 4 56 7 8 9 10left00 2 3 7 5 8 0 10 1data j h f d b a c e g iright 0 0 0 9 4 0 0 0 0 0其中bt为树根结点指针，left、right分别为结点的左、右孩子指针域，data为结点的数据域。请完成下列各题：（1） 画出二叉树bt的逻辑结构；（2） 写出按先序、中序和后序遍历二叉树bt所得到的结点序列；（3） 画出二叉树bt的后线索化树。5、有一份电文中共使用五个字符：a、b、c、d、e，它们的出现频率依次为0.13、0.37、0.25、0.16、0.09，试画出对应的Huffman树（请按左子树根结点的权小于等于右子树根结点的权的次序构造），求出每个字符的Huffman编码。 四、算法设计题每题10分，共40分1 试编