《数据结构与算法》习题：选择题、判断题.doc

《《数据结构与算法》习题：选择题、判断题.doc》由会员分享，可在线阅读，更多相关《《数据结构与算法》习题：选择题、判断题.doc（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1/10第一章第一章绪论绪论1.从逻辑上可以把数据结构分为C两大类。A动态结构、静态结构B顺序结构、链式结构C线性结构、非线性结构D初等结构、构造型结构2.在下面的程序段中，对 x 的赋值语句的频度为C。Fork=1；k=n；k+Forj=1；jnext=s；s-next=p-next；Bs-next=p-next；p-next=s；Cp-next=s；p-next=s-next；Dp-next=s-next；p-next=s；9在双向链表存储结构中，删除 p 所指的结点时须修改指针A。A p-prior)-next=p-next;p-next-prior=p-prior;Bp-prior=p

2、-prior-prior;p-prior-next=p;C p-next-prior=p;p-rlink=p-next-next;Dp-next=p-prior-prior;p-prior=p-next-next10.完成在双向循环链表结点 p 之后插入 s 的操作是D。Ap-next=s;s-prior=p;p-next-prior=s;s-next=p-next;Bp-next-prior=s;p-next=s;s-prior=p;s-next=p-next;Cs-prior=p;s-next=p-next;p-next=s;p-next-prior=s;Ds-prior=p;s-next

3、=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。3/10Atop-next=p；Bp-next=top-next；top-next=p；C

4、p-next=top；top=p；Dp-next=top；top=top-next；2对于栈操作数据的原那么是B。A先进先出 B后进先出C后进后出 D不分顺序3假设一个栈的入栈序列是 1，2，3，n，其输出序列为 p1，p2，p3，pn，假设pn是 n，那么 Pi为D。AiBniCnilD不确定4表达式 a*bcd 的后缀表达式是B。Aabcd*Babc*dCabc*dD*abcd5采用顺序存储的两个栈的共享空间 S1.m，用 topi代表第 i 个栈i=1，2的栈顶，栈 1 的底在 S1，栈 2 的底在 Sm，那么栈满的条件是B。Atop2top1=0Btop11=top2Ctop1top2

5、=mDtop1=top26一个栈的入栈序列是 a，b，c，d，e，那么栈的不可能的输出序列是C。AedcbaBdecbaCdceabDabcde7在一个链队列中，假设 f、r 分别为队首、队尾指针，那么插入 p 所指结点的操作为B。Af-next=p；f=pBr-next=p；r=pCp-next=r；r=pDp-next=f；f=p8用不带头结点的单链表存储队列时，在进展删除运算时D。A仅修改头指针 B仅修改尾指针C头、尾指针都要修改 D头、尾指针可能都要修改9.递归过程或函数调用时，处理参数与返回地址，要用一种称为C的数据结构。A队列B静态链表C栈D顺序表10.栈和队都是C。A顺序存储的线

6、性结构 B链式存储的非线性结构C限制存取点的线性结构 D限制存取点的非线性结构第四章第四章字符串与线性结构的扩展字符串与线性结构的扩展1.下面关于串的表达，错误的选项是C。A串是字符的有限序列B串既可以采用顺序存储，也可以采用链式存储C空串是由空格构成的串4/10D模式匹配是串的一种重要运算2.串的长度是指B。A串中所含不同字母的个数B串中所含字符的个数C串中所含不同字符的个数D串中所含非空格字符的个数3.4.二维数组 M 的成员是 6 个字符每个字符占一个存储单元，即一个字节组成的串，行下标 i 的围从 0 到 8，列下标 j 的围从 1 到 10，那么存放 M 至少需要1 D个字节；M 的

7、第 8 列和第 5 行共占2 A个字节；假设 M 按行优先方式存储，元素 M85的起始地址与当 M 按列优先方式存储时的3 C元素的起始地址一致。1A.90B.180C.240D.5402A.108B.114C.54D.603A.M85B.M310C.M58D.M095.数组 A 中，每个元素的存储占 3 个单元，行下标 i 从 1 到 8，列下标 j 从 1 到 10，从首地址 SA 开场连续存放在存储器，存放该数组至少需要的单元个数是1 C；假设该数组按行存放，元素 A85的起始地址为2 D；假设该数组按列存放，元素 A85的起始地址为3 B。1A.80B.100C.240D.2702A.

8、SA+141B.SA+144C.SA+222D.SA+2253A.SA+141B.SA+180C.SA+117D.SA+2256.稀疏矩阵采用压缩存储，一般有C两种方法。A二维数组和三维数组B三元组和散列C三元组表和十字链表D散列和十字链表第五章第五章树结构树结构1.以下说确的是C。A二叉树中任何一个结点的度都为 2B二叉树的度为 2C一棵二叉树的度可小于 2D任何一棵二叉树中至少有一个结点的度为 22.以二叉链表作为二叉树的存储结构，在具有 n 个结点的二叉链表中n0，空链域的个数为C。A2n1Bn1CnlD2nl3.线索化二叉树中，某结点*p 没有孩子的充要条件是B。A.p-lchild=

9、NULLB.p-ltag=1 且 p-rtag=1C.p-ltag=0D.p-lchild=NULL 且 p-ltag=14.如果结点 A 有 3 个兄弟，而且 B 是 A 的双亲，那么 B 的度是B。A3B4 C5D15/105.某二叉树T有n个结点，设按某种顺序对T中的每个结点进展编号，编号值为1，2，n，且有如下性质：T 中任意结点 v，其编号等于左子树上的最小编号减 1，而 v 的右子树的结点中，其最小编号等于 v 左子树上结点的最大编号加 1，这是按 B 编号的。A.中序遍历序列B.先序遍历序列C.后序遍历序列D.层次顺序6.设 F 是一个森林，B 是由 F 转换得到的二叉树，F 中

10、有 n 个非终端结点，B 中右指针域为空的结点有C个。An1BnCnlDn27.一棵完全二叉树上有 1001 个结点，其中叶子结点的个数是C。A500B501C490D4958.设森林 F 中有 3 棵树，第 1、第 2 和第 3 棵树的结点个数分别为 N1，N2和 N3。与森林F 对应的二叉树根结点的右子树上的结点个数是D。AN1BN1N2CN2DN2N39.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序A。A.不发生改变B.发生改变C.不能确定D.以上都不对10.假设一棵二叉树的后序遍历序列为 dabec，中序遍历序列为 debac，那么先序遍历序列为D。A.cbedB.de

11、cabC.deabcD.cedba11.假设一棵二叉树的先序遍历序列为 abdgcefh，中序遍历的序列为 dgbaechf，那么后序遍历的结果为D。A.gcefhaB.gdbecfhaC.bdgaechfD.gdbehfca12.一棵非空二叉树的先序遍历序列与后序遍历序列正好相反，那么该二叉树一定满足B。A.所有的结点均无左孩子B.所有的结点均无右孩子C.只有一个叶子结点 D.是一棵满二叉树13.设高度为 h 的二叉树上只有度为 0 和度为 2 的结点，那么此类二叉树中所包含的结点数至少为B。A.2hB.2h1C.2h1D.h114.一个具有 567 个结点的二叉树的高 h 为D。A.9B.

12、10C.9566 之间D.10567 之间第六章第六章图结构图结构1.n 条边的无向图的邻接表的存储中，边结点的个数有A。A.nB.2nC.n/2D.nn6/102.n 条边的无向图的邻接多重表的存储中，边结点的个数有A。A.nB.2nC.n/2D.nn3.以下哪一种图的邻接矩阵是对称矩阵？BA.有向图B.无向图C.AOV 网D.AOE 网4.最短路径的生成算法可用C。A.普利姆算法B.克鲁斯卡尔算法C.迪杰斯特拉算法D.哈夫曼算法5.一个无向图的邻接表如以下图所示。1从顶点 v0出发进展深度优先搜索，经历的结点顺序为B。A.v0，v3，v2，v1B.v0，v1，v2，v3C.v0，v2，v1

13、，v3D.v0，v1，v3，v22从顶点 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(en)C.O(elog2n)D.O(ne)7.含有 n 个顶点 e 条边的无向连通图，利用 Kruskal 算法生成最小生成树，其时间复杂度为A。A.O(elog2e)B.O(en)C.O(elog2n)D.O(nlog2n)8.关键路径是事件结点网络中A。A.从源点到汇点的最长路径 B.从源点到汇点的最

14、短路径C.最长的回路 D.最短的回路9.下面关于求关键路径的说法，不正确的选项是C。A.求关键路径是以拓扑排序为根底的B.一个事件的最早开场时间同以该事件为尾的弧的活动最早开场时间一样C.一个事件的最迟开场时间为以该事件为尾的弧的活动最迟开场时间与该活动的持续时间的差D.关键活动一定位于关键路径上10.有 10 个结点的无向图至少有B条边才能确保其是连通图。A.8B.9C.10D.117/10第七章第七章查找查找1.静态查找表与动态查找表的根本区别在于B。A.它们的逻辑结构不一样 B.施加在其上的操作不一样C.所包含的数据元素类型不一样 D.存储实现不一样2.在表长为 n 的顺序表上实施顺序查

15、找，在查找不成功时与关键字比拟的次数为A。A.nB.1 C.n+1D.n-13.顺序查找适用于存储结构为C的线性表。A.散列存储 B.压缩存储C.顺序存储或链式存储 D.索引存储4.用顺序查找法对具有 n 个结点的线性表查找一个结点的时间复杂度为C。AO(log2n2)B.O(nlog2n)C.O(n)D.O(log2n)5.适用于折半查找的表的存储方式与元素排列要求为D。A.方式存储，元素无序B.方式存储，元素有序C.顺序方式存储，元素无序D.顺序方式存储，元素有序6.有一个长度为 12 的有序表，按折半查找法对该表进展查找，在表各元素等概率情况下查找成功所需的平均比拟次数为B。A.35/1

16、2B.37/12C.39/12D.43/127.在有序表1，3，9，12，32，41，62，75，77，82，95，100上进展折半查找关键字为 82 的数据元素需要比拟C次。A.1B.2C.4D.58.设散列表长为 14，散列函数为 Hkey=key%11。当前表中已有 4 个结点：addr(15)=4，addr(38)=5，addr(61)=6，addr(84)=7。如用二次探测再散列处理冲突，那么关键字为 49 的结点的地址是D。A.8B.3C.5D.99.散列函数有一个共同的性质，即函数值应当以D取其值域的每个值。A.最大概率B.最小概率C.平均概率D.同等概率8/1010.假定有 k

17、 个关键字互为同义词，假设用线性探测法把这 k 个关键字存入散列表中，至少要进展D次探测。A.k1 次B.k 次C.k1 次D.kk1/2 次11.在散列函数 Hk=k%m 中，一般来讲，m 应取C。A.奇数B.偶数C.素数D.充分大的数12.在采用线性探测法处理冲突所构成的散列表上进展查找，可能要探测多个位置，在查找成功的情况下，所探测到的这些位置上的键值B。A.一定是同义词 B.一定不是同义词C.都一样 D.不一定都是同义词第八章第八章排序排序1.在待排序的元素序列根本有序的前提下，效率最高的排序方法是A。A.插入排序 B.选择排序 C.快速排序 D.归并排序2.设有 1000 个无序的元

18、素，希望用最快的速度挑选出其中前 10 个最大的元素，最好选用C排序法。A.冒泡排序 B.快速排序 C.堆排序 D.基数排序3.具有 12 个记录的序列，采用冒泡排序最少的比拟次数是C。A.1B.144C.11D.664.以下四种排序方法中，要求存容量最大的是D。A.插入排序 B.选择排序 C.快速排序 D.归并排序5.初始序列已经按键值有序时，用直接插入算法进展排序，需要比拟的次数为 D。An2B.nlog2nC.log2nD.n16.以下四种排序方法，在排序过程中，关键码比拟的次数与记录的初始排列顺序无关的是C。A.直接插入排序和快速排序B.快速排序和归并排序C.直接选择排序和归并排序D.

19、直接插入排序和归并排序7.一组记录的排序码为46，79，56，38，40，84，那么利用堆排序的方法建立的初始堆为B。A.79，46，56，38，40，84B.84，79，56，38，40，46C.84，79，56，46，40，38D.84，56，79，40，46，388.一组记录的排序码为46，79，56，38，40，84，那么利用快速排序的方法，以第一个记录为基准得到的一次划分结果为C。A.38，40，46，56，79，84B.40，38，46，79，56，849/10C.40，38，46，56，79，84D.40，38，46，84，56，799.用某种排序方法对线性表 25，84，21，

20、47，15，27，68，35，20进展排序时，元素序列的变化情况如下：125，84，21，47，15，27，68，35，20220，15，21，25，47，27，68，35，84315，20，21，25，35，27，47，68，84415，20，21，25，27，35，47，68，84那么所采用的排序方法是D。A.选择排序 B.希尔排序 C.归并排序 D.快速排序10.快速排序方法在C情况下最不利于发挥其长处。A.要排序的数据量太大 B.要排序的数据中含有多个一样值C.要排序的数据已根本有序 D.要排序的数据个数为奇数第一章第一章绪论绪论1.数据的逻辑结构是指数据的各个数据项之间的逻辑关系。2

21、.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。3.数据的逻辑结构说明数据元素之间的次序关系，它依赖于数据的存储结构。4.算法优劣与描述算法的语言无关，但与所用计算机的性能有关。5.算法必须有输出，但可以没有输入。第二章第二章线性表线性表1线性表的逻辑顺序与存储顺序总是一致的。2顺序存储的线性表可以按序号随机存取。3顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。4线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有一样的特性，因此是属于同一数据对象。5在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。6在线性表

22、的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。7线性表的链式存储结构优于顺序存储结构。8在线性表的顺序存储结构中，插入和删除时移动元素的个数与该元素的位置有关。9线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。10在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。11静态链表既有顺序存储的优点，又有动态链表的优点。所以它存取表中第 i 个元素的时间与 i无关。12线性表的特点是每个元素都有一个前驱和一个后继。第三章第三章栈和队列栈和队列10/10第四章第四章字符串与线性结构的扩展字符串与线性结构的扩展第五章第五章树结构树结构1.二叉树是树的特殊形式。2.由树转换成二叉树，其根结点的右子树总是空的。20.满二叉树一定是完全二叉树，反之未必。第六章第六章图结构图结构第七章第七章查找查找第八章第八章排序排序