哈工大2010年春季学期

《哈工大2010年春季学期》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、班号学号姓名哈工大2010年春季学期数据结构与算法A试卷题号一二三四总分分值1515202070得分一、填空题（每空1分，共15分）注意行为规范遵守考场纪律1.在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是____________。2．某二叉树的前序遍历序列是ABCDEFG，中序遍历序列是CBDAFGE，则其后序遍历序列是_______________。3．在有n个叶子的哈夫曼树中，分支结点总数为___________个。4．对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为___________。5.表

2、达式a*(b+c)-d的后缀表达式是___________。6.假定一棵二叉树的结点数为18，则它的最小深度为_______，最大深度为______。7.设有一个n阶的下三角矩阵A，如果按照行的顺序将下三角矩阵中的元素（包括对角线上元素）存放在n(n+1)个连续的存储单元中，则A[i][j]与A[0][0]之间有_______个数据元素。8.设一组初始记录关键字序列为(20，18，22，16，30，19)，则根据这些初始关键字序列建成的初始堆为________________________。9.磁盘文件的归并技术有______________

3、、____________、__________。10.设有向图G中有向边的集合E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，则该图的一种拓扑序列为____________________。11.设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行________趟的分配和回收才能使得初始关键字序列变成有序序列。主管领导签字12.利用Dijkstra算法求从有向图顶点v1到其他各顶点的最短路径要求边上权值_________。二、选择题（每题1分，共15分）1．若某线性表最常用的操作是存

4、取任一指定序号的元素和在最后进行插入和删除运算，则利用___________存储方式最节省时间。A.顺序表 B.双链表 C. 单循环链表D.带头结点的双循环链表02．在一个具有n个单元的顺序栈中，假定以地址低端（即下标为0的单元）作为栈底，以top作为栈顶指针，当出栈时，top的变化为______。A.不变B.top=0;C.top=top-1;D.top=top+1;3．设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为_________。A、10，15，14，18，

5、21，36，40，20B、10，15，14，18，20，40，36，21C、10，15，14，20，18，40，36，2lD、15，10，14，18，20，36，40，214．任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序________。A.肯定不发生改变B.肯定发生改变C.不能确定D.有时发生变化5．用有向无环图描述表达式(A+B)*((A+B)/A)，至少需要顶点的数目为_________。A.5 B.6 C.8 D.96.对线性表进行二分查找时，要求线性表必须___________。A、以顺序方式存储B、以链接方式存储C

6、、以顺序方式存储，且数据元素有序D、以链接方式存储，且数据方式有序7.设散列表表长m=14，散列函数H(k)=kmod11。表中已有15、38、61、84四个元素，如果用线性探侧法处理冲突，则元素49的存储地址是_________。A.8B.3C.5D.98.若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是_________。A.快速排序 B.堆排序 C.归并排序D.插入排序9. 下面关于m阶B树的说法正确的是__________。①每个结点至少有两株非空子树②树中每个结点至多有m-1个关键字③所有的叶

7、子都在同一层上④当插入一个记录引起B树分裂后，树增高一层A.①②③ B.②③ C.②③④D.①③10.已知一个有序表为（12，18，24，35，47，50，62，83，90，115，134），当折半查找值为90的元素时，经过_______次比较后查找成功。A.2B.3C.4D.511.能有效缩短关键路径长度的方法是_________。　A．缩短任意一个活动的持续时间　B．缩短关键路径上任意一个关键活动的持续时间　C．缩短多条关键路径上共有的任意一个关键活动的持续时间　　D．缩短所有关键路径上共有的任意一个关键活动的持续时间12.在采用线性探测法

8、处理冲突所构成的闭散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置的关键字值________。A.一定都是同义词B.一定都不