急需数据结构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分）
一道数据结构（C语言）编程题
楼主的问题要很麻烦啊。我记得第二题好像是东南大学99年或2000年的一道研究生测试题了。
就只给出算法了：
//在用邻接表方式存储的无向图g中，删除边(i,j)
{p=g[i].firstarc;
pre=null;
//删顶点i
的边结点(i,j),pre是前驱指针
while
(p)
if
(p-adjvex==j)
{if(pre==null)g[i].firstarc=p-next;else
pre-next=p-next;free(p);}//释放结点空间。
else
{pre=p;
p=p-next;}
//沿链表继续查找
p=g[j].firstarc;
pre=null;
//删顶点j
的边结点(j,i)
while
(p)
if
(p-adjvex==i)
{if(pre==null)g[j].firstarc=p-next;else
pre-next=p-next;free(p);}//释放结点空间。
else
{pre=p;
p=p-next;}
//沿链表继续查找
}//
DeletEdge
算法讨论：
算法中假定给的i，j
均存在，否则应检查其合法性。若未给顶点编号，而给出顶点信息，则先用顶点定位函数求出其在邻接表顶点向量中的下标i和j。
关于数据结构（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(n0){
k=n%d;
push(S,k);
n=n/d;
}//将余数进栈
while(S.top!=S.base){
pop(S,e);
printf(“%1d”,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++) if(!vis[j] dis[j]Min)
Min=dis[ p=j ];
vis[p]=1; ans+=Min;
cout”加边:(“p”,”F[p]”) 边权：”Map[p][F[p]]endl;
for(int j = 1; j = 7; j++) if(!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; cinab; if( a==-1 b==-1) break;
int c; cinc; Map[a][b] = Map[b][a] = c;
}
Prim();
return 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,1) 边权：6
加边:(5,6) 边权：9
加边:(7,6) 边权：17
加边:(3,7) 边权：15
加边:(4,3) 边权：13
加边:(2,3) 边权：16
总权值：76
Kruskal算法：
struct Edge{
int u,v,w;
bool operator (const Edge a)const{
return 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;itot;i++){
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) continue;
pre[fu]=fv; cnt++; ans+=w;
cout”加边（”u”,”v”） “”边权：”wendl;
}
cout”总的权值：”ansendl;
}
int main(){
while( true ){
int a,b; cinab; if( a==-1 b==-1) break;
int c; cinc; edge[tot++] = (Edge){a,b,c};
}
Kruskal();
return 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
结果：
加边（1,6） 边权：6
加边（6,5） 边权：9
加边（3,4） 边权：13
加边（7,3） 边权：15
加边（2,3） 边权：16
加边（6,7） 边权：17
总的权值：76
数据结构（c语言版）题目求答案
3.28
void InitCiQueue(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;//直接把p加在Q的后面
Q-next=p;
Q=p;//修改尾指针
}
Status DeCiQueue(CiQueueQ,int x)//从循环链表表示的队列Q头部删除元素x
{
if(Q==Q-next)return INFEASIBLE;//队列已空
p=Q-next-next;
x=p-data;
Q-next-next=p-next;
free(p);
rturn OK;
}//DeCiqueue
3.31
int Palindrome_Test()
{
InitStack(S);InitQueue(Q);
while((c=getchar())!=’@’)
{
Push(S,c);EnQueue(Q,c);
}
while(!StackEmpty(S))
{
pop(S,a);DeQueue(Q,b);
if(a!=b)return ERROR;
}
return OK;
}
微信扫一扫 
支付宝扫一扫 
