数据结构
附录
A
样卷一
一、判断题:(
10
分)
正确在括号内打√,错误打×
( ) 1.
在单链表中,头结点是必不可少的?/p>
?/p>
?/p>
2
.如果一个二叉树中没有度?/p>
1
的结点,则必为满二叉树?/p>
( )
3.
循环链表的结点结构与单链表的结点结构完全相同?/p>
只是结点间的连接方式不同?/p>
( ) 4.
顺序存储结构只能用来存放线性结构;链式存储结构只能用来存放非线性结构?/p>
( ) 5.
在一个大根堆中,最小元素不一定在最后?/p>
( ) 6.
在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和?/p>
?/p>
?/p>
7.
在采用线性探测法处理冲突的散列表中,所有同义词在表中相邻?/p>
?/p>
?/p>
8.
内部排序是指排序过程在内存中进行的排序?/p>
?/p>
?/p>
9.
拓扑排序是指结点的值是有序排列?/p>
( )10. AOE
网所表示的工程至少所需的时间等于从源点到汇点的最长路径的长度?/p>
二、选择?/p>
(30
?/p>
,
每题
1.5
?/p>
)
1
.有一个含头结点的单链表,头指针为
head,
则判断其是否为空的条件为?/p>
________________
A
?/p>
head=NIL B. head^.next=NIL C. head^.next=head D. head<>NIL
?/p>
A
?/p>
head==NULL B. Head->next==NULL C. head->next==head D. Head!=NULL
2
.非空的循环单链?/p>
head
的尾指针
p
满足
______________
?/p>
A. p^.next=NIL B. p=NIL C. p^.next=head D. p=head
?/p>
A. p->next=NULL B. p==NULL C. P->next==head D. p==head
3
.链表不具有的特点是
?/p>
A
、可随机访问任一个元?/p>
B
、插入删除不需要移动元?/p>
C
、不必事先估计存储空?/p>
D
、所需空间与线性表的长度成?/p>
?/p>
4
.若某链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点,?/p>
采用
存储方式最节省运算时间?/p>
A
、单链表
B
、双链表
C
、单循环链表
D
、带头结点的
双循环链?/p>
5
.若线性表最常用的操作是存取?/p>
i
个元素及其前驱的值,则采?/p>
存储方式节省
时间?/p>
A
、单链表
B
、双链表
C
、单循环链表
D
、顺?/p>
?/p>
6
?/p>
设一个栈的输入序列为
A
?/p>
B
?/p>
C
?/p>
D
?/p>
则借助一个栈所得到的输出序列不可能的是
?/p>
A
?/p>
A
?/p>
B
?/p>
C
?/p>
D B
?/p>
D
?/p>
C
?/p>
B
?/p>
A
C
?/p>
A
?/p>
C
?/p>
D
?/p>
B D
?/p>
D
?/p>
A
?/p>
B
?/p>
C
7
.一个队列的入队序列?/p>
1
?/p>
2
?/p>
3
?/p>
4
,则队列的输出序列是
?/p>
A
?/p>
4
?/p>
3
?/p>
2
?/p>
1 B
?/p>
1
?/p>
2
?/p>
3
?/p>
4 C
?/p>
1
?/p>
4
?/p>
3
?/p>
2 D
?/p>
3
?/p>
2
?/p>
4
?/p>
1
8
.设循环队列中数组的下标范围?/p>
1~n
,其头尾指针分别?/p>
f
?/p>
r
,若队列中元素个?/p>
?/p>
?/p>
A
?/p>
r-f B
?/p>
r-f+1 C
?/p>
?/p>
r-f+1
?/p>
mod
n D
?/p>
?/p>
r-f+n
?/p>
mod n
9
.串?/p>
?/p>
A
、不少于一个字母的序列
B
、任意个字母的序?/p>
C
、不少于一个字符的序列
D
、有限个字符的序?/p>
10
.数?/p>
A[1..5,1..6]
的每个元素占
5
个单元,将其按行优先次序存储在起始地址?/p>
1000
的连续内存单元中,则
A[5
?/p>
5]
的地址?/p>
?/p>
A
?/p>
1140 B
?/p>
1145 C
?/p>
1120 D
?/p>
1125
11
.将一棵有
100
个结点的完全二叉树从根这一层开始,每一层从左到右依次对结点进行
编号,根结点编号?/p>
1
,则编号?/p>
49
的结点的左孩子的编号?/p>
?/p>