华东交通大学2008—2009学年第一学期考试卷
试卷编号： （A ）卷
考生注意事项：1、本试卷共 8 页，总分100分，考试时间120分钟。
2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。
一、选择题(每题2分，共20分)
1．以下不属于算法要素的是（ ）。
A. 有穷性
B. 可行性
C. 可读性
D. 输入
2．顺序表随机访问元素a k 基本操作的时间复杂度为（ ）。 A. O( 1 ) B. O( n ) C. O( logn ) D. O( k ) 3．图的广度优先搜索算法中定义的辅助数据结构为（ ） A. 队列
B. 栈
C. 邻接表
D. 二叉树
4．求串T 在串S 中首次出现位置的基本操作叫做（ ） A. 求子串
B. 模式匹配
C. 串替换
D. 串连接 5．广义表L = ( ( apple, pear ), ( banana, orange ) ) 的表尾是（ ） A. ( apple, pear ) B. ( ( apple, pear ) ) C. ( banana, orange ) D. ( ( banana, orange ) ) 6．n×n 阶对称矩阵压缩存储到（ ）个元的空间中。（考试范围之外） A. n 2 B. n 2/2 C. n(n+1) D. n(n+1)/2 7．在一棵含有2009个结点的完全二叉树中，叶子结点有（ ）个。 A. 1001 B. 1003 C. 1005 D. 1007
8．由权值为7，19，2，6，32，3，21，10的结点构成的赫夫曼树的带权路径长度为（ ） A. 271 B. 261 C. 241 D. 231 9．有向图中所有顶点的入度之和为n ，则出度之和为（ ） A. n+1 B. n
C. n-1
D.n/2
10．在有序表( 1, 5, 8, 9, 12, 16, 23 )中折半查找关键字16的比较次数是（ ） A. 2 B. 3 C. 4 D. 5
二、填空题(每空2分，共30分)
1．线性表的顺序表示称为___顺序表____。
2．8个顶点的连通图最多有__28_条边，最少有__7___条边。
3．含有9个叶子结点的3阶B-树中至少有_____个非叶子结点。（考试范围之外） 4．广义表 ( ( ( ) ), a, ( ( b, c ), ( ), d ) ) 的深度为__3__
5．按低下标优先存储整数数组A 9×3×5×8时，第1个元素a 0000的存储地址是0，每个整数占4个字节，a 3125的地址是_____________。（考试范围之外） 6．设串S = ‘I AM A WORKER!’，T = ‘GOOD’，
Concat( SubString( S, 6, 2 ), Concat( T, SubString( S, 7, 6 ) ) = A GOOD WORKE 。 7．总长为n 的顺序循环队列中，队头指针为front ，队尾指针为rear ，队列满的条件为______(rear+1) mod n =front____，队列空的条件为__front=rear__。
8．下图中的AOE-网关键活动为 __，____，________，< H, I >。 9．下图中的有向图，从顶点A 出发进行广度优先遍历的顶点序列为_ABCDEFGHI___。 10．p 是指向单链表L 的中间结点的指针，补充下列删除p 的后继结点的程序段。 s = p->next;
__p->nex t=s->next;____ free( s );
11．程序段
for( i=0; i中，语句k++的执行次数为___n*(n-1)/2___。
三、应用题(每题5分，共40分)
1．写出图中所示的AOV 网的2个不同的拓扑序列。
参考答案： 1，5，2，3，6，4 1，5，2，6，3，4
1，5，6，2，3，4
2．画出和下图中的森林对应的二叉树。
参考答案：
3．进栈序列为ABC ，写出所有可能的出栈序列。
参考答案：
可以通过穷举所有可能性来求解：
① A 入A 出，B 入B 出，C 入C 出， 即ABC ； ② A 入A 出，B 、C 入C 、B 出， 即ACB ； ③ A 、B 入，B 出，C 入C 出，A 出 即BCA ； ④ A 、B 入，B 、A 出，C 入C 出， 即BAC ； ⑤ A 、B 、C 入，C 、B 、A 出， 即CBA ； 合计有5种可能性。
4．按照四则运算加、减、乘、除和幂运算(∧)的优先关系的惯例，将表达式 A －B×C÷D ＋E
∧F 转换为前缀和后缀表达式。（考试范围之外） 5．画出3个结点的二叉树的所有形态。 5种形态
6．二叉树的先序序列为ABCDEF ，中序序列为CBAEDF ，画出该二叉树。
参考答案：
7．按下表中关键字的顺序构造一棵二叉平衡树。（考试范围之外）
( 5, 4, 8, 1, 9, 7, 6, 2, 11, 12, 10, 3 )
8．选取哈希函数H(k) = (3k) MOD 11。用开放地址法处理冲突，d i = i×( (7k) MOD 10 + 1 )，( i = 1, 2,3, …)。试在0~10的散列地址空间中对关键字序列( 22, 41, 53, 46, 30, 13, 01, 67 ) 构造哈希表。
四、算法设计题(每题10分，共10分)
1．写一算法，对带头结点的单链表L实现就地逆置。
单链表结点存储结构定义如下
typedef struct LNode {
int data;
struct LNode *next;
}LNode, *LinkList;
参考答案：
void ConverseList(LinkList &L)
{
LinkList p,q;
p=L->next;
if(p!=NULL) {
q=p->next;
p->next=NULL;
while (q!=NULL)
{
p=q;
q=q->next;
p->next=L->next;
L->next=p;
}
}
}
2007级软件工程专业数据结构（72学时）试题，不适用于各背景专业
