数据结构c语言版题库
《数据结构》期末试卷(一)
一、选择题(每小题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，所以第五个元素的地址是:b。
A.110 B .108
C.100 D. 120
6.字符串是一种特殊的线性表，其特殊性体现在:b
A.它可以顺序存储。数据元素是一个字符。
C.链接存储数据元素可以是多个字符。
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(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，称为同义词的关键字是(d)。
A.35和41 B.23和39
C.15和44 D.25和51
2.已知二叉树的前序遍历结果为A，B，D，E，G，C，F，H，I，J，前序遍历结果为D，B，G，E，A，H，F，I，J，C..请画出二进制的具体结构。(注意具体步骤)(10分)
原理见教材第128页。
3.有一个图表如下。请写下从顶点c0开始的深度优先和宽度优先遍历的结果。(10分)
深度第一；C0-CC3-C4-C5-C2
宽度优先:C0-CC2-C3-C4-C5
四、有如下图，根据Kruskal算法得到最小生成树。要求写出完整的步骤。(10分)
原理见教材第250页。
5.给定线性表(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
高=3，低=0，中=1
高=0，低=0，中=0(找到12个)
高=8，低=5，中=6(找到93个)
高=8，低=7，中=7
高=8低=8中=8
算法:见教材第84页。
六、知识列表的节点结构如下
下一个数据
下面的算法只是简单的对带有前导节点的单链表L进行选择和排序，使L中的元素从小到大排列。
请在空白处填入适当的内容，使之成为一个完整的算法。(算法的基本思想和实现过程能用文字说明，10分)
void SelectSort(LinkedList L)
{
LinkedList p，q，min
数据类型rcd
p =(1)；
而(p！=NULL) {
min = p；
q = p-next；
而(q！=NULL){
如果((2))min = q；
q = q-next；
}
如果((3) ){
rcd = p-data；
p-data = min-data；
min-data = rcd；
}
(4) ;
}
}
这个问题不会。嘿嘿。。。。
7.一个完整算法的基本性质是什么？分别简要说明每个属性的含义。(5分)
输入:
四个基本属性:1。输入:有零个或多个外部提供的量作为算法的输入。
2.输出:算法至少生成一个量作为输出。
3.确定性:构成算法的每一条指令都是清晰明确的。
4.:有限性:算法中每条指令执行的次数是有限的，执行每条指令的时间也是有限的。
8.队列“假溢出”是什么现象？怎么解决？(5分)
队列的假溢出现象是指在指数群实现的顺序队列中，队列尾指针已经达到数组表的上界而溢出，但在队列头指针之前还有一些空间空闲的现象。解决方案之一是使用循环队列技术来连接数组空间的末端。
9.解释和比较文件的各种物理结构。(6分)
一个数据结构的编程问题(C语言)
楼主的问题很麻烦。我记得第二个问题好像是1999年或者2000年东南大学的研究生考试。
只要给出算法:
//邻接表存储的无向图G中，删除边(I，j)。
p=g[i]。firstarc
pre = null
//删除顶点I
和pre的边节点(I，j)是前驱指针。
在…期间
(p)
如果
(p-adjvex==j)
{if(pre==null)g[i]。first arc = p-next；其他
pre-next = p-next；免费(p)；}//释放节点空间。
其他
{ pre = p；
p = p-next；}
//继续沿着链表搜索
p=g[j]。firstarc
pre = null
//删除顶点j
的边节点(j，I)。
在…期间
(p)
如果
(p-adjvex==i)
{if(pre==null)g[j]。first arc = p-next；其他
pre-next = p-next；免费(p)；}//释放节点空间。
其他
{ pre = p；
p = p-next；}
//继续沿着链表搜索
}//
删除边缘
算法讨论:
算法中假设的I，j
两者都存在，否则要查其合法性。如果给定的是顶点信息而不是顶点数，那么邻接表的顶点向量中的下标I和j是利用顶点定位函数得到的。
关于数据结构(C语言)的几个问题 1.
随便画几棵二叉树，其中空链域用ε表示，数一下节点数和ε就知道是n 1
2.
具体流程如图所示。
3.
第一步，将数据(假设E)放入S的数据中；
步骤S的后继指向Q的后继节点；
第三步Q的后继指向s。
4.
找到72只需要两步:
第一步:设置低、高、中指针，将72与mid指向的值，即48进行比较；
第二部分:72大于48，low指向mid 1，重新计算mid，指向72，与72比较，即搜索成功。
关于比较的最大次数，请参阅严为民数据结构第9章第220页。
5.
比如图中这棵树，假设i=2，2i=4不大于n，2i 1=5大于n，那么节点2没有右子树。
6.
顺序堆栈的类型定义:
typedef结构{
char * base//ElemType也可以，只要定义好了。
char * top
int stacksize
} SqStackTp//注意名字要和主函数一致。
运行结果:
ABCDEFGHIJKLM
MLKJIHGFEDCBA
结果的详细说明:
这里' A '到' A' 12='M '同时放入堆栈并输出。
for(ch = ' A '；ch = ' A ' 12ch)
{ Push(sq，ch)；
printf("%c "，ch)；
}
这里‘a’到‘m’同时弹出并输出。
而(！空栈(平方))
{ Pop(sq，ch)；
printf("c "，ch)；
} printf(" \ n ")；
因为堆栈是LIFO，所以有这样的结果。
7.
void converse(int n，int d){
sq stack S；//创建新的堆栈
InitStack//初始化堆栈
int k，e；
while(n0){
k = n % d；
push(S，k)；
n = n/d；
}//将余数放入堆栈
while(S.top！=S.base){
pop(S，e)；
printf(" ",e)；
}//输出结果
}
8.
优先遍历:ABCDEF
中阶遍历:BCDAFE
后序遍历:DCBFEA
数据结构(C语言版)题目，大神来了。 Prim算法:
int Map[10][10]；
int dis[10]，vis[10]，F[10]；
void Prim(){
memset(vis，0，sizeof(vis))；
int ans = 0；vis[1]= 1；
for(int I = 2；I = 7；i ) { dis[i] = Map[i][1]！= -1?map[I][1]:INF；f[I]= 1；}
for(int I = 2；I = 7；i ){
int Min=INF，p；
for(int j = 1；j = 7；j)如果(！vis[j] dis[j]Min
min = dis[p = j]；
vis[p]= 1；ans = Min
Cout "edge: ("p "，" F[p]")edge right:" Map[p][F[p]]endl；
for(int j = 1；j = 7；j)如果(！vis[j] Map[p][j]= -1)
if( Map[p][j]dis[j]){
dis[j]= Map[p][j]；
f[j]= p；
}
}
Cout”总重量:“ansendl
}
int main(){
memset(Map，-1，sizeof(Map))；
while( true ){
int a，b；cinabif( a==-1 b==-1)破；
int c；cincMap[a][b]= Map[b][a]= c；
}
prim()；
返回0；
}
输入和操作结果:
输入:
1 6 6
1 2 20
1 7 19
6 7 17
6 5 9
2 7 17
5 7 19
2 3 16
7 3 15
7 4 20
5 4 24
3 4 13
1
结果:
边缘:(6，1)右侧边缘:6
边缘:(5，6)右边:9
边缘:(7，6)右边:17
边缘:(3，7)右边:15
边缘:(4，3)右边:13
边缘:(2，3)右边:16
总重量:76
克鲁斯卡尔算法:
结构边缘{
int u，v，w；
布尔运算符(常数边a)常数{
返回wa.w
}
};
edge edge[100]；int tot = 0；
int pre[100]；
int Find( int x ){
return x==pre[x]？x:pre[x]= Find(pre[x])；
}
void Kruskal(){
for(int I = 0；I = 7；I)pre[I]= I；
sort(edge，edge tot)；
int cnt = 1，ans = 0；
for(int I = 0；itoti ){
if(CNT = = 7)break；
int u=edge[i]。u，v= edge[i]。v，w=edge[i]。w；
int fu=Find(u)，Fv = Find(v)；
if(fu==fv)继续；
pre[fu]= Fv；cntans = w；
Cout "border ("u "，" v ")" border right:" wendl；
}
Cout”总重量:“ansendl
}
int main(){
while( true ){
int a，b；cinabif( a==-1 b==-1)破；
int c；cincedge[tot ] = (Edge){a，b，c }；
}
克鲁斯卡尔()；
返回0；
}
输入和操作结果:
输入:
1 6 6
1 2 20
1 7 19
6 7 17
6 5 9
2 7 17
5 7 19
2 3 16
7 3 15
7 4 20
5 4 24
3 4 13
1
结果:
边缘(1，6)右边:6
边缘(6，5)右边:9
边缘(3，4)右边:13
边缘(7，3)右边缘:15
边缘(2，3)右边:16
边缘(6，7)右边缘:17
总重量:76
数据结构(C语言版)答案的标题 3.28
voidinitiaciqueue(ciqueueq)//初始化循环链表表示的队列q。
{
q =(CiLNode *)malloc(sizeof(CiLNode))；
Q-next = Q；
}//InitCiQueue
VoidEnCiQueue(CiQueueQ，int x)//将元素x插入到循环链表表示的队列Q中，其中Q指向队列的末尾，Q-next指向头节点，Q-next-next指向队列的末尾。
{
p =(CiLNode *)malloc(sizeof(CiLNode))；
p-data = x；
p-next = Q-next；//直接在q后面加P。
q-next = p；
q = p；//修改尾部指针
}
Status deciqueue (ciqueueq，int x)//从循环链表表示的队列q的头部删除元素x。
{
if(Q==Q-next)返回不可行；//队列为空。
p = Q-next-next；
x = p-数据；
q-next-next = p-next；
免费(p)；
r返回OK；
}//决定队列
3.31
int回文_Test()
{
InitStackinit queue(Q)；
while((c=getchar())！='@')
{
Push(S，c)；EnQueue(Q，c)；
}
而(！栈顶)
{
pop(S，a)；出列(Q，b)；
如果(a！=b)返回错误；
}
退货OK；
}
最后更新于 2023-10-08 02:35:07 并被添加「」标签，已有 位童鞋阅读过。
本站使用「署名 4.0 国际」创作共享协议，可自由转载、引用，但需署名作者且注明文章出处
相关文章