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

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

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

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

2.在有序表（3,8,13,15,16,17,21,24,45）中，用二分查找法查找关键字21，所需进行关键字比较的次数为()。
选项A：2
选项B：3
选项C：4
选项D：5
正确答案问询微信：424329

3.长度为256的表,采用分块查找,每块最佳长度为()。
选项A：14
选项B：16
选项C：18
选项D：26
正确答案问询微信：424329

4.对线性表进行二分查找时，要求线性表必须()。
选项A：以顺序方式存储
选项B：以链接方式存储
奥鹏北京理工大学新学期作业参考 选项C：以顺序方式存储，且结点按关键字有序排列
选项D：以链接方式存储，且结点按关键字有序排列
正确答案问询微信：424329

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

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

7.()是HASH查找的冲突处理方法。
选项A：求余法
选项B：平方取中法
选项C：二分法
选项D：开放定址法
正确答案问询微信：424329

8.数组的数据元素类型DataType可根据实际需要而定义。以下说法完全正确的是()
选项A：数组的读运算可以读取一个数据元素整体,写运算只能修改一个数据元素的一部分
选项B：数组的读、写运算可以读取或修改一个数据元素的一部分或一个整体
选项C：数组的读、写运算只能读取或修改一个数据元素的一部分
选项D：数组的读、写运算只能读取或修改一个数据元素整体
正确答案问询微信：424329

9.若某线性表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用哪一种存储结构算法的时间效率最高?()
选项A：单链表
选项B：给出表头指针的单循环链表
选项C：双向链表
选项D：给出表尾指针的双向循环链表
正确答案问询微信：424329

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

11.栈是一种()的数据结构。
选项A：存取受限的线性结构
选项B：存取不受限的线性结构
选项C：存取受限的非线性结构
选项D：存取不受限的非线性结构
正确答案问询微信：424329

12.在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为().
选项A：n
选项B：n/2
选项C：(n+1)/2
选项D：(n-1)/2
正确答案问询微信：424329

13.3个结点的无向完全连通图至少有()条边。
选项A：3
选项B：4
选项C：5
选项D：6
正确答案问询微信：424329

14.栈与一般的线性表的区别在于()。
选项A：数据元素的类型不同
选项B：运算是否受限制
选项C：数据元素的个数不同
选项D：逻辑结构不同
正确答案问询微信：424329

15.下列存储表示中,哪一个不是树的存储形式()。
选项A：双亲表示法
选项B：孩子链表表示法
选项C：顺序存储表示法
选项D：孩子兄弟表示法
正确答案问询微信：424329

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

17.具有65个结点的完全二叉树其深度为（根的层次号为1）()。
选项A：8
选项B：7
选项C：6
选项D：5
正确答案问询微信：424329

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

19.若构造一棵具有n个结点的二叉排序树，最坏情况下，其深度不会超过()。
选项A：n/2
选项B：n
选项C：(n+1)/2
选项D：n+1
正确答案问询微信：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：直接插入排序的空间复杂度为O(1)
选项B：快速排序附加存储开销为O(log2n)
选项C：堆排序的空间复杂度为O(n)
选项D：二路归并排序的空间复杂度为O(n)
正确答案问询微信：424329

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

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

28.以下不稳定的排序方法是（）
选项A：快速排序
选项B：冒泡排序
选项C：希尔排序
选项D：堆排序
正确答案问询微信：424329

29.某堆栈的输入序列为a, b，c，d,下面的四个序列中，可能是它的输出序列的是（）
选项A：a，c，b，d
选项B：b, c，d，a
选项C：c, d，b, a
选项D：d, c，a，b
正确答案问询微信：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.一个栈的输入序列是12345，则栈的输出序列可以是54312。
选项A：错误
选项B：正确
正确答案问询微信：424329

42.任何一棵二叉树中至少有一个结点的度为2。
选项A：错误
选项B：正确
正确答案问询微信：424329

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

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

45.深度为6的二叉树最多有64个结点。
选项A：错误
选项B：正确
正确答案问询微信：424329

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

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

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

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

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