2022年数据结构第100次模拟试卷 - 在线考试测评模板

:1、请在进入答题前，确保设备性能和系统条件符合线上考试要求2、做题中请勿使用F功能键或查看源代码，如使用系统会记录下来3、诚信考试，请勿上网搜索答案，与其他考生交流，求助外援等4、做题中途遇到问题被退出，在有效期内仍可进入再次进行答题

Q1:下面程序的时间复杂为（）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)

Q2:循环单链表的最主要优点是（）

A、插入和删除的效率更高。

B、是随机存取结构

C、更方便存储

D、从任意结点出发都能遍历整个单链表

Q3:一棵完全二叉树883个结点。则叶子结点有（）个。

A、440

B、441

C、442

D、443

Q4:一棵高度为6个哈夫曼树，最多有（）个结点。

A、32

B、63

C、64

D、11

Q5:9个顶点的有向连通图，最少有（）条边

A、8

B、6

C、7

D、8

Q6:9个顶点的有向连通图，最多有（）条边。

A、36

B、56

C、28

D、28

Q7:AOV网中不能存在回路

是

否

Q8:单链表中设置头结点的作用是方便运算的实现

是

否

Q9:在单链表中某结点p后插入一个结点s的语句是 s-next=p-next;p-next=s;

是

否

Q10:顺序栈为空的条件是 top==0

是

否

Q11:链栈为空的条件是 top==null

是

否

Q12:不稳定的排序算法，没有应用价值

是

否

Q13:折半查找只适用于顺序存储结构，并且是有序序列。

是

否

Q14:单链表只要知道结点的指针就能读取结点中的元素，所以单链表是随机存取结构。

是

否

Q15:算法的时间复杂度是问题规模的函数

是

否

Q16:正确性是算法必须具备的特性

是

否

Q17:哈夫曼树中不能有度为1的结点。

是

否

Q18:二叉树的前序遍历就能唯一确定一棵二叉树

是

否

Q19:aov网的拓扑排序一定是不唯一的。

是

否

Q20:关键路径上的活动提前完成，一定会使得整个工期提前

是

否

Q21:开散列表没有元素个数的限制，也不会产生堆积现象。所以开散列表比闭散列表好。

是

否

Q22:下面哪种排序方法的时间性能与记录的初始状态无关。（）就是问那个是不稳定算法

A、归并排序

B、直接插入排序

C、快速排序

D、希尔排序

Q23:二叉排序树的（）遍历序列，是一个有序序列。

A、前序

B、中序

C、后序

D、层序

Q24:平衡二叉树是一棵完全二叉树

是

否

Q25:完全二叉树是一棵平衡二叉树

是

否

Q26:下面关于无向连通图的生成树说法错误的是（）。

A、该生成树是无向图的子图

C、该生成树有n-1条边

B、极小连通子图

D、极大连通子图

Q27:n个结点的有向完全图有（）条边。

A、2n

B、n-1

C、n(n-1)

D、n(n-1)/2

Q28:哈夫曼树的节点总数是2n-1

是

否

Q29:在哈夫曼树（也叫最优树）中，只有两种类型的结点：度为0或N，即最优二叉树中只有度为0或2的结点

是

否

Q30:在有n个叶子的哈夫曼树中，叶子结点总数为（n），分支结点总数为（n-1）。

是

否

Q31:完全二叉树有60个节点，则叶子结点有个。

A、28

B、29

C、30

D、31

Q32:对于一棵具有n个结点的树，其所有结点的度之和为 n-1

是

否

Q33:在已知p所指结点后插入一个新结点的时间复杂度是。

A、O(n)

B、O(1)

C、O(n/2)

D、O(n2)

Q34:设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为。

(A)q=p->next；p->data=q->data；p->next=q->next；free(q)；

(B)q=p->next；q->data=p->data；p->next=q->next；free(q)；

(C) q=p->next；p->next=q->next；free(q)；

(D) q=p->next；p->data=q->data；free(q)；

Q35:设有n个待排序的记录关键字，则在堆排序中需要个辅助记录单元。

(A) 1

(B) n

(C) nlog2n

(D) n2

Q36:组成数据的基本单位是

A.数据项

B.数据类型

C.数据元素

D.数据变量

Q37:非线性结构中的每个结点

A.无直接前趋结点

B.无直接后继结点

C.只有一个直接前趋结点和一个直接后继结点

D.可能有多个直接前趋结点和多个直接后继结点

Q38:一个线性表第一个元素的存储地址是 100,每个元素的长度为 2,则第 5 个元素的地址是

A.110

B.108

C.100

D.120

Q39:在一个单链表中，若 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;

Q40:链栈与顺序栈相比，有一个比较明显的优点是

A．插入操作更加方便

B．通常不会出现栈满的情况

C．不会出现栈空的情况

D．删除操作根加方便

Q41:一个栈的入栈次序ABCDE，则栈的不可能的输出序列是

A．EDCBA

B．DECBA

C．DCEAB

D．ABCDE

Q42:下列关于串的叙述中，正确的是

A.一个串的字符个数即该串的长度

B.一个串的长度至少是 1

C.空串是由一个空格字符组成的串

D.两个串 S1 和 S2 若长度相同，则这两个串相等

Q43:数组 A[8][10]中,每个元素 A 的长度为 3 个字节,从首地址 SA 开始连续存放在存储器内,该数组按行存放时,元素 A[7][4]的起始地址为。

A.SA+141

B.SA+144

C.SA+222

D.SA+225

Q44:长度为20的数组存储循环队列，队头指针front=17，队尾指针rear=6。入队7个元素，再出队6个元素后，队列长度为

A.9

B.10

C.11

D.8

Q45:一棵二叉树中，有8个叶子结点，7个度为1的结点。则度为2的结点有个

A.7

B.8

C.9

D.不确定

Q46:一棵哈夫曼树中有10个叶子结点，则分支结点有个

A.11

B.7

C.8

D.9

Q47:8个顶点的无向连通图，最少有（）条边，最多有条边

A.8,56

B.7,56

C.7,28

D.8,28

Q48:关于最小生成树，下面说法错误的是

A.代价最小的生成树

B.包含全部顶点

C.极小连通子图

D.包含全部的边

Q49:直接插入排序最好情况的时间复杂度是O(n)，最坏情况的时间复杂度是

A.O(1)

B.O(log2n)

C.O(n)

D.O(n2)

Q50:图的广度优先搜索类似于树的次序遍历。

A.先根遍历

B.中根遍历

C.后根遍历

D.层序遍历