专升本数据结构模拟题试卷

1、-.-.-.可修编-专升本数据结构模拟题试卷一.（共75题,共150分）数据的基本单位是（。 2 分 A.数据元素B.记录C.数据对象D.数据项检查答案标准答案：A（）是数据的不可分割的最小单位。 （2 分A.数据对象B.数据元素C.数据类型D.数据项检查答案标准答案：D算法的空间复杂度是对算法（）的度量。 （2 分A.时间效率B.空间效率C. 可 读 性 D.健壮性检查答案标准答案：B（）A.栈B.队列C. 串 D检查答案标准答案：B串的长度是指串中所含（）的个数。 （2 分A.不同字符B.不同字母C.相同字符检查答案标准答案：D（2 分）采用带头结点双向链表存储的线性表，在删除一个元素时，

2、需要修改指针（）次。 分）A.1B.2C.3D.4检查答案标准答案：B线性表的顺序存储结构是一种（）的存储结构。 （2 分A.顺序存取B.随机存取C.索引存取D.Hash 存取检查答案标准答案：B数组 a1.m和 am地址分别为 1024 和 1150，每个元素占2 字节，则m 是（。（2 分）A.64 B.32 C.16 D.8检查答案标准答案：A深度为h 的二叉树，第h 层最多有（）个结点。 （2 分A.hB.2h-1C.2h-1 D.2h检查答案标准答案：Cm 个结点的二叉树，其对应的二叉链表共有（）个非空链域。 （2 分A.mB.m+1 C.2m D.m-1检查答案标准答案：B下面叙述

3、错误的是（。 2 分）顺序表是借助物理单元相邻表示数据元素之间的逻辑关系C.有向图的邻接矩阵一定是对称的D.具有相同的叶子个数和具有相同的叶子权值的赫夫曼树不是唯一的检查答案标准答案：C以下与数据的存储结构无关的术语是（。 2 分 A.循环队列B.双向链表C. 哈 希 表 D.数组检查答案标准答案：D在一个长度为n的链式栈中出栈实现算法的时间复杂度为（。 2 分 A.O(1)B.O(log n)C.O(n)D.O(n2)检查答案标准答案：A在具有k 个度数为 2 的二叉树中，必有（）个叶子结点。 （2 分A.kB.k-1 C.2k D.k+1检查答案标准答案：D在关键字序列（10,20,30,

4、40,50）中，采用折半法查找 20，关键字之间比较需要（）次。（2 分A.1B.2C.3D.4检查答案标准答案：C16 某二叉树的后序遍历序列和和中序遍历序列均为 abcd，该二叉树的前序遍历序列是（。（2分 A.abcdD.dbca检查答案标准答案：Bn 个顶点的无向连通图的生成树，至少有（）个边。 （2 分A.n(n-1)B.n(n-1)/2 C.2nD.n-1检查答案标准答案：D可以采用（）这种数据结构，实现二叉树的层次遍历运算。 （2 分A.队列B.树C. 栈 D检查答案标准答案：A假设以数组 front 指向队头元素、尾指针 rear 指向队尾元素一个，则在少用一个元素空间的前提下

5、，队列空的判定条件为（。 （2分 A.rear= =frontB.(front+1)n= =rear C.rear+1= =front D.(rear+1)n= =front检查答案标准答案：A序列213）经冒泡排序法由小到大排序，第一趟后所得结果为（。 分）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,C,D(Hash)函数为 H(k)= k % ,其中k 为关键字，关键字()是同义词。 （

6、2 分） A.44,5,15B.28,45,62 C.6,57,125 D.201,31,48检查答案标准答案：B,C,D下列各项键值（）序列不是堆的。 （2 分A.94，68，23，16，5检查答案标准答案：C,D（）的空间复杂度为n 为参加排序的元素个数。分）选择排序B.快速排序C.归并排序D检查答案标准答案：B,C十字链表适合于（）选作存储结构。 （2 分A.队列稀疏矩阵D.二叉树检查答案标准答案：B,C基于数据的逻辑关系，数据的逻辑结构划分为（）基本结构。 （2 分）A.6 类B.5 类C.4 类D.3 类检查答案标准答案：C（）5 个特性之一。 （2 分）有穷性B.确定性C.可行性D

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

8、的入栈序列是 12、4，其出栈序列不可能。 （2分 A.1、43、2B.3、41、2、D.2、3、4、1检查答案标准答案：B数组a 的首地址为12 （。（2 分） A.10 B.30 C.50 D.70检查答案标准答案：C深度为h 的完全二叉树至少有（）个叶子结点。 （2 分A.2(h-1)+1C.2h-1D.2h-2检查答案标准答案：D若二叉树对应的二叉链表共有m 个非空链域，则该二叉树有（）分）A.m B.m-1 C.m+1 D.2m检查答案标准答案：B下面叙述错误的是（。 2 分）A.单链表是借助指针表示数据元素之间的逻辑关系B.在顺序栈的入栈操作过程中可能发生上溢现象C.具有相同的叶子

9、个数和具有相同的叶子权值的赫夫曼树是唯一的D.无向图的邻接矩阵一定是对称的检查答案标准答案：C以下（）术语与数据的存储结构无关 （2 分A.栈B. 哈 希 表 C. 线 索 树 D.双向链表检查答案标准答案：A在一个长度为n的链式队列中入队实现算法的时间复杂度为（。 （2分 A.O(1)B.O(log n)C.O(n)D.O(n2)检查答案标准答案：A队列的出队操作是指（）操作。 （2 分A.队尾删除B.队头删除C.队尾插入D.队头插入检查答案标准答案：B在关键字序列（10,15,20,25,30）中采用折半法查找 25，依次与（）关键字进行了比较。（2 分 ） A.30,25 B.20,25

10、 C.20，30，25 D.25检查答案标准答案：B16 某二叉树的前序遍历序列和和中序遍历序列分别为abcd 和 bcad历序列是（。（2分）A.cbda B.dcba C.abcd D.dcba检查答案标准答案：A所占用的存储空间大小仅与图的顶点个数相关的存储结构是（。（2分 A.邻接表B.逆邻接表C.十字链表D.邻接矩阵检查答案标准答案：D可以采用（）这种数据结构，实现图的深度优先遍历运算。 （2 分A.队列树栈 D检查答案标准答案：Chead为头指针，则判断表空的条件为（。 （2分 A.head= NULLB.head!=NULL C.head-next=NULLhead-next !

11、=NULL检查答案标准答案：C在关键字序列（35，10，15，20，25）中采用最低位优先排序(LSD之后所得结果为（。 2 分）A.10，20，15，25，35 B.10，20，35，15，25 C.20，10，35，25，15 D.20，10，35，15，25检查答案标准答案：B（）为线性结构。（2分 A.栈B.队列C.串D.二叉树检查答案标准答案：A,B,C深度为3 的二叉树可能的结点个数是（。 2 分 A.1B.2C.3D.4检查答案标准答案：A,B下列各项键值（）序列是大顶堆的。 （2 分A.23，68，94，16，5B.94，68，23，16，5C.94，23，68，16，5 D.

12、94，16，68，23，5检查答案标准答案：B,C下列（）是限制了插入和删除操作的特殊线性表。 （2 分A.栈B.队列C. 串 D检查答案标准答案：A,B对一棵二叉排序树，用（）方法进行遍历，不一定得到各结点键值的有序序列。 分）先根遍历B.中根遍历C.后根遍历D检查答案标准答案：A,C,D数据的最小单位是（。 2 分 A.数据元素B.记录C.数据对象D.数据项检查答案标准答案：D（是算法具有的5 个特性之一。分）有穷性B.正确性C.可读性D检查答案标准答案：A（）是数据的逻辑结构。 （2 分A.顺序表B. 链 表 C.线性表D.十字链表检查答案标准答案：C（）是限制了插入和删除操作在一端进行

13、的线性表。 （2 分A.栈B.队列C. 串 D检查答案标准答案：A（）是限制了插入和删除操作分别在两端进行的线性表。 （2 分A.栈B.队列C. 串 D检查答案标准答案：B用链表表示线性表的优点是（。 2 分 A.便于插入和删除便于随机存取花费的存储空间较顺序存储少数据元素的物理顺序与逻辑顺序相同检查答案标准答案：A若已知一个栈的入栈序列是2、，其出栈序列不可能为（ A.1、43、2B.2、3、4、1 C.4、3、2、1 D.3、4、1、2检查答案标准答案：D串下列关于串的叙述中，正确的是（。（2分）A.2 个串的长度相等，则 2 个串相等B.空串至少包一个空格C.替换操作可以实现字符的删除D

14、.一个串的长度至少是 1检查答案标准答案：C深度为h 的二叉树，第h 层至少有（）个结点。 （2 分）（2 分）A.0B.1C.8 D.16检查答案标准答案：B假设n0，在程序段y=0;while(y+1)*(y+1)next=q，q-next=p-next B.q-next=p-next，p-next=q C.p-next=q-next，q-next=p D.p-next=p，q-next=p-next检查答案标准答案：B70. 在关键字序列（149，138，165，197，176，113，127）(LSD数排序，第一趟之后所得结果为（。 2 分）A.149，138，165，197，176，113，127 B.128，149，165，197，113，176，127 C.128，149，165，197，113，127，176 D.113，127，138，149，165，176，197检查答案标准答案：B下列术语表示的数据中（）是同义语。（2分 A.结点B.数据元素C.顶点D.数据项检查答案标准答案：A,B,C对于采用链式结构的队列（）运算的实现算法的时间复杂度为2 分 A.入队B. 出 队 C.求队长D.队清空检查答