计算机应用基础数据结构部分试题及答案.pdf

计算机应用基础数据结构部分试题及答案 1 选择题 1 下面程序段的时间复杂度的量级为 for i 1 i n i for j 1 j i j for k 1 k j k x x 1 A O 1 B O n C O n2 D O n3 2 在数据结构中 从逻辑上可以把数据结构分成 A 动态结构和静态结构 B 紧凑结构和非紧凑结构 C 线性结构和非线性结构 D 内部结构和外部结构 3 数据结构的 包括集合 线性 树形和图形结构四种基本类型 A 存储结构 B 逻辑结构 C 基本运算 D 算法描述 4 数据的 包括查找 插入 删除 更新和排序等 A 存储结构 B 逻辑结构 C 基本运算 D 算法描述 5 数据的存储结构包括顺序 链接 散列和 四种基本类型 A 线性 B 数组 C 集合 D 索引 6 下面 的时间复杂性最好 即执行时间最短 A O n B O logn C O nlogn D O n2 7 下面程序段的时间复杂性的量级为 for int i 0 i m i for int j 0 jnext p next next B p p next C p p next next D next p 27 设单链表中指针p指向结点ai 指针f指向将要插入的新结点 x 则当x插在链表中两个 数据元素ai和ai 1之间时 只要先修改 后修改 即可 A p next f B p next p next next C p next f next D f next p next E f next null F f next p 28 设单链表中指针p指向结点ai 指针f指向将要插入的新结点 x 则在链表中最后一个 结点an之后插入时 只要先修改 后修改 即可 A f next p B f next p next C p next f D p next f next E f null 29 在一个单链表中 若要在p所指向的结点之后插入一个新结点 则需要相继修改 个指针域的值 A 1 B 2 C 3 D 4 30 在一个单链表中 若要在p所指向的结点之前插入一个新结点 则此算法的时间复杂 性的量级为 A O n B O n 2 C O 1 D O n1 2 21 25 D B A C B 26 30 A D A B C B A 31 不带头结点的单链表L为空的判定条件是 A L NULL B L next NULL C L next L D L NULL 32 带头结点的单链表L为空的判定条件是 A L NULL B L next NULL C L next L D L NULL 33 在一个带有头结点的双向循环链表中 若要在p所指向的结点之前插入一个新结点 则需要相继修改 个指针域的值 A 2 B 3 C 4 D 6 34 在一个带有头结点的双向循环链表中 若要在p所指向的结点之后插入一个q指针所指 向的结点 则需要对q next赋值为 A p prior B p next C p next next D p prior prior 35 对一个具有n个元素的线性表 建立其单链表的时间复杂度为 A O n B O 1 C O n2 D O logn 36 线性表采用链式存储时 其地址 A 必须是连续的 B 一定是不连续的 C 部分地址必须是连续的 D 连续与否均可以 37 假定利用数组a N 顺序存储一个栈 用top表示栈顶指针 top 1表示栈空 并已 知栈未满 当元素x进栈时所执行的操作为 A a top x B a top x C a top x D a top x 38 若已知一个栈的入栈序列是1 2 3 n 其输出序列为p1 p2 p3 pn 若p1 n 则pi为 A i B n i C n i 1 D 不确定 39 判定一个栈S 最多元素为m0 为空的条件是 A S top 0 B S top 0 C S top m0 D S top m0 40 判定一个栈S 最多元素为m0 为满的条件是 A S top 0 B S top 0 C S top m0 1 D S top m0 1 31 35 A B C B A 36 40 D C C B D 41 一个队列的入队序列是1 2 3 4 则队列的输出序列是 A 4 3 2 1 B 1 2 3 4 C 1 4 3 2 D 3 2 4 1 42 从一个顺序循环队列中删除元素时 首先需要 A 前移队首指针 B 后移队首指针 C 取出队首指针所指位置上的元素 D 取出队尾指针所指位置上的元素 43 假定一个顺序循环队列的队首和队尾指针分别用front和rear表示 则判断队列空的 条件为 A front 1 rear B rear 1 front C front 0 D front rear 44 假定一个顺序循环队列存储于数组a N 中 其队首和队尾指针分别用front和rear表 示 则判断队列满的条件为 A rear 1 N front B rear 1 N front C front 1 N rear D front 1 N rear 45 树中所有结点的度等于所有结点数加 A 0 B 1 C 1 D 2 46 在一棵树中 每个结点最多有 个前驱结点 A 0 B 1 C 2 D 任意多个 47 在一棵度为3的树中 度为3的结点数为2个 度为2的结点数为1个 度为1的结点点数 为2个 则度为0的结点数为 个 A 3 B 4 C 5 D 6 48 在一棵二叉树上第5层的结点数最多为 A 16 B 15 C 8 D 32 49 在一棵具有n个结点的二叉树的第i层上 最多具有 个结点 A 2i B 2i 1 C 2i 1 D 2n 50 一颗具有35个结点的完全二叉树的深度为 A 6 B 7 C 5 D 8 41 45 B B D B C 46 50 B D A C A 51 在一棵完全二叉树中 若编号为i的结点存在右孩子 则右孩子结点的编号为 A 2i B 2i 1 C 2i 1 D 2i 2 52 设高度为h的二叉树上只有度为0和度为2的结点 则此类二叉树中所包含的结点数至 少为 A 2h B 2h 1 C 2h 1 D h 1 53 按照二叉树的定义 具有3个结点的二叉树有 种状态 A 5 B 4 C 3 D 30 54 若查找每个元素的概率相等 则在长度为n的顺序表上查找任意元素的平均查找长度 为 A n B n 1 C n 1 2 D n 1 2 55 顺序查找法适合于存储结构为 的线性表 A 散列存储 B 顺序存储或链接存储 C 压缩存储 D 索引存储 56 对于顺序存储的有序表 5 12 20 26 37 42 46 50 64 若采用折半查 找 则查找元素26的查找长度 A 2 B 3 C 4 D 5 57 对线性表进行折半查找时 要求线性表必须 A 以顺序方式存储 B 以链接方式存储 C 以顺序方式存储 且结点按关键字有序排序 D 以链接方式存储 且结点按关键字有序排序 58 采用折半查找方法查找长度为n的线性表时 每个元素的平均查找长度为 A O n2 B O nlogn C O n D O logn 59 在对n个元素进行直接插入排序的过程中 共需要进行 趟 A n B n 1 C n 1 D 2n 60 对n个元素进行直接插入排序时间复杂度为 A O 1 B O n2 C O n D O nlog2n 51 55 C B A D B 56 60 C C D C B 61 在对n个元素进行快速排序的过程中 最好情况下需要进行 趟 A n B n 2 C logn D 2n 62 在对n个元素进行冒泡排序的过程中 至少需要 趟完成 A 1 B n C n 1 D n 2 63 在对n个元素进行快速排序的过程中 平均情况下的时间复杂度为 A O 1 B O logn C O n2 D O nlogn 64 排序方法中 从未排序序列中依次取出元素与已排序序列 初始时为空 中的元素进 行比较 将其放入已排序序列的正确位置上的方法 称为 A 插入排序 B 起泡排序 C 希尔排序 D 选择排序 65 用某种排序方法对线性表 25 84 21 47 15 27 68 35 20 进行排序时 元 素序列的变化情况如下 1 25 84 21 47 15 27 68 35 20 2 20 15 21 25 47 27 68 35 84 3 15 20 21 25 35 27 47 68 84 4 15 20 21 25 27 35 47 68 84 则采用的排序方法是 A 选择排序 B 希尔排序 C 插入排序 D 快速排序 66 对下列四个序列进行快速排序 各以第一个元素为基准进行第一次划分 则在该次划 分过程中需要移动元素次数最多的序列为 A 1 3 5 7 9 B 5 7 9 1 3 C 5 3 1 7 9 D 9 7 5 3 1 67 若对n个元素进行简单选择排序 则进行任一趟排序的过程中 为寻找最小值元素所 需要的时间复杂度为 A O 1 B O logn C O n D O n2 68 若对n个元素进行堆排序 则在由初始堆进行每趟排序的过程中 共需要进行 次 筛运算 A n 1 B n 2 C n D n 1 69 排序方法中 从未排序序列中挑选元素 并将其依次放入已排序序列 初始时为空 的一段的方法 称为 A 希尔排序 B 起泡排序 C 插入排序 D 选择排序 70 一组记录的关键字为 45 80 55 40 42 85 则利用堆排序的方法建立的初始 堆为 A 80 45 55 40 42 85 B 85 80 55 40 42 45 C 85 80 55 45 42 40 D 85 55 80 42 45 40 61 65 C A D A D 66 70 B C D D B 71 若对n个元素进行直接插入排序 则进行第i趟排序过程前 有序表中的元素个数为 A 1 B i 1 C i D i 1 72 在对n个元素进行冒泡排序的过程中 第一趟至多需要进行 次相邻元素之间的比 较 A n 1 B n 2 C n D n 1 73 若一个元素序列基本有序 则选用 排序较快 A 堆排序 B 快速排序 C 直接插入排序 D 直接选择排序 74 快速排序方法在 情况下最不利于发挥其长处 A 要排序的数据量太大 B 要排序的数据中含有多个相同值 C 要排序的数据已基本有序 D 要排序的数据个数为奇数 75 排序方法中 将整个无序序列分割成若干个小的子序列并分别进行插入排序的方法 称为 A 希尔排序 B 冒泡排序 C 直接插入排序 D 直接选择排序 76 用直接插入排序方法对下列4个表由小到大进行排序 比较次数最少的是 A 94 32 40 90 80 46 21 69 B 21 32 46 40 80 69 90 94 C 32 40 21 46 69 94 90 80 D 90 69 80 46 21 32 94 40 77 一组记录的关键码为 46 79 56 38 40 84 则利用快速排序方法 以第一个 纪录为基准得到的一次划分结果为 A 38 40 46 56 79 84 B 40 38 46 79 56 84 C 40 38 46 56 79 84 D 40 38 46 84 56 79 78 如果对元素序列 7 2 5 8 1 11 进行堆排序 并且采用小根堆 则由初始数 据构成的初始堆为 A 1 2 5 7 8 11 B 1 2 5 8 7 11 C 1 5 2 7 8 11 D 1 5 2 8 11 7 79 如图所示 该二叉树的前序遍历序列是 A EGFACDB B EAGCFBD C EACBDGF D EGACDFB 80 已知某二叉树的后序遍历序列是DACBE 中序序列是DEBAC 则它的前序遍历序列是 A ACBED B DEABC C DECAB D EDBAC 71 75 C D C C A 76 80 B C B C D 81 已知某二叉树的前序遍历序列是ABDEFGC 中序序列是DEBGFAC 则对应的二叉树为 81 85 B 2 填空题 1 数据结构及数据的逻辑结构包括 四种类型 2 数据的存储结构及物理结构包括 四种基本类型 3 数据结构是研究数据的 以及它们之间的相互关系 并对这种结构定义相 应的 设计出相应的 而确保经过这些运算后所得到的新结构是 结构类 型 4 一个算法应具有 这五个特征 5 一个算法的时间复杂度是该算法包含的 的多少 它是一个算法运行时间的相对 度量 一个算法的空间复杂性是指该算法在运行过程中临时占用的 的大小 6 一个算法的时间复杂性通常用它的 形式表示 当一个算法的时间复杂度与问题 的规模n大小无关时 则表示为 成正比时 则表示为 成对数关系时 则表 示为 成平方时 则表示为 7 是描述客观事物的数 字符以及所有能输入到计算机且被计算机程序加工处理 的符号集合 是数据的基本单位 有时这个单位由若干个 组成 在这种情况 下 又称它为记录 是数据的最小单位 而由记录组成的线性表为 8 一种数据结构的元素集合K和他的二元关系R为 K a b c d e f g h R 该数据结构具有 结构 9 一种数据结构的元素集合K和他的二元关系R为 K a b c d e f g h R 该数据结构具有 结构 10 一种数据结构的元素集合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 该数据结构具有 结构 1 集合 线性结构 树型结构 图形结构 网状结构 2 顺序存储 链式存储 散列 索引 3 物理结构 逻辑结构 二者顺序可颠倒 运算 算法 原来的 4 有穷性 确定性 可行性 输入性 输出性 5 语句执行次数 存储空间 6 数量级 O 1 O n O logn O n2 7 数据 数据元素 数据项 数据项 文件 8 线性结构 9 树型结构 10 图形结构 网状结构 11 若经常需要对线性表进行插入和删除运算 则最好采用 存储结构 若经常需要 对线性表进行查找运算 则最好采用 存储结构 12 访问一个线性表中具有给定值元素的时间复杂性的量级为 13 对于一个长度为n的顺序表 在表头插入元素的时间复杂性为 在表尾插入元 素的时间复杂性为 14 在一个单链表中指针p所指向结点的后面插入一个指针q所指向的结点时 首先把 的值赋给q next 然后把 的值赋给p next 15 在一个单链表中的p所指向结点之前插入一个指针s所指向的结点时 可执行如下操 作 1 s next 2 p next s 3 t p data 4 p data 5 s data 16 假定指向单链表中第一个结点的表头指针为head 则向该单链表的表头插入指针p所 指向的新结点时 首先执行 赋值操作 然后执行 赋值操作 17 在一个单链表中删除指针p所指向结点的后继结点时 需要把 的值赋给 p next指针域 18 在一个单链表中删除指针p所指向结点时 应执行一下操作 q p next p data p next data p next free q 19 在 链表中 既可以通过设定一个头指针也可以通过设定一个尾指针来确定它 即通过头指针或尾指针可以访问到该链表中的每个结点 20 在一个带有头结点的双向循环链表中的p所指向的结点之前插入一个指针s所指向结点 时 可执行如下操作 1 s data element 2 s prior 3 p prior next s 4 s next 5 p prior 11 链式 顺序 12 O n 13 O n O 1 14 p next q 15 p next s data t 16 p next head head p 17 p next next 18 p next next 19 循环 20 p prior p s 21 在一个双向链表中指针p所指向结点之前插入一个新结点时 其时间复杂性的量级为 22 线性表的长度是指 23 在线性表的顺序存储中 元素之间的逻辑关系是通过 决定的 在线性表的链 式存储中 元素之间的逻辑关系是通过 决定的 24 根据线性表的链式存储结构中每个结点所含指针的个数 链表可分为 和 25 线性表 栈和队列都是 结构 对于栈只能在 插入和删除元素 对于队 列只能在 插入元素 在 删除元素 26 设有一空栈 现有输入序列1 2 3 4 5 经过push push pop push pop push push后 对应的输出序列是 27 设元素1 2 3 4 5依次进栈 若要在输出端得到序列34251 则应进行的操作序列 为push S 1 push S 2 pop S push S 4 pop S pop S pop S 28 在一个具有n个存储单元的循环队列中 当队列满时共有 个元素 29 有一棵树如图所示 回答下列问题 1 这棵树的根结点是 2 这棵树的叶子结点是 3 结点C的度是 这棵树的度是 4 结点C的子女是 5 结点C的父结点是 30 对于一个具有n个结点的二叉树 它可能具有的最小深度为 具有的最大深度 为 21 O 1 22 线性表中包含数据元素的个数 23 物理存储地址 指针的值 24 单链表 双链表 25 线性 栈顶 队尾 队头 26 2 3 27 push S 3 pop S push S 5 28 n 1 29 1 A 2 B E G D 3 2 3 4 E F 5 A 30 log2n 1 n 31 一棵深度为k的满二叉树的结点总数为 一棵深度为k的完全二叉树的结点总数 的最小值为 最大值 32 由a b c三个结点构成的二叉树 共有 种不同的结构 33 对于一棵具有n个结点的树 该树中所有结点的度数之和为 34 在一棵二叉树中 假定度为2的结点数为5个 度为1的结点数为6个 则叶子结点数 为 个 35 假定一棵二叉树顺序存储在一维数组a中 但让编号为1的结点存入a 0 元素中 让 编号为2的结点存入a 1 元素中 其余类推 则编号为i结点的左孩子结点对应的数组下标 为 右孩子对应下标为 36 一棵n个结点的完全二叉树从根结点这一层开始 每一层上的结点按从左到右的顺序 存储于数组A 1 n 中 设某个结点在数组中的位置为i 1 i n 则其父结点的位 置是 37 设二叉树的深度为h 且只有度为0和2的结点 则此二叉树中所含结点数最多为 38 假定一组记录为 46 79 56 38 40 84 在冒泡排序的过程中进行第一趟排序后的 结果为 39 假定一组记录为 46 79 56 38 40 80 对其进行快速排序的过程中 共需要 趟排序 40 假定一组记录为 46 79 56 38 40 80 对其进行快速排序 则第一次划分后的结 果为 31 2k 1 2k 1 2k 1 32 5 33 n 1 34 6 35 2i 1 2i 36 i 2 取整数部分 37 2h 1 3