广 东 商 学 院 试 题 纸 考试时间共 分钟
课程名称 数据结构(A 卷 课程代码 110104 课程班号 共 _3_页 ------------------------------------------------------------------------------------------------------------------------
一、 单选题(每小题 1分,共 20分
(注意:请将本题答案写在答题纸第 1页的单项选择题表格中 1、数据结构是指【 】 。
A .数据类型 B .数据定义 C .数据的存储结构 D .数据的组织形式
2、从有 n 个结点的单链表中查找值为 x 的结点时,在查找成功的情况下,需平均比较【 】个结点。 A . n B . n/2 C . (n-1/2 D . (n+1/2
3、一个顺序队列第 5个元素的存储地址是 200,第 10个元素的存储地址是 225,则第 20个元素的存储地 址是【 】 。
A . 220 B . 230 C . 270 D . 275
4、判断一个顺序栈 (最多有 m 个元素 为空的条件是【 】 。 A . S.base==0 B . S.top==-1 C . S.top==S.base D . S.top-S.base>=m 5、判断一个顺序循环队列 Q (最多 m 个元素为满的条件是【 】 。 A . Q.front==Q.rear B . Q.front!=Q.rear
C . Q.front==(Q.rear+1%m D . Q.rear==(Q.front+1%m 6、有 100个叶结点的哈夫曼树共有【 】个结点。 A . 101 B . 199C . 200 D . 201
7、设高度为 h 的二叉树只有度为 0和度为 2的结点,则此类二叉树的结点数至少为【 】个。
A . 2h B . 2h-1 C . 2h+1 D . h+1 8、 5层的二叉树至多有【 】个结点。 A . 10 B . 16 C . 31 D . 32
9、深度为 h 的完全二叉树中,编号最小的叶结点的编号是【 】 。 A . 2h-1B . 2h -1 C . 2h-1+1 D . 2h-2+1
10、森林的中序遍历序列与对应的二叉树的【 】遍历序列一致。 A .先序 B .中序 C .后序 D .不可能
11、要连通有 n 个顶点的无向图至少需要【 】条边。 A . n B . n/2 C . n-1D . n+1
12、在一个无向图中,所有顶点的度数之和等于所有边数之和的【 】倍。 A . 1/2 B . 1 C . 2 D . 4
13、设有 100个数据元素,采用折半查找时最大的关键字比较次数是【 】 。 A . 5 B . 6 C . 7 D . 8
14、 对关键字序列 {50, 70, 40, 85, 75, 20, 35, 45, 65, 30}建立二叉排序树, 查找元素 35需进行 【 】 次关键字的比较。
A . 2 B . 3 C . 4D . 5
15、 m 阶 B-树中所有内部结点的关键字个数必须大于或等于【 】 。 (注:「」代表向上取整
A . 「 m/2」 B . 「 m/2」 -1 C . 「 m/2」 +1 D . m 16、就平均性能而言,目前最好的排序方法是【 】 。 A .起泡排序 B .希尔排序 C .选择排序 D .快速排序
17、在待排序列基本有序的前提下,效率最高的排序方法是【 】 。 A .插入排序 B .归并排序 C .选择排序 D .快速排序 18、下述几种排序方法中,要求内存量最大的是【 】 。
A .插入排序 B .选择排序 C .快速排序 D .归并排序 19、堆是一种基于【 】原则的排序方法。
A .插入 B .选择 C .交换 D .归并 20、对 n 个不同的记录进行起泡排序,在正序的情况下关键字比较的次数为【 】 。 A . n B . n-1 C . n+1 D . n (n-1 /2
二、 填空题(每小题 1分,共 10分 1、在队列中存取数据应遵循 的原则。 2、由一棵二叉树的后序序列和
3、具有 n 个分支的二叉树,共有 个结点。 4、图的存储方式中,邻接多重表用于 图的存储。 5、运行图的深度优先遍历算法需要 6、对 AOV 网运行 7、求最小生成树的
8、在各种查找方法中,平均查找长度与结点个数 n 无关的查找方法是 。
9、对二叉排序树进行平衡化处理的目的,是使 最小。 10、基数排序的两个子过程是 和收集。 三、 简答题(每小题 分,共 分 四、 综合题(每小题 分,共 分 五、 算法设计(共 8 分
现有一个带头结点的单链表 L ,要求: (1写出单链表存储结构的定义; (3分 (注:结点 LNode ,单链表 LinkList
(2编写一个返回 L 中值为 x 的结点的位序的算法 Locate_LinkList。(注:算法可用类 C 或其他语言描述,适当加上说明,以增加可读性
分 (5