数据结构练习.docx

《数据结构练习.docx》由会员分享，可在线阅读，更多相关《数据结构练习.docx（21页珍藏版）》请在三一办公上搜索。

1、数据结构习题Lists、选择题1 .在一个长度为n的顺序表中，向第i个元素(1WiWn+1)之前插入一个新元素时，需向后移动 个元素。A. n-1B. n-i+12. 线性表是。A. 一个有限序列，可以为空C. 一个无限序列，可以为空C. n-i-1D. IB. 一个有限序列，不能为空D. 一个无限序列，不能为空3. 对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的，删除一个元素时大约要移动表中的 个元素。A. n+1B. n-1C. (n-1)/2 D. n4. 线性表采用链式存储时，其地。A. 必须是连续的B.部分地址必须是连续的C. 一定是不连续的D.连续与否均可

2、以5. 设单链表中指针p指着结点(数据域为m)，指针f指着将要插入的新结点(数据域为x)，当x插在结点m之后时，只要先修改 后修改p-link=f即可。A. f-link=p;B. f-link=p-link;C. p-link=f-link;D. f=nil;6. 在双向链表存储结构中，删除p所指的结点时需修改指针。A. (p-rlink) -rlink) -link=p; p-rlink=(p-rlink) -rlink;B. (p-llink) -rlink=p-rlink; (p-rlink) -llink=p-llink;C. p-llink=(p-llink) -llink; (p

3、-llink) -llink) -rlink=p;D. (p-llink) -llink) -rlink=p; p-llink=(p-llink) -llink;7. 在双向链表存储结构中，删除p所指的结点的前趋结点(若存在)时需修改指 针。A. (p-llink) -llink) -rlink=p; p-llink=(p-llink) -llink;B. (p-rlink) -rlink) -llink=p; p-rlink=(p-rlink) -rlink;C. (p-llink) -rlink=p-rlink; (p-rlink) -llink=p-llink;D. p-llink=(p

4、-llink) -llink; (p-llink) -llink) -rlink=p;8. 根据线性表的链式存储结构，每个结点所含指针的个数，链表分为单链表和。A.循环链表 B.多重链表 C.普通链表D.无头结点链表9. 从一个具有n个节点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较 个结点。A. nB. n/2C. (n-1)/2 D. (n+1)/210. 在一个单链表中，已知*q结点是*p结点的前驱结点，若在*4和*?之间插入*，结点， 则执行。A. s-next=p-next; p-next=s;B. p-next=s-next; s-next=p;C. q-next

5、=s; s-next=p;D. p-next=s; s-next=q;、填空1. 在线性结构中第一结点 ，其余每个结点有且只有 ;最后一个结点，其余每个结点有且只有 。2. 对于顺序存储的线性表，当随机插入或删除一个元素时，约需平均移动表长 的元素。3. 对于长度为n的顺序表，插入或删除元素的时间复杂性为 ；对于顺序栈或队歹。，插入或删除元素的时间复杂性为 。4. 从顺序表中删除第i个元素时，首先把第i个元素赋给 带回，接着从 开始向后的所有元素均 一个位置，最后使线性表的长度 。5. 在线性表的顺序存储中，元素之间的逻辑关系是通过 决定的；在线性表的链接存储中，元素之间的逻辑关系是通过 决定

6、的。6. 一个单链表中删除*?结点时，应执行如下操作：(1) q=p-next;(2) p-data=p-next-data;(3) p-next=1;(4) free(q);7. 若要在一个单链表中的*?结点之前插入一个*，结点时，可执行如下操作：(1) s-next=1;(2) p-next=s;(3) t=p-data;(4) p-data=2;(5) s-data=3;8. 对于线性表的顺序存储，需要预先分配好存储空间，若分配太多则容易造成存储空 间的，若分配太少又容易在算法中造，因此适应于数据量 变化不大的情况；对于线性表的链接存储(假定采用动态结点)，不需要 分配 存储空间，存储器

7、中的整个 都可供使用，分配和回收结点都非常方便，能 够有效地利用存储空间，在算法中不必考虑 的发生，因此适应数据量变化较大的情况。四、综合题1. 线性表有两种存储结构：一是顺序表，二是链表。试问：(1) 两种存储表示各有哪些主要优缺点？(2) 如果有n个线性表同时并存，并且在处理过程中各表的长度会动态发生变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构?为什么？(3) 若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么，应采用哪种存储结构?为什么？2. 用线性表的顺序结构来描述一个城市的设计和规划合适吗?为什么？3. 在单链表和双向表中，能

8、否从当前结点出发访问到任一结点？4. 编写下列算法(1) 向类型有list的线性表L的第i个元素(OWiWL.len)之后插入一个新元素x。(2) 从类型为list的线性表L中删除其值等于x的所有元素。(3) 将两个有序表A和B合并成一个有序表C，其中A，B，C均为list类型的变参。5. 编写下列算法，假定单链表的表头指针用HL表示，类型为linklist。(1) 将一个单链表中的所有结点按相反次序链接。(2) 删除单链表中第i个(i31)结点。(3) 删除单链表中由指针p所指向的结点。(4) 从带有附加表头结点的循环单链表中删除其值等于x的第一个结点。(5) 在单链表中指针p所指结点之前插

9、入一个值为x的新结点。(6) 从循环单链表中查找出最小值。(7) 根据一维数组A(1:n)中顺序存储的具有n个元素的线性表建立一个带有附加表头结 点的单链表。(8) 请指出下面的过程执行p(5)和p(6)时分别输出的结果。void P(int n);if n0p(n-2);printf(%d”,n);(9) 假定用一个循环单链表表示队列(称此为循环链队)，该队列只设一个队尾指针，设队首指针，试编写下列算法：(1) 向循环链队插入一个元素为x的结点；(2) 从循环链队中删除一个结点(假定不需要保留被删除结点的值和不需要回收结点)。Stack/Queue一、选择题1. 在一个具有n个单元的顺序栈中

10、，假定以地址低端作为栈底，以top作为栈顶指针， 则当做退栈处理时，top变化为。A. top 不变B. top= -nC. top=top-1 D. top=top+12. 向顺序栈中压入元素时， 。A.先存入元素，后移动栈顶指针B.先移动栈顶指针，后存入元素3. 在一个顺序存储的循环队列中，队首指针指向队首元素的。A.前一个位置 B.后一个位置 C.队首元素位置D.队尾元素位置5 .若进栈序列为1,2,3,4，进栈过程中可以出栈，则 不可能是一个出栈序列。A. 3,4,2,1 B. 2,4,3,1C. 1,4,2,3 D. 3,2,1,46 .在具有n个单元的顺序存储的循环队列中，假定fr

11、ont和rear分别为队首指针和队 尾指针，则判断队空的条件是 。A. front= =rear+1 B. front+1= =rear C. front= =rear D. front= =07 .在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队 尾指针，则判断队满的条件。A. rear % n= =front B. (rear-1) % n= =frontC. (rear-1) % n= =rear D. (rear+1) % n= =front8 .向一个栈项指针为hs的链栈中插入一个*s结点时，则执行。A. hs-next=s;B. s-next=hs-

12、next; hs-next=s;C. s-next=hs； hs=s;D. s-next=hs; hs=hs-next;9. 在一个链队列中，假定front和rear分别为队首指针和队尾指针，则进行插入*，结 点的操作时应执行 。A. front-next=s; front=s;C. front=front-next;B. rear-next=s; rear=s;D. front=rear-next;二、综合题1、试给出链式栈的实现代码？2、试给出链式队列的实现代码?Tree一.选择题（根节点为第1层）1. 假定在一棵二叉树中，双分支结点数为15个，单分支结点数为32个，则叶子结点数 为 。A

13、.15B.16C. 17D.472. 假定一棵二叉树的结点数为18个，则它的最小高度 。A.4B.5C. 6D.183. 在一棵二叉树中第五层（根节点为第1层）上的结点数最多为 。A.8B.15C.16D.324. 在一棵具有五层（根节点为第1层）的满二叉树中，结点总数为 。A.31B.32C.33D.165. 已知8个数据元素为（34、76、45、18、26、54、92、65），按照依次插入结点的方法生成 一棵二叉排序树后，最后两层上的结点总数为 。A. 1B. 2C. 3D. 46. 由分别带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度A. 23B. 37C. 44

14、D. 467. 在树中除根结点外，其余结点分成m （m30）个 的集合T1,T2,T3.Tm,每个集合 又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点（1WiWm）。A.C.互不相交叶结点可以相交B.可以相交D.树枝结点可以相交8. 下面答案 是查找二叉树（又称二叉排序树）。A. 二叉树中的每个结点的两棵子树的高度差的绝对值不大于1B. 二叉树中的每个结点的两棵子树的高度差等于1C. 二叉树中的每个结点的两棵子树是有序的D. 二叉树中的每个结点的关键字大于其左子树（如果存在）所有结点的关键字值， 且小于其右子树（如果存在）所有结点的关键字值。9. 如果结点A有三个兄弟，而且B是入的双

15、亲，则B的出度是。A. 3B. 4C. 5D. 110. 一个深度为L的满K叉树有如下性质：第L层上的结点都是叶子结点，其余各层上每个结 点都有K棵非空子树。如果按层次顺序从1开始对全部结点编号，编号为n的有右兄弟的 条件是。A. (n-1) % k= =0 B. (n-1) % k!=0 C. n % k= =0 D. n % k!=011. 在完全二叉树中，当i为奇数且不等于1时，结点i的左兄弟是结点 ，否则没 有左兄弟。A. 2i-1B. i+1C. 2i+1D. i-112. 某二叉树T有n个结点，设按某种遍历顺序对T中的每个结点进行编号，编号值为1,2,.,n且有如下性质：T中任一结

16、点V，其编号等于左子树上的最小编号减1，而V 的右子树的结点中，其最小编号等于V左子树上结点的最大编号加1。这时按 编 号。A.中序遍历序列B.前序遍历序列 C.后序遍历序列 D.层次遍历序列13. 最小代价生成树 。A.是唯一的B.不是唯一的C.唯一性不确定D.唯一性与原因的边的权数有关二、填空1. 在树型结构中，树根结点没有 结点，其余每个结点有且仅有;树叶 结点没有 ，其余每个结点的 结点数不受限制。2. 对于一棵具有n个结点的树，则该树中所有结点的度之和为。3. 在一棵二叉树中，度为0的结点的个数为n0，度为2的结点的个数为n2，则：4. 在二叉树的顺序存储中，对于下标为5的结点，它的

17、双亲结点的下标为 ，若 它存在左孩子，则左孩子结点的下标为 ，若它存在右孩子，则右孩子结点 的下标为 。5. 假定一棵二叉树的广义表表示为A(B(，D)，C(E(G)，F)，则该树的深度为，度 为0的结点数为，度为1的结点数为，度为2的结点数为 ；C结点 是A结点的 ，E结点是C结点的 。6. 在一棵二叉排序树中，按 遍历得到的结点序列是一个有序序列。7. 由分别带权为3,9,6,2,5的共五个叶子结点构成一棵哈夫曼树，则带权路径长 8. 假定在二叉树的链接存储中，每个结点的结构为| left | data | right |，其中 data为值域，left和right分别为链接左、右孩子结点

18、的指针域，请在下面中序遍历算法中 画有横线的地方填写合适的语句。void inorder(bt) if( bt != NULL ) (1) ;(2) ;(3) ；Gragh一、选择题1. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和白 倍。A. 1/2B. 1C. 2D. 42. 对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为 。A. nB. n+1C. n-1D. n+e3. 具有n个顶点的无向完全图，边的总数为 条。A. n-1B. nC. n+1D. n*(n-1)/24. 设图G有n个顶点和e条边，当G是非孤立顶点的连通图时有2e=n,故可推得深

19、度优先搜 索的时间复杂度为。A. O(e)B. O(n)C. O(ne)D. O(n+e)5. 在无向图G的邻接矩阵A中，若Ai,j等于1，则Aj,i等于。A. i+jB. i-jC. 1D. 06. 图的深度优先或广度优先遍历的空间复杂性均为。(访问标志位数组空间)A. O(n)B. O(e)C. O(n-e)D. O(n+e)二、填空1. 在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点 的 ，对于有向图来说等于该顶点的 。2. 假定一个图具有n个顶点和e条边，则采用邻接矩阵表示的空间复杂性为，采用 邻接表表示的空间复杂性为 。3. 已知一个无向图的邻接矩阵如下

20、所示，则从顶点A出发按深度优先搜索遍历得到的顶点序 列为 ，按广度优先搜索遍历得到的顶点序列为ABCDEF厂011010n A1 101011 1 B1 110100 | C1 001001 1 D1 110001 |EL010110J F4. 已知一个图如下所示，在该图的最小生成树中，各边的权值之和为四、综合题1. 证明n个顶点的无向完全图的边数的n(n1)/2。2. 证明一个有n个顶点，e条边的无向图G,必有dj =2e其中dj为顶点j的度。3. 证明若无向图G的顶点度数的最小值大于或等于2,则G有一条回路。4. 设无向图G如下图：该图的邻接矩阵；(2) 该图的邻接表；(3) 从A出发的“

21、深度优先”遍历序列;(4) 从A出发的“广度优先”遍历序列。Sorting、选择题1. 目前以比较为基础的内部排序时间复杂度T(n)的范围是 ;其比较次数与待 排序的记录的初始排列状态无关的是 。A. O(log2 n)O(n)O(nlog2 n)O(n2 )B. 插入排序快速排序 O(lon2 n)O(n2 )O(n)O(n2)O(n)O(nlog2 n)先用二分法查找，找到后插入排序冒泡排序2. 设关键字序列为：3,7,6,9,8,1,4,5,2。进行排序的最小交换次数是。A. 6B. 7C. 8D. 203. 在归并排序过程中，需归并的趟数为 。A. nB. V n C. log2 n

22、向上取整D. log2 n向下取整4. 一组记录排序码为（46、79、56、38、40、84）,则利用堆排序的方法建立的初始堆为。A.（79、 46、56、38、40、 80）B.（84、79、56、 38、 40、 46）C. （84、 79、56、46、40、 38）D.（84、56、79、 40、 46、 38）5. 一组记录的关键码为（46、79、56、38、40、84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为。A.（38、 40、46、56、79、 84）B.（40、38、 46、 79、 56、 84）C. （40、 38、46、56、79、 84）D.（40

23、、38、 46、 84、 56、 79）6. 在平均情况下快速排序的时间复杂性为 ，空间复杂性为 ；在最坏情况 下（如初始记录已有序），快速排序的时间复杂性为，空间复杂性为。A. O（n） B. O（log2 n） C. O（nlog2 n） D. O（n2 ） 二、填空1. 在对一组记录（54,38,96,23,15,72,60,45,83）进行直接选择排序时，第四次选择和交 换后，未排序记录（即无序表）为 。2. 在对一组记录（54,38,96,23,15,72,60,45,38）进行冒泡排序时，第一趟需进行相邻记录交换的次数为 ，在整个冒泡排序过程中共需进行 趟后才能完成。3. 在归并排

24、序中，若待排序记录的个数为20，则共需要进行 趟归并，在第三趟归并中，是把长度为 的有序表归并为长度为的有序表。4. 在直接插入和直接选择排序中，若初始数据基本正序，则选用 ，若初始数据基本反序，则选用。5 .在堆排序、快速排序和归并排序中，若只从节省空间考虑，则应首先选取 方法，其次选取 方法，最后选取 方法；若只从排序结果的稳定 性考虑，则应选取 ；若只从平均情况下排序最快考虑，则应选取 方法；若只从最坏情况下排序最快并且要节省内存考虑，则应选取方法。单选：在数据结构中，与所使用的计算机无关的数据叫 结构。A.存储B.物理C.逻辑D.物理和存储在数据结构中，从逻辑上可以把数据结构分为（）A

25、.动态结构和静态结构B.紧凑结构和非紧凑结构C. 线性结构和非线性结构D.内部结构和外部结构采用线性链表表示一个向量时，要求占用的存储空间地址（）。A.必须是连续的B.部分地址必须是连续的C. 一定是不连续的D.可连续可不连续在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（）。A. slink = pTink; pTink = s;B. plink = s; slink = q;C. plink = slink; slink = p;D. qlink = s;slink = p;线性表的链式存储结构与顺序（连续）存储结构相比优点是（）入.所有的操作/运算算法简单B

26、.便于随机存取C.便于插入和删除D.便于查找在线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（） 存储方式最节省运算时间。A. 单链表B.仅有头指针的单循环链表。.双链表D.仅有尾指针的单循环链表链表不具有的特点是（）A.可随机访问任一元素B.插入、删除不需要移动元素C.不必事先估计存储空间D.所需空间与线性表长度成正比在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓 冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依相同次序从该缓 冲区中取出数据打印。该缓冲区作为数据结构是一个（）结构。A.栈 B.队列 C.表（Table） D.线性表一个

27、队列的入队序列是1, 2, 3, 4,则队列的出队序列为（）。A. 4,3,2,1B.1,2,3,4 C. 1,4,3,2D. 3,2,4,1一个栈的输入序列为1, 2, 3, 4, 5,则下列序列中不可能是栈的输出序列的 是（ ）A.2 5 3 4 1B.1 2 3 4 5C.3 2 1 4 5D .5 4 3 2 1将一个A0.19 0. 19（注：下标均从0开始计）的矩阵，按行序为主序 存放，每个元素占4个存储单元，并且A1，2的存储地址是1088,则A16, 3的地址是（）A.1292 B. 1296 C.2292 D.2524将一个A 1.20 1. 20（注：下标均从1开始计）的矩

28、阵，按行序为主存放，每个元素占4个存储单元，并且A1, 2的存储地址是1004，则A20, 2的地址是（）。A. 1004 B. 1380 C. 1520 D. 2524非空的循环单链表head的尾结点（由p所指向）满足（）。A. p-next=NULL B. p=NULL C. p-next=headD. p=head设循环队列用数组0. n-1存放其元素值，其头指针front指向队首元素，rear指向队尾元素，则队列的长度为（）。A. rear-frontB. rear-front+ 1C. （rear front + 1）%nD. （rear front + n）%n栈和队列的共同特点是

29、（）。A.都是先进先出 B.都是先进后出C. 都是只允许在端点处进行插入和删除的操作受限的线性表D. 没有共同点在一棵具有5层的满二叉树中结点数为（）A 31 B 32 C 33 D 16设有100个数据元素，采用折半搜索时，最大比较次数为（）A 6 B 7 C 8 D 10在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。A. 3 B. 2C. 1 D. 1/2树中所有结点的度等于所有结点数加（）A. 0B. 1C. -1D. 2在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（）A. nB. n-1C. n+1D. 2*n对二叉树从1开始进行连续编号，要求每个结点的编号大于其左

30、右孩子的编号，同一结点的 左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用（）次序的遍历实现编号。A.先序B.中序 C.后序D.从根开始的层次遍历若无向图G有7个顶点，至少需要（）条边，才能 保证 该图一定是连通图（边可依附任两顶点，但无重复边和自环）A. 43B. 31C. 25D. 6若一棵二叉树具有10个度为2的结点，则该二叉树的度为0的结点个数是（）。A. 9B. 11C. 12D.不确定在下列树中，（）是完全二叉树在一棵度为3的树中，度为3的结点个数为2,度为2的结点个数为1，则度为0的结点个数 为（）A. 4 B. 5C. 6D. 7树的基本遍历策略分为先根遍历和后根遍历；二

31、叉树的基本遍历策略可分为先序遍历、中序 遍历和后序遍历。结论（）是正确的A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同B. 树的后根遍历序列与其对应的二叉树的先序遍历序列相同C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同D. 以上都不对在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（）A. eB.2eC. n2 - e D. n2 - 2e线性表必须是（），才能进行二分查找。A. 用顺序存储的无序表B. 用链表存储的有序表C. 用链表存储的无序表D. 用顺序存储的有序表已知一有向图的邻接表存储结构如下：据有向图的广度优先遍历算法，从顶点V1出发，所得到的顶点序列是

32、（A.V1V2V3V4V5 B.V1V2V3V5V4 C.V1V3V2V4V5 D.V1V4V3V2V5 一个待排序文件的关键字如下：265 301 751 129 087 863 742 694 076 438经过（）趟直接插入排序后可得到如下序列：129 265 301 751 087 863 742 694 076 438A. 1B. 2C. 3D. 4对有18个元素的有序表做折半（二分）查找，则查找A3的比较序列的下标依次为（）。A,1-2-3B.9-5-2-3C.9-5-3 D. 9-4-2-3循环队列用数组A0.m-1存放其元素值，已知其头尾指针分别为front和rear，则当前元

33、 素个数为（）A. （rear-front+m） mod m B. rear-front+1 C. rear-front-1D. rear-front E.以上答案都不对数据结构中，与所使用的计算机无关的是数据的（）A.存储结构 B.物理结构 C.逻辑结构D. 物理结构和存储结构E.以上答案都不对在具有n个结点的单链表中，实现（）的操作，其算法的时间复杂度都是O（n）。A.遍历链表和求链表的第i个结点B.在地址为p的结点之后插入一个结点C.删除开始结点D.删除地址为p的结点的后继结点 E.以上答案都不对某二叉树的前序遍历序列为IJKLMNO，中序遍历序列为JLKINMO，则后序遍历序列为（）A

34、. JLKMNOI B. LKNJOMI C. LKJNOMI D. LKNOJMI E.以上答案都不对有n个结点的无向图的边数最多为（）A. n+1 B. n（n-1）/2 C. n（n+1） D. 2n（n+1） E.以上答案都不对某顺序存储的表格中有90000个元素，已按关键字值额定升序排列，假定对每个元素进行查 找的概率是相同的，且每个元素的关键字的值皆不相同。用顺序查找法查找时，平均比较次 数约为（）A.25000 B .30000 C.45000 D.90000 E .以上答案都不对下列排序算法中，第一趟排序完毕后，其最大或最小元素一定在其最终位置的算法是（）A.归并排序 B.直接

35、插入排序 C.快速排序D. 冒泡排序 E.以上答案都不对关于树和二叉树的有序性，正确的结论是（）A.树和二叉树都是有序的 B.树和二叉树都可能是有序的C.树和二叉树都是无序的D .二叉树是有序的，树可能是有序的，也可能是无序的E. 以上答案都不对在一个图中，所有顶点的度数之和与图的边数的比是（） A. 1:2B. 1:1 C. 2:1D. 4:1 E.以上答案都不对若一组纪录的关键码为（46, 79, 56, 38, 40, 84），则利用快速排序的方法，以第一个纪录 为基准得到的一次划分结果为（）A. 38,40,46,56, 79, 84B.40, 38, 46,79,56, 84C. 4

36、0,38,46,56, 79, 84D.40, 38, 46,84,56, 79E. 以上答案都不对从理论上讲，将数据以（）结构存放，则查找一个数据所用时间不依赖于数据个数n。A.二叉查找树B.链表C.二叉树D.哈希表E.以上答案都不对在非空循环双链表中q所指的结点前插入一个由p所指结点的过程依次为：p-next=q； p-prior=q-prior； q-prior=p；（）；A. q-next=pB. q-prior-next=p C. p-prior-next=pD. p-next-prior=pE.以上答案都不对每个存储结点只含有一个数据元素，存储结点均匀地存放在连续的存储空间，使用函

37、数值对 应结点的存储位置，该存储方式是（）存储方式A.顺序B.链接C.索引D.散列E.以上答案都不对对于单链表形式的队列，队空的条件是（）A. F=R=nilB. F=RC. F尹nil 且 R=nilD. RF=1E. 以上答案都不对对于序列（49,38,65,97,76,13,27,50）按由小到大进行排序，（）是初始步长d=4的希尔排序法第一趟的结果。A. 49,76,65,13,27,50,97,38B. 13,27,38,49,50,65,76,97C. 97,76,65,50,49,38,27,13D. 49,13,27,50,76,38,65,97E. 以上答案都不对树中所有结点

38、的度等于所有结点数加（）。A.0 B.1C .1D.2E .以上答案都不对循环队列用数组A0.m-1存放其元素值，已知其头尾指针分别为front和rear，则当前元 素个数为（ ）。A. （rear-front+m） mod m B . rear-front+1 C . rear-front-1 D. rear-frontE. 以上答案都不对若线性表最常用的运算是查找第i个元素及其前驱的值，则采用（）存储方式节省时间。A.单链表 B-双链表 C.单循环连表D.顺序表E. 以上答案都不对树最适合用来表示（）A.有序数据元素B.无序数据元素C.元素之间无联系的数据D.元素之间有分支层次关系E.以上

39、答案都不对有n个结点的有向完全图的边数为（）A. n*n B. 2nC. n（n-1） D. 2n（n+1）E.以上答案都不对填空：设栈S和队列Q的初始状态为空，元素a、b、c、d、e、f将依次入栈S, 一 个元素出栈后即进入队列。若这6个元素出队列的顺序是b、d、c、f、e、a,则栈S的容量至少应该 是，上述过程才不会出错。已知完全二叉树的第4层（根结点为第1层）总共只有2个结点，则其叶子结点数 是。数据的逻辑结构是从逻辑关系上描述数据，它与数据的无关，是独立于计算机的。对n个元素的序列进行冒泡排序时，最少的比较次数是。已知某二叉树的后序遍历序列是BEDCA,中序遍历序列是BADEC，那么它

40、的前序遍历序列 是0在一个N个单元的顺序栈中，假定以地址低端（下标为0的单元）作为栈底，以top作为栈 顶指针，则向栈中压入一个元素时，tOp指针的变化是：0在一个单链表中，若要删除P所指结点的后继结点，则执行的语句序列0带头结点的单链表head为空的判定条件是： 。在长度为n的顺序表的第i （1 W i W n+1）个位置上插入一个元素，元素的移动次数为 0在长度为n的顺序表的第i （ 1 WiW n）个位置上删除一个元素，元素的移动次数已知一棵完全二叉树中共有768个结点，则该树中共有 个叶子结点。在有序表（12, 24, 36, 48, 60, 72, 84）中二分查找关键字72时所需进

41、行的关键字比较次 数为。写出树（见右图）的先序遍历序列。n个顶点的无向连通图最少有 条边。有一个有序表为1,3,9,12,32,41,45,62,75,77,82,95,100，当二分查找值为9的结点时，经过次比较后查找成功。已知一棵完全二叉树中共有768个结点，则该树中共有 个叶子结点。写出右图所示二叉树按后序遍历的结。写出右图所示二叉树度为1的内部结点的值有向图G用邻接矩阵A1.n,1.n存储，其第i行的所有元素之和等于顶点i的（）。已知完全二叉树的第8层有8个结点，则其叶子结点数是（）有n个顶点的强连通有向图G至少有（）条弧。3个结点可构成（）棵不同形态的树。已知二叉树中叶子数为50,仅

42、有一个孩子的结点数为30,则总结点数是（ ） 在按关键字递增的数组A1.20中，按折半查找方法进行查找时，查找长度为5的元素个数 是（数组A1.10,1.10的每个元素占1个单元，将其按行优先次序存储在起始地址为1000的连续 的内存单元中，则元素A5,6的地址为。两个序列如下：1. L1=25, 57, 48, 37, 92, 86, 12, 332. L2=25, 37, 33, 12, 48, 57, 86, 92用冒泡排序方法分别对序列L1和L2进行排序，交换次数较少的是序列对于一个具有N个结点和E条边的无向图，若采用邻接表表示，则顶点表的大小为（），所有边链表中边结点的总数为（）。链

43、表适用于（）查找。通常程序在调用另一个程序时，都需要使用一个（）来保存被调用程度内分配的局部变量、形式参数的存储空间以及返回地址。前序为abc且后序为cba的二叉树共有（）棵。有n结点的二叉链表中，空指针域有（）个。在单链表中，申请到新结点P，将p指向的结点后插到s所指结点的操作，其一是p-next=s-next，其二是（）。设二维数组A10.20,5.10按行优先存储，每个元素占4个单元，A10,5的地址为160， 则A15,10的地址为（）。已知完全二叉树的高度为8,第7层有10个叶子结点，则二叉树的总结点数至少是（）。 已知二叉树有50个叶子结点，且仅有一个孩子的结点数为30，则总结点数

44、为（）。 从一棵二叉树的前序序列和（）可唯一确定这棵二叉树。设某二叉树的后序遍历为ABKCBPM，则可知该二叉树的根为（）。设有一稠密图G，则G采用（）存储较省空间。分析:使用 二叉链表表示法，画出图示二叉树的存储表示。画出如图所示的树所对应的二叉树。已给无向图如下：要求：写出该图从顶点开始的深度优先和广度优先搜索 序列。设右图为某树的二叉树表示，请画出该树。一棵排序二叉树结构如下，各结点的值从小到大依次为18,请标出各结点的值。已知一个无向图的顶点集为a,b,c,d,e，其邻接矩阵如下所示a0 10 0 1b10 0 10c0 0 0 1 1d0 110 1e10 110（1）根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历，写出相应的遍历序 列。（2）画出该图的图形； 一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来，试求出空格处的 内容，并画出该二叉树。先序序列：BF ICEHG；中序序列：DKFIA一EJC；后序序列： K_FBHJG A已知一组元素为（47, 25, 93, 62, 12, 37, 70，29），试画出按元素排列次序插入生成的一 棵二叉搜索树。设二叉树中每个