数据结构习题(附答案)

1．数据的最小单位是（A）。(A)数据项(B)数据类型(C)数据元素(D)数据变量2．下面关于线性表的叙述错误的是（D）。(A)线性表采用顺序存储必须占用一片连续的存储空间(B)线性表采用链式存储不必占用一片连续的存储空间(C)线性表采用链式存储便于插入和删除操作的实现(D)线性表采用顺序存储便于插入和删除操作的实现3．设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（C）。(A)R-F(B)F-R(C)(R-F+M)％M(D)(F-R+M)％M4．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（A）。(A)BADC(B)BCDA(C)CDAB(D)CBDA5．设某棵二叉树中有2000个结点，则该二叉树的最小高度为（C）。(A)9(B)10(C)11(D)126．下面程序的时间复杂为（B）for（i=1，s=0；i=n；i++）{t=1；for(j=1；j=i；j++)t=t*j；s=s+t；}(A)O(n)(B)O(n2)(C)O(n3)(D)O(n4)7．设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（C）。(A)q=p-next；p-data=q-data；p-next=q-next；free(q)；(B)q=p-next；q-data=p-data；p-next=q-next；free(q)；(C)q=p-next；p-next=q-next；free(q)；(D)q=p-next；p-data=q-data；free(q)；8．设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（C）。(A)O(n)(B)O(nlog2n)(C)O(1)(D)O(n2)9．设一棵二叉树的深度为k，则该二叉树中最多有（D）个结点。(A)2k-1(B)2k(C)2k-1(D)2k-110．设用链表作为栈的存储结构则退栈操作（B）。(A)必须判别栈是否为满(B)必须判别栈是否为空(C)判别栈元素的类型(D)对栈不作任何判别11．函数substr(“DATASTRUCTURE”，5，9)的返回值为（A）。(A)“STRUCTURE”(B)“DATA”(C)“ASTRUCTUR”(D)“DATASTRUCTURE”12．设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（C）。(A)N0=N1+1(B)N0=Nl+N2(C)N0=N2+1(D)N0=2N1+l13．设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（B）。(A)空或只有一个结点(B)高度等于其结点数(C)任一结点无左孩子(D)任一结点无右孩子14.深度为k的完全二叉树中最少有（C）个结点。(A)2k-1-1(B)2k-1(C)2k-1+1(D)2k-115.设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（C）。(A)front-next=s；front=s；(B)s-next=rear；rear=s；(C)rear-next=s；rear=s；(D)s-next=front；front=s；1.设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第i个结点的双亲结点编号为____i/2________，右孩子结点的编号为_____2i+1______。2.设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF，则该二叉树的前序遍历序列为_ABDECF____，中序遍历序列为___DBEAFC________，后序遍历序列为___DEBFCA___。3.6．设F和R分别表示顺序循环队列的头指针和尾指针，则判断该循环队列为空的条件为_____F=R________________。4.对顺序存储的线性表，设其长度为n，假定在任何位置上插入操作都是等概率的，则插入一个元素平均需要移动元素的个数是（n/2）,删除一个元素平均需要移动元素的个数是（(n-1)/2）5.已知二维数组A[3~20][5~20]中每个元素占4个单元，在按行优先方式将其存储到起始地址为1000的连续存储区域时，A[5][9]的地址是（1152）。6.设有一个空栈，栈顶指针为2001H(十六进制)，现有输入序列为1，2，3，4，5，经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，栈顶指针值是（200D）H。设栈为顺序栈，每个元素占4个字节。7.INDEX（‘DATASTRUCTURE’，‘TAST’）=（3）。8.设广义表L=（(a)，((b),c),(((d)))），则L的深度为（4），长度为（3）1.已知一棵树边的集合为{I,M,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的操作序列（设双向链表中结点的两个指针域分别为llink和rlink）。q-llink=p;q-rlink=p-rlink;p-rlink-llink=q;p-rlink=q;4.一棵二叉树的结点数据采用顺序存储结构，存储于数组T中，如图所示，请画出该二叉树并画出该二叉树的链接表示形式。123456789101112131415161718192021eafdgcjihb5、画出如下图所示的二叉树的顺序存储结构图。1234567891011ABCDEJK6.已知二叉树的前序遍历序列是AEFBGCDHIKJ，中序遍历序列是EFAGBCHKIJD，画出此二叉树，写出后序遍历序列，并画出它的后序线索二叉树。AEBFGCDHFKJNULL