文章目录
- 2020年4月
- 应用题
- 算法设计题
- 2020年10月
- 应用题
- 算法设计题
- 2021年4月
- 应用题
- 算法设计题
- 2021年10月
- 应用题
- 算法设计题
- 2022年4月
- 应用题
- 算法设计题
- 2022年10月
- 应用题
- 算法设计题
2020年4月
应用题
-
有二叉树如题29图所示,写出该二叉树的先序遍历、中序遍历和后序遍历序列。
-
如题30图所示的图结构,请写出以10为源点的广度优先搜索得到的顶点访问序列,并画出搜索过程图。(同等情况下,值小的结点优先访问)
-
设散列表的长度为11,散列丽数h(key)=key mod 11,采用线性探查法解决冲突。从空表开始,依次插人下列关键字值序列:80,40,7,18,13,2,请建立散列表。
-
依次输人键值序列:30,10, 20,50,40,60,构建二叉排序树,要求给出构建过程。
https://www.bilibili.com/video/BV1Tk4y117fs?from=search&;seid=15419245847752740376&spm_id_from=333.337.0.0
答 （博主的答案，没找到自考办给的官方答案，如果有小伙伴找到了辛苦下方评论留下地址） ：
- 对序列(45,38,66 ,90,88,10,25,45)进行冒泡排序,写出前三趟排序结果。
算法设计题
- 试写出二分查找的非递归算法。
int SearchBin(SqTable T, KeyType key) {
/**
* 在有序表T中，用二分查找键值等于key的元素
* 变量low、high分别标记查找区的下界和上界
*/
int low, high;
low = 1;
high = T.n;
// low和high的区间长度不为0时继续查找
while (low <= high) {
// low+high本应该还要进行一个向下取整的，但是自考办给的答案忽略了那我们也忽略floor。
mid = (low + high) / 2; // 对区间进行折半
if (key == T.elem[mid].key) {
return mid;
} else if (key < T.elem[mid].key) {
high = mid - 1; // 在前半区间查找
} else {
low = mid + 1; // 在后半区查找
}
}
return 0;
}
- 已知丽数swap(R[min],R[i])功能是将记录R[min]和R[i]交换。试写出直接选择排序算法。
void SelectSort(List R,int n) {
int min, i, j;
// 每次循环，选出一个最小值
for (i = 1; i <= n-1; i++) {
min = i; // 假设第i个记录值最小
for (j = i+1; j <= n; j++) {
if (R[j].key < R[min].key) {
min = j; // 记录下键值较小记录的下标
}
if (min != i) {
swap(R[min], R[i]); // 将最小键值记录和交换第i个记录交换
}
}
}
}
2020年10月
应用题
1.题29图给出了一个稀疏矩阵A，请写出该稀疏矩阵的三元组表。
答：
（（0，1，5），（2，1，-1），（2，3，7），（3，1，6），（4，4，9），（5，5，8））
2.已知二叉树如题30图所示，请将该二叉树转换为对应的森林。
答：
3.设某通信系统中一个待传输的文本有6个不同字符，它们的出现频率分别是0.5、0.7、1.4、2.2、2.4、2.8。试画出哈夫曼树，并给出每个字符的哈夫曼编码。（要求任一结点的左孩子权值小于右孩子）
答：
出现频率为0.5的字符编码为1000
出现频率为0.7的字符编码为1001
出现频率为1.4的字符编码为101
出现频率为2.2的字符编码为00
出现频率为2.4的字符编码为01
出现频率为2.8的字符编码为11
4.选定散列函数为H(key) = key mod 13，实用链地址法建立值为 26，41，25，05，07，15，12，49，51，31，62 的散列表。
答：
5.对于给定的一组键值：83，40，63，13，84，35，96，57，39，79，61，15，请分别写出直接选择排序和冒泡排序的第一趟排序结果。
答：
直接选择排序：13，40，63，83，84，35，96，57，39，79，61，15
冒泡排序：40，63，13，83，35，84，57，39，79，61，15，96
算法设计题
1.写出一个将线性表的顺序表存储方式（数组a，表长为n）改成单链表存储方式（其头结点由头指针head指向）的算法。设函数头为：Node * CreateLinkedList(DataType a[], int n)
答：
Node * CreateLinkedList(DataType a[], int n) {
head = (Node *)malloc(sizeof(Node)); // (1分)
head -> next = NULL; // (1分)
for (i = n; i > 0; i--) { // (1分)
p = (Node *)malloc(sizeof(Node));
p -> data = a[i - 1];
p -> next = head -> next;
head -> next = p; // 整个for循环内容(3分)
}
return head; // (1分)
}
2.以二叉链表作存储结构，请写出二叉链表类型定义；利用二叉树遍历的递归算法，试编写求二叉树高度的算法。
答：
// 二叉链表类型定义如下：
typedef struct btnode {
DataType data;
struct btnode *lchild, *rchild;
} * BinTree; // (2分)
// 求二叉树的高度的算法如下：
int Height(BinTree bt) {
int lh, rh; // (1分)
if (bt == NULL) return 0; // (1分)
lh = Height(bt -> lchild); // (1分)
rh = Height(bt -> rchild); // (1分)
return 1 + (lh > rh ? lh : rh); // (1分)
}
2021年4月
应用题
1.设一个链栈的输入序列为A、B、C，请问共有几种可能的输出序列？试写出所得到的所有可能的输出序列。
答：
共有5种可能的输出序列 (1分)
它们分别是：ABC、BCA、BAC、CBA、ACB【每答出一个1分】
2.假设一棵二叉树的中序序列与后序序列分别为：B A C D E F G H 和 B C A E D G H F,请画出该二叉树。
答：
3.用Kruskal方法求题31图所示的图的最小生成树。（要求给出求解过程）
答：
4.根据二叉排序树的插入算法，从空树开始建立键值序列{ 50，48，24，55，53，90 }的二叉排序树，要求给出建立过程
答 （博主的答案，没找到自考办给的官方答案，如果有小伙伴找到了辛苦下方评论留下地址） ：
5.对于给定的一组键值：25，11，22，34，5，44，76，61，100，3，14，120，请分别写出直接插入排序和冒泡排序的第一趟排序结果。
答 （博主的答案，没找到自考办给的官方答案，如果有小伙伴找到了辛苦下方评论留下地址） ：
直接插入排序：11，25，22，34，5，44，76，61，100，3，14，120
冒泡排序：11，22，25，5，34，44，61，76，3，14，100，120
算法设计题
1.在单链表存储结构中，线性表的表长等于单链表中数据元素的结点个数，即除了头结点以外的结点的个数。通常通过头指针head来访问一个单链表。已知单链表结构如下：
typedef struct node {
DataType data;
struct node * next;
} Node, * LinkList;
设计求表长的算法，要求算法返回表长。
答：
暂无
2.以二叉链表作存储结构，请设计算法求二叉树的结点的个数。
答：
暂无
2021年10月
应用题
1.设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的站台，若列车2最先开出，则列车出站可能的顺序有几种？并写出这四辆列车所有可能的出站顺序。
答 （博主的答案，没找到自考办给的官方答案，如果有小伙伴找到了辛苦下方评论留下地址） ：
若列车2最先开出站，则列车出站可能的顺序有五种。
分别是：
2134
2143
2314
2341
2431
2.将题30图所示的森林转换成二叉树。
答：
3.写出题31图所示的有向带权图的邻接矩阵。
答：
4.已知题32图所示的二叉排序树中各结点的值分别为1~9，请写出图中结点A~I所对应的值
答：
5.已知键值序列 { 11，2，13，26，5，18，4，9 }，设散列表表长为13，散列函数H(key) = key mod 13,处理冲突的方法为线性探测法，请给出散列表。
答：
算法设计题
1.读入 n = 100个整数到一个数组中，写出实现将该组数进行逆置的算法，并分析算法的空间复杂度。
答：
2.试写出二分查找的递归算法。
答：
2022年4月
应用题
1.二叉树的五种基本形态如题29图所示。
问1：子树用什么形状表示？
问2：分别写出题29-1图、题29-2图和题29-5图的形态
答：
2.给定无向图如题30图所示。
问1：计算D(v1)和D(v2)
问2：写出以顶点v0为起点到v3的所有简单路径。
答：
3.给定一组键值 { 45，38，66，90，88，10，25，45 } ，假设在排序过程中，前4个记录已按键值递增顺序重新排列，构成了一个有序序列为 { 38， 45， 66， 90 }。
问1：请写出应用直接插入排序方法对剩余键值排序的排序过程。
问2：直接插入排序方法是否稳定？
答：
4.设有m个顶点的无向图G，采用邻接矩阵作存储结构，在邻接矩阵上判断下列有关问题，给出简单的算法描述。
问1：图中有多少条边？
问2：任意俩个顶点i和j是否有边相连？
问3：任意一个顶点的度是多少？
答：
5.已知散列函数为H(key) = key mod 7,构造散列表如题33表，并用线性探测法解决冲突。若要用该散列表查找元素 25，32，68，请分别给出所需的比较次数。
答：
算法设计题
1.写出实现对一个n * n阶矩阵进行转置的算法。
答：
2.已知二叉链表的类型定义如下：
typedef struct btnode {
DataType data;
struct btnode *lchild, *rchild;
} * BinTree;
假设visit(bt)是一个已定义的过程，其功能是访问指针bt所指结点。设计在二叉链表上的先序遍历算法和中序遍历算法。
答 （博主的答案，没找到自考办给的官方答案，如果有小伙伴找到了辛苦下方评论留下地址） ：
//先序遍历【根左右】
void preOrder(BinTree bt) {
if (bt !== NULL) {
visit(bt);
preorder(bt -> lchild);
preorder(bt -> rchild);
}
}
//中序遍历【左根右】
void midOrder(BinTree bt) {
if (bt !== NULL) {
preorder(bt -> lchild);
visit(bt);
preorder(bt -> rchild);
}
}
2022年10月
应用题
1.题29-1图和题29-2图为俩种形态的二叉树。
问1：题29-1图、题29-2图各属于何种类型的二叉树？
问2：二叉树通常有哪俩类存储结构？
答：
2.无向图如题30图所示。
问1：列出所有简单回路。
问2：写出邻接矩阵。
答：
3.设待排序的键值为 45，38，66，90，88，10，25，45。利用冒泡排序算法进行排序，已知第一趟排序后的键值为：38，45，66，88，10，25，45，90，请写出后续每趟排序的结果。
答：
4.设序列 { d c b a h e i f g } 和 { a b c h d i e f g } 分别是一棵二叉树的先序序列和中序序列，请画出该二叉树。
答：
5.给定表（Jan, Feb, Mar, Apr, May, Jul）。散列表的地址空间为 0 ~10，设散列函数H(x) == ⌊i / 2⌋，其中i为键值中第一个字母在英语字母表中的序号，要求画出以线性探测法解决冲突的散列表。
博主额外补充：⌊⌋符号是向下取整的意思，丢弃结果的小数部分。
答：
算法设计题
1.设计算法在整型数组A[n]中查找值为k的元素，若找到，则输出其位置 i(0 <= i <= n - 1)，否则输出 -1 作为标志。
答：
2.设计算法按先序次序打印二叉树T中叶子结点的值。
答：
