2017年温州大学电子技术之数据结构复试实战预测五套卷
● 摘要
一、应用题
1． 在如图1所示的伙伴系统中，回收两块首地址分别为768及128、大小为的存储块，请画出回收后该伙伴系统的状态图。
图1
【答案】因为
小为
因为所以768和所以首址大小为互为伙伴，伙伴合并后，首址为768，块大的块和首址512、大小为的块合并，成为首址
将其插入可利用空间表中。回其伙伴地址为512、；大小为的空闲块。因为收后该伙伴系统的状态图如图2所示：
图2 回收后该伙伴系统的状态图
2． 特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能? 为什么？
【答案】特殊矩阵指值相同的元素或零元素在矩阵中的分布有一定规律，因此可以对非零元
，将非零元素存储在向量中，元素的下标i 和j 和该素分配单元（对值相同元素只分配一个单元）
元素在向量中的下标有一定规律，可以用简单公式表示，仍具有随机存取功能。而稀疏矩阵是指非零元素和矩阵容量相比很小且分布没有规律。用十字链表作存储结构自然失去了随机
存取的功能。即使用三元组表的顺序存储结构，存取下标为i 和j 的元素时，要扫描三元组表，下标不同的元素，存取时间也不同，最好情况下存取时间为最差情况下是因此也失去了随机存取的功能。
3． 设输入序列为2, 3, 4, 5, 6, 利用一个栈能得到序列2, 5, 3, 4, 6吗? 栈可以用单链表实现吗？
【答案】不能得到序列2, 5, 3, 4, 6。因为根据输入序列，2进栈之后，2出找，3, 4, 5依次进栈。5出栈，此时栈中剩下3, 4。因为4在栈顶，所以4应该比3先出栈，不能得到提供的序列。栈可以用单链表实现，这就是链栈。由于栈只在栈顶操作，所以链栈通常不设头结点。
4． 已知有6个顶点（顶点编号为0--5）的有向带权图G , 其邻接矩阵A 为上三角矩阵，按行为主序（行优先）保存在如下的一维数组中。
要求：
（1）写出图G 的邻接矩阵A 。
（2）画出有向带权图G 。
（3）求图G 的关键路径，并计算该关键路径的长度。
【答案】（1）由题可以画出待定上三角矩阵的结构图如下（图中? 为待定元素）：
可以看出，第一行至第五行主对角线上方的元素分别为5, 4, 3, 2, 1个，由此可以画出压缩存储数组中的元素所属行的情况，如下图所示：
将各元素填入各行即得邻接矩阵：
（2）根据第一步所得矩阵A 容易做出有向带权图G , 如下：
（3）下图中粗线箭头所标识的4个活动组成图G 的关键路径。
由上图容易求得图的关键路径长度为：4+5+4+3 = 16。
5． 证明：具有n 个顶点和多于n-1条边的无向连通图G —定不是树。
【答案】具有n 个顶点n-1条边的无向连通图是自由树，即没有确定根结点的树，每个结点均可当根。若边数多于n-1条，因一条边要连接两个结点，则必因加上这一条边而使两个结点多了一条通路，即形成回路。形 成回路的连通图不再是树。
6． 设LS 是一个线性表，若采用顺序存储结构，则在等概率的前提下，插入一个元素需要平均移动的元素个数是多少? 若元素插
在
【答案】需要分两种情况讨论：
，插入位置0..n ，则平均移动个数为（1）等概率（后插）
（2）若不等概率，则平均移动的元素个数为
7． 假定有下列， 与
之间的概率
为则插入一个元素需要平均移动的元素个数又是多少？ 矩阵（n 为奇数）
如果用一维数组B 按行主次序存储A 的非零元素，问：
（1）A 中非零元素的行下标与列下标的关系；
（2）给出A 中非零元素的下标与B 中的下标R 的关系；
给出利用的下标定（3）假定矩阵中每个元素占一个存储单元且B 的起始地址为
相关内容
相关标签