资源描述:
《《数据结构作业》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)