16春北航《算法与数据结构》在线作业二.doc

1.?? 对于含有n个顶点条边的无向连通图，利用Prim算法生成最小代价生成树其时间复杂度为( )。 . O(log 2 n) . O(n 2 ) . O(n) . O(log 2 ) 正确答案：??????满分：4??分 2.??有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当二分查找值为82的结点时,（ ）次比较后查找成功。 . 1 . 2 . 4 . 8 正确答案：??????满分：4??分 3.??设在栈中，由顶向下已存放元素、、，在第4个元素入栈之前，栈中元素可以出栈， 试问入栈前后，不可能的出栈序列是( )。 . . . . 正确答案：??????满分：4??分 4.??若用冒泡排序法对序列（18，14，6，27，8，12，16，52，10，26，47，29，41，24）从小到大进行排序，共要进行（ ）次比较。 . 33 . 45 . 70 . 91 正确答案：??????满分：4??分 5.??以下时间复杂性不是O(n2)的排序方法是 . 直接插入排序 . 二路归并排序 . 冒泡排序 . 直接选择排序 正确答案：??????满分：4??分 6.??对于顺序表，以下说法错误的是（ ） . 顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址 . 顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列 . 顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻 . 顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中 正确答案：??????满分：4??分 7.??队列操作的原则是（ ）。 . 先进先出 . 后进先出 . 只能进行插入 . 只能进行删除 正确答案：??????满分：4??分 8.??在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（ ）。 . HL=p;p-gt;nxt=HL; . p-gt;nxt=HL;HL=p; . p-gt;nxt=HL;p=HL; . p-gt;nxt=HL-gt;nxt;HL-gt;nxt=p; 正确答案：??????满分：4??分 9.??用线性探测法查找闭散列表，可能要探测多个散列地址，这些位置上的键值（ ） . 一定都是同义词 . 一定都不是同义词 . 都相同 . 不一定都是同义词 正确答案：??????满分：4??分 10.??顺序表的一个存储结点仅仅存储线性表的一个 . 数据元素 . 数据项 . 数据 . 数据结构 正确答案：??????满分：4??分 11.??带头节点的单链表 h 为空的判定条件（ ）。 . h=NULL . h-gt;nxt=NULL . h-gt;nxt=h . h!=h 正确答案：??????满分：4??分 12.??线索化二叉树中某结点，没有左孩子的主要条件是（）。 . -gt;Lhil=Null . -gt;ltg=1 . -gt;Rhil=Null . -gt;ltg=0 正确答案：??????满分：4??分 13.??算法分析的两个主要方面是（ ）。 . 空间复杂度和时间复杂度 . 正确性和简明性 . 可读性和文档性 . 数据复杂性和程序复杂性 正确答案：??????满分：4??分 14.??以下关于树的说法错误的是 . 树形结构的特点是一个结点可以有多个直接前趋 . 线性结构中的一个结点至多只有一个直接后继 . 树形结构可以表达(组织)更复杂的数据 . 树(及一切树形结构)是一种分支层次结构 正确答案：??????满分：4??分 15.??根据数据元素之间关系的不同特性，以下四类基本的逻辑结构反映了四类基本的 数据组织形式。以下解释错误的是 数据组织形式。以下解释错误的是 . 集合中任何两个结点之间都有逻辑关系但组织形式松散 . 线性结构中结点按逻辑关系依次排列形成一条锁链 . 树形结构具有分支、层次特性，其形态有点像自然界中的树 . 图状结构中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接 正确答案：??????满分：4??分 16.??采用二分查找方法查找长度为n的线性表时,每个元素的平均查找长度为（） . O(n2) . O(log2n) . O(n) . O(log2n) 正确答案：??????满分：4??分 17.??排序方法中,从未排序序列中挑选元素并将其依次放入己排序序列(初始为空)的一端的方法,称为（） . 希尔排序 . 归并排序 . 插入排序 . 选择排序 正确答案：??????满分：4??分 18.??对下面四个序列用快速排序的方法进行排序，以序列的第一个元素为基础进行划分 。 在第一趟划分过程中，元素移动次数最多的序列是 ()。