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

《2022年电大数据结构期末综合练习二.docx》由会员分享，可在线阅读，更多相关《2022年电大数据结构期末综合练习二.docx（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品学习资源数据结构（本）期末综合练习二一、单项挑选题1. 从 n 个数中选取最大元素（）；A 基本操作是数据元素间的交换B算法的时间复杂度是On C算法的时间复杂度是On2D 需要进行 n+1 次数据元素间的比较2. 线性表采纳链式储备时，其地址（）；A 肯定是不连续的B必需是连续的 C部分地址必需是连续的D 可以连续也可以不连续3. 设 head 为非空的单向循环链表头指针，p 指向链表的尾结点，就满意规律表达式（）的值为真；A p-next=NULLB p-next= =headCp-next=headD p= =NULL4. 带头结点的单向链表的头指针为head，该链表为空的判定条件是

2、（）的值为真；A head= =NULLB head-next=headC head =head-nextD head-next= = NULL5. 设次序储备的线性表长度为n，要删除第 i 个元素，按课本的算法，当i=（） 时，移动元素的次数为3A 3B n/2C n-3D 36. 设次序储备的线性表长度为n，对于插入操作，设插入位置是等概率的，就插入一个元素平均移动元素的次数为（）；A nB n/2C n-1D n-i+17. 一个栈的进栈序列是a，b， c， d，就栈的不行能的出栈序列是（）；A dcbaBbcadCcbadD adbc8. 一个栈的进栈序列是5， 6， 7， 8，就栈的

3、不行能的出栈序列是（）（进出栈操作可以交替进行）A 7， 6， 8， 5B 5，8， 6， 7C7， 6， 5，8D 8， 7， 6， 5 9设有一个带头结点的链队列，队列中每个结点由一个数据域data 和指针域 next 组成， front 和 rear 分别为链队列的头指针和尾指针，要执行出队操作，用x 储存出队元素的值， p 为指向结点类型的指针，可执行如下操作：p=front-next ； x=p-data；然后指行（）；A front=p-next ；B front-next =p ；C. front=p ；D front-next=p-next ；10栈和队列的相同点是（）；A 都

4、是后进先出B 都是后进后出C规律结构与线性表不同D. 规律结构与线性表相同，都是操作规章受到限制的线性表11在 C 语言中，储备字符串“ ABCD ”需要占用（）字节；A 4B 2C 5D 312. 在 C 语言中，利用数组a 存放字符串“ Hello ”，以下语句中正确选项（）；1 / 12欢迎下载精品学习资源A char a10= “ Hello ”；B char a10 ； a=“ Hello ”；C char a10= Hello ； D char a10= H ,e,l,l ,o ；13. 设有一个10 阶的对称矩阵A ，采纳压缩储备方式将其下三角部分以行序为主序存储到一维数组 b

5、中；（矩阵 A 的第一个元素为 a1,1，数组 b 的下标从 1 开头），就矩阵元素 a5,3 对应一维数组 b 的数组元素是（）；A b18B b8C b13D b1014. 设有一个 15 阶的对称矩阵 A ，采纳压缩储备方式将其下三角部分以行序为主序存储到一维数组 b 中；（矩阵 A 的第一个元素为a1,1，数组 b 的下标从 1 开头），就数组元素 b13 对应 A 的矩阵元素是（）；A a5,3B a6,4C a7,2D a6,815. 深度为 5 的完全二叉树共有20 个结点，就第5 层上有（）个结点 根所在结点为第一层 ；A 3B 8C 5D 616. 一棵完全二叉树共有30 个

6、结点，就该树一共有（）层 根结点所在层为第一层 ；A 6B 4C 3D 517. 已知一个图的全部顶点的度数之和为m，且 m 是以下 4 中情形之一，就 m 只可能是（）；A 9B 7C 15D 8 18以下说法正确选项（）；A 连通图 G 的生成树中不肯定包含G 的全部顶点B连通图 G 的生成树中肯定要包含G 的全部边C连通图 G 肯定存在生成树D连通图 G 的生成树肯定是唯独的19. 线性表只要以（）方式储备就能进行折半查找；A 链接B次序C关键字有序的次序D二叉树20对二叉排序树进行（）遍历，遍历所得到的序列是有序序列； A按层次B前序C中序D后序21. 对 n 个元素进行冒泡排序如某趟

7、冒泡中只进行了（）次元素间的交换，就说明序列已经排好序；A 1B 2C 0 D n-122. 以下排序算法中，在一趟排序过程中，除了其它相关操作外，只进行一次元素间的交换的算法是（）；A. 冒泡B 直接挑选 C直接插入D折半插入23在对一组元素（ 64， 48， 106， 33， 25， 82， 70， 55， 93）进行直接插入排序时， 当进行到要把第7 个元素 70 插入到已经排好序的子表时，为找到插入位置，需进行（）次元素间的比较（指由小到大排序）；A 6B 2C3D 424. 对长度为 n 的线性表进行次序查找，在等概率情形下，平均查找长度为（）；A nB（ n+1） /2 C 2nD

8、 n-125. 如图，如从顶点a 动身按广度优先搜寻法进行遍历，就可能得到的顶点序列为abecdgf（）；A acebdgfB. acfedgb2 / 12欢迎下载精品学习资源C. abecdgf D abecfdg26. 如图如从顶点a 动身按深度优先搜寻法进行遍历，就可能得到的顶点序列为（）；A acfgedb欢迎下载精品学习资源B aedcbgfC acfebdg D aecbdgfabec欢迎下载精品学习资源dgf27. 一棵哈夫曼树有10 个非叶子结点（非终端结点），该树总共有（）个结点；A 21B 20C 22D 1928. 一棵哈夫曼树有12 个叶子结点（终端结点），该树总共有（

9、）个结点；A 21B 22C 23D 2429. 队列的插入操作在（）进行；A 队头B队尾C队头或队尾D 在任意指定位置30. 队列的删除操作在（）进行；A 队尾B队头C队头或队尾D 在任意指定位置二、填空题1. 通常可以把某城市中各公交站点间的线路图抽象成 结构；2. 结构中的元素之间存在多对多的关系称为 结构；3. 要在一个单向链表中删除p 所指向的结点，已知q 指向 p 所指结点的直接前驱结点，如链表中结点的指针域为next，就可执行；4. 设有一个单向循环链表，结点的指针域为next，头指针为 head，指针p 指向表中某结点，如规律表达式 的结果为真，就 p 所指结点为尾结点；5.

10、设有一个链栈，栈顶指针为hs，现有一个 s 所指向的结点要入栈，就可执行操作 和 hs=s；6. 设有一个链栈，栈顶指针为hs，现有一个s所指向的结点要入栈，就可执行操作s-next=hs ；7. 在一个不带头结点的非空链队中，f 和 r 分别为队头和队尾指针，队结点的数据域为data，指针域为next，如要进行出队操作，并用变量x 存放出队元素的数据值，就相关操作为；欢迎下载精品学习资源8. 在一个链队中，f 和 r 分别为队头和队尾指针，队结点的指针域为next ，s 指向一个要入队的结点，就入队操作为 ；9. 次序储备字符串“ ABCD ”需要占用个字节；10. 循环队列的最大储备空间为

11、MaxSize=6 ，采纳少用一个元素空间以有效地判定栈空或栈满，如队头指针front=4 ，当队尾指针rear=时队满，队列中共有个元素；11. 一棵二叉树叶结点（终端结点）数为5，单分支结点数为2，该树共有个结点12. 程序段 char *s= ”aBcD ”；n=0 ； while*s.= 0if*s a&*sdata=x； 2； 3；2设线性表为（ 6， 10， 16， 4），以下程序用说明结构变量的方法建立单向链表，并输出链表中各结点中的数据；#define NULL 0 void main NODE a,b,c,d,*head,*p ；a.data=6；b.data=10；c.da

12、ta=16；d.data=4； /*d 是尾结点 */head=（1）a.next=&b；b.next=&c；c.next=&d；（2）； /* 以上终止建表过程 */p=head； /*p 为工作指针，预备输出链表 */doprintf “%dn”, （3）；四、程序填空题1以下函数为链栈的进栈操作，x 是要进栈的结点的数据域，top 为栈顶指针struct nodeElemType data ；struct node *next ； ；struct node *top ；欢迎下载精品学习资源（4）；while （5）；3. 以下函数在 head 为头指针的具有头结点的单向链表中删除第i 个

13、结点，struct nodeint data ；struct node *next ； ；typedefstruct node NODE int deleteNODE *head,int iNODE *p,*q ；int j ； q=head；j=0 ；whileq.=NULL&1 2；j+ ；ifq=NULLreturn0 ；p=3； 4=p-next ；free5 ；return1 ；4. 以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为left 和 right ，数据域 data 为字符型， BT 指向根结点）；void Inorder struc

14、t BTreeNode *BTifBT.=NULL（ 1）；（ 2）；（ 3）；答案一、单项挑选题（每道题2 分，共 30 分）欢迎下载精品学习资源1 B 2 D 3 B4 D 5 C6 B 7 D 8 B9 D 10 D11 C 12 A 13 C14 A 15 C16 D 17 D 18 C 19 C20 C21 C22 B23 C24 B25 C26A27 A 28 C29 B30 B二、填空题（每题2 分，共 24 分）1. 图状2. 图状3. q-next= p-next ；4. p-next= =head ；5. s-next=hs；6. hs=s；7. x=f-data ； f=

15、f-next ；8. r-next=s ； r=s；9 510 3；511 1112 213 2114 10 15、树形16、深度优先；广度优先17. 线性18. 图状（网状）19. gdbeihfca20 2n-1 21正确22. 次序储备链式储备23. 关键字相等的记录24. 关键字相等的记录三、综合应用题1（ 1） 45 40 65 43 35 9535 40 65 43 35 9535 40 65 43 65 9535 40 43 43 65 9535 40 43 45 65 95（ 2） 40 45 65 43 35 9540 43 45 65 35 9535 40 43 45 65

16、 952（ 1） s=（NODE* ） mallocsizeofNODE ；s-data=1；欢迎下载精品学习资源（ 2） p-next=s；s-next= NULL ；frees（ 3） head =head -next；（ 4） p1 -next= p-next ；p-next=p 1；欢迎下载精品学习资源3（ 1）428267164232欢迎下载精品学习资源欢迎下载精品学习资源10216325752826757欢迎下载精品学习资源52102初始树堆（ 2） 102， 52，42， 82，16， 67，32， 57欢迎下载精品学习资源4（ 1）2212130欢迎下载精品学习资源欢迎下载精品

17、学习资源101525150欢迎下载精品学习资源欢迎下载精品学习资源19100200欢迎下载精品学习资源（ 2） 4 次； 3 次欢迎下载精品学习资源5（ 1）503882欢迎下载精品学习资源欢迎下载精品学习资源1664110欢迎下载精品学习资源10 / 1213欢迎下载精品学习资源（ 2）三次；四次615214461837162 中序遍历中序 2， 3， 4， 5，6， 7， 14，16， 18四、程序填空题1（ 1） sizeof struct node（ 2） p-next=top（ 3） top=p2（ 1） &a（ 2） d next=NULL（ 3） p-data（ 4） p=p-next（ 5） p.=NULL3（ 1） jnext（ 3） q-next（ 4） q-next（ 5） p4（ 1） InorderBT-left欢迎下载精品学习资源（ 2） printf“%c” ,BT-data（ 3） InorderBT-right欢迎下载