资源描述：
《数据结构专升本复习题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、4.图的邻接矩阵:5.有向图的逆邻接表:4.找出下面网络的最小生成树。7.无向完全图的邻接矩阵是____矩阵。A.对称B.上三角C.下三角D.稀疏6.具有10个顶点的无向图,边的总数最多为_。4.试画出下列有向网的十字链表。有向网五、求解下列问题(每小题6分,共24分)1.已知二叉树的前序遍历序列和中序遍历序列分别是：B,A,C,D,F,E,G和D,C,A,F,G,E,B,试画出该二叉树。2.试按表(25,15,19,24,20,5,16,45,40,38)中元素的排列次序,将所有元素插入一棵初始为空的二叉排序树中,使之仍是一棵二叉排序树。(1)试画出插
2、入完成之后的二叉排序树；(2)若查找元素17,它将依次与二叉排序树中哪些元素比较大小?(3)假设每个元素的查找概率相等,试计算该树的平均查找长度ASL；(4)对该树进行中序遍历,试写出中序遍历序列。3.试用权集合{4,6,5,12,2,1,13},构造赫夫曼(Huffman)树,(1)列出构造过程,(2)分别计算该赫夫曼树的路径长度和带权路径长度。4.找出下面网络的最小生成树:六、执行下面的C程序,指出输出结果。(8分)#include#includestructnode{chardata；structnode*ne
3、xt；}；voidlink_list(structnode*p){while(p!=NULL){printf("%c",p->data)；p=p->next；}printf("")；}main(){charch；structnode*q,*p,*f,*head=NULL；for(ch='A'；ch<'F'；ch++){p=(structnode*)malloc(sizeof(structnode))；p->data=ch；p->next=head；head=p；link_list(p)；}p=head；head=NULL；while(p!=NULL)
4、{q=p；p=p->next；q->next=head；head=q；f=head；while(f->next!=NULL){link_list(head)；f=f->next->next；}}}七、算法设计(算法中必须有注释,每小题8分,共16分)1.设n个元素的线性表顺序存储在一维数组st[1..maxlen]的前n个位置上,试写出算法:删除表中第i(1≤i≤n)个元素。2.设Head为带表头结点的单链表的头指针,试写出算法:若为非空表,则输出:最大结点和最小结点的值(data值)；否则,输出:“Emptylist”。网计(专升本)《数据结构》试题(
5、模C)一、选择题1.由____组成的集合是一个数据对象。A.不同类型的数据项B.不同类型的数据元素C.相同类型的数据项D.相同类型的数据元素2.____是线性表。A.(孔子,诸葛亮,曹雪芹)B.{A,B,C,D}C.{10,11,12,13,14}D.(1,2,3,...)3.____是表示线性数据结构的。A.循环链表B.邻接多重表C.孩子链表D.单链表4.将线性表的数据元素以____结构存放,查找一个数据元素所需的时间不依赖于表的长度。A.循环双链表B.哈希(Hash)表C.一维数组D.单链表5.设数组A[1..8,1..10]的基地址为4000,每个
6、元素占2个存储单元,若以列序为主序顺序存储,则元素A[4,7]的存储地址是____。(假定无第0行第0列元素)A.4072B.4104C.4102D.40746.设依次进入一个栈的元素序列为c,a,b,d,不可得到出栈的元素序列有_____。A.a.b,c,dB.a,d,c,bC.b,a,d,cD.c,d,a,b7.___又是一棵满二叉树。A.二叉排序树B.深度为5有31个结点的二叉树C.有15个结点的完全二叉树D.哈夫曼(Huffman)树8.深度为k的满二叉树有____个分枝结点。A.2k-1B.2k-1-1C.2k+1D.2k-1+19.具有n(n
7、>0)个结点的完全二叉树的深度为A.élog2(n)ùB.ëlog2(n)û+1C.élog2(n+1)ùD.ëlog2(n+1)û10.折半查找20个记录的有序表,若查找失败,比较关键字的次数____。A.最多为6B.最多为5C.最少为3D.最少为411.折半查找有序表(2,5,8,20,25,36,40,60),若查找元素60,需依次与表中元素____进行比较。A.25,40,60B.25,40C.20,36,40,60D.20,36,4012.查找哈希(Hash)表,解决冲突的的方法有____A.除留余数法B.线性探测再散列法C.直接地址法D.链地
8、址法13.对有10个记录的表作简单选择排序,需要比较___次关键字。A.100B
