浙江农林大学2018-2019学年数据结构试卷A

共6页，第1页浙江农林大学20182019学年第二学期考试卷(A)课程名称：数据结构课程类别：必修考试方式：闭卷注意事项：1、本试卷满分100分。2、考试时间120分钟。题号一二三四五六七八得分得分评阅人填空题(1×12=12分)1、常见的四类基本数据结构有：线性结构、_________、__________和图状结构。2、栈又称为表，队列又称为表。3.串S=″Iamaworker″的长度是________。4、设有二维数组A[0..9,0..19]，其每个元素占两个字节，第一个元素的存储地址为100，若按行优先顺序存储，则元素A[6,6]的存储地址为。5、使用折半查找时，静态查找表必须不仅是______，并且______存储。6、利用MST性质来构造最小生成树的两种常用算法为_________和__________。7、每次直接或通过基准元素间接比较两个元素，若出现逆序排列时就交换它们的位置，此种排序方法叫做排序；每次使两个相邻的有序表合并成一个有序表的排序方法叫做排序。判断(对的打∨,错误打×,8×2=16分)在数据元素的非空有限集中，存在唯一的一个被称为”前驱”的元素，也存在唯一的一个称为”后继”的元素()一般情况下，在第i(1<=i<=n)个元素之前插入一个元素，需要将第n个到第i个元素向后移动一个位置，移动元素的个数为n-i+1()队列的基本特征是先进后出()数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。赫夫曼树是指带权路径长度WPL最小的二叉树。一般而言，在给定条件下构造出的赫夫曼树不是唯一的。()6、路径长度最长的路径为关键路径。()7、由树转化成二叉树，其根的右子女指针总是空的。()8、直接选择排序是一种稳定的排序方法。()选择题（7×3=21分）线性链表不具有的特点().A.随机访问B.不必事先估计所需存储空间大小C.插入与删除时不必移动元素D.所需空间与线性表长度成正比2、带头结点的单链表first为空的判定条件是： A.first==NULL; B.first->link==NULL; C.first->link==first; D.first!=NULL;3、一个栈的输入序列为1，2，3，4，下面哪一个序列不可能是这个栈的输出序列？

A.1，3，2，4

B.2，3，4，1

C.4，3，1，2

D.3，4，2，14、具有65个结点的完全二叉树的高度为().(根的层次号为1)A.8B.7C.6D.55、ALV树是一种平衡的二叉排序树，树中任一结点的()

A.左、右子树的高度均相同

B.左、右子树高度差的绝对值不超过1C左子树的高度均大于右子树的高度

D.左子树的高度均小于右子树的高度6、若一棵二叉树具有10个度为2的结点，则该二叉树的度为0的结点个数是A.9B.11C.12D.不确定

7、若待排序序列在排序前已按其排序码递增顺序排列,则采用()方法比较次数最少.

A.直接插入排序B.快速排序

C.归并排序D.直接选择排序基本概念分析题(共31分)1、写出下列图的邻接矩阵和邻接表（5+5分）V2V2V1V1V3V5V3V5V6V4V6V42、已知一棵二叉树的前序和中序序列如下：（6+5分）前序序列：A,B,C,D,E,F,G,H,I,J中序序列：C,B,A,E,F,D,I,H,J,G画出该二叉排序树给出该二叉排序树的后序遍历3、设待排序文件的关键码为（512,275,908,677,503,765,612,897,154,170）以第一元素为分界元素进行快速排序（按关键码值递增顺序），请给出一趟扫描后的结果。（10分）五、算法设计题(本大题共2小题，每题10分，共20分)1、假设二叉树T采用如下定义的存储结构：(本题10分)

typedefstructNode{

DataTypedata;

structNode*lchild,*rchild;

}*BiTree;其中，结点的lchild域和rchild域已分别填有指向其左、右孩子结点的指针，编写一个递归算法，计算一棵二叉树中，度数为2的节点个数。IntCountNode(BiTreeT){//考试编写代码}2、编写一个从数组A[n]中进行二分查找的非递归算法。(本题10分)intSearchBin(int*A,intn,intkey){//考试编写代码}数据结构答卷学院：专业班级：学院：专业班级：姓名：学号：装订线内不要答题2、考试时间120分钟。题号一二三四五得分得分评阅人一、填空题(1×12=12分)1、_________、__________。2、，。3.________。4、。5、______，______。6、_________，_________。7、，。二、判断(对的打∨,错误打×,8×2=16分)1、()2、()3、()4、()5、()6、()7、()8、()三、选择题（7×3=21分）1、().2、（）3、()4、()5、()6、（