《专升本《数据结构》-试卷-答案》由会员分享，可在线阅读，更多相关《专升本《数据结构》-试卷-答案（4页珍藏版）》请在金锄头文库上搜索。
1、Co 16Do 8专升本数据结构一、（共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。所有字
2、符标准答案:D6. 采用带头结点双向链表存储的线性表，在删除一个元素时，需要修改指针（）次. （2 分）A。1 B。 2C.3 D。 4标准答案： B7. 线性表的顺序存储结构是一种（）的存储结构. （2 分）A.顺序存取B。随机存取 C。索引存取 Do Hash存取标准答案:B &数组a1o .m采用顺序存储,a 1和am地址分别为1024和1150，每个元素占2字节，则m是（）o （2 分）Ao 64 Bo 32标准答案： A9. 深度为h的二叉树，第h层最多有（）个结点。（2分）A.hB o 2h1Co 2h1D.2h标准答案： C10. m个结点的二叉树，其对应的二叉链表共有（）个非空
3、链域。（2分）Ao mB.m+1 C.2mDo m1标准答案:B11o下面叙述错误的是（）。（2分）A.顺序表是借助物理单元相邻表示数据元素之间的逻辑关系Bo对于空队列进行出队操作过程中发生下溢现象Co有向图的邻接矩阵一定是对称的Do具有相同的叶子个数和具有相同的叶子权值的赫夫曼树不是唯一的 标准答案： C12. 以下与数据的存储结构无关的术语是（）。（2分）A。循环队列B.双向链表 C.哈希表Do数组标准答案： D13. 在一个长度为n的链式栈中出栈实现算法的时间复杂度为（）o （2分）Ao O（1）B.O（log n）C.O（ n）D.O（n2）标准答案： A 14o在具有k个度数为2的二
4、叉树中，必有（）个叶子结点。（2分）Ao kBo k-1Co 2kDo k+1标准答案： D15o在关键字序列（10, 20,30，40，50）中，采用折半法查找20,关键字之间比较需要（）次。（2 分）Ao 1Bo 2Co 3D.4标准答案:C16.16某二叉树的后序遍历序列和和中序遍历序列均为abed，该二叉树的前序遍历序列是（）。（2 分）Ao abed Bo deba Co aebd Do dbea标准答案： B17o n个顶点的无向连通图的生成树，至少有（）个边。（2分）Ao n（n-1） Bo n（n1）/2C.2n Do n-1标准答案： D18o 可以采用（）这种数据结构，实现
5、二叉树的层次遍历运算.（2分）A.队列Bo树Co栈D.集合标准答案： A19o假设以数组A 0oo n-1存放循环队列的元素，其头指针front指向队头元素、尾指针rear指 向队尾元素一个，则在少用一个元素空间的前提下，队列空的判定条件为（） . （2分）A.rear= =frontBo（front+1）%n= =rearC.rear+1= =frontD.（rear+1）n= =front标准答案:A20.序列（21， 19， 37， 5，2）经冒泡排序法由小到大排序，第一趟后所得结果为（）.（2分）A.（19， 21， 37， 5，2）B.（19， 21， 5， 2，37）C.（19，
6、21，5， 37，2）Do（19， 21， 2，5， 37）标准答案： B21o二叉链表适合作为（）的存储结构。（2分）A.队列Bo二叉树Co树D.森林标准答案:B,C,D22o设哈希（Hash）函数为H （k）= k % 17,其中k为关键字,关键字（）是同义词。（2分）Ao 44， 5， 15B.28， 45， 62 Co 6， 57,125 Do 201,31,48标准答案:B,C, DC.2h1A。 ebda B。 deba标准答案： AC。 abed D.deba23. 下列各项键值（）序列不是堆的。 （2分）A。94,68,23,16,5B.94, 23, 68, 5, 16C.
7、94, 23,16, 68, 5 D。94, 16, 68, 23,5标准答案：C,D24。 在下列排序方法中，（）的空间复杂度为O （n）。其中，n为参加排序的元素个数。（2分） A。选择排序 B。快速排序 C。归并排序 D。冒泡排序标准答案： B,C25。十字链表适合于（）选作存储结构. （2分）A.队列B.稀疏矩阵C.边或弧数较少的图D。二叉树标准答案： B,C26。基于数据的逻辑关系,数据的逻辑结构划分为（）基本结构. （2分）Ao 6类 B.5类 C.4类 D.3类标准答案： C27。 （）不是算法具有的 5 个特性之一。（ 2 分）A.有穷性B.确定性C。可行性 D.正确性标准答案
8、:D28。 算法的时间复杂度是对算法（）的度量。（2分）A。时间效率 B.空间效率C。可读性 D。健壮性标准答案： A29。线性表若采用链式存储结构时,要求结点的存储单元地址（） . （2分）A.必须是连续的B.部分地址必须是连续的C。必须是不连续的D.连续或不连续都可以标准答案:D30。 二维数组通常采用顺序存储,其优点是（）。（2分）A.便于增加存储空间B。防止下标溢出C.避免数据元素的移动D。便于依据下标进行随机存取标准答案:D31o采用顺序存储的线性表，若表长为n,在第i号元素之后插入一个元素时，需要移动（）个元 素。（2分）A。 i+1 B。 iC。 n-i D。 ni+1标准答案：
9、 C32。 若已知一个栈的入栈序列是1、2、3、4,其出栈序列不可能为。 （2分）A.1、4、3、2 B。 3、4、1、2 C.4、3、2、1D.2、3、4、1标准答案： B33. 数组a1o .256采用顺序存储,a的首地址为10,每个元素占2字节，则a21的地址是（）.（2 分）A.10 B。 30C.50D.70标准答案:C34o深度为h的完全二叉树至少有（）个叶子结点。（2分）标准答案： D35o若二叉树对应的二叉链表共有m个非空链域，则该二叉树有（）个结点的二叉树。（2分） A.mB。 m-1 C。 m+1 D。 2m标准答案： B36. 下面叙述错误的是（）。 （2分）A. 单链表
10、是借助指针表示数据元素之间的逻辑关系B. 在顺序栈的入栈操作过程中可能发生上溢现象C. 具有相同的叶子个数和具有相同的叶子权值的赫夫曼树是唯一的D. 无向图的邻接矩阵一定是对称的标准答案： C37。以下（）术语与数据的存储结构无关（2分）A。栈 B.哈希表 C.线索树 D。双向链表 标准答案： A38在一个长度为n的链式队列中入队实现算法的时间复杂度为（）。（2分）A.O（1）B.O（log n）C。 O（ n）D.O（n2）标准答案： A 39。 队列的出队操作是指（）操作。 （2分）A。队尾删除 B。队头删除 C。队尾插入 D.队头插入 标准答案:B40. 在关键字序列（10, 15, 2
11、0, 25, 30）中采用折半法查找 25,依次与（）关键字进行了比较。 （2 分）A。 30,25 B。 20,25 C。 20, 30, 25 D.25标准答案： B41 o 16某二叉树的前序遍历序列和和中序遍历序列分别为abed和bead，该二叉树的后序遍历序列是 （）。（2分）42。所占用的存储空间大小仅与图的顶点个数相关的存储结构是（）。（2分）A.邻接表B.逆邻接表C。十字链表D。邻接矩阵标准答案： D43。可以采用（）这种数据结构,实现图的深度优先遍历运算。 （2分） A。队列 B.树C.栈D。集合标准答案:C44. 线性表采用带头结点单链表实现,head为头指针,则判断表空的
12、条件为（）。（2分） A。 head= NULLB . head ！=NULLC.headnext=NULLD.headnext !=NULL标准答案： C45. 在关键字序列（35, 10, 15,20, 25）中采用最低位优先排序（LSD）基数排序，第一趟之后所 得结果为（）。 （2分）A。10，20，15，25，35B.10，20，35，15,25C.20, 10,35, 25,15D.20, 10,35, 15, 25标准答案:B46. 下列逻辑结构中，（）为线性结构。（2分）A.栈B.队列 C.串D.二叉树标准答案:A, B，C47. 深度为3的二叉树可能的结点个数是（ ） .（2分
13、）A。 1B.2C.3D。 4标准答案：A,B48. 下列各项键值（）序列是大顶堆的. （2分）A. 23, 68，94,16,5 B94, 68，23,16,5Co 94, 23, 68, 16, 5 D. 94, 16,68, 23, 5 标准答案： B， C 49o下列（）是限制了插入和删除操作的特殊线性表。（2分）A.栈B。队列 C.串Do数组标准答案： A, B 50o对一棵二叉排序树，用（）方法进行遍历，不一定得到各结点键值的有序序列。（2分）A。先根遍历 B.中根遍历 Co后根遍历 Do层次遍历标准答案： A， C,D51o数据的最小单位是（）。（2分）A.数据元素Bo记录C.数
14、据对象 D.数据项标准答案： D52 o算法是对某一类问题求解步骤的有限序列。其中，（）是算法具有的5个特性之一。（2分） A。有穷性B.正确性Co可读性 Do健壮性标准答案:A53o （）是数据的逻辑结构。（2分）A。顺序表B.链表Co线性表 Do十字链表标准答案： C54.（）是限制了插入和删除操作在一端进行的线性表。（2分）A。栈 Bo队列 C.串Do数组标准答案:A55o （）是限制了插入和删除操作分别在两端进行的线性表.（2分）A。栈 Bo队列Co串D.数组标准答案： B56.用链表表示线性表的优点是（）。（2分）A. 便于插入和删除B. 便于随机存取C. 花费的存储空间较顺序存储少Do数据元素的物理顺序与逻辑顺序相同标准答案： A57 o若已知一个栈的入栈序列是1、2、3、4,其出栈序列不可能为（）。（2分）A.1、 4、3、2 Bo2、3、 4、 1 Co 4、3、2、1D.3、4、1、 2标准答案： D58. 串下列关于串的叙述中，正确的是（） o （2分）Ao 2个串的长度相等,则2个串相等Bo空串至少包一个空格Co替换操作可以实现字符的删除D. 个串的长度至少是1 标准答案： C59. 深度为h的二叉树，第h层至少有（）个结点。（2分）Ao 0B.1Co 8D.16标准答案： B60. 假设 n0
