数据结构作业(答案).docx
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 .设某棵二叉树的中序遍历序列为ABCD,前序遍历序列为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；j<=i;j+)t=t*j；s=s+t;)（八）0(n)(B)0(n2)(C)0(n3)(D)0(n,)7 .设指针变量P指向单链表中结点A,若删除单链表中结点A,则需要修改指针的操作序列为(C)。(A) (B) (C) (D)q=p->next;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(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)“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表示链式队列的队尾指针,指针变量S指向将要入队列的结点X,则入队列的操作序列为(C)。（八）front->next=s;front=s;(B)s->next=rear;rear=s;(C)rear->next=s;i'ear=s?(D)s->next=front;front=s;1 .设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第i个结点的双亲结点编号为i/2右孩子结点的编号为2i+l2 .设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF,则该二叉树的前序遍历序列为_ABDECF,中序遍历序列为DBEAFC,后序遍历序列为DEBFCA。3 .6.设F和R分别表示顺序循环队列的头指针和尾指针，则判断该循环队列为空的条件为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 .INDEX(iDATASTRUCTUREj,'TAST')=(3)。8 .设广义表L=(a),(b),c),(d),则L的深度为(4),长度为(3)1 .已知一棵树边的集合为<LM>,<I,N>,<E,I>,<B,E>,<B,D>,<A,B>,<G,J>,<G,K>,<C,G>,<C,F>,<A,C>,请画出这棵树，并回答下列问题：(1)哪个是根结点？(2)哪些是叶子结点？(3)哪个是结点G的双亲？(4)哪些是结点G的祖先？(5)哪些是结点G的孩子？(6)哪些是结点E的子孙？(7)那些是结点E的子孙？(8)结点B和N的层次号分别是什么？(9)树的深度是多少？(10)以结点C为根的子树的深度是多少？2、写出如图所示的二叉树的先序、中序、后序排列。(1)先序：123456879101112131514(2)中序：348675211091115141312(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,画出此二叉树，写出后序遍历序列，并画出它的后序线索二叉树。
