安阳工学院软件工程专业大二2017-2018数据结构与算法模拟试题七

1、安阳工学院软件工程专业大二2017-2018数据结构与算法模拟试题七您的姓名： 填空题 *_1.以下英文字符串中是回文字符串的是（）。 单选题 *A: aabbaa(正确答案)B: aabbccddC: ABCABCD: AABBB2.数据结构与算法内，折半查找的时间复杂度是（）。 单选题 *A: O(1)B: O(log2n)(正确答案)C: O(n*n)D: O(n)3.栈是操作受限的线性表，不能插入、删除的一端称为（）。 单选题 *A: 栈顶B: 栈底(正确答案)C: 栈中D: 以上都不对4.表达式求值算法中，当某运算符优先级低于栈顶符号的优先级时，该运算符（）。 单选题 *A: 不能进

2、栈(正确答案)B: 可以进栈C: 进栈或者不进栈都可以D: 都不对5.线性结构中，无需为表中的元素之间的逻辑关系而增加额外的存储空间是（）的优点。 单选题 *A: 顺序表(正确答案)B: 链表C: 结构体D: 指针6.线性表n个元素采用顺序表存储，在第i个位置删除需要移动（）个元素,其时间复杂度是(B)。 单选题 *A: n-i+1 O(n)B: n-i O(n)(正确答案)C: n-i O(1)D: (n-1)/2 O(1)7.线性结构中，线性表采用链式存储的好处是（）。 单选题 *A: 可以随机访问任何一个元素B: 元素都存在一片连续的存储空间C: 无需预估存储空间的大小(正确答案)D:

3、插入删除需要移动大量元素8.以下属于哈希函数的构造方法的是（）。 单选题 *A: 直接定址法(正确答案)B: 哈希再散列法C: 线性探测再散列法D: 二次探测再散列法9.下列那个是直接递归形式函数（）。 单选题 *A: void tell_stroy( ) tell_stroy(); (正确答案)B: void tell_stroy( ) void tell_stroy(); C: void tell_stroy( ) stroy(); D: void tell_stroy( ) tell(); 10.如孙子算经中描述的鸡兔同笼问题之穷举算法的时间复杂度是（）。 单选题 *A: O(n)B:

4、O(n*n)(正确答案)C: O(nlog2n)D: O(1)11.以下英文字符串中是回文字符串的应该是（）。 单选题 *A: 123321(正确答案)B: 11223311C: 123213D: 12312312.在一个单层循环中的循环体某处想停止本次循环，继续下一次循环，应在该处使用（）语句。 单选题 *A: break语句B: return语句C: continue语句(正确答案)D: exit(0)语句13.鸡与兔共有35只，脚共94只，问鸡有（）只。 单选题 *A: 23(正确答案)B: 12C: 22D: 1314.一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（

5、）。 单选题 *A: CABDEFGB: ABCDEFG(正确答案)C: DACEFBGD: ADCFEG15.关于二叉树树，某完全二叉树按层次编号后，某结点是i，若有左孩子，则左孩子的编号是（）。 单选题 *A: 2i(正确答案)B: 2i+1C: 2i-1D: i/216.假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？（）。 单选题 *A: k-1次B: k次C: k+1次D: k(k+1)/2次(正确答案)17.n个盘子的汉诺塔问题，移动步数是（）。 单选题 *A: 2的n次幂减1(正确答案)B: 2*n-1C: 2*n+1D: log2n1

6、8.字符串处理函数是字符串连接的是（）。 单选题 *A: strcat(正确答案)B: strcpyC: strcmpD: strlen19.若有说明:int a34;，则对a数组元素的非法引用是：（）。 单选题 *A: a02*1B: a13C: a4-20D: a04(正确答案)20.数据结构与算法内，改进的冒泡排序的任一趟排序过程中，如果没有发生（），则说明已经有序；排序完毕。 单选题 *A: 数据交换(正确答案)B: 数据删除C: 数据增加D: 都不对21.以下英文字符串中是回文字符串的应该是（）。 单选题 *A: 123321(正确答案)B: 11223311C: 123213D:

7、12312322.数据结构与算法内，从时间复杂度的角度来看，快速排序的时间复杂度是（）。 单选题 *A: O(n*n)B: O(nlog2n)(正确答案)C: O(1)D: 都不对23.以下英文字符串中是回文字符串的是（）。 单选题 *A: aabbaa(正确答案)B: aabbccddC: ABCABCD: AABBB24.char s100="abc" 则执行strcpy(s,strcat(s,"123");后s的结果是（）。 单选题 *A: abc123(正确答案)B: 123abcC: abcD: 12325.若有说明int a34;，则对a数组

8、元素的非法引用是（）。 单选题 *A: a02*1B: a13C: a4-20D: a04(正确答案)26.下列关于二叉排序树中说法正确的是（）。 单选题 *A: 二叉排序树的定义具有反复性B: 二叉排序树的定义具有递归性(正确答案)C: 二叉排序树的定义具有回溯性D: 二叉排序树的定义具有反弹性27.冒泡排序最好的情况是，记录完全有序，20个记录待排序只需要比较（）次即可完成排序。 单选题 *A: 20B: 19(正确答案)C: 18D: 19028.哪种排序可能发生在最后一趟排序开始之前，所有记录均不在其最终位置上（）。 单选题 *A: 直接插入排序(正确答案)B: 简单选择排序C: 冒泡

9、排序D: 快速排序29.直接插入排序的时间复杂度和折半查找的时间复杂度分别是（）。 单选题 *A: O(n*n)和O(log2n)(正确答案)B: O(n*n)和O(n)C: O(1)和)O(n)D: O(n)和O(1)30.以下属于哈希函数的构造方法的是（）。 单选题 *A: 直接定址法(正确答案)B: 哈希再散列法C: 线性探测再散列法D: 二次探测再散列法31.队列具有先进先出的特性，那么入队的O，P，Q顺序的三个元素，出队顺序是（）。 单选题 *A: O，P，Q(正确答案)B: O，Q，PC: Q，P，OD: O，Q，P32.单链表中删除p指针指向结点的后继(假设存在)的语句序列正确的

10、是（）。 单选题 *A: p->next=p->next;B: p->next=p->next->next;(正确答案)C: p->next=p;D: p=p->next;33.在树的概念中，树的某结点的直接后继称为该结点的 （）。 单选题 *A: 孩子(正确答案)B: 双亲C: 子孙D: 祖先34.下列选项中关于二叉树先序遍历的顺序说法正确的是（）。 单选题 *A: 左子树 根结点 右子树B: 根结点 左子树 右子树(正确答案)C: 左子树 右子树 根结点D: 无正确答案35.一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（）。 单

11、选题 *A: CABDEFGB: ABCDEFG(正确答案)C: DACEFBGD: ADCFEG36.度为0的结点又称为（） 。 单选题 *A: 叶子(正确答案)B: 根结点C: 分支结点D: 内部结点37.在队列中能插入的一端称为（）。 单选题 *A: 队头B: 队尾(正确答案)C: 栈顶D: 栈底38.有关函数，下面描述正确的是（）。 *A: 定义函数时如果在函数名前加void,表示该函数没有返回值(正确答案)B: 函数的值只能通过return语句返回主调函数(正确答案)C: 定义函数时函数名可以定义fun。(正确答案)D: 从参数角度看函数可分为库函数和用户定义函数39.关于冒泡排序的

12、比较次数和排序趟数描述正确的是（）。 *A: N个记录最多N-1趟排序即可完成(正确答案)B: N个记录最少比较N-1次，可完成排序，这是记录完全有序的情况(正确答案)C: N个记录最多比较N*(N-1)/2次可完成排序，这是记录完全逆序的情况。(正确答案)D: 在一趟排序中若无记录交换，就会停止排序。(正确答案)40.在C语言中，系统函数strcmp的返回值类型不是（）。 *A: intB: char(正确答案)C: char*(正确答案)D: float(正确答案)41.荷兰国旗的算法使用的到的技术有（）。 *A: 循环(正确答案)B: 分支判断(正确答案)C: 一维数组(正确答案)D:

13、循环嵌套42.树的叶子结点描述正确的是（）。 *A: 叶子结点的度为0(正确答案)B: 叶子结点又称终端结点(正确答案)C: 叶子结点一定不是内部结点(正确答案)D: 叶子结点可能是分支结点43.下列排序中是稳定排序的是（）。 *A: 希尔排序B: 快速排序C: 直接插入排序(正确答案)D: 冒泡排序(正确答案)44.以下是回文字符串的是（）。 *A: aba(正确答案)B: 11811(正确答案)C: abcabcD: xyzyx(正确答案)45.动态查找表：边查找，边改变集合中的元素，改变的方式可以是（）。 *A: 增加(正确答案)B: 删除(正确答案)C: 交换D: 移动46.汉诺塔问题

14、的求解方式不属于以下哪类算法（）。 *A: 穷举(正确答案)B: 分治(正确答案)C: 递归D: 迭代(正确答案)47.线性结构之队列的应用包括哪些（）。 *A: 消息的缓存(正确答案)B: 操作系统的作业调度(正确答案)C: 离散事件的模拟(正确答案)D: 进制转换48.在下列结论中，正确的是（）。 *A: 只有一个结点的二叉树的度为0(正确答案)B: 二叉树的度小于等于2(正确答案)C: 二叉树的左右子树不可任意交换(正确答案)D: 深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树(正确答案)49.今有雉(鸡)兔同笼，上有三十五头，下有九十四足。问雉兔各几何？答案不正确的是（）。

15、 *A: 鸡23兔12B: 鸡12兔23(正确答案)C: 鸡22兔13(正确答案)D: 鸡13兔22(正确答案)50.关于二叉排序树描述有误的是（）。 *A: 二叉排序的右子树上结点的关键字小于左子树上的结点的关键字(正确答案)B: 二叉排序的左子树上结点的关键字小于右子树上的结点的关键字C: 二叉排序的根节点的关键大于右子树上结点的关键字(正确答案)D: 二叉排序的根节点的关键大于左子树上结点的关键字51.下列关于查找表描述正确的是（）。 *A: 查找表分为静态查找表和动态查找表(正确答案)B: 动态查找表边查找，边改变集合内的元素(正确答案)C: 静态查找表只查找不改变集合中的元素(正确答

16、案)D: 其它选项说法都正确(正确答案)52.回文字符串的判断可以使用的方法有（）。 *A: 递归方式(正确答案)B: 非递归方式利用循环解决(正确答案)C: 非递归方式用系统函数解决(正确答案)D: 以上答案都正确(正确答案)53.今有雉(鸡)兔同笼，上有三十五头，下有九十四足。问雉兔各几何？答案不正确的是（）。 *A: 鸡23兔12B: 鸡12兔23(正确答案)C: 鸡22兔13(正确答案)D: 鸡13兔22(正确答案)54时间复杂度是O(n*n)的排序是（）。 *A: 简单选择排序(正确答案)B: 冒泡排序(正确答案)C: 直接插入排序(正确答案)D: 快速排序55.完全二叉树中，结点个

17、数为n，则编号最大的分支结点的编号不可能为（）。 *A: n/2向下取整B: n/2向下取整+1(正确答案)C: n/2向下取整+2(正确答案)D: n/2向下取整-1(正确答案)56.已知一个栈入栈顺序是1,2,3，入的过程可以出栈，则是正确出栈的顺序是（）。 *A: 1,2,3(正确答案)B: 3,2,1(正确答案)C: 2,1,3(正确答案)D: 1,3,2(正确答案)57. 二叉树的先序序列是：ABDCEF，中序序列是：ADBECF，则后序序列不可能是（）。 *A: DFECBA(正确答案)B: EFDCBA(正确答案)C: DEFCBAD: DFCEBA(正确答案)58.关于树的概念

18、说法正确的是（）。 *A: 树可以为空树(正确答案)B: 树的定义具有递归性(正确答案)C: 树中若存在根结点，则有且只能有一个。(正确答案)D: 树的结点若大于2个，则除了根结点，其余结点分为m个互不相交的子集，每个子集也是一颗树(正确答案)59.数据结构与算法内，今有雉(鸡)兔同笼，上有三十五头，下有九十四足。问雉兔各几何答案不正确的是（）。 *A: 鸡23兔12B: 鸡12兔23(正确答案)C: 鸡22兔13(正确答案)D: 鸡13兔22(正确答案)60.回文字符串存储方式一般采用字符数组，则关于字符数组描述正确的是（）。 *A: 只能存放字符型数据(正确答案)B: 数组是定长的，定义后

19、不可改变(正确答案)C: 数组元素占有一片连续的存储单元(正确答案)D: 数组元素可以存放不同类型的数据61.希尔排序的时间复杂度不可能是（）。 *A: O(n*n)(正确答案)B: O(nlog2n)(正确答案)C: O(n)(正确答案)D: O(n3/2)62.冒泡排序的改进之处说法不对的是（）。 *A: 增加了比较的次数(正确答案)B: 增加了比较的趟数(正确答案)C: 尽可能的减少比较次数和趟数D: 一定会减少比较的次数和趟数(正确答案)63.以下的排序是内排序的是（）。 *A: 希尔排序(正确答案)B: 快速排序(正确答案)C: 希尔排序(正确答案)D: 快速排序(正确答案)64.下

20、列排序中是稳定排序的是（）。 *A: 希尔排序B: 快速排序C: 直接插入排序(正确答案)D: 冒泡排序(正确答案)65.排序是稳定排序或不稳排序的插入排序是（）。 *A: 希尔排序(正确答案)B: 直接插入排序(正确答案)C: 堆排序D: 快速排序66.关于二叉排序树描述有误的是（）。 *A: 二叉排序的右子树上结点的关键字小于左子树上的结点的关键字(正确答案)B: 二叉排序的左子树上结点的关键字小于右子树上的结点的关键字C: 二叉排序的根节点的关键大于右子树上结点的关键字(正确答案)D: 二叉排序的根节点的关键大于左子树上结点的关键字67.如有定义int a23;则数组a的最后一个元素为a12。 判断题 *对(正确答案)错68.字