数据结构试卷及参考答案.docx

《数据结构试卷及参考答案.docx》由会员分享，可在线阅读，更多相关《数据结构试卷及参考答案.docx（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品名师归纳总结数据结构试卷（七）一、挑选题 30 分1设某无向图有n 个顶点，就该无向图的邻接表中有（）个表头结点。A2nBnCn/2Dnn-12设无向图G 中有 n 个顶点，就该无向图的最小生成树上有（）条边。AnBn-1C2nD 2n-13设一组初始记录关键字序列为60， 80，55， 40，42，85，就以第一个关键字45 为基准而得到的一趟快速排序结果是（）。A 40， 42， 60， 55，80， 85B42， 45， 55， 60，85， 80 C 42，40， 55， 60， 80，85D 42， 40，60， 85， 55， 804（）二叉排序树可以得到一个从小到大的有序序列

2、。A 先序遍历B 中序遍历C 后序遍历D 层次遍历5设根据从上到下、从左到右的次序从1 开头对完全二叉树进行次序编号，就编号为i 结点的左孩子结点的编号为（）。A 2i+1B 2iC i/2D 2i-16程序段s=i=0。 do i=i+1 。 s=s+i。 whileinext=0Chead-next=headDhead.=0 8设某棵二叉树的高度为10，就该二叉树上叶子结点最多有（）。A 20B 256C 512D 10249设一组初始记录关键字序列为13， 18， 24，35， 47， 50， 62，83， 90， 115， 134,就利用二分法查找关键字90 需要比较的关键字个数为（）

3、。A 1B 2C 3D 4可编辑资料 - - - 欢迎下载精品名师归纳总结10.设指针变量top 指向当前链式栈的栈顶，就删除栈顶元素的操作序列为（）。Atop=top+1;Btop=top-1;Ctop-next=top;Dtop=top-next;二、判定题 20 分1不论是入队列操作仍是入栈操作，在次序储备结构上都需要考虑“溢出”情形。（）2当向二叉排序树中插入一个结点，就该结点肯定成为叶子结点。（）3设某堆中有n 个结点，就在该堆中插入一个新结点的时间复杂度为Olog2n。（）4完全二叉树中的叶子结点只可能在最终两层中显现。（）5哈夫曼树中没有度数为1 的结点。（）6对连通图进行深度优

4、先遍历可以拜访到该图中的全部顶点。（）7先序遍历一棵二叉排序树得到的结点序列不肯定是有序的序列。（）8由树转化成二叉树，该二叉树的右子树不肯定为空。（）9线性表中的全部元素都有一个前驱元素和后继元素。（）10.带权无向图的最小生成树是唯独的。（）三、填空题 30 分1. 设指针变量p 指向双向链表中的结点A，指针变量s 指向被插入的结点X，就在结点A的后面插入结点X 的操作序列为 =p 。 s-right=p-right 。 =s 。p-right-left=s 。（设结点中的两个指针域分别为left 和 right ）。2. 设完全有向图中有n 个顶点， 就该完全有向图中共有 条有向条。 设

5、完全无向图中有 n 个顶点，就该完全无向图中共有 条无向边。3. 设关键字序列为Kl，K2 ， Kn，就用挑选法建初始堆必需从第 个元素开头进行挑选。4. 解决散列表冲突的两种方法是 和 。5. 设一棵三叉树中有50 个度数为0 的结点， 21 个度数为 2 的结点，就该二叉树中度数为3 的结点数有 个。可编辑资料 - - - 欢迎下载精品名师归纳总结6. 高度为 h 的完全二叉树中最少有 个结点，最多有 个结点。7. 设有一组初始关键字序列为24， 35，12， 27，18， 26，就第 3 趟直接插入排序终止后的结果的是 。8. 设有一组初始关键字序列为24， 35，12， 27，18，

6、26，就第 3 趟简洁挑选排序终止后的结果的是 。9. 设一棵二叉树的前序序列为ABC，就有 种不同的二叉树可以得到这种序列。10. 下面程序段的功能是实现一趟快速排序，请在下划线处填上正确的语句。struct record int key;datatype others;void quickpassstruct record r, int s, int t, int &iint j=t; struct record x=rs; i=s; whileijwhile ix.key j=j-1;if ij ri=rj;i=i+1;while i=i+1;if ileft=p ，p-right 2.

7、nn-1， nn-1/23.n/24.开放定址法，链的址法5.146.2h-1， 2h-17.12， 24， 35， 27， 18， 268.12， 18， 24， 27， 35， 269.510.ij & ri.keynext=0 return; forq=head; q.=0;q=q-nextmin=q-data; s=q;forp=q-next; p.=0;p=p-next ifminp-datamin=p-data; s=p; ifs.=qt=s-data; s-data=q-data; q-data=t;2. 设计在次序储备结构上实现求子串算法。void substringchar s , long start, long count, char t long i,j,length=strlens;if startlength printfThe copy position is wrong;else if start+count-1length printfToo characters to be copied; else fori=start-1,j=0; ikey=x return; else if bt-keyx levelbt-lchild,x; else levelbt-rchild,x;可编辑资料 - - - 欢迎下载