![](https://csdnimg.cn/release/download_crawler_static/86280099/bg1.jpg)
一、填空题(每空 2 分, 共 30 分)
NO.4
9. 包含 5 个顶点的有向图, 至多有 条弧。
10. 深度为 10 的完全二叉树至少有 个结点, 至多有 个结点。
11. 包含 20 个顶点的连通图, 其最小生成树拥有 条边。
1. 是数据的基本单位, 在计算机程序中通常作为一个整体进行考
虑和处理。
2. 数据的逻辑结构可分为集合、线性结构、 结构和 结构。
3. 数据元素之间的关系在计算机中有两种不同的表示方法: 顺序映象和
非顺序映象, 由此得到两种不同的存储结构: 顺序存储结构和 。
4. 算法的五个重要特性包括: 有穷性、 、 、输入和输出。
5. 下面的算法计算实数 x (x > 0)的非负整数 n (n 0)次幂, 其时间复杂
度是 。
double Power(double x, int n)
{
double y = 1;
if (n > 0)
{
y = Power(x, n / 2);
y *= y;
if (n % 2 == 1) y *= x;
}
return y;
}
6. 只在表的一端进行插入和删除的线性表称为 。在表的一端进行
插入、另一端进行删除的线性表称为 。
7. 在 C 语言中定义下面的二维实型数组:
double a[5][10];
每个元素占用 8 字节内存空间, 若数组起始地址为 0x1000, 则元素
a[3][5] 的地址为 0x 。
8. 已知完全二叉树有 1024 个结点, 则该二叉树的深度为 。
二、单项选择题 (每小题 2 分,共 20 分)
1. 若元素 1, 2, 3 依次进栈, 则出栈的次序不可能是 。
A) 3, 2, 1 B) 1, 3, 2 C) 3, 1, 2 D) 2, 1, 3
2. 在无附加头结点的链栈中, 若栈顶指针为 top, 将指针 s 所指示的结点
入栈, 所执行的操作为 。
A) s->next = top; top = top->next;
B) top = s; s->next = top;
C) s->next = top->next; top->next = s;
D) s->next = top; top = s;
3. 在无附加头结点的链栈中, 若栈顶指针为 top, 则判断栈空的条件是
。
A) top==NULL B) top!=NULL
C) top->next == top D) top->next==NULL
4. 循环队列存于数组 a[M]中, 假定队首和队尾指针分别是 front 和 rear,
则判断队空的条件是 。
A) front == 0 B) rear == 0 C) front == M - 1 D) front == rear
5. 是关于排序算法的错误说法。
A) 直接插入法和冒泡法是稳定的
B) 快速法在任何情况下都是最快的
C) 二路归并算法需要的辅助空间是 O(n)
D) 堆排序的时间复杂度是 O(n lb n)
6. 主关键字是指能唯一标识一条记录的 。
A) 一个数据项 B) 一组数据项 C) A 或 B D) 以上都不是
7. 按照二叉树的定义, 具有 3 个结点的二叉树有 种形态。
评论0