学习通《数据结构与算法》习题（含答案）.docx

1、学习通数据结构与算法习题（含答案）第1章第2章第3章第4章第5章第6章第7章问题：1.在数据结构中,从逻辑上可以把数据结构分成( )。答案：线性结构和非线性结构问题：2. 在数据结构中,从存储结构上可以将之分为( )。答案：顺序存储和非顺序存储问题：3. 某算法的时间复杂度是O(n2),表明该算法的(?)。答案：执行时间与n2成正比问题：4. 在下面的程序段中,x=x+1;的语句频度为( )。for( i=1;i=n;i+) for( j=1;jnext=p-next;p-next=s;问题：7. 对于一个头指针为head的带头结点的单链表,判定该表为空表的条件是()。?答案：headnext

2、=NULL;问题：8. 静态链表与动态链表在元素的插入、删除上类似,不需做元素的移动。答案：正确问题：9. 顺序表适宜于顺序存取,而链表适宜于随机存取。答案：错误问题：10. 线性表的链式存储结构中,逻辑上相邻的两个元素在物理位置上并不一定相邻。答案：正确第15章第16章第17章第18章第19章第20章第21章第22章第23章问题：1. 栈和队列都是( )。答案：限制存取点的线性结构?问题：2. 设栈S和队列Q的初始状态为空,元素e1,e2,e3,e4,e5和e6依次通过栈S,一个元素出栈后随即进入队列Q,若6个元素出队的序列是e2,e4,e3,e6,e5,e1,则栈S的容量至少应该是( )。

3、答案：3问题：3. 设计一个判别表达式中括号是否匹配出现的算法,采用( )的数据结构最佳。答案：栈 ?问题：4. 表达式a*(b+c)-d的后缀表达式是( )。答案：abc+*d-?问题：5. 递归过程或函数调用时,处理参数及返回地址需要用一种( )的数据结构。答案：栈?问题：6. 最大容量为n的循环队列,队尾指针为rear,队头指针为front,则队空的条件是( )。答案：rear=front?问题：7. 用带头结点的单链表表示队长大于1的队列时,其队头指针指向队头结点,其队尾指针指向队尾结点,则在进行删除操作时( )。答案：仅修改队头指针问题：8. 对于一个具有n个结点的单链表,在已知的结

4、点*p后插入一个新结点的时间复杂度和在给定值为x的结点后插入一个新结点的时间复杂度分别为( )。答案：O(1),O(n)?问题：9. 两顺序栈共享空间,也存在空间溢出问题。答案：正确问题：10.在对不带头结点的链队列作出队操作时,不会改变头指针的值。答案：错误第24章第25章第26章第27章第28章第29章第30章问题：1. 串是一种特殊的线性表,其特殊性体现在( )。答案：数据元素是字符问题：2. 若串S= software,其前缀真子串的数目是( )。答案：7问题：3. 设有两个串p和q ,其中q是p的子串,求q在p中首次出现的位置的算法称为( )。答案：串的模式匹配?问题：4. 已知串

5、S=aaab,其next函数值为( )。答案：0123问题：5. 函数strcmp(stcabuc,stbabuc)的返回值是( )。答案：1问题：6. KMP算法的特点是在模式匹配时指示主串的指针不会回溯。答案：正确问题：7. 模式串?P=abaabcac的next函数值序列为01122312。答案：正确问题：8. 串的存储结构有顺序串、堆串和块链串三种。答案：正确问题：9. 子串的定位运算称为串的模式匹配。答案：正确问题：10. 串student和Student相等。答案：错误第31章第32章第33章第34章第35章问题：1. 假设以行序为主序存储二维数组A=array1.100,1.10

6、0,设每个数组元素占2个存储单元,基地址为10,则LOC5,5=( )。答案：818问题：2. 若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B1.(n(n+1)/2中,则在B中确定aij(iLTag=0问题：4.设森林T中有4棵树,其结点个数分别为n1,n2,n3,n4,那么当森林T转换成一棵二叉树后,则根结点的右子树上有(?)个结点。答案：n2+n3+n4问题：5.以数据集4,5,6,7,10,12,18为叶结点权值所构造的哈夫曼树,其带权路径长度为( )。答案：165问题：6.以下属于前缀编码的是( )。答案：0,1101,1110,11

7、00,1111问题：7.一棵具有N个结点的二叉树采用二叉链表进行存储,其中空指针域有( ?)个。答案：N+1问题：8.已知一棵度为3的树有2个度为1的结点,3个度为2的结点,4个度为3的结点,则该树中有( )个叶子结点。答案：12问题：9. 满二叉树一定完全是二叉树。答案：正确问题：10.二叉树的遍历结果不是唯一的。答案：正确第52章第53章第54章第55章第56章第57章第58章第59章第60章第61章第62章第63章第64章第65章第66章问题：1.一个具有n个顶点的无向图最多有( )边。答案：n(n-1)/2?问题：2.对于一个具有n个顶点和e条边的无向图,若采用邻接表表示,则占用的存储

8、空间为( ?)。答案：n+2e问题：3.如果含有n个顶点的图形成一个环,则它有( ?)棵生成树。答案：n问题：4.任何一个无向连通网的最小生成树( )。答案：有一棵或多棵问题：5.判断一个有向图是否存在回路,可以用( )。答案：深度优先遍历算法问题：6.关键路径是事件结点网络中( ?)。答案：从源点到汇点的最长路径问题：7.深度优先遍历类似于二叉树的( )。答案：先序遍历?问题：8.广度优先遍历类似于二叉树的( )。答案：层次遍历问题：9.迪杰斯特拉算法求最短路径时,是按照路径长度递增的顺序求解的。答案：正确问题：10.任何一个有向图都一定存在拓扑序列。答案：错误第67章第68章第69章第70

9、章第71章第72章第73章第74章第75章问题：1. 具有12个关键字的有序表,折半查找的平均查找长度( )。答案：37/12问题：2. 如果要求用线性表既能较快地查找,又能适应动态变化的要求,则可采用( ?)查找方法。答案：分块查找问题：3. 已知一如下10个记录的表,其关键字序列为(2,15,19,25,30,34,44,55,58,80),用折半查找法查找关键字为55的记录,比较次数是( )。答案：2次问题：4. 如果按关键码值递增的顺序依次将99个关键码值插入到二叉排序树中,则对这样的二叉排序树检索时,在等概率情况下查找成功时的平均查找长度ASL为( )。?答案：50问题：5. 对包含

10、n个元素的散列表进行查找,平均查找长度为( )。答案：不直接依赖于n问题：6. 衡量查找算法效率的主要标准是( )。答案：平均查找长度问题：7. Hash表的平均查找长度与处理冲突的方法无关。答案：错误问题：8. 在二叉树排序树中插入一个新结点,总是插入到叶结点下面。答案：正确问题：9. 哈希表是一种将关键字转换为存储地址的存储方法。答案：正确问题：10.在二叉排序树上删除一个结点时,不必移动其它结点,只要将该结点的父结点的相应的指针域置空即可。答案：错误第76章第77章第78章第79章第80章第81章第82章第83章第84章第85章第86章问题：1. 有一组数据(15,9,7,8,20,-1

11、,7,4),用堆排序的筛选方法建立的初始小根堆为( )。答案：-1,4,7,8,20,15,7,9问题：2. 一组记录的关键字为(46,79,56,38,40,84),则利用快速排序的方法,以第一个记录为基准得到的一次划分结果为( )。答案：(40, 38, 46, 56, 79, 84)问题：3. 对下列整数序列使用基数排序,一趟分配收集之后的结果是( )。(179,208,93,306,55,859,984,9,271,33)答案：271,93,33,984,55,306,208,179,859,9问题：4. 对序列15,9,7,8,20,-1,4进行排序,进行一趟后数据的排列变为9,15

12、,7,8,20,-1,4,则采用的排序方法是( )。答案：直接插入排序问题：5. 评价排序算法好坏的标准主要是( )。答案：执行时间和所需的辅助空间问题：6. 对n个不同的排序码进行冒泡(递增)排序,在下列(?)情况比较的次数最多。答案：从大到小排列好的问题：7. 简单选择排序和堆排序性能都受初始序列顺序的影响。答案：错误问题：8. 快速排序算法在每一趟排序中都能找到一个元素放在其最终位置上。答案：正确问题：9. 堆排序所需的时间与待排序的记录个数无关。答案：错误问题：10. 采用希尔方法排序时,若关键字的排列杂乱无序,则效率最高。答案：正确第87章第88章第89章第90章第91章第92章第93章第94章第95章第96章第97章第98章第99章第100章第101章问题：文件压缩产品最主要的功能是（）。答案：压缩#解压问题：哈夫曼树最典型、最广泛的应用是在编码技术上。利用哈夫曼树，构造所得的哈弗曼编码是一种最优前缀编码。答案：正确问题：在设计产品时，只需要办好程序员的角色就可以了。答案：错误第102章