数据结构试卷及参考答案.docx
精品名师归纳总结数据结构试卷（七）一、挑选题 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（）二叉排序树可以得到一个从小到大的有序序列。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。 whilei<=n 。的时间复杂度为（）。A OnB Onlog2nC On2D On3/27设带有头结点的单向循环链表的头指针变量为head，就其判空条件是（）。Ahead=0Bhead->next=0Chead->next=headDhead.=0 8设某棵二叉树的高度为10，就该二叉树上叶子结点最多有（）。A 20B 256C 512D 10249设一组初始记录关键字序列为13， 18， 24，35， 47， 50， 62，83， 90， 115， 134,就利用二分法查找关键字90 需要比较的关键字个数为（）。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对连通图进行深度优先遍历可以拜访到该图中的全部顶点。（）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 个顶点， 就该完全有向图中共有 条有向条。 设完全无向图中有 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， 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; whilei<jwhile i<j && rj.key>x.key j=j-1;if i<j ri=rj;i=i+1;while i=i+1;if i<j rj=ri;j=j-1; ;四、算法设计题20 分1. 设计在链式结构上实现简洁挑选排序算法。2. 设计在次序储备结构上实现求子串算法。3. 设计求结点在二叉排序树中层次的算法。可编辑资料 - - - 欢迎下载精品名师归纳总结数据结构试卷（七）参考答案一、挑选题1B2 B3 C4 B5 B6A7 C8 C9 B10D二、判定题1对2对3对4对5对6对7对8错9错10错三、填空题1.s->left=p ，p->right 2.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.i<j && ri.key<x.key ， ri=x四、算法设计题1. 设计在链式结构上实现简洁挑选排序算法。可编辑资料 - - - 欢迎下载精品名师归纳总结void simpleselectsorlklistlklist *&headlklist *p,*q,*s;int min,t; ifhead=0 |head->next=0 return; forq=head; q.=0;q=q->nextmin=q->data; s=q;forp=q->next; p.=0;p=p->next ifmin>p->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 start<1 | start>length printf"The copy position is wrong"else if start+count-1>length printf"Too characters to be copied" else fori=start-1,j=0; i<start+count-1;i+,j+ tj=si; tj= '0'3. 设计求结点在二叉排序树中层次的算法。int lev=0;typedef struct nodeint key; struct node *lchild,*rchild;bitree; void levelbitree *bt,int xif bt.=0可编辑资料 - - - 欢迎下载精品名师归纳总结lev+; if bt->key=x return; else if bt->key>x levelbt->lchild,x; else levelbt->rchild,x;可编辑资料 - - - 欢迎下载
