东华理工大学软件工程-数据结构-2012-2013试题.doc

《东华理工大学软件工程-数据结构-2012-2013试题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、填空题（20分，每题2分）1、线性表是一种典型的_________结构。2、在一个长度为n的顺序表中删除第i个元素，则需移动______个元素。3、稀疏矩阵的一般的压缩方法为_________。4、设二维数组intA[10][20]，设A[0][0]的元素的地址为100，如果按行序优先顺序存储，则A[8][10]元素的地址为_____，如果按列序优先顺序存储，则A[8][10]元素的地址为_____。5、快速排序算法在平均情况下的时间复杂度为________(用Q表示法)。6、二分查找算法在平均情况下的时间复杂度为_______(用Q表示法)。7、上图所示的二叉树中，叶结点数为__

2、_个，分支结点数为___个。8、上图所示的二叉树中，如果对其采用指针法存储（分支结点用一个数据域和两个指针域存储，叶结点采用一个数据域存储，设数据域所占空间大小为d，指针所占空间大小为p），则该二叉树的结构性开销所占比例为__________。9、上图所示的二叉树中，若将其转换成完全二叉树后，则中序遍历序列为___________________。（完全二叉树定义：从根结点起每层从左到右填充）10、图有两种常用表示方法，分别为____________和___________。二、选择题（20分，每题2分）1、()适合从一个结点出发，在线性表中随意访问它的后继结点而不能访问它的前趋结点。

3、(A)双向链表(B)单链表 (C)循环链表(D)顺序表2、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是()。A、Q(n)B、Q(1)C、Q(n^2)D、Q(log2n)3、栈和队列与一般的线性表的区别在于()。 A、数据元素的类型不同 B、逻辑结构不同 C、数据元素的个数不同 D、运算是否受限制4.一个栈的入栈序列是abcde，则栈的不可能的输出序列是()。A、edcbaB、decbaC、dceabD、abcde5、一个队列的入列序列是abcd，则队列的输出序列是()。A、dcbaB、abcdC、adcbD、cbda6、串是一种特殊的线性表，其特殊性体现在()

4、。A、可以顺序存储B、数据元素是一个字符C、可以链接存储D、数据元素可以是多个字符7、广义表是线性表的推广，它们之间的区别在于()。A、能否使用子表B、能否使用原子项C、表的长度D、是否能为空8、如果图的边数较少，则称这个图为()A、有向图B无向图C稀疏图D密集图9、已知一棵二叉树的前序和中序序列分别为ABDECFG和DBEAFCG，则该二叉树的后序序列为（）A、DEBFGCAB、DBECFGAC、DAEBGCFD、ABCDEFG10、设某二叉树为满二叉树，其分支结点数为7，则其叶结点数为()A、10B、9C、8D、7将下图示的树转换成二叉树（5分）三、设待排序文件的关键码为（8,5,

5、2,1,4,7,6,3），现用插入排序的方法对之进行排序（按关键码值递增顺序），请给出每一趟扫描后的结果（8分）。一、假设用于通信的电文由字符集{a,b,c,d,e,f,g,h}中的字母构成，这8个字母在电文中出现的概率分别为{0.01,0.02,0.20,0.09,0.32,0.15,0.10,0.11}(共10分，第一问6分，第二问4分)　(1)为这8个字母设计哈夫曼编码(注：在构造哈夫曼树时将概率值小的字符放在左子树上)。　(2)若用三位二进制数(0…7)对这8个字母进行等长编码，则哈夫曼编码的平均码长是等长编码的百分之几?它使电文总长平均压缩多少?八、已知某无向图及邻接表如下图

6、所示。（共10分；每题5分，其中前一问3分，后一问2分）(1)给出其相应的深度优先遍历结果（从A开始，用栈结构），并画出其深度优先生成树。(2)给出其相应的广度优先遍历结果（从A开始，用栈结构），并画出其广度优先生成树。九、程序设计题(12分，第一题5分，第二题7分)1、已知Q是一个非空队列，S是一个空栈。仅用队列和栈的ADT函数和少量工作变量编写一个算法，使得Q中的元素倒置。voidreverse(Queue&Q,Stack&S){}栈的ADT函数有：boolpush(constElem&item)//入栈操作，将元素item入栈，如果入栈成功，则函数返回为true，否则函数返回为f

7、alseboolpop(Elem&it)//出栈函数，将栈顶元素出栈并赋值给it，如果出栈成功，则函数返回为true，否则函数返回为falseboolisEmpty()//判断栈是否为空函数，如果栈为空，则函数返回为true，否则返回为false队列ADT的函数有：boolenqueue(constElem&it)//入队函数，将元素it入队，如果入队成功，函数返回为true，否则返回为falsebooldequeue(Elem&it)//出队