《2022年电大数据结构期末综合练习一 .pdf》由会员分享，可在线阅读，更多相关《2022年电大数据结构期末综合练习一 .pdf（12页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1 / 12 数据结构（本）期末综合练习一一、单项选择题1数据元素是数据的基本单位，它（）。A只能有一个数据项组成 B至少有二个数据项组成C至少有一个数据项为指针类型D可以是一个数据项也可以由若干个数据项组成2（）是性质相同的数据元素的集合，是数据的子集。A数据对象 B数据元素 C数据结构 D数据项3线性表的顺序结构中，（）。A逻辑上相邻的元素在物理位置上不一定相邻B逻辑上相邻的元素在物理位置上也相邻C数据元素是不能随机访问的D进行数据元素的插入、删除效率较高4设链表中的结点是NODE 类型的结构体变量，且有NODE *p；为了申请一个新结点，并由 p 指向该结点，可用以下语句（）。Ap=(N
2、ODE *)malloc(sizeof(p)。Bp=(*NODE)malloc(sizeof(NODE)。Cp=(NODE )malloc(sizeof(p) 。Dp=(NODE *)malloc(sizeof(NODE)。5以下表中可以随机访问的是（）。 A 单向链表B顺序表C单向循环链表D双向链表6设顺序存储的线性长度为n，要在第i 个元素之前插入一个新元素，按课本的算法当i=（）时，移动元素次数为2 An/2 Bn C n-1C1 7 . 设顺序存储的线性表长度为n，对于删除操作，设删除位置是等概率的，则删除一个元素平均移动元素的次数为（）。A(n+1)/2B n C2nDn-i 8一个
3、栈的进栈序列是1，2，3，4，则栈的不可能的出栈序列是（）（进出栈操作可以交替进行）A3， 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 和指针域nex
4、t 组成，front 和 rear 分别为链队列的头指针和尾指针。设p指向要入队的新结点(该结点已被赋值)，则入队操作为（）。Arear-next=p 。rear=p。 Brear-next=p。 p = rear。Cp = rear-next。rear=p。 Drear=p。rear-next=p。11以下说法正确的是（）。A队列是后进先出 B栈的特点是后进后出精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 12 页2 / 12 C栈的删除和插入操作都只能在栈顶进行D队列的删除和插入操作都只能在队头进行12以下说法不正确的是（）。 A
5、顺序栈中，栈满时再进行进栈操作称为“上溢”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 C40 D33 15设有一个12 阶的对称矩阵
6、A，采用压缩存储方式将其下三角部分以行序为主序存储到一维数组b 中（矩阵A 的第一个元素为a1,1，数组 b 的下标从1 开始），则矩阵A 中第4行的元素在数组b 中的下标 i 一定有（）。A7i10 B11i15 C9i14 D6i9 16深度为5 的完全二叉树第5 层上有 4个结点，该树一共有（）个结点。A 28 B30 C31 D19 17已知一个图的边数为m，则该图的所有顶点的度数之和为（）。A 2mBm C2m+1 D m/2 18已知一个图的所有顶点的度数之和为m，则 m 一定不可能是（）。A 4 B8 C 12 D9 19以下说法不正确的是（）。A连通图G 一定存在生成树B连通图
7、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 Bj-1 C n-j D n-
8、j-1 23排序过程中，每一趟从无序子表中将一个待排序的记录按其关键字的大小放置到已经排好序的子序列的适当位置，直到全部排好序为止，该排序算法是( )。A直接插入排序 B 快速排序精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 12 页3 / 12 a b e c d h g f a b e c d f C冒泡排序 D选择排序24在排序过程中，可以有效地减少一趟排序过程中元素间的比较次数的算法是（）。A冒泡 B选择 C折半插入D直接插入25采用顺序查找法对长度为n 的线性表进行查找（不采用表尾设监视哨的方法），最坏的情况下要进行（）次元
9、素间的比较。A n+2 B n Cn-1 Dn/2 26如图若从顶点a 出发按深度优先搜索法进行遍历，则可能得到的顶点序列为（）。A aebcfd Babedcf Cacebdf Dacfbde图 1 27如图若从顶点a 出发按广度优先搜索法进行遍历，则可能得到的顶点序列为（）。 Aacebdfgh Baebcghdf Caedfbcgh D abecdfgh 图 2 28一棵哈夫曼树有n 个叶子结点（终端结点），该树总共有（）个结点。A2n-2 B 2n-1 C2n D2n+2 29一棵哈夫曼树总共有23 个结点，该树共有（）个叶结点（终端结点）A10B11C12 D13 30数据的（）结构
10、与所使用的计算机无关。A逻辑 B物理 C存储 D逻辑与存储二、填空题1通常数据的逻辑结构包括_、_、_、 _四种类型。2通常可以把一本含有不同章节的书的目录结构抽象成_结构。3设有一个单向链表，结点的指针域为next，头指针为head，p 指向尾结点，为了使该单向链表改为单向循环链表，可用语句_。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 12 页4 / 12 4要在一个单向链表中p 所指向的结点之后插入一个s 所指向的新结点，若链表中结点的指针域为next，可执行 _和 p-next=s。的操作。5设有一个单向循环链表，头指针为h
11、ead，链表中结点的指针域为next，p 指向尾结点 的 直 接 前 驱 结 点 ， 若 要 删 除 尾 结 点 ， 得 到 一 个 新 的 单 向 循 环 链 表 ， 可 执 行 操 作_ 。6设有一个非空的链栈，栈顶指针为hs，要进行出栈操作，用x 保存出栈结点的值，栈结点的指针域为next，则可执行x=hs-data。_。7在一个链队中，f 和 r 分别为队头和队尾指针，队结点的指针域为next，则插入一个s所指结点的操作为_；r=s；8在一个不带头结点的非空链队中，f 和 r 分别为队头和队尾指针，队结点的数据域为data，指针域为next，若要进行出队操作，并用变量x 存放出队元素的
12、数据值，则相关操作为 x=f-data 。 _。9循环队列的队头指针为f，队尾指针为r，当 _时表明队列为空。10循环队列的最大存储空间为MaxSize=8，采用少用一个元素空间以有效的判断栈空或栈满，若队头指针front=4 ，则当队尾指针rear= _ 时，队列为空，当rear= _时，队列有6 个元素。11“ A”在存储时占_个字节。12稀疏矩阵存储时，采用一个由_ 、_、_3 部分信息组成的三元组唯一确定矩阵中的一个非零元素。13一棵二叉树没有单分支结点，有6个叶结点，则该树总共有_个结点。14一棵二叉树顺序编号为6 的结点（树中各结点的编号与等深度的完全二叉树中对应位置上结点的编号相
13、同），若它存在右孩子，则右孩子的编号为_。15按照二叉树的递归定义，对二叉树遍历的常用算法有_、_、 _三种。16结构中的数据元素存在多对多的关系称为_结构。17把数据存储到计算机中,并具体体现数据之间的逻辑结构称为_结构。18结构中的数据元素存在一对多的关系称为_结构。19如图 3 所示的二叉树，其后序遍历序列为。图 3 20如图 4 所示的二叉树，其前序遍历序列为_ _。e f g i b a c h d g a b d e c 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 12 页5 / 12 图 4 21二叉树为二叉排序的充分
14、必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法是_的。 (回答正确或不正确) 22在队列的顺序存储结构中，当插入一个新的队列元素时，指针的值增1，当删除一个元素队列时，指针的值增1。23根据搜索方法的不同，图的遍历有_、 _两种方法24循环队列的引入，目的是为了克服。三、综合题 1（ 1）已知某二叉树的后序遍历序列是debca，中序遍历序列是dbeac，试画出该二叉树（ 2）若上述二叉树的各个结点的字符分别代表不同的整数（其中没有相等的），并恰好使该树成为一棵二叉排序树，试给出a、b、c、d、e的大小关系（ 3）给出该树的前序遍历序列2（ 1）设 head1和 p1分别
15、是不带头结点的单向链表A 的头指针和尾指针，head2和 p2分别是不带头结点的单向链表B 的头指针和尾指针，若要把B 链表接到A 链表之后，得到一个以head1为头指针的单向循环链表，写出其中两个关键的赋值语句（不用完整程序，结点的链域为next）。（2）单向链表的链域为next，设指针p 指向单向链表中的某个结点，指针s 指向一个要插入链表的新结点，现要把s 所指结点插入p所指结点之后，某学生采用以下语句： p-next=s 。 s-next=p-next 。这样做正确吗？若正确则回答正确，若不正确则说明应如何改写精选学习资料 - - - - - - - - - 名师归纳总结 - - -
16、- - - -第 5 页，共 12 页6 / 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）写出对上述堆对应的完全二叉树进行中序遍历得到的序列精选学习资料
17、 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 12 页7 / 12 6（ 1）利用筛选法，把序列37 ， 77， 62， 97， 11， 27， 52， 47 建成堆（小根堆），画出相应的完全二叉树（2）写出对上述堆所对应的二叉树进行前序遍历得到的序列四、程序填空题1以下函数在a0到an-1 中，用折半查找算法查找关键字等于k的记录，查找成功返回该记录的下标，失败时返回-1，完成程序中的空格typedef struct int key 。NODE 。int Binary_Search(NODEa,int n, int k) int low,mid
18、,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以下函数为直接选择排序算法，对a1,a2, an中的记录进行直接选择排序，完成程序中的空格typedef struct int key 。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 12 页8 / 12 NODE 。void selsort(NODE a,int n) int
19、i,j,k 。NODE temp 。for(i=1 。i= _(1)_ 。i+) k=i 。for(j=i+1 。j= _(2)_ 。j+) if(aj.keydata=x。p-next=NULL。_(2)_。 rear=_(3)_。 4以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为left 和 right ，数据域 data为字符型， BT 指向根结点）。void Inorder (struct BTreeNode *BT) if(BT!=NULL) （1）。（2）。（3）。精选学习资料 - - - - - - - - - 名师归纳总结 - - -
20、- - - -第 8 页，共 12 页9 / 12 a b c e d 答案一、单项选择题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 25B 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行号；列号；非零
21、元1311 1413 15先序；中序；后序16图状17物理（存储）18树形19gdbeihfca 20 abdefcg 21错误22尾头23深度优先广度优先24假上溢三、综合应用题1（ 1）精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 12 页10 / 12 40 28 72 3 100 54 6 42 82 67 52 57 32 16 102 16 42 32 52 57 67 82 5 2 8 4 9 6 3 10 7 1 （2）dbeanext= head2；p2-next= head1；（2）不对， s-next=p-nex
22、t ；p-next=s；3（ 1）（2）ASL= （1x1+2x2+3x3+4 ）/7=18/7 4（ 1）（2）ASL= （1x1+2x2+3x4+4x3 ）/10=29/10 5（1）精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 12 页11 / 12 102 37 77 62 47 52 27 11 97 11 37 27 47 52 62 77 97（2）102，52，42，82，16，67，32， 57 6（ 1）（2） 11，37，47，97，77，27，62， 52 四、程序填空题1（ 1） low=high （2）mid （3）amid.keynext=p （3）p 初始树堆初始树堆精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 12 页12 / 12 4（1） Inorder(BT-left) （2）printf(“%c ”,BT-data) （3） Inorder(BT-right) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 12 页