天大18秋《数据结构》在线作业12参考
《数据结构》在线作业一1.[单选题]数据结构是一门研究非数值计算的程序设计问题中,数据元素的（）、数据信息在计算机中的存储结构以及一组相关的运算等的课程。 (满分:)
A. 操作对象
B. 计算方法
C. 逻辑结构
D. 数据映象
正确答案:——C——
2.[单选题]设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（）。 (满分:)
A. O(n)
B. O(nlog2n)
C. O(1)
D. O(n2)
正确答案:——C——
3.[单选题]设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（）趟的分配和回收才能使得初始关键字序列变成有序序列。 (满分:)
A. 3
B. 4
C. 5
D. 8
正确答案:——A——
4.[单选题]如果只想得到1024个元素组成的序列中第5个最小元素之前的部分排序的序列，用（）方法最快。 (满分:)
A. 起泡排序
B. 快速排序
C. 简单选择排序
D. 堆排序
正确答案:————
5.[单选题]下面程序的时间复杂为（）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)
正确答案:————
6.[单选题]在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（）。 (满分:)
A. s->next=p;p->next=s;
B. s->next=p->next;p->next=s;
C. s->next=p->next;p=s;
D. p->next=s;s->next=p;
正确答案:————
7.[单选题]已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（）。 (满分:)
A. acbed
B. decab
C. deabc
D. cedba
正确答案:————
8.[单选题]二维数组A中，每个元素的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，存放该数组至少需要的字节数是（）。 (满分:)
A. 80
B. 100
C. 240
D. 270
正确答案:————
9.[单选题]若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）。 (满分:)
A. i
B. n=i
C. n-i+1
D. 不确定
正确答案:————
10.[单选题]判定一个顺序栈ST（最多元素为m0）为栈满的条件是（）。 (满分:)
A. top！=0
B. top==0
C. top！=m0
D. top==m0-1
正确答案:————
q 761296021
11.[单选题]在二叉排序树中插入一个结点的时间复杂度为（）。 (满分:)
A. O(1)
B. O(n)
C. O(log2n)
D. O(n2)
正确答案:————
12.[单选题]设串s1='ABCDEFG'，s2='PQRST'，函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是（）。 (满分:)
A. BCDEF
B. BCDEFG
C. BCPQRST
D. BCDEFEF
正确答案:————
13.[单选题]在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。 (满分:)
A. 正确
B. 错误
正确答案:————
14.[单选题]非空的循环单链表head的尾结点（由p所指向）满足（）。 (满分:)
A. p->next==NULL
B. p==NULL
C. p->next==head
D. p==head
正确答案:————
15.[单选题]某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是（）。 (满分:)
A. bdgcefha
B. gdbecfha
C. bdgaechf
D. gdbehfca
正确答案:————
16.[单选题]带头结点的单链表head为空的判定条件是（）。 (满分:)
A. head==NULL
B. head->next==NULL
C. head->next==head
D. head!=NULL
正确答案:————
17.[单选题]进行折半搜索的表必须是顺序存储的有序表。 (满分:)
A. 正确
B. 错误
正确答案:————
18.[单选题]设串的长度为n，则它的子串个数为（）。 (满分:)
A. n
B. n(n+1)
C. n(n+1)/2
D. n(n+1)/2+1
正确答案:————
19.[单选题]常对数组进行的两种基本操作是（）。 (满分:)
A. 建立与删除
B. 索引和修改
C. 对数据元素的存取和修改
D. 查找与索引
正确答案:————
20.[单选题]设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（）。 (满分:)
A. n
B. e
C. 2n
D. 2e
正确答案:————
21.[单选题]向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行（）。(不带空的头结点) (满分:)
A. HS—＞next=s;
B. s—＞next=HS—＞next;HS—＞next=s;
C. s—＞next=HS;HS=s;
D. s—＞next=HS;HS=HS—＞next;
正确答案:————
22.[单选题]深度为5的二叉树至多有（）个结点。 (满分:)
A. 16
B. 32
C. 31
D. 10
正确答案:————
23.[单选题]设有6个结点的无向图，该图至少应有()条边才能确保是一个连通图。 (满分:)
A. 5
B. 6
C. 7
D. 8
正确答案:————
24.[单选题]设顺序循环队列Q的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（）。 (满分:)
A. R-F
B. F-R
C. (R-F+M)％M
D. (F-R+M)％M
正确答案:————
25.[单选题]在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行（）。 (满分:)
A. s->next=p->next;p->next=s;
B. p->next=s->next;s->next=p;
C. q->next=s;s->next=p;
D. p->next=s;s->next=q;
正确答案:————
26.[单选题]设无向图G中有n个顶点，则该无向图的最小生成树上有（）条边。 (满分:)
A. n
B. n-1
C. 2n
D. 2n-1
正确答案:————
27.[单选题]链式存储在插入和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序。 (满分:)
A. 正确
B. 错误
正确答案:————
28.[单选题]对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K%9作为散列函数，则散列地址为1的元素有（）个. (满分:)
A. 1
B. 2
C. 3
D. 4
正确答案:————
29.[单选题]设某棵二叉树中有2000个结点，则该二叉树的最小高度为（）。 (满分:)
A. 9
B. 10
C. 11
D. 12
正确答案:————
30.[单选题]设某完全无向图中有n个顶点，则该完全无向图中有（）条边。 (满分:)
A. n(n-1)/2
B. n(n-1)
C. n2
D. n2-1
正确答案:————
31.[单选题]在以下的叙述中，正确的是（）。 (满分:)
A. 线性表的顺序存储结构优于链表存储结构
B. 线性表的顺序存储结构适用于频繁插入/删除数据元素的情况
C. 线性表的链表存储结构适用于频繁插入/删除数据元素的情况
D. 线性表的链表存储结构优于顺序存储结构
正确答案:————
32.[单选题]在线索化二叉树中，t所指结点没有左子树的充要条件是（）。 (满分:)
A. t—＞left=NULL
B. t—＞ltag=1
C. t—＞ltag=1且t—＞left=NULL
D. 以上都不对
正确答案:————
33.[单选题]二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按行存放时，数组元素A的起始地址为（）。 (满分:)
A. SA+141
B. SA+144
C. SA+222
D. SA+225
正确答案:————
34.[单选题]从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行（）。(不带空的头结点) (满分:)
A. x=HS;HS=HS＞next;
B. x=HS＞data;
C. HS=HS＞next;x=HS＞data;
D. x=HS＞data;HS=HS＞next;
正确答案:————
35.[单选题]设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（）。 (满分:)
A. O(1)
B. O(log2n)
C. O(n4)
D. O(n2)
正确答案:————
36.[单选题]按照二叉树的定义，具有3个结点的不同形状的二叉树有（）种。 (满分:)
A. 3
B. 4
C. 5
D. 6
正确答案:————
37.[单选题]具有五层结点的二叉平衡树至少有（）个结点。 (满分:)
A. 10
B. 12
C. 15
D. 17
正确答案:————
38.[单选题]串是一中特殊的线性表，其特殊性体现在（）。 (满分:)
A. 可以顺序存储
B. 数据元素是一个字符
C. 可以链接存储
D. 数据元素可以是多个字符
正确答案:————
39.[单选题]下面关于线性表的叙述错误的是（）。 (满分:)
A. 线性表采用顺序存储必须占用一片连续的存储空间
B. 线性表采用链式存储不必占用一片连续的存储空间
C. 线性表采用链式存储便于插入和删除操作的实现
D. 线性表采用顺序存储便于插入和删除操作的实现
正确答案:————
40.[单选题]数据结构DS(DataStruct)可以被形式地定义为DS=（D，R），其中D是（）有限集合，R是D上的关系有限集合。 (满分:)
A. 算法
B. 数据元素
C. 数据操作
D. 数据对象
正确答案:————
《数据结构》在线作业二
一、单选题：
1.[单选题]对于查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于（）。 (满分:)
A. 静态查找表
B. 动态查找表
C. 静态查找表与动态查找表
D. 两种表都不适合
正确答案:——B——
2.[单选题]设有向无环图G中的有向边集合E={<1，2>，<2，3>，<3，4>，<1，4>}，则下列属于该有向图G的一种拓扑排序序列的是（）。 (满分:)
A. 1，2，3，4
B. 2，3，4，1
C. 1，4，2，3
D. 1，2，4，3
正确答案:——A——
3.[单选题]（）二叉排序树可以得到一个从小到大的有序序列。 (满分:)
A. 先序遍历
B. 中序遍历
C. 后序遍历
D. 层次遍历
正确答案:——B——
4.[单选题]二叉树是非线性数据结构，所以（）。 (满分:)
A. 它不能用顺序存储结构存储
B. 它不能用链式存储结构存储
C. 顺序存储结构和链式存储结构都能存储
D. 顺序存储结构和链式存储结构都不能使用
正确答案:————
5.[单选题]设完全无向图中有n个顶点，则该完全无向图中有（）条边。 (满分:)
A. n(n-1)/2
B. n(n-1)
C. n(n+1)/2
D. (n-1)/2
正确答案:————
6.[单选题]在二叉排序树中插入一个关键字值的平均时间复杂度为（）。 (满分:)
A. O(n)
B. O(1og2n)
C. O(nlog2n)
D. O(n2)
正确答案:————
7.[单选题]对于静态表的顺序查找法，若在表头设置岗哨，则正确的查找方式为（）。 (满分:)
A. 从第0个元素往后查找该数据元素
B. 从第1个元素往后查找该数据元素
C. 从第n个元素往开始前查找该数据元素
D. 与查找顺序无关
正确答案:————
8.[单选题]设一组权值集合W=(15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为（）。 (满分:)
A. 129
B. 219
C. 189
D. 229
正确答案:————
9.[单选题]采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为（）。 (满分:)
A. O（n2）
B. O(nlog2n)
C. O(n)
D. O(log2n)
正确答案:————
10.[单选题]设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动（）个元素。 (满分:)
A. n-i
B. n+l-i
C. n-1-i
D. i
正确答案:————
11.[单选题]排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（）。 (满分:)
A. 希尔排序
B. 归并排序
C. 插入排序
D. 选择排序
正确答案:————
12.[单选题]设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、T2和T3的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为（）。 (满分:)
A. N1-1
B. N2-1
C. N2+N3
D. N1+N3
正确答案:————
13.[单选题]利用直接插入排序法的思想建立一个有序线性表的时间复杂度为（）。 (满分:)
A. O(n)
B. O(nlog2n)
C. O(n2)
D. O(1og2n)
正确答案:————
14.[单选题]顺序查找法适合于存储结构为（）的线性表。 (满分:)
A. 散列存储
B. 顺序存储或链接存储
C. 压缩存储
D. 索引存储
正确答案:————
15.[单选题]设输入序列1、2、3、?、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是（）。 (满分:)
A. n-i
B. n-1-i
C. n+l-i
D. 不能确定
正确答案:————
16.[单选题]用某种排序方法对线性表（25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变化情况如下：⑴25，84，21，47，15，27，68，35，20；⑵20，15，21，25，47，27，68，35，84；⑶15，20，21，25，35，27，47，68，84；⑷15，20，21，25，27，35，47，68，84。则所采用的排序方法是（）。 (满分:)
A. 选择排序
B. 希尔排序
C. 归并排序
D. 快速排序
正确答案:————
17.[单选题]采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（）. (满分:)
A. n
B. n/2
C. (n+1)/2
D. (n-1)/2
正确答案:————
18.[单选题]下列程序段的时间复杂度为（）。for(i=0；i<m；i++)for(j=0；j<t；j++)c=0；for(i=0；i<m；i++)for(j=0；j<t；j++)for(k=0；k<n；k++)c=c+a*b； (满分:)
A. O(m*n*t)
B. O(m+n+t)
C. O(m+n*t)
D. O(m*t+n)
正确答案:————
19.[单选题]对线性表进行二分查找时，要求线性表必须（）。 (满分:)
A. 以顺序方式存储
B. 以链接方式存储
C. 以顺序方式存储，且结点按关键字有序排序
D. 以链接方式存储，且结点按关键字有序排序
正确答案:————
20.[单选题]二叉排序树中左子树上所有结点的值均（）根结点的值。 (满分:)
A. <
B. >
C. =
D. !=
正确答案:————
21.[单选题]设无向图G中的边的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为（）。 (满分:)
A. aedfcb
B. acfebd
C. aebcfd
D. aedfbc
正确答案:————
22.[单选题]快速排序方法在（）情况下最不利于发挥其长处。 (满分:)
A. 要排序的数据量太大
B. 要排序的数据中含有多个相同值
C. 要排序的数据已基本有序
D. 要排序的数据个数为奇数
正确答案:————
23.[单选题]一个有n个顶点的无向图最多有（）条边。 (满分:)
A. n
B. n(n-1)
C. n(n-1)/2
D. 2n
正确答案:————
24.[单选题]设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法查找值为24的元素需要经过（）次比较。 (满分:)
A. 1
B. 2
C. 3
D. 4
正确答案:————
25.[单选题]设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到HASH表中需要做（）次线性探测。 (满分:)
A. n2
B. n(n+1)
C. n(n+1)/2
D. n(n-1)/2
正确答案:————
26.[单选题]采用邻接表存储的图的宽度优先遍历算法类似于二叉树的（）。 (满分:)
A. 先序遍历
B. 中序遍历
C. 后序遍历
D. 按层遍历
正确答案:————
27.[单选题]树最适合用来表示（）。 (满分:)
A. 有序数据元素
B. 无序数据元素
C. 元素之间具有分支层次关系的数据
D. 元素之间无联系的数据
正确答案:————
28.[单选题]树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵数对应的二叉树。结论（）是正确的。 (满分:)
A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同
B. 树的后根遍历序列与其对应的二叉树的后序遍历序列相同
C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同
D. 以上都不对
正确答案:————
29.[单选题]对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有邻接表中的接点总数是（）。 (满分:)
A. e/2
B. e
C. 2e
D. n+e
正确答案:————
30.[单选题]设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为（）。 (满分:)
A. p->right=s；s->left=p；p->right->left=s；s->right=p->right；
B. s->left=p；s->right=p->right；p->right=s；p->right->left=s；
C. p->right=s；p->right->left=s；s->left=p；s->right=p->right；
D. s->left=p；s->right=p->right；p->right->left=s；p->right=s；
正确答案:————
31.[单选题]判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用（）。 (满分:)
A. 求关键路径的方法
B. 求最短路径的Dijkstra方法
C. 宽度优先遍历算法
D. 深度优先遍历算法
正确答案:————
32.[单选题]把一棵树转换为二叉树后，这棵二叉树的形态是（）。 (满分:)
A. 唯一的
B. 有多种
C. 有多种，但根结点都没有左孩子
D. 有多种，但根结点都没有右孩子
正确答案:————
33.[单选题]关键路径是事件结点网络中（）。 (满分:)
A. 从源点到汇点的最长路径
B. 从源点到汇点的最短路径
C. 最长的回路
D. 最短的回路
正确答案:————
34.[单选题]有8个结点的无向连通图最少有（）条边。 (满分:)
A. 5
B. 6
C. 7
D. 8
正确答案:————
35.[单选题]在一个图中，所有顶点的度数之和等于所有边数的（）倍。 (满分:)
A. 1/2
B. 1
C. 2
D. 4
正确答案:————
36.[单选题]采用线性探测法解决冲突问题，所产生的一系列后继散列地址（）。 (满分:)
A. 必须大于等于原散列地址
B. 必须小于等于原散列地址
C. 可以大于或小于但不能等于原散列地址
D. 地址大小没有具体限制
正确答案:————
37.[单选题]散列表的平均查找长度（）。 (满分:)
A. 与处理冲突方法有关而与表的长度无关
B. 与处理冲突方法无关而与表的长度有关
C. 与处理冲突方法有关而与表的长度有关
D. 与处理冲突方法无关而与表的长度无关
正确答案:————
38.[单选题]在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是（）。 (满分:)
A. 希尔排序
B. 起泡排序
C. 插入排序
D. 选择排序
正确答案:————
39.[单选题]一个有n个顶点的无向连通图，它所包含的连通分量个数为（）。 (满分:)
A. 0
B. 1
C. n
D. n+1
正确答案:————
40.[单选题]设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是（）。 (满分:)
A. F，H，C，D，P，A，M，Q，R，S，Y，X
B. P，A，C，S，Q，D，F，X，R，H，M，Y
C. A，D，C，R，F，Q，M，S，Y，P，H，X
D. H，C，Q，P，A，M，S，R，D，F，X，Y
正确答案:————
附件是答案，核对题目下载，转载注明无忧答案网
页:
[1]