1、 1 1. 以下与数据的存储结构无关的术语是 （ c ） C、哈希表 2. 一个向量第一个元素的存储地址是 100，每个元素的长度为 2，则第 5 个元素的地址是 （ B ） B、 108 3. 假设带头结点的单向循环链表的头指针为 head,则该链表为空的判定条件是 （ C ） C、 headnext= =head 4. 若进栈序列为 1， 2， 3， 4， 5， 6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是 （ D ） D、 2， 3， 5， 1， 6， 4 5. 下列关键字序列中，构成小根堆的是 （ A ） A、 12， 21， 49， 33， 81， 56， 69， 41 6
2、. 下列数据结构中，不属于二叉树的是 （ A ） A、 B 树 7. 用顺序存储的方法来存储一棵二叉树，存放在一维数组 A1.N中，若结点 Ai有右孩子，则其右孩子是（ C ）。 C、 A2i+1 8. 设树 T 的高度为 4，其中度为 1、 2、 3、 4 的结点个数分别为 4、 2、 1、 1，则 T中叶子数为（ D ） D、 8 9. 有数据 53， 30， 37， 12， 45， 24， 96，从空二叉树开始逐个插入数 据来形成二叉排序树，若希望高度最小，则应选择下面哪个序列输入（ B ） B、 37， 24， 12， 30， 53， 45， 96 10. 对下面有向图给出了四种可能的
3、拓扑序列，其中错误的是 （ C ） C、 5， 1， 6， 3， 4， 2 11. m 阶 B-树中所有非终端（除根之外）结点中的关键字个数必须大于或等于 ( B ) B、 m/2-1 12. 散列文件也称为 ( C ) B 、 索引文件 13. 数据结构是 （ D ） D、相互之间存在一种或多种特定关系的数据元素的集合 14. 从逻辑关系来看，数据元素的直接前驱为 0 个或 1 个的数据结构只能是 （ C ） C、线性结构和树型结构 15. 设 p 为指向双向循环链表中某个结点的指针， p 所指向的结点的两个链域分别用 p llink和 p rlink 表示，则同样表示2 p 指针所指向结点
4、的表达式是 （ D ） D、 p llink rlink 16. 若栈采用顺序存储方式存储，现两栈共享空间 V1.m， topi代表第 i 个栈 ( i =1,2)栈顶，栈 1 的底在 v1，栈 2 的底在 Vm，则栈满的条件是 （ B ） B、 top1+1=top2 17. 若一棵二叉树有 11 个叶子结点，则该二叉树中度为 2 的结点个数是 （ A ） A、 10 18. 树的先根序列等同于与该树对应的二叉树的 （ A ） A、先序序列 19. 下面关于哈希 (Hash，杂凑 )查找的说法正确的是 ( C ) C、不存在特别好与坏的哈希函数，要视情况而定 20. 下列序列中，（ D ）是
5、执行第一趟快速排序后所得的序列。 D、 68， 11， 69， 23， 18 93， 73 21. 下列关键字序列中，构成 小根堆的是 ( D ) D、 (15， 28， 46， 37， 84， 58， 62， 41) 22. ISAM 文件和 VASM 文件属于 ( C ) C、索引顺序文件 23. 下面程序段 的时间复杂度为 （ C ） for (i=0; inext=s-next； s-next=p； 25. 为便于判别有向图中是否存在回路，可借助于 （ D ） D、 拓扑排序算法 26. 若以 S 和 X 分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操 作系列是（ D ）
6、D、 SSSXXSXX 27. 设有一顺序栈 S，元素 s1,s2,s3,s4,s5,s6 依次进栈，如果 6 个元素出栈的顺序是 s2,s3,s4,s6,s5,s1,则栈的容量至少应3 该是 ( B ) B、 3 28. 假设以数组 Am存放循环队列的元素。已知队列的长度为 length，指针 rear 指向队尾元素的下一个存储位置，则队头元素所在的存储位 置为 （ B ）。 B、 (rear-length+m)%m 29. 在一个链队列中， front 和 rear 分别为头指针和尾指针，则插入一个结点 s 的操作为（ D ）。 D、 rear-next=s;rear=s; 30. 对于哈
7、希函数 H(key)=key%13,被称为同义词的关键字是（ D ） D、 25 和 51 31. 采用二叉链表存储的 n 个结点的二叉树，共有空指针（ A ）个。 A、 n+1 32. 连通网的最小生成树是其所有生成树中 （ D ） D、 边的权值之和最小的生成树 33. 对记录序列 (314， 298， 508， 123， 486， 145)依次按个位和十位进行两趟基数排序之后所得结果为（ B ） B、 508， 314， 123， 145， 486， 298 34. 任何一个无向连通图的最小生成树 ( C )。 C、一棵或多棵 35. 无向图的邻接矩阵是一个 ( C ) C、对称矩阵 3
8、6. 设无向图 G-=(V,E)和 G =(V ,E ),如 G为 G 的生成树，则下列说法中不正确的是 ( B )。 B、 G为 G 连通分量 37. 以 v1 为起始结点对下图进行深度优先遍历，正确的遍历序列是 （ D ） D、 v1， v2， v5， v6， v7， v3， v4 38. 下面几个符号串编码集合中，不是前缀编码的是（ B ） B、 0,1,00,11 39. 希尔排序的增量序列必须是（ B ）。 B、递减的 40. 采用起泡排序法对 n 个关键字进行升序排序，若要使排序过程中比较 关键字的次数最多，则初始时的序列应满足条件（ D ） D、关键字从大到小排列 41. 在下列
9、内部排序中 ( A )是不稳定的。 4 A、希尔排序 42. 分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是 ( C )。 A、（ 100， 80， 90， 60， 120， 110， 130） 43. 在查找过程中，冲突指的是（ C ）。 C、不同键值对应相同的存储地址 44. 对有 14 个元素的有序表 A1.14作二分查找，查找元素 A4时的被比较元素依次为（ D ）。 D、 A7， A3， A5， A4 45. 以 v1 为起始结点对下图进行 广度 度优先遍历，正确的遍历序列是 （ A ） A、 v1， v2， v3， v4， v5， v6， v7 二、填空题 (本
10、大题共 10 小题，每小题 2 分，若有两个空格，每个空格 1 分，共 20 分 ) 1. 数据的物理结构包括 数据元素 的存储和 数据之间关系 的存储。 2. 若一个算法中的语句频度之和为 T(n)=1921n+4nlogn,则算法的时间复杂度为 nlogn 。 3. 下面程序段的时间复杂度是 nlog3 。 i=1； while (inext-next=L 17. 边 种不同的拓扑序列。 18. 从空树起，依次插入关键字 1l， 27， 35， 48， 52， 66 和 73 构造所得的二叉排序树，在等概率查找的假设下，查找 成功时的平均查找长度为 384 。 19. 带头结点的双循环链表
11、 L 中只有一个元素结点的条件是 队列 。 20. 求最小生成树的克鲁斯卡尔 (Kruskal)算法耗用的时间与图中 边稠密 、 边稀疏 的数目正相关。 21. 已知一棵完全二叉树中共有 768 结点，则该树中共有 5 个叶子结点。 22. 实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需要 8、 64 存放被访问的结点以实现遍历。 23. Prim（普里姆）算法适用于求 2h-1 的网的最小生成树； kruskal（克鲁斯卡尔）算法适用于求 2h-1 的网的最小生成树。 24. 对长度为 20 的有序表进行二分查找的判定树的高度为 n-1 。 25. 设一棵完全二叉树有 1
12、28 个结点，则该完全二叉树的深度为 n ，有 _ 个叶子结点。 26. 高度为 h 的完全二叉树中最少有 栈 个结点，最多有 个结点。 27. 设连通图 G 中有 n 个顶点 e 条边，则对应的最小生成树上有 3 条边。 28. 构造 n 个结点的强连通图，至少有 O(n2) 条弧。 29. 表达式求值是 （ 42,13,94,55,05,46,17） 应用的一个典型例子。 30. 设栈 S 和队列 Q 的初始状 态为空，元素 e1,e2,e3,e4,e5,e6 依次通过栈 S，一个元素出栈后即进入队列 Q，若 6 个元素出队的序列是 e2,e4,e3,e6,e5,e1，则栈的容量至少应该是
13、 。 31. 快速排序算法在最差的情况下其时间复杂度是 。 32. 对序列 55， 46， 13， 05， 94， 17， 42进行基数排序，第一趟排序后的结果是 。 三、应用题（本大题共 5 小题，每小题 6 分，共 30 分） 1. 已知二叉树的先序遍历序列 ABCDEFGH，中序遍历序列为 CBEDFAGH，画出二叉树。 6 答案： 二叉树形态 AFHGDECB2. 如图请给出 邻接表、邻接矩阵及逆邻接表 。 参考答案如下： （ 1） 邻接表： (注意边表中邻接点域的值是顶点的序号，这里顶点的序号是顶点的下标值 -1) vertex firstedge next （ 2） 逆邻接表： （
14、 3） V1 V3 V2 V4 7 3. 由字符集 s， t， a， e， I及其在电文中出现的频度构建的哈夫曼树如图所示。已知某段电文的哈夫曼编码为 111000010100，请根据该哈夫曼树进行译码，写出原来的电文 。 答案：原来的电文为： eatst 4. 请画出下图所示的树所对应的二叉树 ， 并写出对应二叉树的先序遍历和中序遍历 。 答案： 先序遍历为： 12345687 中序遍历为： 34867521 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 8 5. 设散列表为 HT13, 散列函数为 H (key) = key %13。用闭散列法解决冲突 , 对下列关键码序
15、列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。采用线性探查法寻找下一个空位 , 画出相应的散列表 , 并计算等概率下搜索成功的平均搜索长度。 答案： 使用散列函数 H(key) = key mod 13，有 H(12) = 12, H(23) = 10, H(45) = 6, H(57) = 5, H(20) = 7, H(03) = 3, H(78) = 0, H(31) = 5, H(15) = 2, H(36) = 10. 利用线性探查法造表： 0 1 2 3 4 5 6 7 8 9 10 11 12 78 15 03 57 45 20 31 2
16、3 36 12 (1) (1) (1) (1) (1) (1) (4) (1) (2) (1) 搜索成功的平均搜索长度为 ASLsucc = 110(1 + 1 + 1 + 1 + 1 + 1 + 4 + 1 + 2 + 1) = 14106. 已知带权图 G 如图所示，画出图 G 的一棵最小生成树。 答 ： 7. 假设用于通信的电文由字符集 a,b,c,d,e,f,g,h 中的字母构成，这 8 个字母 在电文中出现的 概率分别为0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10，请 为这 8 个字母设计哈夫曼编码。 9 哈夫曼编码为： a:1001 b:01 c:
17、10111 d:1010 e:11 f:10110 g:00 h:1000 注意：答案不唯一 8. 试用权集合 12,4,5,6,1,2构造哈夫 曼树，并计算哈夫曼树的带权路径长度。 21561 11 87341 23 0WPL=12*1+(4+5+6)*3+(1+2)*4=12+45+12=69 9. 画出与如图所示森林对应的二叉树 。 答： 10 10. 已知一个散列表如下图所示： 35 20 33 48 59 0 1 2 3 4 5 6 7 8 9 10 11 12 其散列函数为 h(key)=key%13, 处理冲突的方法为双重散列法，探查序列为： hi=(h(key)+ i *h1(
18、key)%m i =0,1,， m-1 其中： h1(key)=key%11+1 回答下列问题： （ 1）对表中关键字 35， 20， 33 和 48 进行查找时，所需进行的比较次数各为多少？ （ 2）该散列表在等概率查找时查找成功的平均查找长度为多少？ 答： （）对关键字 35、 20、 33 和 48 进行查找的比较次数为、； （）平均查找长度 A S L 3 2 1 1 25 95 11. 请画出与下列二叉树对应的森林。 答： 12. 对于给定结点的关键字集合 K=5， 7， 3， 1， 9， 6， 4， 8， 2， 10， （ 1）试构造一棵二叉排序树； （ 2）求等概率情况下的平均查找长度 ASL。 答：
