最全版专升本《数据结构》试题答案

［试题分类］:专升本《数据结构》_08004150［题型］:单选［分数］：2个顶点的无向连通网的最小成本树，至少有()个边。(n-1)(n-1)/2答案:C个顶点的连通无向图，至少有()个边。(m-1)(m-1)/2答案:C3.空串的长度是()。答案:A假设以数组A［0..n-1］存放循环队列的元素，其头指针front指向队头元素、尾指针rear指向队尾元素一个，则在少用一个元素空间的前提下，队列空的判定条件为()。(front+1)%n==rear(rear+1)%n==front+1==front==front答案:D可以采用()这种数据结构，实现二叉树的层次遍历运算。集合栈队列D.树答案:C线性表的顺序存储结构是一种（）的存储结构。随机存取存取顺序存取索引存取答案:A采用带头结点双向链表存储的线性表，在删除一个元素时，需要修改指针（）次。答案:D队列的出队操作是指（）操作。队头删除队尾删除队头插入队尾插入答案:A在关键字序列（10,15,20,25,30）中，采用折半法查找25,关键字之间比较需要（）次。答案:B串下列关于串的叙述中，正确的是（）。个串的长度相等，则2个串相等替换操作可以实现字符的删除空串至少包一个空格一个串的长度至少是1答案:B若二叉树对应的二叉链表共有n个非空链域，则该二叉树有（）个结点的二叉树。+1答案:D下面叙述错误的是（）。在无向图的邻接矩阵中每行1的个数等于对应的顶点度借助于队列可以实现对二叉树的层遍历对于单链表进行插入操作过程中不会发生上溢现象栈的特点是先进后出答案:C算法是对某一类问题求解步骤的有限序列。其中，（）是算法具有的5个特性之一。可读性有穷性正确性健壮性答案:B队列的入队操作是在（）进行的。任意位置指定位置队尾队头答案:C在关键字序列（10,15,20,25,30）中采用折半法查找20，依次与（）关键字进行了比较。,20,20,10,20答案:C线性表采用带头结点单链表实现，head为头指针，则判断表空的条件为（）。==NULL>next!=NULL!=NULL>next==NULL答案:D队列采用循环队列存储的优点是（）。便于增加队列存储空间防止队列溢出便于随机存取避免数据元素的移动答案:D在一个长度为n的链式栈中出栈实现算法的时间复杂度为（）。⑴（n）（logn）（n2）答案:A在关键字序列（149，138，165，197，176，113，127）中采用最低位优先排序（LSD）基数排序，第一趟之后所得结果为（）。，138，165，197，176，113，127，149，165，197，113，127，176，149，165，197，113，176，127，127，138，149，165，176，197答案:C（）是数据的逻辑结构。链表线性表十字链表顺序表答案:B数据的基本单位是（）。数据元素记录数据项数据对象答案:A在一个长度为n的链式队列中入队实现算法的时间复杂度为（）。（n2）（logn）⑴（n）答案:C以下与数据的存储结构无关的术语是（）。循环队列哈希表。.双向链表D.数组答案:D基于数据的逻辑关系，数据的逻辑结构划分为（）基本结构。类类类类答案:A以下数据结构中，（）是线性结构。栈特殊矩阵二维数组二叉树答案:A某二叉树的前序遍历序列和和中序遍历序列分别为abc和bca，该二叉树的后序遍历序列是（）。答案:A若已知一个栈的入栈序列是1、2、3、4,其出栈序列不可能为、4、3、2、4、1、2、3、4、1、3、2、1答案:B队列的出队操作是在（）进行的。指定位置任意位置队头队尾答案:C个结点的二叉树，其对应的二叉链表共有（）个非空链域。+1+1答案:B下面叙述错误的是（）。树的结点度是指结点的分支数对矩阵进行压缩存储后无法实现对其元素进行随机访问空串的长度为零借助于栈可以实现对图的深度优先遍历答案:B采用带头结点双向链表存储的线性表，在插入一个元素时，需要修改指针（）次。答案:D如果一个huffman树含有n个叶子，则该树必有（）的结点。+1+1答案:B深度为h的二叉树，第h层至少有（）个结点。答案:A数组a[1..256]采用顺序存储，a的首地址为10，每个元素占2字节，则a[21]的地址是（）。答案:D（）不是算法具有的5个特性之一。可行性正确性有穷性确定性答案:B深度为n的完全二叉树最多有（）个结点。+1答案:C37.在关键字序列（35,10，15,20，25）中采用最低位优先排序（LSD）基数排序，第一趟之后所得结果为（）。，10，35，25，15，10，35，15，25，20，35，15，25，20，15，25，35线性表采用顺序存储的优点是（）。便于删除避免数据元素的移动便于随机存取便于插入答案:C可以采用（）这种数据结构，实现表达式中左右括号是否配对出现判别的运算。队列栈集合树答案:B某二叉树的后序遍历序列和和中序遍历序列分别为cba和bca，该二叉树的前序遍历序列是（）。答案:C［试题分类］:专升本《数据结构》_08004150［题型］:单选［分数］:21.在关键字序列（10,20,30,40,50）中，采用折半法查找20，关键字之间比较需要（）次。答案:D在一个长度为n的链式栈中出栈实现算法的时间复杂度为（）。（n2）（n）⑴（logn）答案:C线性表的顺序存储结构是一种（）的存储结构。随机存取存取索引存取顺序存取答案:A（）是限制了数据元素的内部结构仅为一个字符的线性表。串数组队列栈答案:C假设以数组A[0..n-1]存放循环队列的元素，其头指针front指向队头元素、尾指针rear指向队尾元素一个，则在少用一个元素空间的前提下，队列空的判定条件为（）。（front+1）%n==rear（rear+1）%n==front==front+1==front答案:C序列（21,19,37,5,2）经冒泡排序法由小到大排序，第一趟后所得结果为（）。（19,21，5，2，37）（19，21，2，5，37）（19，21，37，5，2）（19,21,5,37,2）答案:A某二叉树的后序遍历序列和和中序遍历序列均为abcd，该二叉树的前序遍历序列是（）。答案:A采用带头结点双向链表存储的线性表，在删除一个元素时，需要修改指针（）次。答案:Cn个顶点的无向连通图的生成树，至少有（）个边。n（n-1）/2（n-1）答案:D以下与数据的存储结构无关的术语是（）。人.双向链表循环队列哈希表数组答案:D算法的空间复杂度是对算法（）的度量。空间效率时间效率健壮性可读性答案:A深度为h的二叉树，第h层最多有（）个结点。答案:C在具有k个度数为2的二叉树中，必有（）个叶子结点。+1答案:A串的长度是指串中所含（）的个数。相同字符不同字符不同字母所有字符答案:D数据的基本单位是（）。数据元素数据项数据对象记录答案:Am个结点的二叉树，其对应的二叉链表共有（）个非空链域。+1答案:C可以采用（）这种数据结构，实现二叉树的层次遍历运算。队列树栈集合答案:A（）是数据的不可分割的最小单位。数据类型数据项数据元素数据对象答案:B19.数组a［1..m］采用顺序存储，a［1］和a［m］地址分别为1024和1150,每个元素占2字节，则m是（）。答案:B20.下面叙述错误的是（）。有向图的邻接矩阵一定是对称的具有相同的叶子个数和具有相同的叶子权值的赫夫曼树不是唯一的顺序表是借助物理单元相邻表示数据元素之间的逻辑关系对于空队列进行出队操作过程中发生下溢现象答案:A［试题分类］:专升本《数据结构》_08004150［题型］:多选［分数］:2在下列排序方法中，（）的空间复杂度为O（n）。其中，n为参加排序的元素个数。归并排序冒泡排序选择排序快速排序答案:A,D十字链表适合于（）选作存储结构。二叉树队列稀疏矩阵边或弧数较少的图答案:C,D设哈希（Hash涵数为H（k）=k%17,其中k为关键字，关键字（）是同义词。,5,15,31,48,45,62,57,125答案:B,C,D下列各项键值（）序列不是堆的。（94,16,68,23,5}{94,68,23,16,5}（94,23,68,5,16}{94,23,16,68,5}答案:A,D二叉链表适合作为（）的存储结构。队列二叉树树森林答案:B,C,D［试题分类］:专升本《数据结构》_08004150［题型］:多选［分数］:2下列术语表示的数据中，（）是同义语。顶点结点数据项数据元素答案:A,B,D构造哈希（Hash）函数的方法有（）等。平方取中法折叠法除留余数法开放寻址法若已知一个栈的入栈序列是(1,2,3,4),其可能出栈序列为()。(3,1,2,4)(4,3,1,2)(1,2,3,4)(4,3,2,1)答案：C,D在下列排序方法中，()的最坏时间复杂度为O(n2)。其中，n为参加排序的元素个数。选择排序冒泡排序快速排序归并排序答案:A,B,C5.下列各项键值()序列是堆的。A.(5,23,68,16,94}B.(5,23,16,68,94}C.(5,94,16,23,68}D.(5,16,23,68,94}答案:B,D设哈希(Hash涵数为H(k)=k%17，其中k为关键字，关键字()是同义词。,5,15,45,62,31,48,57,125答案:B,C,D下列逻辑结构中，队列下列逻辑结构中，队列栈()为线性结构。下列各项键值()序列不是堆的。A.(94,23,16,68,5}B.(94,68,23,16,5}C.(94,23,68,5,16}D.(94,16,68,23,5}答案:A,D二叉树串答案:A,B,D数组通常采用顺序存储的优点是（）。便于增加存储空间防止下标溢出避免数据元素的移动便于依据下标进行随机存取答案:D深度为3的二叉树可能的结点个数是（）。答案:B,D下面叙述错误的是（）。选择一项：空串的长度为零对矩阵进行压缩存储后无法实现对其元素进行随机访问借助于栈可以实现对图的深度优先遍历树的结点度是指结点的分支数反馈正确答案是：对矩阵进行压缩存储后无法实现对其元素进行随机访问题目2获得分中的分标记题目在关键字序列（35,10，15,20，25）中采用最低位优先排序（LSD）基数排序，第一趟之后所得结果为（）。

选择一项：10,20,35,15,2520,10,35,15,2510,20,15,25,3520,10,35,25,15反馈正确答案是：10,20,35,15,25题目3获得分中的分标记题目数据的基本单位是（）。选择一项：记录数据元素数据对象数据项反馈正确答案是：数据元素题目4获得分中的分标记题目算法的时间复杂度是对算法（）的度量。选择一项：A.可读性

空间效率时间效率健壮性反馈正确答案是：时间效率题目5获得分中的分标记题目以下数据结构中，（）是线性结构。选择一项：二维数组二叉树栈特殊矩阵反馈正确;案是：栈题目6获得分中的分标记题目线性表的顺序存储结构是一种（）的存储结构。选择一项：Hash存取顺序存取

随机存取索引存取反馈正确答案是：随机存取题目7获得分中的分标记题目可以采用（）这种数据结构，实现表达式中左右括号是否配对出现判别的运算。选择一项：栈树队列集合反馈正确答案是：栈题目8获得分中的分标记题目线性表采用带头结点单链表实现，head为头指针，则判断表空的条件为（）。选择一项：head->next==NULLhead!=NULLhead==NULL

head->next!=NULL反馈正确答案是：head->next==NULL题目9获得分中的分标记题目数组a[1..256]采用顺序存储，a的首地址为10,每个元素占2字节，则a[21]的地址是（）。选择一项：10705030反馈正确答案是：50题目10获得分中的分标记题目下面叙述错误的是（）。选择一项：具有相同的叶子个数和具有相同的叶子权值的赫夫曼树是唯一的单链表是借助指针表示数据元素之间的逻辑关系无向图的邻接矩阵一定是对称的在顺序栈的入栈操作过程中可能发生上溢现象

反馈正确答案是：具有相同的叶子个数和具有相同的叶子权值的赫夫曼树是唯一的题目11获得分中的分标记题目在一个长度为n的链式栈中出栈实现算法的时间复杂度为()。选择一项：O(n)0(1)O(logn)0(n2)反馈正确答案是：0(1)题目12获得分中的分标记题目若二叉树对应的二叉链表共有m个非空链域，则该二叉树有()个结点的二叉树。选择一项：TOC\o"1-5"\h\zm+12mm-1m反馈正确答案是：m-1

题目13获得分中的分标记题目()是数据的逻辑结构。选择一项：链表线性表顺序表十字链表反馈正确答案是：线性表题目14获得分中的分标记题目数组a[1..256]采用顺序存储，a的首地址为10，每个元素占2字节，则a[21]的地址是()。选择一项：30105070反馈正确答案是：50题目15

获得分中的分标记题目假设以数组A[0..n-1]存放循环队列的元素，其头指针front指向队头元素、尾指针rear指向队尾元素一个，则在少用一个元素空间的前提下，队列空的判定条件为()。选择一项：(rear+1)%n==front(front+1)%n==rearrear==frontrear+1==front反馈正确答案是：rear==front题目16获得分中的分标记题目深度为h的二叉树，第h层至少有()个结点。选择一项：8TOC\o"1-5"\h\z1016标记题目线性表若采用链式存储结构时，要求结点的存储单元地址（）。选择一项：部分地址必须是连续的必须是连续的连续或不连续都可以必须是不连续的反馈正确答案是：连续或不连续都可以题目18获得分中的分标记题目（）不是算法具有的5个特性之一。选择一项：确定性可行性正确性有穷性

标记题目队列的出队操作是指（）操作。选择一项：队尾插入B.队头删除C.队尾删除D.队头插入反馈正确答案是：队头删除题目20获得分中的分标记题目队列采用循环队列存储的优点是（）。B.队头删除C.队尾删除D.队头插入选择一项：便于随机存取防止队列溢出避免数据元素的移动便于增加队列存储空间

标记题目可以采用（）这种数据结构，实现图的深度优先遍历运算。选择一项：栈集合队列树反馈正确答案是：栈题目22获得分中的分标记题目某二叉树的前序遍历序列和和中序遍历序列分别为abcd和bead，该二叉树的后序遍历序列是（）。选择一项：cbdadcbaabcddcba

标记题目队列的出队操作是在（）进行的。选择一项：队尾任意位置指定位置队头反馈正确答案是：队头题目24获得分中的分标记题目所占用的存储空间大小仅与图的顶点个数相关的存储结构是（）。选择一项：邻接表邻接矩阵十字链表逆邻接表

标记题目采用顺序存储的线性表，若表长为n,在第i号元素之后插入一个元素时，需要移动（）个元素。选择一项：i+1n-i+1in-i反馈正确答案是：n-i题目26获得分中的分标记题目以下（）术语与数据的存储结构无关选择一项：哈希表双向链表线索树栈

标记题目m个顶点的连通无向图，至少有()个边。选择一项：mm(m-1)m-1m(m-1)/2反馈正确答案是：m-1题目28获得分中的分标记题目二维数组通常采用顺序存储，其优点是()。选择一项：防止下标溢出便于增加存储空间便于依据下标进行随机存取避免数据元素的移动反馈正确答案是：便于依据下标进行随机存取题目29获得分中的分标记题目若二叉树对应的二叉链表共有n个非空链域，则该二叉树有（）个结点的二叉树。选择一项：2nn+1nn-1反馈正确答案是：n-1题目30获得分中的分标记题目若已知一个栈的入栈序列是1、2、3、4,其出栈序列不可能为选择一项：A.4、3、2、13、4、1、22、3、4、11、4、3、2反馈正确答案是：3、4、1、2题目31获得分中的分标记题目采用带头结点双向链表存储的线性表，在插入一个元素时，需要修改指针（）次。选择一项：TOC\o"1-5"\h\z1342反馈正确答案是：4题目32获得分中的分标记题目在关键字序列（10,15,20,25,30）中，采用折半法查找25,关键字之间比较需要（）次。选择一项：TOC\o"1-5"\h\z1423标记题目基于数据的逻辑关系，数据的逻辑结构划分为（）基本结构。选择一项：TOC\o"1-5"\h\z3类5类4类6类反馈正确答案是：4类题目34获得分中的分标记题目在关键字序列（10,15,20,25,30）中采用折半法查找25,依次与（）关键字进行了比较。选择一项：TOC\o"1-5"\h\z20,2520，30，252530,25标记题目在一个长度为n的链式队列中入队实现算法的时间复杂度为()。选择一项：0(1)0(n)O(logn)0(n2)反馈正确答案是：0(1)题目36获得分中的分标记题目深度为h的完全二叉树至少有()个叶子结点。选择一项：2(h-1)+12h-12(h-2)+12h-2标记题目某二叉树的前序遍历序列和和中序遍历序列分别为abc和bca，该二叉树的后序遍历序列是()。选择一项：acbabccbabca反馈正确答案是：cba题目38获得分中的分标记题目设哈希(Hash)函数为H(k)=k%17,其中k为关键字，关键字()是同义词。选择一项或多项：A.44,5,156,57,12528,45,62201,31,48反馈正确答案是：28,45,62,201,31,48,6,