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

.第一章  绪论1. 从逻辑上可以把数据结构分为（  C  ）两大类。A动态结构、静态结构      B顺序结构、链式结构C线性结构、非线性结构    D初等结构、构造型结构2. 在下面的程序段中，对x的赋值语句的频度为（  C  ）。For（k=1；k<=n；k+）           For（j=1；j<=n；j+） 2="" x="x1；" 3.="" a="" 4.="" d="" 5.="" b="" 1.="" n="" c="" p-="">next=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所指的结点时须修改指针（ &nbsp;A  ）。A（p-> prior)-> next = p->next ; （p->next）->prior =p-> prior ;Bp-> prior=（p-> 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 = 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  ）。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 *（bc）d的后缀表达式是（  B  ）。Aabcd*      Babc*dCabc*d      D*abcd5采用顺序存储的两个栈的共享空间S1.m，用topi代表第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头、尾指针都要修改    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按行优先方式存储，元素M85的起始地址与当M按列优先方式存储时的（3）（  C  ）元素的起始地址一致。（1）A. 90    B. 180    C. 240    D. 540（2）A. 108    B. 114    C. 54    D. 60（3）A. M85    B. M310    C. M58    D. M095. 数组A中，每个元素的存储占3个单元，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元个数是（1）（  C  ）；若该数组按行存放，元素A85的起始地址为（2）（  D  ）；若该数组按列存放，元素A85的起始地址为（3）（  B  ）。（1）A. 80    B. 100    C.240    D. 270（2）A. SA+141    B. SA+144    C. SA+222    D. SA+225（3）A. 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. 以二叉链表作为二叉树的存储结构，在具有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   &nbsp;B4    C5    D15. 某二叉树T有n个结点，设按某种顺序对T中的每个结点进行编号，编号值为1，2，n，且有如下性质：T中任意结点v，其编号等于左子树上的最小编号减1，而v的右子树的结点中，其最小编号等于v左子树上结点的最大编号加1，这是按（  B  ）编号的。A. 中序遍历序列     B. 先序遍历序列     C. 后序遍历序列     D. 层次顺序6. 设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点，B中右指针域为空的结点有（ &nbsp;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. 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（  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. 所有的结点均无右孩子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 &nbsp;  B. 2n    C. n/2    D. nn2. n条边的无向图的邻接多重表的存储中，边结点的个数有（  A  ）。A. n    B. 2n    C. n/2    D. nn3. 下列哪一种图的邻接矩阵是对称矩阵？（  B  ）A. 有向图    B. 无向图    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，v2（2）从顶点v0出发进行广度优先搜索，经历的结点顺序为（  D  ）。A. v0，v3，v2，v1    B. v0，v1，v2，v3C. v0，v2，v1，v3    D. 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. 从源点到汇点的最短路径C. 最长的回路                D. 最短的回路9. 下面关于求关键路径的说法，不正确的是（  C  ）。A. 求关键路径是以拓扑排序为基础的B. 一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同C. 一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差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. 顺序存储或链式存储    D. 索引存储4. 用顺序查找法对具有n个结点的线性表查找一个结点的时间复杂度为（  C  ）。AO(log2n2)    B. O(nlog2n)   &nbsp;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，82，95，100上进行折半查找关键字为82的数据元素需要比较（  C  ）次。A. 1    B. 2    C. 4    D. 58. 设散列表长为14，散列函数为H（key）= 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个关键字存入散列表中，至少要进行（  D  ）次探测。A. k1次    B. k次    C. k1次    D. k（k1）/2次11. 在散列函数H（k）= k % m中，一般来讲，m应取（  C  ）。A. 奇数    B. 偶数    C. 素数    D. 充分大的数12. 在采用线性探测法处理冲突所构成的散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测到的这些位置上的键值（  B  ）。A. 一定是同义词      B. 一定不是同义词C. 都相同            D. 不一定都是同义词第八章  排序1. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是（  A  ）。A. 插入排序    B. 选择排序    C. 快速排序    D. 归并排序2. 设有1000个无序的元素，希望用最快的速度挑选出其中前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. 直接插入排序和快速排序    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    D. 40，38，46，84，56，799. 用某种排序方法对线性表（ 25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变化情况如下：（1）25，84，21，47，15，27，68，35，20（2）20，15，21，25，47，27，68，35，84（3）15，20，21，25，35，27，47，68，84（4）15，20，21，25，27，35，47，68，84则所采用的排序方法是（  D  ）。A. 选择排序    B. 希尔排序    C. 归并排序    D. 快速排序10. 快速排序方法在（  C  ）情况下最不利于发挥其长处。A. 要排序的数据量太大        B. 要排序的数据中含有多个相同值C. 要排序的数据已基本有序    D. 要排序的数据个数为奇数第一章  绪论1. 数据的逻辑结构是指数据的各个数据项之间的逻辑关系。2. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。3. 数据的逻辑结构说明数据元素之间的次序关系，它依赖于数据的存储结构。4. 算法优劣与描述算法的语言无关，但与所用计算机的性能有关。5. 算法必须有输出，但可以没有输入。第二章  线性表1线性表的逻辑顺序与存储顺序总是一致的。2顺序存储的线性表可以按序号随机存取。3顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。 4线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。5在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。6在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。7线性表的链式存储结构优于顺序存储结构。8在线性表的顺序存储结构中，插入和删除时移动元素的个数与该元素的位置有关。9线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。10在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。11静态链表既有顺序存储的优点，又有动态链表的优点。所以它存取表中第i个元素的时间与i无关。12线性表的特点是每个元素都有一个前驱和一个后继。第三章  栈和队列第四章  字符串及线性结构的扩展第五章  树结构1. 二叉树是树的特殊形式。2. 由树转换成二叉树，其根结点的右子树总是空的。20. 满二叉树一定是完全二叉树，反之未必。第六章  图结构第七章  查找第八章  排序可编辑范本