2015-2016-1期中考试试卷
中国十大悍匪张君-淘宝双11活动规则
2015-2016-1《数据结构》期中考试试卷
CDABA BDCCC
BACDB DADDB BCCDC CDABC BCACC
一、选择题(每题2分，共70分)
1．具有线性结构的数据结构是（ ）
A．树 B．图
C．栈和队列 D．广义表
2.
下面几种算法时间复杂度阶数中，值最大的是（ ）
2
A.O(nlog
2
n) B.O(n)
n
C.O(n) D.O(2)
3.下述哪一条是顺序存储结构的优点？（ ）
A．存储密度大 B．插入运算方便 C．删除运算方便
D．可方便地用于各种逻辑结构
的存储表示
4．下面关于线性表的叙述中，错误的是哪一个？（ ）
A．线性表采用顺序存储，必须占用一片连续的存储单元。
B．线性表采用顺序存储，便于进行插入和删除操作。
C．线性表采用链接存储，不必占用一片连续的存储单元。
D．线性表采用链接存储，便于插入和删除操作。
5．若某线性表最常用的操作是存取任一指
定序号的元素和在最后进行插入和删除运算，则
利用（ ）存储方式最节省时间。
A．顺序表 B．双链表 C．带头结点的双循环链表
D．单循环链表
6．链表不具有的特点是（ ）
A．插入、删除不需要移动元素
B．可随机访问任一元素
C．不必事先估计存储空间 D．所需空间与线性长度成正比
7. 下列关于队列的叙述中,错误的是( )
．．
A.队列是一种先进先出的线性表
B.队列是一种后进后出的线性表
C.循环队列中进行出队操作时要判断队列是否为空
D.在链队列中进行入队操作时要判断队列是否为满
8.
若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间
复杂度为（
）(1<=i<=n+1)。
2
A. O(0) B. O(1)
C. O(n) D. O(n)
9.
对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ ）。
A．O(n)
O(n) B. O(n) O(1) C. O(1) O(n)
D. O(1) O(1)
10．在双向链表指针p的结点前插入一个指针q的结点操作是（
）。
A. p->Llink=q;q->Rlink=p;p->Llink->Rlink=q
;q->Llink=q；
B. p->Llink=q;p->Llink->Rlink=q;
q->Rlink=p;q->Llink=p->Llink;
C. q->Rlink=p;q
->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q;
D. q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p-
>Llink=q;
11.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个
元素的地址是
( )
（A）110 （B）108 （C）100
（D）120
12. 链接存储的存储结构所占存储空间：( )
（A）
分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
（B） 只有一部分，存放结点值
（C） 只有一部分，存储表示结点间关系的指针
（D）
分两部分，一部分存放结点值，另一部分存放结点所占单元数
13． 单链表的存储密度( )
（Ａ）大于1； （Ｂ）等于1； （Ｃ）小于1； （Ｄ）不能确定
14.若元素的入栈顺
序为1，2，3....，n，如果第2个出栈的元素是n，则输出的第i(1<=i<=n)
个元素是
( )
A.n-i B.n-i+l
C.n-i+2 D.无法确定
1
5．假设以数组A[60]存放循环队列的元素，其头指针是front=47，当前队列有50个元素，
则队列的尾指针值为（ ）
A．3 B．37
C．50 D．97
16.下列关于队列的叙述中,错误的是( )
．．
A.队列是一种先进先出的线性表
B.队列是一种后进后出的线性表
C.循环队列中进行出队操作时要判断队列是否为空
D.在链队列中进行入队操作时要判断队列是否为满
17.一个队列的输入序列是A，B，C，D，则该队列的输出序列是( )
A.A，B，C，D B.B，C，D，A
C.D，C，B，A D.C，D，B，A
18.队列的特点是（ ）
A.允许在表的任何位置进行插入和删除
B.只允许在表的一端进行插入和删除
C.允许在表的两端进行插入和删除
D.只允许在表的一端进行插入，在另一端进行删除
19.已知循环队列的存储空间大小为m
，队头指针front指向队头元素，队尾指针rear指向
队尾元素的下一个位置，则向队列中插入新
元素时，修改指针的操作是（ ）
=(rear-1)%m;
=(front-1)%m;
=(front+1)%m;
=(rear+1)%m;
20.设栈的初始状态为空，元素1、2、3、4、5、6依次入
栈，得到的出栈序列是（2,4,3,6,5,1）,
则栈的容量至少是( )
A.2
B.3
C.4 D..6
21．若栈的进栈序列为1，2，3，4，5，则经过出入栈操作不可能获得的出栈序列是( )
．．．
A．4，5，3，2，1 B．4，3，5，1，2
C．1，2，3，4，5 D．5，4，3，2，1
22.已知一个栈的入栈序列是1，2
，3，…，n，其输出序列为p
l
，p
2
，p
3
….，p<
br>n
，若p
1
是n，
则p
i
是（ ）
A.i B.n-i
C.n-i+l D.不确定
23．设有一个10阶的下三角
矩阵A，采用行优先压缩存储方式，a
ll
为第一个元素，其存储
地址为1000，每
个元素占一个地址单元，则a
85
的地址为 （ ）
A．1012
B．1017
C．1032 D．1039
24．A是7×4的二维数组，按行优先方式顺序存储，元素A[0][0]的存储地址为1
000，若
每个元素占2个字节，则元素A[3][3]的存储地址为( )
A．1015
B．1016
C．1028 D．1030
25.已知10×12的二维数组A，按“行
优先顺序”存储，每个元素占1个存储单元，已知A[1][1]
的存储地址为420，则A[5][5
]的存储地址为（ ）
A.470 B.471
C.472 D.473
26. 由三个结点可以构造出多少种不同的二叉树( )
A)3
B)4
C)5 D)6
27.
在一棵深度为k的完全二叉树中,所含结点个数至少( )。
A)2
B) 2+1
C)2-1 D) 2
28.
如图所示的4棵二叉树中，（ ）不是完全二叉树。
kk-1
kk
29. 设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数是
(
)。
A)12 B)13 C)14
D)15
30. 树中所有结点的度等于所有结点数加（ ）
A.0
B.1 C.-1 D.2
31.
在一棵树中,每个结点最多有（ ）个前驱结点。
A.0 B.1
C.2 D.任意多个
32.
在一棵具有n个结点的二叉树的第i层上，最多具有（ ）个结点。
A.2 B.
2 C. 2 D. 2
33. 在一棵二叉树上第5层的结点数最多为（
）
A.16 B.15 C.8
D.32
34. 下列关于二叉树的说法正确的是( ) 。
A)一颗二叉树中的结点个数大于0
B)二叉树中任何一个结点要么是叶子,要么恰有两个子女
C)一棵二叉树中叶子结点的个数等于度为2的结点个数加1
D)二叉树中任何一个结点的左子树和右子树上的结点个数一定相等。
35.
在一棵完全二叉树中，若编号从1开始，编号为i的结点存在右孩子，则右孩子结点的
编号为（
）
A.2i B.2i-1 C.2i+1
D.2i+2
顺序 （n-1）2 99和6 n-i+1
XSXXSSXXSS M-1 栈顶 删除
front=(front+1)%m
17 和33 138 2-1 2和2-1
二、填空题(每空2分，共30分)
1．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取
线性表中的
元素时，应采用_______存储结构。
2．线性表L=（a1,a2,…,an）用数组表示，假
定删除表中任一元素的概率相同，则删除一
个元素平均需要移动元素的个数是________。 3．设二叉树根结点的层次为0，对含有100个结点的二叉树，可能的最大树深度和最小树
深分别
是 _______ 。
4．在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个
元素时，需向后移动_____
___个元素。
5.用X代表进栈操作,S代表出栈操作。
给出利用栈将字符串改变为的操作
步骤___________。例如：将改变为则其操作步骤为XXS
XSS。
6．顺序栈存放在S[m]中，S[0]为栈底，栈顶指针top初始值为-1，则栈满的条
件是top=
_________。
7.在栈结构中，允许插入和删除的一端称为______。
8．队列只能在队尾进行插入操作，在队首进行__________操作。
9．设循环队列
存放在向量data[0..m-l]中，在出队操作后，队头指针front变化为______
_____。
10.设循环队列的容量为50(序号从0到49)，现经过一系列的入队和出
队运算后，有
①front=11，rear=29；②front=29，rear=11；在这两种
情况下，循环队列中的元素个数分
别是_____和______。
hk-1k
ii
+1i-1n
11.若二维数组a［4］［5］的基地址是100,每个元素占用2个存
储单元,以行存储，则数组
a中最后一个元素的存储地址是________。
12.设二叉
树的深度为h，且只有度为0和2的结点，则此二叉树中所含结点数最多为
________。
13.深度为k完全二叉树至少有________个结点，至多有________ 个结点。
2015-2016-1《数据结构》期中考试试卷
CDABA
BDCCC BACDB DADDB BCCDC CDABC BCACC
一、选择题(每题2分，共70分)
1．具有线性结构的数据结构是（ ）
A．树 B．图
C．栈和队列 D．广义表
2.
下面几种算法时间复杂度阶数中，值最大的是（ ）
2
A.O(nlog
2
n) B.O(n)
n
C.O(n) D.O(2)
3.下述哪一条是顺序存储结构的优点？（ ）
A．存储密度大 B．插入运算方便 C．删除运算方便
D．可方便地用于各种逻辑结构
的存储表示
4．下面关于线性表的叙述中，错误的是哪一个？（ ）
A．线性表采用顺序存储，必须占用一片连续的存储单元。
B．线性表采用顺序存储，便于进行插入和删除操作。
C．线性表采用链接存储，不必占用一片连续的存储单元。
D．线性表采用链接存储，便于插入和删除操作。
5．若某线性表最常用的操作是存取任一指
定序号的元素和在最后进行插入和删除运算，则
利用（ ）存储方式最节省时间。
A．顺序表 B．双链表 C．带头结点的双循环链表
D．单循环链表
6．链表不具有的特点是（ ）
A．插入、删除不需要移动元素
B．可随机访问任一元素
C．不必事先估计存储空间 D．所需空间与线性长度成正比
7. 下列关于队列的叙述中,错误的是( )
．．
A.队列是一种先进先出的线性表
B.队列是一种后进后出的线性表
C.循环队列中进行出队操作时要判断队列是否为空
D.在链队列中进行入队操作时要判断队列是否为满
8.
若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间
复杂度为（
）(1<=i<=n+1)。
2
A. O(0) B. O(1)
C. O(n) D. O(n)
9.
对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ ）。
A．O(n)
O(n) B. O(n) O(1) C. O(1) O(n)
D. O(1) O(1)
10．在双向链表指针p的结点前插入一个指针q的结点操作是（
）。
A. p->Llink=q;q->Rlink=p;p->Llink->Rlink=q
;q->Llink=q；
B. p->Llink=q;p->Llink->Rlink=q;
q->Rlink=p;q->Llink=p->Llink;
C. q->Rlink=p;q
->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q;
D. q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p-
>Llink=q;
11.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个
元素的地址是
( )
（A）110 （B）108 （C）100
（D）120
12. 链接存储的存储结构所占存储空间：( )
（A）
分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
（B） 只有一部分，存放结点值
（C） 只有一部分，存储表示结点间关系的指针
（D）
分两部分，一部分存放结点值，另一部分存放结点所占单元数
13． 单链表的存储密度( )
（Ａ）大于1； （Ｂ）等于1； （Ｃ）小于1； （Ｄ）不能确定
14.若元素的入栈顺
序为1，2，3....，n，如果第2个出栈的元素是n，则输出的第i(1<=i<=n)
个元素是
( )
A.n-i B.n-i+l
C.n-i+2 D.无法确定
1
5．假设以数组A[60]存放循环队列的元素，其头指针是front=47，当前队列有50个元素，
则队列的尾指针值为（ ）
A．3 B．37
C．50 D．97
16.下列关于队列的叙述中,错误的是( )
．．
A.队列是一种先进先出的线性表
B.队列是一种后进后出的线性表
C.循环队列中进行出队操作时要判断队列是否为空
D.在链队列中进行入队操作时要判断队列是否为满
17.一个队列的输入序列是A，B，C，D，则该队列的输出序列是( )
A.A，B，C，D B.B，C，D，A
C.D，C，B，A D.C，D，B，A
18.队列的特点是（ ）
A.允许在表的任何位置进行插入和删除
B.只允许在表的一端进行插入和删除
C.允许在表的两端进行插入和删除
D.只允许在表的一端进行插入，在另一端进行删除
19.已知循环队列的存储空间大小为m
，队头指针front指向队头元素，队尾指针rear指向
队尾元素的下一个位置，则向队列中插入新
元素时，修改指针的操作是（ ）
=(rear-1)%m;
=(front-1)%m;
=(front+1)%m;
=(rear+1)%m;
20.设栈的初始状态为空，元素1、2、3、4、5、6依次入
栈，得到的出栈序列是（2,4,3,6,5,1）,
则栈的容量至少是( )
A.2
B.3
C.4 D..6
21．若栈的进栈序列为1，2，3，4，5，则经过出入栈操作不可能获得的出栈序列是( )
．．．
A．4，5，3，2，1 B．4，3，5，1，2
C．1，2，3，4，5 D．5，4，3，2，1
22.已知一个栈的入栈序列是1，2
，3，…，n，其输出序列为p
l
，p
2
，p
3
….，p<
br>n
，若p
1
是n，
则p
i
是（ ）
A.i B.n-i
C.n-i+l D.不确定
23．设有一个10阶的下三角
矩阵A，采用行优先压缩存储方式，a
ll
为第一个元素，其存储
地址为1000，每
个元素占一个地址单元，则a
85
的地址为 （ ）
A．1012
B．1017
C．1032 D．1039
24．A是7×4的二维数组，按行优先方式顺序存储，元素A[0][0]的存储地址为1
000，若
每个元素占2个字节，则元素A[3][3]的存储地址为( )
A．1015
B．1016
C．1028 D．1030
25.已知10×12的二维数组A，按“行
优先顺序”存储，每个元素占1个存储单元，已知A[1][1]
的存储地址为420，则A[5][5
]的存储地址为（ ）
A.470 B.471
C.472 D.473
26. 由三个结点可以构造出多少种不同的二叉树( )
A)3
B)4
C)5 D)6
27.
在一棵深度为k的完全二叉树中,所含结点个数至少( )。
A)2
B) 2+1
C)2-1 D) 2
28.
如图所示的4棵二叉树中，（ ）不是完全二叉树。
kk-1
kk
29. 设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数是
(
)。
A)12 B)13 C)14
D)15
30. 树中所有结点的度等于所有结点数加（ ）
A.0
B.1 C.-1 D.2
31.
在一棵树中,每个结点最多有（ ）个前驱结点。
A.0 B.1
C.2 D.任意多个
32.
在一棵具有n个结点的二叉树的第i层上，最多具有（ ）个结点。
A.2 B.
2 C. 2 D. 2
33. 在一棵二叉树上第5层的结点数最多为（
）
A.16 B.15 C.8
D.32
34. 下列关于二叉树的说法正确的是( ) 。
A)一颗二叉树中的结点个数大于0
B)二叉树中任何一个结点要么是叶子,要么恰有两个子女
C)一棵二叉树中叶子结点的个数等于度为2的结点个数加1
D)二叉树中任何一个结点的左子树和右子树上的结点个数一定相等。
35.
在一棵完全二叉树中，若编号从1开始，编号为i的结点存在右孩子，则右孩子结点的
编号为（
）
A.2i B.2i-1 C.2i+1
D.2i+2
顺序 （n-1）2 99和6 n-i+1
XSXXSSXXSS M-1 栈顶 删除
front=(front+1)%m
17 和33 138 2-1 2和2-1
二、填空题(每空2分，共30分)
1．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取
线性表中的
元素时，应采用_______存储结构。
2．线性表L=（a1,a2,…,an）用数组表示，假
定删除表中任一元素的概率相同，则删除一
个元素平均需要移动元素的个数是________。 3．设二叉树根结点的层次为0，对含有100个结点的二叉树，可能的最大树深度和最小树
深分别
是 _______ 。
4．在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个
元素时，需向后移动_____
___个元素。
5.用X代表进栈操作,S代表出栈操作。
给出利用栈将字符串改变为的操作
步骤___________。例如：将改变为则其操作步骤为XXS
XSS。
6．顺序栈存放在S[m]中，S[0]为栈底，栈顶指针top初始值为-1，则栈满的条
件是top=
_________。
7.在栈结构中，允许插入和删除的一端称为______。
8．队列只能在队尾进行插入操作，在队首进行__________操作。
9．设循环队列
存放在向量data[0..m-l]中，在出队操作后，队头指针front变化为______
_____。
10.设循环队列的容量为50(序号从0到49)，现经过一系列的入队和出
队运算后，有
①front=11，rear=29；②front=29，rear=11；在这两种
情况下，循环队列中的元素个数分
别是_____和______。
hk-1k
ii
+1i-1n
11.若二维数组a［4］［5］的基地址是100,每个元素占用2个存
储单元,以行存储，则数组
a中最后一个元素的存储地址是________。
12.设二叉
树的深度为h，且只有度为0和2的结点，则此二叉树中所含结点数最多为
________。
13.深度为k完全二叉树至少有________个结点，至多有________ 个结点。