(大题)数据结构练习题(1).doc

模拟练习题一、单项选择题1、若某线性表中最常用的操作是取第i个元素和查找第i个元素的的前驱元素，则采用（ A）的存储方式最节省时间。A顺序表 B双链表C单链表 D单循环链表2、与数据元素本身的形式、内容、相对位置、个数无关的是数据的（ C ）。A存储结构 B存储实现C逻辑结构 D运算实现3、用链表表示线性表的优点是 （ C）。A便于随机存取 B.花费的存储空间较顺序存储少C便于插入和删除 D.数据元素的物理顺序与逻辑顺序相同4、设单向循环链表中结点的结构为（data, link），且rear是指向非空的带表头结点的单向循环链表的尾结点的指针。若想删除该链表的第一个结点，则应执行下列哪一个操作？（D ）As=rear; rear=rear-link; free(s); Brear=rear-link; free(rear);Crear=rear-link -link; free(rear); Ds=rear-link-link; rear-link-link=s-link; free(s);5、设双向循环链表中结点的结构为（data, lLink, rLink），且不带表头结点。若想在指针p所指结点之后（右链方向）插入指针s所指的结点，则应执行下列哪个操作？（ D ）Ap- rLink =s;s- lLink=p;p-rLink-lLink=s;s-rLink=p-rLinkBp- rLink =s; p-rLink-lLink=s;s-lLink=p; s-rLink=p-rLinkCs-lLink=p;s-rLink=p-rLink;p-rLink=s;p-rLink-lLink=s;Ds-lLink=p;s-rLink=p-rLink;p-rLink-lLink=s;p-rLink=s;6、在具有n个结点的有序单链表中插入一个新结点并使该链表仍然有序的时间复杂度是（ B ）。AO(1)BO(n)CO(nlogn)DO(n2)7、设单循环链表中结点的结构为（data, link），且rear是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行下列哪个操作？（D ）。As =rear; rear=rear-link; delete s; Brear=rear-link; delete rear;Crear=rear-link-link; delete rear;Ds=rear-link-link;rear-link-link=s-link; delete s;8、将下图所示的s所指结点加到p所指结点之后，其语句为（ C）。pnextsnextAs-next=p+1；p-next=s；B(*p).next=s；(*s).next=(*p).next；Cs-next=p-next；p-next=s； Ds-next=p-next；p-next=s-next；9、队列和栈的主要区别是（ D）。A逻辑结构不同 B存储结构不同C所包含的运算个数不同 D限定插入和删除操作的位置不同10、已知广义表的表头为a，表尾为（b，c），则此广义表为（ B ）。A（a，（b，c） B（a，b，c）C（a），b，c） D（a，b，c）11、对表长为n的顺序表进行顺序查找，在查找概率相等的情况下，查找成功的平均查找长度为（ C ）。A(n-1)/2 Bn/2C(n+1)/2 Dn12、如图所示的4棵树中，是满二叉树的为 （A ）。(A) (B) (C) (D)13、一个二叉树按顺序方式存储在一个维数组中，如图0 1 2 3 4 5 6 7 8 9 10 11 12 13 14ABCDEFGHIJ则结点E在二叉树的第（ C ）层。A1 B、2C3 D414、n个顶点的强连通图中至少含有（ B ）。An-l条有向边 Bn条有向边Cn(n-1)2条有向边 Dn(n-1)条有向边15、对有n个结点的顺序表进行快速排序，在最坏情况下其关键码比较次数为（D ）。AO(n) BO(log2n)CO(nlog2n) DO(n2)16、在下面各种链表结构中，能在O(1) 时间内完成在指定结点之前插入元素 X的结构是（ D ）。A单链表 B单向循环链表C带表头结点的单链表 D双向循环链表17、若让元素1,2,3依次进栈，则出栈次序不可能出现（ A ）。A3，1，2 B2，1，3 C3，2，1 D1，3，2 18、如图所示的4棵树中，不是完全二叉树的为 （ C ）。A B C D19、设只包含根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数为（ B ）。A2k B2k+1-1 C2k+1 D2k-1+120、某棵二叉树按顺序方式存储在一维数组中，如下图0 1 2 3 4 5 6 7 8 9 10 11 12 13 14ABCDEFGHIJ则结点E在二叉树的第（C ）层。A1 B2 C3 D421、含有n个结点的二叉链表中，空链域个数为（ B ）。 An Bn+1 C2n Dn222、广义表A（a），则表尾为（ C）。Aa B()C空表 D（a）23、向一个有127个元素的顺序表中插入一个新元素并保持元素原来的先后关系不变，在等概率情况下平均要移动（ B ）个元素。A、8 B、63.5C、63 D、724、设单链表中结点的结构为（data, link）。已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪个操作？（ B ）As-link=p-link;p-link=s; Bq-link= s -link; q-link= s;Cp-link=s-link;s-link=p; Dp-link=s; s-link=q;25、设单向循环链表中结点的结构为（data, link），且rear是指向非空的带表头结点的单向循环链表的尾结点的指针。若想删除该链表的第一个结点，则应执行下列哪一个操作？（ D ）As=rear; rear=rear-link; free(s); Brear=rear-link; free(rear);Crear=rear-link -link; free(rear); Ds=rear-link-link; rear-link-link=s-link; free(s);26、根据二叉树的定义，二叉树有（ B ）种形态。A. 6 B. 5 C. 4 D. 327、一棵有100个结点的完全二叉树从根这一层开始，每一层中从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左子女编号为（ A ）。A. 98 B. 99 C. 50 D. 4828、如图所示的4棵树中，不是完全二叉树的为（ C ）。A B C D29、广义表A（a），则表尾为（ C ）。Aa B() C空表 D（a）30、从顺序表2，5，7，10，14，15，18，23，35，41，52中用折半搜索法搜索出元素18需要做（ A ）次比较。A3 B4 C5 D731、n 个顶点的连通图至少有（A）条弧。An-1 Bn Cn+1 D032、顺序存储结构（ C ）。A仅适合于静态查找表的存储B仅适合于动态查找表的存储C既适合静态又适合动态查找表的存储D既不适合静态又不适合动态查找表的存储33、循环链表最大的优点是（ D ）A已知某个结点的位置后，能够直接找到它的直接前驱B在进行插入、删除等运算时，能够很好地保证链表连续C不再需要头指针D从表中任一结点出发都能扫描到整个链表34、判断头指针为head的带头结点的单链表为空的条件是（ B ）。Ahead=NULL Bhead-next=NULLChead-next=head Dhead!=NULL35、设双向循环链表中结点的结构为（data, lLink, rLink），且不带表头结点。若想在指针p所指结点之后（右链方向）插入指针s所指的结点，则应执行下列哪个操作？（ ）Ap- rLink =s;s- lLink=p;p-rLink-lLink=s;s-rLink=p-rLinkBp- rLink =s; p-rLink-lLink=s;s-lLink=p; s-rLink=p-rLinkCs-lLink=p;s-rLink=p-rLink;p-rLink=s;p-rLink-lLink=s;Ds-lLink=p;s-rLink=p-rLink;p-rLink-lLink=s;p-rLink=s;36、若让元素1,2,3依次进栈，则出栈次序不可能出现（ B ）。A3，2，1 B3，1，2 C2，1，3 D1，3，2 37、如图所示的4棵树中，不是完全二叉树的为 （ C ）。A B C D38、将含有98个结点的完全二叉树从根这一层开始，每层从左至右依次对结点进行编号，根结点的编号为1。则编号为76的结点的双亲结点的编号为（ C ）。A36 B37 C38 D不确定39、含有n个结点的二叉链表中，空指针个数为（ B ）。 An Bn+1 C2n Dn240、n 个顶点的连通图至少有（ A ）条弧。An-1 Bn Cn+1 D041、线性表采用链表存储时，其地址（ D ）A.必须是连续的 B.一定是不连续的C.部分地址必须是连续的 D.连续与否均可以42.链表不具备的特点是（ A ）A.可随机访问任一结点B.插入删除不需要移动元素C.不必事先估计存储空间D.所需空间与其长度成正比43.与单链表相比，双链表的优点之一是（ D ）A.插入、删除操作更简单B.可以进行随机访问C.可以省略表头指针或表尾指针D.访问前后相邻结点更灵活44.在一个长度为n(n1)的带头结点的单链表h上，另设有尾指针r(指向尾结点)，执行（ B ）操作与链表的长度有关。A.删除单链表中的第一个元素B.删除单链表中的最后一个元素C.在单链表第一个元素之前插入一个新元素D.在单链表最后一个元素后插入一个新元素45.两个串相等必有串长度相等且（ B ）A.串的各位置上的字符任意B.串中各位置上的字符均对应相等C.两个串含有相同的字符D.两个串所含字符任意46、算法原则上都是能够有机器或人所完成的。整个算法好象是一个解决问题的“工作序列”，其中的每一步都是我们力所能及的一个动作，这是算法的（ D ）A、正确性 B、有穷性C、确定性 D、可行性47线性表采用链式存储时，其地址（D ） 。(A) 必须是连续的； (B) 部分地址必须是连续的； (C) 一定是不连续的； (D) 连续与否均可以。 48下面关于线性表的叙述错误的是（ D ）。(A) 线性表采用顺序存储，必须占用一片地址连续的单元；(B) 线性表采用顺序存储，不便于进行插入和删除操作；(C) 线性表采用链式存储，不必占用一片地址连续的单元；(D) 线性表采用链式存储，不便于进行插入和删除操作；49. 若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。 (A) 单链表 (B) 仅有头指针的单循环链表 (C) 双链表 (D) 仅有尾指针的单循环链表50假定一个链队的队首和队尾指针分别为front和rear,则判断队空的条件为（ A ） (A) front=rear (B) front!=NULL (C) rear!=NULL (D) front=NULL51、在解决计算机主机与打印机之间速度不匹配问题时，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，打印机则从该缓冲区取出数据打印。该缓冲区应该是一个（ B ）结构。 A.堆栈 B. 队列 C.数组 D.线性表52、用链表表示线性表的优点是（C ）。 (A)便于随机存取 (B)花费的存储空间较顺序存储少 (C)便于插入和删除 (D)数据元素的物理顺序与逻辑顺序相同53、当利用长度为N的数组顺序存储一个栈时，假定用top=N表示栈空，则向这个栈插入一个元素时，首先应执行（B ）语句修改top指针。 A.top+ B.top- C.top D.top=054、设一棵二叉树中，度为1的结点数为9，则该二叉树的叶子结点的数目为（ D ）A.10 B.11 C.12 D.不确定55、有8个顶点的无向连通图最少有（ C）条边。A.5 B.6 C.7 D.856、一个算法必须在执行有穷步之后结束，这是算法的（ B ）。A、正确性 B、有穷性 C、确定性 D、可行性57线性表是（ A ）。 (A)一个有限序列，可以为空；(B) 一个有限序列，不能为空 (C) 一个无限序列，可以为空 (D) 一个无序序列，不能为空。 58对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（ A ）个元素。 (A) n/2 (B) n+1/2 (C) n-1/2 (D) n 59.线性表采用链式存储时，其地址（ D ） 。(A) 必须是连续的； (B) 部分地址必须是连续的； (C) 一定是不连续的； (D) 连续与否均可以。 60用链表表示线性表的优点是（ C ）。 (A)便于随机存取 (B)花费的存储空间较顺序存储少 (C)便于插入和删除 (D)数据元素的物理顺序与逻辑顺序相同61、栈中元素的进出原则是（ B ）A.先进先出 B.后进先出 C.栈空则进 D.栈满则进62、判定一个栈ST（最多元素为m0）为空的条件是（ B ） A.ST-top0 B. ST-top=-1 C. ST-topm0 D. ST-top=m063、当利用长度为N的数组顺序存储一个栈时，假定用top=N表示栈空，则向这个栈插入一个元素时，首先应执行（ B ）语句修改top指针。 A.top+ B.top- C.top D.top=064、设一棵二叉树中，度为1的结点数为9，则该二叉树的叶子结点的数目为（ D ）A.10 B.11 C.12 D.不确定65、有8个顶点的无向图最多有（B）条边。A.14 B.28 C.56 D.11266、算法的每一步必须有确切的定义，也就是说，对于每步需要执行的动作必须严格、清楚地给出规定，这是算法的（ C ）。A、正确性 B、有穷性C、确定性 D、可行性67顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（ A ）个元素。(A) n/2 (B) n+1/2 (C) n -1/2 (D) n 68下面关于线性表的叙述错误的是（ D ）。(A) 线性表采用顺序存储，必须占用一片地址连续的单元；(B) 线性表采用顺序存储，不便于进行插入和删除操作；(C) 线性表采用链式存储，不必占用一片地址连续的单元；(D) 线性表采用链式存储，不便于进行插入和删除操作；69.线性表采用链式存储时，其地址（D ） 。(A) 必须是连续的； (B) 部分地址必须是连续的； (C) 一定是不连续的； (D) 连续与否均可以。 70判定一个队列QU（最多元素为m0）为满队列的条件是（ A ） A.QU-rear-QU-front=m0 B.QU-rear-QU-front-1=m0 C. QU-rear=QU-front D. QU-front=QU-rear+1 71、设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（ C ）A.2h B.2h+1 C.2h-1 D.h+172、深度为5的二叉树至多有（ C ）个结点。 A.16 B.32 C.31 D.1073、设一棵二叉树中，度为1的结点数为9，则该二叉树的叶子结点的数目为（ D ）A.10 B.11 C.12 D.不确定74、在一个图中，所有顶点的度数之和等于图的边数的（ C ）倍。A.1/2 B.1 C.2 D.475、如图所示的4棵树中，是满二叉树的为（ A ）。A B C D76、二维数组A按行优先顺序存储，其中每个元素占1个存储单位。若A11的存储地址为420，A33的存储地址为446，则A55的存储地址为（ C ）。A470B471C472D47377、设有两个均只有头指针的单链表，若要将长度为n的单链表链接到长度为m的单链表之后，则实现该功能的算法的时间复杂度为（ C ）。AO(1)BO(n)CO(m)DO(m+n)78、设单循环链表中结点的结构为（data, link），且rear是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行下列哪个操作？（ D ）As =rear; rear=rear-link; delete s;Brear=rear-link; delete rear;Crear=rear-link-link; delete rear;Ds=rear-link-link;rear-link-link=s-link; delete s;79、从堆中删除一个元素的时间复杂度为（C ）。AO(1)BO(n)CO(log2n)DO(nlog2n)80、对于一棵具有n个结点的二叉树，在其二叉链表的存储结构中，所有结点的空指针数等于（ C ）。AnBn-1Cn+1D2*n81、如图所示的4棵二叉树中，不是完全二叉树的为（ ）。(A) (B) (C) (D)82、利用逐点插入法建立序列(50，72，43，85，75，20，35，45，65，30)对应的二叉搜索树以后，查找元素35要进行（ ）元素间的比较。A4次 B5次C. 7次 D10次83、在一个带权连通图G中，权值最小的边一定包含在G的（ A ）中。A最小生成树B生成树C广度优先生成树D深度优先生成树84、一个有n个顶点和n条边的无向图一定是（A ）。A连通的B不连通的C无回路D有回路85、对n个关键字的序列进行快速排序，其平均情况下的空间复杂度为（ B ）。AO(1)BO(log2n)CO(n)DO(nlogn)二、填空题1.在线性表的顺序存储中，元素之间的逻辑关系是通过（ 元素的存储地址 ）决定的。2、一个顺序栈存储于一维数组am中，当栈顶指针等于（-1 ）时，则为空栈。3、有42个结点的二叉树的高度最小是（ 6 ）。4、在一棵二叉树中，假定度为2的结点有5个，度为1的结点有6个，则叶子结点数有（ 6 ）个。5、在一个最小堆中，堆顶结点的值是所有结点中的（ 最小值 ）。6、对于一个具有n个顶点昨e条边的连通图，其生成树中的边数为（ n-1 ）。7、从邻接矩阵A=可以看出，若该图是有向图，则共有（ 4 ）条边。8、直接插入排序在最好情况下的时间复杂度为（ O（1） ）9.在线性表的链式存储中，元素之间的逻辑关系是通过（结点中的指针 ）决定的。10.在一个长度为n的顺序表中的第i个元素（1in）之前插入一个元素时，需向后移动（ n-i+1）个元素。11.在一个长度为n的顺序表中删除第i个元素（1in）时，需要向前移动（n-i ）个元素。12、数据的逻辑结构是从逻辑上描述数据，它与数据的（存储结构 ）无关，是独立于计算机的。13、数据的逻辑结构是从逻辑上描述数据，它与数据的（ 存储结构 ）无关，是独立于计算机的。14、在下面程序段中，设n为常数，s=s+p；语句的执行次数为（ n）。int i=0, s=0;while(+i=n)int p=1;for(int j=1;j=i; j+) p*=j;s=s+p;15、算法的每一步必须有确切的定义，也就是说，对于每步需要执行的动作必须严格、清楚地给出规定，这是算法的（ 确定性 ）。16、在下面程序段中，设n为常数，s=s+p；语句的执行次数为（ n ）。int i=0, s=0;while(+in)int p=1;for(int j=1;jnext-next ）。29、队列中队尾指针是随着（ 进队 ）操作而发生变化的。30、以折半搜索方法搜索一个线性表时，此线性表必须是（ 有序的 ）。31、在平衡的二叉搜索树中，任意结点的平衡因子的绝对值均（ 不超过1 ）。32、在线性表的链式存储中，元素之间的逻辑关系是通过（ 节点的指针 ）决定的。33、在一个长度为n的顺序表中删除第i个元素（1in）时，若保持元素间的先后关系不变，需要向前移动（ n-i）个元素。34、在顺序表（最后一个 ）元素后面插入一个元素，不需要移动任何元素。35、队列的操作特点是（ “先进先出” ）。36、树中任意结点允许有零个或多个孩子结点，除根结点外，其余结点（ 只有一个 ）双亲结点。37、对二叉排序树进行（ 中序 ）遍历，可以得到按关键字从小到大排列的结点序列。38、以折半搜索方法搜索一个线性表时，此线性表必须是（有序的 ）。39、任何一棵树的结点个数减去边数等于（ 1 ）40、在平衡的二叉排序树中，任意结点的平衡因子的绝对值均（ 不大于1 ）41.删除顺序表的（最后一个 ）元素，不需要移动任何元素。42.删除顺序表的（第一个）元素，需要移动的元素最多。43.在顺序表（最后一个 ）元素后面插入一个元素，不需要移动任何元素。44.在单链表中，要删除某一指定的结点，必须找到该结点的（ 前驱 ）结点。45.栈是一种具有（ “后进先出” ）操作特性的线性表。46、在线性表的顺序存储中，元素之间的逻辑关系是通过（元素的存储地址 ）决定的。47、在线性表的链式存储中，元素之间的逻辑关系是通过（ 结点的指针）决定的。48、在用于表示有向图的邻接矩阵中, 对第J列的元素进行累加, 可得到第J个顶点的（ 入）度。49、在一个长度为n的顺序表中删除第i个元素（1in）时，若保持元素原来的先后关系不变，需要向前移动（ n-i）个元素。50、在单链表中，要删除某一指定的结点，必须找到该结点的（前驱）结点。51、栈是一种具有（ “后进先出”）操作特性的线性表。52、循环队列的优点是（ 充分利用空间，防止假溢出）。53、有10个结点的二叉树的高度最大是（10 ）。54、不加限定时，遍历二叉树有（3 ）种结点排列顺序55、深度为K（K1）的满二叉树有（ 2k-1 ）个结点56.在队列中，新插入的元素只能插入到（ 队尾 ）57.循环队列的优点是（充分利用空间，防止假溢出 ）。58、算法的每一步必须有确切的定义，也就是说，对于每步需要执行的动作必须严格、清楚地给出规定，这是算法的（ 确定性）。59、在线性表的顺序存储中，元素之间的逻辑关系是通过（元素的存储地址 ）决定的。60、在一个长度为n的顺序表中的第i个元素（1in）之前插入一个元素时，若保持元素原来的先后关系不变，需向后移动（ n-i+1 ）个元素。61、在单链表中，要删除某一指定的结点，必须找到该结点的（ 前驱 ）结点。62、循环队列的优点是（充分利用空间，防止假溢出 ）。63、在一棵二叉树中，层次从1开始，第5层上的结点数最多为（ 16 ）。64、有10个结点的二叉树的高度最大是（ 10 ）。65、在一棵二叉树中，假定度为2的结点有5个，度为1的结点有6个，则叶子结点数有（ 6 ）个。66、在用于表示有向图的邻接矩阵中, 对第I行的元素进行累加, 可得到第I 个顶点的（ 出 ）度。三、判断题1.线性表中每个元素都有一个直接前驱和一个直接后继。（ F ）2.线性表中所有元素的排列顺序必须由小到或由大到小。（ F ）3、向栈顺序地输入一个整数序列1,2,3,4,5,6，能得到输出序列3,2,5,6,4,1。（T ）4、满二叉树的结点个数一定为奇数。（ T ）5、在只有度为0和度为k的结点的正则k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。（ F ）6、满二叉树的结点个数不一定为奇数。（ F ）7、若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点。（ T ）8、链表插入排序方法是稳定的。（ T ）9、栈和队列的存储方式既可是顺序方式，也可是链接方式。（ T ）10、邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。（ F ）11、直接插入排序中的数据比较次数与数据的初始排列无关。（F ）12、链表插入排序方法是稳定的。（T ）3.在循环单链表中，从表中任一结点出发都可以通过前后的移动操作扫描整个循环链表。（ F ）13.在单链表中，可以从头结点开始查找任何一个结点。（ T ）14.在n个元素进栈后，它们的出栈顺序和进栈顺序必定正好相反。（ T ）15.对顺序栈进行进栈、出栈操作，不涉及元素的前、后移动问题。（ T ）16.空串就是由空格构成的串。（ F ）17、线性表的链式存储结构优于顺序存储结构。（ F ）18、一个算法的评价主要从时间复杂度和空间复杂度来考虑。（ T ）19、在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。（ F ）20、根据二叉树的先序和后序序列可以唯一地确定一棵二叉树。（ F ）21、无向图的连通分量可以有很多个。（ T ）22、线性表的逻辑顺序与存储顺序总是一致的。（ F ）23、线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。（ T ）24、线性表的顺序存储表示优于链式存储表示。（ F ）25、若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点。（ F ）26、对于同一组待输入的关键码集合，虽然各关键码的输入次序不同，但得到的二叉搜索树都是相同的。（ F ）27、将一棵树转换为二叉树后，根结点没有右子树。（ T ）28、快速排序方法是不稳定的排序方法。（ T ）29、在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。（ F）30、二叉树是一种特殊的树。（ T ）31、无向图的连通分量只有一个。（ F ）32、线性表的链式存储结构优于顺序存储结构。（F ）33、一个算法的评价只从时间复杂度考虑。（ F ）34、在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。（ F ）35、根据二叉树的先序和中序序列可以唯一地确定一棵二叉树。（ T ）36、无向图的连通分量可以有很多个。（ T ）37、哈希冲突是指同一个关键字对应多个不同的哈希地址。（ F ）38、N个元素进队列的顺序和出队列的顺序是一致的。（ T ）39.空串就是由空格构成的串。（ F ）40、图G的最小生成树的代价一定小于其他生成树的代价。（ T ）41一个算法的评价主要从时间复杂度和空间复杂度来考虑。（ T ）42哈希冲突是指同一个关键字对应多个不同的哈希地址。（ F ）43在二叉排序树中，每个结点的关键字都比左孩子关键字大，比右孩子关键小。（ T ）44连通图的生成树包含了图中所有顶点。（ T ）45.哈夫曼树中不存在度为1的结点。（ T ）四、简答题1、设表示式a+b*(c-d)-e/f对应的语法树如图所示，请写出该语法树的前序、中序、后序、层次遍历的结果序列。-+*-d/efabc前序序列：-+a*b-cd/ef中序序列：a+b*c-d-e/f后序序列：abcd-*+ef/-2、已知一棵二叉树如下，请写出按前序、中序、后序、层次遍历时得到的结点序列。前序序列：ABDGHJKECFIM中序序列：GDJHKBEACFMI后序序列：GJKHDEBMIFCA层次遍历: ABCDEFGHIJKM3、设输入元素为1，2，3，P和A，输入次序为123PA，如下图所示，经过栈后到达输出序列，当所有元素均到达输出序列后，有哪些序列可作为高级语言的变量名？123PA输入序列输入序列答：pa321,p3a21,p32a1,p321a,ap3214、设有序列30,18,3,61,14,49，请按该序列构成一棵二叉排序树，并求其查找成功时的平均查找长度。 30 18 61 3 49 14查找成功时的平均查找长度:1/6(1+2+2+3+3+4)=2.55、有7个带权结点，其权值分别为3，7，8，2，6，10，14，试以它们为叶子结点生成一棵霍夫曼树（要求左子女的权值小于右子女），并求出该树的带权路径长度。（这道题还有问题） 50 29 21 14 15 10 11 7 8 5 6 2 3该树的带权路径长度为：14*2+7*3+8*3+10*2+2*4+3*4+6*3=1316、设有一个输入数据的序列为46，25，78，62，12，37，70，29，试根据二叉排序树的插入过程画出逐个输入以上数据而生成的二叉排序树。（要求写出插入过程）(这道题不懂) 46 25 78 12 37 62 29 707、已知某系统在通讯时，只出现F，T，D，S，H五种字符，它们出现的频率依次为5，10，4，2，1，试设计Huffman编码。（定义左子树为0右子树为1） 22 12 10 5 73 4 1 2Huffman编码为：F: 00,T:1,D:011,S:0101,H:01008、用序列（46，88，45，39，70，58，101，10，66，34）建立一棵二叉排序树，画出该树，并求在等概率情况下查找成功的平均搜索长度。（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值； （3）左、右子树也分别为二叉排序树；（66为什么不排在101左下侧） 46 45 88 39 70 101 10 58 34 66平均搜索长度:1/10(1+2+2+3+3+3+4+4+5+5)=3.29、在实际应用中经常遇到的稀疏矩阵是三对角矩阵，如下图所示。在该矩阵中除主对角线及在主对角线上下最临近的两条对角线上的元素外，所有其他元素均为0。现在要将三对角矩阵A中三条对角线上的元素按行优先方式存储在一维数组B中，且a11存放于B0。试给出计算A在三条对角线上的元素aij（1in，i-1ji+1）在一维数组B中的存放位置的计算公式。（5分）（这道题不懂）A=a11a12a21a22a23a32a33a34ann-1ann答：k=2*i+j-310、分别根据Kruskal、普里姆算法的基本思想，从顶点0开始，给出下图的最小生成树(要求写出生成过程)。0543612102825161222241814Kruskal算法的最小生成树如上图红线所示0543612102825161222241814Prim算法如图所示。11、若一个具有n个顶点，k条边的无向图是一个森林（nk），则该森林中必有多少棵树。答假设该森林中有s棵树：T1,T2,TS ，且每个Ti有ni 个结点，ki条边(i=1,2,，S),由树的等价条件可知： kini1，则kk1+k2+ks=（n11）+（n21）（ns1）ns,故s=nk,所以该森