2022年数据结构期末试卷七.docx
精选学习资料 - - - - - - - - - 多练出技巧 巧思出硕果数据结构试卷（七）一、挑选题 30 分 1设某无向图有 n 个顶点,就该无向图的邻接表中有（）个表头结点；A 2n B n C n/2 D nn-1 2设无向图 G 中有 n 个顶点,就该无向图的最小生成树上有（）条边；A n B n-1 C 2n D 2n-1 3设一组初始记录关键字序列为 60,80,55,40,42,85,就以第一个关键字 45 为基准而得到的一趟快速排序结果是（）；A 40,42,60,55,80,85 C 42,40,55, 60,80,85 B 42,45,55,60,85,80 D 42,40,60, 85,55,80 4（）二叉排序树可以得到一个从小到大的有序序列；A 先序遍历 B 中序遍历 C 后序遍历 D 层次遍历5设根据从上到下、从左到右的次序从 1 开头对完全二叉树进行次序编号,就编号为 i 结点的左孩子结点的编号为（）；A 2i+1 B 2i C i/2 D 2i-1 6程序段 s=i=0；do i=i+1； s=s+i； whilei<=n ；的时间复杂度为（）；A On B Onlog2n C On 2 D On 3/2 7设带有头结点的单向循环链表的头指针变量为 head,就其判空条件是（）；A head=0 B head->next=0 C head->next=head D head.=0 8设某棵二叉树的高度为 10,就该二叉树上叶子结点最多有（）；A 20 B 256 C 512 D 1024 9设一组初始记录关键字序列为13, 18,24,35, 47,50,62,83,90,115,134,就利名师归纳总结 用二分法查找关键字90 需要比较的关键字个数为（）；）；第 1 页,共 5 页A 1 B 2 C 3 D 4 10.设指针变量top 指向当前链式栈的栈顶,就删除栈顶元素的操作序列为（A top=top+1; B top=top-1; C top->next=top; D top=top->next; - - - - - - -精选学习资料 - - - - - - - - - 多练出技巧 巧思出硕果二、判定题 20 分 1不论是入队列操作仍是入栈操作,在次序储备结构上都需要考虑“溢出 ”情形；（）2当向二叉排序树中插入一个结点,就该结点肯定成为叶子结点；（）3设某堆中有n 个结点,就在该堆中插入一个新结点的时间复杂度为Olog2n；（4完全二叉树中的叶子结点只可能在最终两层中显现；（）5哈夫曼树中没有度数为1 的结点；（）6对连通图进行深度优先遍历可以拜访到该图中的全部顶点；（7先序遍历一棵二叉排序树得到的结点序列不肯定是有序的序列；（）8由树转化成二叉树,该二叉树的右子树不肯定为空；（）9线性表中的全部元素都有一个前驱元素和后继元素；（）10.带权无向图的最小生成树是唯独的；（）三、填空题 30 分 1.1.设指针变量p 指向双向链表中的结点A,指针变量s 指向被插入的结点X,就在结点 A 的后面插入结点X 的操作序列为 _=p；s->right=p->right ；_=s；p->right->left=s ；（设结点中的两个指针域分别为 left 和 right）；2. 2. 设完全有向图中有 n 个顶点,就该完全有向图中共有 _条有向条；设完全无向图中有 n 个顶点,就该完全无向图中共有 _条无向边；3. 3. 设关键字序列为 Kl,K2,Kn,就用挑选法建初始堆必需从第 _个元素开头进行挑选；4.4.解决散列表冲突的两种方法是_和_；5.5.设一棵三叉树中有50 个度数为 0 的结点, 21 个度数为 2 的结点, 就该二叉树中度数为 3 的结点数有 _个；名师归纳总结 6.6.高度为 h 的完全二叉树中最少有_个结点,最多有_个结点；第 2 页,共 5 页7.7.设有一组初始关键字序列为24,35,12,27,18,26,就第 3 趟直接插入排序结8.束后的结果的是_ ；8.设有一组初始关键字序列为24,35,12,27,18,26,就第 3 趟简洁挑选排序结束后的结果的是_ ；- - - - - - -精选学习资料 - - - - - - - - - 9.9.多练出技巧巧思出硕果设一棵二叉树的前序序列为ABC,就有 _种不同的二叉树可以得到这种序列；10.10.下面程序段的功能是实现一趟快速排序,请在下划线处填上正确的语句；struct record int key;datatype others; void quickpassstruct record r, int s, int t, int &i int j=t; struct record x=rs; i=s; whilei<j while 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.1.设计在链式结构上实现简洁挑选排序算法；2.2.设计在次序储备结构上实现求子串算法；3.3.设计求结点在二叉排序树中层次的算法；数据结构试卷（七）一、挑选题1B 2B 3C 4B 5B 6A 7C 8C 9B 10D 二、判定题名师归纳总结 - - - - - - -第 3 页,共 5 页精选学习资料 - - - - - - - - - 1对2对3对多练出技巧巧思出硕果4对5对6对7对8错9错10错三、填空题1.1.s->left=p ,p->right 2.2.nn-1,nn-1/2 3.3.n/2 4.4.开放定址法,链地址法5.5.14 6.6.2h-1,2h-1 7.7.12,24,35,27,18,26 8.8.12,18,24,27,35,26 9.9.5 10.10.i<j && ri.key<x.key , ri=x 四、算法设计题1.1.设计在链式结构上实现简洁挑选排序算法；void simpleselectsorlklistlklist *&head lklist *p,*q,*s; int min,t; ifhead=0 |head->next=0 return; forq=head; q.=0;q=q->next min=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; 名师归纳总结 - - - - - - -第 4 页,共 5 页精选学习资料 - - - - - - - - - 2.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.3.设计求结点在二叉排序树中层次的算法；int lev=0; typedef struct nodeint key; struct node *lchild,*rchild;bitree; void levelbitree *bt,int x if bt.=0 lev+; if bt->key=x return; else if bt->key>x levelbt->lchild,x; else levelbt->rchild,x; 名师归纳总结 - - - - - - -第 5 页,共 5 页
