数据结构作业(答案).docx

《数据结构作业(答案).docx》由会员分享，可在线阅读，更多相关《数据结构作业(答案).docx（4页珍藏版）》请在优知文库上搜索。

1、1 .数据的最小单位是(A)。（八）数据项(B)数据类型(C)数据元素(D)数据变量2 .下面关于线性表的叙述错误的是(D)。（八）线性表采用顺序存储必须占用一片连续的存储空间(B)线性表采用链式存储不必占用一片连续的存储空间(C)线性表采用链式存储便于插入和删除操作的实现(D)线性表采用顺序存储便于插入和删除操作的实现3 .设顺序循环队列Q0：MT的头指针和尾指针分别为F和R,头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为(C)。(A) R-F(B)F-R(C)(R-F+M)%M(D)(F-R+M)%M4 .设某棵二叉树的中序遍历序列为AB

2、CD,前序遍历序列为CABD,则后序遍历该二叉树得到序列为(A)。（八）BADC(B)BCDA(C)CDAB(D)CBDA5 .设某棵二叉树中有2000个结点，则该二叉树的最小高度为(C)0（八）9(B)10(C)11(D)126 .下面程序的时间复杂为(B)for(i=l,s=0；i=n；i+)t=l;for(j=l；jnext;q=p-next; q=p-next; q=p-next;p-data=q-data; q-data=p-data; p-ncxt=q-next ； p-data=q-data;p-next=q-next; free(q)； p-next=q-next; free(

3、q)； free(q)；free (q)；8 .设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为(C)。（八）0(n)(B)0(nlog2n)(C)0(1)(D)0(n2)9 .设一棵二叉树的深度为k,则该二叉树中最多有(D)个结点。（八）2k-1(B)2k(C)2k1(D)2k-l10 .设用链表作为栈的存储结构则退栈操作(B)。（八）必须判别栈是否为满(B)必须判别栈是否为空(0判别栈元素的类型(D)对栈不作任何判别n.函数SUbStr(Datastructure，5,9)的返回值为(A)。(B) “DATA”（八）“STRUCTURE”(O“Astructur”(D)“

4、Datastructure”12 .设某二叉树中度数为0的结点数为Nft,度数为1的结点数为N1,度数为2的结点数为N2,则下列等式成立的是(C)。（八）N0=N1+l(B)N0=Ni+N2(C)No=N2+1(D)N0=2N1+l13 .设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是(B)（八）空或只有一个结点(B)高度等于其结点数(0任一结点无左孩子(D)任一结点无右孩子14 .深度为k的完全二叉树中最少有(B)个结点。(D) 2k-l（八）2kl-l(B)2k,(C)2k1+l15 .设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针

5、,指针变量S指向将要入队列的结点X,则入队列的操作序列为(C)。（八）front-next=s;front=s;(B)s-next=rear;rear=s;(C)rear-next=s;iear=s?(D)s-next=front;front=s;1 .设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第i个结点的双亲结点编号为i/2右孩子结点的编号为2i+l2 .设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF,则该二叉树的前序遍历序列为_ABDECF,中序遍历序列为DBEAFC,后序遍历序列为DEBFCA。3 .6.设F和R分别表示顺序循环队列的头指针和尾

6、指针，则判断该循环队列为空的条件为F=R04 .对顺序存储的线性表，设其长度为n,假定在任何位置上插入操作都是等概率的，则插入一个元素平均需要移动元素的个数是(n/2),删除一个元素平均需要移动元素的个数是(nT)/2)5 .已知二维数组A320520中每个元素占4个单元，在按行优先方式将其存储到起始地址为100o的连续存储区域时，A59的地址是(1152)。6 .设有一个空栈，栈顶指针为2001H(十六进制)，现有输入序列为1,2,3,4,5,经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，栈顶指针值是(200D)H。设栈为顺序栈，每个元素占4个字节。7 .INDE

7、X(iDATASTRUCTUREj,TAST)=(3)。8 .设广义表L=(a),(b),c),(d),则L的深度为(4),长度为(3)1 .已知一棵树边的集合为,请画出这棵树，并回答下列问题：(1)哪个是根结点？(2)哪些是叶子结点？(3)哪个是结点G的双亲？(4)哪些是结点G的祖先？(5)哪些是结点G的孩子？(6)哪些是结点E的子孙？(7)那些是结点E的子孙？(8)结点B和N的层次号分别是什么？(9)树的深度是多少？(10)以结点C为根的子树的深度是多少？2、写出如图所示的二叉树的先序、中序、后序排列。(1)先序：123456879101112131514(2)中序：34867521109

8、1115141312(3)后序：8765432101514131211913.设指针变量P指向双向链表中结点A,指针变量q指向被插入结点B,要求给出在结点A的后面插入结点B的操作序列(设双向链表中结点的两个指针域分别为Ilink和rlink)0q-llink=p;q-rlink=p-rlink;p-rlink-llink=q;p-rlink=q;4.一棵二叉树的结点数据采用顺序存储结构，存储于数组T中，如图所示，请画出该二叉树并画出该二叉树的链接表示形式。12345678910Il12131415161718192021CafdgCjihb5、画出如下图所示的二叉树的顺序存储结构图。6.已知二叉树的前序遍历序列是AEFBGCDHIKJ,中序遍历序列是EFAGBeHKlJD,画出此二叉树，写出后序遍历序列，并画出它的后序线索二叉树。