东北农业大学网络教育学院数据结构作业题（一）
一、选择题（每题2分，共20分）
1．在一个长度为
的顺序表的任一位置插入一个新元素的渐进时间复杂度为（）。
A、O

B、O
2
C、O1
D、O
2
2．带头结点的单链表first为空的判定条件是（）。
A、firstNULL
B、firstli
kNULL
C、firstli
kfirst
D、firstNULL
3．在一棵树中，（
）没有前驱结点。
A、分支结点B、叶结点
C、树根结点D、空结点
4．在有向图中每个顶点的度等于该顶点的（
）。
A、入度
B、出度
C、入度与出度之和
D、入度与出度之差
5．对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（
）
的值除以9。
A、20
B、18
C、25
D、22
6．下列程序段的时间复杂度为（
）。
s0；
fori1；i
；i
forj1；j
；j
sij；
A、O1
B、O
C、O2

D、O
2
7．栈是一种操作受限的线性结构，其操作的主要特征是（
）。
A、先进先出B、后进先出C、进优于出D、出优于进
8．假设以数组A
存放循环队列的元素，其头、尾指针分别为fro
t和rear。若设定尾指针指向队列中的
队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为（
）。
A、rearfro
t1％

B、rearfro
t％

C、fro
trear1％

D、rearfro
t
％

9．高度为5的完全二叉树中含有的结点数至少为（
）。
A、16
B、17
C、31
D、32
10．如图所示有向图的一个拓扑序列是

A、ABCDEFB、FCBEADC、FEDCBA
D、DAEBCF
二、填空题（每空1分，共20分）
1．
0个顶点的无向图最多有
条边，最少有
条边。
2．在一棵AVL树中，每个结点的左子树高度与右子树高度之差的绝对值不超过
。
3．已知8个数据元素为（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉排
序树，则该树的深度为
。
4．在二叉树的第i层上至多有
结点。
5．对于一棵具有
个结点的二叉树，若一个结点的编号为i1≤i≤
，则它的左孩子结点的编号
f为
，右孩子结点的编号为
，双亲结点的编号为
。
6．数据的存储结构被分为
、
、
和
四种。
7．假定一棵树的广义表表示为ABCDEFGHIJ，则树中所含的结点数为
为
，树的度为
。
8．在一个具有
个顶点的无向图中，要连通所有顶点则至少需要
条边。
9．在线性结构、树形结构和图形结构中，前驱和后继结点之间分别存在着
、
和
的联系。
个，树的深度
10．一棵含999个结点的完全二叉树的深度为
。
三、运算题（每题5分，共10分）
1．设有一个1010的r