哈工大数据结构期末试题2005春季学期试题含参.doc

《哈工大数据结构期末试题2005春季学期试题含参.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、时间复杂度为___________。5.表达式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)，则根据这些初始关键字序列建成的初始堆为_________

3、_______________。9.磁盘文件的归并技术有______________、____________、__________。10.设有向图G中有向边的集合E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，则该图的一种拓扑序列为____________________。11.设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行________趟的分配和回收才能使得初始关键字序列变成有序序列。主管领导签字12.利用Dijkstra算法求从有向

4、图顶点v1到其他各顶点的最短路径要求边上权值_________。二、选择题（每题1分，共15分）1．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用___________存储方式最节省时间。A.顺序表 B.双链表 C. 单循环链表D.带头结点的双循环链表02．在一个具有n个单元的顺序栈中，假定以地址低端（即下标为0的单元）作为栈底，以top作为栈顶指针，当出栈时，top的变化为______。A.不变B.top=0;C.top=top-1;D.top=top+1;3．设一组

5、初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为_________。A、10，15，14，18，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．用有向无环图描述表

6、达式(A+B)*((A+B)/A)，至少需要顶点的数目为_________。A.5 B.6 C.8 D.96.对线性表进行二分查找时，要求线性表必须___________。A、以顺序方式存储B、以链接方式存储C、以顺序方式存储，且数据元素有序D、以链接方式存储，且数据方式有序7.设散列表表长m=14，散列函数H(k)=kmod11。表中已有15、38、61、84四个元素，如果用线性探侧法处理冲突，则元素49的存储地址是_________。A.8B.3C.5D.98.若需在O(nlog2n)的时间内完成对

7、数组的排序，且要求排序是稳定的，则可选择的排序方法是_________。A.快速排序 B.堆排序 C.归并排序D.插入排序9. 下面关于m阶B树的说法正确的是__________。①每个结点至少有两株非空子树②树中每个结点至多有m-1个关键字③所有的叶子都在同一层上④当插入一个记录引起B树分裂后，树增高一层A.①②③ B.②③ C.②③④D.①③10.已知一个有序表为（12，18，24，35，47，50，62，83，90，115，134），当折半查找值为90的元素时，经过_______次比较后查找成功。

8、A.2B.3C.4D.511.能有效缩短关键路径长度的方法是_________。　A．缩短任意一个活动的持续时间　B．缩短关键路径上任意一个关键活动的持续时间　C．缩短多条关键路径上共有的任意一个关键活动的持续时间　　D．缩短所有关键路径上共有的任意一个关键活动的持续时间12.在采用线性探测法处理冲突所构成的闭散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置的关键字值________。A.一定都是同义词B.一定都不