一、填空题（共20分，每空1分）。
1. 数据结构是研究数据元素之间抽象化的相互关系和这种关系在计算机中的存储结构表
示，通常有下列四种存储结构： （1） 、 （2） 、 （3） 和 （4） 。
2. 评价算法的标准很多，通常是以执行算法所需要的 （5） 和所占用的（6） 来判别一
个算法的优劣。
3. 队列操作的原则是（7），栈的插入和删除操作在（8）进行。
4. 对循环队列Q，它的最大存储空间是MAXSIZE，队头指针是front，队尾指针是rear，
采用少用一个存储单元的方法解决假溢出时，队满的判断条件是（9），队空的判断条件是（10）。
5. 在以 head 为表头指针的带有头结点的单链表和循环单链表中，判断链表为空的条件分
别为 （11） 和 （12）。
6. 假设二维数组A[6][8]，每个元素用相邻的4个字节存储，存储器按字节编址 ，已知
A[0][0]的存储位置为100，按行优先顺序存储的元素A[2][5]的第一个字节的地址为（13）。
7. 空格串的长度为串中所包含（14） 字符的个数，空串的长度为 （15） 。
8. 有向图 G 用邻接矩阵 A[n][n] 存储表示，其第 i 行的所有元素之和等于顶点 i 的
（16） 。
9. 在关键字序列 (12 ， 23 ， 34 ， 45 ， 56 ， 67 ， 78 ， 89 ， 91) 中折半查找
关键字为89和25的结点时，所需进行的比较次数分别为 （17） 和 （18） 。 10. 请说出两种处理哈希冲突的方法 （19） 、_（20）_。 二、选择题（共20分，每题2分）。
1. 对线性表，在下列哪种情况下应采用链式存储结构？（ ）
A.经常需要随机存取元素 C.表中元素的个数不变
B.经常需要进行插入和删除操作
D.表中元素需要占据一片连续的存储空间
2. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功情况下，则平均比
较（ ）个结点。 A.n
B.n/2
C.(n-1)/2
D.(n+1)/2
3. 若对某线性表最常进行的操作是在最后一个元素之后插入和删除第一个元素，则采用
（ ）存储方式最节省运算时间。 A.单链表
C.仅有头指针的单循环链表
B.双链表
D.仅有尾指针的单循环链表
4. 在一个单链表中，若要删除p指针所指结点的后继结点，则执行（ ）。
A.p=p->next; p->next=p->next->next; C.p=p->next;
B.p->next=p->next->next; D.p=p->next->next;
5. 在具有 n 个结点的二叉链表中，非空的链域个数为（ ）。
A.n-1
B.n
C.n+1
D.不确定
6. 有64个结点的完全二叉树的深度为（ ）（假设根结点的层次为1）。
A.8
B.7
C.6
D.5
7. 边远山区的那个小村庄，现要为他们建成能互相通信的网 ，并且总的花费最少，这可
以归结为什么问题（ ）。 A.最短路径
B.关键路径
C.拓扑排序
D.最小生成树
8. 折半查找法要求查找表中各元素的键值必须是（ ）。
A.递增或递减
B.递增
C.递减
D.无序
9. 下列排序算法中，（ ）算法在进行一趟相应的排序处理结束后不一定能选出一个元素
放到其最终位置上。 A.直选择排序
B.冒泡排序
C.归并排序
D.堆排序
10. 对于键值序列（2，33，21，18，65，38，7，49，24，86），用筛选法建堆，必须从键
值为（ ）的结点开始。 A.86
B.2
C.65
D.38
三、判断题（共10分，每题2分）。
1. 已知指针P指向链表L中的某结点，执行语句P=P->next不会删除该链表中的结点。
（ ）
2. 如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。( ) 3. 若一棵二叉树的任一非叶结点度均为2，则该二叉树为满二叉树。（ ）
4. 任一AOE网中至少有一条关键路径，且是从源点到汇点的路径中最短的一条。（ ） 5. 在采用线性探测法处理冲突的散列表中所有同义词在表中相邻。（ ） 四、简答题（共24分，每题8分）。
1. 二叉树的先序遍历序列为：A B C D E F G H I，中序遍历序列为：B C A E D G H F I，
画出这棵二叉树。
2. 输入一个结点序列{300，100，80，52，40，64，350}，试画出构造平衡二叉树的过程，
并说明平衡旋转类型。
3. 已知一组记录的排序码为（46，79，56，38，40，80，95，24），写出对其进行快速排
序的每一趟排序的结果。
五、算法设计题（共16分，每小题8分）。 1. 试写一建立单链表的算法。
2. 已知一个非空线性链表第一个结点的指针为L，请写一算法，将链表中数据域值最大的
那个结点移到链表最后面。