98计算机《数据结构》试卷（a）-.doc

98级计算机《数据结构》试卷（A） 学号________ 姓名__________ 选择题（每小题2分，共20分） 在二维数组A中引用A[i,j]的时间_________ 与的i、j大小有关 与的i、j大小无关 与的i大小有关，与的j大小无关 与的i大小无关，与的j大小有关 设有一个文件有200个记录，按分块查找法查找记录，如分成10块，每块20个记录，用二分查找法查索引表，用顺序查找法查块内记录，则平均查找长度为_______________ A、8.4 B、10.5 C、13.4 D、16 快速排序在最坏情况下的时间复杂性为________________ A、O（nlog2n） 堆排序在最坏情况下的时间复杂性为________________ A n 个权构成一棵Huffman树，其节点总数为________________ A、2n-1 B、2n C、2n+1 D、不确定 下列排序算法中，________需要的辅助存储空间最大。 A、快速排序 B、插入排序 C、希尔排序 D、基数排序 下列排序算法中，________是稳定的。 A、插入、希尔 B、冒泡、快速 C、选择、堆排序 D、基数、归并 下列算法中，________算法用来求图中每对顶点之间的最短路径。 A、Dijkstra B、Floyed C、Prim D、Kruskal 若前序遍历二叉树的结果为序列A、B、C，则有_________棵不同的二叉树可以得到这一结果。 A、3 B、4 C、5 D、6 由N个顶点组成的有向图，最多可以有_________条边。 A、N*N B、N（N+1） C、N（N-1） D、N N-1 /2 填空题（每空2分，共20分） 在含有n个结点的平衡二叉排序树中查找关键字，其时间复杂性为____________________ 对表 45，30，55，21，94，66，90，82 用堆排序方法进行排序，首先建立一个初始堆，这个堆是__________________________________________________ 设散列表为T[0..100]，初始状态为空，用线性探测法解决块冲突，向散列表中插入一个关键字，在插入成功的情况下，至多探测_________次。 设一棵Huffman树有6个叶结点，权值分别为3、4、7、14、15、20，则根节点的权值是_______ a+b *c+ e*f-h / q+r +3的后缀表达式为___________________________________ 已知数组R中的前n个元素已组成一个堆，下列程序将R的前n+1个元素变成堆。 Procedure insertH n:position ; var R : LIST Var i, j : position; extra : integer; done : boolean; begin i : n + 1; extra : R[i]; done : ____________________________; while i 1 and not done do begin j : _______________________________; if extra R[j] then begin R[i] : R[j]; i : ______________________________ end; else done : ________________________________ end; ______________ : extra end; 给定关键字序列 19，14，23，01，68，20，84，27，55，11，10，79 ，散列函数H key key MOD 13，用拉链法解决冲突，试构造Hash表，并求其平均查找长度。（10分） 给定N个整数，试编写一个算法将其分成两个部分，其中一部分为负数，另一部分为正数。要求算法的时间复杂性为O（n）。（12分） 已知图G如图所示 写出图G的邻接表； 画出从顶点1出发的深度优先生成树和广度优先生成树； 写出图G的拓扑排序列； 求出关键路径。（12分） 设计一个算法，按层次顺序输出二叉树中的所有节点，要求同一层上的节点从左到右输出。（12分） 设计一个算法求广义表的深度。（14分）