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

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

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

2、为head,该链表为空的判定条件是（）的值为真；Ahead= =NULL B head-next=head Chead =head-next D head-next= = NULL 5设次序储备的线性表长度为3 n,要删除第i 个元素,按课本的算法,当i=（）时,移动元素的次数为A3 Bn/2 C n-3 D 3 6设次序储备的线性表长度为n,对于插入操作,设插入位置是等概率的,就插入一个元素平均移动元素的次数为（）；An Bn/2C n-1Dn-i+1 7一个栈的进栈序列是a,b,c,d,就栈的不行能的出栈序列是（）；Adcba Bbcad Ccbad D adbc 8一个栈的进栈序列是5,

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

4、都是后进后出 A都是后进先出 C规律结构与线性表不同 D规律结构与线性表相同,都是操作规章受到限制的线性表11在 C 语言中,储备字符串“ABCD ” 需要占用（）字节；A4 B2 C5 D3 12在 C 语言中,利用数组a 存放字符串“Hello ” ,以下语句中正确选项（）；1 / 12 名师归纳总结 - - - - - - -第 1 页,共 12 页精选学习资料 - - - - - - - - - Achar a10= “ Hello ” ； Bchar a10； a=“ Hello ” ；Cchar a10= Hello ； D char a10= H , e , l , l , o

5、；13设有一个 10 阶的对称矩阵 A ,采纳压缩储备方式将其下三角部分以行序为主序存储到一维数组 b 中；（矩阵 A 的第一个元素为 a1,1,数组 b 的下标从 1 开头）,就矩阵元素 a5,3对应一维数组 b 的数组元素是（）；Ab18 B b8 C b13 D b10 14设有一个 15 阶的对称矩阵 A,采纳压缩储备方式将其下三角部分以行序为主序存储到一维数组 b 中；（矩阵 A 的第一个元素为 a1,1,数组 b 的下标从 1 开头）,就数组元素 b13 对应 A 的矩阵元素是（）；Aa5,3Ba6,4C a7,2Da6,8 15深度为 5 的完全二叉树共有20 个结点,就第5 层

6、上有（）个结点 根所在结点为第一层 ；A3 B 8 C5 D 6 16一棵完全二叉树共有30 个结点,就该树一共有（）层 根结点所在层为第一层；A6 B 4 C3 D5 17已知一个图的全部顶点的度数之和为m,且 m 是以下 4 中情形之一,就m 只可能是（）；A9 B7 C15 D8 18以下说法正确选项（）；A连通图 G 的生成树中不肯定包含 G 的全部顶点B连通图 G 的生成树中肯定要包含 G 的全部边C连通图 G 肯定存在生成树D连通图 G 的生成树肯定是唯独的19线性表只要以（）方式储备就能进行折半查找；A链接 B次序 C关键字有序的次序 D二叉树20对二叉排序树进行（）遍历,遍历所

7、得到的序列是有序序列；A按层次 B前序 C中序 D后序21对 n 个元素进行冒泡排序如某趟冒泡中只进行了（序列已经排好序；A1 B2 C0 Dn-1 ）次元素间的交换,就说明22以下排序算法中,在一趟排序过程中,除了其它相关操作外,只进行一次元素间 的交换的算法是（）； A冒泡 B直接挑选 C直接插入 D折半插入23在对一组元素（64,48,106,33, 25,82,70,55,93）进行直接插入排序时,当进行到要把第 7 个元素 70 插入到已经排好序的子表时,为找到插入位置,需进行（）次元素间的比较（指由小到大排序）；A6 B2 C3 D 4 24对长度为n 的线性表进行次序查找,在等概

8、率情形下,平均查找长度为（）；An B（ n+1）/2 C2n D n-125如图,如从顶点（）；a 动身按广度优先搜寻法进行遍历,就可能得到的顶点序列为Aacebdgf a Bacfedgb名师归纳总结 2 / 12 b d e g c f 第 2 页,共 12 页- - - - - - -精选学习资料 - - - - - - - - - Cabecdgf Dabecfdg26如图如从顶点 a 动身按深度优先搜寻法进行遍历,就可能得到的顶点序列为（）； Aacfgedb Baedcbgf a g c f ）个结Cacfebdg b e Daecbdgf 27一棵哈夫曼树有d 10 个非叶子结

9、点（非终端结点）,该树总共有（点；A21 B20C22D19 28一棵哈夫曼树有12 个叶子结点（终端结点）,该树总共有（）个结点；A21 B22 C23 D 24 29队列的插入操作在（）进行；A队头 B队尾 C队头或队尾 D 在任意指定位置30队列的删除操作在（）进行； A队尾 B队头 C队头或队尾 D 在任意指定位置二、填空题1通常可以把某城市中各公交站点间的线路图抽象成 _结构；2结构中的元素之间存在多对多的关系称为 _结构；3要在一个单向链表中删除 p 所指向的结点,已知 q 指向 p 所指结点的直接前驱结点,如链表中结点的指针域为next,就可执行 _；4设有一个单向循环链表,结点

10、的指针域为 next,头指针为 head,指针 p 指向表中某结点,如规律表达式 _的结果为真,就 p 所指结点为尾结点；5设有一个链栈,栈顶指针为 hs,现有一个 s 所指向的结点要入栈,就可执行操作_和 hs=s；6设有一个链栈,栈顶指针为hs,现有一个s所指向的结点要入栈,就可执行操作s-next=hs ；_；7在一个不带头结点的非空链队中,f 和 r 分别为队头和队尾指针,队结点的数据域为data,指针域为next,如要进行出队操作,并用变量x 存放出队元素的数据值,就相关操作为 _； _；3 / 12 名师归纳总结 - - - - - - -第 3 页,共 12 页精选学习资料 -

11、- - - - - - - - 8在一个链队中,f 和 r 分别为队头和队尾指针,队结点的指针域为next,s 指向一个要入队的结点,就入队操作为 _；_；9次序储备字符串“ABCD ” 需要占用 _个字节；10循环队列的最大储备空间为MaxSize=6 ,采纳少用一个元素空间以有效地判定栈空或栈满,如队头指针front=4 ,当队尾指针rear= _时队满,队列中共有_个元素；11一棵二叉树叶结点（终端结点）数为5,单分支结点数为2,该树共有 _个结点12程序段 char *s= ”aBcD ” ；n=0；while*s.= 0 if*s a &*sdata=x；_2_；_3_； 2设线性表

12、为（6,10,16, 4）,以下程序用说明结构变量的方法建立单向链表,并输出链表中各结点中的数据；#define NULL 0 void main NODE a,b,c,d,*head,*p；a.data=6；b.data=10；c.data=16；d.data=4； /*d 是尾结点 */ ；head= （1）a.next=&b；b.next=&c；c.next=&d；（2）； /* 以上终止建表过程 */ p=head； /*p 为工作指针,预备输出链表 */ do printf “%dn”, （3）；7 / 12 名师归纳总结 - - - - - - -第 7 页,共 12 页精选学习资

13、料 - - - - - - - - - （4）； while （5） ； 3以下函数在head为头指针的具有头结点的单向链表中删除第i 个结点,struct node int data ；struct node *next ； ；typedefstruct node NODE int deleteNODE *head,int i NODE *p,*q ； int j ；q=head；j=0； whileq.=NULL&_1_ _2_；j+； ifq=NULL return0 ； p=_3_ ；_4_=p-next ； free_5_ ； return1 ； 4以下程序是中序遍历二叉树的递归算法

14、的程序,完成程序中空格部分（树结构中 左、右指针域分别为 left 和 right ,数据域 data为字符型, BT 指向根结点）；void Inorder struct BTreeNode *BT ifBT.=NULL （ 1）；（ 2）；（ 3）； 答案 一、单项挑选题（每道题 2 分,共 30 分）8 / 12 名师归纳总结 - - - - - - -第 8 页,共 12 页精选学习资料 - - - - - - - - - 1B 2 D 3 B4D 5 C6B 7 D 8 B9 D 10 D 11C 12 A 13 C 14 A 15 C 16 D 17 D 18C 19 C20C 2

15、1 C 22 B23C 24 B 25 C26A27A 28 C 29 B 30 B 二、填空题（每题 2 分,共 24 分）1图状 2图状 3q-next= p-next ；4p-next= =head ；5s-next=hs；6hs=s；7x=f-data ； f=f-next ；8r-next=s ；r=s；95 103；5 1111 122 1321 1410 15、树形 16、深度优先；广度优先 17线性 18图状（网状）19gdbeihfca 20 2n-1 21正确 22次序储备 链式储备23关键字相等的记录 24关键字相等的记录三、综合应用题1（1） 45 40 65 43 3

16、5 95 35 40 65 43 35 95 35 40 65 43 65 95 35 40 43 43 65 95 35 40 43 45 65 95 （2） 40 45 65 43 35 95 40 43 45 65 35 95 35 40 43 45 65 95 2（1）s=（NODE* ）mallocsizeofNODE ；s-data=1；9 / 12 名师归纳总结 - - - - - - -第 9 页,共 12 页精选学习资料 - - - - - - - - - （2）p-next=s；s-next= NULL ；frees （3）head =head -next；（4）p1-ne

17、xt= p-next ；p-next=p 1；3（ 1）82 42 67 42 16 32 52 102 16 32 57 堆102 52 82 67 57 初始树（2） 102,52,42,82,16, 67,32,57 4（ 1）22 10 12 15 25 130150 20019 100（2）4 次； 3 次5（ 1）50 38 82 名师归纳总结 13 16 64 110 10 / 12 第 10 页,共 12 页- - - - - - -精选学习资料 - - - - - - - - - （2）三次；四次61 2 4 5 6 14 18 3 7 16 2中序遍历 中序 2,3,4,5

18、,6, 7,14,16,18 四、程序填空题1（ 1）sizeof struct node （2）p-next=top （3）top=p 2（1）&a （2）d next=NULL （3）p-data （4）p=p-next （5）p.=NULL 3（ 1）jnext （3）q-next （4）q-next （5）p 4（1）InorderBT-left 11 / 12 名师归纳总结 - - - - - - -第 11 页,共 12 页精选学习资料 - - - - - - - - - （2）printf“ %c”,BT-data （3） InorderBT-right 12 / 12 名师归纳总结 - - - - - - -第 12 页,共 12 页