内容发布更新时间 : 2024/4/19 14:26:05星期一 下面是文章的全部内容请认真阅读。

西安交通大学17年3月课程考试《数据结构》作业考核试题

一、单选题（共 30 道试题，共 60 分。）

1. 与数据元素本身的形式、内容、相对位置、个数无关的是数据的（） A. 存储结构 B. 逻辑结构 C. 算法 D. 操作

正确答案：B

2. 设一棵完全二叉树中有65个结点，则该完全二叉树的深度为（）。 A. 8 B. 7 C. 6 D. 5

正确答案：B

3. 利用直接插入排序法的思想建立一个有序线性表的时间复杂度为（）。 A. O(n)

B. O(nlog2n) C. O(n)

D. O(1og2n) 正确答案：C

4. 栈的插入和删除操作在（）进行。 A. 栈顶 B. 栈底

C. 任意位置 D. 指定位置 正确答案：A

5. 二路归并排序的时间复杂度为（）。

A. O(n) B. O(n)

C. O(nlog2n) D. O(1og2n) 正确答案：C

6. 设某强连通图中有n个顶点，则该强连通图中至少有（）条边。

A. n(n-1) B. n+1 C. n

D. n(n+1) 正确答案：C

7. 设一个顺序有序表A[1:14]中有14个元素，则采用二分法查找元素A[4]的过程中比较元

素的顺序为（）

A. A[1]，A[2]，A[3]，A[4] B. A[1]，A[14]，A[7]，A[4] C. A[7]，A[3]，A[5]，A[4] D. A[7]，A[5]，A[3]，A[4] 正确答案：C

8. 下列各种排序算法中平均时间复杂度为O（n）是（）。 A. 快速排序 B. 堆排序 C. 归并排序 D. 冒泡排序 正确答案：D

9. 如下陈述中正确的是（） A. 串是一种特殊的线性表 B. 串的长度必须大于零 C. 串中元素只能是字母 D. 空串就是空白串 正确答案：A

10. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置（）？脚注(10)表示用10进制表示。

A. 688 B. 678 C. 692 D. 696

正确答案：C

11. 适于对动态查找表进行高效率查找的组织结构是（） A. 有序表 B. 分块有序表 C. 三叉排序树 D. 线性链表 正确答案：C

12. 设某完全无向图中有n个顶点，则该完全无向图中有（）条边。

A. n(n-1)/2 B. n(n-1) C. n D. n-1

正确答案：A

13. 设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为（）。 A. O(n+e) B. O(n) C. O(ne) D. O(n)

正确答案：A

14. 在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p之间插入一个s所指的结点,则执行（）。

A. s→link=p→link;p→link=s B. p→link=s;s→link=q

C. p→link=s→link;s→link=p D. q→link=s;s→link=p 正确答案：D

15. 设某哈夫曼树中有199个结点，则该哈夫曼树中有（）个叶子结点。

A. 99 B. 100 C. 101 D. 102

正确答案：B

16. 若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为（） A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 正确答案：D

17. 用链表表示线性表的优点是（） A. 便于随机存取

B. 花费的存储空间比顺序表少 C. 便于插入与删除

D. 数据元素的物理顺序与逻辑顺序相同 正确答案：C

18. 设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为（）。

A. 2i+1 B. 2i C. i/2 D. 2i-1

正确答案：B

19. 设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（）。 A. 空或只有一个结点 B. 高度等于其结点数 C. 任一结点无左孩子 D. 任一结点无右孩子 正确答案：D

20. 对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（）=K%9作为散列函数，则散列地址为1的元素有（）个 A. 1 B. 2 C. 3