安徽大学数据结构试卷2010a

《安徽大学数据结构试卷2010a》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、院/系年级专业姓名学号答题勿超装订线------------------------------装---------------------------------------------订----------------------------------------线----------------------------------------安徽大学2009—2010学年第2学期《数据结构》考试试卷（A卷）（闭卷时间120分钟）题号一二三四五六七总分得分阅卷人得分一、填空题（每空1分，共15分）1、在线性结构中，第一个结点前驱结点，其余每个结点有且只有

2、个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。2、下面程序段的时间复杂度是。for(i=0;i

3、点的度要么是0，要么是2。这棵二叉树中度为2的结点有___________________个。8、在堆排序和快速排序中，若原始记录接近正序或反序，则选用____。9、若采用邻接表的存储结构，则图的广度优先搜索类似于二叉树的________遍历。得分二、单向选择题（每小题1.5分，共15分）1、n个顶点的强连通图中至少含有()。A、n—l条有向边B、n条有向边C、n(n—1)／2条有向边D、n(n一1)条有向边2、在一个不带头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，执行()。A、HL＝p;p一>next＝HL;B、p一>next＝HL；HL＝p

4、;C、p一>next＝HL;p＝HL;D、p一>next＝HL一>next;HL一>next＝p;第6页共6页3、采用线性链表表示一个向量时，要求占用的存储空间地址（）。A:必须是连续的B部分地址必须是连续的C:一定是不连续的D:可连续可不连续4、如果想在4092个数据中只需要选择其中最小的5个，采用（）方法最好。A:起泡排序B:堆排序C:锦标赛排序D:快速排序5、在循环队列中用数组A[0..m-1]存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（）。A:(front-rear+1)%mB:(rear-front+1)%mC

5、:(front-rear+m)%mD:(rear-front+m)%m6、数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是(     )。A:1175           B:1180           C:1205           D:12107、已知广义表LS＝((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是(    )A:head(tail(LS))                     B:tail(head(LS))C:he

6、ad(tail(head(tail(LS)))          D:head(tail(tail(head(LS))))8、某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问顺序是（）。A:bdgcefhaB:gdbecfhaC:bdgaechfD:gdbehfca9、在一个无向图中,所有顶点的度数之和等于所有边数的（）倍。A:1/2B:1C:2D:410、设串s1=’ABCDEFG’，s2=’PQRST’，函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i的字符

7、开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是（）。A：BCDEFB：BCDEFGC：BCPQRSTD：BCDEFEF得分三、应用题（每小题8分，共32分）1．一棵深度为h的满m叉树具有如下性质:第h层上的结点都是叶结点,其余各层上每个结点都有m棵非空子树。若按层次从上到下,每层从左到右的顺序从1开始对全部结点编号,试计算:(1)第k层结点数(1≤k≤h)。(2)整棵树结点数。(3)编号为i的结点的双亲结点的编号。(4)编号为i的结点的第j个孩子结点(若有)

8、的编号。答题勿超装订线--------