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

温馨提示：端正考风，严肃考纪，诚信参加考试凡是代考、使用通讯工具作弊、二次作弊，一经发现开除学籍专用考试纸，请勿浪费专业班级学号姓名东华理工大学(南昌校区)2012—2013学年第一学期试卷数据结构课程(A)卷课程类别：必修题号一二三四五六七八九总分分数评卷人共4页第1页一、填空题（20分，每题2分）1、线性表是一种典型的_________结构。2、在一个长度为n的顺序表中删除第i个元素，则需移动______个元素。3、稀疏矩阵的一般的压缩方法为_________。4、设二维数组intA[10][20]，设A[0][0]的元素的地址为100，如果按行序优先顺序存储，则A[8][10]元素的地址为_____，如果按列序优先顺序存储，则A[8][10]元素的地址为_____。5、快速排序算法在平均情况下的时间复杂度为________(用表示法)。6、二分查找算法在平均情况下的时间复杂度为_______(用表示法)。7、上图所示的二叉树中，叶结点数为___个，分支结点数为___个。8、上图所示的二叉树中，如果对其采用指针法存储（分支结点用一个数据域和两个指针域存储，叶结点采用一个数据域存储，设数据域所占空间大小为d，指针所占空间大小为p），则该二叉树的结构性开销所占比例为__________。9、上图所示的二叉树中，若将其转换成完全二叉树后，则中序遍历序列为___________________。（完全二叉树定义：从根结点起每层从左到右填充）10、图有两种常用表示方法，分别为____________和___________。二、选择题（20分，每题2分）1、()适合从一个结点出发，在线性表中随意访问它的后继结点而不能访问它的前趋结点。(A)双向链表(B)单链表(C)循环链表(D)顺序表2、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是()。A、(n)B、(1)C、(n^2)D、(log2n)3、栈和队列与一般的线性表的区别在于()。A、数据元素的类型不同B、逻辑结构不同C、数据元素的个数不同D、运算是否受限制4.一个栈的入栈序列是abcde，则栈的不可能的输出序列是()。A、edcbaB、decbaC、dceabD、abcde5、一个队列的入列序列是abcd，则队列的输出序列是()。A、dcbaB、abcdC、adcbD、cbda6、串是一种特殊的线性表，其特殊性体现在()。A、可以顺序存储B、数据元素是一个字符C、可以链接存储D、数据元素可以是多个字符7、广义表是线性表的推广，它们之间的区别在于()。A、能否使用子表B、能否使用原子项C、表的长度专业班级学号姓名共4页专用考试稿纸请勿浪费第2页D、是否能为空8、如果图的边数较少，则称这个图为()A、有向图B无向图C稀疏图D密集图9、已知一棵二叉树的前序和中序序列分别为ABDECFG和DBEAFCG，则该二叉树的后序序列为（）A、DEBFGCAB、DBECFGAC、DAEBGCFD、ABCDEFG10、设某二叉树为满二叉树，其分支结点数为7，则其叶结点数为()A、10B、9C、8D、7将下图示的树转换成二叉树（5分）三、设待排序文件的关键码为（8,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个字母进行等长编码，则哈夫曼编码的平均码长是等长编码的百分之几?它使电文总长平均压缩多少?八、已知某无向图及邻接表如下图所示。（共10分；每题5分，其中前一问3分，后一问2分）(1)给出其相应的深度优先遍历结果（从A开始，用栈结构），并画出其深度优先生成树。(2)给出其相应的广度优先遍历结果（从A开始，用栈结构），并画出其广度优先生成树。专业班级学号姓名共4页专用考试稿纸请勿浪费第3页九、程序设计题(12分，第一题5分，第二题7分)1、已知Q是一个非空队列，S是一个空栈。仅用队列和栈的ADT函数和少量工作变量编写一个算法，使得Q中的元素倒置。voidreverse(Queue&Q,Stack&S){}栈的ADT函数有：boolpush(constElem&item)//入栈操作，将元素item入栈，如果入栈成功，则函数返回为true，否则函数返回为falseboolpop(Elem&it)//出栈函数，将栈顶元素出栈并赋值给it，如果出栈成功，则函数返回为true，否则函数返回为falseboolisEmpty()//判断栈是否为空函数，如果栈为空，则函数返回为true，否则返回为false队列ADT的函数有：boolenqueue(constElem&it)//入队函数，将元素it入队，如果入队成功，函数返回为true，否则返回为falsebooldequeue(Elem&it)//出队函数，将队首元素出队，如果出队成功，则函数返回为true，否则返回为falseboolisEmpty()//判断队列是否为空函数，如果队为空，则函数返回为true，否则返回为false2、已知链表结点定义为：templateclassElemclassLink{public:Elemelement;//ValueforthisnodeLink*next;//PointertonextnodeinlistLink(constElem&elemval,Link*nextval=NULL){element=elemval;next=nextval;}Link(Link*nextval=NULL){next=nextval;}}链表类定义为：templateclassElemclassLList{private:LinkElem*head;//PointertolistheaderLinkElem*tail;//PointertolastEleminlistLinkElem*fence;//Lastelementonleftsideintleftcnt;//Sizeofleftpartitionintrightcnt;//Sizeofrightpartitionvoidinit(){//Intializationroutinefence=tail=head=newLinkElem;leftcnt=rightcnt=0;};voidremoveall(){//Returnlinknodestofreestorewhile(head!=NULL){fence=head;head=head-next;deletefence;}}public:专业班级学号姓名共4页专用考试稿纸请勿浪费第4页LList(intsize=DefaultListSize){init();}~LList(){removeall();}//Destructorboolinsert(constElem&item);………………………..};其中insert函数为插入函数，它将元素item插入到fence位置后，如果插入成功，则函数返回true，否则返回为false，写出insert函数的实现。boolLListElem::insert(constElem&item){}