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

admin

【兰州大学网院】-数据结构课程作业第一套
试卷总分:100    得分:100
第1题,单链表的结点包含____和_____
A、结点域，符号域
B、数据域，符号域
C、结点域，指针域
D、 数据域，指针域
正确资料:


第2题,设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（  ）。
A、O(log2n)
B、O(1)
C、O(n2)
D、O(n)
正确资料:


第3题,设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（  ）。
A、6
B、4
C、3
D、2
正确资料:


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


资料来源：谋学网（www.mouxue.com）,设s ="I  AM  A  STUDENT",则字符串的长度 Length(s) ＝？
A、11
B、12
C、14
D、15
正确资料:


第6题,由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（  ）
A、24
B、 71
C、48
D、53
正确资料:


第7题,将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（  ）
A、O(1)
B、O(n)
C、O(m)     
D、O(m+n)
正确资料:


第8题,下面程序的时间复杂为（  ）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)
正确资料:


第9题,设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为（  ）。
A、2i+1
B、2i
C、i/2
D、2i-1
正确资料:


资料来源：谋学网（www.mouxue.com）,函数substr("DATASTRUCTURE"，5，9)的返回值为（  ）。
A、"STRUCTURE"
B、"DATA"
C、"ASTRUCTUR"
D、"DATASTRUCTURE"
正确资料:


第11题,已知一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。（  ）
√、对
×、错
正确资料:


资料来源：谋学网（www.mouxue.com）,一个深度为5的二叉树至多有31个节点
√、对
×、错
正确资料:


第13题,如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。（  ）
√、对
×、错
正确资料:


第14题,直接插入排序是一种最简单的排序方法
√、对
×、错
正确资料:


资料来源：谋学网（www.mouxue.com）,栈是后进先出的线性表
√、对
×、错
正确资料:


第16题,设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（  ）。
A、n
B、e
C、2n
D、2e
正确资料:


第17题,设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（  ）个空指针域。
A、2m-1
B、2m
C、2m+1
D、4m
正确资料:


第18题,设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。
A、688
B、678
C、692
D、696
正确资料:


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


资料来源：谋学网（www.mouxue.com）,将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（  ）。
A、100
B、40
C、55
D、80
正确资料:


第21题,广义表（（a）,a）的表尾是______
A、a
B、b
C、(a)
D、((a))
正确资料:


第22题,链式队列Q为空的判定条件
A、Q.front==Q.rear
B、Q.front==Q
C、Q ==Q.rear
D、没有正确资料
正确资料:


第23题,设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为(  )。
A、10，15，14，18，20，36，40，21
B、10，15，14，18，20，40，36，21
C、 10，15，14，20，18，40，36，2l
D、 15，10，14，18，20，36，40，21
正确资料:


第24题,由两个栈共享一个向量空间的好处是：（   ）
A、减少存取时间，降低下溢发生的机率
B、节省存储空间，降低上溢发生的机率
C、减少存取时间，降低上溢发生的机率
D、节省存储空间，降低下溢发生的机率
正确资料:


资料来源：谋学网（www.mouxue.com）,图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶点是否被访问过。（  ）
√、对
×、错
正确资料:√


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


第27题,栈是限定在表尾进行插入或删除操作的线性表
√、对
×、错
正确资料:√


第28题,带权无向图的最小生成树是唯一的。（  ）
√、对
×、错
正确资料:×


第29题,数据元素是数据的最小单位
√、对
×、错
正确资料:×