当前位置:主页>>考研试题>>正文:北京航天航空大学2002年硕士研究生入学考试程序设计与数据结构试卷一、简答题1.“数据结构”课程是计算机专业的基础课还是专业课,或者专业基础课?(2’)2.学习“数据结构”课程需要哪些课程作为它的基础(举例两门课程)?若没有这些知识,对学习“数据结构”课程可能会产生哪些影响?请举例说明(不超过100字)。(4’)3.“数据结构”课程将为那些课程学习奠定必要的基础?请举例说明哪些课程(举例两门课程)用到了“数据结构”课程的哪些知识(不超过100字)。(4’)二、三、A)必须连续C)不一定连续(5’)单项选择题(2’x15)B)部分地址必须连续D)连续与否无所谓B)link(q)link(p);link(p)q;D)link(p)q;link(q)p;请推导出结论:具有n0个叶结点的哈夫曼树(Huffman)的分支总数为2(n0-1)。1.线性链表中各链接点之间的地址__________。2.在非空线性链表中由p所指的链接点后面插入一个由q所致的链接点的过程是依次执行动作__________。A)link(q)p;link(p)q;C)link(q)link(p);pq;3.在非空双向循环链表中由q所指的那个链接点前插入一个p指的链接点的动作对应的语句依次为rlink(p)q,llink(p)llink(q),llink(q)p,__________。(空白处为一条赋值语句)A)rlink(q)pC)rlink(llink(p))p__________。A)cA)iB)dB)n-iC)bC)n-i+1B)求子串D)eD)哪个元素无所谓C)串的模式匹配D)串的连接5.若某堆栈的输入序列为1,2,3,……,n,输出序列的第1个元素为n,则第i个输出元素为__________。6.求字符串T在字符串S中首次出现的位置的操作称为__________。A)求串的长度7.若一棵度为7的树有8个度为1的结点,有7个度为2的结点,有6个度为3的结点,有5个度为4的结点,有4个度为5的结点,有3个度为6的结点,有2个度为7的结点,该树一共有__________个叶结点。A)35A)498B)28B)499C)77C)500D)78D)5018.若一棵二叉树有1001个结点,且无度为1的结点,则叶结点的个数为__________。9.已知某完全二叉树采用顺序存储结构,结点数据信息的存放顺序依次为A、B、C、D、E、F、G、H,该完全二叉B)rlink(llink(q))pD)rlink(rlink(p))p4.在初始为空的堆栈中依次插入元素f,e,d,c,b,a以后,连续进行了三次删除操作,此时栈顶元素是树的后序遍历序列为__________。A)HDEBFGCAB)HEDBFGCAC)HDEBAFGCD)HDEFGBCA10.若某带权图为G=(V,E),其中V={v1,v2,v3,v4,v5,v6,v7,v8,v9,v10},E={(v1,v2)5,(v1,v3)6,(v2,v5)3,(v3,v5)6,(v3,v4)3,(v4,v5)3,(v4,v7)1,(v4,v8)4,(v5,v6)4,(v5,v7)2,(v6,v10)4,(v7,v9)5,(v8,v9)2,(v9,v10)2}(注:顶点偶对右下角的数据表示边上的权值),则G的关键路径的长度为__________。A)19B)20C)21D)22B)散列存储结构11.顺序查找法适合于存储结构为__________的线性表。A)顺序存储结构或链式存储结构C)索引存储结构__________。A)(n+1)/2B)n/2C)log2(n+1)-1D)log2(n+1)13.下述命题中,不成立的应是__________。A)m阶B树中的每一个分支结点的子树的个数都小于或等于mB)m阶B树中的每一个分支结点的子树的个数都大于或等于ém/2ùC)m阶B树中的任何一个结点的子树的高度都相等D)m阶B树中有k个子树的分支结点包含k-1个关键字14.已知散列范围为[0..9],散列函数(哈希函数)为H(key)=keyMOD9,处理冲突的方法为线性探测再散列法,依次插入关键字序列8,18,25,44,34,21,19,23后的哈希表为__________。0A)0B)0C)0D)1918121B)选择排序法21811813421932314421932144452521932145236343214523634772588452367258891867258894488944934D)压缩存储结构12.当n足够大时,在按值有序的顺序表中进行折半查找,当查找概率相等的情况下,其查找成功的平均查找长度是15.在下述的排序方法中,不属于内排序方法的是__________。A)插入排序法四、(15’)请设计一个事件复杂度为O(n),空间复杂度不超过O(2)的算法,该算法将数组A[0:n-1]中所有元素循环右移k个位置。五、(15’)已知某二叉树采用广义表形式作为输入,请写一非递归算法,建立该二叉树的二叉链表存储结构。设该链接点构造C)拓扑排序法D)归并排序法为,根结点地址为T。关于采用广义表形式表示二叉树的约定如下:llll表中的一个字母表示一个结点的数据信息;每个根结点作为由子树构成的表的构成的表的名字放在表的前面;每个结点的左子树与右子树之间用逗号分开;若只有右子树而无左子树,则逗号不能省略;整个广义表的末尾由一个特殊符号@作为表的结束标志。例如:(A(B(D),C(F(,E),G))@表示某一棵二叉树,该二叉树的根结点数据信息为A。其中,数据信息为F的结点只有右子树,而无左子树。六、(1’x10)在下面给出的C函数实现中的__________处填上适当的内容,使其完成正确的功能。函数说明:函数voidftoa(doublef,chars[])将浮点数f转换成相应的字符串,并存放在s中,该函数最多只能转换小数点后四位,如123.45将转换成“123.45”,-123.456789将转换成“-123.4567”。voidftoa(doublef,chars[]){inti,j,len,c,n;doublesign;if((sign=f)<0)f=-f;n=(int)f;i=0;do{s[i++]=n+__________;}while(__________);if(sign<0)__________;len=i;for(i=0,j=len-1;__________;__________){c=s;__________;s[j]=c;}f-=(int)f;s[len++]=__________;for(i=0;i<4;i++){f*=10;
北京航天航空大学2002年硕士研究生入学考试程序设计与数据结构试卷



