2022年电大数据结构期末综合练习一 .docx

精选学习资料 - - - - - - - - - 数据结构（本）期末综合练习一一、单项挑选题1数据元素是数据的基本单位,它（）；A 只能有一个数据项组成 B至少有二个数据项组成C至少有一个数据项为指针类型D可以是一个数据项也可以由如干个数据项组成2（）是性质相同的数据元素的集合,是数据的子集；A数据对象 B数据元素 C数据结构 D数据项3线性表的次序结构中,（）；A 规律上相邻的元素在物理位置上不肯定相邻B规律上相邻的元素在物理位置上也相邻C数据元素是不能随机拜访的D进行数据元素的插入、删除效率较高4设链表中的结点是 NODE 类型的结构体变量,且有 NODE *p ；为了申请一个新结点,并由 p 指向该结点,可用以下语句（）；A p=NODE *mallocsizeofp；Bp=*NODEmallocsizeofNODE；Cp=NODE mallocsizeofp ；Dp=NODE *mallocsizeofNODE；5以下表中可以随机拜访的是（）； A 单向链表 B次序表C单向循环链表 D双向链表6设次序储备的线性长度为 n,要在第 i 个元素之前插入一个新元素,按课本的算法当i=（）时,移动元素次数为 2 A n/2 B n C n-1C1 7 . 设次序储备的线性表长度为n,对于删除操作,设删除位置是等概率的,就删除一个元素平均移动元素的次数为（）；An+1/2B n C2nDn-i 8一个栈的进栈序列是1,2,3,4,就栈的不行能的出栈序列是（）（进出栈操作可以交替进行）A 3, 2,4,1 B3,2,1, 4 C4, 3,2,1 D1,4,2, 3 9设 top 是一个链栈的栈顶指针,栈中每个结点由一个数据域data 和指针域next 组成,设用 x 接收栈顶元素,就出栈操作为（）；A top=top->next ；x=top->data ；Bx=top->data ；top=top->next ；Cx=top-> next ；top=top-> data ； Dtop->next =top ； x=top->data ；10设有一个带头结点的链队列,队列中每个结点由一个数据域 data 和指针域 next 组成,front 和 rear 分别为链队列的头指针和尾指针；设 p 指向要入队的新结点 该结点已被赋值 ,就入队操作为（）；A rear->next=p ；rear=p； B rear->next=p； p = rear；Cp = rear->next ；rear=p； Drear=p；rear->next=p；11以下说法正确选项（）；A 队列是后进先出 B栈的特点是后进后出1 / 12 名师归纳总结 - - - - - - -第 1 页,共 12 页精选学习资料 - - - - - - - - - C栈的删除和插入操作都只能在栈顶进行 D队列的删除和插入操作都只能在队头进行 12以下说法不正确选项（）； A次序栈中,栈满时再进行进栈操作称为“ 上溢”B次序栈中,栈空时再作出栈栈操作称为“ 下溢”C次序队列中,队列的头指针和尾指针均超越队列储备空间的上界,就队列已空 D次序队列中,当尾指针已经超越队列储备空间的上界,就肯定是队列已满 13串函数 StrCmp“abA” ,” aba” 的值为（）；A 1 B 0 C“abAaba” D-1 14设有一个 20 阶的对称矩阵 A ,采纳压缩储备方式,将其下三角部分以行序为主序 储备到一维数组中（矩阵 A 的第一个元素为 a11,数组 b 的下标从 1 开头）,就矩 阵元素 a8,5 在一维数组 b 中的下标是（）；A30 B28 C 40 D33 15设有一个 12 阶的对称矩阵 A ,采纳压缩储备方式将其下三角部分以行序为主序存 储到一维数组 b 中（矩阵 A 的第一个元素为 a1,1,数组 b 的下标从 1 开头）,就矩阵 A 中第4 行的元素在数组 b 中的下标 i 肯定有（）；A7i10 B 11i15 C9i14 D6i9 16深度为 5 的完全二叉树第5 层上有 4 个结点,该树一共有（）个结点；A 28 B30 C 31 D19 17已知一个图的边数为m,就该图的全部顶点的度数之和为（）；A 2mBm C2m+1 D m/2 18已知一个图的全部顶点的度数之和为m,就 m 肯定不行能是（）；A 4 B8 C 12 D9 19以下说法不正确选项（）；A连通图 G 肯定存在生成树 B连通图 G 的生成树中肯定包含 G 的全部顶点 C连通图 G 的生成树中不肯定包含 G 的全部边 D连通图 G 的生成树可以是不连通的 20以下说法正确选项（）； A连通图 G 的生成树中可以包含回路 B连通图 G 的生成树可以是不连通的 C连通图 G 的生成树肯定是连通而不包含回路的 D连通图 G 的生成树肯定是唯独的）；21散列查找的原理是（A在待查记录的关键字值与该记录的储备位置之间建立确定的对应关系 B按待查记录的关键字有序的次序方式储备 C按关键字值的比较进行查找 D基于二分查找的方法（22 对 n 个元素进行冒泡排序,通常要进行n-1 趟冒泡,在第j 趟冒泡中共要进行）次元素间的比较；A j B j-1 C n-j D n-j-1 23排序过程中,每一趟从无序子表中将一个待排序的记录按其关键字的大小放置到已 经排好序的子序列的适当位置,直到全部排好序为止,该排序算法是 ；A直接插入排序 B 快速排序2 / 12 名师归纳总结 - - - - - - -第 2 页,共 12 页精选学习资料 - - - - - - - - - C冒泡排序 D挑选排序24在排序过程中,可以有效地削减一趟排序过程中元素间的比较次数的算法是（）；A冒泡 B 挑选 C折半插入 D直接插入25采纳次序查找法对长度为n 的线性表进行查找（不采纳表尾设监视哨的方法）,最坏的情形下要进行（）次元素间的比较；A n+2 B n Cn-1 D n/2 （）；26 如图如从顶点a 动身按深度优先搜寻法进行遍历,就可能得到的顶点序列为A aebcfd Babedcf b d a c f Cacebdf Dacfbdee 图 1 （）；27 如图如从顶点a 动身按广度优先搜寻法进行遍历,就可能得到的顶点序列为 Aacebdfgh Baebcghdf a Caedfbcgh D abecdfgh b d e g c h f 图 2 28一棵哈夫曼树有n 个叶子结点（终端结点）,该树总共有（）个结点；A2n-2 B 2n-1 C 2n D2n+2 29一棵哈夫曼树总共有23 个结点,该树共有（）个叶结点（终端结点）A10B11C12 D 13 30数据的（）结构与所使用的运算机无关；A规律 B物理 C 储备 D规律与储备二、填空题1通常数据的规律结构包括_、_、_、 _四种类型；2通常可以把一本含有不同章节的书的目录结构抽象成 _结构；3设有一个单向链表,结点的指针域为 next,头指针为 head,p 指向尾结点,为了使该单向链表改为单向循环链表,可用语句 _；3 / 12 名师归纳总结 - - - - - - -第 3 页,共 12 页精选学习资料 - - - - - - - - - 4要在一个单向链表中p 所指向的结点之后插入一个s 所指向的新结点,如链表中结点的指针域为 next,可执行 _和 p->next=s ；的操作；5设有一个单向循环链表,头指针为 head,链表中结点的指针域为 next,p 指向尾结点 的 直 接 前 驱 结 点 , 如 要 删 除 尾 结 点 , 得 到 一 个 新 的 单 向 循 环 链 表 , 可 执 行 操 作_ ；6设有一个非空的链栈,栈顶指针为 hs,要进行出栈操作,用 x 储存出栈结点的值,栈结点的指针域为 next,就可执行 x=hs->data；_；7在一个链队中,f 和 r 分别为队头和队尾指针,队结点的指针域为 next,就插入一个s所指结点的操作为 _；r=s；8在一个不带头结点的非空链队中,f 和 r 分别为队头和队尾指针,队结点的数据域为data,指针域为next,如要进行出队操作,并用变量x 存放出队元素的数据值,就相关操作为 x=f->data ； _；9循环队列的队头指针为f ,队尾指针为r,当 _时说明队列为空；10循环队列的最大储备空间为MaxSize=8 ,采纳少用一个元素空间以有效的判定栈空或栈满,如队头指针front=4 ,就当队尾指针rear= _ 时,队列为空,当rear= _时,队列有6 个元素；11“A” 在储备时占 _个字节；12稀疏矩阵储备时,采纳一个由 定矩阵中的一个非零元素；_ 、_、_3 部分信息组成的三元组唯独确13一棵二叉树没有单分支结点,有6 个叶结点,就该树总共有_个结点；14一棵二叉树次序编号为6 的结点（树中各结点的编号与等深度的完全二叉树中对应位置上结点的编号相同）,如它存在右孩子,就右孩子的编号为 _；15依据二叉树的递归定义,对二叉树遍历的常用算法有_、_、 _三种；16结构中的数据元素存在多对多的关系称为 _结构；17把数据储备到运算机中 ,并详细表达数据之间的规律结构称为 _结构；18结构中的数据元素存在一对多的关系称为 _结构；19如图 3 所示的二叉树,其后序遍历序列为；a b c d e f i g h 图 3 _ _；20如图 4 所示的二叉树,其前序遍历序列为a b c 名师归纳总结 d 4 / 12 g 第 4 页,共 12 页e - - - - - - -精选学习资料 - - - - - - - - - 图 4 21二叉树为二叉排序的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值；这种说法是 _的； 回答正确或不正确 22在队列的次序储备结构中,当插入一个新的队列元素时,指针的值增 1,当删除一个元素队列时,指针的值增 1；23依据搜寻方法的不同,图的遍历有 _、 _两种方法24循环队列的引入,目的是为了克服；三、综合题 1（ 1）已知某二叉树的后序遍历序列是debca,中序遍历序列是dbeac,试画出该二叉树（ 2）如上述二叉树的各个结点的字符分别代表不同的整数（其中没有相等的）,并恰好使该树成为一棵二叉排序树,试给出（ 3）给出该树的前序遍历序列a、b、c、d、e 的大小关系2（ 1）设 head1和 p1分别是不带头结点的单向链表 A 的头指针和尾指针,head2和 p2分别是不带头结点的单向链表 B 的头指针和尾指针,如要把 B 链表接到 A 链表之后,得到一个以 head1 为头指针的单向循环链表,写出其中两个关键的赋值语句（不用完整程序,结点的链域为 next）；（2）单向链表的链域为 next,设指针 p 指向单向链表中的某个结点,指针 s 指向一个要插入链表的新结点,现要把 s 所指结点插入 p 所指结点之后,某同学采纳以下语句： p->next=s ； s->next=p->next ；这样做正确吗？如正确就回答正确,如不正确就说明应如何改写5 / 12 名师归纳总结 - - - - - - -第 5 页,共 12 页精选学习资料 - - - - - - - - - 3（ 1）设有一个整数序列 一棵二叉排序树40 ,28,6,72,100,3,54 依次取出序列中的数,构造（2）对上述二叉排序树,在等概率条件下,求胜利查找的平均查找长度4（ 1）画出对长度为10 的有序表进行折半查找的判定树（以序号1,2, 10 表示树结点）（2）对上述序列进行折半查找,求等概率条件下,胜利查找的平均查找长度5（ 1）利用挑选过程把序列42 , 82 , 67, 102, 16, 32, 57, 52 建成堆（小根堆）,画出相应的完全二叉树（不要求中间过程）（2）写出对上述堆对应的完全二叉树进行中序遍历得到的序列6 / 12 名师归纳总结 - - - - - - -第 6 页,共 12 页精选学习资料 - - - - - - - - - 6（ 1）利用挑选法,把序列37 , 77, 62, 97, 11, 27, 52, 47 建成堆（小根堆）,画出相应的完全二叉树（2）写出对上述堆所对应的二叉树进行前序遍历得到的序列四、程序填空题1以下函数在 a0到an-1 中,用折半查找算法查找关键字等于该记录的下标,失败时返回-1,完成程序中的空格typedef struct int key ； NODE ；int Binary_SearchNODEa,int n, int k int low,mid,high； low=0； high=n-1； while _1_ mid=low+high/2； ifamid.key=k return _2_ ； else if _3_ low=mid+1； else _4_ ； _5_ ； k的记录,查找胜利返回2以下函数为直接挑选排序算法,对 a1,a2, an中的记录进行直接挑选排序,完成程序中的空格typedef struct int key ；7 / 12 名师归纳总结 - - - - - - -第 7 页,共 12 页精选学习资料 - - - - - - - - - NODE ；void selsortNODE a,int n int i,j,k ；NODE temp ；fori=1 ；i<= _1_ ；i+ k=i ；forj=i+1 ；j<= _2_ ；j+ ifaj.key<ak.key _3_；ifi.=k temp=ai ；_4_；_5_； 3以下函数为链队列的入队操作,x 为要入队的结点的数据域的值,front 、rear 分别是链队列的队头、队尾指针struct node ElemType data ；struct node *next ；struct node *front , *rear；void InQueueElemType x struct node *p；_1_ ； p= struct node* p->data=xp->next=NULL ；_2_ ； rear= _3_ ； 4以下程序是中序遍历二叉树的递归算法的程序,完成程序中空格部分（树结构中 左、右指针域分别为 left 和 right ,数据域 data 为字符型, BT 指向根结点）；void Inorder struct BTreeNode *BT ifBT.=NULL （1）；（2）；（3）；8 / 12 名师归纳总结 - - - - - - -第 8 页,共 12 页精选学习资料 - - - - - - - - - 答案 一、单项挑选题1 D2 A 3 B4 D 5 B6 C 7 A 8 D 9 B10 A11 C 12 D 13 D 14D 15A 16 D 17 A 18 D 19 D20C 21 A 22 C 23A 24 C 25 B 26 B 27 D 28 B 29 C 30 A 二、填空题1集合；线性；树形；图状 2树形 3p->next=head；4s->next= p->next ；5p->next=head；6hs=hs->next；7r->next=s 8f=f->next ；9r= =f 104；2 111；2 12行号；列号；非零元 1311 1413 15先序；中序；后序 16图状 17物理（储备）18树形 19gdbeihfca 20 abdefcg 21错误22尾 头 23深度优先 广度优先24假上溢三、综合应用题1（ 1）a 名师归纳总结 d b e c 9 / 12 第 9 页,共 12 页- - - - - - -精选学习资料 - - - - - - - - - （2）d<b<e<a<c （3）abdec 2（1）p1->next= head2；p2->next= head1；（2）不对, s->next=p->next ；p->next=s ；3（ 1）40 28 72 6 54 100 3 （2）ASL= （1x1+2x2+3x3+4 ）/7=18/7 4（ 1）5 1 2 3 4 6 8 9 10 7 （2）ASL= （1x1+2x2+3x4+4x3 ）/10=29/10 5名师归纳总结 （1）52 102 82 42 67 57 10 / 12 52 42 16 32 57 第 10 页,共 12 页32 67 16 82 - - - - - - -精选学习资料 - - - - - - - - - 102 初始树 堆（2）102,52,42,82,16,67,32, 57 6（ 1）77 37 62 37 11 27 47 97 11 27 52 堆9747 77 62 52 初始树（2） 11,37,47,97,77,27,62, 52 四、程序填空题1（ 1） low<=high （2）mid （3）amid.key<k ；（4）high=mid-1 （5）return -1 ；2（ 1） n-1 （2）n （3）k=j （4）ai=ak （5）ak=temp 3（ 1） mallocsizeof struct node （2）rear->next=p （3）p 11 / 12 名师归纳总结 - - - - - - -第 11 页,共 12 页精选学习资料 - - - - - - - - - 4（1） InorderBT->left （2）printf“ %c” ,BT->data （3） InorderBT->right 12 / 12 名师归纳总结 - - - - - - -第 12 页,共 12 页