| 网站首页 | 考试学习 | 英语学习 | 求职 |出国留学 | 资源下载 | 论文中心 | 箐箐校园 | 精品课程 | 网络学院 | 网站留言 |
|
|
||||||||||||||||
|
||||||||||||||||
一、 名词解释(每小题5分，共30分)
1. 描述线性表中三个概念的区别：头指针、头结点、首元结点(第1个元素结点 )。
2. 数据结构
3. 二叉排序树
4. 关键路径
5. 稀疏矩阵
6. 连通图
二、 单项/多项选择题(每空3分，共30分)
1. 具有N个结点的二叉树的二叉链表结构中，指针域为NULL的数目应为( )；
A) N B) 2N
C) N+1； D) 2N+1
2. 假定有T1、T2、T3、T4、T5五个元素进栈，进栈次序为T1T2T3T4T5，不可能 的出栈序列有( )；
A)T1T2T3T4T5 B)T5T4T3T2T1
C)T1T2T5T3T4 D)T3T2T4T5 T1
E)T3T5T2T4 T1 F)T2T4 T3T5 T1
3. 表达式(15-3)*6/3*(20+6)的逆波兰式，正确的是( )；
A)15 3 6 3 20 6-*/*+ B)15 3-6 *3/20 6+*
C)15 3 - 6 3 20 6+*/* D)15 3-6 3*20 6+*/
4. 下列各函数是按照增长率由大至小的顺序排列的是( )；
A) B)
C) D)
5. 已知L是带表头结点的单链表，其P结点既不是首结点(第一结点)，也不是尾 结点：
1) 删除P结点的直接后继结点的语句序列是( )；
2) 删除P结点的语句序列是( )；
3) 删除首结点的语句序列是( )；
4) 删除尾结点的语句序列是( )；
A) P=P→next ;
B) P→next=P ;
C) P→next=P→next→next ;
D) P=P→next→next ;
E) while P !=NULL { P=P→next ;}
F) while P→next !=NULL { P=P→next ;}
G) while P→next !=Q {P=P→next ;}
H) while P→next→next !=Q { P=P→next ;}
I) Q=NULL ;
J) Q=P ;
K) Q=P→next ;
L) P=L ;
M) L=L→next ;
N) free(Q);
6. N个结点的集合，利用二叉排序树查找方法的平均查找长度(ASL)的计算公式 为( )；
A)N+1 B)log2N
C)(N+1)/2 D)1+4 log2N
7. 对下列关键字序列按照起泡排序算法进行排序，则两趟排序后的结果可能为 ( )。
(Kay, Eva, Amy, Roy, Dot, Jon, Kim, Boy)
A)(Amy, Eva, Dot, Jon, Kay, Boy, Kim, Roy)
B)(Amy, Boy, Dot, Eva, Jon, Kay, Kim, Roy)
C)(Eva, Amy, Kay, Dot, Jon, Kim, Boy, Roy)
D)(Eva, Amy, Dot, Roy, Jon, Boy, Kim, Kay)
三、 填空题(每题2分，共20分)
1. 在顺序存储结构的线性表中，插入或删除一个元素需要平均移动 【1】 元 素，具体移动元素个数与 【2】 有关。
2. 假设二维数组A[6][8]，每个元素用相邻的4个字节存储，存储器按字节编址 ，已知A的开始存储位置为100，则数组的存储容量为 【3】 字节；按列优先顺序存储 的元素A[2][5]的第一个字节的地址为 【4】 。
3. 一棵深度为5，18个结点的完全二叉树，编号为10的结点的右儿子的编号 【 5】 ，其双亲结点的编号为 【6】 。
4. 在一棵有14个结点的完全二叉树中，所含叶子结点的数目为 【7】 个。
5. 对稀疏矩阵的压缩存储，一般包括三元组表和 【8】 两种基本方法。如图 (A)所示的稀疏矩阵，试给出它所对应的三元组线性表 【9】 ；
6. 如图(B)所示的有向图，该图有 【10】 个强连通分量。
四、 简答题(每题8分，共40分)
1. 对长度为n的记录序列进行快速排序时，所需进行的比较次数依赖于这n个元 素的初始序列。现假设n=7，试问在最好的情况下需进行多少次比较？请说明理由。
2. 试证明：具有n个结点的二叉树的最小深度为 。
3. 在串操作中，执行以下函数会产生怎样的输出结果？
void demonstrate(){
StrAssign(s, ‘THIS IS A BOOK’);
Replace(s, SubString(s, 3, 7), ‘ESE ARE’);
StrAssign(t, Concat(s, ‘S’));
StrAssign(u, ‘XYXYXYXYXYXY’);
StrAssign(v, SubString(u, 6, 3));
StrAssign(w, ‘W’);
printf(‘t=’, t, ‘v=’, v, ’u=’, Replace(u, v, w));
} //demonstrate
4. 判别下面的一个序列是否为堆。如果不是，则把它调整为堆，画出生成堆的 调整过程(要求记录交换次数最少，且堆顶元素为最小值)。
(12，70，48，86，24，56，30，92，65，38)
5. 试列出如图(C)中全部可能的拓扑有序序列。
图 (C)
五、 综合设计题(每题15分，共30分)
1. 试利用Dijkstra算法求图(D)中从顶点a到其他各顶点间的最短路径，写出执 行算法过程中各步的状态。
图 (D)
2. 假设用于通信的电文只使用A，B，C，D，E，F这六个字母组成，字母在电文 中出现的频率依次为4，2，6，8，3，2。按照要求完成如下任务：
1)试为这6个字母设计哈夫曼编码和等长二进制编码方案，给出两种编码的对照 表。
2)求出这两种编码的带权路径长度WPL，比较两种方案的优缺点。
3)给出哈夫曼树的逻辑结构。
