盐城师范学院数据结构与算法期末复习题及参考答案.docx

《盐城师范学院数据结构与算法期末复习题及参考答案.docx》由会员分享，可在线阅读，更多相关《盐城师范学院数据结构与算法期末复习题及参考答案.docx（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、盐城师范继续教育学院数据结构与算法普通用卷一单项选择题（共50题，总分值75分）1.设有一组关键字值（46,79,56,38,40,84）,那么用堆 排序的方法建立的初始堆为（）。（1.5分）A. 79,46,56,38,40,84B. 84,79,56,38,40,46C. 84,79,56,46,40,38D. 84,56,79,40,46,38.在带有头结点的单链表HL中，要向表头插入一个由 指针P指向的结点，那么执行（）（1.5分）A. p-next=HL-next;HL-next=pB. p-next=HL;HL=pC. p-next=HL;p=HLD. HL=p;p-next=HL

2、.以下是动态规划算法基本要素的是（）o （1.5分）A.定义最优解B.构造最优解C.算出最优解D.子问题重叠性质4.不带头结点的单链表（头指针为head）为空的判定 条件是（）。（L5分）A. head=NULLB. head-next=headD. n-136. Strassen矩阵乘法是利用（）实现的算法。（1.5 分）A.分治策略B.动态规划法C.贪心法D.回溯法37.队列的删除操作是在（）进行。（1.5分）A.队首B.队尾C.队首前一单元D.队尾后一单元.设输入序列为ABC,输出序列为CBA,那么经过的栈 操作为（）。（1.5分）A. push,pop,push,pop,push,po

3、pB. push,push,push,pop,pop,popC. push,push,pop,pop,push,popD. push,pop,push,push,pop,pop.实现最长公共子序列利用的算法是（）（1.5分）A.分治策略B.动态规划法C.贪心法D.回溯法.以下不属算法特性的是（）。（1.5分）A.有穷性B.确定性C.零或多个输入D.健壮性.在一般输入数据的程序里，输入多多少少会影响到 算法的计算复杂度，为了消除这种影响可用()对 输入进行预处理(1.5分)A.蒙特卡罗算法B.拉斯维加斯算法C.舍伍德算法D.数值概率算法.设广义表 L二(a, (),b, (c, d, e),那么

4、Head (Tail (Tail (L)的值为()。(L5 分)A. bB. cC. (c)D. (c,d,e).设一个有序的单链表中有n个结点，现要求插入一 个新结点后使得单链表仍然保持有序，那么该操作的 时间复杂度为()(1.5分)A. O (Iog2n)B. 0 (1)C. 0 (n2)D. 0 (n).银行业务叫号系统采用了 数据结构。（1.5分）A.栈B.广义表C.队列D.图45.以下属单链表优点的是（）。（1.5分）A.顺序存取B.插入操作能在0（1）的时间复杂度上完成C.插入时不需移动数据元素D.节省存储空间46.在对问题的解空间树进行搜索的方法中，一个活结点有屡次机会成为活结点

5、的是（）（1.5分）A.回溯法B.分支限界法C.回溯法和分支限界法D.动态规划.假设有18个元素的有序表存放在一维数组A19中,第一个元素放Al中，现进行二分查找，那么查找A3的比拟序列的下标依次为（）（1.5分）A. 1, 2, 3B. 9, 5, 2, 3C. 9, 5, 3D. 9, 4, 2, 3.假设为循环队列分配的向量空间为Q20,假设队列 的长度和队头指针值分别为13和17,那么当前尾指 针的值为 o （1.5分）A. 10B. 11C. 12D. 13.树最适合用来表示（）。（1. 5分）A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据

6、. 一棵度为3的树中，度为3的结点有2个，度为2 的结点有2个，度为1的结点有2个，那么度为0的 结点有（）。（L5分）个个个个5 6 7 8AB.CD.一单项选择题（共50题，总分值75分）.答案：B1 .答案：A.答案：D2 .答案：A.答案：D3 .答案：C.答案：D4 .答案：C.答案：A5 .答案：B.答案：A6 .答案：B.答案：D7 .答案：A.答案：A8 .答案：B.答案：C9 .答案：D.答案：D10 .答案：B.答案：C11 .答案：B.答案：B12 .答案：D.答案：D13 .答案：A.答案：D14 .答案：B.答案：B15 .答案：B.答案：B16 .答案：B.答案：D

7、17 .答案：A.答案：A18 .答案：A.答案：A19 .答案：B.答案：B20 .答案：D.答案：B21 .答案：D.答案：D22 .答案：C.答案：C23 .答案：A.答案：D24 .答案：A.答案：C25 .答案：CC. head-next=NULLD. head!=NULL.直接插入排序在最好情况下的时间复杂度为（）。 （1.5 分）A. O（logn）B. 0（n）C. O（n*logn）D. 0（n2）.设有一个二维数组A m n,假设A 0 0存放位置 在644（10）, A2 2存放位置在676（存）,每个元 素占一个空间,问A3 3 （10）存放在什么位置？ 脚注（10）表

8、示用10进制表示。（）（1.5分）A. 688B. 678C. 692D. 696.设串 si=abcdefg, s2=ab,那么 Concat （si, s2） 的返回值（）。（1.5分）A. abB. cdefgC. abcdefgD. abcdefgab. 一个栈的输入序列为123,那么以下序列中不可能是 栈的输出序列的是（）（1.5分）A. 231B. 321C. 312D. 1239,使用分治法求解不需要满足的条件是（）。（1.5 分）A.子问题必须是一样的B.子问题不能够重复C.子问题的解可以合并D.原问题和子问题使用相同的方法解.设无向图的顶点个数为n,那么该图最多有（）条 边。

9、（1.5分）A. n-1B. n（n-l）/2C. n（n+l）/2D. n2.分支限界法解旅行售货员问题时，活结点表的组织 形式是（）。（1.5分）A.最小堆B.最大堆C.栈D.数组12.在树形结构中，数据元素间存在（）的关系。（1.5 分）A.对B. 一对多C.多对多D.除同属一个集合外别无关系13.（）是贪心算法与动态规划算法的共同点。（1.5 分）A.重叠子问题B.构造最优解C.贪心选择性质D.最优子结构性质.设对以下图从顶点a出发进行深度优先遍历，那么（）是可能得到的遍历序列。 分）(1.5A. acfgdebB. abcdefgC. acdgbefD. abefgcd.分支限界法在

10、问题的解空间树中，按（）策略, 从根结点出发搜索解空间树（1.5分）A.广度优先B.活结点优先C.扩展结点优先D.深度优先16.下面关于NP问题说法正确的选项是（）（1.5分）A. NP问题都是不可能解决的问题B. P类问题包含在NP类问题中C. NP完全问题是P类问题的子集D. NP类问题包含在P类问题中n个结点的线索二叉树上含有的线索数为 o （1.5 分）A. 0B. n-1C. n+1D. 2nNP类语言在图灵机下的定义为（）（1.5分）A. NP=L|L是一个能在非多项式时间内被一台NDTM所接受的语言B. NP=L|L色一个能在多项式时间内被一台NDTM所接受的语言C.NP=L|L

11、是一个能在多项式时间内被一台DTM所接受的语言D. NP=L|L是一个能在多项式时间内被一台NDTM所接受的语言19.在一个可存放n个数据元素的顺序栈中，假设以高 地址端为栈底，以top为栈顶指针，当向栈中压入 一个数据元素时，top的变化是（）。（1. 5分）A.不变B. top=nC. top+D. top-20. 串的长度是指（）。（1.5分）A.串中所含不同字母的个数B.串中所含字符的个数C.串中所含不同字符的个数D.串中所含非空格字符的个数21.动态规划算法的基本要素（）（1.5分）A.最优子结构性质与贪心选择性质B.重叠子问题性质与贪心选择性质C.最优子结构性质与重叠子问题性质D.

12、预排序与递归调用.二叉树T的先序序列为abdegcfh,中序序列 为dbgeachf,那么T的后序序列为（）o （1.5分）A. gedhfbcaB. dgebhfcaC. abcdefghD. acbfedhg.设连通图G中的边集E= （a, b） , （a, e） , （a, c） , （b, e） , （e, d） , （d, f） , （f, c） , 那么从顶点a出发可以得到一种深度优先遍历的顶点 序列为（）（1.5分）A. abedfcB. acfebdC. aebdfcD. aedfcb.二叉树的第k层的结点数最多为（）.（1.5分）A. 2k-lB. 2K+1C. 2K-1D.

13、 2k-l.假设需要利用形参直接访问实参时，应将形参变量说 明为（）参数。（）（L5分）A.值B.函数C.指针D.引用.假设采用顺序映象，那么数据元素在内存中占用的存储 空间（）。（1.5分）A. 一定连续B. 一定不连续C.可连续可不连续.设哈希表地址范围为019,哈希函数H（key）=key%17,使用二次探测再散列法处理冲突。 假设表中已存放有关键字值为6、22、38、55的记录, 那么再放入关键字值为72的记录时，其存放地址应为（）o （1.5 分）A. 2B. 3C. 4D. 7E. 8F.以上都不对28.以下排序算法中（）不能保证每趟排序至少能将 一个元素放到其最终的位置上。（1.

14、5分）A.快速排序B. shell 排序C.堆排序D.冒泡排序. 一棵高为k的二叉树最少有（）个结点。（1.5分）A. k-1B. kC. k+1D. 2匕1E. 2k-l.蒙特卡罗算法是（）的一种。（1.5分）A.分支界限算法B.概率算法C.贪心算法D.回溯算法.对二叉排序树进行（）遍历所得的遍历序列中， 关键字值是按升序排列的。（1.5分）序序序序前中后层AB.CD.31 . k带图灵机的空间复杂性S（n）是指（）（1.5分）A. k带图灵机处理所有长度为n的输入时，在某 条带上所使用过的最大方格数B.k带图灵机处理所有长度为n的输入时，在k 条带上所使用过的方格数的总和C.k带图灵机处理所有长度为n的输入时，在k条带上所使用过的平均方格数D.k带图灵机处理所有长度为n的输入时，在某 条带上所使用过的最小方格数.对于线性表（7, 34, 55, 25, 64, 46, 20, 10） 进行散列存储时，假设选用H （K）=K %9作为散列函 数，那么散列地址为1的元素有（）个，（1.5分）A. 1B. 2C. 3D.4.在稀疏矩阵的带行指针向量的链接存储中，每个单 链表中的结点都具有相同的（）（L5分）号号素行列元AB.CD.非零元素个数35,将两个各有n个元素的有序表归并成一个有序表, 最少进行（）次比拟。（1.5分）A. nB. 2n-lC. 2n