专升本《数据结构》模拟题试卷.doc

专升本数据结构模拟题试卷一. （共75题,共150分）1. 数据的基本单位是（）。（2分）A.数据元素B.记录C.数据对象D.数据项检查答案标准答案：A 2. （）是数据的不可分割的最小单位。（2分）A.数据对象B.数据元素C.数据类型D.数据项检查答案标准答案：D 3. 算法的空间复杂度是对算法（）的度量。（2分）A.时间效率B.空间效率C.可读性D.健壮性检查答案标准答案：B 4. （）是限制了数据元素的内部结构仅为一个字符的线性表。（2分）A.栈B.队列C.串D.数组检查答案标准答案：B 5. 串的长度是指串中所含（）的个数。（2分）A.不同字符B.不同字母C.相同字符D.所有字符检查答案标准答案：D （2采用带头结点双向链表存储的线性表，在删除一个元素时，需要修改指针（）次。6. 分）A.1 B.2 C.3 D.4 检查答案标准答案：B 7. 线性表的顺序存储结构是一种（）的存储结构。（2分）A.顺序存取B.随机存取C.索引存取D.Hash存取检查答案标准答案：B 8. 数组a1.m采用顺序存储，a1和am地址分别为1024和1150，每个元素占字节，则2分）。是（）（2mA.64 B.32 C.16 D.8 A 检查答案标准答案：分）2（深度为h的二叉树，第h层最多有（）个结点。9. A.h B.2h-1 C.2h-1 D.2h C 检查答案标准答案：分）个结点的二叉树，其对应的二叉链表共有（）个非空链域。2（10. mA.m B.m+1 C.2m D.m-1 B 检查答案标准答案：分）。11. 下面叙述错误的是（）（2顺序表是借助物理单元相邻表示数据元素之间的逻辑关系A.对于空队列进行出队操作过程中发生下溢现象B.C.有向图的邻接矩阵一定是对称的D.具有相同的叶子个数和具有相同的叶子权值的赫夫曼树不是唯一的检查答案标准答案：C 12. 以下与数据的存储结构无关的术语是（）。（2分）循环队列A.双向链表B.哈希表C.数组D.D 检查答案标准答案：13. 在一个长度为n的链式栈中出栈实现算法的时间复杂度为（）。（2分）A.O(1) B.O(log n) C.O(n) D.O(n2) 检查答案标准答案：A 14. 在具有k个度数为2的二叉树中，必有（）个叶子结点。（2分）A.k B.k-1 C.2k D.k+1 D 检查答案标准答案：15. 在关键字序列（10,20,30,40,50）中，采用折半法查找20，关键字之间比较需要（）次。分）（2A.1 B.2 C.3 D.4 C 检查答案标准答案：16. 16某二叉树的后序遍历序列和和中序遍历序列均为，该二叉树的前序遍历序列是abcd分）2（）。A.abcd B.dcba C.acbd D.dbca 检查答案标准答案：B 17. n个顶点的无向连通图的生成树，至少有（）个边。（2分）A.n(n-1) B.n(n-1)/2 C.2n D.n-1 D 检查答案标准答案：18. 可以采用（）这种数据结构，实现二叉树的层次遍历运算。（2分）队列A.树B.栈C.集合D.A 检查答案标准答案：19. 假设以数组A0.n-1存放循环队列的元素，其头指针front指向队头元素、尾指针rear。（2分）指向队尾元素一个，则在少用一个元素空间的前提下，队列空的判定条件为（）A.rear= =front n= =rear B.(front+1)C.rear+1= =front n= =front D.(rear+1)A 检查答案标准答案：20. 序列（21，19，37，5，2）经冒泡排序法由小到大排序，第一趟后所得结果为（）。（2分）2) ，5，A.(19，21，3737) ，2B.(19，21，5，2) ，537，C.(192137) 5，2D.(19，21，B 检查答案标准答案：21. 二叉链表适合作为（）的存储结构。分）2（队列A.二叉树B.树C.森林D.B,C,D 检查答案标准答案：22. 设哈希(Hash)函数为H(k)= k % 17,其中k为关键字，关键字()是同义词。（2分）A.44,5,15 B.28,45,62 C.6,57,125 D.201,31,48 检查答案标准答案：B,C,D 23. 下列各项键值（）序列不是堆的。（2分）A.94，68，23，16，5 B.94，23，68，5，16 C.94，23，16，68，5 D.94，16，68，23，5 检查答案标准答案：C,D 24. 在下列排序方法中，（）的空间复杂度为O(n)。其中，n为参加排序的元素个数。（2分）选择排序A.快速排序B.归并排序C.冒泡排序D.B,C 检查答案标准答案：分）（225. 十字链表适合于（）选作存储结构。队列A.稀疏矩阵B.边或弧数较少的图C.二叉树D.B,C 检查答案标准答案：分）基于数据的逻辑关系，数据的逻辑结构划分为（）基本结构。26. （2类A.6类B.5类C.4类D.3C 检查答案标准答案：分）（527. （）不是算法具有的个特性之一。2有穷性A.B.确定性C.可行性D.正确性检查答案标准答案：D 28. 算法的时间复杂度是对算法（）的度量。（2分）时间效率A.空间效率B.可读性C.健壮性D.A 检查答案标准答案：29. 线性表若采用链式存储结构时，要求结点的存储单元地址（）。（2分）必须是连续的A.部分地址必须是连续的B.必须是不连续的C.连续或不连续都可以D.D 检查答案标准答案：30. 二维数组通常采用顺序存储，其优点是（）。（2分）便于增加存储空间A.防止下标溢出B.避免数据元素的移动C.便于依据下标进行随机存取D.D 检查答案标准答案：31. 采用顺序存储的线性表，若表长为n，在第i号元素之后插入一个元素时，需要移动（）分）（2个元素。A.i+1 B.i C.n-i D.n-i+1 C 检查答案标准答案：32. 若已知一个栈的入栈序列是分）2（。_，其出栈序列不可能为4、3、2、12 4A.1、32 、B.3411 、3、2、C.41 、4、3、D.2检查答案标准答案：B 33. 数组a1.256采用顺序存储，a的首地址为10，每个元素占2字节，则a21的地址是（）。（2分）A.10 B.30 C.50 D.70 检查答案标准答案：C 34. 深度为h的完全二叉树至少有（）个叶子结点。（2分）A.2(h-1)+1 B.2(h-2)+1 C.2h-1 D.2h-2 检查答案标准答案：D 35. 若二叉树对应的二叉链表共有m个非空链域，则该二叉树有（）个结点的二叉树。（2分）A.m B.m-1 C.m+1 D.2m B 检查答案标准答案：分）236. 下面叙述错误的是（）。（单链表是借助指针表示数据元素之间的逻辑关系A.在顺序栈的入栈操作过程中可能发生上溢现象B.具有相同的叶子个数和具有相同的叶子权值的赫夫曼树是唯一的C.无向图的邻接矩阵一定是对称的D.C 检查答案标准答案：分）237. 以下（）术语与数据的存储结构无关（栈A.哈希表B.线索树C.双向链表D.A 检查答案标准答案：38. 在一个长度为n的链式队列中入队实现算法的时间复杂度为（）。（2分）A.O(1) B.O(log n) C.O(n) D.O(n2) 检查答案标准答案：A 39. 队列的出队操作是指（）操作。（2分）队尾删除A.队头删除B.队尾插入C.队头插入D.B 检查答案标准答案：40. 在关键字序列（10,15,20,25,30）中采用折半法查找25，依次与（）关键字进行了比较。分）2（A.30,25 B.20,25 25 ，30，C.20D.25 B 检查答案标准答案：41. 16某二叉树的前序遍历序列和和中序遍历序列分别为abcd和bcad，该二叉树的后序遍分）历序列是（）。（2A.cbda B.dcba C.abcd D.dcba A 检查答案标准答案：42. 所占用的存储空间大小仅与图的顶点个数相关的存储结构是（）。（2分）邻接表A.逆邻接表B.十字链表C.邻接矩阵D.D 检查答案标准答案：分）2（可以采用（）这种数据结构，实现图的深度优先遍历运算。43. A.队列B.树C.栈D.集合检查答案标准答案：C 44. 线性表采用带头结点单链表实现，head为头指针，则判断表空的条件为（）。（2分）A.head= NULL B.head!=NULL C.head-next=NULL D.head-next !=NULL 检查答案标准答案：C 45. 在关键字序列（35，10，15，20，25）中采用最低位优先排序基数排序，第一趟(LSD)分）2之后所得结果为（）。（35 ，1525，A.10，20，25 ，15，B.10，20，3515 25，C.20，1035，25 15，10，35，D.20B 检查答案标准答案：分）246. 下列逻辑结构中，（）为线性结构。（栈A.队列B.串C.二叉树D.A,B,C 检查答案标准答案：分）。（247. 深度为3的二叉树可能的结点个数是（）A.1 B.2 C.3 D.4 A,B 检查答案标准答案：分）2下列各项键值（）序列是大顶堆的。48. （5 ，16，94A.23，68，5 ，6823，16，B.945 ，16，68，23，C.94D.94，16，68，23，5 检查答案标准答案：B,C 49. 下列（）是限制了插入和删除操作的特殊线性表。（2分）A.栈B.队列C.串D.数组检查答案标准答案：A,B 50. 对一棵二叉排序树，用（）方法进行遍历，不一定得到各结点键值的有序序列。2（分）先根遍历A.中根遍历B.后根遍历C.层次遍历D.A,C,D 检查答案标准答案：分）（数据的最小单位是（）。251. 数据元素A.记录B.数据对象C.数据项D.D 检查答案标准答案：（2（）是算法具有的算法是对某一类问题求解步骤的有限序列。其中，5个特性之一。52. 分）有穷性A.正确性B.可读性C.健壮性D.A 检查答案标准答案：分）53. （）是数据的逻辑结构。2（顺序表A.链表B.线性表C.十字链表D.C 检查答案标准答案：54. （）是限制了插入和删除操作在一端进行的线性表。（2分）A.栈B.队列C.串D.数组检查答案标准答案：A 55. （）是限制了插入和删除操作分别在两端进行的线性表。（2分）A.栈B.队列C.串D.数组检查答案标准答案：B 56. 用链表表示线性表的优点是（）。（2分）A.便于插入和删除B.便于随机存取C.花费的存储空间较顺序存储少D.数据元素的物理顺序与逻辑顺序相同检查答案标准答案：A 57. 若已知一个栈的入栈序列是1、2、3、4，其出栈序列不可能为（）。（分）22 4、3、A.1、1 、4、B.2、31 2、C.4、3、2 、D.3、4、1D 检查答案标准答案：分）串下列关于串的叙述中，正确的是（）。（258. 个串相等A.2个串的长度相等，则2空串至少包一个空格B.替换操作可以实现字符的删除C.1 一个串的长度至少是D.C 检查答案标准答案：分）hh59. 深度为的二叉树，第层至少有（）个结点。（2A.0 B.1 C.8 D.16 检查答案标准答案：B 60. 假设n0，在程序段y=0;while(y+1)*(y+1)next=p-next A.p-next=q，p-next=q B.q-next=p-next，q-next=p ，C.p-next=q-nextq-next=p-next ，D.p-next=pB 检查答案标准答案：70. 在关键字序列（149，138，165，197，176，113，127）中采用最低位优先排序(LSD)分）2。（基数排序，第一趟之后所得结果为（）127 113，197，176，A.149，138，165127 176，197，113，B.128，149，165，176 127，113，C.128，149，165，197197 ，165，176127，138，149，D.113，B 检查答案标准答案：分）2（）是同义语。（71. 下列术语表示的数据中，结点A.数据元素B.顶点C.数据项D.A,B,C 检查答案标准答案：分）（2对于采用链式结构的队列，（）运算的实现算法的时间复杂度为O(1)。72. 入队A.出队B.求队长C