北京理工大学《实用数据结构与算法》在线作业三

奥鹏北京理工大学新学期作业参考

北理工《实用数据结构与算法》在线作业-00003

1.下列排序算法中，其中()是稳定的。
选项A：堆排序，冒泡排序
选项B：快速排序，堆排序
选项C：直接选择排序，希尔排序
选项D：归并排序，冒泡排序
正确答案问询微信：424329

2.有一个有序表为｛1，3，9，12，32，41，45，62，75，77，82，95，100｝，当采用折半查找值为82的节点时，()次比较后查找成功。
选项A：1
选项B：2
选项C：4
选项D：8
正确答案问询微信：424329

3.一棵高度（假定树根结点为第0层）为4的完全二叉树中的结点数最少为()。
选项A：15
选项B：16
选项C：17
选项D：31
正确答案问询微信：424329

4.根据二叉树的定义可知二叉树共有()种不同的形态。
选项A：4
选项B：5
选项C：6
选项D：7
正确答案问询微信：424329

5.设有7000个无序的元素,希望用最快的速度挑选出其中前5个最大的元素,最好选用()法。
选项A：冒泡排序
选项B：快速排序
选项C：堆排序
选项D：基数排序
正确答案问询微信：424329

6.设有一个长度为80的已排好序的表，用二分查找法进行查找，若查找不成功，至少比较()次。
选项A：9
选项B：8
选项C：7
选项D：6
正确答案问询微信：424329

7.具有线性结构的数据结构是()
选项A：赫夫曼树
选项B：栈
选项C：图
选项D：树
正确答案问询微信：424329

8.稀疏矩阵一般的压缩存储方法有两种，即()。
选项A：二维数组和三维数组
选项B：三元组表和散列表
选项C：三元组表和十字链表
选项D：散列表和十字链表
正确答案问询微信：424329

9.设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为()
选项A：abedfc
选项B：acfebd
选项C：aebdfc
选项D：aedfcb
正确答案问询微信：424329

10.从1000个元素中选出其中五个最大值元素()排序最适合。
选项A：冒泡
选项B：快速排序
选项C：堆排序
选项D：选择排序
正确答案问询微信：424329

11.对于经常要存取线性表任意指定位置元素的应用，线性表应采用()存储结构。
选项A：顺序存储结构
选项B：链式存储结构
选项C：线性链表
选项D：栈
正确答案问询微信：424329

12.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为()排序法。
选项A：插入
选项B：选择
选项C：交换
选项D：二路归并
正确答案问询微信：424329

13.一个具有767个结点的完全二叉树，其叶子结点个数为()。
选项A：383
选项B：384
选项C：385
选项D：386
正确答案问询微信：424329

14.快速排序属于那种排序类型()。
选项A：选择排序
选项B：插入排序
选项C：交换排序
选项D：基数排序
正确答案问询微信：424329

15.含4个结点（元素值均不相同）的二叉搜索树有()种。
选项A：12
选项B：14
选项C：5
选项D：15
正确答案问询微信：424329

16.对哈希(HASH)函数H(k)= k MOD m, 一般来说，m应取()。
选项A：素数
选项B：很大的数
选项C：偶数
选项D：奇数
正确答案问询微信：424329

17.当两个元素比较出现反序时就相互交换位置的排序方法称为()。
选项A：归并排序
选项B：选择排序
选项C：交换排序
选项D：插入排序
正确答案问询微信：424329

18.任何一个无向连通图的最小生成树()。
选项A：只有一棵
选项B：有一棵或多棵
选项C：一定有多棵
选项D：可能不存在
正确答案问询微信：424329

19.开放定址法中，增量序列的取法不包括()
选项A：线性探测再散列
选项B：委随机探测再散列
选项C：二次探测再散列
选项D：随机探测再散列
正确答案问询微信：424329

20.学习数据结构主要目的是()。
选项A：处理数值计算问题
选项B：研究程序设计技巧
选项C：选取合适数据结构，写出更有效的算法
选项D：是计算机硬件课程的基础
正确答案问询微信：424329

21.以下说法错误的是（）
选项A：数据元素是数据的最小单位
选项B：数据项是数据的基本单位
选项C：数据结构是带有结构的各数据项的集合
选项D：数据结构是带有结构的数据元素的集合
正确答案问询微信：424329

22.下述哪些不是顺序存储结构的优点？（）
选项A：存储密度大
选项B：插入运算方便
选项C：删除运算方便
选项D：可方便地用于各种逻辑结构的存储表示
正确答案问询微信：424329

23.对线性表，可进行如下基本操作（）
选项A：随机存取
选项B：插入
选项C：删除
选项D：查找
正确答案问询微信：424329

24.下面关于求关键路径的说法正确的是（）
选项A：求关键路径是以拓扑排序为基础的
选项B：一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同
选项C：一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差
选项D：关键活动一定位于关键路径上
正确答案问询微信：424329

25.下面关于串的的叙述中，正确的是（）
选项A：串是字符的有限序列
选项B：空串是由空格构成的串
选项C：模式匹配是串的一种重要运算
选项D：串既可以采用顺序存储，也可以采用链式存储
正确答案问询微信：424329

26.在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形可能出现的是（）
选项A：G中有弧Vi，Vj
选项B：G中有一条从Vi到Vj的路径
选项C：G中没有Vi,Vj
选项D：G中有一条从Vj到Vi的路径
正确答案问询微信：424329

27.图的存储结构有（）
选项A：邻接矩阵
奥鹏北京理工大学新学期作业参考选项B：邻接表
选项C：数组表示法
选项D：十字链表
正确答案问询微信：424329

28.对于顺序表的优缺点，以下说法正确的是（）
选项A：无需为表示结点间的逻辑关系而增加额外的存储空间
选项B：可以方便地随机存取表中的任一结点
选项C：插入和删除运算较方便
选项D：由于顺序表要求占用连续的空间，存储分配只能预先进行(静态分配)
正确答案问询微信：424329

29.单链表表示法的基本思想是指针P表示结点间的逻辑关系，则以下说法正确的是（）
选项A：任何指针都不能用打印语句输出一个指针型变量的值
选项B：如果要引用(如访问)p所指结点，只需写出p(以后跟域名)即可
选项C：若想修改变量p的值(比如让P指向另一个结点)，则应直接对p赋值
选项D：对于一个指针型变量P的值。只需知道它指的是哪个结点
正确答案问询微信：424329

30.下列说法正确的是（）
选项A：栈是限定在表尾进行插入或删除操作的线性表
选项B：栈是限定在表头进行插入或删除操作的线性表
选项C：对列是先进先出的线性表
选项D：栈是后进先出的线性表
正确答案问询微信：424329

31.线性表的逻辑顺序与物理顺序总是一致的。
选项A：错误
选项B：正确
正确答案问询微信：424329

32.快速排序是排序算法中平均性能最好的一种排序。
选项A：错误
选项B：正确
正确答案问询微信：424329

33.层次遍历初始堆可以得到一个有序的序列。
选项A：错误
选项B：正确
正确答案问询微信：424329

34.顺序查找法适用于存储结构为顺序或链接存储的线性表。
选项A：错误
选项B：正确
正确答案问询微信：424329

35.在单链表中，要访问某个结点，只要知道该结点的指针即可；因此，单链表是一种随机存取结构。
选项A：错误
选项B：正确
正确答案问询微信：424329

36.完全二叉树的某结点若没有左孩子，则它必是叶子结点。
选项A：错误
选项B：正确
正确答案问询微信：424329

37.中序遍历二叉排序树可以得到一个有序的序列。
选项A：错误
选项B：正确
正确答案问询微信：424329

38.广义表中原子个数即为广义表的长度。
选项A：错误
选项B：正确
正确答案问询微信：424329

39.哈夫曼树是带权路径最短的树,路径上权值较大的结点离根较近。
选项A：错误
选项B：正确
正确答案问询微信：424329

40.完全二叉树中，若一个结点没有左孩子，则它必是树叶。
选项A：错误
选项B：正确
正确答案问询微信：424329

41.算法必须具备的5个特征是：有穷性、确定性、可行性、有0或多个输入量，至少有1个输出量。
选项A：错误
选项B：正确
正确答案问询微信：424329

42.对于同一组结点，由于建立二叉排序树时插入结点的先后次序不同，所构成的二叉排序树的形态及深度也不同，所以含有n个结点的二叉排序树不唯一。
选项A：错误
选项B：正确
正确答案问询微信：424329

43.快速排序的速度在所有排序方法中为最快，而且所需附加空间也最少。
选项A：错误
选项B：正确
正确答案问询微信：424329

44.队列和栈都是运算受限的线性表。
选项A：错误
选项B：正确
正确答案问询微信：424329

45.一个栈的输入序列是12345，则栈的输出序列可以是54312。
选项A：错误
选项B：正确
正确答案问询微信：424329

46.顺序存储方式只能用于存储线性结构。
选项A：错误
选项B：正确
正确答案问询微信：424329

47.空格也是合法字符，它可以出现在较长的字符串中，也可以单独出现 。
选项A：错误
选项B：正确
正确答案问询微信：424329

48.空栈就是所有元素都为0的栈。
选项A：错误
选项B：正确
正确答案问询微信：424329

49.若有向图有n个顶点，则其强连通分量最多有n个。
选项A：错误
选项B：正确
正确答案问询微信：424329

50.二叉树是二叉排序树的充要条件是其任意非叶结点的值均大于其左孩子的值、小于其右孩子的值。
选项A：错误
选项B：正确
正确答案问询微信：424329