2017年昆明理工大学J010数据结构(同等学力加试)复试仿真模拟三套题
● 摘要
一、应用题
1． 设
阶稀疏矩阵A 有t 个非零元素，其三元组表示为
表示A 才有意义？ 的
个存储单元，用二维数组存储时占用
个单元，
只有当试问：非零元
素的个数t 达到什么程度时用，共占用三元组表
元组）
时，用
【答案】稀疏矩阵A 有t 个非零元素，加上行数mu 、列数皿和非零元素个数tu （也算一个三
表示A 才有意义。解不等式得
2． 线性表有两种存储结构：一是顺序表，二是链表。试问：
（1）如果有，2个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构? 为什么？
（2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构? 为什么？
【答案】（1）应选择链式存储结构。因为它可动态申请内存空间，不受表长度（即表中元素个数）的影响，插入、删除时间复杂度为O （1）。
（2）应选择顺序存储结构。因为顺序表可以随机存取，时间复杂度为O （1）。
3． 用单链表保存m 个整数，节点的结构为（data , link ）, 且点而删除其余绝对值相等的节点。
例如若给定的单链表head 如下
删除节点后的head 为
要求
（1）给出算法的基本思想 （2）使用c 或
语言，给出单链表节点的数据类型定义。
语言描述算法，关键之处给出注释。
（3）根据设计思想，采用c 或【答案】（1）算法思想：
（n 为正整数）。现要求
设计一个时间复杂度尽可能高效地算法，对于链表中绝对值相等的节点，仅保留第一次出现的节
（4）说明所涉及算法的时间复杂度和空间复杂度。
定义一个大小为n 的布尔数组flag ，初始时所有的元素都赋值为false , 用来标识遍历过程中是否出现元素绝对值为flag 的节点。然后遍历链表，遍历过程中，每一个当前结点data 域的绝对值，则将flag 位置为真（true ）所对应的flag 位：若为真，则删除该结点；若为假（false ）。
（2）节点的数据结构定义如下：
（3）
全局数组标志节点的绝对值是否出现过
如果此绝对值已经在节点值的绝对值中出现过则删除该节点
否则，将flag 中对应的位置置为true ，并将指针指向下一个元素
，申请大小（4）只遍历一次链表，所以时间复杂度为0 （m ） （m 为单链表中元素的个数）
为n 的数组，所以空间复杂度为0 （n ） （n 为节点绝对值的最大值）。
4． 在多关键字排序时，LSD 和MSD 两种方法的特点是什么？
【答案】（1）最高位优先（MSD ）法
先对最高位关键字进行排序，将序列分成若干子序列，
每个子序列中的记录都具有相同的值，然后，分别就每个子序列对关键字列。
（2）最低位优先先对最低位关键字位关键字
序列参加排序，
但对
法
进行排序，然后对高一级关键字
进行排序，依次重复，直至对最高
进行排序，按值不同再分成若干更小的子序列，依
次重复，直至最后对最低位关键字排序完成，将所有子序列依次连接在一起，成为一个有序子序
排序后便成为一个有序序列。进行排序时，不必分成子序列，对每个关键字都是整个
排序时，只能用稳定的排序方法。另一方面，按LSD 进行排序
时，可以不通过关键字比较实现排序，而是通过若干次“分配”和“收集”来实现排序。
5． 特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能? 为什么？
【答案】特殊矩阵指值相同的元素或零元素在矩阵中的分布有一定规律，因此可以对非零元，将非零元素存储在向量中，元素的下标i 和j 和该素分配单元（对值相同元素只分配一个单元）
元素在向量中的下标有一定规律，可以用简单公式表示，仍具有随机存取功能。而稀疏矩阵是指非零元素和矩阵容量相比很小
且分布没有规律。用十字链表作存储结构自然失去了随机
最差情况下是
因此也失去
存取的功能。即使用三元组表的顺序存储结构，存取下标为i 和j 的元素时，要扫描三元组表，下标不同的元素，存取时间也不同，最好情况下存取时间为了随机存取的功能。
6． 画出同时满足下列两个条件的两棵不同的二叉树。
（1）按前序遍历二叉树的顺序为ABCDE 。
（2）高度为5其对应的树（森林）的高度最大为4。 【答案】（1）满足条件的二叉树如图1所示：
图1
（2）满足条件的二叉树如图2所示：
图2
7． 若森林共有n 个结点和b 条边（b 【答案】森林的n 个结点开始可看做是n 个连通分量，加入一条边将减少一个连通分量。因为树可以定义为无环的图，故加入b 条边将减少b 个连通分量，因而n 个结点b 条边的森林有n-b 棵树。
相关内容
相关标签