《《数据结构》(本)模拟试题二》由会员分享，可在线阅读，更多相关《《数据结构》(本)模拟试题二（7页珍藏版）》请在金锄头文库上搜索。
1、数据结构（本）模拟试题二一、填空题（每小题2分，共24分）1结构中的数据元素存在多对多的关系称为_ _结构。2要求在n个数据元素中找其中值最大的元素，设基本操作为元素间的比较。则比较的次数和算法的时间复杂度分别为_和 。3设有一个头指针为head的单向循环链表，p指向链表中的结点，若p-next= =_，则p所指结点为尾结点。4向一个栈顶指针为h的链栈中插入一个s所指结点时，可执行s-next=h和 。5在一个链队中，设f和r分别为队头和队尾指针，则插入s所指结点的操作为_和r=s; (结点的指针域为next)6设有n阶对称矩阵A，用数组S进行压缩存储，当inext= =NULL Chead-
2、next= =head Dhead!=NULL9从一个栈顶指针为top的链栈中删除一个结点时，用变量x保存被删结点的值，则执行（ ）。 Ax=top-data; top=topnext; Bx=top-data; Ctop=top-next; x=top-data; Dtop=top-next; x=data;10线性结构中数据元素的位置之间存在（ ）的关系。 A一对一 B一对多 C多对多 D每一个元素都有一个直接前驱和一个直接后继11一棵完全二叉树共有5层，且第5层上有六个结点，该树共有（ ）个结点。 A30 B20 C21 D2312设顺序存储的线性表长度为n，要删除第i个元素，按课本的算
3、法，当i=（ ）时，移动元素的次数为3A3 Bn/2 Cn-3 D413在一个无向图中，所有顶点的度数之和等于边数的（ ）倍。 A3 B2.5 C1.5 D214 .以下说法不正确的是（ ）。A栈的特点是后进先出 B队列的特点是先进先出C栈的删除操作在栈底进行，插入操作在栈顶进行D队列的插入操作在队尾进行，删除操作在队头进行15已知如图2所示的一个图，若从顶点V1出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（ ）。 AV1V2V4V8V5V3V6V7 BV1V2V4V5V8V3V6V7CV1V2V4V8V3V5V6V7 DV1V3V6V7V2V4V5V8V6V7V1V2V3V8V
4、4V5 图2三、综合题（每小题10分，共30分）1一组记录的关键字序列为（46，79，56，38，40，84）（1）利用快速排序的方法，给出以第一个记录为基准得到的一次划分结果（给出逐次交换元素的过程，要求以升序排列）（2）对上述序列用堆排序的方法建立大根堆，要求以二叉树逐次描述建堆过程。2设查找表为(16,15,20,53,64,7), (1)用冒泡法对该表进行排序（要求升序排列），写出每一趟的排序过程，通常对n个元素进行冒泡排序要进行多少趟冒泡？第j趟要进行多少次元素间的比较？ (2)在排序后的有序表的基础上，画出对其进行折半查找所对应的判定树.(要求以数据元素作为树结点)(3)求在等概率
5、条件下,对上述有序表成功查找的平均查找长度.3(1)“一棵二叉树若它的根结点的值大于左子树所有结点的值，小于右子树所有结点的值，则该树一定是二叉排序树”。该说法是否正确，若认为正确，则回答正确，若认为不正确则说明理由？(2)设有查找表7，16，4，8，20，9，6，18，5，依次取表中数据构造一棵二叉排序树. 对上述二叉树给出后序遍历的结果.四、程序填空题（每空2分，共16分）1以下函数在a0到an-1中，用折半查找算法查找关键字等于k的记录，查找成功返回该记录的下标，失败时返回-1，完成程序中的空格typedef struct int key;NODE;int Binary_Search(N
6、ODE a,int n, int k) int low,mid,high; low=0; high=n-1; while(_(1)_) mid=(low+high)/2; if(amid.key=k) return _(2)_; else if(_(3)_) low=mid+1; else _(4)_; _(5)_; 2以下程序是后序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中，左、右指针域分别为left和right，数据域data为字符型，BT指向根结点）。void Postorder (struct BTreeNode *BT) if(BT!=NULL) （1） ; （2） ;
7、 （3） ; 参考答案一、填空题（每小题2分，共24分）1图状 （网状）2n-1, O（1）3head 4h =s;5r-next=s; 6i(i-1)/2+j72i和2i+1 8n 9中序10abdefcg11不正确 12关键字相等的记录二、单项选择题（每小题2分，共30分）1A 2D 3D 4C 5A 6C 7B 8B 9A 10A 11C 12C 13D 14C 15A三、综合题（每小题10分，共30分）1(1)初始序列 46，79，56，38，40，8440，79，56，38，40，8440，79，56，38，79，8440，38，56，38，79，8440，38，56，56，79，8
8、440，38，46，56，79，845679384084468479384046566567938404679384084845646(2) 2(1)原序列16 15 20 53 64 7 15 16 20 53 7 64 n-1趟 15 16 20 7 53 64 n-j次 15 16 7 20 53 64 15 7 16 20 53 64 7 15 16 20 53 6471520641653(2)(3)平均查找长度=（1*1+2*2+3*3）/6=14/63(1)不正确，二叉排序树要求其子树也是二叉排序树。468952071618(2)后续遍历 5，6，4，9，8，18，20，16，7四、程序填空题（每空2分，共16分）1（1）low=high（2）mid（3）amid.keyk;（4）high=mid-1（5）return -1;2（1）
