专升本数据结构

专升本《数据结构》一、（共75题，共150分）数据的基本单位是（）。（2分）数据元素 B.记录 C.数据对象 D.数据项.标准答案：A（）是数据的不可分割的最小单位。（2分）A.数据对象.标准答案：DB.数据元素C.数据类型D.数据项3.算法的空间复杂度是对算法（）的度量。 （2分）A.时间效率B.空间效率C.可读性D.健壮性.标准答案：B4.（）是限制了数据元素的内部结构仅为一个字符的线性表。（2分）A.栈.标准答案：BB.队列C.串D.数组5.串的长度是指串中所含（）的个数。 （2分）A.不同字符B.不同字母C.相同字符D.所有字符.标准答案：D6.采用带头结点双向链表存储的线性表,在删除一个元素时,需要修改指针（）次。（2分）A.1B.2C.3D.4.标准答案：B7.线性表的顺序存储结构是一种（）的存储结构。（2分）A.顺序存取B.随机存取C.索引存取存取.标准答案：B

数组a[1]采用顺序存储，a[1]和a[m]地址分别为1024和1150,每个元素占2字节，则m是（）。 （2分）TOC\o"1-5"\h\z\o"CurrentDocument"64 B.32 C.16 D.8.标准答案：A深度为h的二叉树,第h层最多有（）个结点。（2分）2121 D.2h.标准答案：Cm个结点的二叉树，其对应的二叉链表共有（）个非空链域。 （2分）\o"CurrentDocument"1 C.2m 1.标准答案：B下面叙述错误的是（）。 （2分）顺序表是借助物理单元相邻表示数据元素之间的逻辑关系对于空队列进行出队操作过程中发生下溢现象有向图的邻接矩阵一定是对称的具有相同的叶子个数和具有相同的叶子权值的赫夫曼树不是唯一的.标准答案：C以下与数据的存储结构无关的术语是（）。（2分）A.循环队列 B.双向链表 C.哈希表 D.数组.标准答案：D在一个长度为n的链式栈中出栈实现算法的时间复杂度为（）。（2分）TOC\o"1-5"\h\z\o"CurrentDocument"（1） （n）（n） （n2）.标准答案：A在具有k个度数为2的二叉树中,必有（）个叶子结点。 （2分）\o"CurrentDocument"-1 C.2k 1.标准答案：D15.在关键字序列(10,20,30,40,50)中，采用折半法查找20,关键字之间比较需要()次。(2分)1 B.2 C.3 D.4.标准答案：C16某二叉树的后序遍历序列和和中序遍历序列均为，该二叉树的前序遍历序列是()o(2分).标准答案：Bn个顶点的无向连通图的生成树，至少有()个边。(2分)(1) (1)/2C.2n1.标准答案：D可以采用()这种数据结构，实现二叉树的层次遍历运算。 (2分)A.队列 B树 C.栈 D.集合.标准答案：A假设以数组A[01]存放循环队列的元素，其头指针指向队头元素、尾指旨向队尾元素一个，则在少用一个元素空间的前提下，队列空的判定条件为()o(2分)⑴％1= D.⑴％.标准答案：A经冒泡須E序法由到大須E序，第一趟B.(19,21,5,2,37)D.经冒泡須E序法由到大須E序，第一趟B.(19,21,5,2,37)D.(19,21,2,5,37)(19,21,37,5,2)(19,21,5,37,2).标准答案：B21.二叉链表适合作为()的存储结构。(2分)D.森林A.队列 B.二叉树 C.D.森林.标准答案:22.设哈希（）函数为H（k）二k%17,其中k为关键字，关键字（）是同义词。（2分）A.44,5,15 B.2&45,62C.6,57,125D.201,31,48.标准答案:TOC\o"1-5"\h\z23.下列各项键值（）序列不是堆的。 （2分）A.{94,68,23,16,5 B.{94,23,68,5,16C.{94,23,16,68,5 D.{94,16,68,23,5.标准答案:24.在下列排序方法中，（）的空间复杂度为O（n）。其中，n为参加須E序的元素个数。 （2分）A.选择須E序 B.快速須E序 C.归并須E序 D.冒泡須E序.标准答案:25.十字链表适合于（）选作存储结构。 （2分）A.队列C.边或弧数较少的图.标准答案:B.稀疏矩阵D.二叉树26.基于数据的逻辑关系，数据的逻辑结构划分为（）基本结构。（2分）A.6类 B5类C.4类D.3类.标准答案：CTOC\o"1-5"\h\z（）不是算法具有的5个特性之一。 （2分）A.有穷性 B.确定性 C.可行性 D.正确性.标准答案：D（2分）（2分）D.健壮性时间效率 B.空间效率 C.可读"生线性表若采用链式存储结构时，要求结点的存储单元地址（）。（2分）必须是连续的 B.部分地址必须是连续的C.必须是不连续的 D.连续或不连续都可以.标准答案：D二维数组通常采用顺序存储，其优点是（）。（2分）便于增加存储空间 B.防止下标溢出C.避免数据元素的移动 D.便于依据下标进行随机存取.标准答案：D采用顺序存储的线性表，若表长为n在第i号元素之后插一一个元素时，需要移动（）个元素。（2分）11.标准答案：C若已知一个栈的入栈序列是1、2、3、4，其出栈序列不可能为。（2分）A.1、4、3、2 B.3、4、1、2 C.4、3、2、1 D.2、3、4、1.标准答案：B数组a[1..256]采用顺序存储，a的首地址为10,每个元素占2字TOC\o"1-5"\h\z节，贝Ua[21]的地址是（）。 （2分）A.10 B.30 C.50 D.70.标准答案：C深度为h的完全二叉树至少有（）个叶子结点。 （2分）A.2（1）+1 B.2（2）+1C.21 D.22.标准答案：D若二叉树对应的二叉链表共有m个非空链域，则该二叉树有（）个结点的二叉树。（2分）-1 C1 D.2m.标准答案：B下面叙述错误的是（）。（2分）A.单链表是借助指针表示数据元素之间的逻辑关系在顺序栈的入栈操作过程中可能发生上溢现象具有相同的叶子个数和具有相同的叶子权值的赫夫曼树是唯一的无向图的邻接矩阵一定是对称的.标准答案：C以下（）术语与数据的存储结构无关（2分）A.栈 B.哈希表 C.线索树 D.双向链表.标准答案：A在一个长度为n的链式队列中入队实现算法的时间复杂度为TOC\o"1-5"\h\z（）。 （2分）（1） （n）（n） （n2）.标准答案：A队列的出队操作是指（）操作。 （2分）A.队尾删除 B.队头删除 C.队尾插入 D.队头插入.标准答案：B在关键字序列（10,15,20,25,30）中采用折半法查找25,依次与（）关键字进行了比较。 （2分）A.30,25 B.20,25 C.20,30,25 D.25.标准答案：B16某二叉树的前序遍历序列和和中序遍历序列分别为和,该二叉树的后序遍历序列是（）。（2分）.标准答案：A所占用的存储空间大小仅与图的顶点个数相关的存储结构是（）。 （2分）A.邻接表 B.逆邻接表C.十字链表 D.邻接矩阵.标准答案：D可以采用（）这种数据结构，实现图的深度优先遍历运算。 （2分）A.队列 B树 C.栈 D.集合.标准答案：C为扌旨针，则判断表空的条*线性表采用带头结点单链表实现,为（）O（2分）为扌旨针，则判断表空的条*.标准答案:C45.在关键字序列45.在关键字序列（35,10,15,20,25）中采用最低位优先排序（）基数須E序，第一趟之后所得结果为（）o（2分）A.10,20,15,25,35A.10,20,15,25,35C.20,10,35,25,1510,20,35,15,2520,10,35,15,2546.下列逻辑结构中，（）46.下列逻辑结构中，（）为线性结构。 （2分）A.栈B.队列C.串.标准答案:D.二叉树47.深度为3的二二叉树可能的结点个数是（）。（2分）A.1B.2C.3D.4.标准答案:TOC\o"1-5"\h\z下列各项键值（）序列是大顶堆的。 （2分）\o"CurrentDocument"A.{23, 68,94,16, 5 B.{94, 68,23,16, 5\o"CurrentDocument"{94, 23,68,16, 5 D.{94, 16,68,23, 5.标准答案:下列（）是限制了插入和删除操作的特殊线性表。 （2分）A.栈 A.栈 B.队列 C.串D.数组.标准答案:对一棵二叉須E序树，用（）方法进行遍历，不_定得到各结点键值的有序序列。 （2分）A.先根遍历.标准答案:B.中根遍历C.后根遍历D.层次遍历51.数据的最小单位是（）o（2分）D.数据项A.数据元素 B.记录 C.D.数据项.标准答案：D52.算法是对某一类问题求解步骤的有限序列。其中,有的5个特性之,一。（2分）A.有穷性B.正确性C.可读性.标准答案：A（）是算法具D.健壮性TOC\o"1-5"\h\z（）是数据的逻辑结构。 （2分）D.十字链表A.顺序表 B.链表 C.D.十字链表（）是限制了插入和删除操作在一端进行的线性表。 （2分）A.栈 B.队列 C.串 D.数组.标准答案：A（）是限制了插入和删除操作分别在两端进行的线性表。 （2分）A.栈 B.队列 C.串 D.数组.标准答案：B用链表表示线性表的优点是（）。 （2分）便于插入和删除便于随机存取花费的存储空间较川页序存储少数据元素的物理川页序与逻辑川页序相同.标准答案：A若已知一个栈的入栈序列是1、2、3、4,其出栈序列不可能为0o（2分）A.1、4、3、2 B2、3、4、1C.4、3、2、1D.3、4、1、2.标准答案：D串下列关于串的叙述中，正确的是（）。 （2分）2个串的长度相等，则2个串相等空串至少包一个空格替换操作可以实现字苻的删除_个串的长度至少是1.标准答案：C深度为h的二叉树，第h层至少有（）个结点。 （2分）A.0 B.1 C.8 D.16.标准答案：B假设n>0,在程序段{0（（1）^（1）B.:]2.标准答案：C下面叙述错误的是（）。 （2分）在集合{1,2,3,4,5中元素1是2的直接前驱二叉須E序树的中序遍历序列一定是有序的有3个结点的不同形态二叉树的数目为5哈夫曼树中所有结点的孩子数目只可能为2或者为0.标准答案：ATOC\o"1-5"\h\z以下数据结构中，（）是线性结构。 （2分）A.广义表 B.二叉树 C.稀疏矩阵 D.串.标准答案：D在一个长度为n的川页序表中删除一个元素的算法的时间复杂度为0o（2分）⑴ （n）(n2)如果一个树含有n个叶子，则该树必有（）的结点。 （2分）1 B.21 C.2n21.标准答案：D在关键字序列（10,15,20,25,30）中，采用折半法查找25,关键字之间比较需要（）次。（2分）A.1 B.2 C.34.标准答案：B16某二叉树的前序遍历序列和和中序遍历序列均为，该二叉树的后序遍历序列是（）o（2分）.标准答案：Bm个顶点的有向完全图有（）个弧。（2分）（1）/21（1）.标准答案：D下列各项键值（）序列不是堆的。 （2分）A.{94,68,16C.{94,23,5.标准答案:23, 16, 5 B.{94,23, 68, 5,68, 16, 5 D.{94,16, 68, 23,D69.设单链表中指针p指向结点A,q指向新元素结点，若要A之后插>一个新元素，则所需修改指针的操作为（）o（2分）>,»»,>»,>>,».标准答案：B70.在关键字序列70.在关键字序列(149,138,165,197,176,113,低位优先須E序（）基数須E序，第一趟之后所得结果为（）A.149,138,165,197,176,113,127B.128,149,165,197,113,176,127C.128,149,165,197,113,127,176D.113,127,138,149,165,176,197.标准答案:B127）中采用最□ （2分）71.下列术语表示的数据中，（）是同义语。（2分）A.结点 B.数据元素 C.顶点 D.数据项.标准答案