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

1、第一章绪论1.从逻辑上可以把数据结构分为（A.动态结构、静态结构C.线性结构、非线性结构C）两大类。B.顺序结构、链式结构D.初等结构、构造型结构2.在下面的程序段中，对 x 的赋值语句的频度为(C)For(k=1；k=n；k+)For(j=1；jnext=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)cA.(p-prior)-next=p-next;(p-next)-prior=p-pr

2、ior;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-ne

3、xt=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）

4、。B. p-next=top-next;top-next=p；D.p-next=top；top=top-next;2 .对于栈操作数据的原则是（A.top-next=p；C.p-next=top；top=p；A.先进先出 B.后进先出C.后进后出 D.不分顺序3 .若已知一个栈的入栈序列是 1,2,3,，n,其输出序列为 pi,P2,P3,，Pn,若 Pn是 n,则 R 为（D）。A.iB.n-iC.n-i+lD,不确定4 .表达式 a*（b-c）+d 的后缀表达式是（B）。A.abcd*+B.abc*d+C. abc*d+D.+*abcd5.采用顺序存储的两个栈的共享空间 S1.m,用 to

5、pi代表第 i 个栈（i=1,2）的栈顶,栈 1 的底在 S1,栈 2 的底在 Sm,则栈满的条件是（B）。A.top2top1=0B.top1+1=top2C.top1+top2=mD.top1=top26 .一个栈的入栈序列是 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

6、）oA.仅修改头指针 B,仅修改尾指针C.头、尾指针都要修改 D.头、尾指针可能都要修改9 .递归过程或函数调用时，处理参数及返回地址，要用一种称为（C）的数据结构。第四章字符串及线性结构的扩展1 .下面关于用的叙述，错误的是（C）。A.用是字符的有限序列B.用既可以采用顺序存储，也可以采用链式存储C.空用是由空格构成的用D.模式匹配是用的一种重要运算2 .用的长度是指（B）。A.用中所含不同字母的个数 B,用中所含字符的个数C.用中所含不同字符的个数 D.用中所含非空格字符的个数 3.4 .二维数组 M 的成员是 6 个字符（每个字符占一个存储单元，即一个字节）组成的申，行下标 i 的范围从

7、 0 到 8,列下标 j 的范围从 1 至 IJ10,则存放 M 至少需要（1）（D）个字节；M 的A.队列 B.静态链表C.栈 D.顺序表10.栈和队都是（C）。A.顺序存储的线性结构C.限制存取点的线性结构B.链式存储的非线性结构D.限制存取点的非线性结构第 8 列和第 5 行共占 0（A）个字节；若 M 按行优先方式存储，元素 M85的起始地址与当 M按列优先方式存储时的 J（C）元素的起始地址一致。（1） A.90B.180C.240D.540（2）A.108B.114C.54D.60（3）A.M85B.M310C.M58D.M095 .数组 A 中，每个元素的存储占 3 个单元，行下

8、标 i 从 1 到 8,列下标 j 从 1 到 10,从首地址SA 开始连续存放在存储器内，存放该数组至少需要的单元个数是 5（C）;若该数组按行存放，元素 A85的起始地址为21（D）;若该数组按列存放，元素 A85的起始地址为（J!（B）0（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）

9、。A.二叉树中任何一个结点的度都为 2B.二叉树的度为 2C.一棵二叉树的度可小于 2D,任何一棵二叉树中至少有一个结点的度为 22 .以二叉链表作为二叉树的存储结构，在具有 n 个结点的二叉链表中（n0）,空链域的个数为（C）。A.2n1B.n-1C.n+lD,2n+l3 .线索化二叉树中，某结点*p 没有孩子的充要条件是（B）0A.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 .某二叉树

10、 T 有 n 个结点，设按某种顺序对 T 中的每个结点进行编号，编号值为 1,2,n,且有如下性质：T 中任意结点 v,其编号等于左子树上的最小编号减 1,而 v 的右子树的结点中，其最小编号等于 v 左子树上结点的最大编号加 1,这是按（B）编号 IA.中序遍历序列 B.先序遍历序列 C.后序遍历序列 D.层次顺序6 .设 F 是一个森林，B 是由 F 转换得到的二叉树，F 中有 n 个非终端结点，B 中右指针域为空的结点有（C）个。7 .一棵完全二叉树上有 1001 个结点，其中叶子结点的个数是（C）。A.500B.501C.490D.4958 .设森林 F 中有 3 棵树，第 1、第 2

11、 和第 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.gdbecfha

12、C.bdgaechfD.gdbehfca12 .一棵非空二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（B）。A.所有的结点均无左孩子 B.所有的结点均无右孩子C.只有一个叶子结点 D.是一棵满二叉树13 .设高度为 h 的二叉树上只有度为 0 和度为 2 的结点，则此类二叉树中所包含的结点数至少为（B）。A.2hB.2h-1C.2h+1D.h+114 .一个具有 567 个结点的二叉树的高八为（D）。A.9B.10C.9566 之间 D.10567 之间第六章图结构1.n 条边的无向图的邻接表的存储中，边结点的个数有（A）。A.nB.2nC.n/2D.nn2. n 条边的无向

13、图的邻接多重表的存储中，边结点的个数有（A）。A.nB.2nC.n/2D.nn3. 下列哪一种图的邻接矩阵是对称矩阵？（B）A.有向图 B.无向图 C.AOV 网 D.AOE 网4. 最短路径的生成算法可用（C）。A.普利姆算法 B.克鲁斯卡尔算法 C.迪杰斯特拉算法 D.哈夫曼算法B.nC.n+lD.n+2A.nB.1C.n+1D.n-15. 一个无向图的邻接表如下图所示(1)从顶点 V0 出发进行深度优先搜索，经历的结点顺序为(B)0A.V0,V3,V2,V1B.V0,Vi,V2,V3C.V0,V2,V1,V3D.V0,V1,V3,V2(2)从顶点 V0 出发进行广度优先搜索，经历的结点顺

14、序为(D)0A.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 苗 C.O(elog2n)D.O(n+e)7 .含有 n 个顶点 e 条边的无向连通图，利用 Kruskal 算法生成最小生成树，其时间复杂度为（A）oA.O（elog2e）B.O（e 为 C.O（elog2n）D.O（nlog2n）9 .下面关于求关键路径的说法，不正确的是（C）。A.求关键路径是以拓扑排序为基础的B. 一个事件的最早开始时间同以该事件为尾的弧的活动最早

15、开始时间相同C. 一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差D.关键活动一定位于关键路径上10 .有 10 个结点的无向图至少有（B）条边才能确保其是连通图A.8B.9C.10D.11第七章查找1 .静态查找表与动态查找表的根本区别在于（B）。A.它们的逻辑结构不一样 B.施加在其上的操作不一样C.所包含的数据元素类型不一样 D.存储实现不一样2.在表长为 n 的顺序表上实施顺序查找，在查找不成功时与关键字比较的次数为（A）。8.关键路径是事件结点网络中（A.从源点到汇点的最长路径C.最长的回路A）。B.从源点到汇点的最短路径D.最短的回路序号vertex

16、firstedge3 .顺序查找适用于存储结构为(C)的线性表。A,散列存储 B.压缩存储C.顺序存储或链式存储 D.索引存储4 .用顺序查找法对具有 n 个结点的线性表查找一个结点的时间复杂度为(C)。2A.O(log2n)B.O(nlog2n)C.O(n)D.O(log2n)5 .适用于折半查找的表的存储方式及元素排列要求为(D)。A.链接方式存储，元素无序B.链接方式存储，元素有序C.顺序方式存储，元素无序D.顺序方式存储，元素有序6.有一个长度为 12 的有序表，按折半查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为(B)。A.35/12B.37/12C.39

17、/12D.43/12A.1B.2C.4D.58 .设散列表长为 14,散列函数为 H(key)=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.同等概率10 .假定有 k 个关键字互为同义词，若用线性探测法把这 k 个关键字存入散列表中，至少要进行(D)次探测。A.k1 次 B.k 次 C.k+1 次 D.k(

18、k+1)/2 次11 .在散列函数 H(k)=k%m 中，一般来讲，m 应取(C)A.奇数 B.偶数 C.素数 D.充分大的数12 .在采用线性探测法处理冲突所构成的散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测到的这些位置上的键值(B)。A.一定是同义词 B.一定不是同义词C.都相同 D.不一定都是同义词7.在有序表1,3,9,12,32,41,62,为 82 的数据元素需要比较(C)次。75,77,82,95,100上进行折半查找关键字第八章排序1 .在待排序的元素序列基本有序的前提下，效率最高的排序方法是（A）0A.插入排序 B.选择排序 C.快速排序 D.归并排序2

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

20、.直接插入排序和快速排序 B.快速排序和归并排序C.直接选择排序和归并排序 D.直接插入排序和归并排序125,84,21,47,220,15,21,25,315,20,21,25,415,20,21,25,7. 一组记录的排序码为(46,79,56,38,堆为(B)。A.79,46,56,38,40,84B.84,C.847956464038D.848. 一组记录的排序码为(46,79,56,38,个记录为基准得到的一次划分结果为(CA.384046567984B.40C.403846567984D.4040,84）,则利用堆排序的方法建立的初始7956384046567940463840,8

21、4）,则利用快速排序的方法，以第一）。384679568438468456799 .用某种排序方法对线性表（25,84,21,47,15,27,68,35,20）进行排序时,元素序列的变化情况如下：1527683520472768358435274768842735476884则所采用的排序方法是（D）10 .快速排序方法在（C）情况下最不利于发挥其长处。A.要排序的数据量太大 B.要排序的数据中含有多个相同值C.要排序的数据已基本有序 D.要排序的数据个数为奇数第一章绪论1 1 . .数据的逻辑结构是指数据的各个数据项之间的逻辑关系。2 2 .顺序存储方式的优点是存储密度大，且插入、删除运算效率高。3 3 . .数据的逻辑结构说明数据元素之间的次序关系，它依赖于数据的存储结构。4 4 . .算法优劣与描述算法的语言无关，但与所用计算机的性能有关。5