一、判断题：（10 分）

正确在括号内打√，错误打×

( × ) 1.在单链表中，头结点是必不可少的。

（ × ）2．如果一个二叉树中没有度为1的结点，则必为满二叉树。

( √ ) 3. 循环链表的结点结构与单链表的结点结构完全相同，只是结点间的连接方式不同。 ( × ) 4. 顺序存储结构只能用来存放线性结构；链式存储结构只能用来存放非线性结构。 ( √ ) 5. 在一个大根堆中，最小元素不一定在最后。

( √ ) 6. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和。 （ × ）7. 在采用线性探测法处理冲突的散列表中，所有同义词在表中相邻。 （ √ ）8. 内部排序是指排序过程在内存中进行的排序。 （ × ）9. 拓扑排序是指结点的值是有序排列。

( × )10. AOE网所表示的工程至少所需的时间等于从源点到汇点的最长路径的长度。

二、选择题(30分, 每题1.5分)

二：选择题

1．有一个含头结点的单链表，头指针为head, 则判断其是否为空的条件为：________________

A． head=NIL B.head^.next=NIL C. head^.next=head D. head<>NIL 或 A． head==NULL B. Head->next==NULL C. head->next==head D. Head!=NULL 2．非空的循环单链表head的尾指针p满足______________。

A. p^.next=NIL B. p=NIL C. p^.next=head D. p=head 或 A. p->next=NULL B. p==NULL C. P->next==head D. p==head 3

、插入删除不需要移动元素

、所需空间与线性表的长度成正比

4．若某链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用 存储方式最节省运算时间。

A、单链表 B、双链表 C、单循环链表 D、带头结点的双循环链表

5．若线性表最常用的操作是存取第i个元素及其前驱的值，则采用 存储方式节省时间。

A、单链表 B、双链表 C、单循环链表 D、顺序表 6．设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能的是 。 A、 A，B，C， D B、D，C，B，A

C、 A，C，D，B D、D，A，B，C

7．一个队列的入队序列是1，2，3，4，则队列的输出序列是 。

A、4，3，2，1 B、1，2，3，4 C、1，4，3，2 D、3，2，4，1 8．设循环队列中数组的下标范围是1~n，其头尾指针分别为f，r，若队列中元素个数为 。 A、r-f B 、r-f+1 C、（r-f+1）mod n D、（r-f+n）mod n

9．串是 。