《数据结构与算法》(张晓莉)习题：选择题、判断题

第一章绪论1.从逻辑上可以把数据结构分为（C）两大类。A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构2.在下面的程序段中，对x的赋值语句的频度为（C）。For（k=1；k=n；k++）For（j=1；j=n；j++）x=x＋1；A．O(2n)B．O(n)C．O(n2)D．O(log2n)3.采用顺序存储结构表示数据时，相邻的数据元素的存储地址（A）。A．一定连续B．一定不连续C．不一定连续D．部分连续、部分不连续4.下面关于算法的说法，正确的是（D）。A．算法的时间复杂度一般与算法的空间复杂度成正比B．解决某问题的算法可能有多种，但肯定采用相同的数据结构C．算法的可行性是指算法的指令不能有二义性D．同一个算法，实现语言的级别越高，执行效率就越低5.在发生非法操作时，算法能够作出适当处理的特性称为（B）。A．正确性B．健壮性C．可读性D．可移植性第二章线性表1.线性表是（A）。A．一个有限序列，可以为空B．一个有限序列，不能为空C．一个无限序列，可以为空D．一个无限序列，不能为空2．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（A）个元素。A．n/2B．（n＋1）/2C．（n－1）/2D．n3．线性表采用链式存储时，其地址（D）。A．必须是连续的B．部分地址必须是连续的C．一定是不连续的D．连续与否均可以4．用链表表示线性表的优点是（C）。A．便于随机存取B．花费的存储空间较顺序存储少C．便于插入和删除D．数据元素的物理顺序与逻辑顺序相同5．链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用（C）存储方式最节省运算时间。A．单链表B．双链表C．单循环链表D．带头结点的双向循环链表6．下面关于线性表的叙述，错误的是（B）。A．线性表采用顺序存储，必须占用一片地址连续的单元B．线性表采用顺序存储，便于进行插入和删除操作C．线性表采用链式存储，不必占用一片地址连续的单元D．线性表采用链式存储，不便于进行插入和删除操作7．单链表中，增加一个头结点的目的是为了（C）。A．使单链表至少有一个结点B．标识表结点中首结点的位置C．方便运算的实现D．说明单链表是线性表的链式存储8．在单链表指针为p的结点之后插入指针为s结点，正确的操作是（B）。A．p-next=s；s-next=p-next；B．s-next=p-next；p-next=s；C．p-next=s；p-next=s-next；D．p-next=s-next；p-next=s；9．在双向链表存储结构中，删除p所指的结点时须修改指针（A）。A．（p-prior)-next=p-next;（p-next）-prior=p-prior;B．p-prior=（p-prior）-prior;（p-prior）-next=p;C．（p-next）-prior=p;p-rlink=（p-next）-next;D．p-next=（p-prior）-prior;p-prior=（p-next）-next10.完成在双向循环链表结点p之后插入s的操作是（D）。A．p-next=s;s-prior=p;p-next-prior=s;s-next=p-next;B．p-next-prior=s;p-next=s;s-prior=p;s-next=p-next;C．s-prior=p;s-next=p-next;p-next=s;p-next-prior=s;D．s-prior=p;s-next=p-next;p-next-prior=s;p-next=s;11.若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（B）存储方式最节省运算时间。A．单链表B．顺序表C．双向链表D．单循环链表12.若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（D）存储方式最节省运算时间。A．单链表B．仅有头指针的单循环链表C．双向链表D．仅有尾指针的单循环链表第三章栈和队列1．向一个栈顶指针为top的链栈中插入一个p所指结点时，其操作步骤为（C）。A．top-next=p；B．p-next=top-next；top-next=p；C．p-next=top；top=p；D．p-next=top；top=top-next；2．对于栈操作数据的原则是（B）。A．先进先出B．后进先出C．后进后出D．不分顺序3．若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若pn是n，则Pi为（D）。A．iB．n－iC．n－i＋lD．不确定4．表达式a*（b－c）＋d的后缀表达式是（B）。A．abcd*－＋B．abc－*d＋C．abc*－d＋D．＋－*abcd5．采用顺序存储的两个栈的共享空间S[1..m]，用top[i]代表第i个栈（i=1，2）的栈顶，栈1的底在S[1]，栈2的底在S[m]，则栈满的条件是（B）。A．top[2]－top[1]=0B．top[1]＋1=top[2]C．top[1]＋top[2]=mD．top[1]=top[2]6．一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是（C）。A．edcbaB．decbaC．dceabD．abcde7．在一个链队列中，若f、r分别为队首、队尾指针，则插入p所指结点的操作为（B）。A．f-next=p；f=pB．r-next=p；r=pC．p-next=r；r=pD．p-next=f；f=p8．用不带头结点的单链表存储队列时，在进行删除运算时（D）。A．仅修改头指针B．仅修改尾指针C．头、尾指针都要修改D．头、尾指针可能都要修改9.递归过程或函数调用时，处理参数及返回地址，要用一种称为（C）的数据结构。A．队列B．静态链表C．栈D．顺序表10.栈和队都是（C）。A．顺序存储的线性结构B．链式存储的非线性结构C．限制存取点的线性结构D．限制存取点的非线性结构第四章字符串及线性结构的扩展1.下面关于串的叙述，错误的是（C）。A．串是字符的有限序列B．串既可以采用顺序存储，也可以采用链式存储C．空串是由空格构成的串D．模式匹配是串的一种重要运算2.串的长度是指（B）。A．串中所含不同字母的个数B．串中所含字符的个数C．串中所含不同字符的个数D．串中所含非空格字符的个数3.4.二维数组M的成员是6个字符（每个字符占一个存储单元，即一个字节）组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要（1）（D）个字节；M的第8列和第5行共占（2）（A）个字节；若M按行优先方式存储，元素M[8][5]的起始地址与当M按列优先方式存储时的（3）（C）元素的起始地址一致。（1）A.90B.180C.240D.540（2）A.108B.114C.54D.60（3）A.M[8][5]B.M[3][10]C.M[5][8]D.M[0][9]5.数组A中，每个元素的存储占3个单元，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元个数是（1）（C）；若该数组按行存放，元素A[8][5]的起始地址为（2）（D）；若该数组按列存放，元素A[8][5]的起始地址为（3）（B）。（1）A.80B.100C.240D.270（2）A.SA+141B.SA+144C.SA+222D.SA+225（3）A.SA+141B.SA+180C.SA+117D.SA+2256.稀疏矩阵采用压缩存储，一般有（C）两种方法。A．二维数组和三维数组B．三元组和散列C．三元组表和十字链表D．散列和十字链表第五章树结构1.下列说法正确的是（C）。A．二叉树中任何一个结点的度都为2B．二叉树的度为2C．一棵二叉树的度可小于2D．任何一棵二叉树中至少有一个结点的度为22.以二叉链表作为二叉树的存储结构，在具有n个结点的二叉链表中（n＞0），空链域的个数为（C）。A．2n－1B．n－1C．n＋lD．2n＋l3.线索化二叉树中，某结点*p没有孩子的充要条件是（B）。A.p-lchild=NULLB.p-ltag=1且p-rtag=1C.p-ltag=0D.p-lchild=NULL且p-ltag=14.如果结点A有3个兄弟，而且B是A的双亲，则B的度是（B）。A．3B．4C．5D．15.某二叉树T有n个结点，设按某种顺序对T中的每个结点进行编号，编号值为1，2，…，n，且有如下性质：T中任意结点v，其编号等于左子树上的最小编号减1，而v的右子树的结点中，其最小编号等于v左子树上结点的最大编号加1，这是按（B）编号的。A.中序遍历序列B.先序遍历序列C.后序遍历序列D.层次顺序6.设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点，B中右指针域为空的结点有（C）个。A．n－1B．nC．n＋lD．n＋27.一棵完全二叉树上有1001个结点，其中叶子结点的个数是（C）。A．500B．501C．490D．4958.设森林F中有3棵树，第1、第2和第3棵树的结点个数分别为N1，N2和N3。与森林F对应的二叉树根结点的右子树上的结点个数是（D）。A．N1B．N1＋N2C．N2D．N2＋N39.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（A）。A.不发生改变B.发生改变C.不能确定D.以上都不对10.若一棵二叉树的后序遍历序列为dabec，中序遍历序列为debac，则先序遍历序列为（D）。A.cbedB.decabC.deabcD.cedba11.若一棵二叉树的先序遍历序列为abdgcefh，中序遍历的序列为dgbaechf，则后序遍历的结果为（D）。A.gcefhaB.gdbecfhaC.bdgaechfD.gdbehfca12.一棵非空二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（B）。A.所有的结点均无左孩子B.所有的结点均无右孩子C.只有一个叶子结点D.是一棵满二叉树13.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（B）。A.2hB.2h－1C.2h＋1D.h＋114.一个具有567个结点的二叉树的高h为（D）。A.9B.10C.9～566之间D.10～567之间第六章图结构1.n条边的无向图的邻接表的存储中，边结点的个数有（A）。A.nB.2nC.n/2D.n×n2.n条边的无向图的邻接多重表的存储中，边结点的个数有（A）。A.nB.2nC.n/2D.n×n3.下列哪一种图的邻接矩阵是对称矩阵？（B）A.有向图B.无向图C.AOV网D.AOE网4.最短路径的生成算法可用（C）。A.普利姆算法B.克鲁斯卡尔算法C.迪杰斯特拉算法D.哈夫曼算法5.一个无向图的邻接表如下图所示。序号vertexfirstedge13023011^^^^v0v1v2v30123（1）从顶点v0出发进行深度优先搜索，经历的结点顺序为（B）。A.v0，v3，v2，v1B.v0，v1，v2，v3C.v0，v2，v1，v3D.v0，v1，v3，v2（2）从顶点v0出发进行广度优先搜索，经历的结点顺序为（D）。A.v0，v3，v2，v1B.v0，v1，v2，v3C.v0，v2，v1，v3D.v0，v1，v3，v26.设有向图n个顶点和e条边，进行拓扑排序时，总的计算时间为（D）。A.O(nlog2e)B.O(e×n)C.O(elog2n)D.O(n＋e)7.含有n个顶点e条边的无向连通图，利用Kruskal算法生成最小生成树，其时间复杂度为（A）。A.O(elog2e)B.O(e×n)C.O(elog2n)D.O(nlog2n)8.关键路径是事件结点网络中（A）。A.从源点到汇点的最长路径B.从源点到汇点的最短路径C.最长的回路D.最短的回路9