21春【兰大网院】数据结构课程作业第三套

admin

【兰州大学网院】-数据结构课程作业第三套
试卷总分:100    得分:100
第1题,程序段s=i=0；do {i=i+1； s=s+i；}while(i<=n)；的时间复杂度为（  ）。
A、O(n)
B、 O(nlog2n)
C、O(n2)
D、O(n3/2)
正确资料:


第2题,具有4个顶点的无向完全图有_____条边
A、6
B、12
C、16
D、20
正确资料:


第3题,一个栈的入栈序列是A、B、C、D、E，五个元素都入栈后，首次出栈的元素是_____
A、A
B、E
C、B
D、D
正确资料:


第4题,函数substr("DATASTRUCTURE"，5，9)的返回值为（  ）。
A、"STRUCTURE"
B、"DATA"
C、"ASTRUCTUR"
D、"DATASTRUCTURE"
正确资料:


资料来源：谋学网（www.mouxue.com）,数组的逻辑结构不同于下列（  ）的逻辑结构。
A、线性表
B、栈
C、队列
D、树
正确资料:


第6题,设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（  ）。
A、R-F
B、F-R
C、(R-F+M)％M
D、(F-R+M)％M
正确资料:


第7题,带头节点的单链表L为空的判定条件是_____
A、L = =null
B、  L->data= =null
C、  L->next= =null
D、  L->next= =data
正确资料:


第8题,栈和队列的共同特点是(      )。
A、只允许在端点处插入和删除元素
B、都是先进后出
C、都是先进先出
D、没有共同点
正确资料:


第9题,线性表的顺序存储结构是一种?的存储结构
A、随机存取
B、顺序存取
C、索引存取
D、散列存取
正确资料:


资料来源：谋学网（www.mouxue.com）,设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（  ）。
A、O(1)
B、 O(log2n)
C、O(0)
D、O(n2)
正确资料:


第11题,平衡二叉树的平衡因子只可能是-1、0、1
√、对
×、错
正确资料:


资料来源：谋学网（www.mouxue.com）,任何有向网的拓扑排序的结果是唯一的
√、对
×、错
正确资料:


第13题,数据的逻辑结构是指各数据元素之间的逻辑关系
√、对
×、错
正确资料:


第14题,先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。（  ）
√、对
×、错
正确资料:


资料来源：谋学网（www.mouxue.com）,一个有n个顶点的有向图的边数e最多为e=n(n-1)
√、对
×、错
正确资料:


第16题,设一组初始记录关键字序列为(45，80，55，40，42，85)，则以第一个记录关键字45为基准而得到一趟快速排序的结果是（  ）。
A、40，42，45，55，80，83
B、42，40，45，80，85，88
C、42，40，45，55，80，85
D、42，40，45，85，55，80
正确资料:


第17题,假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有弧的时间复杂度是(    )
A、O(n)
B、O(e)
C、O(n+e)
D、O(n*e)
正确资料:


第18题,序列278、109、930经过一趟基数排序后结果为
A、930、278、109
B、109、930、278
C、109、278、930
D、278、109、930
正确资料:


第19题,设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（  ）。
A、3
B、4
C、5
D、1
正确资料:


资料来源：谋学网（www.mouxue.com）,在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为  (  )。
A、n
B、 n/2
C、 (n+1)/2
D、 (n-1)/2
正确资料:


第21题,常对数组进行的两种基本操作是
A、建立与删除
B、索引与修改
C、查找与修改
D、查找与索引
正确资料:


第22题,设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（  ）。
A、head==0
B、head->next==0
C、head->next==head
D、 head!=0
正确资料:


第23题,设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂度为（  ）。
A、O(n)
B、O(n2)
C、O(nlog2n)
D、O(1og2n)
正确资料:


第24题,不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。（  ）
√、对
×、错
正确资料:√


资料来源：谋学网（www.mouxue.com）,由树转化成二叉树，其根节点的右子树总是空
√、对
×、错
正确资料:√


第26题,层次遍历初始堆可以得到一个有序的序列。（  ）
√、对
×、错
正确资料:×


第27题,完全二叉树中的叶子结点只可能在最后两层中出现。（  ）
√、对
×、错
正确资料:√


第28题,线性结构只能用顺序存储
√、对
×、错
正确资料:×