计算机软件技术基础题库.doc

1 计算机软件技术基础题库计算机软件技术基础题库 目 录 第一章 数据结构 1 参考答案 28 第二章 软件工程 47 参考答案 56 第三章 面向对象的软件开发技术 69 参考答案 72 第四章 操作系统 77 参考答案 86 第五章 数据库基础 94 参考答案 101 第六章 信息系统 107 参考答案 113 2 第第 1 章章 数据结构数据结构 一 选择题一 选择题 1 算法指的是 A 计算机程序 B 解决问题的计算方法 C 排序方法 D 解决问题的有限运算序列 2 在数据的树形结构中 数据元素之间为 的关系 A 0 0 B 1 1 C 1 n D m n 3 数据的存储结构包括顺序 链接 散列和 4 种基本类型 A 索引 B 数组 C 集合 D 向量 4 一个数组元素 a i 与 的表示等价 A else s2 i A O 1 B O 1bn C O n D O 2n 8 下面程序段的时间复杂度为 for int i 0 i m i for int j 0 j n j a i j i j A O m2 B O n2 C O m n D O m n 9 执行下面程序段时 S 语句的执行次数为 for int i 1 i n i for int j 1 jnext ph B p next ph ph p C p next ph p ph D p next ph next ph next p 21 在一个表头指针为 ph 的单链表中 若要在指针 q 所指结点的后面插入一个 由指针 p 所指向的结点 则执行 操作 A q next p next p next q B p next q next q p C q next p next p next q D p next q next q next p 22 在一个单链表 HL 中 若要删除由指针 q 所指向结点的后继结点 若存在的 话 则执行 操作 A p q next p next q next B p q next q next p C p q next q next p next D q next q next next q next q 23 在一个带头结点的循环双向链表中 若要在指针 p 所指向的结点之后插入一 个 q 指针所指向的结点 则需要对 q next 赋值为 A P prior B p next C p next next D p prior prior 24 在一个带头结点的循环双向链表中 若要在指针 p 所指向的结点之前插入一 个 q 指针所指向的结点 则需要对 p prior next 赋值为 A q B p C p next D p prior 25 在一个带头结点的循环双向链表中 若要删除指针 p 所指向的结点则执行 操作 A p prior next p next p next prior p prior B p next prior p p next p next next C p prior next p p next p next prior 4 D p p next p prior next p prior 26 栈的插入和删除操作在 进行 A 栈顶 B 栈底 C 任意位置 D 指定位置 27 当利用大小为 N 的数组顺序存储一个栈时 假定用 top N 表示栈空 则向 这个栈插入一个元素时 首先应执行 语句修改 top 指针 A top B top C top 0 D top N 1 28 假定利用数组 a N 顺序存储一个栈 用 top 表示栈顶指针 用 top N 1 表示 栈空 该数组所存储的栈的最大长度为 N 则表示栈满的条件为 A top 1 B top 1 C top 0 D top N 1 29 假定利用数组 a N 顺序存储一个栈 用 top 表示栈顶指针 用 top 1 表示 栈空 并已知栈未满 当元素 x 进栈时所执行的操作为 A a top x B a top x C a top x D a top x 30 假定利用数组 a N 顺序存储一个栈 用 top 表示栈顶指针 用 top 1 表示 栈空 并已知栈未空 当退栈并返回栈顶元素时所执行的操作为 A return a top B return a top C return a top D return a top 31 假定一个链式栈的栈顶指针用 top 表示 该链式栈为空的条件 A top NULL B top top next C top NULL D top top next 32 假定一个链式栈的栈顶指针用 top 表示 每个结点结构为 当 p 所 data next 指向的结点进栈时 执行的操作为 A p next top top top next B top p p next top C p next top next top next p D p next top top p 33 假定一个链式栈的栈顶指针用 top 表示 每个结点结构为 退栈时 data next 所执行的操作为 A top next top B top top data C top top next D top next top next next 34 若让元素 1 2 3 4 依次进栈 则出栈次序不可能出现 的情况 A 3 2 1 4 B 2 1 4 3 C 4 3 2 1 D 1 4 2 3 35 在一个顺序循环队列中 队首指针指向队首元素的 位置 A 前一个 B 后一个 C 当前 D 最后 36 当利用大小为 N 的数组循环存储一个队列时 该队列的最大长度为 A N 2 B N 1 C N D N 1 37 从一个顺序循环队列中删除元素时 首先需要 A 前移队首指针 B 后移队首指针 C 取出队首指针所指位置上的元素 D 取出队尾指针所指位置上的元素 38 假定一个顺序循环队列的队首和队尾指针分别用 f 和 r 表示 则判断队空的 条件为 A f 1 r B r 1 f C f 0 D f r 39 假定一个顺序循环队列存储于数组 a N 其队首和队尾指针分别用 f 和 r 表 示 则判断队满的条件为 A r 1 N f B r 1 N f C f 1 N r D f 1 N r 40 假定利用数组 a N 循环顺序存储一个队列 其队首和队尾指针分别用 f 和 r 5 表示 并已知队列未满 当元素 x 入列时所执行的操作为 A a r N x B a r N x C a r N x D a r N x 41 假定利用数组 a N 循环顺序存储一个队列 其队首和队尾指针分别用 f 和 r 表示 并已知队列未空 当出列并返回队首元素时所执行的操作为 A return a r N B return a r N C return a f N D return a f N 42 假定一个链式队列的队首和队尾指针分别为 front 和 rear 则判断队空的条件 为 A front rear B front NULL C rear NULL D front NULL 43 假定一个链式队列的队首和队尾指针分别为 front 和 rear 每个结点结构为 当出列时所进行的操作为 data next A front front next B rear rear next C front next rear rear rear next D front front next front next rear 44 假定一个带头结点的循环链式队列的队首和队尾指针分别用 front 和 rear 表 示 则判断对空的条件为 A front rear next B rear NULL C front NULL D front rear 45 假定一个链式队列的队首和队尾指针分别为 front 和 rear 每个结点结构为包 含值域 data 和指针域 next 则使 p 所指结点入列所执行的操作为 A p next NULL rear rear next p B p next rear next rear rear next p C p next front front p D p next front next front next p 46 在一个长度为 N 的数组空间中 循环顺序存储着一个队列 该队列的队首和 队尾指针分别用 front 和 rear 表示 则该队列中数组元素个数为 A rear front N B rear front N N C rear N N D front N N 47 二维数组 A 12 10 采用行优先存储 每个数据元素占用 4 个存储单元 该数 组的首地址 即 A 0 0 的地址 为 1200 则 A 6 5 的地址为 A 1400 B 1404 C 1372 D 1460 48 有一个 M N 的矩阵 A 若采用行优先进行顺序存储 每个元素占用 8 个字 节 则 Aij 1 i M 1 j N 元素的相对字节地址 相对首元素地址而言 为 A i 1 N j 8 B i 1 N j 1 8 C i N j 1 8 D i 1 N j 1 8 49 有一个 N N 的下三角矩阵 A 若采用行优先进行顺序存储 每个元素占用 k 个字节 则 Aij 1 i N 1 j i 元素的相对字节地址 相对首元素地址而言 为 A i i 1 2 j 1 4 B i i 2 j 4 C i i 1 2 j 1 4 D i i 1 2 j 4 50 树中所有结点的度等于所有结点数加 A 0 B 1 C 1 D 2 51 在一棵树中 没有前驱结点 6 A 树枝结点 B 叶子结点 C 树根结点 D 空结点 52 在一棵树中 每个结点最多有 个前驱结点 A 0 B 1 C 2 D 任意多个 53 在一棵二叉树的二叉链表中 空指针域数等于非空指针域数加 A 2 B 1 C 0 D 1 54 在一棵具有 n 个结点的二叉树中 所有结点的空子树个数等于 A n B n 1 C n 1 D 2n 55 在一棵具有 n 个结点的二叉树的第 i 层上 最多具有 个结点 A 2i B 2i 1 C 2i 1 D 2n 56 在一棵深度为 h 的完全二叉树中 所含结点个数不小于 A 2h B 2h 1 C 2h 1 D 2h 1 57 在一棵深度为 h 的完全二叉树中 所含结点个数不大于 A 2h B 2h 1 C 2h 1 D 2h 1 58 在一棵具有 35 个结点的完全二叉树中 该树的深度为 A 6 B 7 C 5 D 8 59 在一棵完全二叉树中 若编号为 i 的结点存在左孩子 则左孩子结点编号为 A 2i B 2i 1 C 2i 1 D 2i 2 60 在一棵完全二叉树中 若编号为 i 的结点存在右孩子 则右孩子结点编号为 A 2i B 2i 1 C 2i 1 D 2i 2 61 在一棵完全二叉树中 对于编号为 i i 1 的结点其双亲结点的编号为 A i 1 2 B i 1 2 C i 2 D i 2 62 有如图 1 1 所示的一棵二叉树 则该二叉树 所含单支结点数为 A 2 B 3 C 4 D 5 63 有如图 1 2 所示的一棵二叉树 则该二叉树 的中序遍历序列为 A ABCDEFG B CDBGFEA C CBDAEGF D ABECDFG 64 有如图 1 2 所示的一棵二叉树 则该二叉树 的先序遍历序列为 A ABCDEFG B CDBGFEA C CBDAEGF D ABECDFG 65 有如图 1 2 所示的一棵二叉树 则该二叉树的后序便利序列为 A ABCDEFG B CDBGFEA C CBDAEGF D ABECDFG 66 利用 n 个值生成的哈夫曼树中共有 个结点 A n B n 1 C 2n D 2n 1 67 利用 3 6 8 12 这 4 个值作为叶子结点的权 生成一棵哈夫曼树 该树的带权路径长度为 A 55 B 29 C 58 D 38 A B C E 图 1 1 D G H F A B C 图 1 2 E G D F 7 68 在一个具有 n 个顶点的有向图中 若所有顶点的出度数之和为 s 则所有的 入度数之和为 A s B s 1 C s 1 D n 69 在一个具有 n 个顶点的有向图中 若所有顶点的出度数之和为 s 则所有的 度数之和为 A s B s 1 C s 1 D 2s 70 在一个具有 n 个顶点的无向图中 若具有 e 条边 则所有顶点的度数为 A n B e C n e D 2e 71 在一个具有 n 个顶点的无向完全图中 所含的边数为 A n B n n 1 C n n 1 2 D n n 1 2 72 在一个具有 n 个顶点的有向完全图中 所含的边数为 A n B n n 1 C n n 1 2 D n n 1 2 73 在一个具有 n 个顶点的无向连通图中 它包含的连通分量的个数为 A 0 B 1 C n D n 1 74 若有一个图中包含 k 个连通分量 若按照深度优先搜索的方法访问所有顶点 则必须调用 次深度优先搜索遍历的算法 A k B 1 C k 1 D k 1 75 若要把 n 个顶点连接为一个连通图 则至少需要 条边 A n B n 1 C n 1 D 2n 76 在一个具有 n 个顶点和 e 条边的无向图的邻接矩阵中 表示边存在的元素 又称为有效元素 的个数为 A n B ne C e D 2e 77 在一个具有 n 个顶点和 e 条边的有向图的邻接矩阵中 表示边存在的元素的 个数为 A n B ne C e D 2e 78 在一个具有 n 个顶点和 e 条边的无向图的邻接矩阵中 边结点的个数为 A n B ne C e D 2e 79 对于一个有向图 若一个顶点的度为 k1 出度为 k2 则对应邻接表中该顶 点单链表的边数结点为 A k1 B k2 C k1 k2 D k1 k2 80 对于一个有向图 若一个顶点的度为 k1 出度为 k2 则对应逆邻接表中该 顶点单链表的边数结点为 A k1 B k2 C k1 k2 D k1 k2 81 对于一个无向图 下面 的说法是正确的 A 每个顶点的入度等于出度 B 每个顶点的度等于入度和出度之和 C 每个顶点的入度为 0 D 每个顶点的出度为 0 82 在一个有向图的邻接表中 每个顶点单链表中结点的个数等于该顶点的 A 出边数 B 入边数 C 度数 D 度数减一 83 若一个图的边集为 A B A C B D C F D E D F 则从顶点 A 开始对该图进行深度优先搜索 得到的顶点序列可能为 A ABCFDE B ACFDEB C ABDCFE D ABDFEC 8 84 若一个图的边集为 A B A C B D C F D E D F 则从顶点 A 开始对该图进行广度优先搜索 得到的顶点序列可能为 A ABCDEF B ABCFDE C ABDCEF D ACBFDE 85 若一个图的边集 1 2 1 4 2 5 3 1 3 5 4 3 则从 顶点 1 开始对该图进行深度优先搜索 得到的顶点序列可能为 A 1 2 5 4 3 B 1 2 3 4 5 C 1 2 5 3 4 D 1 4 3 2 5 86 若一个图的边集 1 2 1 4 2 5 3 1 3 5 4 3 则从 顶点 1 开始对该图进行广度优先搜索 得到的顶点序列可能为 A 1 2 3 4 5 B 1 2 4 3 5 C 1 2 4 5 3 D 1 4 2 5 3 87 由一个具有 n 个顶点的连通图生成的最小树中有 条边 A n B n 1 C n 1 D 2n 88 若查找每一个元素的概率相等 则在长度为 n 的顺序表上查找任一元素的平 均查找长度为 A n B n 1 C n 1 2 D n 1 2 89 对长度为 n 的单链有序表 若查找每个元素的概率相等 则查找任一个元素 的平均查找长度为 A n 2 B n 1 2 C n 1 2 D n 4 90 对于长度为 9 的顺序存储的有序表 若采用二分查找 在等概率情况下的平 均查找长度为 的值除以 9 A 20 B 18 C 25 D 22 91 对于长度为 18 的顺序存储的有序表 若采用二分查找 则查找第 15 个元素 的查找长度为 A 2 B 3 C 4 D 6 92 对于顺序存储的有序表 5 12 20 26 37 42 46 50 64 若采用二 分查找 则查找元素 26 的查找长度为 A 2 B 3 C 4 D 5 93 在分块查找中 若用于保存数据元素的主表长度为 n 它被分为 k 个子表 每个子表的长度均为 n k 若用顺序查找确定块 则分块查找的平均查找长度为 A n k B k n k C k n k 2 D k n k 2 1 94 在分块查找中 若用于保存数据元素的主表长度为 144 它被分为 12 个子表 每个子表的长度均为 12 若用顺序查找确定块 则分块查找的平均查找长度为 A 13 B 24 C 12 D 79 95 在一棵深度为 h 的具有 n 个元素的二叉排序树中 查找所有元素的最长查找 长度为 A n B lbn C h 1 2 D h 96 在一棵平衡二叉排序树中 每个结点的平衡因子的取值范围是 A 1 1 B 2 2 C 1 2 D 0 1 97 若根据查找表 23 44 36 48 52 73 64 58 建立线性哈希表 采用 H K K 13 计算哈希地址 则元素 64 的哈希地址为 A 4 B 8 C 12 D 13 98 若根据查找表 23 44 36 48 52 73 64 58 建立线形哈希表 采用 9 H K K 13 计算哈希地址 则哈希地址为 3 的元素个数为 A 1 B 2 C 3 D 4 99 若根据查找表建立长度为 m 的线性哈希表 采用线性探测再哈希法处理冲突 假定对一个元素第一次计算的哈希地址为 d 则下一次的哈希地址为 A d B d 1 C d 1 m D d 1 m 100 在采用线性探测再哈希法处理冲突的线性哈希表上 假定装填因子 a 的值 为 0 5 则查找任一个元素的平均查找长度为 A 1 B 1 5 C 2 D 2 5 101 在哈希查找中 平均查找长度主要与 有关 A 哈希表长度 B 哈希元素个数 C 装填因子 D 处理冲突方法 102 若对 n 个元素进行直接插入排序 则进行第 i 趟排序过程前 有序表中元素 的个数为 A i B i 1 C i 1 D 1 103 若对 n 个元素进行直接插入排序 在进行第 i 趟排序时 为寻找插入位子最 多需要进行 次元素的比较 假定第 0 号元素放有待查的键值 A i B i 1 C i 1 D 1 104 若对 n 个元素进行直接插入排序 在进行第 i 趟排序时 假定元素 r i 1 的插 入位置为 r j 则需要移动元素的次数为 A j i B i j 1 C i j D i j 1 105 若对 n 个元素进行直接插入排序 在进行任意一趟排序的过程中 为寻找 插入位置而需要的时间复杂度为 A O 1 B O n C O n2 D O lbn 106 在对 n 个元素进行直接插入排序的过程中 共需要进行 趟 A n B n 1 C n 1 D 2n 107 对 n 个元素进行直接插入排序的时间复杂度为 A O 1 B O n C O n2 D O lbn 108 在对 n 个元素进行冒泡排序的过程中 第一趟排序至多进行 对相邻元 素之间的交换 A n B n 1 C n 1 D n 2 109 在对 n 个元素进行冒泡排序的过程中 最坏情况下的时间复杂度为 A O 1 B O lbn C O n2 D O n 110 在对 n 个元素进行冒泡排序的过程中 至多需要 趟完成 A 1 B n C n 1 D n 2 111 在对 n 个元素进行快速排序的过程中 最好情况下需要进行 趟 A n B n 2 C lbn D 2n 112 在对 n 个元素进行快速排序的过程中 最坏情况下需要进行 趟 A n B n 1 C n 2 D lbn 113 对下列 4 个序列进行快速排序 各以第一个元素为基准进行第一次划分 则在该次划分过程中需要移动元素次数最多的序列为 A 1 3 5 7 9 B 9 7 5 3 1 C 5 3 1 7 9 D 5 7 9 1 3 114 假定对元素序列 7 3 5 9 1 12 8 15 进行快速排序 则进行第 一次划分后 得到的左区间中元素的个数为 A 2 B 3 C 4 D 5 115 在对 n 个元素进行简单选择排序的过程中 在第 i 趟需要从 个元素中选 10 择出最小值元素 A n i 1 B n i C i D i 1 116 若对 n 个元素进行简单选择排序 则进行任一趟排序的过程中 为寻找最 小值元素所需要的时间复杂度为 A O 1 B O lbn C O n2 D O n 117 假定一个初始堆为 1 5 3 9 12 7 15 10 则进行第一趟堆排序 后得到的结果为 A 3 5 7 9 12 10 15 1 B 3 5 9 7 12 10 15 1 C 3 7 5 9 12 10 15 1 D 3 5 7 12 9 10 15 1 118 若一个元素序列基本有序 则选用 方法较快 A 直接插入排序 B 简单选择排序 C 堆排序 D 快速排序 119 若要从 1000 个元素中得到 10 个最小元素 最好采用 方法 A 直接插入排序 B 简单选择排序 C 堆排序 D 快速排序 120 在平均情况下速度最快的排序方法为 A 简单选择排序 B 冒泡排序 C 堆排序 D 快速排序 二二 填空题填空题 1 数据的逻辑结构可分为 和 两大类 2 数据的存储结构被分为 和 4 种 3 在下面的程序段中 s s p 语句被执行次数为 p j 语句的执行次数为 该程序的复杂度为 int i 0 s 0 while i n int p 1 for int j 1 j i j p j s s p 4 一种数据结构的元素集合 K 和它的二元关系 R 为 K a b c d e f g h R 则该数据结构具有 结构 5 线性表的两种存储结构分别为 和 6 线性表的顺序存储结构称为 链式存储结构称为 7 若经常需要对线性表进行插入和删除运算 则最好采用 存储结构 若经常 需要对线性表进行查找运算 则最好采用 存储结构 8 对于一个长度为 n 的顺序存储的线性表 在表头插入元素的时间复杂度为 9 对于一个单链表存储的线性表 在表头插入结点的时间复杂度为 在表 尾插入结点的时间复杂度为 10 在线性表的单链表存储中 若一个元素所在结点的地址为 p 则其后的断结 点的地址为 11 在以 HL 为头指针的带头结点的单链表和循环单链表中 链表为空的条件分 别为 和 12 在 链表中 既可以通过设定一个头指针 也可以通过设定一个尾指针来 11 确定它 即通过头指针或尾指针可以访问到该链表的每个结点 13 在一个单链表中删除指针 p 所指向结点的后继结点时 需要把 的值赋给 p next 指针域 14 在一个单链表中指针 p 所指向结点的后面插入一个指针 q 所指向的节点时 首先把 的值赋给 p next 然后把 的值赋给 p next 15 假定指向单链表中第一个结点的头指针为 head 则像该单链表的表头插入指 针 p 所指向的新结点时 首先执行 赋值操作 然后执行 赋值操作 16 访问一个顺序表和一个单链表中第 i 个元素的时间复杂度分别为 和 17 在一个带头结点的循环单链表中 在表头插入或删除与在其它位置插入和删 除 其操作过程是否相同 18 在双向链表中每个结点包含有两个指针域 一个指向其 结点 另一个指 向其 结点 19 在一个双向链表中指针 p 所指向的结点之后插入一个指针 q 所指向的结点时 需要对 p next prior 指针域赋值为 20 在一个双向链表中删除指针 p 所指向的结点时 需要对 p next prior 指针 域赋值为 21 栈又称为 表 队列又称为 表 22 在一个用一维数组 a N 表示的顺序栈中 该栈所含元素的个数最少为 个 最多为 个 23 像一个顺序栈插入一个元素时 首先使 后移一个位置 然后把新元素 到这个位子 24 从一个栈删除元素时 首先取出 然后再使 减一 25 一个顺序栈存储一个一维数组 a M 中 栈顶指针用 top 表示 当栈顶指针等 于 时为空栈 栈顶指针为 时为满栈 26 假定一个链栈的栈顶指针为 top 每个结点包含值域 data 和指针域 next 当 p 所指向的结点入栈时 则首先执行 操作 然后执行 操作 27 假定一个链栈的栈顶指针为 top 每个结点包含值域 data 和指针域 next 当 进行出栈运算时 假定栈非空 需要把栈顶指针修改为 的值 28 设元素 1 2 3 4 5 依次进栈 若要在输出端得到序列 34251 则应进行 的操作序列为 Push s 1 Push s 2 Pop s Push s 4 Pop s Pop s Pop s 29 设元素 a b c d 依次进栈 若要在输出端得到序列 cbda 则应进行的操 作序列为 Push s a Push s b Push s c Pop s Pop s 30 队列的插入操作在 进行 删除操作在 进行 31 一个顺序循环队列存在于 a M 中 假定队首和队尾指针分别为 front 和 rear 则判断对空的条件为 判断对满的条件为 32 一个顺序循环队列存在于 a M 中 假定队首和队尾指针分别为 front 和 rear 则求出队首和队尾指针的下一个位置的计算公式分别为 和 33 在一个用一维数组 a N 存储的顺序循环队列中 该队列中的元素个数最少为 个 最多为 个 34 向一个顺序循环队列中插入元素时 需要首先移动 然后再向它所指位 置 新元素 12 35 在一个空链队列中 假定队首和队尾指针分别为 f 和 r 当向他插入一个新 结点 p 时 则首先执行 操作 然后执行 操作 36 在一个带头结点的循环链队列中 假定队首和队尾指针分别为 f 和 r 当向 它插入一个新结点 p 时 则首先执行 操作 然后执行 操作 37 假定 front 和 rear 分别为一个链队列的对首和队尾指针 则该链队列中只有 一个结点的条件为 38 在一个链栈中 若栈顶指针等于 NULL 则为 在一个链队列中 若对首 和队尾的指针相同 则表示该队列为 或该队列 39 一个二维数组 A 15 10 采用行优先方式存储 每个数据元素占用 4 个存储 单元 以该数组第 3 列第 0 行的地址 即 A 3 0 的地址 1000 为首地址 则 A 12 9 的地址为 40 在二维数组 a 10 20 中 每个元素占 8 个存储单元 假定该数组的首地址为 2000 则数组元素 a 6 15 的字节地址为 41 有一个 8 8 的下三角矩阵 A 若将其进行顺序存储于一维数组 a N 中 则 N 的值为 42 有一个 10 10 的下三角矩阵 A 若将 其进行顺序存储于一维数组 a N 中 则 Aij 1 i 10 1 j i 存储于 a 中的下标 位置为 43 有一个 8 8 的下三角矩阵 A 若将其 进行顺序存储 每个元素占用 4 个字节 则 A5 4元素的相对字节地址为 相对首元 素地址而言 44 一种数据结构的元素集合 K 和它的二元 关系 R 为 K a b c d e f g h R 则该数据结构具有 结构 45 对于一棵具有 n 个结点的树 则该树中所有结点的度数之和为 46 在一棵树中 结点没有前驱结点 其余每个结点有并且只有一个 可以有人以多个 结点 47 如图 1 3 所示为一棵树 该树的叶子结点数为 个 单支结点数为 个 双分支结点数为 个 三分支结点数为 个 48 如图 1 3 所示的一棵树 结点 K 的所有祖先的 结点数为 个 结点 B 的所有子孙结点数为 个 49 如图 1 3 所示的一棵树 结点 D 和 X 的层数 分别为 和 50 如图 1 4 所示的一棵树 则树中所含的结点数 为 个 树的深度为 树的度为 51 如图 1 4 所示的一棵树 则度为 3 2 1 0 的结点数分别为 A BI CD GJK EFHXY 图 1 3 A B CD H EGI 图 1 4 F J 13 52 如图 1 4 所示一棵树 则结点 H 的双亲为 孩子结点为 53 在一棵二叉树中 假定双分支结点数为 5 个 单分支结点数为 6 个 则叶子 结点数为 54 对于一棵二叉树 若一个结点的编号 i 若它的左孩子结点存在 则其编号 为 若右孩子结点存在 则其编号为 若双亲结点存在 则其编号为 55 在一棵二叉树中 第 5 层上的结点数最多为 56 假定一棵二叉树的结点数为 18 则它的最小深度 为 最大深度为 57 如图 1 5 所示为一棵二叉树 则 E 结点的双亲结 点数为 左孩子结点为 右孩子结点为 58 如图 1 5 所示为一棵二叉树 它含有双支结点 个 单分支结点 个 叶子结点 个 59 假定一棵二叉树顺序存储在一维数组 a 中 若 a 5 元素的左孩子存在则对应 的元素为 若右孩子存在则对应的元素为 双亲元素为 60 若对一棵二叉树从 0 开始进行结点编号 并按此编 号把它存储到一维数组 a 中 即编号为 0 的结点存储 到 a 0 中 依次类推 则 a i 元素的左孩子为 右孩子为 双亲元素 i 0 为 61 对于一棵具有 n 个结点的二叉树 对应 二叉链 表中指针总数为 个 其中 个用于指向孩子结 点 个指针空闲 62 在一棵深度为 h 的完全平衡二叉树中 最少含有 个结点 最多含有 个结点 63 一棵深度为 5 的完全二叉树中的结点数最 少为 个 最多为 个 64 如图 1 6 所示为一棵二叉树 对它进行先 序遍历结果为 65 若将如图 1 7 所示为一棵树转换为二叉树 该二叉树中双支结点的个数为 个 单支 结点的个数为 个 叶子结点个数为 66 一棵树转换为二叉树后如图 1 8 所示 则原树中 分支结点数为 叶子结点数为 67 一个树林转换成二叉树后如图 1 9 所示 则该素 林中包含 棵树 68 若由 3 6 8 12 10 作为叶子结点的值生成一 A B C D E F 图 1 5 G A B C F D E 图 1 6 A B CI F G 图 1 7 DE H A B C G 图 1 8 D F EHI 14 棵哈夫曼树 则该树的深度为 带权路径长度为 69 一种数据结构的元素集合 K 和它的二元关系 R 为 K 1 2 3 4 5 6 R 1 2 2 3 2 4 3 4 3 5 3 6 4 5 4 6 则该数据结构具有 数据结构 70 在一个图中 所有顶点的度数之和等于所有边数的 倍 71 在一个具有 n 个顶点的无向完全图中 包含有 条 边 在一个具有 n 个顶点的有向完全图中 包含有 条边 72 已知一个连通图的边集为 1 2 1 3 1 4 2 3 2 5 3 5 4 5 则度为 3 的顶点 的个数有 个 73 假定一个有向图的顶点的集为 a b c d e f 边集 则出度为 0 的顶点个数为 入度为 1 的顶点个数为 74 在一个具有 n 个顶点的无向图中 要连通所有顶点则至少需要 条边 75 表示图的两种存储结构为 和 76 在一个连通图中存在着 个连通分量 77 若一个图的顶点集为 a b c d e f 边集为 a b a c b c d e 则 该图含有 个连通分量 78 若一个图的边集为 则从顶点 V0到顶点 V4共有 条简单路径 79 如图 1 10 所示为一个带权有向图 从顶点 V0到顶 点 V4的最短路径长度为 80 对于一个具有 n 个顶点的图 若采用邻接矩阵表示 则矩阵大小至少为 81 对于一个具有 n 个顶点和 e 条边的有向图和无向图 在其对应的邻接表中 所含边结点的个数分别为 和 82 在有向图的邻接表和逆邻接表表示中 每个顶点邻接表分别链接着该顶点的 所有 和 83 有一个图的边集为 a c a e b e c d d e 从顶点 a 出发进 行深度优先搜索遍历得到的顶点序列为 从顶点 a 出发进行广度优先 搜索遍历得到的顶点序列为 84 一个图的边集为 a c a e c f d c e b e d 从顶点 a 出发 出发进行深度优先搜索遍历得到的顶点序列为 从顶点 a 出发进行广 度优先搜索遍历得到的顶点序列为 85 图的 优先搜索遍历算法是一种递归算法 图的 优先搜索遍历算法需 要使用队列 86 若一个连通图中每个边上的权值均不同 则得到的最小生成树是 唯一 不唯一 87 以顺序查找方法从长度为 n 的顺序表或单链表中查找一个元素时 平均查找 A B CE 图 1 9 D G IH F 43 2 A 1 6 2 4 10 5 5 图 1 10 15 长度为 88 对长度为 n 的查找表进行查找时 假定查找第 i 个元素的概率为 P 查找长 度 即在查找过程中依次同有关元素比较的总次数 为 C 则在查找成功的情 况下的平均查找长度的计算公式为 89 假定一个顺序表的长度为 40 并假定查找每个元素的概率都相同 则在查找 成功的情况下的平均查找长度 则在查找不成功的情况下的平均查找长度 90 以折半查找方法从长度为 n 的有序表中查找一个元素时 平均查找长度约等 于 减一 91 以折半查找方法从长度为 50 的有序表中查找一个元素时 其查找长度不超 过 92 从有序表 12 18 30 43 56 78 82 95 中分别折半查找 43 和 56 元 素时 其查找长度分别为 和 93 假定对长度 n 50 的有序表进行折半查找 则对应的判定树深度为 最 后一层的结点数为 94 在分块查找中 假定查找表 即主表 的长度为 96 被等分为 8 个子表 则 进行分块查找的平均查找长度为 95 假定对长度为 n 的有序表进行分块查找 并假定每个子表的长度为 则n 进行分块查找的平均查找长度为 96 在一棵二叉树排序中 每个分支结点的左子树上所有结点的值一定 该结 点的值 右子树上所有结点的值一定 该结点的值 97 从一棵二叉排序树中查找某个元素时 若元素的值等于根结点的值 则表明 若元素的值小于根结点的值 则继续向 查找 若元素的值大于根结 点的值 则继续向 查找 98 向一棵二叉排序树种插入一个元素时 若元素的值小于根结点的值 则接着 向根结点的 插入 若元素的值大于根结点的值 则接着向根结点的 插 入 99 在一棵平衡二叉排序树中 每个结点的左子树深度与右子树深度之差的绝对 值不超过 100 假定对线性表 38 25 74 52 48 进行散列存储 采用 H K K 7 作为哈希函数 采用线性探测再散列法处理冲突 则在建立哈希表过程中 将 会碰到 次冲突 101 假定对线性表 38 25 74 52 48 进行散列存储 采用 H K K 7 作为哈希函数 采用线性探测再散列法处理冲突 则平均查找长度为 102 在线性表的散列存储中 装填因子 a 又称装填系数 若用 m 表示散列表的 长度 n 表示散列存储的元素个数 则 a 等于 103 对线性表 18 25 63 50 42 32 90 进行散列存储时 若选用 H K K 9 作为哈希函数 则散列地址为 0 的元素有 个 则散列地址为 5 的元素有 个 104 每次从无序子表中取出一个元素 把它插入到有序子表的适当位置 此种 排序方法叫做 排序 每次从无序子表中挑选出一个最小或最大元素 把它 交换到有序表的一段 此种排序方法叫做 排序 105 若对一组记录 46 79 56 38 40 80 35 50 74 进行直接插入排 16 序 当把第 8 个记录插入到前面已排序的有序表时 为寻找插入位置需比较 次 106 排序方法能够每次使无序表中的第一个记录插入到有序表中 107 对 n 个记录进行冒泡排序时 最少的比较次数为 最少的趟数为 108 假定一组记录为 46 79 56 38 40 84 在冒泡排序过程中进行第一 趟排序后的结果为 109 假定一组记录为 46 79 56 64 38 40 84 43 在冒泡排序过程中 进行第一趟排序时 元素 97 将最终下沉到其后第 位置 110 排序方法使键值达的记录逐渐下沉 使键值小的记录逐渐上浮 111 假定一组记录为 46 79 56 38 40 80 对其进行快速排序的过程中 共需要 趟 112 假定一组记录为 46 79 56 25 76 38 40 80 对其进行快速排序 的第一次划分后 右区间内元素个数为 113 假定一组记录为 46 79 56 38 40 80 对其进行快速排序的第一次 划分后的结果为 114 在所有排序方法中 排序方法采用的是折半查找法的思想 115 在简单选择排序中 记录比较次数的时间复杂度为 记录移动次数的 时间复杂度为 116 若对一组记录 46 79 56 38 40 80 35 50 74 进行简单选择排 序 用 k 表示最小值元素的下标 进行第一趟是可得初值为 1 则在第一趟选 择最小值的过程中 k 的值被修改 次 117 在时间复杂度为 O n2 的所有排序方法中 排序方法使不稳定的 118 假定一个堆为 38 40 56 79 46 84 则利用堆排序方法进行第一趟 交换和对根结点筛运算后得到的结果为 119 在所有排序方法中 方法使数据的组织采用的是完全二叉树的结构 120 排序方法能够每次从无序表中查找出一个最小值 三 名词解释三 名词解释 1 数据 2 数据元素 3 数据对象 4 数据结构 5 逻辑结构 6 时间复杂度 7 空间复杂度 8 栈 9 队列 10 压缩存储 11 树形结构 12 结点的度 13 树的度 14 树的深度 15 有序树 16 遍历 17 哈夫曼树 18 邻接关系 19 路径 20 连通图 21 强连通图 22 完全无向图 23 完全有向图 24 主关键字 四 简答题四 简答题 1 简述线性结构 树形结构 网状结构的不同 2 简述算法复杂度的评价方法 3 设有两个算法在同一台机器上运行 其执行时间分别为 100n2和 2n 要使前者 快于后者 n 至少为多大 4 在顺序表中插入和删除一个结点需平均移动多少个结点 具体移动的次数取 决于哪些因素 17 5 简述定义 线性表 单链表 线性表的存储方式 循环链表 双向链表 6 在单链表 双向链表和单循环链表中 若仅知道指针 p 指向某结点 不知道 头指针 能否将 p 从相应的链表中删去 若可以 其时间复杂度分别为多少 7 有哪些链表可仅有一个尾指针来唯一确定 即从尾指针出发能访问到链表上 任何一个结点 8 何时选用顺序表 何时选用链表作为线性表的存储结构 9 简述栈与队列的不同之处 10 设将整数 1 2 3 4 依次进栈 但只要出栈时栈非空 则可将出栈操作按 任何次序压入其中 请回答下述问题 1 若入 出栈次序为 Push 1 Pop Push 2 Push 3 Pop Pop Push 4 Pop 则出栈的数字序列如何 2 能否得到出栈序列 1423 和 1432 并说明为什么不能得到或者如何得到 3 请分析 1 2 3 4 的各种排列中 哪些序列是可以通过相应的入 出栈 操作得到的 11 举例说明栈的 上溢 和 下溢 现象 12 循环队列的优点是什么 如何判别它的空和满 13 假定用一维数组 a 7 顺序存储一个循环队列 队首和队尾指针分别用 front 和 rear 表示 当前队列中有 5 个元素 23 45 67 80 34 其中 23 为队首元 素 front 的值为 3 请画出对应的存储状态 当连 续进行 4 次出队运算后 再让 15 36 48 元素依次 进队 请再次画出对应的存储状态 14 空串和空格串有何区别 字符串中空格符有何意 义 空串在串的处理中有何作用 15 两个字符串相等的充要条件是什么 16 二叉树和树之间有何区别 一棵度为 2 的树与二 叉树有何区别 17 在一棵二叉树如图 1 11 所示 写出对此树进行 先序 中序 后序遍历时得到的结点序列 18 已知一棵二叉树的中序遍历序列为 CDBAEGF 先序遍历序列为 ABCDEFG 试问能 不能唯一确定一棵二叉树 若能 画出该二叉 树 若给定先序遍历序列和后序遍历序列 能 否唯一确定 19 将图 1 12 所示的树转换成二叉树 20 一棵度为 2 的有序树与一棵二叉树有何区别 21 试分别画出具有 3 个结点的树和 3 个结点的 二叉树的所有不同形态 22 高度为 h 的完全二叉树至少有多少个结点 至多有多少个结点 23 试采用顺序存储方法和链式存储方法分别画 A B D 图 1 11 C F E A B E 图 1 12 D C FG H L M 1 2 图 1 13 1 33 4 2 4 18 出如图 1 13 所示各二叉树的存储结构 24 假定用于通信的电文由 8 个字母组成 分别是 A B C D E F G 和 H 各字母在电文中出现的概率为 5 25 4 7 9 12 30 8 试为 8 个字母设计哈夫曼编码 25 根据如图 1 14 所示的带 权有向图 G 试回答下面问 题 1 给出从结 点 V1出发按深 度优先搜索遍 历 G 所得的结 点序列 并给出按广度优先搜索遍历 G 所得的结点序列 2 给出从结点 V1到结点 V8的最短路径 26 对于如图 1 15 所示的有向图 请给出 1 对应的邻接矩阵 并给出 A B C 三个顶点的出度与入度 2 邻接表表示和逆邻接表表示 3 强连通分量 27 假设图的顶点是 A B C D 请根据下述邻接矩阵画出相应的有向图和 无向图 1 0 1 1 1 2 0 1 1 0 0 1 0 1 1 0 0 0 1 0 1 1 0 1 1 0 0 0 1 1 1 1 0 0 1 0 1 0 28 对 n 个顶点的无向图和有向图 采用邻接矩阵和邻接表表示时 如何判别下 列有关问题 1 图中有多少条边 2 任意两个顶点 i 和 j 是否有边相连 3 任意一个顶点的度是多少 29 试述顺序查找法 折半查找法和分块查找法对查找表中元素的要求 30 若有一个长度为 n 的表 其查找该表中每个元素的概率相同 采用顺序查找 折半查找和分块查找 3 种查找方法进行查找时的其平均查找长度各为多少 31 设有一组关键字 17 13 14 153 29 35 需插入到表长为 12 的散列表 中 请回答下列问题 1 设计一个适合该散列表的哈希函数 2 用设计的哈希函数将上述关键字插入到散列表中 画出其结构 并指出用 线性探测再散列法解决冲突时构造散列表的装填因子为多少 32 选择排序算法是否稳定 为什么 33 给出一组关键字 19 01 26 92 87 11 43 87 21 进行冒泡排序 2 3 1A5 43 1 46 4 图 1 14 67 8 6 50 1 12 24 20 8 38 12 AD E F B C 图 1 15 19 列出每一遍排序后关键字的排列次序 并统计每遍排序进行的关键