上饶师范学院模拟试题二

《上饶师范学院模拟试题二》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、上饶师范学院模拟试题二课程名称：数据结构适用学期：第四学期适用专业：计算机科学与技术适用层次：本科班级：学号：姓名题号一二三四五六七总分得分阅卷教师签名得分一、选择题：(每小题2分，10小题共20分)1.数据结构是一门研究计算机中()对象及其关系的学科。A.数值运算B.非数值运算C.集合D.非集合2.在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行()。A.s->link=p;p->next=s;B.s->link=p->link;p->link=s;C.s->link=p->link;p=s;D.p->lin

2、k=s;s->link=p;3.在数组表示的循环队列中，front、rear分别为队列的头、尾指针，maxSize为数组的最大长度，队满的条件是()。A.front=maxSizeB.(rear+1)%maxSize=frontC.rear=maxSizeD.rear=front4.设有串t=“Iamagoodstudent”，那么subStr(t,6,6)=()。A.“student”B.“agoods”C.“good”D.“agood”5.一个二叉树按顺序方式存储在一个维数组中，如图01234567891011121314ABCD

3、EFGHIJ则结点G在二叉树的第（）层,规定根结点为第0层。A.1B.2C.3D.46.在一棵具有4层的满二叉树中结点总数为()。A.31B.32C.33D.16第8页1.利用逐点插入法建立序列{50,72,43,85,20,35,45,65,30}对应二叉排序树以后，查找元素35要进行()元素间的比较。A．4次　B.5次　C.7次　D.10次2.一有向图的邻接表存储结构如图所示，按深度优先算法，从v1出发得到的顶点序列为()A.v1,v3,v2,v4,v5B.v1,v3,v4,v2,v5C.v1,v2,v3,v4,v5D.v1,v3

4、,v4,v5,v23.在下列算法中，()算法可能出现下列情况：在最后一趟开始之前，所有的元素都不在其最终的位置上。A.堆排序B.冒泡排序C.插入排序D.快速排序4.对于关键字序列{46，58，15，45，90，18，10，62}，其快速排序第一趟的结果是()。A.1545184610625890B.1015184546586290C.1018154546905862D.1510184546625890得分一、填空题：(每小题2分，分值平均分配在每小空上，8小题共16分)5.下面程序段的时间复杂度是_____。for(i=0;i

5、++)for(j=0;j

6、元素，采用折半搜索时，最大比较次数为_________。5.若已知一棵二叉树的先序序列为–+a*b–cd/ef，中序序列为a+b*c–d–e/f，则其后序序列为___________________。6.在所学的排序算法中，第一趟排序完毕后，其最大或最小元一定在其最终位置上的算法有______________________________________________。得分一、概念简答题：(每小题3分,共9分)19.（1）什么是递归程序？（2）递归程序的优点，缺点是什么（3）递归程序在执行时应借助于什么来完成？20.什么是内部排序

7、？什么是外部排序？21.举例或图示说明什么是中序穿线树？第8页得分一、简单解答题：(每小题5分，4小题共20分)22.以数据集{3，4，5，8，12，18，20，30}为叶子结点的权值，（1）构造一棵哈夫曼树　（3分）（2）计算其带权路径长度（2分）。23.设散列函数H(K)=KMOD13，若输入序列为{18,73,10,5,68,99,27,41,51,32,25}，求：（1）设处理冲突的方法为开地址法中的线性探查法，请构造出散列表。（3分）（2）求出在等概率查找情况下查找成功的平均查找长度。（2分）第8页24．设有下列带权无向图：

8、(1)　请画出该图的邻接表。(2)　设以邻接表作为存储结构，请列出从顶点2出发深度优先遍历该图所得到的一个顶点序列。　25．对上题用图示画出Kruskal算法求一棵最小生成树过程（要求画出求最小生成树的每一步）。得分一、