专升本数据结构试卷答案.docx

专升本《数据结构》

一、（共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

6.采用带头结点双向链表存储的线性表，在删除一个元素时，需要修改指针（）次。（2分）
A.1B.2C.3D.4
.标准答案：B

7.线性表的顺序存储结构是一种（）的存储结构。（2分）
A.顺序存取B.随机存取C.索引存取D.Hash存取
.标准答案：B

8.数组a[1..m]采用顺序存储，a[1]和a[m]地址分别为1024和1150，每个元素占2字节，则m是（）。（2分）
A.64B.32C.16D.8
.标准答案：A

9.深度为h的二叉树，第h层最多有（）个结点。（2分）
A.hB.2h-1
C.2h-1D.2h
.标准答案：C

10.m个结点的二叉树，其对应的二叉链表共有（）个非空链域。（2分）
A.mB.m+1C.2mD.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(logn)
C.O(n)D.O(n2)
.标准答案：A

14.在具有k个度数为2的二叉树中，必有（）个叶子结点。（2分）
A.kB.k-1C.2kD.k+1
.标准答案：D

15.在关键字序列（10,20,30,40,50）中，采用折半法查找20，关键字之间比较需要（）次。（2分）
A.1B.2C.3D.4
.标准答案：C

16.16某二叉树的后序遍历序列和和中序遍历序列均为abcd，该二叉树的前序遍历序列是（）。（2分）
A.abcdB.dcbaC.acbdD.dbca
.标准答案：B

17.n个顶点的无向连通图的生成树，至少有（）个边。（2分）
A.n(n-1)B.n(n-1)/2C.2nD.n-1
.标准答案：D

18.可以采用（）这种数据结构，实现二叉树的层次遍历运算。（2分）
A.队列B.树C.栈D.集合
.标准答案：A

19.假设以数组A［0..n-1］存放循环队列的元素，其头指针front指向队头元素、尾指针rear指向队尾元素一个，则在少用一个元素空间的前提下，队列空的判定条件为（）。（2分）
A.rear==frontB.(front+1)％n==rear
C.rear+1==frontD.(rear+1)％n==front
.标准答案：A

20.序列（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

21.二叉链表适合作为（）的存储结构。（2分）
A.队列B.二叉树C.树D.森林
.标准答案：B,C,D

22.设哈希(Hash)函数为H(k)=k%17,其中k为关键字，关键字()是同义词。（2分）
A.44,5,15B.28,45,62C.6,57,125D.201,31,48
.标准答案：B,C,D

23.下列各项键值（）序列不是堆的。（2分）
A.{94，68，23，16，5B.{94，23，68，5，16
C.{94，23，16，68，5D.{94，16，68，23，5
.标准答案：C,D

24.在下列排序方法中，（）的空间复杂度为O(n)。其中，n为参加排序的元素个数。（2分）
A.选择排序B.快速排序C.归并排序D.冒泡排序
.标准答案：B,C

25.十字链表适合于（）选作存储结构。（2分）
A.队列B.稀疏矩阵
C.边或弧数较少的图D.二叉树
.标准答案：B,C

26.基于数据的逻辑关系，数据的逻辑结构划分为（）基本结构。（2分）
A.6类B.5类C.4类D.3类
.标准答案：