哈尔滨工业大学数据结构与算法历年考题汇总

[期末]2005数据结构与算法试卷试卷类型:期末试卷年份:05授课教师:廖明宏有无答案:无答案哈工大2005年春季学期数据结构与算法试卷一．填空题（每空1分，共10分）1．假定对线性表(38,25,74,52,48)进行散列存储，采用H(K)=K%7作为散列函数，若分别采用线性探查法和链接法处理冲突，则对各自散列表进行查找的平均查找长度分别为_______和________。2．假定一组记录的排序码为(46,79,56,38,40,80)，对其进行归并排序的过程中，第二趟归并后的结果为________________。3．在堆排序的过程中，对任一分支结点进行调整运算的时间复杂度为________，整个堆排序过程的时间复杂度为________。4．有向图的邻接矩阵表示法中某一行非0元素的个数代表该顶点的，某一列非0元素的个数是该顶点的。5．对于下面的带权图G3，若从顶点v0出发，则按照普里姆（Prim）算法生成的最小生成树中，依次得到的各条边为______________。6．由带权为3，9，6，2，5的5个叶子结点构成一棵哈夫曼树，则带权路径长度为7．由三个结点构成的二叉树，共有种不同结构。二．选择题（每题1分，共10分）1．快速分类在的情况下不利于发挥其长处.A.待分类的数据量太大B.待分类的数据相同值过多C.待分类的数据已基本有序D.待分类的数据值差过大.2．两路归并排序中，归并的趟数是。A.O(n)B.O(log2n)C.O(nlog2n)D.O(n2)注意行为规范遵守考场纪律第1页，共6页3．对外部分类的K路平衡归并，采用败者树时，归并的效率与K。A.有关B.无关C.不能确定D.都不对4．对于一个索引顺序文件，索引表中的每个索引项对应主文件中的。A.一条记录B.多条记录C.所有记录D.三条以上记录5．.若线性表采用顺序存储结构，每个元素占用4个存储单元，第一个元素的存储地址为100，则第12个元素的存储地址时。A.112B.144C.148D.4126．若频繁地对线性表进行插入和删除操作，该线性表应该采用存储结构。A.散列B.顺序C.链式D.索引7．若长度为n的非空线性表采用顺序储存结构，删除表中第i个数据元素，需要移动表中个数据元素。A.n+iB.n-iC.n-i+1D.n-i-18．栈和队列的相同之处是。A.元素的进出满足先进后出B.元素的进出满足后进先出C.只允许在端点进行插入和删除操作D.无共同点9．在一棵高度为k的二叉树中，最多含有()个结点。A．2k-1B．2k-lC．2k-1D．k10．任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序()。A．发生改变B．不发生改变C．不能确定D．以上都不对三．判断题，正确的在括号内画∨，错误的在括号内画╳。（每小题1分，共10分）1．树的父链表示就是用数组表示树的存储结构。（）.2．任何二元树都唯一对应一个森林，反之亦然。.（）3．有向图的邻接矩阵一定不是对称的。（）4．AOE网中，只有一个入度为0的顶点（起始点），只有一个出度为0的顶点（结束点）。（）5．关键路径可能不只一条，但缩短某一关键路径一定能够缩短工期。（）6．顺序存储方式只能用于存储线性结构。()7．用循环链表作为存储结构的队列就是循环队列。()8．倒排文件的主要优点为便于节省空间（）。9．一组记录的关键字为（46,79,56,38,40,84）,则利用快速排序的方法，以第一个记录为基准元素得到的一次划分结果为40,38,46,56,79,84（）。10．算法分析的目的是分析算法的易读性（）。四．简答题1.简述如何用两个栈模拟一个队列的入队和出队操作.(6分)2.对于图G5所示的树：（7分）(1)写出先根遍历得到的结点序列；(2)写出按层遍历得到的结点序列；(3)画出转换后得到的二元树图G5五．算法设计1.设二元树采用左右链存储，写出后序遍历该二元树的非递归算法。(12分)2.设图中各边上的权值均相等,试以邻接表为存储结构,写出求源点Vi到Vj的最短路径算法。(15分)..哈工大数据结构与算法2009年试题2010年春A卷一、填空题（每空1分，共15分）1.在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是____________。2．某二叉树的前序遍历序列是ABCDEFG，中序遍历序列是CBDAFGE，则其后序遍历序列是_______________。3．在有n个叶子的哈夫曼树中，分支结点总数为___________个。4．对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为___________。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)，则根据这些初始关键字序列建成的初始堆为________________________。9.磁盘文件的归并技术有______________、____________、__________。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．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用___________存储方式最节省时间。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，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.5B.6C.8D.96.对线性表进行二分查找时，要求线性表必须___________。A、以顺序方式存储B、以链接方式存储C、以顺序方式存储，且数据元素有序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个关键字③所有的叶子都在同一层上④当插入一个记录引起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.在采用线性探测法处理冲突所构成的闭散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置的关键字值________。A.一定都是同义词B.一定都不是同义词C.不一定都是同义词D.都相同13.设哈夫曼编码的长度不超过4，若已对两个字符编码为1和01，则最多还可以对_______个字符编码。A．2B．3C．4D．514.已知图的邻接表如下所示，根据算法，则从顶点0出发深度优先遍历的结点序列是____________。A.0132B.0231C.0321D.012315.在具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是_________。A.O(1)B.O(n)C.O(n2)D.O(nlog2n)三、简答题：每题10分，共20分.1．一个按数组元素有序的一维数组一定是堆吗？请说明理由。2.设有一组初始记录关键字为(45，80，48，40，22，78)，可以构造出一棵二叉排序树，若不是平衡树则调整平衡，并给出其前序遍历该树的序列，并写出右旋转函数算法。四、算法设计：每题10分，共20分要求：⑴描述算法设计的基本思想⑵描述算法的详细实现步骤⑶根据设计思想和实现步骤，采用程序设计语言描述算法（使用C或C++或JAVA语言实），关键之处请给出简要注释。（栈、队列的存储结构、基本操作可以直接引用）1．对给定的序号j（1＜j＜n），要求在无序记录A[1]~A[n]中找到按关键码从小到大排在第j位上的记录，试利用快速排序的划分思想设计算法实现上述查找。2．设计算法，判断以邻接表存储的有向图中是否存在由顶点vi到顶点vj的路径（i≠j）。参考答案：一．填空：1.logi=logj2.CDBGFEA3.n-14.O(n2)5.abc+*d-6.5187.i(i+1)/2+j-18.1618192030229.多路归并、I/O并行处理初始归并段产生10.1,4,2,311.312.非负二、单选：1A2C3A4A5A6C7A8C9B10A11D12C13C14D15B三、简答：1.按数组元素有序的一维数组一定是堆。（4分）非升序数组一定是最小堆为例说明如下：假设非升序数组为K1,K2,…,Kn，则满足K1≤K2,≤…≤Kn，则一定满足：Ki≤K2i且Ki≤K2i+1，即满足最小堆的定义。同理可知，非降序数组一定是最大堆。因此，按数组元素有序的一维数组一定是堆。（6分）2.二叉平衡树为48，40，80，22，45，78（3分）前序：48，40，22，45，80，78（3分）右旋转函数：voidR_Rotate(BSTree&p){lc=p-lchild;p-lchild=lc-rchild;lc-rchild=p;p=lc;}四、算法1.1、本算法不要求将整个记录进行排序，而只进行查找第j个记录。(1)基本思想：改进划分算法，是一次划分将基准元素定位于k，如果k==j，则找到第j小的元素；否则，递归地在k的左边或右边进行划分，直到k==j为止。(2)算法详细步骤：略(3)算法如下：intSearch(intA[],intn,intj){s=1;t=nk=Partition(A,s,t);while(k！=j)if(kj)k=Partition(A,k+1，t);elsek=Partition(A,s，k-1);returnA[j];}intPartition(intA[],intlow,inthigh){i=low;j=high;pivot=A[l