数据结构附录A 样卷一
一、判断题：（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．链表不具有的特点是。
A、可随机访问任一个元素
B、插入删除不需要移动元素
C、不必事先估计存储空间
D、所需空间与线性表的长度成正比
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．串是。
A、不少于一个字母的序列
B、任意个字母的序列
C、不少于一个字符的序列
D、有限个字符的序列
10．数组A[1..5,1..6]的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续内存单元中，则A[5，5]的地址是。
A、1140
B、1145
C、1120
D、1125
11．将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为。
A、98
B、99
C、
50 D、48
12．对二叉树从1开始编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用实现编号。
A、先序遍历
B、中序遍历
C、后序遍
历 D、从根开始进行层次遍历
13．某二叉树的先序序列和后序序列正好相反，则该二叉树一定是的二叉树。
A、空或只有一个结点
B、高度等于其结点数
C、任一结点无左孩子
D、任一结点无右孩子
14．在有n个叶子结点的哈夫曼树中，其结点总数为。
A、不确定
B、2n
C、2n+1
D、2n-1
15．一个有n个顶点的无向图最多有条边。
A、n
B、n（n-1）
C、n（n-1）
/2 D、2n
16．任何一个无向连通图的最小生成树。
A、只有一棵
B、有一棵或多棵
C、一定有多棵
D、可能不存在
17．一组记录的关键字为（46，79，56，38，40，84），利用快速排序的方法，以第一个记录为基准得到的一次划分结果为。
A、38，40，46，56，79，84
B、40，38，46，79，56，84
C、40，38，46，56，79，84
D、40，38，46，84，56，79
18．已知数据表A中每个元素距其最终位置不远，则采用排序算法最节省时间。
A、堆排序
B、插入排序
C、快速排序
D、直接选择排序
19．下列排序算法中，算法可能会出现下面情况：初始数据有序时，花费时间反而最多。
A、堆排序
B、冒泡排序
C、快速排
序 D、SHELL 排序
20．对于键值序列（12，13，11，18，60，15，7，18，25，100），用筛选法建堆，必须从键值为的结点开始。
