大学《数据结构与算法》各章节测试题与答案

《数据结构与算法》的答案

第I章

第2章

第3章

第4章

第5章

第6章

第7章

问题：1.在数据结构中，从逻辑上可以把数据结构分成()。

答案：线性结构和非线性结构

问题：2.在数据结构中,从存储结构上可以将之分为()。

答案：顺序存储和非顺序存储

问题：3.某算法的时间复杂度是0(M2),表明该算法的(??)。

答案：执行时间与M2成正比

问题：4.在下面的程序段中,x=x+l;的语句频度为()。for(i=l;i<=n;i++)

for(j=l;j<=n;j++)x=x+l;

答案：0(nA2)

问题：5.以下数据结构中,()是非线性数据结构。

答案：树

问题：6.顺序存储，存储单元的地址()。

答案：一定连续

问题：7.评价一个算法性能好坏的重要标准是（）。

答案：算法的时间和空间复杂度

问题：8.若需要利用形式参数直接访问修改实参值，则应将形参说明为（）参

数。

答案：指针

问题：9.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

答案：错误

问题：10.数据结构中评价算法的两个重要指标是算法的时间复杂度和空

间复杂度。

答案：正确

第8章

第9章

第10章

第11章

第12章

第13章

第14章

问题：1.下述哪一条是顺序存储结构的优点（）。

答案：存储密度大

问题：2.若某线性表最常用的操作是存取任一指定序号的元素和在最后进

行插入和删除运算，则利用()存储方式最节省时间。

答案：顺序表?？

问题：3.设某顺序表中第一个元素的地址是se(下标从1开始)，每个结点占

m个单元，则第i个结点的地址为()。

答案:se+(i-l)xm

问题：4.某线性表中最常用的操作是在最后一个元素之后插入一个元素和

删除第一个元素,则采用0存储方式最节省运算时间。

答案：仅有尾指针的单循环链表

问题：5.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个

新元素的算法的时间复杂度为()。

答案：O(n)??

问题：6.在单链表指针为p的结点之后插入指针为s的结点，正确的操作是

()。

答案：s->next=p->next;p->next=s;

问题：7.对于一个头指针为head的带头结点的单链表，判定该表为空表的

条件是()。????????

答案：head-next==NULL;

问题：8.静态链表与动态链表在元素的插入、删除上类似，不需做元素的移

动。

答案：正确

问题：9.顺序表适宜于顺序存取，而链表适宜于随机存取。

答案：错误

问题：10.线性表的链式存储结构中，逻辑上相邻的两个元素在物理位置上

并不一定相邻。

答案：正确

第15章

第16章

第17章

第18章

第19章

第20章

第21章

第22章

第23章

问题：1.栈和队列都是（）。

答案：限制存取点的线性结构?？

问题：2.设栈S和队列Q的初始状态为空，元素el,e2,e3,e4,e5和e6依次通

过栈S,一个元素出栈后随即进入队列Q,若6个元素出队的序列是

e2,e4,e3,e6,e5,el,则栈S的容量至少应该是（）。

答案：3

问题：3.设计一个判别表达式中括号是否匹配出现的算法，采用（）的数据结

构最佳。

答案：栈？？

问题：4.表达式a*（b+c）-d的后缀表达式是（）。

答案：abc+*d-??

问题：5.递归过程或函数调用时，处理参数及返回地址需要用一种（）的数据

结构。

答案•^9999999999

问题：6.最大容量为n的循环队列，队尾指针为rear,队头指针为front,则队

空的条件是（）。

答案：rear==front????????

问题：7.用带头结点的单链表表示队长大于1的队列时，其队头指针指向队

头结点，其队尾指针指向队尾结点，则在进行删除操作时（）。

答案：仅修改队头指针

问题：8.对于一个具有n个结点的单链表，在已知的结点*p后插入一个新

结点的时间复杂度和在给定值为x的结点后插入一个新结点的时间复杂度

分别为（）。

答案:O（l）,O（n）??

问题：9.两顺序栈共享空间，也存在空间溢出问题。

答案：正确

问题：10.在对不带头结点的链队列作出队操作时，不会改变头指针的值。

答案：错误

第24章

第25章

第26章

第27章

第28章

第29章

第3（）章

问题：1.串是一种特殊的线性表，其特殊性体现在（）。

答案：数据元素是字符

问题：2.若串S=，software：其前缀真子串的数目是（）。

答案：7

问题：3.设有两个串p和q，其中q是p的子串，求q在p中首次出现的位

置的算法称为（）。

答案：串的模式匹配?？

问题：4.已知串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=array口…100,1…10()],设每个

数组元素占2个存储单元，基地址为1(),则LOC[5,5]=()。

答案：818

问题：2.若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包

括主对角线上所有元素)依次存放于一维数组B[1…(n(n+l))⑵中，则在B中

确定aij(i<j)的位置k的计算公式为()。

答案：i(i-l)/2+j

问题:3.设广义表L=((a,b,c)),则L的长度和深度分别为()。

答案：1和2

问题：4.在稀疏矩阵的三元组顺序表中，每个三元组表示()。

答案：矩阵中非零元素的行号、列号和数据值

问题：5.多维数组可以看作是一种特殊的线性表。

答案：正确

问题：6.一个稀疏矩阵A[m,n]采用三元组顺序表形式表示，若把三元组中

有关行下标与列下标的值互换，并把m和n的值互换，则就完成了A[m,n]的

转置运算。？？

答案：错误

问题：7.广义表B=(a,B)=(a,(a,(a,...,??)))的长度为无穷大。

答案：正确

问题：8.一个广义表可以为其它广义表所共享。

答案：正确

问题：9.稀疏矩阵中非零元素的个数远小于矩阵中元素的总数。

答案：正确

问题：10.tail(head(((a,b,c,d,e))))=(a,b,c,d,e)»

答案：错误

第36章

第37章

第38章

第39章

第4()章

第41章

第42章

第43章

第44章

第45章

第46章

第47章

第48章

第49章

第50章

第51章

问题：1.树最适合用来表示的结构是（??）。

答案：元素间具有分支及层次关系的结构

问题：2.任意一棵二叉树的叶子结点在其先序、中序、后序序列中的相对

位置（）。

答案：肯定不发生变化

问题：3.判断线索二叉树中某结点P有左孩子的条件是（）。

答案：p->LTag==0

问题：4.设森林T中有4棵树，其结点个数分别为nl,n2,n3,n4,那么当森林

T转换成一棵二叉树后，则根结点的右子树上有（??）个结点。

答案：n2+n3+n4

问题：5.以数据集｛4,5,6,7,10,12,18｝为叶结点权值所构造的哈夫曼树，其带

权路径长度为（）。

答案：165

问题：6.以下属于前缀编码的是（）。

答案：{0,1101,1110,1100,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-l）/2??

问题：2.对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则占

用的存储空间为（??）»

答案:n+2e

问题：3.如果含有n个顶点的图形成一个环，则它有（？?）棵生成树。

答案：n

问题：4.任何一个无向连通网的最小生成树（）。

答案：有一棵或多棵

问题：5.判断一个有向图是否存在回路,可以用（）。

答案：深度优先遍历算法

问题：6.关键路径是事件结点网络中（？?）。

答案：从源点到汇点的最长路径

问题：7.深度优先遍历类似于二叉树的（）。

答案：先序遍历?？

问题：8.广度优先遍历类似于二叉树的（）。

答案：层次遍历

问题：9.迪杰斯特拉算法求最短路径时，是按照路径长度递增的顺序求解

的。

答案：正确

问题：10.任何一个有向图都一定存在拓扑序列。

答案：错误

第67章

第68章

第69章

第70章

第71章

第72章

第73章

第74章

第75章

问题：1.具有12个关键字的有序表，折半查找的平均查找长度（）。

答案：'37/12

问题：2.如果要求用线性表既能较快地查找，又能适应动态变化的要求，则

可采用（？?）查找方法。

答案：分块查找

问题：3.已知一如下10个记录的表，其关键字序列为

（2,15,19,25,30,34,44,55,58,8（））,用折半查找法查找关键字为55的记录，比较

次数是（）。

答案：2次

问题：4.如果按关键码值递增的顺序依次将99个关键码值插入到二叉排

序树中，则对这样的二叉排序树检索时,在等概率情况下查找成功时的平均

查找长度ASL为（）。??????

答案：5（）

问题：5.对包含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,7,4),用堆排序的筛选方法建立的初始

小根堆为()。

答案：-1,4,7,8,20,15,7,9

问题：2.一组记录的关键字为(46,79,56,38,4(),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