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

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

1、北交数据结构在线作业一 一、单选题（共 38 道试题，共 95 分。 ）1. 设有一个二元数组mn，假设00存放位置在 644(10)，22存放位置在 676 (10)，每个元素占一个空间，则45在（ ）位置，(10)表明用 10 进数表示。. 692(10) . 626(10) . 709(10) . 724(10) 正确答案： 2. 对下面四个序列用快速排序的方法进行排序，以序列的第一个元素为基础进行划分 。 在第一趟划分过程中，元素移动次数最多的序列是 ()。 . 82，75，70，16，10，90，68，23 . 23，10，16，70，82，75，68，90 . 70，75，68，2

2、3，10，16，90，82 . 70，75，82，90，23，16，10，68 正确答案： 3. 下列那种排序需要的附加存储开销最大（） 。 . 快速排序 . 堆排序 . 归并排序 . 插入排序 正确答案： 4. 顺序查找法适合于存储结构为（）的线性表。 . 散列表 . 顺序存储或链接存储 . 压缩存储 . 索引存储 正确答案： 5. 设单链表中指针 p 指着结点，若要删除之后的结点（若存在） ，则需要修改指针操作为 （） 。 . P 一nxtp 一nxt 一nxt . pP 一nxt . pP 一nxt 一nxt . p 一nxtp 正确答案： 6. 算法分析的目的是（)。 . 找出数据结构

3、的合理性 . 研究算法中的输入和输出的关系. 分析算法的效率以求改进 . 分析算法的易读性和文档性 正确答案： 7. 若给定的关键字集合为20，15，14，18，21，36，40，10，一趟快速排序结束时，键 值的排列为( )。 . 10，15，14，18，20，36，40，21 . 10，15，14，18，20，40，36，21 . 10，15，14，20，18，40，36，21 . 15，10，14，18，20，36，40，21 正确答案： 8. 设有一个 10 阶的对称矩阵，采用压缩存储方式，以行序为主的存储，11 为第一个元素， 其存储地址为 1，每个元素占 1 个地址空间，则 85

4、的地址为（） 。. 13 . 18 . 33 . 40 正确答案： 9. 设有 50 行 60 列的二维数组5060，其元素长度为 4 字节，按行优先顺序存储，基地 址为 200，则元素1825的存储地址为（） 。. 3700 . 4376 . 3900 . 4620 正确答案： 10. 已知二叉树后序遍历序列是，中序遍历序列是，它的前序遍历序列是（ ） 。. . . . 正确答案： 11. 对于一个具有 n 个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（ ） 。. n . (n-1)(n-1) . n-1 . n*n 正确答案： 12. 在稀疏矩阵的带行指针向量的链接存储中，每个行单

5、链表中的结点都具有相同的（） 。 . 行号 . 列号 . 元素值 . 地址 正确答案： 13. 向二叉排序树中插入一个元素时，其时间复杂度大致为( )。 . O(log 以 2 为底的 n). O(n) . O(1) . O(n*log2n) 正确答案： 14. 判定一个顺序栈（最多元素为 m 个）为空的条件是（ ） 。 . top0 . topm . top!0 . top!m 正确答案： 15. 线性表的链接实现有利于（）运算。 . 插入 . 读表元 . 查找 . 定位 正确答案： 16. 用某种排序方法队线性表（25，84，21，47，15，27，68，35，20）进行排序，元素 序列变

6、化如下：（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 排序 . 归并排序 . 快速排序 正确答案： 17. 线性表是一个具有 n 个（）的有限序列。 . 表元素 . 字符 . 数据元素 . 数据项 正确答案： 18. 一个队的入队序列是 1，2，3，4 ，则队列的输出序列是（ ） 。 . 4，3，2，1 . 1，2，3，4 . 1，4，3，2

7、 . 3，2，1，4 正确答案： 19. 具有 65 个结点的完全二叉树其深度为（） 。. 8 . 7 . 6 . 5 正确答案： 20. 采用顺序查找方法查找长度为 n 的线性表时，每个元素的平均长度为( ） 。. n . n/2 . (n+1)/2 . (n-1)/2 正确答案： 21. 线索化二叉树中某结点，没有左孩子的主要条件是（） 。. -Lhil=Null . -ltg=1 . -Rhil=Null . -ltg=0 正确答案： 22. 以下关于数据的存储结构的叙述哪一条是正确的（ ） 。 . 数据的存储结构是数据间关系的抽象描述 . 数据的存储结构是逻辑结构在计算机存储器中的实现

8、 . 数据的存储结构分为线性结构和非线性结构 . 数据的存储结构对数据运算的具体实现没有影响 正确答案： 23. 某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。 . 空或只有一个结点高度等于其结点数 . 任一结点无左孩子 . 任一结点无右孩子 正确答案： 24. 下列数据组织形式中， （ ）的各个结点可以任意邻接。 . 集合 . 树形结构 . 线性结构 . 图状结构 正确答案： 25. n 个顶点的连通图至少有（ ）条边。. n-1 . n . n+1 . 0 正确答案： 26. 当利用大小为 N 的数组顺序存储一个栈时，假定用 top = = N 表示栈空，则退栈时，

9、 用（ ）语句修改 top 指针。. top+ . top=0 . top- . top=N 正确答案： 27. 按照二叉树的定义，具有 3 个结点的二叉树有（ ）种。. 3 . 4. 5 . 6 正确答案： 28. 队列的插入操作是在（ ）进行。 . 队首 . 队尾 . 队前 . 队后 正确答案： 29. 图的深度优先遍历类似于二叉树的（ ） 。 . 先序遍历 . 中序遍历 . 后序遍历 . 层次遍历 正确答案： 30. 算法的时间复杂度是指（ ） 。 . 执行算法程序所需要的时间 . 算法程序的长度 . 算法执行过程中所需要的基本运算次数 . 算法程序中的指令条数 正确答案： 31. 线性

10、链表不具有的特点是（） 。 . 随机访问 . 不必事先估计所需存储空间大小 . 插入与删除时不必移动元素 . 所需空间与线性表长度成正比 正确答案： 32. 在一个长度为 n 的顺序存储的线性表中，向第 i 个元素（1in+1）之前插入一个新 元素时，需要从前向后依次后移（ ）个元素。. n-i . n-i+1 . n-i-1 . i 正确答案： 33. 向一个有 127 个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（ ）个元素。. 8 . 63.5 . 64 . 7 正确答案： 34. 在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是（ ） 。 . Shll 排

11、序 . 起泡排序. 插入排序 . 选择排序 正确答案： 35. 在一个单链表 HL 中，若要向表头插入一个由指针 p 指向的结点，则执行（ ） 。. HL=p;p-nxt=HL; . p-nxt=HL;HL=p; . p-nxt=HL;p=HL; . p-nxt=HL-nxt;HL-nxt=p; 正确答案： 36. 树最适合用来表示（ ） 。 . 有序数据元素 . 无序数据元素 . 元素之间具有分支层次关系的数据 . 元素之间无联系的数据 正确答案： 37. 若某线性表中最常用的操作是取第 I 个元素和找第 I 个元素的前趋元素，则采用( )存 储方式最节省时间。 . 顺序表 . 单链表 .

12、双链表 . 单循环链表 正确答案： 38. 完成堆排序的全过程需要 ( )个纪录大小的辅助空间。. 1 . n . nlog2n . |nlog2n| 正确答案：北交数据结构在线作业一 二、判断题（共 2 道试题，共 5 分。 ）1. 线性表的顺序存储表示优于链式存储表示? . 错误 . 正确 正确答案： 2. 线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续? . 错误. 正确 正确答案：北交数据结构在线作业一 一、单选题（共 38 道试题，共 95 分。 ）1. 对某二叉树进行前序遍历的结果为 F，中序遍历的结果为 F，则后序遍历的结果为（ ） 。. F . F . F

13、. F 正确答案： 2. 深度为 5 的二叉树至多有（ ）个节点。. 16 . 32 . 31 . 10 正确答案： 3. 对 n 个记录的文件进行堆排序，最坏情况下的执行时间为 ( )。. O(log2n) . O(nlogn) . O(n) . O(n*n) 正确答案： 4. 若让元素 1，2，3 依次进栈，则出栈次序不可能出现（）种情况。 . 3，2，1 . 2，1，3 . 3，1，2 . 1，3，2 正确答案： 5. 具有 65 个结点的完全二叉树其深度为（） 。. 8 . 7 . 6 . 5 正确答案： 6. 下列数据组织形式中， （ ）的各个结点可以任意邻接。. 集合 . 树形结构

14、 . 线性结构 . 图状结构 正确答案： 7. 向一个有 127 个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（ ）个元素。. 8 . 63.5 . 64 . 7 正确答案： 8. 图的深度优先遍历类似于二叉树的（ ） 。 . 先序遍历 . 中序遍历 . 后序遍历 . 层次遍历 正确答案： 9. 无向图的邻接矩阵是一个 ( )。 . 对称矩阵 . 零矩阵 . 上三角矩阵 . 对角矩阵 正确答案： 10. 由两个栈共享一个向量空间的好处是（ ） 。 . 减少存取时间，降低下溢发生的机率 . 节省存储空间，降低上溢发生的机率 . 减少存取时间，降低上溢发生的机率 . 节省存储空间，

15、降低下溢发生的机率 正确答案： 11. 在线性表的散列存储中，若用 m 表示散列表的长度，n 表示待散列存储的元素的个数， 则装填因子等于（） 。. n/m . m/n . n/(n+m) . m/(n+m) 正确答案： 12. 在一个单链表 HL 中，若要向表头插入一个由指针 p 指向的结点，则执行（ ） 。. HL=p;p-nxt=HL; . p-nxt=HL;HL=p; . p-nxt=HL;p=HL; . p-nxt=HL-nxt;HL-nxt=p; 正确答案： 13. 设有 1000 个元素，用折半查找时，最大比较次数是（） 。. 1 . 7 . 10 . 25 正确答案： 14.

16、一个有顺序表有 255 个对象，采用顺序搜索法查表，平均搜索长度为（ ） 。. 128 . 127 . 126 . 255 正确答案： 15. 线性表的链接实现有利于（）运算。 . 插入 . 读表元 . 查找 . 定位 正确答案： 16. 设有一个 10 阶的对称矩阵，采用压缩存储方式，以行序为主的存储，11 为第一个元 素，其存储地址为 1，每个元素占 1 个地址空间，则 85 的地址为（） 。. 13 . 18 . 33 . 40 正确答案： 17. 下列关于栈的叙述正确的是（ ） 。 . 栈是非线性结构 . 栈是一种树状结构 . 栈具有先进先出的特征 . 栈具有后进先出的特征 正确答案： 18. 串的逻辑结构与（ ）的逻辑结构不同。 . 线性表 . 栈 . 队列 . 树 正确答案： 19. 队列的删除操作是在（