数据结构和算法是高考真题。
06-07第一学期期末试卷
试卷代码:03266A授课时间:112
课程名称:数据结构与算法适用对象:本科
一、选择题(从下列问题的四个备选答案中选择一个正确答案，并在答题卡相应位置写下其代码。答案错误或未选，该题不得分。每道小题2分，***24分。)
1.数据结构被正式定义为(K，R)，其中K是数据元素的有限集，R是K上的有限集合..
A.运营b .形象c .店铺d .关系
2.如果线性表采用链式存储结构，则需要内存中可用存储单元的地址。
A.它必须是连续的。有些地址必须是连续的。c .必须是不连续的。连续或不连续都可以
3.如果一个栈的栈入口序列是A、B、C、D、E，那么这个栈的不可能输出序列是_ _ _ _。
A.edcba B.decba C.dceab D.abcde
4.如果队列的入队顺序是1、2、3和4，则队列输出顺序是_ _ _ _。
A.4、3、2、1 B.1、2、3、4 C.1、4、3、2 D.3、2、4、1
5.堆栈和队列的相似之处是_ _ _ _。
A.都是先入后出。b .都是先入先出。
C.只有元素D可以在端点插入或删除。没有* * *共同点。
6.在单链表中，已知Q指向的节点是P指向的节点的前任节点，如果在Q和P之间插入一个S节点，则执行_ _ _ _ _。
A.s-& gt；next = p-& gt；接下来；p->；next = s；B. p->next = s-& gt；接下来；s-& gt；next = p；
C.q->；next = s；s-& gt；next = p；D. p->next = s；s-& gt；next = q；
7.设字符串S1 =' abcdefg '，S2 =' pqrst '，函数con (x，Y)返回X和Y字符串的连接字符串，函数subs (s，I，j)返回从序列号I的字符开始的j个字符组成的字符串S的子串，函数len (s)返回字符串S的长度，然后con
A.BCDEF b . BCDEFG c . BCPQRST d . BCDEFEF
8.如果一棵高度为h的二叉树上只有度为0和度为2的节点，那么这样一棵二叉树所包含的节点数至少为_ _ _ _。
A.2h b . 2h-1 c . 2h+1d . h+1
9.二叉树的前序遍历节点的访问顺序是abdgcefh，中间遍历节点是dgbaechf，后续遍历节点是_ _ _ _。
A.bdgcefha b . gdbecfha c . bdgaechf d . gdbehfca
10.一个有六个顶点的无向图应该至少有_ _ _条边才能保证它是一个连通图。
A.5 B. 6 C. 7 D. 8
11.用顺序搜索法搜索长度为n的线性表时，每个元素的平均搜索长度为-。
A.注意:n/2 c .(n+1)/2d .(n-1)/2
12.在排序法中，从无序序列中选取元素，放入有序序列的一端(注:开头为空)的方法称为_ _ _ _。
A.希尔排序b .归并排序c .插入排序d .选择排序
填空(请在每道小题横线上填写正确内容，每道空格1分***7分。)
1.在树形结构中，根节点没有节点，其他每个节点只有一个前任节点。
2.当通过气泡对n个元素的序列进行排序时，最少的比较次数是。
3.空字符串为，其长度等于0。
4.有n个节点的完全二叉树有一个叶节点。
5.在哈希函数H(key)=key% p中，应该取p。
6.已知模式串T = ' abcaabbabc '，KMP方法得到的每个字符对应的下一个函数值为。
三、简答题(本大题***3小题，每小题5分，***15分)
1.线性表的处理一般采用两种存储结构，顺序存储结构和链式存储结构。试着描述在什么情况下使用顺序列表比使用链表更好。
2.简述什么是稳定排序，什么是不稳定排序。
3.下面中缀表达式对应的后缀形式是什么？
(1) (A + B) * D + E / (F + A * D) + C
(2)A & amp；& ampB||！(E & gtf){注:根据C)的优先级
四。判断题(本大题* * 10，正确的在题后括号内写“T”，错误的在题后括号内写“F”，每道小题1分，* * 10分)。
1.数据元素不是数据的最小单位()。
2.已知二叉树的前序序列和后序序列可以唯一地构造二叉树。( )
3.AOE网是一个加权无环连通图。( )
4.对于要输入的同一组键码，虽然每个键码的输入顺序不同，但得到的二叉查找树是相同的()。
5.一棵树的叶子数必须等于其对应的二叉树的叶子数。( )
6.邻接表只能用于有向图的存储，邻接矩阵适用于有向图和无向图的存储。( )
7.折叠插入排序稳定。( )
8.在哈希方法中，使用双重哈希函数可以确保绝对没有冲突。( )
9.消除递归不一定需要使用stack()。
10.堆排序是交换排序的一种。( )
五、应用题分析(本题***26分，1，4子题各6分，2、3子题各7分)
1.读后感下面这个程序段的作用是什么？(6分)
S2，tmp，seq stack s 1；
数据类型x；//堆叠tmp和S2已经初始化。
而(！StackEmpty (S1))
{ x = Pop(s 1)；
Push(tmp，x)；
}
而(！StackEmpty (tmp))
{ x = Pop(tmp)；
推(S2，x)；
}
2.一个子系统的通信中可能只出现8个字符，它们出现的概率是0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11。尝试设计霍夫曼编码。(7分)
3.设哈希表为HT[13]，哈希函数为H (key) = key %13。冲突用线性探针重散列法解决，下面的键码序列12，23，45，57，20，03，78，31，15，36列表。画出相应的哈希表，计算等概率下成功搜索的平均搜索长度。(7分)
4.设要排序的排序码顺序为{12，2，16，30，28，10，16 *，20，6，18}，试着用希尔排序法(增量为5，2，668) (6分)写一篇课文
六、算法设计问题(此题***18分，第1项10分，第二项8分)
1.编写一个算法频率来计算输入字符串中包含的不同字符的频率。用适当的测试数据验证了该算法。(10分)
2.在二叉链表表示的二叉树上，试着写一个算法，按层次顺序遍历二叉树，统计树中度数为1的节点数。需要二进制链表的类型定义。(8分)
回答:
06-07第一学期
期末考试参考答案及评分标准
试卷代码:03266A授课时间:112
课程名称:数据结构与算法适用对象:本科
一、选择题(每小题2分，***24分。)
1.D 2。D 3。C 4炸药。B 5。C 6。C
7.D 8。B 9。D 10。A 11。C 12。D
二、填空(65438+每格0分，***7分。)
1.父(或前任)，1
2.n-1
3.没有任何字符的字符串
4.(n+1)/2
5.质数
6.0111223123
三。简答题(每道小题5分，***15分)
1.答:①在顺序存储中，相邻数据元素的存储地址也是相邻的(逻辑和物理合一)；要求存储器中可用存储单元的地址必须是连续的。
优点:存储密度高，存储空间利用率高。缺点:插入或删除元素不方便。
②在链式存储中，相邻的数据元素可以随意存储，但所占用的存储空间分为两部分，一部分存储节点值，另一部分存储代表节点间关系的指针。
优点:插入或删除元素方便，使用灵活。缺点:存储密度低(
序列表适用于静态操作，如搜索；链表适用于插入和删除等动态操作。
如果线性表的长度变化不大，其主要操作是查找，则使用顺序表；
如果线性表的长度变化很大，并且其主要操作是插入和删除，则使用链表。
2.答案:在排序序列中，任意两个相等的关键词Ki=Kj。如果排序前Ki在序列中领先于Kj，排序后Ki在序列中仍领先于Kj，则称使用的排序方法是稳定的；另一方面，如果在排序的序列中有可能使Kj排在Ki前面，就说使用的排序方法不稳定。
3.答:中缀表达的后缀形式如下:
(1)AB+D*EFAD*+/+C+
(2)AB & amp；& ampEF & gt！||
四。判断题(本大题* * 10，正确的在题后括号内写“T”，错误的在题后括号内写“F”，每道小题1分，* * 10分)。
1.T2。F3。T4。F5。F
6.F7。t8。F9。t 10。F
五、应用问题分析(1，4小项各6分，2、3小项各7分)
1.(6分)
答:程序段的作用是利用tmp栈将一个非空栈s1的所有元素复制到一个栈s2中。
2.(7分)
答案:为方便起见，假设各种字符的权重为w = {5，29，7，8，14，23，3，11}。因为n=8，所以要构造的赫夫曼树有m = 2n-1 = 2 * 8-1 = 15个节点。生成的Hoeffmann树如下所示:
霍夫曼码是:概率为0.23的字符码是:00。
概率为0.11的字符码为010。
概率为0.05的字符码是:0110。
概率为0.03的字符编码为:0111。
概率为0.29的字符码是:10。
概率为0.14的字符码为:110。
概率为0.07的字符编码为:1110。
概率为0.08的字符编码为:1111。
3.(7分)
答:使用哈希函数H(key)=key mod 13包括:
H(12)=12，H(23)=10，H(45)=6，H(57)=5，H(20)=7，H(03)=3，H(78)=0，H(31)=5，H(15)=2，H(36)=10
通过线性探索制作表格；
0 1 2 3 4 5 6 7 8 9 10 11 12
78 15 03 57 45 20 31 23 36 12
1 1 1 1 1 1 4 1 2 1
成功搜索的平均长度为:
ASL = 1/10(1+1+1+1+4+1+2+1)= 14/10
4.(6分)
答:希尔排序(增量为5，2，1)。
六、算法设计题(1项10分，第二项8分)
1.(10分)
包括& ltiostream.h & gt
包括“string.h”
int char number = 128；
空频(弦& amps，int C[ ]){
for(int I = 0；我& ltcharnumberi++)C[I]= 0；
for(I = 0；我& lts.length()。i++)C[atoi(s[I])]++；
for(I = 0；我& ltcharnumberi++)
if(C[I]& gt；0)cout & lt；& lt"(" & lt& lt我& lt& lt”):" t " & lt& ltc[I]& lt；& lt”\ t”；
}
2.(8分)
类型定义(省略)
Int Level(BiTree bt) //分层遍历二叉树，统计度数为1的节点数。
{
int num = 0；//num统计度为1的节点数
如果(bt){
queue init(Q)；QueueIn(Q，Bt)；//Q是以二叉树节点指针为元素的队列。
而(！QueueEmpty(Q))
{ p = queue out(Q)；printf(p-& gt；数据)；//出队并访问节点
如果(p->；儿童与健康。& amp！p->；rchild ||！p->；儿童与健康。& ampp->；rchild)
num++；//度为1的节点
如果(p->；lchild) QueueIn(Q，p-& gt；l child)；//非空左孩子加入队伍
如果(p->；rchild) QueueIn(Q，p->rchild)；//非空右子加入队伍
}
}
return(数字)；//返回度为1的节点数
}
乙:
06-07第一学期期末试卷
试卷代码:03266B授课时间:112
课程名称:数据结构与算法适用对象:本科
一、选择题(从下列问题的四个备选答案中选择一个正确答案，并在答题卡相应位置写下其代码。答案错误或未选，该题不得分。每道小题2分，***24分。)
1.数据结构被正式定义为(K，R ),其中K是有限的_ _ _ _集合，R是K上有限的关系集合..
A.算法b .数据元素c .数据操作d .逻辑结构
2.在数据结构中，数据结构在逻辑上可以分为_ _ _ _。
A.动态结构和静态结构b .紧凑结构和非紧凑结构
C.线性结构和非线性结构d .内部结构和外部结构
3.下列说法中，正确的是_ _ _ _。
A.线性表的存储结构优于链式存储结构。
二维数组是一个线性表，它的数据元素是线性表。
C.堆栈的操作模式是FIFO。
D.队列的操作模式是FIFO。
4.如果一个栈的堆栈顺序是1，2，3，…，n，其输出顺序是p1，p2，p3，…，pn，如果p1=n，那么pi是_ _ _ _。
A.ib.n = i.c.n-i+1 d .不确定。
5.判断一个循环队列qu(最大元素为m)为空的条件是_ _ _ _。
A.屈-& gt；front = = QU-& gt；后方b .曲-& gt；前面！= QU->；后面的
C.屈-& gt；front = =(QU-& gt；rear+1)% m d . QU->；前面！=(QU->；后方+1)%m
6.在单链表中，已知P指向的节点不是最后一个节点。如果S指向的节点插在P之后，那么会执行_ _ _ _。
A.s-& gt；next = p；p->；next = s；B. s->next = p-& gt；接下来；p->；next = s；
C.s-& gt；next = p-& gt；接下来；p = s；D. p->next = s；s-& gt；next = p；
7.字符串是一种特殊的线性表，其特殊性体现在_ _ _ _。
A.它可以顺序存储。数据元素是一个字符。
C.链接存储数据元素可以是多个字符。
8.已知二叉树的后序遍历序列是dabec，中序遍历序列是debac，前序遍历序列是_ _ _ _。
A.acbed B. decab C. deabc D. cedba
9.对于一棵有m片叶子，n个节点，深度为h的完全二叉树，那么_ _ _ _。
A.n = h+m b . h+m = 2n c . m = h-1d . n = 2h-1
10.有n个顶点的无向图最多有_ _ _ _条边。
A.n b n(n-1)c n(n-1)/2d 2n
11.顺序搜索法适用于存储结构为_ _ _ _的线性表。
A.散列存储b .顺序存储或链接存储
C.压缩存储d .索引存储
12.在待排序元素顺序基本有序的前提下，最高效的排序方法是_ _ _ _。
A.插入排序b .选择排序c .快速排序d .合并排序
填空(请在每道小题横线上填写正确内容，每道空格1分***7分。)
1.在线性结构中，第一个节点是前驱节点，其他每个节点只有1个前驱节点。
2.在未加权图G的邻接矩阵中，若A[i][j]等于1，则等于A[j][i] =。
3.根据二叉树的定义，有三个节点的二叉树有不同的形式。
4.空格字符串意味着它的长度等于。
5.在哈希存储中，填充因子α的值越大，存储元素时就越有可能出现冲突。
6.已知模式串T =' abacabaaad '，用KMP方法得到的每个字符对应的下一个函数值为。
三、简答题(本大题***3小题，每小题5分，***15分)
1.比较静态搜索和动态搜索的主要区别，它们的基本操作是什么？
2.逻辑结构和存储结构是什么？
3.在n (n >: 1)的系统中，不同形状的树中，深度最小的树的深度是多少？它有多少叶子和非叶子节点？
四。判断题(本大题* * 10，正确的在题后括号内写“T”，错误的在题后括号内写“F”，每道小题1分，* * 10分)。
1.每个数据结构都应该有三个基本操作:插入、删除和搜索()。
2.完全二叉树不一定是完全二叉树。( )
3.加权连通图的最小生成树的权重之和必须小于其它生成树的权重之和。( )
4.任意二叉查找树的平均搜索时间小于顺序搜索法搜索同一节点的序列表的平均搜索时间。( )
5.线性链表中的所有节点必须是同一类型。( )
6.用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，占用的存储空间只与图中的顶点数有关，而与图的边数无关()。
7.在哈希方法中解决冲突时，加载因子必须在(0，1)之间。( )
8.如果任何关键活动被延迟，整个项目将被延迟。( )
9.平衡二叉树的左右子树深度之差的绝对值不应超过1。( )
具有10.n个节点的有向图必须是强连通的，如果它有n (n-1)条边。( )
五、应用题分析(本题***26分，1，4子题各6分，2、3子题各7分)
1.下面这个算法的作用是什么？(6分)
链表演示(链表L)
{// L是一个无头节点单链表。
ListNode *Q，* P；
如果(L & amp& ampl-& gt；下一个){
q = L；
L = L-& gt；接下来；
p = L；
while(P->；下一个)P = P-& gt；接下来；
p->；next = Q；q->；next = NULL
}
返回L；
}
2.将给定的图简化成最小生成树需要从顶点1开始。(7分)
3.设哈希表为HT[13]，哈希函数为H (key) = key %13。用双哈希法解决冲突，列表如下键码序列12，23，45，57，20，03，78，31，15，36。再散列函数是RH(key)=(7 * key)% 10+1，求下一个地址的公式是hi =(hi-1+RH(key))% 13，h1 = h (key)。画出相应的哈希表，计算等概率下成功搜索的平均搜索长度。(7分)
4.设要排序的排序码顺序为{12，2，16，30，28，10，16 *，20，6，18}，用快速排序法写出每次排序的结果。(6分)
六、算法设计问题(此题***18分，第1项10分，第二项8分)
1.试着设计一个满足以下要求的查找操作函数Locate。有一个带头节点的双向链表L，每个节点有四个数据成员:指向前一个节点的指针llink、指向后一个节点的指针rlink、存储字符数据的成员数据和访问频率freq。所有节点的频率最初为0。每当对链表进行Locate(L，x)操作时，元素值为x的节点的访问频率freq增加1，将该节点前移并链接到访问频率相同的节点，这样链表中的所有节点按访问频率降序排列，使得频繁访问的节点总是靠近头部。(10分)
2.设置一个以二叉链表为存储结构的二叉树，设计一个算法，交换二叉树中所有节点的左右子树。需要二进制链表的类型定义。(8分)
回答:
06-07第一学期
期末考试参考答案及评分标准
试卷代码:03266B授课时间:112
课程名称:数据结构与算法适用对象:本科
一、选择题(每小题2分，***24分。)
1.B2。C3。B4。C5。一个6。B
7.b8。d9。d 10。c 11。b 12。A
二、填空(65438+每格0分，***7分。)
1.没有人
2.1
3.5
4.字符串中的字符都是空格，空格的个数
5.大的
6.0112123422 。
三、简答题(本大题***5小题，每小题5分，***15分)
1.答:两种搜索方式的最大区别在于:
静态查找方法不修改查找表；当动态搜索不成功时，将节点插入查找表，这意味着可以修改查找表；
静态查找的基本操作是建表、查表和读表元素。除了上述基本操作，动态搜索还有初始化、插入和删除操作；
2.答:根据数据元素之间关系的不同特点，通常有以下四种基本结构:(1)集合；(2)线性结构；(3)树形结构；(4)图形结构或网络结构。有两种不同的存储结构:顺序存储结构和链式存储结构。
3.答:深度最小的树深度为2。对于这n个节点，除了一个根节点，其他n-1个节点都是叶节点，所以它的深度是2。叶节点数为n-1，非叶节点数为1。
四、对或错(每道小题1分，***10分)
1.(T)2。(F)3。(T)4。(F)5。(吨)
6.(T)7。(F)8。(T)9。(T)10。(吨)
五、应用题分析(本题***26分，1，4子题各6分，2、3子题各7分)
1.(6分)
答:这个算法的作用是:去掉起始节点链接到终止节点后，成为新的终止节点，而原来的第二个节点成为新的起始节点，返回新链表的头指针。
2.(7分)
答:
3.(7分)
答:使用哈希函数H(key)=key mod 13包括:
H(12)=12，H(23)=10，H(45)=6，H(57)=5，H(20)=7，H(03)=3，H(78)=0，H(31)=5，H(15)=2，H(36)=10
用双哈希法做表:hi =(hi-1+RH(key))% 13，hi = h (key)。
0 1 2 3 4 5 6 7 8 9 10 11 12
78 15 03 57 45 20 31 36 23 12
1 1 1 1 1 1 3 5 1 1
搜索成功的平均长度为:ASL = 1/10(1+1+1+1+65438+65438+3+5+65438。
4.(6分)
答:
六、算法设计题(1项10分，第二项8分)
1.(10分)
答:
(1)定义链表结构
struct DoubleListNode {
char数据；
int freq
DoubleListNode * llink，* rlink
};
最初，所有节点的freq字段的值都是0。
(2)定义功能
DoubleListNode * locate(DoubleListNode * f；char & ampx ) {
DoubleListNode * p，* q；
p = f→rlink；/*跳过标题节点*/
而(p！= NULL & amp& ampp→数据！= x)p = p→rlink；/*搜索*/
如果(p ) {
p→freq++；q = p→llink；
p→rlink→llink = q；q→rlink = p→rlink；/*删除p*/
而(q！= f & amp& ampq→freq & lt；p→freq)q = q→llink；
p→llink = q；
p→rlink = q→rlink；q→rlink→llink = p；
q→rlink = p；/*插入p*/
}
返回p；
}
2.(8分)
答:类型定义(略)
void ee Exchange(Bitree bt)//交换二叉树BT所有节点的左右子树。
{
如果(bt)
{ BiTree s；
s = Bt-& gt；lchildBt-& gt；l child = Bt-& gt；rchildBt-& gt；rchild = s；//左右子交换
交换(Bt-& gt；l child)；//交换左子树中所有节点的左右子树。
交换(Bt-& gt；rchild)；//交换右子树上所有节点的左右子树。
}
}