资源描述：
《《数据结构作业》word版》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、作业二作业二一、单项选择题1.给定有n个元素的向量，建立一个有序单链表的时间复杂度是（C ）。 A.O(1) B.O(n) C.O(n2)D.O(nlog2n)2.带表头的双向循环链表的空表满足（B ）。 A.first＝NULL; B.first->rLink==first C.first->lLink==NULLD.first->rLink==NULL3.栈的插入和删除操作在(A )进行。 A.栈顶 B.栈底 C.任意位置 D.指定位置4.在一个顺序存储的循环队列中，队头指针指向队头元素的( A
2、 )位置。 A.前一个 B.后一个 C.当前 D.后面5.假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断队空的条件为( D )。 A.front+1==rearB.rear+1==front C.front==0D.front==rear6.设链式栈中结点的结构为（data,link），且top是指向栈顶的指针。若想摘除链式栈的栈顶结点，并将被摘除结点的值保存到x中，则应执行( A )操作。 A.x=top->data;top=top->link; B.top=t
3、op->link;x=top->data; C.x=top; top=top->link; D.x=top->data;7.为增加内存空间的利用率和减少溢出的可能性,由两个栈共享一块连续的内存空间时,应将两栈的( D )分别设在这块内存空间的两端。 A.长度 B.深度 C.栈顶 D. 栈底8.在系统实现递归调用时需利用递归工作记录保存（C ），当递归调用程序执行结束时通过它将控制转到上层调用程序。 A.调用地址 B.递归入口 C.返回地址 D.递归出口9.如果一个递归函数过
4、程中只有一个递归语句，而且它是过程体的最后语句，则这种递归属于（ D ），它很容易被改写为非递归过程。 A.单向递归 B.回溯递归 C.间接递归 D.尾递归10.设有一个广义表A(a)，其表尾为（C ）。 A．a B．(()) C．（） D．(a)11.对于一组广义表A(),B(a,b),C(c,(e,f,g)),D(B,A,C),E(B,D)，其中的E是（D ）。 A.线性表 B.纯表 C.递归表 D.再入表12.在一棵树中，( C )没有前驱结点。 A.树枝结点
5、 B.叶子结点 C.树根结点 D.空结点13.在一棵具有n个结点的二叉树的第i层上(假定根结点为第0层，i大于等于0而小于等于树的高度)，最多具有( A )个结点。 A.2i B.2i+1 C.2i-1 D.2n二、填空题1.链表与顺序表、索引表、散列表等都是数据逻辑结构的（存储）表示。2.队列是一种限定在表的一端插入，在另一端删除的线性表，它又被称为（先进先出）表。3.向一个顺序栈插入一个元素时，首先使（栈顶指针）后移一个位置，然后把待插入元素写入到这个位置上。4.向一个循环队列中插入元素时，需要首先移动（
6、队尾）指针，然后再向所指位置写入新元素。5.在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列至多有（1）个结点。6.递归工作栈起到两个作用，其一是将递归调用时的实际参数和返回地址传递给下一层递归；其二是保存本层的形式参数和（局部变量）。7.非空广义表的除第一个元素外其他元素组成的表称为广义表的（表尾）。8.广义表的深度定义为广义表括号的（重数）。9.一棵树的广义表表示为a(b(c,d(e,f),g(h)),i(j,k(x,y)))，结点f的层数为（3）。假定树根结点的层数为0。10.在一棵三叉树中，度为3的结点数有2个，度为2的
7、结点数有1个，度为1的结点数为2个，那么度为0的结点数有（6）个。11．一棵二叉树中，假定双分支结点数为5个，单分支结点数为6个，则叶子结点数为（6）个。12.在一棵高度为h的理想平衡二叉树中，最多含有（2h+1-1）个结点。假定树根结点的高度为0。三、判断题（对/错）1．在用单链表表示的链式队列Q中，队头指针为Q->front，队尾指针为Q->rear，则队空条件为Q->front==Q->rear。错2递归调用算法与相同功能的非递归算法相比，主要问题在于重复计算太多，而且调用本身需要分配额外的空间和传递数据和控制，所以时间与空间开销通常
8、都比较大。对3将f=1+1/2+1/3+…+1/n转化为递归函数时，递归部分为f(n)=f(n-1)+1/n，递归结束条件为f(1)=1。对4.一个广义表((a),((b),c)
