数据结构课程习题汇编

选择题1、若入栈序列的元素顺序为A、B、C、D、E，判断下列哪一个出栈序列是不可能的。（）AA、B、C、D、EBB、C、D、E、ACE、A、B、C、DDD、C、B、A、E2、某程序的时间复杂度为（3NNLOG2NN28）,其数量级表示为（）。AO（N）BO（NLOG2N）CO（N2）DO（LOG2N）3、一个循环队列的队首和队尾指针分别是FRONT和REAR,则判别队空的条件是（）AFRONT1REARBFRONTREAR1CFRONT0DFRONTREAR4、一个非空广义表的表头（）A不可能是子表B只能是子表C只能是原子D可以是子表或原子5、一个有顺序表有255个对象，采用顺序搜索法查表，平均搜索长度为（）A128B127C126D2556、设有一个含200个表项的散列表，用线性探查法解决冲突，按关键码查询时找到一个表项的平均探查次数不超过15，则散列存储空间应能够至少容纳（）个表项。（搜索成功的平均搜索长度为SNL11/1A/2,其中A为装填因子A400B526C624D6767、在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为。A4B5C6D78以下哪个数据结构不是多型数据类型（）A栈B广义表C有向图D字符串9以下数据结构中，（）是非线性数据结构A树B字符串C队D栈10下列数据中，（）是非线性数据结构。A栈B队列C完全二叉树D堆11连续存储设计时，存储单元的地址（）。A一定连续B一定不连续C不一定连续D部分连续，部分不连续12对稀疏矩阵进行压缩存储目的是（）。A便于进行矩阵运算B便于输入和输出C节省存储空间D降低运算的时间复杂度13以下属于逻辑结构的是（）。A顺序表B哈希表C有序表D单链表14从一棵B_树删除元素的过程中，若最终引起树根结点的合并，则新树高度是（）。A原树高度加1B原树高度减1C原树高度D不确定15在一个具有N个顶点的无向图中，要连通所有顶点则至少需要（）条边。ANB2NCN1DN116在某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用存储方式最节省运算时间。A单链表B、仅有头指针的单循环链表C、双链表D、仅有尾指针的单循环链表17下列4种排序方法中，不稳定的方法是（）。A直接插入排序B冒泡排序C归并排序D直接选择排序18串是一种特殊的线性表，其特殊性体现在（）A可以顺序存储B数据元素是一个字符C可以链接存储D数据元素可以是多个字符19在一个图中，所有顶点的度数之和等于所有边数的（）倍。A1/2B1C2D420有一个有序表为1，3，9，12，32，41，45，62，75，77，82，95，100，当二分查找值为82的结点时，（）次比较后查找成功。A1B2C4D821一棵左右子树不空的二叉树在先序线索化后，其空指针域数为（）。A0B1C2D不确定22在下列排序算法中，在待排序的数据表已经为有序时，花费时间反而最多的是（）。A快速排序B希尔排序C冒泡排序D堆排序23向顺序栈中压入新元素时，应当（）。A先移动栈顶指针，再存入元素B先存入元素，再移动栈顶指针C先后次序无关紧要D同时进行24在线索二叉树中，下面说法不正确的是A在中序线索树中，若某结点有右孩子，则其后继结点是它的右子树的左支末端结点。B线索二叉树是利用二叉树的N1个空指针来存放结点前驱和后继信息的。C每个结点通过线索都可以直接找到它的前驱和后继D在中序线索树中，若某结点有左孩子，则其前驱结点是它的左子树的右支末端结点。25广义表AA,B,C,D,E,F,G,则下面式子的值为（）。HEADTAILHEADTAILTAILAAGBDCCDD26有三个数字1,2,3,将它们构成二叉树，中序遍历序列为1,2,3的不同二叉树有种。A5B6C7D827一个算法应该是（）。A程序B问题求解步骤的描述C要满足五个基本特性DA和C28下面关于算法说法错误的是（）A算法最终必须由计算机程序实现B为解决某问题的算法同为该问题编写的程序含义是相同的C算法的可行性是指指令不能有二义性D以上几个都是错误的29下面说法错误的是（）1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模N下，复杂度ON的算法在时间上总是优于复杂度O2N的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A1B1,2C1,4D330从逻辑上可以把数据结构分为（）两大类。A动态结构、静态结构B顺序结构、链式结构C线性结构、非线性结构D初等结构、构造型结构31以下与数据的存储结构无关的术语是（）。A循环队列B链表C哈希表D栈32以下数据结构中，哪一个是线性结构（）A广义表B二叉树C稀疏矩阵D串33以下那一个术语与数据的存储结构无关（）A栈B哈希表C线索树D双向链表34一棵左右子树不空的二叉树在先序线索化后，其空指针域数为（）。A0B1C2D不确定35在一棵二叉树中，第4层上的结点数最多为（）。A31B8C15D1636向堆中插入一个元素的时间复杂度为（）。AOLOG2NBONCO1DONLOG2N37广义表L（A，（B，C），进行TAIL（L）操作后的结果为（）。ACBB，CC（B，C）D（B，C）38一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）A250B、500C254D、50139计算机算法必具备输入、输出和等五个特性A可行性、可移植性和可扩充性B可行性、确定性和有穷性C确定性、有穷性和稳定性D易读性、稳定性和安全性40下面的叙述不正确的是（）A线性表在链式存储时，查找第I个元素的时间同I的值成正比B线性表在链式存储时，查找第I个元素的时间同I的值无关C线性表在顺序存储时，查找第I个元素的时间同I的值成正比D线性表在顺序存储时，查找第I个元素的时间同I的值无关41在长度为N的顺序表的第I1IN1个位置上插入一个元素，元素的移动次数为ANI1BNICIDI142对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为A顺序表B用头指针表示的单循环链表C用尾指针表示的单循环链表D单链表43若一个具有N个顶点，K条边的无向图是一个森林NK，则该森林中必有棵树。AKBNCNKD144若已知一个栈的入栈序列是1，2，3，N，其输出序列为P1,P2,P3,PN,若P1是N，则PI是AIBNICNI1D不确定45表达式ABCD的后缀表达式是AABCDBABCDCABCDDABCD46在倒排文件中，通常包含有倒排表。A一个B多个C两个D一个或两个47二维数组MI,J的元素占三个字节，行下标I的范围从0到4，列下标J的范围从0到5，M按行存储时元素M3，5的起始地址与M按列存储时元素的起始地址相同。A、M2,4B、M3,4C、M3,5D、M4,448在一个单链表HL中，若要在指针Q所指结点的后面插入一个由指针P所指向的结点，则执行（）。AQNEXTPNEXTPNEXTQBPNEXTQNEXTQPCQNEXTPNEXTPNEXTQDPNEXTQNEXTQNEXTP49非空的循环链表HEAD的尾结点P满足（）APNEXTNULLBPNULLCPNEXTHEADDPHEAD50若要尽可能快地完成对实数数组的排序，且要求排序是稳定的，则应选（）A快速排序B堆排序C归并排序D基数排序。51二叉树在线索化后，仍不能有效求解的问题是（）。A先序线索二叉树中求先序后继B中序线索二叉树中求中序后继C中序线索二叉树中求中序前驱D后序线索二叉树中求后序后继52在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡点为A，并已知A的左孩子的平衡因子为1，右孩子的平衡因子为0，则做（）型调整以使其平衡。ALLBLRCRLDRR53对有18个元素的有序表做折半查找，则查找A3的比较序列的下标依次（）。A123B9523C953D942354计算机算法指的是（）A计算方法B排序方法C解决问题的有限运算序列D调度方法55设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（）。AM1BM1M2CM3DM2M356以下叙述正确的是（）A线性表的线性存储结构优于链表存储结构B二维数组是其数据元素为线性表的线性表C栈的操作方式是先进先出D队列的操作方式是先进后出57一个顺序存储的线性表的第一个元素的存储地址是100，每个元素的长度是2，则第5个元素的地址是（）A100B108C110D12058判定一个栈ST（最多元素为M）为空的条件是（）ASTTOP0BSTTOP0CSTTOPMDSTTOPM59静态链表中指针表示的是（）A内存地址B数组下标C下一元素地址D左、右孩子地址60已知某二叉树的后序遍历序列是DABEC，中序遍历序列是DEBAC，它的前序遍历序列是（）AACBEDBDECABCDEABCDCEDBA61有N个叶子的哈夫曼树的结点总数为（）。A不确定B2NC2N1D2N162在一非空二叉树的中序遍历序列中，根结点的右边（）A只有右子树上的所有结点B只有右子树上的部分结点C只有左子树上的部分结点D只有左子树上的所有结点63对于一个具有N个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（）ANB（N1）2CN1DN264下面的叙述中，不正确的是A关键活动不按期完成就会影响整个工程的完成时间B任何一个关键活动提前完成，将使整个工程提前完成C所有关键活动若提前完成，则整个工程将提前完成D某些关键活动若提前完成，将使整个工程提前完成65二叉树上叶结点数等于（）。A分支结点数加1B单分支结点数加1C双分支结点数加1D双分支结点数减166若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用遍历方法最合适。A前序B中序C后序D按层次67每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做（）排序A插入B交换C选择D归并68设循环队列中数组的下标范围是1N，其头尾指针分别为F和R，则其元素个数为（）。ARFBRF1CRFMODN1DRFNMODN69二叉树在线索化后，仍不能有效求解的问题是（）。A先序线索二叉树中求先序后继B中序线索二叉树中求中序后继C中序线索二叉树中求中序前驱D后序线索二叉树中求后序后继70下面说法正确的为（）（1）二叉树按某种方式线索化后，任一结点均有指向前驱和后继的线索（2）二叉树的前序遍列序列中，任意一个结点均处在子孙结点前（3）二叉排序树中任一结点的值大于其左孩子的值，小于右孩子的值A（1）（2）（3）B（1）（2）C（1）（3）D前面的可选答案都不对71下面的说法中正确的是（）1任何一棵二叉树的叶结点在三种遍历中的相对次序不变2按二叉树定义,具有三个结点的二叉树共有6种A1,2B1C2D1,2都错72一棵二叉树高度为H,所有结点的度或为0,或为2,则这棵二叉树最少有（）个结点A2HB2H1C2H1DH173下列排序算法中，在待排序数据已有序时，花费时间反而最多的是（）排序A冒泡B希尔C快速D堆74与链表不相适宜的叙述是（）A、动态存储分配B、可表示任何类型的数据结构C、插入和删除操作灵活D、查找速度快75设I为N个结点的二叉树结点编号，I1,2,N；若INEXTPNEXTPNEXTQB、PNEXTQNEXTQPC、QNEXTPNEXTPNEXTQD、PNEXTQNEXTQNEXTP79SSOFTWARE，其子串的数目是（）A、8B、37C、36D、980下面的说法中正确的是（）（1）任何一棵二叉树的叶子结点在三种遍历中的相对次序不变；（2）按二叉树定义，具有三个结点的二叉树共有6种。A12B1C2D1、2都错81二维数组MI,J的元素占三个字节，行下标I的范围从0到4，列下标J的范围从0到5，M按行存储时元素M3，5的起始地址与M按列存储时元素的起始地址相同。A、M2,4B、M3,4C、M3,5D、M4,482下列几种排序方法中，平均查找长度最小的是A、插入排序B、选择排序C、快速排序D、归并排序83采用顺序查找方法查找长度为N的线性表时，每个元素的平均查找长度为（）A、NB、N/2C、（N1）/2D、（N1）/284下述几种排序方法中，要求内存量最大的是（）A、插入排序B、选择排序C、快速排序D、归并排序85数据结构是一门研究非数值计算的程序设计问题中计算机的（），以及它们之间的（）和运算等的学科。A、操作对象关系B、计算方法结构C、逻辑存储运算D、数据映象算法86下述哪一条是顺序存储结构的优点（）A存储密度大B插入运算方便C删除运算方便D可方便地用于各种逻辑结构的存储表示87计算机算法必须具备输入、输出、（）等五个特性。A、可行性、可移植性和可扩充性B、可行性、确定性和有穷性C、确定性、有穷性和稳定性D、易读性、稳定性和安全性88栈和队列的共同点是（）A、都是先进后出B、都是先进先出C、只允许在端点处插入和删除元素D、没有共同点89在一个单链表中，若删除P所指结点的后续结点，则执行（）A、PNEXTPNEXTNEXTB、PPNEXTPNEXTPNEXTNEXTC、PNEXTPNEXTD、PPNEXTNEXT90深度为5的二叉树至多有（）个结点A、16B、32C、31D、1091设循环队列中数组的下标范围是1N，其头尾指针分别为F和R，则其元素个数为（）。A、RFB、RF1C、RFMODN1D、RFNMODN92递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构。A队列B多维数组C栈D线性表93对一棵二叉排序树进行（）遍历得到的结点序列是一个有序序列。A、前序B、中序C、后序D、层序94任何一个无向连通图的最小生成树（）。A、有一棵或多棵B、只有一棵C、一定有多棵D、可能不存在95数组A15,16的每个元素占5个单元，将其按行优先顺序存储在起始地址为1000的连续的内存单元中，则元素A5,5的地址为（）。A1140B1145C1120D112596下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是（）。A堆排序B冒泡排序C快速排序D直接插入排序97设栈S和队列Q的初始状态为空，元素E1，E2，E3，E4,E5和E6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是E2，E4，E3,E6,E5,E1则栈S的容量至少应该是。A6B4C3D2100一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（）A所有的结点均无左孩子B所有的结点均无右孩子C只有一个叶子结点D是任意一棵二叉树101在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（）A都不相同B完全相同C先序和中序相同，而与后序不同D中序和后序相同，而与先序不同102某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。A空或只有一个结点B任一结点无左子树C高度等于其结点数D任一结点无右子树103若线性表最常用的操作是存取第I个元素及其前驱的值，则采用（）存储方式节省时间。A单向链表B双向链表C单循环链表D顺序表104对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一双亲的左、右孩子中，左孩子的编号小于右孩子的编号，则可采用（）顺序实现编号。A前序遍历B中序遍历C后序遍历D层序遍历105设连通图G的顶点数N，则G的生成树的边数为（）。ANBN1C2ND，2N1106若长度为N的线性表采用顺序存储结构，删除一元素需要移动元素的平均个数为（）AN1/2BNCN1DN/2107设A是NN的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B1NN1/2中，对上述任一元素AIJ1I，JN，且IJ在B中的位置为。AIIL/2JBJJL/2ICJJL/2I1DIIL/2J1108设栈的输入序列为（1，2，3，4），则不可能的出栈序列为（）A1234B2134C1432D4312109从一棵深度为H的二叉排序树中查找一个元素时，其时间复杂度为。AOHBOH2COLOG2HDONLOG2H110一个循环队列的队首和队尾指针分别是FRONT和REAR,则判别队空的条件是（）AFRONT1REARBFRONTREAR1CFRONT0DFRONTREAR111由两个栈共享一个向量空间的好处是（）A、减少存取时间，降低下溢发生的机率B、节省存取空间，降低上溢发生的机率C、减少存取时间，降低上溢发生的机率D、节省存取空间，降低下溢发生的机率112如下陈述中正确的是（）A、串是一种特殊的线性表B、串的长度必须大于零C、串中元素只能是字母D、空串就是空白串113引入二叉线索树的目的是（）A加快查找结点的前驱或后继的速度B为了能在二叉树中方便的进行插入与删除C为了能方便的找到双亲D使二叉树的遍历结果唯一114线索二叉树是一种（）结构。A逻辑B逻辑和存储C物理D线性115N个结点的线索二叉树上含有的线索数为（）A2NBNLCNLDN116二叉树在线索后，仍不能有效求解的问题是（）。A前（先）序线索二叉树中求前（先）序后继B中序线索二叉树中求中序后继C中序线索二叉树中求中序前驱D后序线索二叉树中求后序后继117设F是一个森林，B是由F变换得的二叉树。若F中有N个非终端结点，则B中右指针域为空的结点有（）个。AN1BNCN1DN2118如果T2是由有序树T转换而来的二叉树，那么T中结点的后序就是T2中结点的（）。A先序B中序C后序D层次序119、无向图G（V，E），其中VA,B,C,D,E,F,EA,B,A,E,A,C,B,E,C,F,F,D,E,D对该图进行深度优先遍历，得到的顶点序列正确的是（）AA,B,E,C,D,FBA,C,F,E,B,DCA,E,B,C,F,DDA,E,D,F,C,B120对序列15，9，7，8，20，1，4进行排序，进行一趟后数据的排列变为4，9，1，8，20，7，15；则采用的是（）排序。A选择B快速C希尔D冒泡121设哈希表长为14，哈希函数是HKEYKEY11,表中已有数据的关键字为15,38,61,84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是（）A8B3C5D9122用数组R存储静态链表,结点的NEXT域指向后继,工作指针J指向链中结点,使J沿链移动的操作为（）AJRJNEXTBJJ1CJJNEXTDJRJNEXT123判定一个有图是否存在回路，除了可以利用拓扑排序的方法外，还可以利用。A求关键路径的方法B求最短路径的DIJKSTRA方法C深度优先遍历算法D广度优先遍历算法124为查找某一特定单词在文本中出现的位置，可应用的串运算是A插入B删除C串联接D子串定位125设单循环链表中结点的结构为（DATA，NEXT），且REAR是指向非空的带头结点的单循环链表的尾结点的指针。若要删除链表的第一个结点，则应执行下列哪一个操作ASREARREARREARNEXTFREESBREARREARNEXTFREESCREARREARNEXTNEXTFREESDSREARNEXTNEXTREARNEXTNEXTSNEXTFREES126下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是（）。A直接插入排序B快速排序C直接选择排序D堆排序127在一棵二叉树上，第4层上的结点数最多为A31B8C15D16128快速排序方法在情况下，最不利于发挥其长处A要排序的数据量太大B要排序的数据含有多个相同值C要排序的数据已基本有序D要排序的数据个数为奇数129对于无向图的生成树，下列说法不正确的是A生成树是遍历的产物B从同一顶点出发所得的生成树相同C生成树是图的极小连通子图D不同遍历方法所得到的生成树不同130算法分析的目的是A找出数据结构的合理性B研究算法中的输入和输出的关系C分析算法的效率以求改进D分析算法的易懂性和文档性131下列陈述中正确的是A二叉树是度为2的有序树B二叉树中结点只有一个孩子时无左右之分C二叉树中必有度为2的结点D二叉树中最多只有两棵子树，并且有左右之分132判断有向图是否有回路，除了可以用深度优先遍历算法外，还可以用A求关键路径的方法B广度优先遍历算法C求最短路径的方法D拓扑排序133有一个有序表为5,8,10,15,32,41,45,62,75,77,82,95,100,当二分查找值为82的数据时次比较成功。A1B4C2D8134下列关于AOE网的叙述中，不正确的是（）。A关键活动不按期完成就会影响整个工程的完成时间B任何一个关键活动提前完成，那么整个工程将会提前完成C所有的关键活动提前完成，那么整个工程将会提前完成D某些关键活动提前完成，那么整个工程将会提前完成135采用顺序查找方法查找长度为N的线性表，平均查找长度为。ANBN/2CN1/2DN1/2136下列哪一种图的邻接矩阵是对称矩阵（）A有向图B无向图CAOV网DAOE网137对线性表采用折半查找法，该线性表必须。A采用顺序存储结构B采用链式存储结构C采用顺序存储结构，且元素按值有序D采用链式存储结构，且元素按值有序138已知二叉树的前序序列为ABDCEFG，中序序列为DBCAFEG，则后序序列为。ADCBAFGEBDCBFGEACDCBFEGADDCBGFEA139当利用大小为N的数组顺序存储一个栈时，假定用TOPN表示栈空，则退栈时，用（）语句修改TOP指针。ATOPBTOP0CTOPDTOPN140数据序列（2，1，4，9，8，10，6，20）只能是下列排序算法中的的两趟排序后的结果。A快速排序B冒泡排序C选择排序D插入排序141从一棵B_树删除元素的过程中，若最终引起树根结点的合并，则新树高度是（）。A原树高度加1B原树高度减1C原树高度D不确定142在倒排文件中，通常包含有倒排表。A一个B多个C两个D一个或两个143若用冒泡排序方法对序列10,14,26,29,41,52从大到小排序，需进行（）次比较。A3B10C15D25144循环队列A0M1存放其元素值，用FRONT和REAR分别表示队头及队尾，则当前队列中的元素数是AREARFRONTMMBREARFRONT1CREARFRONT1DREARFRONT145下列说法不正确的是（）。A图的遍历是从给定的源点出发每一个顶点仅被访问一次B图的深度遍历不适用于有向图C遍历的基本算法有两种深度遍历和广度遍历D图的深度遍历是一个递归过程146一个队列的入队序列是1、2、3、4，则队列的输出序列是（）A4、3、2、1B1、2、3、4C1、4、3、2D3、2、4、1147在一个单链表中，已知Q所指结点是P所指结点的前驱结点，若在Q和P之间插入S结点，则执行（）ASNEXTPNEXTPNEXTSBPNEXTSNEXTSNEXTPCQNEXTSSNEXTPDPNEXTSSNEXTQ148下列排序算法中不能保证每趟排序至少能将一个元素放到其最终的位置上。A快速排序BSHELL排序C堆排序D冒泡排序149具有N个顶点的有向图最多有（）条边。ANBNN1CNN1DNN150在数据结构中，逻辑上数据结构可分为（）。A动态结构和静态结构B线性结构和非线性结构C紧凑结构和非紧凑结构D内部结构和外部结构151在下面的排序方法中，辅助空间为O（N）的是。A希尔排序B堆排序C选择排序D归并排序152不便于插入和删除操作的是（）。A单链表B双链表C顺序表D循环链表153在有向图G的拓扑序列中，若顶点VI在顶点VJ之前，则下列情形不可能出现的是（）。AG中有弧BG中有一条从VI到VJ的路径CG中没有弧DG中有一条从VJ到VI的路径154下面关于求关键路径的说法不正确的是（）。A求关键路径是以拓扑排序为基础的B一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同C一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差D关键活动一定位于关键路径上155树最适合用来表示（）A有序数据元素B无序数据元素C元素之间具有分支层次关系的数据D元素之间无联系的数据156具有4个顶点的无向完全图至多有（）条边。A6B12C16D20157具有6个顶点的无向图至少应有（）条边才能确保是一个连通图。A5B6C7D8158假定有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少要进行多少次探测AK1次BK次CK1次DK（K1）/2次159设哈希表长为14，哈希函数是HKEYKEY11,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是A8B3C5D9160设有一组记录的关键字为19，14，23，1，68，20，84，27，55，11，10，79，用链地址法构造散列表，散列函数为H（KEY）KEYMOD13,散列地址为1的链中有（）个记录。A1B2C3D4填空题二、填空题1栈的特点是，队列的特点是。2设二维数组A2030,3020,每个元素占有4个存储单元,存储起始地址为200如按行优先顺序存储,则元素A25,18的存储地址为；如按列优先顺序存储,则元素A18,25的存储地址为。3一个图的表示法是唯一的，而表示法是不唯一的。4二叉树由，三个基本单元组成。5树在计算机内的表示方式有，。6在二叉树中，指针P所指结点为叶子结点的条件是。7中缀式AB34（CD）对应的前缀式为，若A1，B2，C3，D4，则后缀式DB/CCAB的运算结果为。8二叉树中某一结点左子树的深度减去右子树的深度称为该结点的。9具有256个结点的完全二叉树的深度为。10已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有个叶子结点。11在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为。12深度为H的完全二叉树至少有个结点；至多有个结点；H和结点总数N之间的关系是。13高度为4的3阶B树中，最多有个关键字。14在完全二叉树中，编号为I和J的两个结点处于同一层的条件是。15具有N个结点的满二叉树，其叶子结点的个数为16已知广义表A9,7,8,10,99,12，试用求表头和表尾的操作HEAD和TAIL将原子元素99从A中取出来。17已知广义表L（X,Y,Z）,A,U,T,W）,则HEADTAILTAILL。18设有二维数组A09,019,其每个元素占两个字节，第一个元素的存储地址为100，若按列优先顺序存储，则元素A6,6存储地址为。19一棵有N个结点的满二叉树有个度为1的结点、有个分支（非终端）结点和个叶子，该满二叉树的深度为。20假设根结点的层数为，具有个结点的二叉树的最大高度是。21在一棵二叉树中，度为零的结点的个数为N0,度为2的结点的个数为N2,则有N0。22设只含根结点的二叉树的高度为0，则高度为K的二叉树的最大结点数为,最小结点数为。23设有N个结点的完全二叉树顺序存放在向量A1N中，其下标值最大的分支结点为。24假定有K个关键字互为同义词，若用线性探测再散列法把这K个关键字存入散列表中，至少要进行次探测。25高度为8的完全二叉树至少有个叶子结点。26已知二叉树有50个叶子结点，则该二叉树的总结点数至少是。27一个有2001个结点的完全二叉树的高度为。28设F是由T1,T2,T3三棵树组成的森林,与F对应的二叉树为B,已知T1,T2,T3的结点数分别为N1,N2和N3则二叉树B的左子树中有个结点，右子树中有个结点。29一个深度为K的，具有最少结点数的完全二叉树按层次，（同层次从左到右）用自然数依此对结点编号，则编号最小的叶子的序号是；编号是I的结点所在的层次号是（根所在的层次号规定为1层）。30如某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数为。31如果结点A有3个兄弟，而且B是A的双亲，则B的度是。32有N个结点并且其高度为N的二叉树的数目是。33将下三角矩阵A18,18的下三角部分逐行地存储到起始地址为1000的内存单元中，已知每个元素占4个单元，则A7,5的地址是。34已知二维数组A110，09中每个元素占4个单元，在按行优先方式将其存储到起始地址为1000的连续存储区域时，A5，9的地址是。35按13、24、37、90、53的次序形成二叉平衡树，则该二叉平衡树的高度是，其根为，左子树中的数据是，右子树中的数据是。36假定一棵三叉树的结点个数为50，则它的最小深度为。37在操作序列QINSERT1,QINSERT2,QDELETE,QINSERT3,QINSERT4,QDELETE,QINSERT5之后，队头元素和队尾元素分别是什么、QINSERTK表示整数K入队列,QDELETE表示元素出队列。38带头结点的双循环链表L为空表的条件是。39在操作序列PUSH1,PUSH2,POP,PUSH3,PUSH4,POP,PUSH5之后,栈顶、栈底元素分别是什么、。PUSHK表示整数K入栈，POP表示栈顶元素出栈。40设数组A08,110,数组中任一元素AI,J均占内存48个二进制位，从首地址2000开始连续存放在主内存里，主内存字长为16位，那么（L）存放该数组至少需要的单元数是（2）存放数组的第8列的所有元素至少需要的单元数是（3）数组按列存储时，元素A5,8的起始地址是。41高度为8的平衡二叉树的结点数至少有个。42完全二叉树中，结点个数为N，则编号最大的分支结点的编号为。43设一棵完全二叉树叶子结点数为K,最后一层结点数2，则该二叉树的高度为。44对于一个具有N个结点的二元树，当它为一棵二元树时具有最小高度，当它为一棵时，具有最大高度。45具有N个结点的二叉树，采用二叉链表存储，共有个空链域。468层完全二叉树至少有个结点，拥有100个结点的完全二叉树的最大层数为。47含4个度为2的结点和5个叶子结点的二叉树，可有_个度为1的结点。48一棵树T中，包括一个度为1的结点，两个度为2的结点，三个度为3的结点，四个度为4的结点和若干叶子结点，则T的叶结点数为。49N（N大于1）个结点的各棵树中，其深度最小的那棵树的深度是。它共有个叶子结点和个非叶子结点，其中深度最大的那棵树的深度是，它共有个叶子结点和个非叶子结点。50每一棵树都能唯一的转换为它所对应的二叉树。若已知一棵二叉树的前序序列是BEFCGDH，对称序列是FEBGCHD，则它的后序序列是。设上述二叉树是由某棵树转换而成，则该树的先根次序序列是。51先根次序周游树林正好等同于按周游对应的二叉树，后根次序周游树林正好等同于按周游对应的二叉树。52二叉树结点的对称序序列为A,B,C,D,E,F,G,后序序列为B,D,C,A,F,G,E,则该二叉树结点的前序序列为,则该二叉树对应的树林包括棵树。53二叉树的先序序列和中序序列相同的条件是。54已知一棵二叉树的前序序列为ABDECFHG,中序序列为DBEAHFCG，则该二叉树的根为，左子树中有，右子树中有。55设二叉树中每个结点均用一个字母表示，若一个结点的左子树或右子树为空，用表示，现前序遍历二叉树，访问的结点的序列为ABDGCEHF，则中序遍历二叉树时，访问的结点序列为后序遍历二叉树时，访问的结点序列为。56已知二叉树前序为ABDEGCF，中序为DBGEACF，则后序一定是。57现有按中序遍历二叉树的结果为ABC，问有种不同的二叉树可以得到这一遍历结果，这些二叉树分别是。58一个无序序列可以通过构造一棵树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。59利用树的孩子兄弟表示法存储，可以将一棵树转换为。60若一个二叉树的叶子结点是某子树的中序遍历序列中的最后一个结点，则它必是该子树的序列中的最后一个结点。61先根次序周游树林正好等同于按周游对应的二叉树；后根次序周游树林正好等同于周游对应的二叉树。62在一棵存储结构为三叉链表的二叉树中，若有一个结点是它的双亲的左子女，且它的双亲有右子女，则这个结点在后序遍历中的后继结点是。63一棵左子树为空的二叉树在先序线索化后，其中的空链域的个数为。64具有N个结点的满二叉树，其叶结点的个数是。65设一棵后序线索树的高是50，结点X是树中的一个结点，其双亲是结点Y,Y的右子树高度是31，X是Y的左孩子。则确定X的后继最多需经过中间结点（不含后继及X本身）66线索二元树的左线索指向其，右线索指向其。67二叉树的前序遍历的操作步骤若二叉树非空（1）；（2）；（3）。68己知三对角矩阵A【19,19】的每个元素占2个单元，现将其三条对角线上的元素逐行存储在起始地址为1000的连续的内存单元中，则元素A7,8的地址为。69数据结构包括、四种结构。70表达式231232/4345/7108/9的后缀表达式是。71假设一个15阶的上三角矩阵A按行优先顺序压缩存储在一维数组B中，则非零元素A9,9在B中的存储位置K。（注矩阵元素下标从1开始）72哈夫曼树是。73若以4，5，6，7，8作为叶子结点的权值构造哈夫曼树，则其带权路径长度是。74有数据WG7，19，2，6，32，3，21，10，则所建HUFFMAN树的树高是，带权路径长度WPL为。75有一份电文中共使用6个字符A,B,C,D,E,F,它们的出现频率依次为2,3,4,7,8,9，试构造一棵哈夫曼树，则其加权路径长度WPL为，字符C的编码是。76设N0为哈夫曼树的叶子结点数目，则该哈夫曼树共有个结点。77设HEAD（P）为求广义表P的表头函数，TAIL（P）为求广义表P的表尾函数，给出下列广义表的运算结果HEAD（A,B,C），HEADA,B，TAILHEADAB,C,D。78设循环队列存放在向量SQDATA0M中，则队头指针SQFRONT在循环意义下的出队操作可表示为，若用牺牲一个单元的办法来区分队满和队空（设队尾指针SQREAR）,则队满的条件为。79深度为5的二叉数至多有个节点。80对于一个具有N个结点的单链表，在已知的结点P后插入一个新结点的时间复杂度为,在给定值为X的结点后插入一个新结点的时间复杂度为。81多个栈共存时，最好用作为存储结构。82在一棵7阶B树中，一个结点中最多有个关键字，最少有个关键字。83在双向循环链表中,向P所指的结点之后插入指针F所指的结点，其操作是、。84在一棵二叉树中有N0个叶结点，有N2个度为2的结点，则N0。85G是一个非连通无向图，共有28条边，则该图至少有个顶点。86顺序存储结构是通过表示元素之间的关系的链式存储结构是通过表示元素之间的关系的。87循环队列的引入，目的是为了克服。88不带头结点的单链表HEAD为空的判断条件是，带头结点的单链表HEAD为空的判断条件是。89某二叉树有10个叶子结点，20个结点仅有一个孩子，该二叉树的总的结点数是。90广义表A,A,B,C，HEADTAILHEADTAILHEADA等于。91带头结点的双循环链表L中只有一个元素结点的条