一、简要回答问题：[15分]

1．  数据结构

2．  简述数组和广义表属于线性结构的理由

3．  计算式查找方法的基本思想

4．  线性结构与非线性结构的差别

5．  快速排序的最坏情况是什么？你认为应怎样避免。

二、判别正误[5分]

   判断下题是否正确，若正确在（ ）内打√ ，否则打╳

（   ）1．线性结构只能用顺序存储方式存放，而非线性结构只能用链式方式存放。

（   ）2．图G的一棵最小代价树的代价一定小于该图其它任何一棵生成树的代价。

（   ）3．线性表采用链式存储，它比采用顺序存储方式，使得插入、删除、查找等运算的时间性能都更好。

（   ）4． 二叉排序树或者是一空树，或是具有下列性质的二叉树：

u       若它的左子树非空，则根结点的值大于其左孩子的值。

u       若它的右子树非空，则根结点的值小于其右孩子的值。

（   ）5．只要还有可用空间，链栈和链队就不会出现栈满和队满的情况。

三、选择题：[12分]

1．  一个栈的输入序列是12345，则栈的不可能的输出序列是___    ___。

(a) 54321    (b) 45321    (c)43512    (d)12345

2．  子串是­­­_____   _。

(a)串中一些字符构成的序列   （b）串中若干个连续字母构成的序列

 (c)串中一个以上连续字符组成的序列   

(d) 串中任意个连续字符组成的序列

3．  表长为25的哈希表，用除留余数法，即按式H（Key）=Key mod P，建立哈希函数，P应取___      。

(a)26        (b)15        (c)24       (d)23

4．  已知一待排序文件已基本有序的前提下，采用如下方法中效率最高的排序方法是_____  _。

(a)直接插入排序   （b）直接选择排序    (c)快速排序   (d)归并排序

5．  排序方法中，从未排序序列中挑选最大（或最小）元素，并将其依次放入已排序（初始为空）的一端，其方法称为_______。

(a)插入排序   （b）归并排序     (c)选择排序     (d)快速排序

6．  关键路径是事件结点网络中­­­________。

(a)从开始结点到完成结点的最长路径

(b)从开始结点到完成结点的最短路径

(c)最长的回路且按拓扑排序

(d)最短的回路

四、填空：[20分]

1．  设数组B[0..3，1..5]，数组中的任一元素B[I，j]均占两个单元，从首地址SA开始，把数组B按行序为主序进行存放，则元素B[3，4]的地址为______­_。

2．  设有n个结点的二叉树，采用二叉链表存储，空链域个数_______。

3．  深度为6（根层次为1）的二叉树至多有_______个结点。

4．  在单链表中，若要在指针q所指结点之后插入一个指针s所指的结点，则需执行下列两个语句­­_________     ；__________  _。

5．