《嵌入式系统开发人员C语言测试题数据结构与算法》由会员分享，可在线阅读，更多相关《嵌入式系统开发人员C语言测试题数据结构与算法（16页珍藏版）》请在金锄头文库上搜索。
1、11.1 选择题 （833） 下面关于算法说法错误的是_。 a. 算法最终必须由计算机程序实现 b. 为解决某问题的算法同为该问题编写的程序含义是相同的 c. 算法的可行性是指指令不能有二义性 d. 以上几个都是错误的 （834） 下面说法错误的是_. a. 算法原地工作的含义是指不需要任何额外的辅助空间 b. 在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 c. 所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 d. 同一个算法，实现语言的级别越高，执行效率就越低 （835） 在下面的程序段中，对x的赋值语句的频度为_。 for (int i; in;
2、i+) for (int j=o; jLlink=q; q-Rlink=p; p-Llink-Rlink=q; q-Llink=q； b. p-Llink=q; p-Llink-Rlink=q; q-Rlink=p; q-Llink=p-Llink; c. q-Rlink=p; q-Llink=p-Llink; p-Llink-Rlink=q; p-Llink=q; d. q-Llink=p-Llink; q-Rlink=q; p-Llink=q; p-Llink=q; （845） 下面说法正确的是_。 a. 顺序存储结构的主要缺点是不利于插入或删除操作； b. 线性表采用链表存储时，结点和结
3、点内部的存储空间可以是不连续的； c. 顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好； d. 顺序存储方式只能用于存储线性结构。 （846） 下面说法正确的是_。 a. 线性表只能用顺序存储结构实现。 b. 为了很方便的插入和删除数据，可以使用双向链表存放数据。 c. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 d. 链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。 （847） 下面说法正确的是_。 a. 数据元素是数据的最小单位。 b. 队列逻辑上是一个下端口和上端能增加又能减少的线性表。 c. 任何一个递归过程都可以转换成
4、非递归过程。 d. 只有那种使用了局部变量的递归过程在转换成非递归过程时才必须使用栈。 （848） 下面说法正确的是_。 a. 数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入、删除等操作。 b. 两分法插入排序所需比较次数与待排序记录的初始排列状态相关。 c. 当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省。 d. 在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。 （849） 下面说法正确的是_。 a. 在执行某个排序算法过程中，出现了排序码朝着最终排序序列相反方向移动，则该算法是不
5、稳定的。 b. 堆排序是稳定的排序方法。 c. 在分配排序时，最高位优先分配法比最低位优先分配法简单。 d. 最佳两叉排序树的任何子树都是最佳的。 （850） 具有N个结点的完全二叉树的深度是：_。 a. log2n b.LOG2N/1 c. LOG2(N/1) d.LOG2N-1 （851） 用单循环链表表示队列，正确的说法是：_。 a. 可设一个头指针使入队、出队都方便 b. 可设一个尾指针使入队、出队都方便 c. 必须设头尾指针才能使入队、出队都方便 d. 无论如何,只可能使入队方便 （852） 一个哈希函数被认为是好的，如果它满足条件_。 a. 哈希地址分布均匀 b. 保证不产生冲突
6、c. 所有哈希地址在表长范围内 d. 满足(2)和(3) （853） ISAM文件和VSAM文件属于_。 a. 索引非排序文件 b. 索引顺序文件 c. 顺序文件 d. 散列文件 （854） 在下述排序算法中_算法是稳定的排序算法。 a. 希尔排序 b. 快速排序 c. 冒泡排序 d. 堆排序 （855） 在下述三种排序算法中，所需辅助存储量最多的是_，所需存储量最少的是_，平均速度最快的是_。 a. 堆排列 b. 快速排列 c.归并排列 （856） 存贮稀疏图的数据结构常有的是_。 a. 邻接矩阵 b. 三元组 c. 邻接表 d. 十字链表 （857） 内部排序多个关键字的文件，最坏情况下最
7、快的排列方法是_,相应的时间复杂度为_,该算法是的稳定性_。 a. 快速排序 b. 插入排序 c. 归并排序 d. 简单选择排序 e. O(nlog2(n) f. O(n2) g. O(n2log2(n) h. O(n) i. 稳定 j. 不稳定 （858） 倒排文件包含若干个倒排表，倒排表的内容是_。 a. 一个关键字值和关键字的记录地址； b. 一个属性值和该属性的一个记录地址； c. 一个属性值和该属性的全部属性地址； d. 多个关键字值和它们对应的某个记录的地址。 （859） 在下述几种树当中,_可以表示静态查找表. a. 次优查找树; b. 二叉排序树; c. B-树 d. 平衡二叉
8、树 （860） 选择填空： (1). 在文件局部有序或文件长度较小的情况下,最优内部排序的方法是_. (2). 快速排序在最坏的情况下,时间复杂度是_,_的性能差; (3). 就平均时间而言,_最佳. a.: (1)直接插入排序 (2)起泡排序 (3)简单选择排序; b.: (1)O(nlog(n) (2)O(n2) (3)O(n3) c.: (1)堆排序 (2)起泡排序 (3)选择排序. d.: (1)堆排序 (2)快速排序 (3) 归并排序. （861） 算法的时间复杂度取决于_。 a. 问题的规模 b. 待处理数据的初态 c. both a and b （862） 假定有k个关键字互为同
9、义词,若用线性探测法把这k个关键字存入散列表中,至少要进行_次探测。 a. k-1 b. k c. k=1 d. k(k+1)/2 （863） 若需要在O(nlog2(n)的时间内完成对数组的排序,且要求排序是稳定的,则可选择的排序方法是: a. 快速排序 b. 堆排序 c. 归并排序 d. 直接插入排序 （864） 将两个各有n个元素的有序表归并成一个有序表,其最少的比较次数是_。 a. n b. 2n-1 c. 2n d. n-1 （865） 下述二叉树中,_满足性质:从任意结点出发到根的路径上所经过的结点序列按其关键字有序。 a. 二叉排序树 b. 哈夫曼树 c. AVL树 d. 堆 （
10、866） 若在线性表中采用折半查找法查找元素，该线性表应该_。 a. 元素按值有序 b. 采用顺序存储结构 c. 元素按值有序，且采用顺序存储结构 d. 元素按值有序，且采用链式存储结构 （867） 若二叉树采用二叉链表存储结构，要交换其所有分支结点左右子树的位置，利用_遍历方法最合适。 a. 前序 b.中序 c.后序 d. 按层次 （868） 对二叉排序树进行_遍历，可以得到该二叉树所有结点构成的排序序列。 a. 前序 b. 中序 c.后序 d. 按层次 （869） 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为_排序法。 a. 插入 b. 选择 c. 谢尔 d. 二路归并 （870） 排序趟数
