《16秋北交《数据结构(专)》在线作业一》由会员分享，可在线阅读，更多相关《16秋北交《数据结构(专)》在线作业一（19页珍藏版）》请在金锄头文库上搜索。
1、北交数据结构（专） 在线作业一 一、单选题（共 38 道试题，共 95 分。 ）1. 对某二叉树进行前序遍历的结果为 ABDEFC，中序遍历的结果为 DBFEAC，则后序遍 历的结果为（ ） 。 A. DBFEAC B. DFEBCA C. BDFECA D. BDEFAC 正确答案： 2. 二叉树第 i 层上至多有（）结点。 A. 2i B. 2 的 i 次方 C. 2i-1 D. 2 的 i-1 次方 正确答案： 3. 若某线性表中最常用的操作是取第 I 个元素和找第 I 个元素的前趋元素，则采用( )存储 方式最节省时间。 A. 顺序表 B. 单链表 C. 双链表 D. 单循环链表 正确
2、答案： 4. 由两个栈共享一个向量空间的好处是（ ） 。 A. 减少存取时间，降低下溢发生的机率 B. 节省存储空间，降低上溢发生的机率 C. 减少存取时间，降低上溢发生的机率 D. 节省存储空间，降低下溢发生的机率 正确答案： 5. 从一棵 B_树删除元素的过程中，若最终引起树根结点的合并，则新树高度是（ ） 。 A. 原树高度加 1 B. 原树高度减 1 C. 原树高度 D. 不确定 正确答案： 6. 若让元素 1，2，3 依次进栈，则出栈次序不可能出现（）种情况。 A. 3，2，1B. 2，1，3 C. 3，1，2 D. 1，3，2 正确答案： 7. 判定一个顺序栈（最多元素为 m 个）
3、为空的条件是（ ） 。 A. top0 B. topm C. top!0 D. top!m 正确答案： 8. 具有 2000 个节点的二叉树，其高度至少为（） 。 A. 9 B. 10 C. 11 D. 12 正确答案： 9. 线性表是一个具有 n 个（）的有限序列。 A. 表元素 B. 字符 C. 数据元素 D. 数据项 正确答案： 10. 向一个有 127 个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（ ）个元素。 A. 8 B. 63.5 C. 64 D. 7 正确答案： 11. 对于一个具有 n 个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（ ） 。 A. n
4、B. (n-1)(n-1) C. n-1 D. n*n 正确答案： 12. 线索化二叉树中某结点 D，没有左孩子的主要条件是（） 。 A. D-Lchild=Null B. D-ltag=1 C. D-Rchild=Null D. D-ltag=0 正确答案： 13. 若从二叉树的任一节点出发到根的路径上所经过的节点序列按其关键字有序，则该二 叉树是（ ） 。 A. 二叉排序树B. 哈夫曼树 C. 堆 D. AVL 树 正确答案： 14. 设有 50 行 60 列的二维数组 A5060，其元素长度为 4 字节，按行优先顺序存储， 基地址为 200，则元素 A1825的存储地址为（） 。 A.
5、3700 B. 4376 C. 3900 D. 4620 正确答案： 15. 两个串相等的充分必要条件是（ ） 。 A. 两个串的长度相等 B. 两个串对应位置的字符相等 C. 两个串的长度相等且对应位置的字符相同 D. 以上条件都不正确 正确答案： 16. 下列数据结构中，能用折半查找的是( )。 A. 顺序存储的有序线性表 B. 线性链表 C. 二叉链表 D. 有序线性链表 正确答案： 17. 已知二叉树后序遍历序列是 dabec，中序遍历序列是 debac，它的前序遍历序列是（ ） 。A. acbed B. decab C. deabc D. cedba 正确答案： 18. 设循环队列
6、Q1.N-1的头尾指针为 F，R，当插入元素时尾指针 R 加 1，头指针 F 总 是指在队列中第一个元素的前一个位置，则队列中元素计数为（） 。 A. R-F B. N-（R-F） C. （R-F+N）%N D. （F-R+N）%N 正确答案： 19. 对 n 个记录的文件进行堆排序，最坏情况下的执行时间为 ( )。 A. O(log2n) B. O(nlogn) C. O(n) D. O(n*n) 正确答案： 20. 设有一个 10 阶的对称矩阵 A，采用压缩存储方式，以行序为主的存储，a11 为第一个元素，其存储地址为 1，每个元素占 1 个地址空间，则 a85 的地址为（） 。 A. 1
7、3 B. 18 C. 33 D. 40 正确答案： 21. 设单链表中指针 p 指着结点 A，若要删除 A 之后的结点（若存在） ，则需要修改指针 操作为（） 。 A. P 一nextp 一next 一next B. pP 一next C. pP 一next 一next D. p 一nextp 正确答案： 22. 串的逻辑结构与（ ）的逻辑结构不同。 A. 线性表 B. 栈 C. 队列 D. 树 正确答案： 23. 在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相同的（） 。A. 行号 B. 列号 C. 元素值 D. 地址 正确答案： 24. 一个栈的入栈序列是 a,b,c,
8、d,e,则栈的不可能的输出序列是（） 。 A. edcba B. decba C. abcde D. dceab 正确答案： 25. 数组 A 中，每个元素 A 的长度为 3 个字节，行下标 I 从 1 到 8,列下标 j 从 1 到 10， 从首地址 SA 开始连续存放在存储器内，存放该数组至少需要的单元数为（ ） 。 A. 80 B. 100 C. 240 D. 270 正确答案： 26. 对于含有 n 个顶点 e 条边的无向连通图，利用 Prim 算法生成最小代价生成树其时间 复杂度为( )。 A. O(log2n) B. O(n*n) C. O(ne)D. O(elog2e) 正确答案
9、： 27. 计算机的算法必须具备输入，输出和（ ）五个特性。 A. 可行性，可移植性和可扩充性 B. 可行性，确定性和有穷性 C. 确定性，有穷性和稳定性 D. 易读性，稳定性和安全性 正确答案： 28. 算法分析的两个主要方面是（ ） 。 A. 空间复杂度和时间复杂度 B. 正确性和简明性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 正确答案： 29. 设无向图的顶点个数为 n，则该图最多有（）条边。 A. n-1 B. n(n-1)/2 C. n(n+1)/2 D. 0 正确答案： 30. 邻接表是图的一种（ ） 。 A. 顺序存储结构 B. 链式存储结构 C. 索引存储结构 D.
10、 列存储结构 正确答案： 31. 每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做 （）排序. A. 插入 B. 交换 C. 选择 D. 归并 正确答案： 32. 采用顺序查找方法查找长度为 n 的线性表时，每个元素的平均长度为( ） 。 A. n B. n/2 C. (n+1)/2 D. (n-1)/2 正确答案： 33. 深度为 5 的二叉树至多有（ ）个节点。 A. 16 B. 32 C. 31 D. 10正确答案： 34. Substring(DATA STRUCTURE，5，9)=（ ） 。 A. STRUCTURE B. ASTUCTUR C. DATA
11、STRUCTRUE D. DATA 正确答案： 35. 用某种排序方法队线性表（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. 快速排序 正确答案： 36. 由权值分别为 3,6,7,2,5 的叶子结点生成一棵哈夫曼树，它的带权路
12、径长度为（） 。 A. 23 B. 51 C. 53 D. 74 正确答案： 37. 广义表（a）,a）的表头是（） 。 A. a B. b C. (a) D. (a) 正确答案： 38. 下列那种排序需要的附加存储开销最大（） 。 A. 快速排序 B. 堆排序 C. 归并排序 D. 插入排序 正确答案：北交数据结构（专） 在线作业一 二、判断题（共 2 道试题，共 5 分。 ）1. 线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续? A. 错误 B. 正确 正确答案： 2. 二维数组是其数组元素为线性表的线性表? A. 错误 B. 正确 正确答案：北交数据结构（专） 在线作
13、业一 一、单选题（共 38 道试题，共 95 分。 ）1. 若某线性表中最常用的操作是取第 I 个元素和找第 I 个元素的前趋元素，则采用( )存储 方式最节省时间。 A. 顺序表 B. 单链表 C. 双链表 D. 单循环链表 正确答案： 2. 设在栈中，由顶向下已存放元素 c、b、a，在第 4 个元素 d 入栈之前，栈中元素可以出 栈， 试问 d 入栈前后，不可能的出栈序列是( )。 A. d c b a B. c b d a C. c a d b D. c d b a 正确答案： 3. 若从二叉树的任一节点出发到根的路径上所经过的节点序列按其关键字有序，则该二 叉树是（ ） 。 A. 二叉
14、排序树 B. 哈夫曼树 C. 堆 D. AVL 树 正确答案： 4. 由两个栈共享一个向量空间的好处是（ ） 。 A. 减少存取时间，降低下溢发生的机率 B. 节省存储空间，降低上溢发生的机率 C. 减少存取时间，降低上溢发生的机率 D. 节省存储空间，降低下溢发生的机率正确答案： 5. 设 F 是一个森林，B 是由 F 转换得到的二叉树，F 中有 n 个非叶结点，则 B 中右指针 域为空的结点有（）个。 A. n-1 B. n C. n+1 D. n+2 正确答案： 6. 若让元素 1，2，3 依次进栈，则出栈次序不可能出现（）种情况。 A. 3，2，1 B. 2，1，3 C. 3，1，2
15、D. 1，3，2 正确答案： 7. 设无向图的顶点个数为 n，则该图最多有（）条边。 A. n-1 B. n(n-1)/2 C. n(n+1)/2 D. 0 正确答案： 8. Substring(DATA STRUCTURE，5，9)=（ ） 。 A. STRUCTURE B. ASTUCTUR C. DATA STRUCTRUE D. DATA 正确答案： 9. 设单链表中指针 p 指着结点 A，若要删除 A 之后的结点（若存在） ，则需要修改指针操 作为（） 。 A. P 一nextp 一next 一next B. pP 一next C. pP 一next 一next D. p 一next
16、p 正确答案： 10. 对于一个具有 n 个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（ ） 。 A. n B. (n-1)(n-1) C. n-1 D. n*n 正确答案： 11. 对某二叉树进行前序遍历的结果为 ABDEFC，中序遍历的结果为 DBFEAC，则后序 遍历的结果为（ ） 。 A. DBFEAC B. DFEBCA C. BDFECAD. BDEFAC 正确答案： 12. 每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做 （）排序. A. 插入 B. 交换 C. 选择 D. 归并 正确答案： 13. 对下面四个序列用快速排序的方法进行排序，以序列的第一个元素为基础进行划分 。 在第一趟划分过程中，元素移动次数最多的序列是 ()。 A. 82，75，70，16，10，90，68，23 B
