2016春北交《数据结构(专)》在线作业一

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

1、北交数据结构（专） 在线作业一 一、单选题（共 38 道试题，共 95 分。 ）1. 算法的时间复杂度是指（ ） 。 . 执行算法程序所需要的时间 . 算法程序的长度 . 算法执行过程中所需要的基本运算次数 . 算法程序中的指令条数 正确答案： 2. 线性表的链接实现有利于（）运算。 . 插入 . 读表元 . 查找 . 定位 正确答案： 3. 若由森林转化得到的二叉树是非空的二叉树，则二叉树形状是 （） 。 . 根结点无右子树的二叉树 . 根结点无左子树的二叉树 . 根结点可能有左二叉树和右二叉树 . 各结点只有一个儿子的二叉树 正确答案： 4. 若待排序对象序列在排序前已按其排序码递增顺序排

2、序，则采用（ ）方法比较次数最 少。 . 直接插入排序 . 快速排序 . 归并排序 . 直接选择排序 正确答案： 5. 队列操作的原则是（ ） 。 . 先进先出 . 后进先出 . 只能进行插入 . 只能进行删除 正确答案： 6. 下列数据结构中，能用折半查找的是( )。 . 顺序存储的有序线性表 . 线性链表 . 二叉链表 . 有序线性链表正确答案： 7. 非空的循环单链表 h 的尾节点（由 p 所指向）满足（ ） 。. p-nxt=NULL . p=NULL . p-nxt=h . p=h 正确答案： 8. 以下关于数据的存储结构的叙述哪一条是正确的（ ） 。 . 数据的存储结构是数据间关系

3、的抽象描述 . 数据的存储结构是逻辑结构在计算机存储器中的实现 . 数据的存储结构分为线性结构和非线性结构 . 数据的存储结构对数据运算的具体实现没有影响 正确答案： 9. 在含 n 个顶点和条边的无向图的邻接矩阵中,零元素的个数为()。. . 2 . n*n . n*n2 正确答案： 10. 对于含有 n 个顶点条边的无向连通图，利用 Prim 算法生成最小代价生成树其时间复杂 度为( )。. O(log2n) . O(n*n) . O(n) . O(log2) 正确答案： 11. 设有向图有 n 个顶点和条边，采用领接表作为其存储表示，在进行拓扑排序时，总的 计算时间为（） 。 . O（n

4、log2） . O（n+）. O(n*) . O(n*n) 正确答案： 12. 采用顺序查找方法查找长度为 n 的线性表时，每个元素的平均长度为( ） 。. n . n/2 . (n+1)/2 . (n-1)/2 正确答案： 13. 判定一个顺序栈（最多元素为 m 个）为空的条件是（ ） 。 . top0 . topm . top!0 . top!m正确答案： 14. 在一个单链表 HL 中，若要向表头插入一个由指针 p 指向的结点，则执行（ ） 。. HL=p;p-nxt=HL; . p-nxt=HL;HL=p; . p-nxt=HL;p=HL; . p-nxt=HL-nxt;HL-nxt=

5、p; 正确答案： 15. 二叉树上叶结点数等于（） 。 . 分支结点数加 1 . 单分支结点数加 1 . 双分支结点数加 1 . 双分支结点数减 1 正确答案： 16. 顺序查找法适合于存储结构为（）的线性表。 . 散列表 . 顺序存储或链接存储 . 压缩存储 . 索引存储 正确答案： 17. 线性链表不具有的特点是（） 。 . 随机访问 . 不必事先估计所需存储空间大小 . 插入与删除时不必移动元素 . 所需空间与线性表长度成正比 正确答案： 18. 从一棵_树删除元素的过程中，若最终引起树根结点的合并，则新树高度是（ ） 。 . 原树高度加 1 . 原树高度减 1 . 原树高度 . 不确定

6、 正确答案： 19. 广义表（）,）的表头是（） 。. . . () . () 正确答案： 20. 如下叙述中正确的是（ ） 。 . 串是一种特殊的线性表 . 串的长度必须大于零 . 串中元素只能是字母 . 空串就是空白串 正确答案： 21. 数组中，每个元素的长度为 3 个字节，行下标 I 从 1 到 8,列下标 j 从 1 到 10，从首地址 S 开始连续存放在存储器内，存放该数组至少需要的单元数为（ ） 。. 80 . 100 . 240 . 270 正确答案： 22. 完成堆排序的全过程需要 ( )个纪录大小的辅助空间。. 1 . n . nlog2n . |nlog2n| 正确答案：

7、 23. 按照二叉树的定义，具有 3 个结点的二叉树有（ ）种。. 3 . 4 . 5 . 6 正确答案： 24. 在有 n 个叶子结点的哈夫曼树中，其结点总数为（ ） 。 . 不确定. 2n . 2n+1 . 2n-1 正确答案： 25. 当利用大小为 N 的数组顺序存储一个栈时，假定用 top = = N 表示栈空，则退栈时， 用（ ）语句修改 top 指针。. top+ . top=0 . top- . top=N 正确答案： 26. 设单链表中指针 p 指着结点，若要删除之后的结点（若存在） ，则需要修改指针操作为 （） 。 . P 一nxtp 一nxt 一nxt . pP 一nxt

8、. pP 一nxt 一nxt . p 一nxtp 正确答案： 27. 在线性表的散列存储中，若用 m 表示散列表的长度，n 表示待散列存储的元素的个数， 则装填因子等于（） 。. n/m . m/n . n/(n+m) . m/(n+m)正确答案： 28. 设循环队列 Q1.N-1的头尾指针为 F，R，当插入元素时尾指针 R 加 1，头指针 F 总 是指在队列中第一个元素的前一个位置，则队列中元素计数为（） 。. R-F . N-（R-F） . （R-F+N）%N . （F-R+N）%N 正确答案： 29. 链表不具有的特点是（ ） 。 . 不必事先估计存储空间 . 可随机访问任一元素 . 插

9、入删除不需要移动元素 . 所需空间与线性表长度成正比 正确答案： 30. 树最适合用来表示（ ） 。 . 有序数据元素 . 无序数据元素 . 元素之间具有分支层次关系的数据 . 元素之间无联系的数据 正确答案： 31. 下列关于栈的叙述正确的是（ ） 。 . 栈是非线性结构 . 栈是一种树状结构 . 栈具有先进先出的特征 . 栈具有后进先出的特征 正确答案： 32. 带头节点的单链表 h 为空的判定条件（ ） 。. h=NULL . h-nxt=NULL . h-nxt=h . h!=h 正确答案： 33. 在一个长度为 n 的顺序存储的线性表中，向第 i 个元素（1in+1）之前插入一个新

10、元素时，需要从前向后依次后移（ ）个元素。. n-i . n-i+1 . n-i-1 . i 正确答案： 34. 由权值分别为 3,6,7,2,5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为（） 。. 23 . 51 . 53 . 74正确答案： 35. 关于有向图的邻接表和逆邻接表表示法，下列结论正确的是 （） 。 . 用邻接表表示法计算入度比较方便 . 用邻接表表示法计算入度和出度都方便 . 用逆邻接表表示法计算入度和出度都不方便 . 用逆邻接表表示法计算入度比计算出度方便 正确答案： 36. n 个顶点的连通图至少有（ ）条边。. n-1 . n . n+1 . 0 正确答案： 37

11、. 某二叉树结点的前序序列为、 、 、 、 、G、F，中序遍历为、 、 、 、 、F、G。 该二叉树结点的后 序序列为 ( )。. ,F,G, . ,F,G, . ,G,F, . ,G,F, 正确答案： 38. 算法分析的两个主要方面是（ ） 。 . 空间复杂度和时间复杂度 . 正确性和简明性 . 可读性和文档性 . 数据复杂性和程序复杂性 正确答案：北交数据结构（专） 在线作业一 二、判断题（共 2 道试题，共 5 分。 ）1. 二维数组是其数组元素为线性表的线性表? . 错误 . 正确 正确答案： 2. 线性表的逻辑顺序与物理顺序总是一致的 . 错误 . 正确 正确答案：北交数据结构（专）

12、 在线作业一 一、单选题（共 38 道试题，共 95 分。 ）1. 对下面四个序列用快速排序的方法进行排序，以序列的第一个元素为基础进行划分 。 在第一趟划分过程中，元素移动次数最多的序列是 ()。 . 82，75，70，16，10，90，68，23 . 23，10，16，70，82，75，68，90 . 70，75，68，23，10，16，90，82 . 70，75，82，90，23，16，10，68 正确答案： 2. 算法分析的两个主要方面是（ ） 。 . 空间复杂度和时间复杂度 . 正确性和简明性 . 可读性和文档性 . 数据复杂性和程序复杂性 正确答案： 3. 图的深度优先遍历类似于二

13、叉树的（ ） 。 . 先序遍历 . 中序遍历 . 后序遍历 . 层次遍历 正确答案： 4. 设有一个二元数组mn，假设00存放位置在 644(10)，22存放位置在 676 (10)，每个元素占一个空间，则45在（ ）位置，(10)表明用 10 进数表示。. 692(10) . 626(10) . 709(10) . 724(10) 正确答案： 5. 链表不具有的特点是（ ） 。 . 不必事先估计存储空间 . 可随机访问任一元素 . 插入删除不需要移动元素 . 所需空间与线性表长度成正比 正确答案： 6. 两个串相等的充分必要条件是（ ） 。 . 两个串的长度相等. 两个串对应位置的字符相等

14、. 两个串的长度相等且对应位置的字符相同 . 以上条件都不正确 正确答案： 7. 下列数据结构中，能用折半查找的是( )。 . 顺序存储的有序线性表 . 线性链表 . 二叉链表 . 有序线性链表 正确答案： 8. 向二叉排序树中插入一个元素时，其时间复杂度大致为( )。 . O(log 以 2 为底的 n). O(n) . O(1) . O(n*log2n) 正确答案： 9. 广义表（）,）的表头是（） 。. . . () . () 正确答案： 10. 每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做 （）排序. . 插入 . 交换 . 选择 . 归并 正确答案： 1

15、1. n 个顶点的连通图至少有（ ）条边。. n-1 . n . n+1 . 0 正确答案： 12. 对于含有 n 个顶点条边的无向连通图，利用 Prim 算法生成最小代价生成树其时间复杂 度为( )。. O(log2n) . O(n*n) . O(n) . O(log2) 正确答案： 13. 线性表的链接实现有利于（）运算。 . 插入. 读表元 . 查找 . 定位 正确答案： 14. 数组中，每个元素的长度为 3 个字节，行下标 I 从 1 到 8,列下标 j 从 1 到 10，从首 地址 S 开始连续存放在存储器内，存放该数组至少需要的单元数为（ ） 。. 80 . 100 . 240 .

16、 270 正确答案： 15. 若从二叉树的任一节点出发到根的路径上所经过的节点序列按其关键字有序，则该二 叉树是（ ） 。 . 二叉排序树 . 哈夫曼树 . 堆 . VL 树 正确答案： 16. 无向图的邻接矩阵是一个 ( )。 . 对称矩阵 . 零矩阵 . 上三角矩阵 . 对角矩阵 正确答案： 17. 用某种排序方法队线性表（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 所采用的排序方法是（ ） 。 . 选择排序 . Shll 排序