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

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

1、第一章 绪论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 。Ap- prior)- next = p-next ; p-next-prior =p- prior ;Bp-

2、 prior=p- prior- prior ; p- prior- next =p ;Cp-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;

3、 s- next = p-next; p- next =s; p- next- prior =s;Ds- 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向一个栈顶

4、指针为top的链栈中插入一个p所指结点时，其操作步骤为 C 。Atop-next=p； Bp-next=top-next；top-next=p；Cp-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 。Ai Bni Cnil D不确定4表达式a *bcd的后缀表达式是 B 。Aabcd* Babc*dCabc*d D*abcd5采用顺序存储的两个栈的共享空间S1.m，用topi代

5、表第i个栈i=1，2的栈顶，栈1的底在S1，栈2的底在Sm，那么栈满的条件是 B 。Atop2top1=0 Btop11= top2Ctop1top2 =m Dtop1= top26一个栈的入栈序列是a，b，c，d，e，那么栈的不可能的输出序列是 C 。Aedcba Bdecba Cdceab Dabcde7在一个链队列中，假设f、r分别为队首、队尾指针，那么插入p所指结点的操作为 B 。Af-next=p；f=p Br-next=p；r=pCp-next=r；r=p Dp-next=f；f=p8用不带头结点的单链表存储队列时，在进展删除运算时 D 。A仅修改头指针 B仅修改尾指针C头、尾指针

6、都要修改 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的成员

7、是6个字符每个字符占一个存储单元，即一个字节组成的串，行下标i的范围从0到8，列下标j的范围从1到10，那么存放M至少需要1 D 个字节；M的第8列与第5行共占2 A 个字节；假设M按行优先方式存储，元素M85的起始地址与当M按列优先方式存储时的3 C 元素的起始地址一致。1A. 90 B. 180 C. 240 D. 5402A. 108 B. 114 C. 54 D. 603A. M85 B. M310 C. M58 D. M095. 数组A中，每个元素的存储占3个单元，行下标i从1到8，列下标j从1到10，从首地址SA开场连续存放在存储器内，存放该数组至少需要的单元个数是1 C ；假设该

8、数组按行存放，元素A85的起始地址为2 D ；假设该数组按列存放，元素A85的起始地址为3 B 。1A. 80 B. 100 C.240 D. 2702A. SA+141 B. SA+144 C. SA+222 D. SA+2253A. SA+141 B. SA+180 C. SA+117 D. SA+2256. 稀疏矩阵采用压缩存储，一般有 C 两种方法。A二维数组与三维数组 B三元组与散列C三元组表与十字链表 D散列与十字链表第五章 树构造1. 以下说法正确的选项是 C 。A二叉树中任何一个结点的度都为2 B二叉树的度为2C一棵二叉树的度可小于2 D任何一棵二叉树中至少有一个结点的度为22

9、. 以二叉链表作为二叉树的存储构造，在具有n个结点的二叉链表中n0，空链域的个数为 C 。A2n1 Bn1 Cnl D2nl3. 线索化二叉树中，某结点*p没有孩子的充要条件是 B 。A. p-lchild=NULL B. p-ltag=1且p-rtag=1C. p-ltag=0 D. p-lchild=NULL且p-ltag=14. 如果结点A有3个兄弟，而且B是A的双亲，那么B的度是 B 。A3 B4 C5 D15. 某二叉树T有n个结点，设按某种顺序对T中的每个结点进展编号，编号值为1，2，n，且有如下性质：T中任意结点v，其编号等于左子树上的最小编号减1，而v的右子树的结点中，其最小编

10、号等于v左子树上结点的最大编号加1，这是按 B 编号的。A. 中序遍历序列 B. 先序遍历序列 C. 后序遍历序列 D. 层次顺序6. 设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点，B中右指针域为空的结点有 C 个。An1 Bn Cnl Dn27. 一棵完全二叉树上有1001个结点，其中叶子结点的个数是 C 。A500 B501 C490 D4958. 设森林F中有3棵树，第1、第2与第3棵树的结点个数分别为N1，N2与N3。与森林F对应的二叉树根结点的右子树上的结点个数是 D 。AN1 BN1N2 CN2 DN2N39. 任何一棵二叉树的叶结点在先序、中序与后序遍历序列中的

11、相对次序 A 。A. 不发生改变 B. 发生改变 C. 不能确定 D. 以上都不对10. 假设一棵二叉树的后序遍历序列为dabec，中序遍历序列为debac，那么先序遍历序列为 D 。A. cbed B. decab C. deabc D. cedba11. 假设一棵二叉树的先序遍历序列为abdgcefh，中序遍历的序列为dgbaechf，那么后序遍历的结果为 D 。A. gcefha B. gdbecfha C. bdgaechf D. gdbehfca12. 一棵非空二叉树的先序遍历序列与后序遍历序列正好相反，那么该二叉树一定满足 B 。A. 所有的结点均无左孩子 B. 所有的结点均无右孩

12、子C. 只有一个叶子结点 D. 是一棵满二叉树13. 设高度为h的二叉树上只有度为0与度为2的结点，那么此类二叉树中所包含的结点数至少为 B 。A. 2h B. 2h1 C. 2h1 D. h114. 一个具有567个结点的二叉树的高h为 D 。A. 9 B. 10 C. 9566之间 D. 10567之间第六章 图构造1. n条边的无向图的邻接表的存储中，边结点的个数有 A 。A. n B. 2n C. n/2 D. nn2. n条边的无向图的邻接多重表的存储中，边结点的个数有 A 。A. n B. 2n C. n/2 D. nn3. 以下哪一种图的邻接矩阵是对称矩阵？ B A. 有向图 B

13、. 无向图 C. AOV网 D. AOE网4. 最短路径的生成算法可用 C 。A. 普利姆算法 B. 克鲁斯卡尔算法 C. 迪杰斯特拉算法 D. 哈夫曼算法5. 一个无向图的邻接表如以下图所示。1从顶点v0出发进展深度优先搜索，经历的结点顺序为 B 。A. v0，v3，v2，v1 B. v0，v1，v2，v3C. v0，v2，v1，v3 D. v0，v1，v3，v22从顶点v0出发进展广度优先搜索，经历的结点顺序为 D 。A. v0，v3，v2，v1 B. v0，v1，v2，v3C. v0，v2，v1，v3 D. v0，v1，v3，v26. 设有向图n个顶点与e条边，进展拓扑排序时，总的计算时

14、间为 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. 从源点到汇点的最短路径C. 最长的回路 D. 最短的回路9. 下面关于求关键路径的说法，不正确的选项是 C 。A. 求关键路径是以拓扑排序为根底的B. 一个事件的最早开场时间同以该事件为尾的弧的活动最早开场时间一样C. 一个事件的最迟开

15、场时间为以该事件为尾的弧的活动最迟开场时间与该活动的持续时间的差D. 关键活动一定位于关键路径上10. 有10个结点的无向图至少有 B 条边才能确保其是连通图。A. 8 B. 9 C. 10 D. 11第七章 查找1. 静态查找表与动态查找表的根本区别在于 B 。A. 它们的逻辑构造不一样 B. 施加在其上的操作不一样C. 所包含的数据元素类型不一样 D. 存储实现不一样2. 在表长为n的顺序表上实施顺序查找，在查找不成功时与关键字比拟的次数为 A 。A. n B. 1 C. n+1 D. n-13. 顺序查找适用于存储构造为 C 的线性表。A. 散列存储 B. 压缩存储C. 顺序存储或链式存

16、储 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/12 B. 37/12 C. 39/12 D. 43/127. 在有序表1，3，9，12，32，41，62，75，77，

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

18、列表中，至少要进展 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个无序的元素，希望用最快

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

20、B. 快速排序与归并排序C. 直接选择排序与归并排序 D. 直接插入排序与归并排序7. 一组记录的排序码为46，79，56，38，40，84，那么利用堆排序的方法建立的初始堆为 B 。A. 79，46，56，38，40，84 B. 84，79，56，38，40，46C. 84，79，56，46，40，38 D. 84，56，79，40，46，388. 一组记录的排序码为46，79，56，38，40，84，那么利用快速排序的方法，以第一个记录为基准得到的一次划分结果为 C 。A. 38，40，46，56，79，84 B. 40，38，46，79，56，84C. 40，38，46，56，79，84

21、 D. 40，38，46，84，56，799. 用某种排序方法对线性表 25，84，21，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. 要排序的数据

22、已根本有序 D. 要排序的数据个数为奇数第一章 绪论1. 数据的逻辑构造是指数据的各个数据项之间的逻辑关系。2. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。3. 数据的逻辑构造说明数据元素之间的次序关系，它依赖于数据的存储构造。4. 算法优劣与描述算法的语言无关，但与所用计算机的性能有关。5. 算法必须有输出，但可以没有输入。第二章 线性表1线性表的逻辑顺序与存储顺序总是一致的。2顺序存储的线性表可以按序号随机存取。3顺序表的插入与删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。 4线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有一样的特性

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