电脑桌面
添加小米粒文库到电脑桌面
安装后可以在桌面快捷访问

北航数据结构与程序设计真题-2013年北航991真题及答案VIP免费

北航数据结构与程序设计真题-2013年北航991真题及答案_第1页
1/10
北航数据结构与程序设计真题-2013年北航991真题及答案_第2页
2/10
北航数据结构与程序设计真题-2013年北航991真题及答案_第3页
3/10
2013年“数据结构与C程序设计”(代码991)试题一、单项选择题(本题共20分,每小题各2分)1.对于长度为n的线性表,建立其对应的单链表的时间复杂度为()。A.O(1);B.O(log2n);.O(n);D.O(n2)。2.一般情况下,在一个双向链表中插入一个新的链结点,()。A.需要修改4个指针域内的指针;B.需要修改3个指针域内的指针;C.需要修改2个指针域内的指针;D.只需要修改1个指针域内的指针。3.假设用单个字母表示中缀表达式中的一个运算数(或称运算对象),并利用堆栈产生中缀表达式对应的后缀表达式。对于中缀表达式A+B*(C/D-E),当从左至右扫描到运算数E时,堆栈中的运算符依次是()。(注:不包含表达式的分界符)A.+*/-;B.+*(/-;C.+*-;.+*(-。4.若某二叉排序树的前序遍历序列为50,20,40,30,80,60,70,则后序遍历序列为()。A.30,40,20,50,70,60,80;B.30,40,20,70,60,80,50;C.70,60,80,50,30,40,20;D.70,60,80,30,40,20,50。5.分别以6,3,8,12,5,7对应叶结点的权值构造的哈夫曼(Huffman)树的深度为()。A.6;B.5;C.4;D.3。6.下列关于图的叙述中,错误的是()。A.根据图的定义,图中至少有一个顶点;B.根据图的定义,图中至少有一个顶点和一条边(弧);C.具有n个顶点的无向图最多有n(n-1)/2条边;D.具有n个顶点的有向图最多有n(n-1)条边(弧)。7.若在有向图G的拓扑序列中,顶点vi在顶点vj之前,则下列4种情形中不可能出现的是()。A.G中有弧;B.G中没有弧;C.G中有一条从顶点vi到顶点vj的路径;D.G中有一条从顶点vj到顶点vi的路径。8.下列关于查找操作的叙述中,错误的是()。A.在顺序表中查找元素可以采用顺序查找法,也可以采用折半查找法;B.在链表中查找结点只能采用顺序查找法,不能采用折半查找法;C.一般情况下,顺序查找法不如折半查找法的时间效率高;D.折半查找的过程可以用一棵称之为“判定树”的二叉树来描述。9.在一棵m阶B-树中,除根结点之外的任何分支结点包含关键字的个数至少是()。A.m/2-1;B.m/2;C.m/2-1;D.m/2。10.若对序列(49,38,65,97,76,13,27,49’)进行快速排序,则第一趟排序结束(即确定了第1个分界元素的最终位置)时,序列的状态是()。A.(13,27,49’,38,49,76,97,65);B.(13,38,27,49’,49,76,97,65);C.(13,38,49’,27,49,97,76,65);D.(13,38,49’,27,49,76,97,65)。二、填空题(本题共20分,每小题各2分)1.非空线性表在采()存储结构的情况下,删除表的一个数据元素平均需要移动表中近一半元素的位置。2.将一个长度为n的单链表链接到一个长度为m的单链表后面,该算法的时间复杂度用大O符号表示为()。3.若完全二叉树的叶结点的数目为k,且最下面一层的结点数大于1,则该完全二叉树的深度为()。4.若深度为8的完全二叉树的第7层有10个叶结点,则该二叉树的结点总数为()。5.在具有n个顶点的有向图中,每个顶点的度最大可以达到()。6.若对有向图进行拓扑排序,则能够得到拓扑序列的条件是()。7.已知长度为10的顺序表中数据元素按值从小到大排列。若在该表中进行折半查找,则平均查找长度(ASL)是()。8.若在一棵m阶B-树的某个结点中插入一个新的关键字值而引起结点产生分裂,则该结点中原有的关键字值的数目是()。9.有一种排序方法可能会出现这种情况:最后一趟排序开始之前,序列中所有的元素都不在其最终应该在的位置上,这种排序方法是()。10.若按照泡排序法的思想将序列(2,12,16,5,10)中元素按值从小到大进行排序,整个排序过程中所进行的元素之间的比较次数为()。三、综合题(本题共20分,每小题各5分)1.一般情况下,当一个算法中需要建立多个堆栈时可以选用下列三种处理方案之一。问:这三种方案之间相比较各有什么优点和缺点?(1)多个堆栈共享一个连续的存储空间;(2)分别建立多个采用顺序存储结构的堆栈;(3)分别建立多个采用链式存储结构的堆栈。2.已知二叉树采用二叉链表存储结构,根结点指针为T,链结点类型定义为:typedefstructnode{chardata;/*数据域*/structnode*lchild,*rchild;/*指向左、右子树的指针域*/}*BTREE;下面的算法...

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。
3、如文档内容存在违规,或者侵犯商业秘密、侵犯著作权等,请点击“违规举报”。

碎片内容

北航数据结构与程序设计真题-2013年北航991真题及答案

确认删除?
VIP
微信客服
  • 扫码咨询
会员Q群
  • 会员专属群点击这里加入QQ群
客服邮箱
回到顶部