一、填空题（20分，共10题）
设使用某算法对n个元素进行处理，所需的时间是T(n)=100nlog2n+200n+2000，则该算法的渐进时间复杂度为O(_______)。
一个算法的时间复杂度为(3n2+2nlog2n+4n-7)/(10n)，则f = O(_______)。
已知顺序表中每个元素占2个存储单元，第一个元素a0在计算机内存中的首地址是100，则表中元素a5在内存中的存储地址为_______。
设顺序表的长度为9，并设从表中删除元素的概率相等。则在平均情况下，从表中删除一个元素需移动的元素个数是________。
在初始为空的堆栈中依次插入元素f，e，d，c，b，a以后，连续进行了3次删除操作，此时栈顶元素是_________。
设有一个空栈，栈顶指针为1000H（十六进制，下同，且设每个入栈元素需要1个单位存储空间），现有输入序列为1，2，3，4，5，经过PUSH，PUSH，POP，PUSH，POP，PUSH，POP，PUSH后，栈顶指针是________H。 一个n×n的对称矩阵，压缩后的存储容量为______。
已知一棵二叉树的后序遍历结果是K B C D F E N，则该二叉树的根结点为 。
已知一棵二叉树有n个结点，则其二叉链表结构中共有 个空指针域。 在字符串S=\中，以t为首的子串有________个。
二叉搜索树左子树不空，则左子树上所有结点的关键字值均 （小于、大于、等于）根结点的关键字值。
一个无向图的生成树是一个极小连通子图，它包括图中n个顶点，但只有足以构成一棵树的 条边。
已知哈夫曼树中有5个度为2的结点，则该二叉树共有 个结点。
对序列（9，9，7）使用某种排序算法，得到的结果为（7，9，9），则该算法是________（稳定、不稳定）的排序算法。
已知有向图G，V（G）={0，1，2，3，4}，E（G）={<0,1>, <1,2>, <2,0>, <2,4>, <3,0>, <3,2>, <3,4>,<4,0>}，则顶点0的入度为_________。
在长度为n (n>1)的顺序表上进行顺序查找，查找不成功的平均查找长度为________。 图 1所示的AOE网络的关键路径长度为 。
a0=1v1v2v3a4=4a5=5v0a1=2v4a7=1v5 a2=3a6=6图 1
二、选择题（20分，共10题）
顺序查找法适合于存储结构为________的线性表。 A. 散列压缩 B. 顺序存储或链式存储 C. 压缩存储 D. 索引存储
将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为________。 A. O(1) B. O(n) C. O(m) D. O(m+n)
采用二分法在线性表上查找的条件是线性表有序且________。 A. 使用链式存储结构 C. 使用索引结构
B. 使用顺序存储结构 D. 使用散列结构
图 2表示的堆是 。
9270624675
图 2
A. 最小堆 A. 8
B. 最大堆
C. 不是堆
D. 既是最大堆，也是最小堆
后缀表达式6 4 2 - / 3 2 * +的结果为 。
B. 9
C. 7 D. 10
已知一棵由关键字集合{18，43，27，77，44，36，39}所构造的二叉搜索树，对该树进行中序遍历得到的结点序列为________。 A．树形未定，无法确定
B．18，43，27，77，44，36，39 C．18，27，36，39，43，44，77 D．77，44，43，39，36，27，18
分别以下列序列构造二叉搜索树，与众不同的是________。 A. 100,80,60,85,110,120,150
B. 100,80,60,85,120,110,150
C. 100,80,85,60,120,110,150 D. 100,80,60,85,120,150,110 一组关键字（87,73,25,55,90,28,31,17,101,22,3,62），若散列函数为h(key)=key mod 11，在链地址法处理后的同一链表中的是________。 A. 81, 90 B. 31, 101 C. 3, 78 D. 62, 73 Huffman树中，不存在度为 的结点。 A．1
B. 2
C. 0
D. 0和2
均匀的散列函数应当使关键字集合中的元素，经散列函数映射到散列表中任何位置的概率________。 A．相等
B．最小 C．最大 D．一定
对半搜索是一种二分搜索。设当前搜索的子表为（alow, alow+1, …, ahigh），假设对半搜索
的划分点为am，则m = 。
A. (low - high)/2 B. (low + high)/2 C. (low -high)/3 D. (low + high)/3
图的遍历算法BFS中用到辅助队列，每个顶点最多进队_______次。 A. 1 B. 2 C. 3 D. 不确定 二叉搜索树中， 是关键字值最小的结点。 A. 中序遍历序列中的第一个结点 B. 中序遍历序列中的最后一个结点 C. 后序遍历序列中的最后一个结点 D. 按层遍历序列中的最后一个结点 对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小为_______。
22
A．(n-1) B. n C. n-1 D. n 对以下关键子序列用快速排序进行排序，选项_______所示的情况排序速度最慢？ A. {19, 23, 3, 15, 7, 21, 28}
B. {23, 21, 28, 15, 19, 3, 7} C. {19, 7, 15, 28, 23, 21, 3} D. {3, 7, 15, 19, 21, 23, 28}
在数据结构中，从逻辑上可以把数据结构分为________。 A. 线性结构和非线性结构 B. 紧凑结构和非紧凑结构 C. 动态结构和静态结构 D. 内部结构和外部结构
链表不具有的特点是_________。
A. 可随机访问任一个元素 B. 插入和删除时不需要移动元素 C. 不必事先估计存储空间 D. 所需空间与线性表的长度成正比 设有一个栈，元素的进栈次序为A，B，C，D，E，下列________是不可能的出栈序列。
A．A，B，C，D，E
B. B，C，D，E，A
C. E，A，B，C，D D. E，D，C，B，A 下面关于串的的叙述中，哪一个是不正确的？ A. 串是字符的有限序列 B. 空串是空格构成的串
C. 模式匹配是串的一种重要运算
D. 串既可以采用顺序存储，也可以采用链式存储
假定一棵二叉树的结点数为50，则它的最小高度为 。 A. 4
B. 5 C. 6 D. 7
三、简答题（50分，共5题）
以A，Z，B，Y，C，X序列为输入，从空树开始构造AVL搜索树。 将图 3中的二叉树转换为森林。
ABCKHJ图 3
DEFG
设有散列表ht[11]，散列函数为h(key)=key % 11，采用线性探测法处理冲突，试用关键字序列70，25，80，35，60，45，50，55建立散列表。
设有一组关键字{9，1，23，14，55，20，84，27}，采用哈希函数h(key)=key mod 7，表长为10，用线性探测法解决冲突。要求：对该关键字序列构造哈希表。 已知关键字序列为（20，30，50，60，70，80），依照此顺序建立一棵3阶B-树，试着给出B-树的最终结果。若删除了50和60，B-树的形态如何？
使用普里姆（Prim）算法以0为源点，画出图 4所示的无向图的最小代价生成树。并计算该生成树的代价。
0103413712265
图 4
51设某项工程由下图所示的工序组成。若各工序以流水方式进行（即串行进行）。 ① 画出给工程的AOV网络；
② 给出该工程的全部合理的工程流程。
元素序列(61,87,12,03,08,70,97,75,53,26)按冒泡算法排序，给出第一趟排序结果。同时请回答冒泡排序的稳定性。
设S={A,B,C,D,E,F}，W={2,3,5,7,9,12}，对字符集合进行哈夫曼编码，W为各字符的频率。
