2020南京邮电大学Mooc—在线期末考试主观卷qq43656353的博客-

👇为客观卷部分，自取。
2020南京邮电大学Mooc—在线期末考试客观卷

1 ( 20分 )

请对序列进行快速排序，写出前5趟的排序过程，按照如下答题格式进行答题，答题时注意不要漏掉下划线，下划线标错扣分。

答题格式：
第1趟：
第2趟：____________________________
第3趟：____________________________
第4趟：____________________________
第5趟：____________________________

参考答案：

2 ( 20分 )
已知英文字母集合 {A,B,C,D,E,F,G,H}及其权值集合{28,10,24,20,14,27,17,9}，请给出以上英文字母的哈夫曼编码，要求该编码对应的哈夫曼树上左分支编码为0，右分支编码为1，且任意结点的左孩子权值不大于右孩子权值。请按照以下格式答题。

答题格式：
A:____________ B:____________ C:____________
D:____________ E:____________ F:____________
G:____________ H:____________ WPL=____________

参考答案：

3 ( 20分 )
请用克鲁斯卡尔算法画出下图的最小代价生成树，注意按照给定的答题格式进行答题，给出最小代价生成树的生成过程。


参考答案

4 ( 20分 )
给定一个长度为11的散列表ht如下所示，采用双散列法解决冲突，两个散列函数分别为：
h1(key)=key%11
h2(key)=key%9+1
请向散列表依次插入关键字为71,24,56,89的集合元素，给出插入完成后的散列表。

参考答案：

5 ( 20分 )
请给出下图的深度优先遍历序列和宽度优先遍历序列，注意图上边的权值代表边的优先级（值越小则优先权越高），在遍历过程中优先选择权值大（即值小）的边进行结点的访问，不按照指定优先级规则进行遍历的答案不得分。

答题格式：
深度优先遍历序列（以9为起点）：_________________________________
宽度优先遍历序列（以5为起点）：_________________________________
参考答案

6 ( 20分 )
向下图二叉平衡树依次插入关键字为56,63,2,65,18的元素，请画出二叉平衡树的构造过程，注意需要画出每插入一个关键字后的树形，共计5个，答题时请按照如下格式进行答题。（数据结构B考生可跳过）

参考答案

7 ( 20分 )
已知稀疏矩阵A[8][7]中非零元个数为8，稀疏矩阵如下所示：

0 49 0 0 0 0 0
35 0 0 0 0 0 0
0 0 0 0 0 11 0
0 0 0 0 42 0 0
0 0 0 0 19 0 0
0 32 0 0 0 0 0
0 0 0 0 91 0 0
0 0 0 0 0 89 0

请给出（1）该稀疏矩阵的行三元组表、（2）用于快速转置的num数组和（3）k数组

参考答案

8 ( 20分 )
请完成下列算法，将两个非空有序链表L1和L2逆序合并至新链表L。
例如给定两个有序链表（默认升序）：
3->4->6 和 2->7->9，逆序合并的结果是：9->7->6->4->3->2
单链表的类型定义如下：

typedef struct node {        ElemType element; struct Node *link; }Node; typedef struct {        Struct node * first; int n; }SingleList;    SingleList* ReversedMerge(SingleList *L1, SingleList*L2, SingleList* L) { Init(L);//假设L非空，初始化新链表L Node* p1 = L1->first; Node* p2 = L2->first; while(__________(1)___________) {        Node* p = L->first; if(p1->element<=p2->element) {               Node * q = (Node*)malloc(sizeof(Node));            q->element =______(2)_____;               q->link = ____(3)____; ________(4)________;               p1 = p1->link; } else {               Node * q = (Node*)malloc(sizeof(Node));            q->element = ________(5)_________;               q->link = p;               L->first = q;               p2 = p2->link; } } while(p1!=NULL) {               Node * q = (Node*)malloc(sizeof(Node));            q->element = p1->element;               q->link = p;               L->first = q;               p1 = p1->link; } while(p2!=NULL) { Node * q = (Node*)malloc(sizeof(Node));            q->element = p2->element;               q->link = p;               L->first = q;               p2 = p2->link; } return &L; } 

参考答案

SingleList* ReversedMerge(SingleList *L1, SingleList*L2, SingleList* L) { Init(L);//假设L非空，初始化新链表L Node* p1 = L1->first; Node* p2 = L2->first; while(__________p2!=NULL && p1!=NULL___________) {        Node* p = L->first; if(p1->element<=p2->element) {               Node * q = (Node*)malloc(sizeof(Node));            q->element =______p1->element_____;               q->link = ____p____;               ____L->first = q;____;               p1 = p1->link; } else {               Node * q = (Node*)malloc(sizeof(Node));            q->element = ____p2->element_________;               q->link = p;               L->first = q;               p2 = p2->link; } } 

9 ( 20分 )
请完成下列算法缺少的代码块，将两个有序顺序表L1和L2逆序合并至L（逆序合并的含义同上题）。

参考答案

if (L1->element[i1]>=L2->element[i2]) { L->element[i] = L1->element[i1]; i1--; i++; } else { L->element[i] = L2->element[i2]; i2--; i++; } while(i1>=0) { L->element[i] = L1->element[i1]; i1--; i++; } while(i2>=0) { L->element[i] = L2->element[i2]; i2--; i++; } 

10 ( 20分 )
给定一棵二叉树，请完成下列算法交换左右子树。

void Exchange(BTree bt) { (1) ; } void Exchange (BTNode* t) { if(!t) return;  BTNode* temp = t->LChild; (2) ; t->RChild = temp; (3) ; (4) ; } 

参考答案

void Exchange(BTree bt) { Exchange (bt->root); } void Exchange (BTNode* t) { if(!t) return; BTNode* temp = t->LChild; t->LChild = t->RChild; t->RChild = temp; Exchange(t->LChild); Exchange(t->RChild); } 

关于南邮mooc 的作业已经收尾，后续会陆续上传关于数据结构的整理的复习资料！，请需要的小伙伴关注一下动态！你的随手鼓励，是我不断创作的最大动力！感谢🙏

👇为客观卷部分，自取。
2020南京邮电大学Mooc—在线期末考试客观卷