数据结构课em题目(附答案)

第一章1算法的计算量的大小称为计算的（B）。A效率B复杂性C现实性D难度2一个算法应该是（B）。A程序B问题求解步骤的描述C要满足五个基本特性DA和C3下面说法错误的是（A）1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模N下，复杂度ON的算法在时间上总是优于复杂度O2N的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A1B1,2C1,4D34在数据结构中，从逻辑上可以将之分为D。A动态结构和静态结构B紧凑结构和非紧凑结构C内部结构和外部结构D线性结构和非线性结构5计算算法的时间复杂度是属于一种B。A事前统计的方法B事前分析估算的方法C事后统计的方法D事后分析估算的方法6可以用D定义一个完整的数据结构A数据元素B数据对象C数据关系D抽象数据类型7算法分析的目的是_C_。A找出数据结构的合理性B研究算法中的输入和输出的关系C分析算法的效率以求改进D分析算法的易懂性和文档性8设计一个“好”的算法应考虑达到的目标有_BCD_。A是可行的B是健壮的C无二义性D可读性好第二章1线性表是具有N个（C）的有限序列（N0）。A表元素B字符C数据元素D数据项E信息项2若线性表最常用的操作是存取第I个元素及其前驱和后继元素的值，为节省时间应采用的存储方式A。A单链表B双向链表C单循环链表D顺序表3某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（D）存储方式最节省运算时间。A单链表B仅有头指针的单循环链表C双链表D仅有尾指针的单循环链表4设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用A最节省时间。A带头结点的双循环链表B单循环链表C带尾指针的单循环链表D单链表5静态链表中指针表示的是CA下一元素的地址B内存储器的地址C下一元素在数组中的位置D左链或右链指向的元素的地址6下述哪一条是顺序存储结构的优点（C）A插入运算方便B可方便地用于各种逻辑结构的存储表示C存储密度大D删除运算方便7下面关于线性表的叙述中，错误的是哪一个（B）A线性表采用顺序存储，必须占用一片连续的存储单元B线性表采用顺序存储，便于进行插入和删除操作C线性表采用链接存储，不必占用一片连续的存储单元D线性表采用链接存储，便于插入和删除操作。8若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（A）存储方式最节省时间。A顺序表B双链表C带头结点的双循环链表D单循环链表9链表不具有的特点是（B）A插入、删除不需要移动元素B可随机访问任一元素C不必事先估计存储空间D所需空间与线性长度成正比101静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第I个元素的时间与I无关。2静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。3静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。以上错误的是（B）A1,2B1C1,2,3D211对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（C）。AONONBONO1CO1ONDO1O112单链表中，增加一个头结点的目的是为了C）。A使单链表至少有一个结点B标识表结点中首结点的位置C方便运算的实现D说明单链表是线性表的链式存储13对于双向循环链表,在P指针所指的结点之后插入S指针所指结点的操作应为（D）。APRIGHTSSLEFTPPRIGHTLEFTSSRIGHTPRIGHTBPRIGHTSPRIGHTLEFTSSLEFTPSRIGHTPRIGHTCSLEFTPSRIGHTPRIGHTPRIGHTSPRIGHTLEFTSDSLEFTPSRIGHTPRIGHTPRIGHTLEFTSPRIGHTS14对于一个头指针为HEAD的带头结点的单链表，判定该表为空表的条件是（B）AHEADNULLBHEADNEXTNULLCHEADNEXTHEADDHEADNULL第三章无第四章1下面关于串的的叙述中，哪一个是不正确的（B）A串是字符的有限序列B空串是由空格构成的串C模式匹配是串的一种重要运算D串既可以采用顺序存储，也可以采用链式存储2串是一种特殊的线性表，下面哪个叙述体现了这种特殊性（A）A数据元素是一个字符B可以顺序存储C数据元素可以是多个字符D可以链接存储3串的长度是指（B）A串中所含不同字母的个数B串中所含字符的个数C串中所含不同字符的个数D串中所含非空格字符的个数4设S为一个长度为N的字符串，其中的字符各不相同，则S中的互异的非平凡子串（非空且不同于S本身）的个数为（C）。A2N1BC/2N/2D/2N/2122N2NE/2N/21F其他情况2N第五章1数组是同类型值的集合。（F）2从逻辑结构上看，N维数组的每个元素均属于N个向量。（T）3数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。（F）第六章1NN0个结点的树的高度最低是多少2最高是多少N2NN0个结点的二叉树的高度最低是多少最高是多少3有关二叉树下列说法正确的是（B）A二叉树的度为2B一棵二叉树的度可以小于2C二叉树中至少有一个结点的度为2D二叉树中任何一个结点的度都为24一棵124个叶结点的完全二叉树，最多有C个结点。A247B248C249D250E2515已知一棵完全二叉树中共有626个结点，叶子结点的个数应为C。A311B312C313D314E其它6一个具有1025个结点的二叉树的高H为（C）A11B10C11至1025之间D10至1024之间7一棵树高为K的完全二叉树至少有（C）个结点A1B1C1D22KK2K28已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有_12_个叶子结点。9已知二叉树的先序序列ABDFCEHG中序序列DBFAHECG请构造该二叉树。10已知二叉树的后序序列DMFBHELGCA中序序列DBMFAHECGL请构造该二叉树。11一棵二叉树的先序、中序和后序序列如下，其中有部分未标出，试构造出该二叉树。先序序列为_CDE_GHI_K中序序列为CB_FA_JKIG后序序列为_EFDB_JIH_A12试找出满足下列条件的二叉树1）先序序列与后序序列相同2）中序序列与后序序列相同3）先序序列与中序序列相同4）中序序列与层次遍历序列相同13一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（B）。ACABDEFGBABCDEFGCDACEFBGDADCFEGB14一棵非空的二叉树的先序序列和后序序列正好相反，则该二叉树一定满足C。A其中任意一个结点均无左孩子B其中任意一个结点均无右孩子ABCDEFGHIJKLABCDEFGHIJKLAGJBCDHIKEFLMNC其中只有一个叶子结点D其中度为2的结点最多为一个15某二叉树的先序序列和后序序列正好相反，则该二叉树一定是B的二叉树A空或只有一个结点B高度等于其结点数C任一结点无左孩子D任一结点无右孩子16二叉树在线索化后，仍不能有效求解的问题是（D）。A先序线索二叉树中求先序后继B中序线索二叉树中求中序后继C中序线索二叉树中求中序前驱D后序线索二叉树中求后序后继17引入二叉线索树的目的是（A）A加快查找结点的前驱或后继的速度B为了能在二叉树中方便的进行插入与删除C为了能方便的找到双亲D使二叉树的遍历结果唯一18若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为CAX的双亲BX的右子树中最左的结点CX的左子树中最右结点DX的左子树中最右叶结点19一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是B。A0B1C2D不确定20将树转换成二叉树树转换成的二叉树其右子树一定为空21森林转为二叉树22已知一个森林的先序序列和后序序列如下，请构造出该森林。先序序列ABCDEFGHIJKLMNO后序序列CDEBFHIJGAMLONK解森林的前序序列和后序序列对应其转换的二叉树的前序序列和中序序列，应先据此构造二叉树，再构造出森林23设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（ABGCEHFJKILMNDV2V4V1V5V3V6V7V8D。AM1BM1M2CM3DM2M324设F是一个森林，B是由F变换得的二叉树。若F中有N个非终端结点，则B中右指针域为空的结点有（C）个。AN1BNCN1DN225设X是树T中的一个非根结点，B是T所对应的二叉树。在B中，X是其双亲的右孩子，下列结论正确的是D。A在树T中，X是其双亲的第一个孩子B在树T中，X一定无右边兄弟C在树T中，X一定是叶子结点D在树T中，X一定有左边兄弟26设树形T在后根次序下的结点排列和各结点相应的次数如后根次序次数请画出的树形结构图。27给定权值7，6，3，32，5，26，12，9，构造相应的哈夫曼树，并计算其带权路径长度。为使结果答案唯一，请用左结点的值小于等于右结点的值来构造哈夫曼树。第七章1图中有关路径的定义是（A）。A由顶点和相邻顶点序偶构成的边所形成的序列B由不同顶点所形成的序列C由不同边所形成的序列D上述定义都不是2设无向图的顶点个数为N，则该图最多有（B）条边。AN1BNN1/2CNN1/2D0E2N3一个有N个结点的图，最少有（B）个连通分量，最多有（D）个连通分量。A0B1CN1DN4要连通具有N个顶点的有向图，至少需要（B）条边。ANLBNCNLD2N5G是一个非连通无向图，共有28条边，则该图至少有_9_个顶点。6用邻接表存储图所用的空间大小A。A与图的顶点数和边数都有关B只与图的边数有关C只与图的顶点数有关D与边数的平方有关7图G是N个顶点的无向完全图，则下列说法正确的有BCDAG的邻接多重表需要NN1个边结点和N个顶点结点；BG的连通分量个数最少；CG为连通图；DG所有顶点的度的总和为NN18在有向图的邻接表存储结构中，顶点V在链表中出现的次数是B。A顶点V的度B顶点V的出度C顶点V的入度D依附于顶点V的边数8图的遍历举例1假定以邻接表存储，邻接点按编号升序排列。遍历序列如下深度优先搜索V1143V2V3V4V5V6245352012345V2V4V1V5V3V6V2V4V1V5V3V616211114336191865V1V2V4V8V5V6V3V7广度优先搜索V1V2V3V4V5V6V7V82已知邻接矩阵求遍历序列深度优先搜索V1V2V3V4V5宽度优先搜索V1V2V3V4V53已知邻接表求遍历序列深度优先遍历V1V2V3V6V5V4宽度优先遍历V1V2V5V4V3V69深度优先广度优先生成树V1V2V3V4V5V613520410544023512410最小生成树100101235461425483234567123546142548323456711试画出从顶点V1开始利用PRIM算法得到的最小生成树12利用KRUSKAL算法求最小生成树4209581102V2V3V1V4V58112102549ABEDCFBCADEV1V2V5V6V0V3V414321010050206030510V2V4V1V5V3V6V2V4V1V5V3V613用DAG图描述表达式ABBCDCDECDE14AOV网的拓扑排序15写出有向图的所有拓扑排序，并指出应用教材中的算法求得的是哪个序列，设邻接表的边表结点中的邻接点序号是递增的。16求最短路径17求最短路径FLOYD算法18设图如右所示，在下面的5个序列中，符合深度优先遍历的序列有多少（D）AEBDFCACFDEBAEDFCBAEFDCBAEFDBCA5个B4个C3个D2个19下面哪一方法可以判断出一个有向图是否有环（回路）（AB）A深度优先遍历B拓扑排序C求最短路径D求关键路径20在有向图G的拓扑序列中，若顶点VI在顶点VJ之前，则下列情形不可能出现的是（D）。AG中有弧BG中有一条从VI到VJ的路径CG中没有弧DG中有一条从VJ到VI的路径21关键路径是AOE网中BA从始点到终点的最短路径B从始点到终点的最长路径C从始点到终点的边数最多的路径D从始点到终点的边数最少的路径22下列关于AOE网的叙述中，不正确的是（B）。A关键活动不按期完成就会影响整个工程的完成时间B任何一个关键活动提前完成，那么整个工程将会提前完成C所有的关键活动提前完成，那么整个工程将会提前完成D某些关键活动若提前完成，那么整个工程将会提前完成23下列有关图的说法错误的是（C）A在有向图中，出度为0的结点4称为叶子。B用邻接矩阵表示图，容易判断任意两个结点之间是否有边相连，并求得各结点的度。C按深度方向遍历图和先根次序遍历树类似，得到的结果是唯一的。D若有向图G中从结点VI到结点VJ有一条路径，则在图G的结点的线性序列中结点VI必在结点VJ之前的话，则称为一个拓扑序列。第八章1地址为大小为的存储块的伙伴地址是什么BUDDY1664,71664153610641028722地址为大小为的存储块的伙伴地址是什么BUDDY2816,62816288028663已知一个大小为512个字长的存储，假设先后有6个用户申请大小分别为23，45，52，100，11和19的存储空间，然后再顺序释放大小为45，52，11的占用块。假设以伙伴系统实现动态存储管理。（1）画出可利用空间表的初始状态。（2）画出为6个用户分配所需要的存储空间后可利用空间表的状态以及每个用户所得到的存储块的起始地址。（3）画出在回收3个占用块之后可利用空间表的状态。第九章1画出含有12个元素的有序表的判定树（1）求查找成功时的平均查找长度（2）求查找失败时的平均查找长度2若查找每个记录的概率均等，则在具有N个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为C。AN1/2BN/2CN1/2DN3对线性表进行二分查找（就是折半查找）时，要求线性表必须（）A以顺序方式存储B以顺序方式存储,且数据元素有序C以链接方式存储D以链接方式存储,且数据元素有序4当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度CA必定快B不一定C在大部分情况下要快D取决于表递增还是递减5在有序表A120中，按二分查找方法进行查找，查找长度为4的元素的下标从小到大依次是_1，3，6，8，11，13，16，19_6分块检索中，若索引表和各块内均用顺序查找，则有900个元素的线性表分成_30_块最好若分成25块，其平均查找长度为_315（块内顺序查找）_。7设关键码序列为63，90，70，55，67，42，98，83，则构造一棵二叉排序树的过程如下8二叉排序树上删除10或40或45或559构造二叉排序树将FOR,CASE,WHILE,SWITCH,BREAK,DO,DEFINE,CONST,IF,INT中的关键字依次插入初态为空的二叉排序树（按字母在字母表中的序号排序）中，请画出所得到的树T。然后画出删除FOR之后的二叉排序树T。10按关键字序列15,21,27,43,36,8,11构造平衡二叉树11构造平衡二叉树给定表25，18，48，07，76，52，81，70，92，15，按表中元素顺序构造一棵AVL树，并求其在等概率情况下查找成功的平均查找长度。12已知长度为11的表（XAL,WAN,WIL,ZOL,YO,XUL,YUM,WEN,WIM,ZI,YON）按表中元素顺序依次插入一棵初始为空的1二叉排序树2平衡二叉排序树；3最佳二叉排序树分别求其在等概率的情况下查找成功的平均查找长度。13二叉查找树的查找效率与二叉树的（1）C有关,在（2）C时其查找效率最低1A高度B结点的多少C树型D结点的位置2A结点太多B完全二叉树C呈单枝树D结点太复杂。14分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是CA100,80,90,60,120,110,130B100,120,110,130,80,60,90C100,60,80,90,120,110,130D100,80,60,90,120,130,11015在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1,则应作C型调整以使其平衡。ALLBLRCRLDRR16设二叉排序树中关键字由1到1000的整数组成，现要查找关键字为363的结点，下述关键字序列哪一个不可能是在二叉排序树中查到的序列说明原因。（1）51,250,501,390,320,340,382,363（2）24,877,125,342,501,623,421,363答序列（2）不可能是二叉排序树中查到363的序列。查到501后，因363归并分类快速分类D堆分类快速分类归并分类11设要将序列Q,H,C,Y,P,A,M,S,R,D,F,X中的关键码按字母升序重新排序，1B是初始步长为4的SHELL排序一趟扫描的结果；2C是对排序初始建堆的结果；3A是以第一个元素为分界元素的快速一趟扫描的结果从下面供选择的答案中选出正确答案填入括号内。AF,H,C,D,P,A,M,Q