2014-201学年一学期数据结构期末考试试卷1.doc

长沙理工大学计算机与通信工程学院 班级:___________学号:___________姓名:___________得分:___________ 题号 一 二 三 四 五 六 七 八 九 十 成绩 复核 得分 ? ? ? ? ? ? ? ? ? ? ? ? 阅卷 ? ? ? ? ? ? ? ? ? ? ? 题目部分，(卷面共有32题,100分,各大题标有题量和总分) 一、应用题(2小题,共16分) 1．一个线性表为B=（12，23，45，57，20，03，78，31，15，36），设散列表为HT[0..12]，散列函数为H（key）= key % 13并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。 2．分析下面各程序段的时间复杂度 （1） s1(int n) { int p=1,s=0; ? for (i=1;i=n;i++) ???? { p*=i;s+=p; } return(s); } （2） s2(int n) x=0; y=0; For (k=1;k=n;k++) x++; For (i=1;i=n;i++) For (j=1;j=n;j++) y++; ? ?二、判断正误(7小题,共14分) 1．线性链表的删除算法简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。（? ） ?2．顺序队和循环队关于队满和队空的判断条件是一样的。（? ） ?3．在线索二叉树中，任一结点均有指向其前趋和后继的线索。（? ） 4．设一棵树T可以转化成二叉树BT，则二叉树BT中一定没有右子树。（? ） 5．散列技术的查找效率主要取决于散列函数和处理冲突的方法。（? ） 6．数据的逻辑结构和数据的存储结构是相同的。（? ） ?7．??逻辑结构与数据元素本身的内容和形式无关。（? ） 三、单项选择题(10小题,共20分) 1．单链表的存储密度（??? ）。 ?? A． 大于1??? ? ??????B． 等于1?? ?????C．小于1?? ?????? ??D． 不能确定 ?2．两个指针P和Q，分别指向单链表的两个元素，P所指元素是Q所指元素前驱的条件是（??? ）。 A．P-next==Q-next?? B．P-next== Q???? C．Q-next== P?????? D．P== Q 3．字符串的长度是指（?? ）。 ?? A ?串中不同字符的个数????????????????? B ?串中不同字母的个数 ?? C ?串中所含字符的个数????????????????? D ?串中不同数字的个数 ? 4．线索二叉树中某结点R没有左孩子的充要条件是（ 　　）。A R.lchild=NULL???? ?B R.ltag=0????? ?C R.ltag=1????? ?D R.rchild=NULL 5．设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（? ）。 ???? A ?20????????????????????? B ?256???????????????? C ?512???????????????? D ?1024 6．下面关于工程计划的AOE网的叙述中，不正确的是（ ） ?A 关键活动不按期完成就会影响整个工程的完成时间B 任何一个关键活动提前完成，那么整个工程将会提前完成C 所有的关键活动都提前完成，那么整个工程将会提前完成D 某些关键活动若提前完成，那么整个工程将会提前完 7．设有向无环图G中的有向边集合E={1，2，2，3，3，4，1，4}，则下列属于该有向图G的一种拓扑排序序列的是（? ）。 ???? A ?1，2，3，4????????? B ?2，3，4，1???????????? ?? C ?1，4，2，3????????? D ?1，2，4，3 ? 8．设有一组初始记录关键字序列为(34，76，45，18，26，54，92)，则由这组记录关键字生成的二叉排序树的深度为（? ）。 ???? A ?4??????????????????????? B ?5???????????????????? C ?6??????????????????? D ?7 9．一趟排序结束后不一定能够选出一个元素放在其最终位置上的是（? ）。 ?????? A ?堆排序???????????? B ?冒泡排序???????? C ?快速排序?????????? D ?希尔排序 ? 10．算法分析的两个主要方面是（??? ）。 A.? 空间复杂性和时间复杂性?????? ???????? ?B.? 正确性和简明性 C.? 可读性和文档性?????????? ???????????? ?D.? 数据复杂性和程序复杂性 ? 四、算法设计题(3