三、单项选择题（每小题1分，共20分）
（ C ）1．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：
（A）存储结构 （B）逻辑结构 （C）顺序存储结构 （D）链式存储结构
（ C ）2.若已知一个栈的入栈序列是1，2，3， ，n，其输出序列为p1，p2，p3， ，pn，若p1=n，则pi为
Ａ．i Ｂ．n=i Ｃ．n-i+1 Ｄ．不确定
解释：当p1=n，即n是最先出栈的，根据栈的原理，n必定是最后入栈的（事实上题目已经表明了），那么输入顺序必定是1，2，3， ，n，则出栈的序列是n， ，3，2，1。
（若不要求顺序出栈，则输出序列不确定）
（ B ）3、判定一个栈ST（最多元素为m0）为空的条件是
Ａ．ST->top<>0 Ｂ．ST->top=0 Ｃ．ST->top<>m0
Ｄ．ST->top=m0
( B )4、 设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分（如下图所示）按行序存放在一维数组B[ 1, n(n-1)/2 ]中，对下三角部分中任一元素ai,j(i≤j), 在一维数组B中下标k的值是：
Ａ．i(i-1)/2+j-1 Ｂ．i(i-1)/2+j Ｃ．i(i+1)/2+j-1 Ｄ．i(i+1)/2+j
a1,1 a2,1A an,1a2,2an,2 an,n
（ C ）5．具有n(n>0)个结点的完全二叉树的深度为 。
(Ａ) log2(n) (Ｂ) log2(n) (Ｃ) log2(n) +1 (Ｄ) log2(n)+1
（ C ）6. 有8个结点的无向连通图最少有 条边。
A．5 B. 6 C. 7 D. 8
7、 答案：A＝ B＝ C＝ D＝ E＝
8、 答案：A＝ B＝ C＝ D＝
9、答案：A＝ B＝ C＝ D＝ E＝
四、简答题（每小题4分，共20分）
1.说明线性表、栈与队的异同点。
刘答：相同点：都是线性结构，都是逻辑结构的概念。都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表，只是对插入、删除运算加以限制。
不同点：①运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入、删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。
② 用途不同，堆栈用于子程调用和保护现场，队列用于多道作业处理、指令寄存及其他运算等等。
2. 试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。