我要评论pdf文档公众号回复关键字:20240608
单项选择题（共15题，每题2分，共计30分：每题有且仅有一个正确选项）
4 假设有一个链表的节点定义如下：
struct node {
int data;
node* next;
};
现在有一个指向链表头部的指针：node* head。如果想要在链表中插入一个新节点，其成员data的值为42，并使新节点成为链表的第一个节点，下面哪个操作是正确的？（ ）
a node* newnode = new node; newnode->data = 42; newnode->next = head; head = newnode;
b node* newnode = new node; head->data = 42; newnode->next = head; head = newnode;
c node* newnode = new node; newnode->data = 42; head->next = newnode;
d node* newnode = new node; newnode->data = 42; newnode->next = head;
10 假设有一组字符{a,b,c,d,e,f}，对应的频率分别为5%，9%，12%，13%，16%，45%。请问以下哪个选项是字符a,b,c,d,e,f分别对应的一组哈夫曼编码？（ ）
a 1111，1110，101，100，110，0
b 1010，1001，1000，011，010，00
c 000，001，010，011，10，11
d 1010，1011，110，111，00，01
2 相关知识点
1 指针
指针是 c++语言中广泛使用的一种数据类型，运用指针编程是 c++语言最主要的风格之一
指针是一个变量，其值为另一个变量的地址，即，内存位置的直接地址
基础数据类型指针
#include <iostream>
using namespace std;
int main (){
int a = 20; // 实际变量的声明
int *ip; // 指针变量的声明
ip = &a; // 在指针变量中存储 a 的地址
cout << "指针对应变量的值: ";
cout << a << endl;
// 输出在指针变量中存储的地址
cout << "指针变量的值,指针指向的变量的地址: ";
cout << ip << endl;
// 访问指针中地址的值
cout << "指针指向地址对应变量的值(a的值): ";
cout << *ip << endl;
return 0;
}
结构体指针
#include<bits/stdc++.h>
using namespace std;
/*
定义一个结构体，包括姓名和年龄
*/
struct student{
string name;
int age;
};
int main(){
student stu1;//声明 student stu1
stu1.name="张三";// 张三赋值 name
stu1.age=21;// 21赋值 age
student *p1=&stu1;//声明指针p1 指向 &stu1
//指针去结构体内成员需要用 ->
cout<<"姓名:"<<p1->name<<",年龄:"<<p1->age;
return 0;
}
2) 链表的插入
指针指向地址的变换
在newnode1前插入newnode2
/*
1 刚开始head指针指向newnode1
2 需要newnode2的next指向newnode1
3 head指向newnode2
*/
#include<bits/stdc++.h>
using namespace std;
struct node{
int no;
node* next;
};
int main(){
node* newnode1=new node;//newnode1 地址0xbe3ea0 指向 no=1变量
newnode1->no=1;
node* head=newnode1;//指针head 指向 newnode1地址0xbe3ea0
node* newnode2=new node;//newnode2 地址0xbe3ee0 指向 no=2变量
newnode2->no=2;
newnode2->next=head;//newnode2->next 指针指向指针head对应地址0xbe3ea0
head=newnode2;//指针head指向 0xbe3ee0
cout<<head->no<<" "<<head->next->no;
return 0;
}
创建newnode1
node* newnode1=new node;//newnode1 地址0xbe3ea0 指向 no=1变量 c++
newnode1->no=1;
head指针指向newnode1
node* head=newnode1;//指针head 指向 newnode1地址0xbe3ea0
创建newnode2
node* newnode2=new node;//newnode2 地址0xbe3ee0 指向 no=2变量
newnode2->no=2;
newnode2的next指向head指针对应地址
newnode2->next=head;//newnode2->next 指针指向指针head对应地址0xbe3ea0
head指针指向newnode2
head=newnode2;//指针head指向 0xbe3ee0
上述操作在头指针head后和newnode1之间插入了newnode2
3) 哈夫曼编码
哈夫曼树
哈夫曼树是带权路径长度wpl最短的二叉树（最优二叉树）
构造哈夫曼树的wpl为35是最小的
哈夫曼树的构造
1 选剩下的两棵根权值最小的树合并成一棵新树
2 新树的根权值等于两棵合并前树的根权值和
3 重复1和2
例题
4个点，a、b、c、d，权值分别为7、5、2、4
选根权值最小的两棵树2（c）和4（d）合并，新树的根节点为6
选根权值最小的两棵树5（b）和6合并，新树的根节点为11
选根权值最小的两棵树7（a）和11合并，新树的根节点为18
哈夫曼编码
对哈夫曼树的左右孩子进行编码称为哈夫曼编码，通常左边为0，右边为1
例题
有5个字母e,m,c,a,d
这5个字母的使用频度分别为｛e,m,c,a,d｝=｛1,2,3,3,4｝
分析
构造哈夫曼树，并进行编码
用频度为权值生成哈夫曼树，并在叶子上标注对应的字母，在树枝上标注分配码“0”或“1”
对应字母的哈夫曼是编码从根节点开始，每条路径到达叶子结点的01代码排列起来
对应的哈夫曼编码
e：000
m:001
c:01
a:10
d:11
哈夫曼编码性质
只对叶子节点进行编码/解码，编码唯一
哈夫曼编码是前缀编码，任何一个字符的编码都不是另一个字符编码的前缀(只有叶子节点编码)
哈夫曼编码左边为0，右边为1是通常规定，也可以左边为1右边为0，但确定后编码是唯一的
3 思路分析
4 假设有一个链表的节点定义如下：
struct node {
int data;
node* next;
};
现在有一个指向链表头部的指针：node* head。如果想要在链表中插入一个新节点，其成员data的值为42，并使新节点成为链表的第一个节点，下面哪个操作是正确的？（ ）
a node* newnode = new node; newnode->data = 42; newnode->next = head; head = newnode;
b node* newnode = new node; head->data = 42; newnode->next = head; head = newnode;
c node* newnode = new node; newnode->data = 42; head->next = newnode;
d node* newnode = new node; newnode->data = 42; newnode->next = head;
答案 a
插入一个新节点
a
假设head开始指向tmp节点，具体需要如下步骤
//1 创建一个node节点指针 newnode
node* newnode = new node;
//2 通过newnode指针给newnode成员data 赋值为42
newnode->data = 42;
//3 通过newnode指针给newnode成员next 赋值为head指针地址，指向head后续节点tmp
newnode->next = head;
//4 步骤3中新节点已经指向head后续节点tmp，head指向newcode完成插入tmp前
head = newnode;
b
head->data = 42;//和要求不符，要求是对插入节点的data为42
c
//假设head开始指向tmp节点，缺少下面为新节点指向下个节点，tmp被从链表中剔除
newnode->next = head;
d
//新节点没有插入到链表中，需要加入如下语句
head = newnode;
10 假设有一组字符{a,b,c,d,e,f}，对应的频率分别为5%，9%，12%，13%，16%，45%。请问以下哪个选项是字符a,b,c,d,e,f分别对应的一组哈夫曼编码？（ ）
a 1111，1110，101，100，110，0
b 1010，1001，1000，011，010，00
c 000，001，010，011，10，11
d 1010，1011，110，111，00，01
答案 a
根据出现的频率对a,b,c,d,e,f构造一棵哈夫曼树
1 频率最小的a和b合并构造1个节点 5+9=14
2 剩下频率最小的2个字符，c和d合并构造1个节点，12+13=25
3 剩下频率最小的2个字符，14和e(16)合并构造1个节点14+16=30
4 剩下频率最小的2个字符，25和30合并构造1个节点，25+30=55
5 剩下频率最小的2个字符，f(45)和55合并构造一个节点45+55=100
对哈夫曼数进行编码
通常对哈夫曼数上的边左边为0，右边为1进行编码，编码后如下图所示
根据上图哈夫曼编码对选项进行分析
有1个1位的哈夫曼编码，选项中只有a有1个1位的哈夫曼编码，其余都没用1位的哈夫曼编码
核对一下a是否正确
a选项abcdef
1111，1110，101，100，110，0
构造哈夫曼树的abcdef
1100，1101，100，101，111，0
由于左右边规定的0和1是可交换的
我们发现c和d最后1位是相反，所以c和d对应边交换一下即可
e也是最后1为是相反的，并且a和b的倒数第2位也都需要交换，所以14和e对应边也可以交换一下
a和b最后1位也都是相反的，所以a和b对应边也可以交换一下
上述操作后对应下图
对应abcdef的哈夫曼树
构造哈夫曼树的abcdef
1111，1110，101，100，110，0
和选项a一致
a选项abcdef
1111，1110，101，100，110，0
发表评论