西南大学 网络与继续教育学院

课程名称：《数据结构》 课程代码：0012 学年学季：20192

单项选择题

1、用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下：

20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 则所采用的排序方法是（ ） A. 选择排序 希尔排序

快速排序.【√】 归并排序

2、不定长文件是指（ ） 记录的长度不固定 关键字项的长度不固定 字段的长度不固定

文件的长度不固定 .【√】

3、如下陈述中正确的是（ ） 串中元素只能是字母 .【√】 串是一种特殊的线性表 串的长度必须大于零 空串就是空白串

4、将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（ ） O（m+n） O（n） O（m）

O（1）.【√】

5、设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（ ） F. front=(front+1)%m.【√】 front=(front-1)%m front=front+1

front=(front+1)%(m-1)

6、计算机算法必须具备输入、输出和等5个特性 易读性、稳定性和安全性

确定性、有穷性和稳定性 可行性、可移植性和可扩充性 可行性、确定性和有穷性.【√】

7、有8个结点的无向图最多有条边 112 56

28.【√】 14

8、不含任何结点的空树 是一棵树 是一棵二叉树

是一棵树也是一棵二叉树.【√】 既不是树也不是二叉树

9、一棵深度为6的满二叉树有个分支结点 30

31.【√】 32 33

10、在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是: O(log2n) O(1).【√】 O(n)

O(nlog2n)

11、若需要在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ ） 快速排序 堆排序

归并排序.【√】 直接插入

12、设哈希表长m=14,哈希函数H(key)=key MOD 11。表中已有4个结点：addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7 其余地址为空，如用二次探测再散列处理冲突，则关键字为49的地址为: 3 5

8.【√】 9

13、设一棵完全二叉树有300个结点，则共有个叶子结点

150.【√】 152 154 156

14、由３个结点所构成的二叉树有 种形态. 2 3 4

5.【√】

15、设有两个串p和q，求q在p中首次出现的位置的运算称作： 连接

模式匹配.【√】 求子串 求串长

16、栈中元素的进出原则是: 先进先出

后进先出.【√】 栈空则进 栈满则出

17、链表是一种采用 存储结构存储的线性表. 顺序 星式

链式.【√】 网状

18、数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为： 存储结构

顺序存储结构.【√】 逻辑结构 链式存储

19、一个具有n个顶点的有向图最多有（ ）条边 n×(n-1)/2

n×(n+1)/2.【√】 n×(n-1) n2

20、判断一个循环队列Q（最多n个元素）为满的条件是: Q->front==(Q->rear+1)%n.【√】 Q->rear==Q->front+1