数据结构作业题(一)

《数据结构作业题(一)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《数据结构》复习题（一）一、判断题（下列各题，你认为正确的，请在前面的括号内打√，错误的打×。每题1分，共10分）（）1.数据的存贮结构是数据的逻辑结构的存贮映象。（）2.用顺序表来存储线性表时，不需要另外开辟空间来保存数据元素之间的相互关系。（）3.非线性结构中，至少存在一个元素不止一个直接前趋或不止一个直接后继。（）4.树的最大特点是层次结构。（）5.队列的特点是先进先出。（）6.图的最小生成树是唯一的。（）7.线性表是广义表的特殊形式。（）8.后序序列和中序序列能唯一确定一棵二叉树。（）9

2、.散列表是一种链式存贮结构。（）10.快速排序并非在任何情况下都比其它排序方法速度快。二、填空题（每空2分，共20分）1．数据的存贮结构的四种形式为存贮、存贮、存贮和存贮。2．所有插入和删除都在表的一端进行的线性表称为。3．n个结点的完全二叉树，其深度h=。4．对于顺序循环队列Q[M]，下标从0到M-1，头尾指针分别为F和R，入队时，队尾指针循环加1可表示为R=。矚慫润厲钐瘗睞枥庑赖。5．散列法既是一种查找方法，又是一种方法。6．n个顶点的有向完全图具有条弧。7．n个元素的顺序查找的平均查找长度

3、为。三、单选题（本题的每一备选答案中，只有一个是正确的，请把你认为正确的答案的题号填入题干的括号内，多选不给分，每小题3分，共15分）。聞創沟燴鐺險爱氇谴净。1．若进栈序列为1，2，3，4，则不可能得到的出栈序列是（）（1）3,2,1,4（2）3,2,4,1（3）4,2,3,1（4）2,3,4,12．对于下列二叉树，其后序序列为（）（1）ABDECFG（2）DBEAFCG（3）DEBFGCA（4）GFCEBDA3．对于下列AOV网，不能出现的拓扑序列为（）18/18（1）12345（2）1243

4、5（3）24135（4）21435残骛楼諍锩瀨濟溆塹籟。4．深度为k的完全二叉树所含叶结点的个数最多为（）（1）2k（2）2k-1（3）k（4）2k5．衡量查找算法效率的主要标准是（）（1）元素个数（2）所需的存贮量（3）平均查找长度（4）算法难易程度四、应用题（25分）1．将下列森林转化为二叉树。（3分）2．对下图：（1）写出其邻接矩阵。（2分）（2）按Kruskal算法求其最小生成树；并写出相应的边集数组。（4分）18/183．请画出后序和中序序列相同的二叉树的所有形态。（3分）4．散列函数

5、为H（k）=k%7，散列表的地址从0到6，用线性探查法解决冲突，建立散列表ht。给定关键字序列酽锕极額閉镇桧猪訣锥。{32，13，49，55，22，38，21}要求：（1）构造散列表（只画出表，不写算法）；（5分）（2）求出平均查找长度。（2分）5．用直接选择排序方法对下列关键字进行排序，请写出每一趟排序的结果。（6分）68452090151050五、算法设计（在下列算法的横线上填上适当的表达式或语句或运算符。每空3分，共30分）1．在带头结点的head单链表的结点a之后插入新元素xstruct

6、node{elemtypedata;node*next;};18/18voidlkinsert(node*head,elemtypex){node*s,*p;s=──────────────────────;s->data=_____;p=head->next;while(p!=NULL)&&(p->data!=a)___________________;if(p==NULL)cout<<“不存在结点a”;else{__________________________;_____________

7、_____________;}}2．快速排序voidqksort(intR[],intp,intq)//按递增序对R[p]~R[q]进行快速排序彈贸摄尔霁毙攬砖卤庑。{inti=p,j=q;R[0]=R[i];//R[0]作临时单元while(_______){while(j>i)&&(R[j]____R[0])j--;if(j>i){R[i]=R[j];i++;}while(i

8、i++;j--;if(j>p)qksort(R,p,j);if(i