（ ）1. 在一个图中，所有顶点的度数之和等于图的边数的 倍。
A．1/2 B. 1 C. 2 D. 4 （ ）2. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。 A．1/2 B. 1 C. 2 D. 4 （ ）3. 有8个结点的无向图最多有 条边。
A．14 B. 28 C. 56 D. 112 （ ）4. 有8个结点的无向连通图最少有 条边。
A．5 B. 6 C. 7 D. 8 （ ）5. 有8个结点的有向完全图有 条边。
A．14 B. 28 C. 56 D. 112 （ ）6. 用邻接表表示图进行广度优先遍历时，通常是采用 来实现算法的。
A．栈 B. 队列 C. 树 D. 图 （ ）7. 用邻接表表示图进行深度优先遍历时，通常是采用 来实现算法的。
A．栈 B. 队列 C. 树 D. 图 （ ）8. 已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序
?0????1???1????1???1????0????1?111101??001001??000100??100110??011010???001101??100010??A．0 2 4 3 1 5 6
B. 0 1 3 6 5 4 2 C. 0 4 2 3 1 6 5 D. 0 3 6 1 5 4 2
列是
（ ）9. 已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按深度优先遍历的结点序列是
A． 0 2 4 3 1 5 6 B. 0 1 3 5 6 4 2 C. 0 4 2 3 1 6 5 D. 0 1 3 4 2
5 6
（ ）10. 已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按广度优先遍历的结点序列是
A． 0 2 4 3 6 5 1 B. 0 1 3 6 4 2 5 C. 0 4 2 3 1 5 6 D. 0 1 3 4 2
5 6
（ ）11. 已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按广度优先遍历的结点序列是
A． 0 2 4 3 1 6 5 B. 0 1 3 5 6 4 2 C. 0 1 2 3 4 6 5 D. 0 1 2 3 4 5
6
（ ）12. 已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是
5
A．0 1 3 2 B. 0 2 3 1 C. 0 3 2 1 D. 0 1 2 3
（ ）13. 已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是
A．0 3 2 1 B. 0 1 2 3 C. 0 1 3 2 D. 0 3 1 2
（ ）14. 深度优先遍历类似于二叉树的
A．先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历 （ ）15. 广度优先遍历类似于二叉树的
A．先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历 （ ）16. 任何一个无向连通图的最小生成树
A．只有一棵 B. 一棵或多棵 C. 一定有多棵 D. 可能不存
在
二、填空题
1. 一个计算机系统包括 硬件系统 和 软件系统 两大部分。 2. 一台计算机中全部程序的集合，称为这台计算机的 。
3. 计算机软件可以分为 系统 软件和 应用 软件两大类。科学计算程序包属于 应用软件 ，诊断程序属于 系统软件 。
4. 一种用助忆符号来表示机器指令的操作符和操作数的语言是 。
5. 数据结构是一门研究非数值计算的程序设计问题中计算机的 操作对象 以及它们之间的 关系 和运算等的学科。
6. 线性结构中元素之间存在 一对一 关系，树形结构中元素之间存在 一对多 关系，图形结构中元素之间存在 多对多 关系。
7. 在树形结构中，树根结点没有 双亲 结点，其余每个结点有且只有 一 个
前驱结点；叶子结点没有 后驱 结点，其余每个结点的后续结点数可以 有一个或多个 。
8. 在图形结构中，每个结点的前驱结点数和后续结点数可以 。 9. 数据的存储结构可用四种基本的存储方法表示，它们分别是 顺序存储、链式存储、索引存储、散列存储 。
10．数据的运算最常用的有5种，它们分别是 初始化、插入、
6
删除、查找、按序号取元素 。
11. 任何一个C程序都由 一个main函数 和若干个被调用的其它函数组成。
12. 变量一经说明，就确定该变量的取值范围及 。
13．在顺序表中插入或删除一个元素，需要平均移动 表中一半 元素，具体移动的元素个数
与 插入和删除的位置 有关。
1. 线性表中结点的集合是 的，结点间的关系是 的。
2. 向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动 n-i 个元素。
3. 在顺序表中访问任意一结点的时间复杂度均为 O(1) ，因此，顺序表也称为 的数据结构。
4. 顺序表中逻辑上相邻的元素的物理位置 一定 相邻。单链表中逻辑上相邻的元素的物理位置 不一定 相邻。
5. 在单链表中，除了首元结点外，任一结点的存储位置由 结点的指针域 指示。
1. 向量、栈和队列都是 线性 结构，可以在向量的 任意 位置插入和删除元
素；对于栈只能在 栈顶 插入和删除元素；对于队列只能在 队尾 插入和 对头 删除元素。
2. 队列 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。
3. 在一个循环队列中，队首指针指向队首元素的 相同 位置。 4. 在具有n个单元的循环队列中，队满时共有 n 个元素。
5. 向栈中压入元素的操作是先 插入元素 ，后 移动指针 。
6. 从循环队列中删除一个元素时，其操作是 先 修改指针 ，后 删除元素 。
7. 带表头结点的空循环双向链表的长度等于 0 。
1. 零个字符的串 称为空串； 由一个或多个空格组成的串 称为空白串。
2. 设S=“A;/document/Mary.doc”，则strlen(s)= 20 , “/”的字符定位的位置为 3 。
7
3. 子串的定位运算称为串的模式匹配； 称为目标串， 称为模式。
4. 设目标T=”abccdcdccbaa”，模式P=“cdcc”，则第 6 次匹配成功。
5. 若n为主串长，m为子串长，则串的古典匹配算法最坏的情况下需要比较字符的总次数为 n-m 。
6. 假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为 1288 ；末尾元素A57的第一个字节地址为 1276或1246 ；若按行存储时，元素A14的第一个字节地址为 1018 ；若按列存储时，元素A47的第一个字节地址为 1234 。
7. 设数组a[1?60, 1?70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为 8950 。
8.求下列广义表操作的结果：
（1） GetHead【((a,b),(c,d))】=== （a,b） ; （2） GetHead【GetTail【((a,b),(c,d))】】=== (c,d) ;
1． 由３个结点所构成的二叉树有 5 种形态。
2. 一棵深度为6的满二叉树有 63 个分支结点和 32 个叶子。
3． 一棵具有２５７个结点的完全二叉树，它的深度为 9 。
4. 设一棵完全二叉树有700个结点，则共有 350 个叶子结点。
5. 设一棵完全二叉树具有1000个结点，则此完全二叉树有 个叶子结点，有 个度为2的结点，有 个结点只有非空左子树，有 个结点只有非空右子树。
6.一棵含有n个结点的k叉树，可能达到的最大深度为 ，最小深度为 。
7. 二叉树的基本组成部分是：根（N）、左子树（L）和右子树（R）。因而二叉树的遍历次序有六种。最常用的是三种：前序法（即按N L R次序），后序法（即按 次序）和中序法（也称对称序法，即按L N R次序）。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是 。
8.中序遍历的递归算法平均空间复杂度为 。
8
相关推荐：
loading