《数据结构》复习资料
一 单选题 (共48题 ，总分值0分 )
1. 设用链表作为栈的存储结构，则退栈操作 （0 分）
A. 必须判别栈是否为满
B. 必须判别栈是否为空
C. 判别栈元素的类型
D. 对栈不作任何判别
2. 下面关于m阶B树说法正确的是（　）。
①每个结点至少有两棵非空子树；  ②树中每个结点至多有m-1个关键字；
③所有叶子在同一层上；      ④当插入一个数据项引起B树结点分裂后，树长高一层。 （0 分）
A. ①②③ 
B. ②③ 
C. ②③④ 
D. ③
3. 下列关于文件的说法，错误的是（　）。 （0 分）
A. 选择文件的组织方式时应考虑外存的性质和容量
B. 不定长文件指的是总长度可变的文件
C. 对文件的操作主要是维护和检索
D. 文件的存储结构指的是文件在外存上的组织方式
4. 设无向图的顶点个数为n，则该图最多有（　）条边。 （0 分）
A. n-1　
B. n(n-1)/2　
C. n(n+1)/2　
D. n2
5. 设广义表L=((a,()),b,(c,d,e))，则Head(Tail(Tail(L)))的值为（　）。 （0 分）
A. b　
B. c　
C. (c)　
D. (c,d,e)
6. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。 （0 分）
A.  688
B. 678
C. 692
D. 696
7. 设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为 （0 分）
A. n
B. e
C. 2n
D. 2e
8. 广义表(a,(b,(),c))的深度为（ ）。 （0 分）
A. 1　
B. 2　
C. 3　
D. 4
9. 设有向图G中有五个顶点，各顶点的度分别为3、2、2、1、2，则G中弧数为（　）。 （0 分）
A. 4条　
B. 5条　
C. 6条　
D. 无法确定
10. 若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查，则查A[3]的比较序列的下标依次为 （0 分）
A. 1，2，3
B. 9，5，2，3
C. 9，5，3
D. 9，4，2，3
11. 具有n个顶点的有向强连通图最少有（ ）条弧。 （0 分）
A. n-1　
B. n　
C. n(n-1)　
D. n(n-1)/2
12. 将两个各有n个元素的有序表归并成一个有序表，最少进行（ ）次比较。 （0 分）
A. n　
B. 2n-1　
C. 2n　
D. n-1
13. 若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（　）。 （0 分）
A. 快速排序 
B. 堆排序 
C. 归并排序 
D. 直接插入排序
14. 下列说法中错误的是（  ）。 （0 分）
A. 栈是一种非线性结构
B. 一个数据元素由一或多个数据项构成
C. 在顺序存储结构中，结点间的逻辑关系由存储单元的邻接关系来体现
D. 语句的频度就是语句的执行次数
15. 对稀疏矩阵进行压缩存储的目的是（　）。 （0 分）
A. 便于进行矩阵运算　
B. 便于输入和输出
C. 节省存储空间　
D. 降低运算的时间复杂度
16. 二叉树的第k层的结点数最多为 （0 分）
A. 2k-1
B. 2K+1
C. 2K-1
D.  2k-1
17. 下面给出的四种排序法中（　）排序法是不稳定的排序法。 （0 分）
A. 插入 
B. 冒泡 
C. 二路归并 
D. 堆
18. 外部排序是指（ ）。 （0 分）
A. 在外存上进行的排序方法
B. 不需要使用内存的排序方法
C. 数据量很大，需要人工干预的排序方法
D. 排序前后数据在外存，排序时数据调入内存的排序方法
19. 下述文件中适合于磁带存储的是（ ）。 （0 分）
A. 顺序文件　
B. 索引文件　
C. 散列文件　
D. 多关键字文件
20. 栈和队列的共同特点是 （0 分）
A. 只允许在端点处插入和删除元素
B. 都是先进后出
C. 都是先进先出
D. 没有共同点
21. 下列说法中错误的是（ ）。 （0 分）
A. 数据对象是数据的子集
B. 数据元素间关系在计算机中的映象即为数据的存储结构
C. 非顺序映象的特点是借助指示元素存储地址的指针来表示数据元素间逻辑关系
D. 抽象数据类型指一个数学模型及定义在该模型上的一组操作
22. 设有一组关键字值（46,79,56,38,40,84），则用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）。 （0 分）
A. 38,40,46,56,79,84　
B. 40,38,46,79,56,84
C. 40,38,46,56,79,84　
D. 40,38,46,84,56,79
23. 在树形结构中，数据元素间存在（ ）的关系。 （0 分）
A. 一对一　
B. 一对多　
C. 多对多　
D. 除同属一个集合外别无关系
24. 设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为 （0 分）
A. O(n)数据结构与算法题库
B. O(nlog2n)
C. O(1)
D. O(n2)
25. 用链接方式存储的队列，在进行插入运算时 （0 分）
A. 仅修改头指针
B. 头、尾指针都要修改
C. 仅修改尾指针
D. 头、尾指针可能都要修改
26. 下列叙述中错误的是（　）。 （0 分）
A. 由树的先序遍历序列和后序遍历序列可以惟一确定一棵树
B. 二叉树不同于度为2的有序树
C. 深度为k的二叉树上最少有k个结点
D. 在结点数目相同的二叉树中，最优二叉树的路径长度最短
27. 若查每个元素的概率均相等，则在具有n个元素的静态查表中采用顺序查法查一个记录，其平均查长度ASL为（　）。 （0 分）
A. (n-1)/2 
B. n/2 
C. (n+1)/2 
D. n
28. 判定一个栈顶指针为S且不带头结点的链栈为空栈的条件是（ ）。 （0 分）
A. S　
B. S->next　
C. S->next==NULL　
D. !S
29. 设在一不带头结点的链队列中，front和rear分别为其队头和队尾指针，则删除一个结点的操作是（ ）。 （0 分）
A. rear=front->next　
B. rear=rear->next　
C. front=front->next　
D. front=rear->next
30. 设表中含100个数据元素，用折半查法进行查，则所需最大比较次数为（ ）。 （0 分）
A. 50　
B. 25　
C. 10　
D. 7
31. 串的长度是指（ ）。 （0 分）
A. 串中所含不同字母的个数　
B. 串中所含字符的个数
C. 串中所含不同字符的个数　
D. 串中所含非空格字符的个数
32. ISAM文件和VSAM文件属于（ ）。 （0 分）
A. 索引非顺序文件　
B. 索引顺序文件　
C. 顺序文件　
D. 散列文件
33. 设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（  ）条有向边。 （0 分）
A. n
B. n-1
C. m
D. m-1
34. 设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（  ）趟的分配和回收才能使得初始关键字序列变成有序序列。 （0 分）
A. 3
B. 4
C. 5
D. 8
35. 对二叉排序树进行（　）遍历所得的遍历序列中，关键字值是按升序排列的。 （0 分）
A. 前序　
B. 中序　
C. 后序　
D. 层序
36. 下列叙述中错误的是（ ）。 （0 分）
A. 树的度与该树中结点的度的最大值相等　
B. 二叉树就是度为2的有序树
C. 有5个叶子结点的二叉树中必有4个度为2的结点　
D. 满二叉树一定是完全二叉树
37. 顺序表中数据元素的存取方式为（  ）。 （0 分）