混合班“数据结构”试卷

《混合班“数据结构”试卷》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2000年混合班“数据结构”试卷一、选择及填空题（除非特别注明，一般每小题2分，共30分）1、下列说法哪个正确：A）堆栈是在两端操作、先进后出的线性表B）堆栈是在一端操作、先进先出的线性表C）队列是在一端操作、先进先出的线性表D）队列是在两端操作、先进先出的线性表2已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历的结果为：A）CBEFDAB）FEDCBAC）CBEDFAD）不定3、对哈希(HASH)函数H(k)=kMODm,一般来说,m应取A)素数B)很大的数C)偶数D)奇数4_____是HASH查找的冲突处理方法:A）求余法B)平方取中法

2、C)二分法D)开放地址法5、下列哪种排序算法（均在内存中进行）要求内存量最大:A）选择排序B）插入排序C）冒泡排序D）归并排序6设有序列12、42、37、19，当使用直接插入排序从小到大排序时，其比较次数为：A）3B）4C）5D）67下列哪种排序算法数据交换的次数最多:A）选择排序B）插入排序C）冒泡排序D）归并排序8、可用类似下列哪些算法判别一有向图是否存在回路________:宽度优先遍历算法、深度优先遍历算法、最小生成树算法、求关键路径算法、求最短路径的Dijkstra算法、Topsort算法。9、（3分）若要维护一个数的集合，要求：1）能往该集合中插入任意一个数，且

3、2）能随时从该集合中删除最小及最大的数，你认为采用的最佳数据结构是：_______________10、（3分）请列出主要的算法设计方法____________________11、判别下列序列是否是最大堆，若不是，按书中的算法调整（8分）。序号原始序列是否为最大堆（Y/N）调整后的数的序列1（100，66，48，73，35，39，42，57，86，21）2（103，97，56，38，66，23，42，12，30，53，6，20）3（1，2，3，4，5，6，7，8，9，10）一、下列二叉树是某一森林的表示，请画出对应森林（8分）：二、画出下列无向图的相应邻接表(adjace

4、ncylists)表示法（邻接顺序按节点数字从小到大），并计算每一节点的dfn（从0开始）和low值，指出哪些节点是关节点（ArticulationPoints）（12分）三、对以下关键字序列构造地址空间为0~16的哈希（HASH）表，选取哈希函数H(k)=ëk/2û，k为关键字第一个字母在字母表中的序号，地址冲突处理策略为链地址法（直接插入在相应链表的头上）。请画出当关键字序列为（Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec）时的哈希表,并求等概率情况下查找成功与不成功的平均查找长度(10分).四、Deap是将最小堆作为左

5、子树、最大堆作为右子树的堆。在Deap中要求最小堆中任何元素i的值均小于最大堆中对应元素j（按书中定义）的值。（1）请写出i和j间的函数关系；（2）请画出将下列Deap中的最小元素删除后Deap的结构。（10分）五、下面程序是循环归并排序的程序框架(共18分)：voidmerge_pass(elementlist[],elementsorted[],intn,intlength){inti,j;for(i+0;i<=n-2*length;i+=2*length)merge(list,sorted,i,____①____;i+2-1);if(i+length

6、list,sorted,i,i+length-1,n-1);elsefor(j=i;j

7、,intm,intn)将两个已排序好的序列：list[i]...list[m]与list[m+1]...list[n]归并，并将结果放在sorted[i]...sorted[n]中。(1)请将上述程序中缺少的部分补上(2)对于待排序序列（100，66，48，73，35，39，42，57，86，21），请分别针对循环归并和递归归并画出相应归并过程中的子序列的划分/合并结构。(3)请写出完整的voidmerge(elementlist[],elementsorted[],inti,intm,intn)函数;六、请写出函