《数据结构综合练习及参考答案.doc》由会员分享，可在线阅读，更多相关《数据结构综合练习及参考答案.doc（46页珍藏版）》请在金锄头文库上搜索。
1、数据结构（01111、01211）作业题（一）一、判断题（下列各题，你认为正确的，请在前面的括号内打，错误的打。每题1分，共10分）1、（） 2、（） 3、（） 4、（） 5、（）6、（） 7、（） 8、（） 9、（） 10、（）（ ）1. 数据的存贮结构是数据的逻辑结构的存贮映象。（ ）2. 用顺序表来存储线性表时，不需要另外开辟空间来保存数据元素之 间的相互关系。（ ）3. 非线性结构中，至少存在一个元素不止一个直接前趋或不止一个直接后继。（ ）4. 树的最大特点是层次结构。（ ）5. 队列的特点是先进先出。（ ）6. 图的最小生成树是唯一的。（ ）7. 线性表是广义表的特殊形式。（ ）8
2、. 后序序列和中序序列能唯一确定一棵二叉树。（ ）9. 散列表是一种链式存贮结构。（ ）10. 快速排序并非在任何情况下都比其它排序方法速度快。二、填空题（每空2分，共20分）1 数据的存贮结构的四种形式为 存贮、 存贮、 存贮和 存贮。2所有插入和删除都在表的一端进行的线性表称为 。3n个结点的完全二叉树，其深度h= 。4对于顺序循环队列QM，下标从0到M-1，头尾指针分别为F和R，入队时，队尾指针循环加1可表示为R= 。5散列法既是一种查找方法，又是一种 方法。6n个顶点的有向完全图具有 条弧。7n个元素的顺序查找的平均查找长度为 。三、单选题（本题的每一备选答案中，只有一个是正确的，请把
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）GFCEBDA 3对于下列AOV网，不能出现的拓扑序列为（ ）（1） 1 2 3 4 5 （2）1 2 4 3 5 （3）2 4 1 3 5 （4）2 1 4 3 5 4深度为k的完全二叉树所含叶结点的个数最多为（ ）（1）2k （2） 2k-1 （3） k （4） 2
4、k 5衡量查找算法效率的主要标准是（ ）（1） 元素个数 （2） 所需的存贮量 （3） 平均查找长度 （4） 算法难易程度 四、应用题（25分）1将下列森林转化为二叉树。（3分） 2对下图：（1）写出其邻接矩阵。（2分）（2）按Kruskal算法求其最小生成树；并写出相应的边集数组。（4分） 3请画出后序和中序序列相同的二叉树的所有形态。（3分）4散列函数为H（k）=k%7，散列表的地址从0到6，用线性探查法解决冲突，建立散列表ht。给定关键字序列 32，13，49，55，22，38，21要求：（1）构造散列表（只画出表，不写算法）；（5分）（2）求出平均查找长度。（2分）5用直接选择排序方法
5、对下列关键字进行排序，请写出每一趟排序的结果。（6分）68 45 20 90 15 10 50五、算法设计（在下列算法的横线上填上适当的表达式或语句或运算符。每空3分，共30分）1在带头结点的head单链表的结点a之后插入新元素x struct node elemtype data; node *next; ; void lkinsert (node *head, elemtype x) node *s, *p;s= new node ;s-data= x ; p=head-next;while (p!=NULL) &( p-data!=a )_p=p-next_;if (p=NULL)cou
6、tnext=p-next _;_p-next=s _;2 快速排序void qksort (int R , int p, int q) / 按递增序对Rp Rq 进行快速排序 int i=p, j=q;R 0 =R i ; /R0作临时单元 while ( _ii )&( R j _R 0 ) j- -; if (ji) R i =R j ; i+;while (ij )& (R i _R 0 ) i+; if (ip) qksort(R,p,j);if (iq) qksort(R,i,q) ; 数据结构（01111、01211）作业题（二）一、 判断题（下列各题，你认为正确的，请在前面的括号
7、内打，错误的打。每小题1分，共10分）（ ）1. 数据的存贮结构独立于计算机。（ ）2. 线性表简称为“顺序表”。（）3. 对数据的任何运算都不能改变数据原有的结构特性。（）4. 从循环单链表的任一结点出发，可以找到表中所有结点。（ ）5. 栈是一种先进先出的线性表。（ ）6. 链表的主要缺点是不能随机访问。（ ）7. 二叉树是树的特殊形式。（ ）8. 图可以没有边，但不能没有顶点。（ ）9. 冒泡排序算法是稳定的排序。（ ）10. 散列法是一种对关键字进行比较的查找方法。二、 填空题（每空2分，共20分）1、 引 用 、 加工 2、 队列 、 队尾 3、 n0=n2+1 4、 F=R 5、
8、n*(n-1) / 2 6、 AOV 网 7、 8、 插入 1对数据所施加的运算可分为两类，即 型和 型。2将插入限定在表的一端，而删除限定在表的另一端进行的线性表称为 ； 允许插入的一端称为 。3二叉树的叶结点数n0与二度结点数n2的关系是 。4对于顺序循环队列QM，下标从0到M1，头尾指针分别用F和R表示，则队空条件是 。5n个顶点的无向完全图具有 条边。6拓扑排序的操作对象是 。7快速排序的最坏情况是初始序列为正序和反序，其时间复杂度为 。 8希尔排序是属于 排序的改进方法。三、单选题（本题的每一备选答案中，只有一个是正确的，请把你认为正确的答案的题号填入题干的括号内，多选不给分，每小题
9、3分，共15分） 1、（2） 2、（3） 3、（4） 4、（3） 5、（1） 1栈和队列都是（ ）（1）顺序存贮的线性结构 （2）限制存取点的线性结构（3）链接存贮的线性结构 （4）限制存取点的非线性结构2与线性表的链接存贮不相符合的特性是 （ ）（1）便于插、删运算（2）存贮空间动态分配（3）需要连续的存贮空间 （4）只能顺序查找3设二叉树的根为第一层，则第i层上的结点数最多有 （ ）（1）i （2） i +1 （3）i - （4）i -1 4直接选择排序的时间复杂度为 （ ）（1）O（n） （2）O(n2n) （3）O(n2 ) （4）O(2 n)5给定下列有向图，从顶点V1出发，其深度优
10、先搜索序列为（ ）（1）12534 （2）12435 （3） 14325 （4）12345四、应用题（25分） 1画出下列二叉树所对应的森林。（3分） 2对于下边有向图 （1）画出其邻接表（4分） （2）写出三种不同的拓扑序列（3分） 3请画出先序与中序序列相同的二叉树的所有形态。（3分）4给定关键字序列19，14，27，68，84，23，1，20，55，12，10，79，散列函数为HK=K% 11散列表的地址从0到10，用外链法处理冲突，散列地址为d的同义词均挂在以htd为头指针的单链表中。（1）请画出其散列表（不写算法）；（5分）（2）求出成功的平均查找长度。（2分）5对下列关键字序列进行快速排序，请写出第一趟排序结果，并标识出在第一趟排序过程中数据交换的情况。（5分）35 92 15 19 10 80 100第一趟排序结果：五、算法设计（在下列算法的横线内填上适当的语句或表达式。 每空3分，共30分）1 直接插入排序 、 、 、 、 void insertsort(int R )/ 按递增序对R1 R n 进行直接插入排序 int i, j; for ( i=2; i = n ; i+ ) R 0 =R i ; / 设定R0为监视哨 j= i 1 ； while (R 0 R j ) Rj+1=Rj ; j- - ; R j+1 = R0 ; / 插入第i个记录
