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

李老师

北航《算法与数据结构》在线作业二
试卷总分：100       测试时间：--
单选题  


一、单选题（共 25 道试题，共 100 分。）V 1.  
对于含有n个顶点e条边的无向连通图，利用Prim算法生成最小代价生成树其时间复杂度为( )。

A. O(log2n)
B. O(n2)
C. O(ne)
D. O(elog2e)
      满分：4  分
2.  有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当二分查找值为82的结点时,（ ）次比较后查找成功。
A. 1
B. 2
C. 4
D. 8
      满分：4  分
3.  设在栈中，由顶向下已存放元素c、b、a，在第4个元素d入栈之前，栈中元素可以出栈， 试问d入栈前后，不可能的出栈序列是( )。
A. d c b a
B. c b d a
C. c a d b
D. c d b a
      满分：4  分
4.  若用冒泡排序法对序列（18，14，6，27，8，12，16，52，10，26，47，29，41，24）从小到大进行排序，共要进行（ ）次比较。
A. 33
B. 45
C. 70
D. 91
      满分：4  分
5.  以下时间复杂性不是O(n2)的排序方法是
A. 直接插入排序
B. 二路归并排序
C. 冒泡排序
D. 直接选择排序
      满分：4  分
6.  对于顺序表，以下说法错误的是（ ）
A. 顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址
B. 顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列
C. 顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻
D. 顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中
      满分：4  分
7.  队列操作的原则是（ ）。
A. 先进先出
B. 后进先出
C. 只能进行插入
D. 只能进行删除
      满分：4  分
8.  在一个单链表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;
      满分：4  分
9.  用线性探测法查找闭散列表，可能要探测多个散列地址，这些位置上的键值（ ）
A. 一定都是同义词
B. 一定都不是同义词
C. 都相同
D. 不一定都是同义词
      满分：4  分
10.  顺序表的一个存储结点仅仅存储线性表的一个
A. 数据元素
B. 数据项
C. 数据
D. 数据结构
      满分：4  分
11.  带头节点的单链表 head 为空的判定条件（ ）。
A. head=NULL
B. head->next=NULL
C. head->next=head
D. head!=head
      满分：4  分
12.  线索化二叉树中某结点D，没有左孩子的主要条件是（）。
A. D->Lchild=Null
B. D->ltag=1
C. D->Rchild=Null
D. D->ltag=0
      满分：4  分
13.  算法分析的两个主要方面是（ ）。
A. 空间复杂度和时间复杂度
B. 正确性和简明性
C. 可读性和文档性
D. 数据复杂性和程序复杂性
      满分：4  分
14.  以下关于树的说法错误的是
A. 树形结构的特点是一个结点可以有多个直接前趋
B. 线性结构中的一个结点至多只有一个直接后继
C. 树形结构可以表达(组织)更复杂的数据
D. 树(及一切树形结构)是一种"分支层次"结构
      满分：4  分
15.  根据数据元素之间关系的不同特性，以下四类基本的逻辑结构反映了四类基本的数据组织形式。以下解释错误的是 数据组织形式。以下解释错误的是
A. 集合中任何两个结点之间都有逻辑关系但组织形式松散
B. 线性结构中结点按逻辑关系依次排列形成一条"锁链"
C. 树形结构具有分支、层次特性，其形态有点像自然界中的树
D. 图状结构中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接
      满分：4  分
16.  采用二分查找方法查找长度为n的线性表时,每个元素的平均查找长度为（）
A. O(n2)
B. O(log2n)
C. O(n)
D. O(log2n)
      满分：4  分
17.  排序方法中,从未排序序列中挑选元素并将其依次放入己排序序列(初始为空)的一端的方法,称为（）
A. 希尔排序
B. 归并排序
C. 插入排序
D. 选择排序
      满分：4  分
18.  对下面四个序列用快速排序的方法进行排序，以序列的第一个元素为基础进行划分 。 在第一趟划分过程中，元素移动次数最多的序列是 ()。
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，16，10，68
      满分：4  分
19.  广义表（（a）,a）的表头是（）。
A. a
B. b
C. (a)
D. ((a))
      满分：4  分
20.  指针的全部作用就是
A. 指向某常量
B. 指向某变量
C. 指向某结点
D. 存储某数据
      满分：4  分
21.  对于数据结构课程的主要内容，以下解释正确的是
A. 数据结构的定义，包括逻辑结构、存储结构和基本运算集
B. 数据结构的实现，包括存储实现、运算实现和基本运算集
C. 数据结构的评价和选择，包括逻辑结构的选择、基本运算集的选择和存储选择
D. 以上说法均不正确
      满分：4  分
22.  计算机的算法是（ ）。
A. 计算方法
B. 排序方法
C. 对特定问题求解步骤的一种描述
D. 调度算法
      满分：4  分
23.  在一个顺序队列中，队首指针指向队首元素的（　　）位置。
A. 后一个
B. 前一个
C. 当前
D. 不确定
      满分：4  分
24.  栈的插入和删除操作在（ ）进行。
A. 栈顶
B. 栈底
C. 任意位置
D. 指定位置
      满分：4  分
25.  若给定的关键字集合为{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
      满分：4  分