13春北京交通大学《数据结构》在线作业二

北交《数据结构》在线作业二
试卷总分：100
单选题
判断题
一、单选题（共 38 道试题，共 95 分。）
V
1. 下列数据结构中，能用折半查找的是( )。
A. 顺序存储的有序线性表
B. 线性链表
C. 二叉链表
D. 有序线性链表
满分：2.5 分
2. 若待排序对象序列在排序前已按其排序码递增顺序排序，则采用（ ）方法比较次数最少。
A. 直接插入排序
B. 快速排序
C. 归并排序
D. 直接选择排序
满分：2.5 分
3. 设有两个串（S1和S2），求S1在S2中首次出现的位置的运算称为（）。
A. 连接
B. 模式匹配
C. 求子串
D. 求串长
满分：2.5 分
4. 为了最快地对线性结构的数据进行某数据元素的读取操作，则其数据存储结构宜采用( )方式。
A. 顺序存储
B. 链式存储
C. 索引存储
D. 散列存储
满分：2.5 分
5. 设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶结点，则B中右指针域为空的结点有（）个。
A. n-1
B. n
C. n+1
D. n+2
满分：2.5 分
6. 设有向图有n个顶点和e条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为（）。
A. O（nlog2e）
B. O（n+e）
C. O(n*e)
D. O(n*n)
满分：2.5 分
7. 队列的插入操作是在（ ）进行。
A. 队首
B. 队尾
C. 队前
D. 队后
满分：2.5 分
8. 非空的循环单链表head的尾节点（由p所指向）满足（ ）。
A. p- next=NULL
B. p=NULL
C. p- next=head
D. p=head
满分：2.5 分
9. 串的长度是（ ）。
A. 串中不同字符的个数
B. 串中不同字母的个数
C. 串中所含字符的个数且字符个数大于0
D. 串中所含字符的个数
此题选: D 满分：2.5 分
10. Substring(DATA STRUCTURE，5，9)=（ ）。
A. STRUCTURE
B. ASTUCTUR
C. DATA STRUCTRUE
D. DATA
满分：2.5 分
11. 线性表是一个具有n个（）的有限序列。
A. 表元素
B. 字符
C. 数据元素
D. 数据项
满分：2.5 分
12. 算法分析的两个主要方面是（ ）。
A. 空间复杂度和时间复杂度
B. 正确性和简明性
C. 可读性和文档性
D. 数据复杂性和程序复杂性
满分：2.5 分
13. 顺序表中逻辑上相邻的节点其物理位置也（ ）。
A. 一定相邻
B. 不必相邻
C. 按某种规律排列
D. 无要求
满分：2.5 分
14. 线性链表不具有的特点是（）。
A. 随机访问
B. 不必事先估计所需存储空间大小
C. 插入与删除时不必移动元素
D. 所需空间与线性表长度成正比
满分：2.5 分
15. 队列的删除操作是在（ ）进行。
A. 队首
B. 队尾
C. 队前
D. 队后
满分：2.5 分
16. 如下叙述中正确的是（ ）。
A. 串是一种特殊的线性表
B. 串的长度必须大于零
C. 串中元素只能是字母
D. 空串就是空白串
满分：2.5 分
17. 向二叉排序树中插入一个元素时，其时间复杂度大致为( )。
A. O(log以2为底的n)
B. O(n)
C. O(1)
D. O(n*log2n)
满分：2.5 分
18. 带头节点的单链表 head 为空的判定条件（ ）。
A. head=NULL
B. head- next=NULL
C. head- next=head
D. head!=head
满分：2.5 分
19. 在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为()。
A. e
B. 2e
C. n*n－e
D. n*n－2e
此题选: D 满分：2.5 分
20. 以下关于数据的存储结构的叙述哪一条是正确的（ ）。
A. 数据的存储结构是数据间关系的抽象描述
B. 数据的存储结构是逻辑结构在计算机存储器中的实现
C. 数据的存储结构分为线性结构和非线性结构
D. 数据的存储结构对数据运算的具体实现没有影响
满分：2.5 分
21. 从一棵B_树删除元素的过程中，若最终引起树根结点的合并，则新树高度是（ ）。
A. 原树高度加1
B. 原树高度减1
C. 原树高度
D. 不确定
满分：2.5 分
22. 在线性表的散列存储中，若用m表示散列表的长度，n表示待散列存储的元素的个数，则装填因子a等于（）。
A. n/m
B. m/n
C. n/(n+m)
D. m/(n+m)
满分：2.5 分
23. 向顺序栈中压入新元素时，应当（ ）。
A. 先移动栈顶指针，再存入元素
B. 先存入元素，再移动栈顶指针
C. 先后次序无关紧要
D. 同时进行
满分：2.5 分
24. 已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（ ）。
A. acbed
B. decab
C. deabc
D. cedba
此题选: D 满分：2.5 分
25. 对某二叉树进行前序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果为（ ）。
A. DBFEAC
B. DFEBCA
C. BDFECA
D. BDEFAC
满分：2.5 分
26. 对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（ ）。
A. n
B. (n-1)(n-1)
C. n-1
D. n*n
此题选: D 满分：2.5 分
27. 设有1000个元素，用折半查找时，最大比较次数是（）。
A. 1
B. 7
C. 10
D. 25
满分：2.5 分
28. 用某种排序方法队线性表（25，84，21，47，15，27，68，35，20）进行排序，元素序列变化如下：（1）25，84，21，47，15，27，68，35，20 （2）20，15，21，25，47，27，68，35，84 （3）15，20，21，25，35，27，47，68，84 （4）15，20，21，25，27，35，47，68，84 所采用的排序方法是（ ）。
A. 选择排序
B. Shell排序
C. 归并排序
D. 快速排序
此题选: D 满分：2.5 分
29. 两个串相等的充分必要条件是（ ）。
A. 两个串的长度相等
B. 两个串对应位置的字符相等
C. 两个串的长度相等且对应位置的字符相同
D. 以上条件都不正确
满分：2.5 分
30. 下列那种排序需要的附加存储开销最大（）。
A. 快速排序
B. 堆排序
C. 归并排序
D. 插入排序
满分：2.5 分
31. 若给定的关键字集合为{20，15，14，18，21，36，40，10}，一趟快速排序结束时，键值的排列为( )。
A. 10，15，14，18，20，36，40，21
B. 10，15，14，18，20，40，36，21
C. 10，15，14，20，18，40，36，21
D. 15，10，14，18，20，36，40，21
满分：2.5 分
32. 在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是（ ）。
A. Shell排序
B. 起泡排序
C. 插入排序
D. 选择排序
此题选: D 满分：2.5 分
33. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（ ）个元素。
A. 8
B. 63.5
C. 64
D. 7
满分：2.5 分
34. 由两个栈共享一个向量空间的好处是（ ）。
A. 减少存取时间，降低下溢发生的机率
B. 节省存储空间，降低上溢发生的机率
C. 减少存取时间，降低上溢发生的机率
D. 节省存储空间，降低下溢发生的机率
满分：2.5 分
35. 每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做（）排序.
A. 插入
B. 交换
C. 选择
D. 归并
满分：2.5 分
36. n个顶点的连通图至少有（ ）条边。
A. n-1
B. n
C. n+1
D. 0
满分：2.5 分
37. 对n个记录的文件进行堆排序，最坏情况下的执行时间为 ( )。
A. O(log2n)
B. O(nlogn)
C. O(n)
D. O(n*n)
满分：2.5 分
38. 判定一个顺序栈（最多元素为m个）为空的条件是（ ）。
A. top＝＝0
B. top＝＝m
C. top!＝0
D. top!＝m
满分：2.5 分
北交《数据结构》在线作业二
试卷总分：100
单选题
判断题
二、判断题（共 2 道试题，共 5 分。）
V
1. 线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续?
A. 错误
B. 正确
满分：2.5 分
2. 线性表的逻辑顺序与物理顺序总是一致的
A. 错误
B. 正确
满分：2.5 分