数据结构的习题（C语言版）
2024-05-21
1. 数据结构的习题（C语言版）
第一个问题，分析下要求，可以知道要做的事情是合并两个数组到一个数组里去，数组C的长度是AB之和。表C的第一个字符不是A的第一个字符就是B的第一个字符。因此接下来要做的事情就是做一个长度为AB之和的循环，每一次找出A或B中的最小元素，存到C里面去，循环结束，C就自动有了。 第二个问题，有时间和空间的要求，不太容易，只有更好，没有最好。不过提供一个思路。可以首先扫描整个数列，将奇数偶数的位置和个数标注出来，存在一个数列中。例如数列奇 奇 偶 奇 奇，可以得到奇数个数为4，位置为[0,1,3,4]，偶数为1，位置为[2]，因此要生成的数列中前4个必定为奇数，而题目中没有对大小的要求，因此只用将偶数与最后面的奇数对换位置即可。对换的次数即为偶数的个数。 大概思路如此，不过有很多方法可以高效的存储和计算，具体实现，希望你能亲自琢磨下，还可以巩固一下C技巧。 祝好，有问题可以探讨。
2. 急需数据结构C语言版（清华大学出版社）的期末考试试题及答案
《数据结构》期末考试试卷（ A ）
一、 选择题（每小题2分，共24分）
1．计算机识别、存储和加工处理的对象被统称为( A )
A.数据 B.数据元素
C.数据结构 D.数据类型
2．栈和队列都是（ A ）
A．限制存取位置的线性结构 B．顺序存储的线性结构
C．链式存储的线性结构 D．限制存取位置的非线性结构
3．链栈与顺序栈相比，比较明显的优点是( D )
A.插入操作更加方便 B.删除操作更加方便
C.不会出现下溢的情况 D.不会出现上溢的情况
4．采用两类不同存储结构的字符串可分别简称为( B )
A.主串和子串 B.顺序串和链串
C.目标串和模式串 D.变量串和常量串
5． 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是：B
A. 110 B .108
C. 100 D. 120
6．串是一种特殊的线性表，其特殊性体现在：B
A.可以顺序存储 B .数据元素是一个字符
C. 可以链接存储 D. 数据元素可以是多个字符
7．设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为： C
A. 2h B .2h-1
C. 2h+1 D. h+1
软件开发网
8．树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把 由树转化得到的二叉树叫做这棵树对应的二叉树。下列结论哪个正确？ A
A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同
B .树的后根遍历序列与其对应的二叉树的后序遍历序列相同
C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同
D. 以上都不对
9．一个有n个顶点的无向图最多有多少边？C
A. n B .n(n-1)
C. n(n-1)/2 D. 2n
10．在一个图中，所有顶点的度数之和等于所有边数的多少倍?C
A. 1/2 B .1
C. 2 D. 4
11．当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为（ A ）
A．左子树的叶子结点 B．左子树的分支结点
C．右子树的叶子结点 D．右子树的分支结点
软件开发网
12．对于哈希函数H(key)=key%13,被称为同义词的关键字是( D )
A.35和41 B.23和39
C.15和44 D.25和51
二、已知某棵二叉树的前序遍历结果为A,B,D,E,G,C,F,H,I,J，其中中序遍历的结果为D,B,G,E,A,H,F,I,J,C。请画出二叉的具体结构。（注意要写出具体步骤）（10分）
原理见课本128页
三、有图如下，请写出从顶点c0出发的深度优先及宽度优先遍历的结果。(10分)
深度优先；C0-C1-C3-C4-C5-C2
宽度优先：C0-C1-C2-C3-C4-C5
四、有图如下，按Kruskal算法求出其最小生成树。要求写出完整的步骤。（10分）
原理见课本250页
五、给定线性表（12，23，45，66，76，88，93，103，166），试写出在其上进行二分查找关键字值12，93，166的过程。并写出二分查找的算法。（20分）
0 1 2 3 4 5 6 7 8
12 23 45 66 76 88 93 103 166
过程：
mid=(0+8)/2=4
high=3,low=0 mid=1
high=0,low=0 mid=0（找到12）
high=8,low=5,mid=6（找到93）
high=8,low=7,mid=7
high=8 low=8 mid=8
算法：见课本84页上
六、知单链表的结点结构为
Data next
下列算法对带头结点的单链表L进行简单选择排序，使得L中的元素按值从小到大排列。
请在空缺处填入合适的内容，使其成为完整的算法。 (可用文字说明该算法的基本思想及执行的过程，10分)
void SelectSort(LinkedList L)
{
LinkedList p,q,min;
DataType rcd;
p= (1) ;
while(p!=NULL) {
min=p;
q=p->next;
while(q!=NULL){
if( (2) )min=q;
q=q->next;
}
if( (3) ){
rcd=p->data;
p->data=min->data;
min->data=rcd;
}
(4) ;
}
}
本题不会。嘿嘿。。。。
七、一个完整的算法应该具有哪几个基本性质？分别简要说明每一性质的含意。(5分)
输入：
四个基本性质：1.输入：有零个或多个有外部提供的量作为算法的输入
2：输出：算法产生至少一个量作为输出
3.：确定性：组成算法的每条指令是清晰的，无歧异的。
4.：有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的
八、何谓队列的"假溢"现象？如何解决？（5分）
队列的假溢现象是指数组实现的顺序队列中，队尾指针已到达数组的下表上界产生上溢而队头指针之前还有若干 空间闲置的现象。解决的办法之一是利用循环队列技术使数组空间的首尾相连。
九、说明并比较文件的各种物理结构。（6分）
3. 关于数据结构（C语言）的几个题
1.
随意画几个二叉树就知道了，这里空链域用ε表示，数一数结点个数与ε个数就知道是n+1了
2.
具体过程在图中给出。
3.
第一步将数据（假设为e）放入s的data中；
第二步s的后继指向q的后继节点；
第三步q的后继指向s
4.
查找72只需2步：
第一步：设立low、high与mid指针，将72与mid指向的值即48比较；
第二部：72比48大，low指向mid+1，重新算出mid，指向72，再与72比较，即查找成功。
最多比较次数参考严蔚敏《数据结构》第九章 查找 220页。
5.
例如图中这棵树，假设i=2，2i=4不大于n，2i+1=5大于n，所以2这个结点没有右子树。
6.
顺序栈的类型定义：
typedef struct{ char *base; //也可用ElemType，只要定义了就行 char *top; int stacksize;}SqStackTp; //注意名字要和主函数里的统一运行结果：
ABCDEFGHIJKLM
MLKJIHGFEDCBA
结果详解：
在这里将'A'到'A'+12='M'进栈同时输出
for(ch=’A’;ch<=’A’+12;ch++)
{ Push(&sq,ch);
printf(“%c”,ch);
}
在这里将'A'到'M'出栈同时输出
while(!EmptyStack(sq))
{ Pop(&sq,&ch);
printf(“&c”,ch);
} printf(“\n”);
由于栈是后进先出，所以就有这样的结果
7.
void converse(int n,int d){ SqStack S; //新建一个栈 InitStack(S); //初始化栈 int k,e; while(n>0){ k=n%d; push(S,k); n=n/d; }//将余数进栈 while(S.top!=S.base){ pop(S,e); printf("%1d",e); }//输出结果}
8.
先序遍历：ABCDEF
中序遍历：BCDAFE
后序遍历：DCBFEA
4. 谁有数据结构的期末试题，借我参考下马上考试了
A：
06－07第一学期期末考试试卷
试卷代码：03266A 授课课时：112
课程名称：数据结构与算法 适用对象：本科
一、单项选择题(从下列各题四个备选答案中选出一个正确答案，并将其代号写在答题纸相应位置处。答案错选或未选者，该题不得分。每小题2分，共24分。)
1.数据结构被形式地定义为(K,R)，其中K是数据元素的有限集，R是K上的___有限集。
A.操作 B.映像 C.存储 D.关系
2.线性表若采用链式存储结构时，要求内存中可用存储单元的地址____。
A.必须连续的 B.部分地址必须连续的 C.一定是不续的 D.连续不连续都可以
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->next = p->next; p->next=s; B. p->next = s->next; s->next = p;
C. q->next = s; s->next = p; D. p->next = s; s->next = q;
7.设串s1=‘ABCDEFG’，s2=‘PQRST’，函数con (x, y) 返回x与y串的连接串，函数subs (s, i, j) 返回串s的从序号i的字符开始的j个字符组成的子串，函数len (s) 返回串s的长度，则con (subs (s1, 2, len (s2)), subs (s1, len (s2), 2)) 的结果串是____。
A. BCDEF B. BCDEFG C. BCPQRST D. BCDEFEF
8.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为____。
A. 2h B. 2h-1 C. 2h +1 D. h +1
9.某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历结点访问顺序是dgbaechf，则其后序遍历结点访问顺序是____。
A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca
10.具有6个顶点的无向图至少应有____条边才能确保是一个连通图。
A. 5 B. 6 C. 7 D. 8
11.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为–。
A. n B. n/2 C. (n+1)/2 D. (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法求得的每个字符对应的next函数值为 。
三、简答题(本大题共3小题，每小题5分，共15分)
1.在对线性表的处理中一般使用两种存储结构，顺序存储结构和链式存储结构。试叙述在什么情况下使用顺序表比链表好？
2.简述什么是稳定的排序，什么是不稳定的排序。
3.下列中缀表达式对应的后缀形式是什么？
(1) (A + B) * D + E / (F + A * D) + C
(2) A && B|| ! (E > F) {注：按C的优先级)
四、判断题(本大题共10小题，命题正确的在题后括号内写 “T”，错误的在题后括号内写“F”，每小题1分，共10分)
1.数据元素不是数据的最小单位( )。
2.已知一棵二叉树的前序序列和后序序列可以唯一地构造出该二叉树。( )
3.AOE网是一种带权的无环连通图。( )
4.对于同一组待输入的关键码集合，虽然各关键码的输入次序不同，但得到的二叉搜索树都是相同的( )。
5.一棵树中的叶子数一定等于与其对应的二叉树的叶子数。( )
6.邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。( )
7.折半插入排序是稳定的。( )
8.在散列法中，使用双散列函数可保证绝对不产生冲突。( )
9.消除递归不一定需要使用栈( )
10.堆排序是交换排序的一种。( )
五、分析应用题（本题共26分，1、4小题各6分，2、3小题各7分）
1．阅读后分析下面程序段的功能是什么? （6分）
SeqStack S1, S2, tmp;
DataType x; //设栈tmp和S2已做过初始化
while ( ! StackEmpty (S1))
{ x=Pop(S1) ;
Push(tmp,x);
}
while ( ! StackEmpty (tmp) )
{ x=Pop(tmp);
Push( 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,1)方法每趟排序后的结果。（6分）
六、算法设计题（本题共18分，第1小题10分，第2小题8分）
1.编写一个算法frequency，统计在一个输入字符串中所含各个不同字符出现的频度。用适当的测试数据来验证这个算法。(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
二、填空题(每空1分，共7分。)
1.父(或前驱)， 1
2. n-1
3. 不包含任何字符的串
4. (n+1)/2
5. 素数
6. 0111223123
三、简答题(每小题5分，共15分)
1.答：① 顺序存储时，相邻数据元素的存放地址也相邻(逻辑与物理统一)；要求内存中可用存储单元的地址必须是连续的。
优点：存储密度大，存储空间利用率高。缺点：插入或删除元素时不方便。
②链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小(<1)，存储空间利用率低。
顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。
若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；
若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。
2.答：在排序序列中，任何两个相等的关键字Ki=Kj,如果在排序前的序列中Ki领先于Kj，若在排序后的序列中Ki仍领先于Kj，则称所用的排序方法是稳定的；反之，若可能使排序后的序列中Kj领先于Ki，则称所用的排序方法是不稳定的。
3.答：各中缀表达式的后缀形式如下：
(1)AB+D*EFAD*+/+C+
(2)AB&&EF>!||
四、判断题(本大题共10小题，命题正确的在题后括号内写 “T”，错误的在题后括号内写“F”，每小题1分，共10分)
1.T 2.F 3.T 4.F 5.F
6.F 7.T 8.F 9.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个结点。生成的赫夫曼树为下图所示：
赫夫曼编码为：概率为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+1+1+4+1+2+1）=14/10
4.（6分）
答： 希尔排序(增量为5,2,1)
六、算法设计题（第1小题10分，第2小题8分）
1. (10分)
include
include”string.h”
int charnumber=128;
void frequency(string&s,int C[ ]){
for(int i=0;i< charnumber;i++) C[i]=0;
for( i=0;i< s.length();i++) C[atoi(s[i])]++;
for( i=0;i< charnumber;i++)
if(C[i]>0) cout<<”(”<<i<<”):\t”<<C[i]<<”\t”;
}
2. (8分)
类型定义（略）
int Level(BiTree bt) //层次遍历二叉树，并统计度为1的结点的个数
{
int num=0; //num统计度为1的结点的个数
if(bt){
QueueInit(Q); QueueIn(Q,bt)；//Q是以二叉树结点指针为元素的队列
while(!QueueEmpty(Q))
{ p=QueueOut(Q); printf(p->data); //出队,访问结点
if(p->lchild && !p->rchild ||!p->lchild && p->rchild)
num++;//度为1的结点
if(p->lchild) QueueIn(Q,p->lchild); //非空左子女入队
if(p->rchild) QueueIn(Q,p->rchild); //非空右子女入队
}
}
return(num); //返回度为1的结点的个数
}
B：
06－07第一学期期末考试试卷
试卷代码：03266B 授课课时：112
课程名称：数据结构与算法 适用对象：本科
一、单项选择题(从下列各题四个备选答案中选出一个正确答案，并将其代号写在答题纸相应位置处。答案错选或未选者，该题不得分。每小题2分，共24分。)
1.数据结构被形式地定义为 (K, R)，其中K是____的有限集，R是K上的关系有限集。
A.算法 B.数据元素 C.数据操作 D.逻辑结构
2.在数据结构中，从逻辑上可以把数据结构分成____。
A.动态结构和静态结构 B.紧凑结构和非紧凑结构
C.线性结构和非线性结构 D.内部结构和外部结构
3.以下的叙述中，正确的是____。
A.线性表的存储结构优于链式存储结构
B.二维数组是其数据元素为线性表的线性表
C.栈的操作方式是先进先出
D.队列的操作方式是先进后出
4.若一个栈的入栈序列是1、2、3、… 、n，其输出序列为p1、p2、p3、… 、pn，若p1=n，则pi为____。
A. i B. n = i C. n - i +1 D.不确定
5.判断一个循环队列QU (最多元素为m) 为空的条件是____。
A. QU->front == QU->rear B. QU->front != QU->rear
C. QU->front == (QU->rear+1)%m D. QU->front != (QU->rear+1)%m
6.在某单链表中，已知p所指结点不是最后结点，在p之后插入s所指结点，则执行____。
A. s->next = p; p->next=s; B. s->next = p->next; p->next = s;
C. s->next = p->next; p = s; D. p->next = s; s->next = p;
7.串是一种特殊的线性表，其特殊性体现在____。
A.可以顺序存储 B.数据元素是一个字符
C.可以链接存储 D.数据元素可以是多个字符
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-1 D. n = 2h -1
10.一个有n个顶点的无向图最多有____条边。
A. n B. n(n-1) C. n(n-1)/2 D. 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法求得的每个字符对应的next函数值为 。
三、简答题(本大题共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分）
LinkList Demo(LinkList L)
{ // L 是无头结点单链表
ListNode *Q,*P;
if(L&&L->next){
Q=L;
L=L->next;
P=L;
while (P->next) P=P->next;
P->next=Q; Q->next=NULL;
}
return 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分，第2小题8分）
1.试设计一个实现下述要求的查找运算函数Locate。设有一个带表头结点的双向链表L， 每个结点有4个数据成员：指向前驱结点的指针llink、指向后继结点的指针rlink，存放字符数据的成员data和访问频度freq。所有结点的freq 初始时都为0。每当在链表上进行一次Locate(L, x) 操作时，令元素值为x的结点的访问频度freq加1，并将该结点前移，链接到与它的访问频度相等的结点后面，使得链表中所有结点保持按访问频度递减的顺序排列，以使频繁访问的结点总是靠近表头。(10分)
2.设一棵二叉树以二叉链表为存贮结构，设计一个算法将二叉树中所有结点的左，右子树相互交换。要求给出二叉链表的类型定义。(8分)
答案：
06－07第一学期
期末考试参考答案与评分标准
试卷代码：03266B 授课课时：112
课程名称：数据结构与算法 适用对象：本科
一、单项选择题(每小题2分，共24分。)
1. B 2. C 3. B 4. C 5. A 6. B
7. B 8. D 9. D 10.C 11. B 12. A
二、填空题(每空1分，共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. (T)
6. (T) 7. (F) 8. (T) 9. (T ) 10.(T)
五、分析应用题（本题共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+1+1+3+5+1+1）=16/10
4.（6分）
答：
六、算法设计题（第1小题10分，第2小题8分）
1.(10分)
答：
(1) 定义链表结构
struct DoubleListNode {
char data ;
int freq;
DoubleListNode * llink, *rlink ;
};
初始时，所有结点的freq域的值都为0。
(2) 定义函数
DoubleListNode * locate ( DoubleListNode *f ; char &x ) {
DoubleListNode * p, *q;
p = f→rlink; /*跳过表头结点*/
while ( p != NULL && p→data != x ) p = p→rlink; /*搜索*/
if ( p ) {
p→freq ++; q = p→llink;
p→rlink→llink = q; q→rlink = p→rlink; /*从链中摘下p*/
while ( q != f &&q→freq < p→freq ) q =q→llink;
p→llink = q;
p→rlink = q→rlink; q→rlink→llink = p;
q→rlink = p; /*在q后面插入p*/
}
return p;
}
2． (8分)
答：类型定义（略）
void exchange(BiTree bt)//将二叉树bt所有结点的左右子树交换
{
if(bt)
{ BiTree s；
s=bt->lchild; bt->lchild=bt->rchild; bt->rchild=s; //左右子女交换
exchange(bt->lchild); //交换左子树上所有结点的左右子树
exchange(bt->rchild); //交换右子树上所有结点的左右子树
}
}
5. 数据结构（C语言版），求高手解决。。
1．二叉树是度为2的有序树（ ） 【答案】× 2．完全二叉树一定存在度为1的结点（ ） 【答案】× 3．深度为K的二叉树中结点总数≤2k-1（ ） 【答案】√ 4．由一棵二叉树的先序序列和后序序列可以惟一确定它（ ） 【答案】× 5．完全二叉树中，若一个结点没有左孩子，则它必是树叶（ ） 【答案】√ 6．用二叉链表存储n个结点的二叉树时，结点的2n个指针中有n+1个空指针（ ） 【答案】√ 7．完全二叉树的存储结构通常采用顺序存储结构（ ） 【答案】√ 8．哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近（ ） 【答案】√ 9．在中序线索二叉树中，每一非空的线索均指向其祖先结点（ ） 【答案】√ 【解析】在二叉树上，对有左右子女的结点，其中序前驱是其左子树上按中序遍历的最右边的结点（该结点的后继指针指向祖先），中序后继是其右子树上按中序遍历的最左边的结点（该结点的前驱指针指向祖先）。 10．二叉树中序线索化后，不存在空指针域（ ） 【答案】×
6. 跪求数据结构（c语言版）的几个问题解答
实验一
单链表有一个头节点h
e
a
d，指向链表在内存的首地址。链表中的每一个节点的数据类型为结构体类型，节点有两个成员：整型成员（实际需要保存的数据）和指向下一个结构体类型节点的指针即下一个节点的地址（事实上，此单链表是用于存放整型数据的动态数组）。链表按此结构对各节点的访问需从链表的头找起，后续节点的地址由当前节点给出。无论在表中访问那一个节点，都需要从链表的头开始，顺序向后查找。链表的尾节点由于无后续节点，其指针域为空，写作为N
U
L
L。
删除运算是将表的第i个结点删去。
具体步骤：
（1）找到要删除结点ai的存储位置p（因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中）
（2）令p-＞next指向ai的直接后继结点（即把ai从链上摘下）
（3）释放结点ai的空间，将其归还给"存储池"。
插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。
具体步骤：
（1）找到ai-1存储位置p
（2）生成一个数据域为x的新结点*s
（3）令结点*p的指针域指向新结点
（4）新结点的指针域指向结点ai。
#include
typedef
int
numtype;
typedef
float
scoretype;
typedef
struct
node
{numtype
num;
scoretype
score;
struct
node
*next;
}linklist;
int
n;
//创建单链表
linklist
*creat()
{
linklist
*head,*p1,*p2;
n=0;
p1=p2=(linklist*)malloc(sizeof(linklist));
printf("请输入第1个学号:\n");
//单链表内容,学号和成绩
scanf("%d",&p1->num);
printf("请输入第1个成绩:\n");
scanf("%f",&p1->score);
head=NULL;
while(1)
{n=n+1;
if(n==1)
head=p1;
else
p2->next=p1;
p2=p1;
p1=(linklist*)malloc(sizeof(linklist));
printf("请输入第%d个学号:\n",n+1);
scanf("%d",&p1->num);
if(p1->num
==
0)
//这里是终止输入的符号，也就是学号输入0，那么就停止输入。你也可以设置为其它的符号
break;
printf("请输入第%d个成绩:\n",n+1);
scanf("%f",&p1->score);
}
p2->next=NULL;
return
head;
}
//单链表的插入
linklist
*insert(linklist
*head,linklist
*stud)
{
linklist
*p1,*p2,*p0;
p1=head;
p0=stud;
if(head==NULL)
{
head=p0;p0->next=NULL;}
else
{
while((p0->score>=p1->score)&&(p1->next!=NULL))
{
p2=p1;p1=p1->next;
}
if(p0->scorescore)
{
if(head==p1)
head
=p0;
else
p2->next=p0;
p0->next=p1;}
else
{
p1->next=p0;
p0->next=NULL;
}
}
return
head;
}
//单链表的删除
linklist
*del(linklist
*head,float
dscore)
{
linklist
*p1,*p2;
if(head==NULL)
{printf("\n
list
is
NULL!");
return
(head);
}
else
{
p1=head;
while((dscore!=p1->score)&&(p1->next!=NULL))
{
p2=p1;
p1=p1->next;
}
if(dscore
==
p1->score)
{
if(p1==head)
head=head->next;
else
p2->next=p1->next;
free(p1);
printf("已删除:%.2f\n",dscore);
}
else
printf("%.2f
没有在链表中找到!\n",dscore);
}
return
head;
}
//输出单链表
void
display(linklist
*r)
{linklist
*t;
t=(linklist*)malloc(sizeof(linklist));
t=r;
printf("\n
单链表显示
:\n学号\t成绩\n");
if(t==NULL)
printf("链表为空。");
else
while(t!=NULL)
{
printf("%d\t",t->num);
printf("%.2f\n
",t->score);
t=t->next;
}
printf("\n");
}
//单链表的插入与删除
int
main()
{
float
s;
linklist
*q,*p;
p=(linklist*)malloc(sizeof(linklist));
q=creat();
display(q);
printf("请输入要删除的结点对应的成绩:");
scanf("%f",&s);
q=del(q,s);
display(q);
printf("请输入要插入的学号和成绩:\n");
printf("学号：");
scanf("%d",&p->num);
printf("成绩:");
scanf("%f",&p->score);
q=insert(q,p);
display(q);
return
0;
}
7. c语言题型，数据结构题
#include
#include
typedef struct student
{
char name[20];
long num;
char sex;
struct student *pNext;
}Stu, *pStu;
void creatInfo(pStu *stu);
int deletInfo(pStu stu, long numTemp);
void printInfo(pStu stu);
int main(void)
{
long numTemp = 0;
pStu myStu = NULL;
creatInfo(&myStu);
scanf("%ld", &numTemp);
if(1 == deletInfo(myStu, numTemp))
printInfo(myStu);
return 0;
}
void creatInfo(pStu *stu)
{
int n = 1;
pStu pNew = NULL, pTail = NULL;
*stu = (pStu)malloc(sizeof(Stu));
if(*stu == NULL)
return ;
(*stu)->pNext = NULL;
pTail = *stu;
while(n <= 10)
{
pNew = (pStu)malloc(sizeof(Stu));
if(NULL == pNew)
return ;
pNew->pNext = NULL;
scanf("%s", pNew->name);
if('#' == pNew->name[0])
{
free(pNew);
pNew = NULL;
return ;
}
scanf("%ld %c", &pNew->num, &pNew->sex);
pTail->pNext = pNew;
pTail = pNew;
++n;
}
}
int deletInfo(pStu stu, long numTemp)
{
pStu pTail = NULL, pHead = NULL;
pHead = stu;
pTail = stu->pNext;
while(pTail)
{
if(pTail->num == numTemp)
{
pHead->pNext = pTail->pNext;
free(pTail);
pTail = NULL;
return 1;
}
pTail = pTail->pNext;
pHead = pHead->pNext;
}
printf("链表中唔该学生！\n");
return 0;
}
void printInfo(pStu stu)
{
while(stu = stu->pNext)
printf("%s, %d, %c\n", stu->name, stu->num, stu->sex);
}
8. 一道数据结构试题和一道C语言试题
1、B，因为每次拆半，所以第一次100万拆成50万，50万拆成25万……它说最多，因此就是拆到2也就不能拆了，这就是2的N次方大于等于100万的问题。可以算的2的20次方大于100万 2、a 这个数组长度是4.a也就是第一个元素a[0]的地址，因此a相当于 一个指向8个整数指针。而B 是一个指针数组，C是一个数组的指针。所以选C
最新文章
热门文章
推荐阅读