《数据结构》期末考试试卷（ 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)/2D. 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和41B.23和39
C.15和44D.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分）
第一章 绪论
1.16
void print_descending(int x,int y,int z)//按从大到小顺序输出三个数
{
scanf("%d,%d,%d",&x,&y,&z)
if(x<y) x<->y//<->为表示交换的双目运算符,以下同
if(y<z) y<->z
if(x<y) x<->y//冒泡排序
printf("%d %d %d",x,y,z)
}//print_descending
1.17
Status fib(int k,int m,int &f)//求k阶斐波那契序列的第m项的值f
{
int tempd
if(k<2||m<0) return ERROR
if(m<k-1) f=0
else if (m==k-1) f=1
else
{
for(i=0i<=k-2i++) temp[i]=0
temp[k-1]=1//初始化
for(i=ki<=mi++) //求出序列第k至第m个元素的值
{
sum=0
for(j=i-kj<ij++) sum+=temp[j]
temp[i]=sum
}
f=temp[m]
}
return OK
}//fib
分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m^2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(k^m).
1.18
typedef struct{
char *sport
enum{male,female} gender
char schoolname//校名为'A','B','C','D'或'E'
char *result
int score
} resulttype
typedef struct{
int malescore
int femalescore
int totalscore
} scoretype
void summary(resulttype result[ ])//求各校的男女总分和团体总分,假设结果已经储存在result[ ]数组中
{
scoretype score
i=0
while(result[i].sport!=NULL)
{
switch(result[i].schoolname)
{
case 'A':
score[ 0 ].totalscore+=result[i].score
if(result[i].gender==0) score[ 0 ].malescore+=result[i].score
else score[ 0 ].femalescore+=result[i].score
break
case 'B':
score .totalscore+=result[i].score
if(result[i].gender==0) score .malescore+=result[i].score
else score .femalescore+=result[i].score
break
…… …… ……
}
i++；
}
for(i=0i<5i++)
{
printf("School %d:n",i)
printf("Total score of male:%dn",score[i].malescore)
printf("Total score of female:%dn",score[i].femalescore)
printf("Total score of all:%dnn",score[i].totalscore)
}
}//summary
1.19
Status algo119(int a[ARRSIZE])//求i!*2^i序列的值且不超过maxint
{
last=1
for(i=1i<=ARRSIZEi++)
{
a[i-1]=last*2*i
if((a[i-1]/last)!=(2*i)) reurn OVERFLOW
last=a[i-1]
return OK
}
}//algo119
分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常.
1.20
void polyvalue()
{
float ad
float *p=a
printf("Input number of terms:")
scanf("%d",&n)
printf("Input the %d coefficients from a0 to a%d:n",n,n)
for(i=0i<=ni++) scanf("%f",p++)
printf("Input value of x:")
scanf("%f",&x)
p=axp=1sum=0//xp用于存放x的i次方
for(i=0i<=ni++)
{
sum+=xp*(*p++)
xp*=x
}
printf("Value is:%f",sum)
}//polyvalue
第二章 线性表
2.10
Status DeleteK(SqList &a,int i,int k)//删除线性表a中第i个元素起的k个元素
{
if(i<1||k<0||i+k-1>a.length) return INFEASIBLE
for(count=1i+count-1<=a.length-kcount++) //注意循环结束的条件
a.elem[i+count-1]=a.elem[i+count+k-1]
a.length-=k
return OK
}//DeleteK
2.11
Status Insert_SqList(SqList &va,int x)//把x插入递增有序表va中
{
if(va.length+1>va.listsize) return ERROR
va.length++
for(i=va.length-1va.elem[i]>x&&i>=0i--)
va.elem[i+1]=va.elem[i]
va.elem[i+1]=x
return OK
}//Insert_SqList
2.12
int ListComp(SqList A,SqList B)//比较字符表A和B,并用返回值表示结果,值为正,表示A>B值为负,表示A<B值为零,表示A=B
{
for(i=1A.elem[i]||B.elem[i]i++)
if(A.elem[i]!=B.elem[i]) return A.elem[i]-B.elem[i]
return 0
}//ListComp
2.13
LNode* Locate(linkList L,int x)//链表上的元素查找,返回指针
{
for(p=l->nextp&&p->data!=xp=p->next)
return p
}//Locate
2.14
int Length(linkList L)//求链表的长度
{
for(k=0,p=Lp->nextp=p->next,k++)
return k
}//Length
2.15
void ListConcat(linkList ha,linkList hb,linkList &hc)//把链表hb接在ha后面形成链表hc
{
hc=hap=ha
while(p->next) p=p->next
p->next=hb
}//ListConcat
2.16
见书后答案.
2.17
Status Insert(linkList &L,int i,int b)//在无头结点链表L的第i个元素之前插入元素b
{
p=Lq=(linkList*)malloc(sizeof(LNode))
q.data=b
if(i==1)
{
q.next=pL=q//插入在链表头部
}
else
{
while(--i>1) p=p->next
q->next=p->nextp->next=q//插入在第i个元素的位置
}
}//Insert
2.18
Status Delete(linkList &L,int i)//在无头结点链表L中删除第i个元素
{
if(i==1) L=L->next//删除第一个元素
else
{
p=L
while(--i>1) p=p->next
p->next=p->next->next//删除第i个元素
}
}//Delete
2.19
Status Delete_Between(linklist &L,int mink,int maxk)//删除元素递增排列的链表L中值大于mink且小于maxk的所有元素
{
p=L
while(p->next->data<=mink) p=p->next//p是最后一个不大于mink的元素
if(p->next)//如果还有比mink更大的元素
{
q=p->next
while(q->data<maxk) q=q->next//q是第一个不小于maxk的元素
p->next=q
}
}//Delete_Between
2.20
Status Delete_Equal(linklist &L)//删除元素递增排列的链表L中所有值相同的元素
{
p=L->nextq=p->next//p,q指向相邻两元素
while(p->next)
{
if(p->data!=q->data)
{
p=p->nextq=p->next//当相邻两元素不相等时,p,q都向后推一步
}
else
{
while(q->data==p->data)
{
free(q)
q=q->next
}
p->next=qp=qq=p->next//当相邻元素相等时删除多余元素
}//else
}//while
}//Delete_Equal
2.21
void reverse(SqList &A)//顺序表的就地逆置
{
for(i=1,j=A.lengthi<ji++,j--)
A.elem[i]<->A.elem[j]
}//reverse
2.22
void linkList_reverse(linklist &L)//链表的就地逆置为简化算法,假设表长大于2
{
p=L->nextq=p->nexts=q->nextp->next=NULL
while(s->next)
{
q->next=pp=q
q=ss=s->next//把L的元素逐个插入新表表头
}
q->next=ps->next=qL->next=s
}//linkList_reverse
分析:本算法的思想是,逐个地把L的当前元素q插入新的链表头部,p为新表表头.
2.23
void merge1(linkList &A,linkList &B,linkList &C)//把链表A和B合并为C,A和B的元素间隔排列,且使用原存储空间
{
p=A->nextq=B->nextC=A
while(p&&q)
{
s=p->nextp->next=q//将B的元素插入
if(s)
{
t=q->nextq->next=s//如A非空,将A的元素插入
}
p=sq=t
}//while
}//merge1
2.24
void reverse_merge(linkList &A,linkList &B,linkList &C)//把元素递增排列的链表A和B合并为C,且C中元素递减排列,使用原空间
{
pa=A->nextpb=B->nextpre=NULL//pa和pb分别指向A,B的当前元素
while(pa||pb)
{
if(pa->data<pb->data||!pb)
{
pc=paq=pa->nextpa->next=prepa=q//将A的元素插入新表
}
else
{
pc=pbq=pb->nextpb->next=prepb=q//将B的元素插入新表
}
pre=pc
}
C=AA->next=pc//构造新表头
}//reverse_merge
分析:本算法的思想是,按从小到大的顺序依次把A和B的元素插入新表的头部pc处,最后处理A或B的剩余元素.
2.25
void SqList_Intersect(SqList A,SqList B,SqList &C)//求元素递增排列的线性表A和B的元素的交集并存入C中
{
i=1j=1k=0
while(A.elem[i]&&B.elem[j])
{
if(A.elem[i]<B.elem[j]) i++
if(A.elem[i]>B.elem[j]) j++
if(A.elem[i]==B.elem[j])
{
C.elem[++k]=A.elem[i]//当发现了一个在A,B中都存在的元素,
i++j++//就添加到C中
}
}//while
}//SqList_Intersect
2.26
void linkList_Intersect(linkList A,linkList B,linkList &C)//在链表结构上重做上题
{
p=A->nextq=B->next
pc=(LNode*)malloc(sizeof(LNode))
while(p&&q)
{
if(p->data<q->data) p=p->next
else if(p->data>q->data) q=q->next
else
{
s=(LNode*)malloc(sizeof(LNode))
s->data=p->data
pc->next=spc=s
p=p->nextq=q->next
}
}//while
C=pc
}//linkList_Intersect
2.27
void SqList_Intersect_True(SqList &A,SqList B)//求元素递增排列的线性表A和B的元素的交集并存回A中
{
i=1j=1k=0
while(A.elem[i]&&B.elem[j])
{
if(A.elem[i]<B.elem[j]) i++
else if(A.elem[i]>B.elem[j]) j++
else if(A.elem[i]!=A.elem[k])
{
A.elem[++k]=A.elem[i]//当发现了一个在A,B中都存在的元素
i++j++//且C中没有,就添加到C中
}
}//while
while(A.elem[k]) A.elem[k++]=0
}//SqList_Intersect_True
2.28
void linkList_Intersect_True(linkList &A,linkList B)//在链表结构上重做上题
{
p=A->nextq=B->nextpc=A
while(p&&q)
{
if(p->data<q->data) p=p->next
else if(p->data>q->data) q=q->next
else if(p->data!=pc->data)
{
pc=pc->next
pc->data=p->data
p=p->nextq=q->next
}
}//while
}//linkList_Intersect_True
2.29
void SqList_Intersect_Delete(SqList &A,SqList B,SqList C)
{
i=0j=0k=0m=0//i指示A中元素原来的位置,m为移动后的位置
while(i<A.length&&j<B.length&&k<C.length)
{
if(B.elem[j]<C.elem[k]) j++
else if(B.elem[j]>C.elem[k]) k++
else
{
same=B.elem[j] //找到了相同元素same
while(B.elem[j]==same) j++
while(C.elem[k]==same) k++//j,k后移到新的元素
while(i<A.length&&A.elem[i]<same)
A.elem[m++]=A.elem[i++] //需保留的元素移动到新位置
while(i<A.length&&A.elem[i]==same) i++//跳过相同的元素
}
}//while
while(i<A.length)
A.elem[m++]=A.elem[i++]//A的剩余元素重新存储。
A.length=m
}// SqList_Intersect_Delete
分析:先从B和C中找出共有元素,记为same,再在A中从当前位置开始, 凡小于same的
元素均保留(存到新的位置),等于same的就跳过,到大于same时就再找下一个same.
2.30
void linkList_Intersect_Delete(linkList &A,linkList B,linkList C)//在链表结构上重做上题
{
p=B->nextq=C->nextr=A-next
while(p&&q&&r)
{
if(p->data<q->data) p=p->next
else if(p->data>q->data) q=q->next
else
{
u=p->data//确定待删除元素u
while(r->next->data<u) r=r->next//确定最后一个小于u的元素指针r
if(r->next->data==u)
{
s=r->next
while(s->data==u)
{
t=ss=s->nextfree(t)//确定第一个大于u的元素指针s
}//while
r->next=s//删除r和s之间的元素
}//if
while(p->data=u) p=p->next
while(q->data=u) q=q->next
}//else
}//while
}//linkList_Intersect_Delete
2.31
Status Delete_Pre(CiLNode *s)//删除单循环链表中结点s的直接前驱
{
p=s
while(p->next->next!=s) p=p->next//找到s的前驱的前驱p
p->next=s
return OK
}//Delete_Pre
2.32
Status DuLNode_Pre(DulinkList &L)//完成双向循环链表结点的pre域
{
for(p=L!p->next->prep=p->next) p->next->pre=p
return OK
}//DuLNode_Pre
2.33
Status linkList_Divide(linkList &L,CiList &A,CiList &B,CiList &C)//把单链表L的元素按类型分为三个循环链表.CiList为带头结点的单循环链表类型.
{
s=L->next
A=(CiList*)malloc(sizeof(CiLNode))p=A
B=(CiList*)malloc(sizeof(CiLNode))q=B
C=(CiList*)malloc(sizeof(CiLNode))r=C//建立头结点
while(s)
{
if(isalphabet(s->data))
{
p->next=sp=s
}
else if(isdigit(s->data))
{
q->next=sq=s
}
else
{
r->next=sr=s
}
}//while
p->next=Aq->next=Br->next=C//完成循环链表
}//linkList_Divide
2.34
void Print_XorlinkedList(XorlinkedList L)//从左向右输出异或链表的元素值
{
p=L.leftpre=NULL
while(p)
{
printf("%d",p->data)
q=XorP(p->LRPtr,pre)
pre=pp=q//任何一个结点的LRPtr域值与其左结点指针进行异或运算即得到其右结点指针
}
}//Print_XorlinkedList
2.35
Status Insert_XorlinkedList(XorlinkedList &L,int x,int i)//在异或链表L的第i个元素前插入元素x
{
p=L.leftpre=NULL
r=(XorNode*)malloc(sizeof(XorNode))
r->data=x
if(i==1) //当插入点在最左边的情况
{
p->LRPtr=XorP(p.LRPtr,r)
r->LRPtr=p
L.left=r
return OK
}
j=1q=p->LRPtr//当插入点在中间的情况
while(++j<i&&q)
{
q=XorP(p->LRPtr,pre)
pre=pp=q
}//while //在p,q两结点之间插入
if(!q) return INFEASIBLE//i不可以超过表长
p->LRPtr=XorP(XorP(p->LRPtr,q),r)
q->LRPtr=XorP(XorP(q->LRPtr,p),r)
r->LRPtr=XorP(p,q)//修改指针
return OK
}//Insert_XorlinkedList
2.36
Status Delete_XorlinkedList(XorlinkedList &L,int i)//删除异或链表L的第i个元素
{
p=L.leftpre=NULL
if(i==1) //删除最左结点的情况
{
q=p->LRPtr
q->LRPtr=XorP(q->LRPtr,p)
L.left=qfree(p)
return OK
}
j=1q=p->LRPtr
while(++j<i&&q)
{
q=XorP(p->LRPtr,pre)
pre=pp=q
}//while //找到待删结点q
if(!q) return INFEASIBLE//i不可以超过表长
if(L.right==q) //q为最右结点的情况
{
p->LRPtr=XorP(p->LRPtr,q)
L.right=pfree(q)
return OK
}
r=XorP(q->LRPtr,p)//q为中间结点的情况,此时p,r分别为其左右结点
p->LRPtr=XorP(XorP(p->LRPtr,q),r)
r->LRPtr=XorP(XorP(r->LRPtr,q),p)//修改指针
free(q)
return OK
}//Delete_XorlinkedList
2.37
void OEReform(DulinkedList &L)//按1,3,5,...4,2的顺序重排双向循环链表L中的所有结点
{
p=L.next
while(p->next!=L&&p->next->next!=L)
{
p->next=p->next->next
p=p->next
} //此时p指向最后一个奇数结点
if(p->next==L) p->next=L->pre->pre
else p->next=l->pre
p=p->next//此时p指向最后一个偶数结点
while(p->pre->pre!=L)
{
p->next=p->pre->pre
p=p->next
}
p->next=L//按题目要求调整了next链的结构,此时pre链仍为原状
for(p=Lp->next!=Lp=p->next) p->next->pre=p
L->pre=p//调整pre链的结构,同2.32方法
}//OEReform
分析:next链和pre链的调整只能分开进行.如同时进行调整的话,必须使用堆栈保存偶数结点的指针,否则将会破坏链表结构,造成结点丢失.
2.38
DuLNode * Locate_DuList(DulinkedList &L,int x)//带freq域的双向循环链表上的查找
{
p=L.next
while(p.data!=x&&p!=L) p=p->next
if(p==L) return NULL//没找到
p->freq++q=p->pre
while(q->freq<=p->freq) q=q->pre//查找插入位置
if(q!=p->pre)
{
p->pre->next=p->nextp->next->pre=p->pre
q->next->pre=pp->next=q->next
q->next=pp->pre=q//调整位置
}
return p
}//Locate_DuList
2.39
float GetValue_SqPoly(SqPoly P,int x0)//求升幂顺序存储的稀疏多项式的值
{
PolyTerm *q
xp=1q=P.data
sum=0ex=0
while(q->coef)
{
while(ex<q->exp) xp*=x0
sum+=q->coef*xp
q++
}
return sum
}//GetValue_SqPoly
2.40
void Subtract_SqPoly(SqPoly P1,SqPoly P2,SqPoly &P3)//求稀疏多项式P1减P2的差式P3
{
PolyTerm *p,*q,*r
Create_SqPoly(P3)//建立空多项式P3
p=P1.dataq=P2.datar=P3.data
while(p->coef&&q->coef)
{
if(p->exp<q->exp)
{
r->coef=p->coef
r->exp=p->exp
p++r++
}
else if(p->exp<q->exp)
{
r->coef=-q->coef
r->exp=q->exp
q++r++
}
else
{
if((p->coef-q->coef)!=0) //只有同次项相减不为零时才需要存入P3中
{
r->coef=p->coef-q->coef
r->exp=p->expr++
}//if
p++q++
}//else
}//while
while(p->coef) //处理P1或P2的剩余项
{
r->coef=p->coef
r->exp=p->exp
p++r++
}
while(q->coef)
{
r->coef=-q->coef
r->exp=q->exp
q++r++
}
}//Subtract_SqPoly
2.41
void QiuDao_linkedPoly(linkedPoly &L)//对有头结点循环链表结构存储的稀疏多项式L求导
{
p=L->next
if(!p->data.exp)
{
L->next=p->nextp=p->next//跳过常数项
}
while(p!=L)
{
p->data.coef*=p->data.exp--//对每一项求导
p=p->next
}
}//QiuDao_linkedPoly
2.42
void Divide_linkedPoly(linkedPoly &L,&A,&B)//把循环链表存储的稀疏多项式L拆成只含奇次项的A和只含偶次项的B
{
p=L->next
A=(PolyNode*)malloc(sizeof(PolyNode))
B=(PolyNode*)malloc(sizeof(PolyNode))
pa=Apb=B
while(p!=L)
{
if(p->data.exp!=2*(p->data.exp/2))
{
pa->next=ppa=p
}
else
{
pb->next=ppb=p
}
p=p->next
}//while
pa->next=Apb->next=B
}//Divide_linkedPoly
#include<stdio.h>
int main(){
fload a[3]
scanf("%f,%f,%f",&a[0],&a[1],&a[2])
float temp
if(a[0]>a[1]){
temp = a[0]
a[0] = a[1]
a[1] = temp
}
if(a[1]>a[2]){
temp = a[1]
a[1] = a[2]
a[2] = temp
}
if(a[0]>a[1]){
temp = a[0]
a[0] = a[1]
a[1] = temp
}
print("%f %f %f n", a[0],a[1],a[2])
}
以上就是关于急需数据结构C语言版（清华大学出版社）的期末考试试题及答案全部的内容，如果了解更多相关内容，可以关注醉学网，你们的支持是我们更新的动力！
温馨提示：
