数据结构试题.doc

数据结构期末考试题一、单项选择：1. 一个存储结点存放一个（ ） （A） 数据项 （B） 数据元素 （C） 数据结构 （D） 数据类型2. 下列算法的时间复杂度是 ( )for （ i=0 ； in ； i+ ） for （ j=0 ； jn ； j+ ） cij=i+j （A） 0(1) （B） 0(n) （C） 0(log2n) （D） 0(n2) 3. 数据结构是一门研究非数值计算的程序设计问题中计算机的( )以及它们之间的关系和运算等的学科（A） 操作对象 （B） 计算方法 （C） 逻辑存储 （D） 数据映象4. 在数据结构中，从逻辑上可以把数据结构分成( )（A） 动态结构和静态结构 （B） 紧凑结构和非紧凑结构（C） 线性结构和非线性结构 （D） 内部结构和外部结构5. 算法分析的目的是( )（A） 找出数据结构的合理性 （B） 研究算法中的输入和输出的关系（C） 分析算法的效率以求改进 （D） 分析算法的易懂性和文档性6. 设有一顺序栈已经含有3个元素,如图3.1所示,元素a4正等待入栈.以下序列中不可能出现的出栈序列是( )（A） a3,a1,a4,a2 （B） a3,a2,a4,a1 （C） a3,a4,a2,a1 （D） a4,a3,a2,a17. 在栈顶一端可进行的全部操作是( )（A） 插入 （B） 删除 （C） 插入和删除 （D） 进栈8. 栈的特点是( )（A） 先进先出 （B） 后进先出 （C） 后进后出 （D） 不进不出9. 顺序栈是空栈的条件是 ( ）（A） top=0 （B） top=1 （C） top=-1 （D） top=m10. 元素A、B、C、D依次进顺序栈后，栈顶元素是 ( ）（A） A （B） B （C） C （D） D11. 对矩阵压缩存储的主要目的是 （ ） （A） 方便运算 （B） 节省存储空间 （C） 降低计算复杂度 （D）提高运算速度12. 如图8.7所示的4棵二叉树中,（ ）不是完全二叉树13. 如图8.8所示的4棵二叉树,（ ）是平衡二叉树14. 如图8.9所示二叉树的中序遍历序列是（ ）.（A） abcdgef （B） dfebagc （C） dbaefcg（D） defbagc15. 深度为6的二叉树最多有( )个结点（A） 64 （B） 63 （C） 32 （D） 31二、填空题1、在树形结构中,根结点只有_,其余每个结点有且只有_前驱结点;叶结点没有_结点,其余每个结点的后继结点可以有_.2、下列程序段的时间复杂度是_.for (i=1;i=n;i+)Ai,j=0;3、已知某二叉树的后序遍历序列dabec, 中序遍历序列是debac, 它的前序遍历序列是_.4、有一棵树如图8.12所示, 回答下面问题: (1). 这棵树的根结点是_;(2). 这棵树的叶子结点是_;(3). 结点k3的度是_;(4). 这棵树的度为_;(5). 这棵树的深度是_;(6). 结点k3的子女是_;(7). 结点k3的父结点是_;三、简答题：1、算法的五个特性分别是什么？2、请画出图10的邻接矩阵和邻接表。图103、请画出与下列二叉树对应的森林。 4、一个稀疏矩阵如图5.8所示,写出对应的行三元组四、综合题：1、设有一个输入数据的序列是 46, 25, 78, 62, 12, 80 , 试画出从空树起，逐个输入各个数据而生成的二叉搜索树。2、设给定一个权值集合W=(3，5，7，9，11)，要求根据给定的权值集合构造一棵哈夫曼树并计算哈夫曼树的带权路径长度WPL。 3、设完全二叉树的顺序存储结构中存储数据ABCDE，要求给出该二叉树的前序、中序和后序遍历序列。4、如下为二分查找的非递归算法，试将其填写完整。Int Binsch(ElemType A ,int n,KeyType K)int low=0;int high=n-1;while (low=high)int mid=_；if (K=Amid.key) return mid; /查找成功，返回元素的下标 else if (Kmid.key) _; /在左子表上继续查找 else _; /在右子表上继续查找return -1; /查找失败，返回-1答案一、单项选择题：1、B2、D3、C4、C5、C6、A7、C8、B9、C10、D11、B12、C13、B14、B15、B二、填空题：1、一个 一个 后继 任意个2、O(n)3、cedba4、(1)k1(2)k2、k5、k7、k4(3)2(4)3(5)4(6)k5、k6(7)k1三、简答题1、有穷性 确定性 可行性 输入 输出2、邻接矩阵： 邻接表如图11所示：图113、4、 row col value0 0 3 2 1 1 0 3 2 2