专升本《数据结构》试卷答案

1、专升本数据结构-试卷-答案hC2h-iD.2hB2hD.2hB2h-1专升本数据结构一、（共75题洪150分）1.数据的基本单位是（）。（2分）A数据元素B记录C数据对象D数据项标准答案：A2（）是数据的不可分割的最小单位。（2分）A数据对象B数据元素C数据类型D数据项标准答案：D3算法的空间复杂度是对算法（）的度量。（2分）A时间效率B空间效率C可读性D健壮性标准答案：B4（）是限制了数据元素的内部结构仅为一个字符的线性表。（2分）A栈B.队列C串D数组标准答案：B5串的长度是指串中所含（）的个数。（2分）A不同字符B不同字母C相同字符D所有字符标准答案：D6采用带头结点双向链表存储的线性表

2、，在删除一个元素时，需要修改指针（）次。 （2分）A1B2C3D4标准答案：B7线性表的顺序存储结构是一种（）的存储结构。（2分）A顺序存取B随机存取C索引存取DHash存取标准答案：B8数组a1m采用顺序存储，a1和am地址分别为1024和1150,每个元素占2字节，则m是（）。（2分）A64B32C16D.8标准答案：A9深度为h的二叉树，第h层最多有（）个结点。（2分）10m个结点的二叉树，其对应的二叉链表共有（）个非空链域。（2分）AmBm+1C2mDm-1标准答案：B11下面叙述错误的是（）。（2分）A顺序表是借助物理单元相邻表示数据元素之间的逻辑关系B.对于空队列进行出队操作过程中

3、发生下溢现象C有向图的邻接矩阵一定是对称的D具有相同的叶子个数和具有相同的叶子权值的赫夫曼树不是唯一的标准答案：C12以下与数据的存储结构无关的术语是（）。（2分）A循环队列B双向链表C哈希表D数组标准答案：D13在一个长度为n的链式栈中出栈实现算法的时间复杂度为（）。（2分）AO（1）BO（log n）CO（n）DO（n2）标准答案：A14在具有k个度数为2的二叉树中，必有（）个叶子结点。（2分）AkBk-1C2kDk+1标准答案：D15在关键字序列（10200,40,50）中，采用折半法查找20,关键字之间比较需要 （）次。（2分）A1B2C3D4标准答案：C1616某二叉树的后序遍历序列

4、和和中序遍历序列均为abed，该二叉树的前序遍历 序列是（）。（2分）AabcdBdcbaCacbdDdbea标准答案：B17n个顶点的无向连通图的生成树，至少有（）个边。（2分）An（n-1）Bn（n-1）/2 C2n Dn-1标准答案：D18.可以采用（）这种数据结构，实现二叉树的层次遍历运算。（2分）A.队列B树C栈D集合标准答案：A假设以数组A 0n-1存放循环队列的元素，其头指针front指向队头元素、 尾指针rear指向队尾元素一个，则在少用一个元素空间的前提下，队列空的判定条 件为（）。（2分）A.rear= =frontB.（front+1） % n= =rearC.rear+

5、1= fontD.（rear+1） % n= =front标准答案：A序列（21，19, 37, 5, 2）经冒泡排序法由小到大排序，第一趟后所得结果为 （）。（2 分）A.（19,21，37, 5,2）B（19,21，5,2,37）C.（19,21,5, 37,2）D.（19,21,2,5,37）标准答案：B二叉链表适合作为（）的存储结构。（2分）A队列B二叉树C树D森林标准答案：B,CD设哈希（Hash）函数为H（k）= k % 17,其中k为关键字，关键字（）是同义词。（2 分）A.44,5,15B.28,45,62C.6,57,125D.201,31,48标准答案：B,CD下列各项键值

6、（）序列不是堆的。（2分）A94, 68,23,16,5B.94,23, 68,5, 16C.94, 23,16,68,5D.94,16, 68,23, 5标准答案：CD在下列排序方法中，（）的空间复杂度为O（n）。其中，n为参加排序的元素个 数。（2分）A选择排序B快速排序C归并排序D冒泡排序标准答案：B,C十字链表适合于（）选作存储结构。（2分） A队列B稀疏矩阵C边或弧数较少的图D二叉树基于数据的逻辑关系，数据的逻辑结构划分为（）基本结构。（2分）A.6类B.5类C.4类D.3类标准答案：C（）不是算法具有的5个特性之一。（2分）A有穷性B确定性C可行性D正确性标准答案：D算法的时间复杂

7、度是对算法（）的度量。（2分）A.时间效率B空间效率C可读性D健壮性标准答案：A线性表若采用链式存储结构时，要求结点的存储单元地址（）。（2分）A必须是连续的B部分地址必须是连续的C必须是不连续的D连续或不连续都可以标准答案：D二维数组通常采用顺序存储，其优点是（）。（2分）A便于增加存储空间B.防止下标溢出C避免数据元素的移动D便于依据下标进行随机存取标准答案：D采用顺序存储的线性表，若表长为n,在第i号元素之后插入一个元素时，需要 移动（）个元素。（2分）A.i+1B.iC.n-iD.n-i+1标准答案：C若已知一个栈的入栈序列是1、2、3、4,其出栈序列不可能为。 （2分）A.1、4、3

8、、2B3、4、1、2C4、3、2、1D2、3、4、1标准答案：B数组a1256采用顺序存储，a的首地址为10,每个元素占2字节，则a21啲地址是（）。（2分）A.10B.30C.50D.70标准答案：C深度为h的完全二叉树至少有（）个叶子结点。（2分）A.2（h-1）+1B.2（h-2）+14545在关键字序列（35，10, 第一趟之后所得结果为（）。A 10, 20，15, 25, 35C20， 10, 35, 25, 15标准答案：BC2h-1D2h-2标准答案：D若二叉树对应的二叉链表共有m个非空链域，则该二叉树有（）个结点的二叉 树。（2分）A.mB.m-1C.m+1D.2m标准答案：

9、B下面叙述错误的是（）。（2分）A单链表是借助指针表示数据元素之间的逻辑关系B在顺序栈的入栈操作过程中可能发生上溢现象C.具有相同的叶子个数和具有相同的叶子权值的赫夫曼树是唯一的D无向图的邻接矩阵一定是对称的标准答案：C37以下（）术语与数据的存储结构无关（2分）A栈B哈希表C线索树D双向链表标准答案：A在一个长度为n的链式队列中入队实现算法的时间复杂度为（）。（2分）AO（1）B.OQog n）CO（n）D. O（n2）标准答案：A队列的出队操作是指（）操作。（2分）A队尾删除B队头删除C队尾插入D队头插入标准答案：B40在关键字序列（10,15,20,25,30）中采用折半法査找25,依次

10、与（）关键字进行 了比较。（2分）A.3025B.2025C.20, 30，25D.25标准答案：B4116某二叉树的前序遍历序列和和中序遍历序列分别为abed和bead,该二叉树 的后序遍历序列是（）。（2分）AcbdaBdebaCabcdDdeba标准答案：A42所占用的存储空间大小仅与图的顶点个数相关的存储结构是（）。（2分）A邻接表B逆邻接表C十字链表D邻接矩阵43可以采用（）这种数据结构，实现图的深度优先遍历运算。（2分）A队列B树C栈D集合标准答案：C44线性表采用带头结点单链表实现，head为头指针，则判断表空的条件为（）。 （2分）Ahead= NULLBhead!=NULLC

11、head-next=NULLDhead-next !=NULL标准答案：C15, 20, 25）中采用最低位优先排序（LSD）基数排序, （2分）B10, 20, 35, 15, 25D20, 10, 35, 15, 2546下列逻辑结构中，（）为线性结构。（2分）A栈B队列C串D二叉树标准答案：AQC 47深度为3的二叉树可能的结点个数是（）。（2分） TOC o 1-5 h z A1B2C3D4标准答案：A,B 48下列各项键值（）序列是大顶堆的。（2分） HYPERLINK l bookmark0 o Current Document A23, 68,94,16,5B94,68,23,1

12、6, 5 HYPERLINK l bookmark2 o Current Document C94, 23,68,16,5D94,16,68,23, 5标准答案：B,C 49下列（）是限制了插入和删除操作的特殊线性表。（2分）A栈B队列C串D数组标准答案：AB50对一棵二叉排序树，用（）方法进行遍历，不一定得到各结点键值的有序序列。（2分）A先根遍历B中根遍历C后根遍历D层次遍历标准答案：A,C,D 51数据的最小单位是（）。（2分）（）是算法具有的5（）是算法具有的5个特性D健壮性D十字链表A数据元素B记录标准答案：D 52算法是对某一类问题求解步骤的有限序列。其中, 之一。（2分）A有穷性

13、B正确性C可读性标准答案：A 53（）是数据的逻辑结构。（2分）A顺序表B链表C线性表标准答案：C 54（）是限制了插入和删除操作在一端进行的线性表。（2分）A栈B队列C串D数组标准答案：A55（）是限制了插入和删除操作分别在两端进行的线性表。（2分）A栈B队列C串D数组标准答案：B 56用链表表示线性表的优点是（）。（2分）A便于插入和删除B便于随机存取C花费的存储空间较顺序存储少D数据元素的物理顺序与逻辑顺序相同标准答案：A 57若已知一个栈的入栈序列是1、2、3、4,其出栈序列不可能为（）。（2分）A.1、4、3、2B.2、3、4、1C.4、3、2、1D.3、4、1、2标准答案：D 58

14、串下列关于串的叙述中，正确的是（）。（2分） A.2个串的长度相等，则2个串相等B空串至少包一个空格C替换操作可以实现字符的删除D一个串的长度至少是1标准答案：C 59深度为h的二叉树，第h层至少有（）个结点。（2分）A0B1C8D1660假设 n0 在程序段y=0;while（y+1）*（y+1）AnBCna标准答案：C61下面叙述错误的是（）。（2分）A在集合1, 2, 3, 4, 5中元素1是2的直接前驱B二叉排序树的中序遍历序列一定是有序的C有 3个结点的不同形态二叉树的数目为5D哈夫曼树中所有结点的孩子数目只可能为2或者为0标准答案：A62以下数据结构中，（）是线性结构。（2分）A广

15、义表B二叉树C稀疏矩阵 D.串标准答案：D63在一个长度为n的顺序表中删除一个元素的算法的时间复杂度为（）。（2分）AO（1）BO（log n）CO（n）DO（n2）标准答案：C64如果一个huffman树含有n个叶子，则该树必有（）的结点。（2分）An+1B2n+1 C2n D2n-1标准答案：D65在关键字序列（10,15,20,25,30）中，采用折半法査找25,关键字之间比较需要 （）次。（2分）A1B2C3D4标准答案：B6616某二叉树的前序遍历序列和和中序遍历序列均为abed,该二叉树的后序遍历 序列是（）。（2分）Aabcd Bdcba Caebd Ddbea标准答案：B67m

16、个顶点的有向完全图有（）个弧。（2分）Am（m-1）/2Bm+1 Cm Dm（m-1）标准答案：D68下列各项键值（）序列不是堆的。（2分）A94,68,23,16,5B94,23,68,5, 16C94,23,68,16,5D.94,16,68,23, 5标准答案：D设单链表中指针p指向结点A, q指向新元素结点，若要A之后插入一个新元 素，则所需修改指针的操作为（）。（2分）Ap-next=q, q-next=p-nextq-next=p-next, p-next=qp-next=q-next, q-next=pp-next=p, q-next=p-next标准答案：B在关键字序列（149, 138, 165, 197, 176, 113, 127）中采用最低位优先排序（LSD）基数排序，第一趟之后所得结果为（）。（2分）149, 138, 165, 197, 176, 113, 127128, 149, 1砧，197, 113, 176, 127128, 149, 165, 197, 113, 127, 176113, 127, 138, 149, 165, 176, 197标准答案：B下列术语表示的数据中，（）是同义语。（2分）A结点B数据元素C顶点D数据项标准答案