16秋北交《数据结构(专)》在线作业二

《16秋北交《数据结构(专)》在线作业二》由会员分享，可在线阅读，更多相关《16秋北交《数据结构(专)》在线作业二（19页珍藏版）》请在金锄头文库上搜索。

1、北交数据结构（专） 在线作业二一、单选题（共 38 道试题，共 95 分。 ）1. 在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是（ ） 。 A. Shell 排序 B. 起泡排序 C. 插入排序 D. 选择排序 正确答案： 2. 对 n 个记录的文件进行堆排序，最坏情况下的执行时间为 ( )。 A. O(log2n) B. O(nlogn) C. O(n) D. O(n*n) 正确答案： 3. 在线性表的散列存储中，若用 m 表示散列表的长度，n 表示待散列存储的元素的个数， 则装填因子 a 等于（） 。 A. n/m B. m/n C. n/(n+m) D. m/(n+m)

2、 正确答案： 4. 线性表是一个具有 n 个（）的有限序列。 A. 表元素 B. 字符 C. 数据元素 D. 数据项 正确答案： 5. 在一个单链表 HL 中，若要向表头插入一个由指针 p 指向的结点，则执行（ ） 。 A. HL=p;p-next=HL; B. p-next=HL;HL=p; C. p-next=HL;p=HL; D. p-next=HL-next;HL-next=p; 正确答案： 6. 设有 50 行 60 列的二维数组 A5060，其元素长度为 4 字节，按行优先顺序存储，基 地址为 200，则元素 A1825的存储地址为（） 。 A. 3700B. 4376 C. 39

3、00 D. 4620 正确答案： 7. 广义表（a）,a）的表头是（） 。 A. a B. b C. (a) D. (a) 正确答案： 8. 计算机的算法是（ ） 。 A. 计算方法 B. 排序方法 C. 对特定问题求解步骤的一种描述 D. 调度算法 正确答案： 9. 两个串相等的充分必要条件是（ ） 。 A. 两个串的长度相等 B. 两个串对应位置的字符相等 C. 两个串的长度相等且对应位置的字符相同 D. 以上条件都不正确 正确答案： 10. 判定一个顺序栈（最多元素为 m 个）为空的条件是（ ） 。 A. top0 B. topm C. top!0 D. top!m 正确答案： 11.

4、若某线性表中最常用的操作是取第 I 个元素和找第 I 个元素的前趋元素，则采用( )存 储方式最节省时间。 A. 顺序表 B. 单链表 C. 双链表 D. 单循环链表 正确答案： 12. 当利用大小为 N 的数组顺序存储一个栈时，假定用 top = = N 表示栈空，则退栈时， 用（ ）语句修改 top 指针。 A. top+ B. top=0 C. top- D. top=N 正确答案： 13. 设单链表中指针 p 指着结点 A，若要删除 A 之后的结点（若存在） ，则需要修改指针 操作为（） 。A. P 一nextp 一next 一next B. pP 一next C. pP 一next

5、一next D. p 一nextp 正确答案： 14. 在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相同的（） 。A. 行号 B. 列号 C. 元素值 D. 地址 正确答案： 15. 算法分析的两个主要方面是（ ） 。 A. 空间复杂度和时间复杂度 B. 正确性和简明性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 正确答案： 16. 在含 n 个顶点和 e 条边的无向图的邻接矩阵中,零元素的个数为()。 A. e B. 2e C. n*ne D. n*n2e 正确答案： 17. 对于一个具有 n 个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（ ） 。 A.

6、n B. (n-1)(n-1) C. n-1 D. n*n 正确答案： 18. 计算机的算法必须具备输入，输出和（ ）五个特性。 A. 可行性，可移植性和可扩充性 B. 可行性，确定性和有穷性 C. 确定性，有穷性和稳定性 D. 易读性，稳定性和安全性 正确答案： 19. 无向图的邻接矩阵是一个 ( )。 A. 对称矩阵 B. 零矩阵 C. 上三角矩阵 D. 对角矩阵 正确答案： 20. 一个队的入队序列是 1，2，3，4 ，则队列的输出序列是（ ） 。 A. 4，3，2，1B. 1，2，3，4 C. 1，4，3，2 D. 3，2，1，4 正确答案： 21. 如果待排序序列中两个数据元素具有相

7、同的值，在排序后它们的位置发生颠倒，则称 该排序是不稳定的。下列选项中， （）就是不稳定的排序方法。 A. 起泡排序 B. 归并排序 C. 直接插入法排序 D. 简单选择排序 正确答案： 22. 若给定的关键字集合为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 正确答案： 23. 已知二叉树后序遍历序列是 dabec，中序遍历序列是 d

8、ebac，它的前序遍历序列是（ ） 。A. acbed B. decab C. deabc D. cedba 正确答案： 24. 完成堆排序的全过程需要 ( )个纪录大小的辅助空间。 A. 1 B. n C. nlog2n D. |nlog2n| 正确答案： 25. 对下面四个序列用快速排序的方法进行排序，以序列的第一个元素为基础进行划分 。 在第一趟划分过程中，元素移动次数最多的序列是 ()。 A. 82，75，70，16，10，90，68，23 B. 23，10，16，70，82，75，68，90 C. 70，75，68，23，10，16，90，82 D. 70，75，82，90，23，1

9、6，10，68 正确答案： 26. 设 F 是一个森林，B 是由 F 转换得到的二叉树，F 中有 n 个非叶结点，则 B 中右指针 域为空的结点有（）个。 A. n-1 B. n C. n+1 D. n+2正确答案： 27. 算法的时间复杂度是指（ ） 。 A. 执行算法程序所需要的时间 B. 算法程序的长度 C. 算法执行过程中所需要的基本运算次数 D. 算法程序中的指令条数 正确答案： 28. 在有 n 个叶子结点的哈夫曼树中，其结点总数为（ ） 。 A. 不确定 B. 2n C. 2n+1 D. 2n-1 正确答案： 29. 下列关于栈的叙述正确的是（ ） 。 A. 栈是非线性结构 B.

10、 栈是一种树状结构 C. 栈具有先进先出的特征 D. 栈具有后进先出的特征 正确答案： 30. 具有 65 个结点的完全二叉树其深度为（） 。 A. 8 B. 7 C. 6 D. 5 正确答案： 31. 为了最快地对线性结构的数据进行某数据元素的读取操作，则其数据存储结构宜采用 ( )方式。 A. 顺序存储 B. 链式存储 C. 索引存储 D. 散列存储 正确答案： 32. 设无向图的顶点个数为 n，则该图最多有（）条边。 A. n-1 B. n(n-1)/2 C. n(n+1)/2 D. 0 正确答案： 33. 一个栈的入栈序列是 a,b,c,d,e,则栈的不可能的输出序列是（） 。 A.

11、edcba B. decba C. abcde D. dceab 正确答案：34. 每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做 （）排序. A. 插入 B. 交换 C. 选择 D. 归并 正确答案： 35. 二叉树第 i 层上至多有（）结点。 A. 2i B. 2 的 i 次方 C. 2i-1 D. 2 的 i-1 次方 正确答案： 36. 某二叉树结点的前序序列为 E、A、C、B、D、G、F，中序遍历为 A、B、C、D、E、F、G。 该二叉树结点的后序序列为 ( )。 A. B,D,C,A,F,G,E B. B,D,C,F,A,G,E C. E,G,F,A,C

12、,D,B D. E,G,A,C,D,F,B 正确答案： 37. 数组 A 中，每个元素 A 的长度为 3 个字节，行下标 I 从 1 到 8,列下标 j 从 1 到 10， 从首地址 SA 开始连续存放在存储器内，存放该数组至少需要的单元数为（ ） 。 A. 80 B. 100 C. 240 D. 270 正确答案： 38. 二叉树上叶结点数等于（） 。 A. 分支结点数加 1 B. 单分支结点数加 1 C. 双分支结点数加 1 D. 双分支结点数减 1 正确答案：北交数据结构（专） 在线作业二二、判断题（共 2 道试题，共 5 分。 ）1. 线性表的逻辑顺序与物理顺序总是一致的A. 错误 B

13、. 正确 正确答案： 2. 线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续? A. 错误 B. 正确 正确答案：北交数据结构（专） 在线作业二一、单选题（共 38 道试题，共 95 分。 ）1. 线性表是一个具有 n 个（）的有限序列。 A. 表元素 B. 字符 C. 数据元素 D. 数据项 正确答案： 2. 按照二叉树的定义，具有 3 个结点的二叉树有（ ）种。 A. 3 B. 4 C. 5 D. 6 正确答案： 3. 由权值分别为 3,6,7,2,5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为（） 。 A. 23 B. 51 C. 53 D. 74 正确答案： 4.

14、 在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相同的（） 。 A. 行号 B. 列号 C. 元素值 D. 地址 正确答案： 5. 队列的删除操作是在（ ）进行。 A. 队首 B. 队尾C. 队前 D. 队后 正确答案： 6. 由两个栈共享一个向量空间的好处是（ ） 。 A. 减少存取时间，降低下溢发生的机率 B. 节省存储空间，降低上溢发生的机率 C. 减少存取时间，降低上溢发生的机率 D. 节省存储空间，降低下溢发生的机率 正确答案： 7. 深度为 5 的二叉树至多有（ ）个节点。 A. 16 B. 32 C. 31 D. 10 正确答案： 8. 采用顺序查找方法查找长度

15、为 n 的线性表时，每个元素的平均长度为( ） 。 A. n B. n/2 C. (n+1)/2 D. (n-1)/2 正确答案： 9. 如果只想得到 1024 个元素组成的序列中第 5 个最小元素之前的部分排序的序列，用（ ）方法最快。 A. 起泡排序 B. 快速排序 C. 简单选择排序 D. 堆排序 正确答案： 10. 每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做 （）排序. A. 插入 B. 交换 C. 选择 D. 归并 正确答案： 11. 若由森林转化得到的二叉树是非空的二叉树，则二叉树形状是 （） 。 A. 根结点无右子树的二叉树 B. 根结点无左子树的

16、二叉树 C. 根结点可能有左二叉树和右二叉树 D. 各结点只有一个儿子的二叉树 正确答案： 12. 图的深度优先遍历类似于二叉树的（ ） 。 A. 先序遍历 B. 中序遍历C. 后序遍历 D. 层次遍历 正确答案： 13. 如果一个树中，结点 A 有 3 个兄弟，而且 B 为 A 的双亲，则 B 的度为（ ） 。 A. 1 B. 3 C. 4 D. 5 正确答案： 14. 设循环队列 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 正确答案： 15. Substring(DATA STRUCTURE，5，9)=（ ） 。 A. STRUCTURE B. ASTUCTUR C. DA