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

北交《数据结构（专）》在线作业一 一、单选题（共 38 道试题，共 95 分。） 1. 算法的时间复杂度是指（ ）。 . 执行算法程序所需要的时间 . 算法程序的长度 . 算法执行过程中所需要的基本运算次数 . 算法程序中的指令条数 正确答案： 2. 线性表的链接实现有利于（）运算。 . 插入 . 读表元 . 查找 . 定位 正确答案： 3. 若由森林转化得到的二叉树是非空的二叉树，则二叉树形状是 （）。 . 根结点无右子树的二叉树 . 根结点无左子树的二叉树 . 根结点可能有左二叉树和右二叉树 . 各结点只有一个儿子的二叉树 正确答案： 4. 若待排序对象序列在排序前已按其排序码递增顺序排序，则采用（ ）方法比较次数最少。 . 直接插入排序 . 快速排序 . 归并排序 . 直接选择排序 正确答案： 5. 队列操作的原则是（ ）。 . 先进先出 . 后进先出 . 只能进行插入 . 只能进行删除 正确答案： 6. 下列数据结构中，能用折半查找的是( )。 . 顺序存储的有序线性表 . 线性链表 . 二叉链表 . 有序线性链表 正确答案： 7. 非空的循环单链表h的尾节点（由p所指向）满足（ ）。 . p-nxt=NULL . p=NULL . p-nxt=h . p=h 正确答案： 8. 以下关于数据的存储结构的叙述哪一条是正确的（ ）。 . 数据的存储结构是数据间关系的抽象描述 . 数据的存储结构是逻辑结构在计算机存储器中的实现 . 数据的存储结构分为线性结构和非线性结构 . 数据的存储结构对数据运算的具体实现没有影响 正确答案： 9. 在含n个顶点和条边的无向图的邻接矩阵中,零元素的个数为()。 . . 2 . n*n－ . n*n－2 正确答案： 10. 对于含有n个顶点条边的无向连通图，利用Prim算法生成最小代价生成树其时间复杂度为( )。 . O(log2n) . O(n*n) . O(n) . O(log2) 正确答案： 11. 设有向图有n个顶点和条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为（）。 . O（nlog2） . O（n+） . O(n*) . O(n*n) 正确答案： 12. 采用顺序查找方法查找长度为n的线性表时，每个元素的平均长度为( ）。 . n . n/2 . (n+1)/2 . (n-1)/2 正确答案： 13. 判定一个顺序栈（最多元素为m个）为空的条件是（ ）。 . top＝＝0 . top＝＝m . 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=p; 正确答案： 15. 二叉树上叶结点数等于（）。 . 分支结点数加1 . 单分支结点数加1 . 双分支结点数加1 . 双分支结点数减1 正确答案： 16. 顺序查找法适合于存储结构为（）的线性表。 . 散列表 . 顺序存储或链接存储 . 压缩存储 . 索引存储 正确答案： 17. 线性链表不具有的特点是（）。 . 随机访问 . 不必事先估计所需存储空间大小 . 插入与删除时不必移动元素 . 所需空间与线性表长度成正比 正确答案： 18. 从一棵_树删除元素的过程中，若最终引起树根结点的合并，则新树高度是（ ）。 . 原树高度加1 . 原树高度减1 . 原树高度 . 不确定 正确答案： 19. 广义表（（）,）的表头是（）。 . . . () . (()) 正确答案： 20. 如下叙述中正确的是（ ）。 . 串是一种特殊的线性表 . 串的长度必须大于零 . 串中元素只能是字母 . 空串就是空白串 正确答案： 21. 数组中，每个元素的长度为3个字节，行下标I 从1到8,列下标j从1到10，从首地址S开始连续存放在存储器内，存放该数组至少需要的单元数为（ ）。 . 80 . 100 . 240 . 270 正确答案： 22. 完成堆排序的全过程需要 ( )个纪录大小的辅助空间。 . 1 . n . nlog2n . |nlog2n| 正确答案： 23. 按照二叉树的定义，具有3个结点的二叉树有（ ）种。 . 3 . 4 . 5 . 6 正确答案： 24. 在有n个叶子结点的哈夫曼树中，其结点总数为（ ）。 . 不确定 . 2n . 2n+1 . 2n-1 正确答案： 25. 当利用大小为N 的数组顺序存储一个栈时，假定用top = = N表示栈空，则退栈时，用（ ）语句修改top指针。 . top++ . top=0 . top-