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；B p=*NODEmallocsizeofNODE；Cp=NODE mallocsizeofp；D p=NODE *mallocsizeofNODE；5. 以下表中可以随机拜访的是（）；A单向链表B次序表C单向循环链表 D双向链表6. 设次序储备的线性长度为n，要在第 i 个元素之前插入一个新元素，按课本的算法当i= （）时，移动元素次数为2A n/2B nC n-1C 17 . 设次序储备的线性表长度为n，对于删除操作，设删除位置是等概率的，就删除一个元素平均移动元素的次数为（）；A n+1/2B nC 2nD n-i8. 一个栈的进栈序列是1，2， 3， 4，就栈的不行能的出栈序列是（）（进出栈操作可以交替进行）A 3， 2， 4， 1B 3，2， 1， 4 C4， 3， 2，1D 1，4， 2， 39. 设 top 是一个链栈的栈顶指针，栈中每个结点由一个数据域data 和指针域 next 组成，设用 x 接收栈顶元素，就出栈操作为（）；A top=top->next ；x=top->data ；B x=top->data ；top=top->next ；Cx=top-> next ；top=top-> data ；D top->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；D rear=p；rear->next=p ；11. 以下说法正确选项（）；A 队列是后进先出B栈的特点是后进后出欢迎下载精品学习资源C栈的删除和插入操作都只能在栈顶进行 D 队列的删除和插入操作都只能在队头进行12. 以下说法不正确选项（）；A次序栈中，栈满时再进行进栈操作称为“上溢” B次序栈中，栈空时再作出栈栈操作称为“下溢” C次序队列中，队列的头指针和尾指针均超越队列储备空间的上界，就队列已空D次序队列中，当尾指针已经超越队列储备空间的上界，就肯定是队列已满13. 串函数 StrCmp “abA”,”aba”的值为（）；A. 1B 0C“ abAaba”D -114. 设有一个 20 阶的对称矩阵 A ，采纳压缩储备方式，将其下三角部分以行序为主序储备到一维数组中（矩阵A 的第一个元素为a11，数组 b 的下标从1 开头），就矩阵元素 a8,5 在一维数组 b 中的下标是（）；A 30B 28C 40D 3315. 设有一个 12 阶的对称矩阵A ，采纳压缩储备方式将其下三角部分以行序为主序存储到一维数组 b 中（矩阵 A 的第一个元素为 a1,1，数组 b 的下标从 1 开头），就矩阵 A 中第4 行的元素在数组 b 中的下标 i 肯定有（）；A 7i 10B 11 i 15C 9 i 14D 6 i 916. 深度为 5 的完全二叉树第 5 层上有 4 个结点，该树一共有（）个结点；A 28B 30C 31D 1917. 已知一个图的边数为m，就该图的全部顶点的度数之和为（）；A. 2mB mC 2m+1D m/2 18已知一个图的全部顶点的度数之和为m，就 m 肯定不行能是（）；A 4B 8C 12D 9 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 jB j-1C n-jD n-j-1 23排序过程中，每一趟从无序子表中将一个待排序的记录按其关键字的大小放置到已经排好序的子序列的适当位置，直到全部排好序为止，该排序算法是 ；A直接插入排序B 快速排序欢迎下载精品学习资源C冒泡排序D 挑选排序24. 在排序过程中，可以有效地削减一趟排序过程中元素间的比较次数的算法是（ ）；A冒泡B 挑选C折半插入 D 直接插入25. 采纳次序查找法对长度为n 的线性表进行查找（不采纳表尾设监视哨的方法），最坏的情形下要进行（）次元素间的比较；A n+2B nC n-1D n/226 如图如从顶点a 动身按深度优先搜寻法进行遍历，就可能得到的顶点序列为欢迎下载精品学习资源（）；A. aebcfdB. abedcfC. acebdf D acfbdeabecdf欢迎下载精品学习资源图 1欢迎下载精品学习资源（）；27 如图如从顶点a 动身按广度优先搜寻法进行遍历，就可能得到的顶点序列为A. acebdfgh欢迎下载精品学习资源B. aebcghdfC. aedfbcghD. abecdfghabec欢迎下载精品学习资源dfgh图 228. 一棵哈夫曼树有n 个叶子结点（终端结点），该树总共有（）个结点；A 2n-2B 2n-1C 2nD 2n+229. 一棵哈夫曼树总共有23 个结点，该树共有（）个叶结点（终端结点）A 10B 11C 12D 1330. 数据的（）结构与所使用的运算机无关；A规律B物理C 储备D规律与储备二、填空题1. 通常数据的规律结构包括 、 四种类型；2. 通常可以把一本含有不同章节的书的目录结构抽象成 结构；3. 设有一个单向链表，结点的指针域为next，头指针为 head， p 指向尾结点，为了使该单向链表改为单向循环链表，可用语句 ；欢迎下载精品学习资源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 所示的二叉树，其后序遍历序列为；abcdefhg图 3i20. 如图 4 所示的二叉树，其前序遍历序列为 ；abc4 / 12dge欢迎下载精品学习资源图 421. 二叉树为二叉排序的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值；这种说法是 的；回答正确或不正确 22. 在队列的次序储备结构中，当插入一个新的队列元素时，指针的值增1，当删除一个元素队列时，指针的值增1；23. 依据搜寻方法的不同，图的遍历有 、两种方法24. 循环队列的引入，目的是为了克服；三、综合题1（ 1）已知某二叉树的后序遍历序列是debca，中序遍历序列是dbeac，试画出该二叉树（ 2）如上述二叉树的各个结点的字符分别代表不同的整数（其中没有相等的），并恰好使该树成为一棵二叉排序树，试给出a、b、c、d、e 的大小关系（ 3）给出该树的前序遍历序列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 ；这样做正确吗？如正确就回答正确，如不正确就说明应如何改写欢迎下载精品学习资源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 （ 1 ）利用挑选法，把序列37 ， 77， 62， 97， 11， 27， 52， 47 建成堆（小根堆），画出相应的完全二叉树（ 2）写出对上述堆所对应的二叉树进行前序遍历得到的序列四、程序填空题1. 以下函数在 a0 到an-1 中，用折半查找算法查找关键字等于k的记录，查找胜利返回该记录的下标，失败时返回-1，完成程序中的空格typedefstructint key ；NODE ；int Binary_SearchNODEa,int n, int kint 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；2. 以下函数为直接挑选排序算法，对a1,a2, an中的记录进行直接挑选排序，完成程序中的空格typedefstructint key ；欢迎下载精品学习资源NODE ；void selsortNODE a,int nint i,j,k ；NODE temp ；fori=1 ；i<=1；i+k=i ；forj=i+1 ；j<=2；j+ ifaj.key<ak.key3；欢迎下载精品学习资源 4； 5；ifi.=ktemp=ai ；欢迎下载精品学习资源3. 以下函数为链队列的入队操作，x 为要入队的结点的数据域的值，front 、rear 分别是链队列的队头、队尾指针struct nodeElemType data ；struct node *next ； ；struct node *front ， *rear ；void InQueueElemType x欢迎下载精品学习资源struct node *p；p= struct node*p->data=x；p->next=NULL ； 2； 1；欢迎下载精品学习资源rear= 3；欢迎下载精品学习资源4. 以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为left 和 right ，数据域 data 为字符型， BT 指向根结点）；void Inorder struct BTreeNode *BTifBT.=NULL（ 2）（ 3）；（ 1）；欢迎下载精品学习资源答案一、单项挑选题1 D2 A 3 B4 D 5 B6 C 7 A 8 D 9 B10 A11 C12 D 13 D14 D 15 A 16 D 17 A 18 D19 D20 C21 A22 C23 A 24 C 25 B 26 B 27 D 28 B29 C 30 A二、填空题1. 集合；线性；树形；图状2. 树形3. p->next=head ；4. s->next= p->next ；5. p->next=head ；6. hs=hs->next；7. r->next=s8. f=f->next ；9. r= =f10 4；211 1； 2 12行号；列号；非零元13 1114 13 15先序；中序；后序16图状 17物理（储备） 18树形19. gdbeihfca20. abdefcg 21错误22尾 头23. 深度优先广度优先24. 假上溢三、综合应用题abcde1（ 1）9 / 12欢迎下载精品学习资源（ 2）d<b<e<a<c（ 3）abdec2（ 1）p1->next= head2； p2 ->next= head1；（ 2）不对， s->next=p->next ； p->next=s ；3（ 1）402872欢迎下载精品学习资源654100欢迎下载精品学习资源3（ 2）ASL= （ 1x1+2x2+3x3+4 ） /7=18/74（ 1）52813694710（ 2） ASL= （ 1x1+2x2+3x4+4x3 ） /10=29/105欢迎下载精品学习资源（ 1）428267164232欢迎下载精品学习资源欢迎下载精品学习资源10216325710 / 1252826757欢迎下载精品学习资源52欢迎下载精品学习资源102初始树堆（ 2） 102， 52，42， 82，16， 67，32， 57欢迎下载精品学习资源6（ 1）377762113727欢迎下载精品学习资源欢迎下载精品学习资源9711275247776252欢迎下载精品学习资源9747初始树堆（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=temp3（ 1） mallocsizeof struct node（ 2） rear->next=p（ 3） p欢迎下载精品学习资源4（ 1） InorderBT->left（ 2） printf“ %c” ,BT->data（ 3） InorderBT->right欢迎下载