manbetx网页版题目解析

2019年05月16日 浏览量:193

题目1:请判断下面程序的时间复杂度(D)

1.d=0;

2.for(i=1;i

    3. for(j=1;j

     4. s+=i*j;

A.O(0) B.O(n)

C.O(2n) D.O(n2)

问题解析:算法中基本操作重复执行的次数是问题规模n的某个函数f(n),算法的时间量度记作 T(n)=O(f(n))。

上面程序中有两个for循环,两个N*N矩阵,所以自然时间复杂度也就是D。


题目2.假设某个带头结点的单链表的头指针为head,则判定该表为空表的条件是(B)

A.head==NULL  B.head->next==NULL

C.head!=NULL  D.head->next==head

问题解析:线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。因此,为了表示每个数据元素a;与其直接后继数据元素a+1之间的逻辑关系,对数据元素a;来说,除了存储其本身的信息之外还需存储一个指示其直接后继的信息(即直接后继的存储位置)。这两部分信息组成数据元素a;的存储映像,称为结点(node)。它包括两个域:其中存储数据元素信息的域称为数据域;存储直接后继存储位置的域称为指针域。指针域中存储的信息称做指针或链。

整个链表的存取必须从头指针开始进行,头指针指示链表中第一个结点(即第一个数据元素的存储映像)的存储位置。同时,由于最后一个数据元素没有直接后继,则线性链表中最后一个结点的指针为“空”(NULL)。

所以看上题目,头结点为head,所以只需要判断head的下一个节点是否为空,就能判断出该表是否为空,所以答案为B。


3.栈是一种操作受限的线性结构,其操作的主要特征是(B)

A.先进先出 B.后进先出 C.进优于出 D.出优于进

题目解析:栈( stack)是限定仅在表尾进行插入或删除操作的线性表。因此,对栈来说,表尾端有其特殊含义,称为栈顶(top),相应地,表头端称为栈底(bottom)。不含元素的空表称为空栈。栈的修改是按后进先出的原则进行的。所以答案为B。

评论区:

昵称:
内容:
验证码: 1350