智慧树知到《数据结构与算法》章节测试答案.pdf

《智慧树知到《数据结构与算法》章节测试答案.pdf》由会员分享，可在线阅读，更多相关《智慧树知到《数据结构与算法》章节测试答案.pdf（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、智慧树知到数据结构与算法章节测试答案第一章1、在数据结构中，从逻辑上可以把数据结构分成（ ）。A:紧凑结构和非紧凑结构B:线性结构和非线性结构C:内部结构和外部结构D:动态结构和静态结构正确答案：线性结构和非线性结构2、在数据结构中，从存储结构上可以将之分为（ ）。A:动态结构和静态结构B:顺序存储和非顺序存储C:紧凑结构和非紧凑结构D:线性结构和非线性结构正确答案：顺序存储和非顺序存储3、某算法的时间复杂度是O(n2)，表明该算法的（ ）。A:执行时间与n2成正比B:问题规模是n2C:执行时间等于n2D:问题规模与n2成正比正确答案：执行时间与n2成正比4、在下面的程序段中，x=x+1;的语

2、句频度为（ ）。for( i=1;i=n;i+) for( j=1;jnext=p-next;p-next=s;B:p-next=s;s-next=p-next;C:p-next=s;p-next=s-next;D:p-next=s-next;p-next=s;正确答案：s-next=p-next;p-next=s;7、 对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）。A:headnext=NULL;B:head=NULL;C:headnext=he;D:head!=NULL;正确答案：headnext=NULL;8、 静态链表与动态链表在元素的插入、删除上类似，不需做

3、元素的移动。A:对B:错正确答案：对9、 顺序表适宜于顺序存取，而链表适宜于随机存取。A:对B:错正确答案：错10、线性表的链式存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。A:对B:错正确答案：对第三章1、栈和队列都是（ ）。A:限制存取点的非线性结构B:顺序存储的线性结构C:链式存储的非线性结构D:限制存取点的线性结构正确答案：限制存取点的非线性结构2、设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后随即进入队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1，则栈S的容量至少应该是（ ）。A:3B:6C:4D:2正确

4、答案：A3、设计一个判别表达式中括号是否匹配出现的算法，采用（ ）的数据结构最佳。A:栈B:顺序表C:队列D:单链表正确答案：A4、表达式a*(b+c)-d的后缀表达式是( )。A:abc+d-B:cb+ad-C:abc+*d-D:abcd+-正确答案：abc+*d-5、递归过程或函数调用时，处理参数及返回地址需要用一种（ ）的数据结构。A:栈B:队列C:多维数组D:线性表正确答案：A6、最大容量为n的循环队列，队尾指针为rear，队头指针为front，则队空的条件是（ ）。A:rear=frontB:(rear+1)%n=frontC:rear+1=frontD:(rear-l)%n=fro

5、nt正确答案：rear=front7、用带头结点的单链表表示队长大于1的队列时，其队头指针指向队头结点，其队尾指针指向队尾结点，则在进行删除操作时（ ）。A:仅修改队头指针B:仅修改队尾指针C:队头、队尾指针都要修改D:队头,队尾指针都可能要修改正确答案：仅修改队头指针8、对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度和在给定值为x的结点后插入一个新结点的时间复杂度分别为（ ）。A:O(1),O(n)B:O(n),O(n)C:O(1),O(1)D:O(n),O(1)正确答案：A9、两顺序栈共享空间，也存在空间溢出问题。A:对B:错正确答案：A10、在对不带头结点的链队

6、列作出队操作时，不会改变头指针的值。A:对B:错正确答案：B第四章1、串是一种特殊的线性表，其特殊性体现在（ ）。A:数据元素是单个字符B:顺序存储C:链式存储D:逻辑结构是线性结构正确答案：数据元素是单个字符2、若串S= software，其前缀真子串的数目是( )。A:7B:10C:9D:8正确答案：A3、设有两个串p和q ，其中q是p的子串，求q在p中首次出现的位置的算法称为( )。A:串的模式匹配B:求子串C:串联接D:求串长正确答案：A4、已知串 S=aaab，其next函数值为（ ）。A:0123B:1123C:1231D:1211正确答案：A5、函数strcmp(stcabuc,

7、stbabuc)的返回值是（ ）。A:0B:-1C:2D:1正确答案：D6、KMP算法的特点是在模式匹配时指示主串的指针不会回溯。A:对B:错正确答案：A7、模式串 P=abaabcac的next函数值序列为01122312。A:对B:错正确答案：A8、串的存储结构有顺序串、堆串和块链串三种。A:对B:错正确答案：A9、子串的定位运算称为串的模式匹配。A:对B:错正确答案：A10、串student和Student相等。A:对B:错正确答案：B第五章1、假设以行序为主序存储二维数组A=array1100，1100，设每个数组元素占2个存储单元，基地址为10，则LOC5，5=( )。A:818B:

8、808C:1010D:1020正确答案：A2、若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B1(n(n+1)/2中，则在B中确定aij（iLTag=1B:p!=NULLC:p-lchild!=NULLD:p-LTag=0正确答案：D4、设森林T中有4棵树，其结点个数分别为n1,n2,n3,n4，那么当森林T转换成一棵二叉树后，则根结点的右子树上有（ ）个结点。A:n2+n3+n4B: n1-1C:n1D:n1+n2+n3正确答案：A5、以数据集4，5，6，7，10，12，18为叶结点权值所构造的哈夫曼树，其带权路径长度为（ ）。A:155B:

9、160C:165D:170正确答案：C6、以下属于前缀编码的是（ ）。A:0,1101,1110,1100,1111B:0,1,01,010,110C:00,01,10,11,101D:01,00,10,001,110,101正确答案：A7、一棵具有N个结点的二叉树采用二叉链表进行存储，其中空指针域有( )个。A:N+1B:NC:N-1D:不确定正确答案：A8、已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有（ ）个叶子结点。A:10B:11C:12D:13正确答案：C9、满二叉树一定完全是二叉树。A:对B:错正确答案：A10、二叉树的遍历结果不是唯一的。A

10、:对B:错正确答案：A第七章1、一个具有n个顶点的无向图最多有（ ）边。A:n(n-1)/2B:n(n-1)C:nD:2n正确答案：A2、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则占用的存储空间为（ ）。A:n+eB:eC:2eD:n+2e正确答案：D3、如果含有n个顶点的图形成一个环，则它有（ ）棵生成树。A:nB:n-1C:n+1D:不确定正确答案：A4、任何一个无向连通网的最小生成树（ ）。A:有一棵或多棵B:只有1棵C:一定有多棵D:可能不存在正确答案：A5、判断一个有向图是否存在回路，可以用（ ）。A:广度优先遍历算法B:求关键路径的方法C:Dijkstra方法D:深

11、度优先遍历算法正确答案：D6、关键路径是事件结点网络中（ ）。A:从源点到汇点的最长路径B:最长回路C:从源点到汇点的最短路径D:最短回路正确答案：A7、深度优先遍历类似于二叉树的（ ）。A:先序遍历B:中序遍历C:后序遍历D:层次遍历正确答案：A8、广度优先遍历类似于二叉树的( )。A:先序遍历B:中序遍历C:后序遍历D:层次遍历正确答案：D9、迪杰斯特拉算法求最短路径时，是按照路径长度递增的顺序求解的。A:对B:错正确答案：A10、任何一个有向图都一定存在拓扑序列。A:对B:错正确答案：B第八章1、具有12个关键字的有序表，折半查找的平均查找长度( )。A:10/12B:25C:25/12

12、D:37/12正确答案：D2、如果要求用线性表既能较快地查找，又能适应动态变化的要求，则可采用（ ）查找方法。A:分块查找B:顺序查找C:折半查找D:基于属性正确答案：A3、已知一如下10个记录的表，其关键字序列为（2，15，19，25，30，34，44，55，58，80），用折半查找法查找关键字为55的记录，比较次数是（ ）。A:1次B: 2次C:3次D:4次正确答案：B4、如果按关键码值递增的顺序依次将99个关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，在等概率情况下查找成功时的平均查找长度ASL为( ）。A:50B:48C:45D:47正确答案：A5、对包含n个元素的散列表进行

13、查找，平均查找长度为（ ）。A:不直接依赖于nB:O(n2)C:O(log2n)D:O(n)正确答案：A6、 衡量查找算法效率的主要标准是（ ）。A:平均查找长度B:元素个数C:所需的存储量D:算法难易程度正确答案：A7、Hash表的平均查找长度与处理冲突的方法无关。A:对B:错正确答案：B8、在二叉树排序树中插入一个新结点，总是插入到叶结点下面。A:对B:错正确答案：A9、哈希表是一种将关键字转换为存储地址的存储方法。A:对B:错正确答案：A10、在二叉排序树上删除一个结点时，不必移动其它结点，只要将该结点的父结点的相应的指针域置空即可。A:对B:错正确答案：B第九章1、 有一组数据（15，

14、9，7，8，20，-1，7，4），用堆排序的筛选方法建立的初始小根堆为( )。A:-1，4，7，8，20，15，7，9B:-1，4，8，9，20，7，15，7C:-1，7，15，7，4，8，20，9D: A，B，C均不对。正确答案：A2、一组记录的关键字为（46,79,56,38,40,84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）。A:（40, 38, 46, 56, 79, 84）B:（38, 40, 46, 56, 79, 84）C:（40, 38, 46, 79, 56, 84）D:（40, 38, 46, 84, 56, 79）正确答案：A3、对下列整数序

15、列使用基数排序，一趟分配收集之后的结果是( )。（179，208，93，306，55，859，984，9，271，33）A:271,93,33,984,55,306,208,179,859,9B:93,55,9,33,179,208,271,306,859,984C:208,306,9,33,55,859,179,271,984,93D:9,33,55,93,179,208,271,306,859,984正确答案：A4、对序列15，9，7，8，20，-1，4进行排序，进行一趟后数据的排列变为9，15，7，8，20，-1，4，则采用的排序方法是（ ）。A:直接插入排序B:选择排序C:堆排序D:希

16、尔排序正确答案：A5、评价排序算法好坏的标准主要是（ ）。A:执行时间和所需的辅助空间B:执行时间C:辅助空间D:算法本身的复杂度正确答案：A6、对个不同的排序码进行冒泡（递增）排序，在下列（ ）情况比较的次数最多。A:从大到小排列好的B:从小到大排列好的C:元素无序D:元素基本有序正确答案：A7、简单选择排序和堆排序性能都受初始序列顺序的影响。A:对B:错正确答案：B8、 快速排序算法在每一趟排序中都能找到一个元素放在其最终位置上。A:对B:错正确答案：A9、堆排序所需的时间与待排序的记录个数无关。A:对B:错正确答案：B10、采用希尔方法排序时，若关键字的排列杂乱无序，则效率最高。A:对B:错正确答案：A