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

1 / 12 数据结构（本）期末综合练习二一、单项选择题1从 n 个数中选取最大元素（）。A基本操作是数据元素间的交换 B算法的时间复杂度是O(n) C算法的时间复杂度是O(n2) 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带头结点的单向链表的头指针为head，该链表为空的判定条件是（）的值为真。Ahead= =NULL B head-next=head Chead =head-next D head-next= = NULL 5设顺序存储的线性表长度为n，要删除第i 个元素，按课本的算法，当i=（）时，移动元素的次数为3 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 Dadbc 8一个栈的进栈序列是5，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 。 Bfront-next =p 。Cfront=p 。 Dfront-next=p-next 。10栈和队列的相同点是（）。A都是后进先出 B都是后进后出C逻辑结构与线性表不同D逻辑结构与线性表相同，都是操作规则受到限制的线性表11在 C 语言中，存储字符串“ABCD ”需要占用（）字节。A4 B2 C5 D3 12在 C 语言中，利用数组a存放字符串“Hello”，以下语句中正确的是（）。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 12 页2 / 12 a b e c d f g Achar a10= “Hello ”。 Bchar a10。 a=“Hello”。Cchar a10= Hello 。 D char a10= H , e , l , l , o 。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 层上有（）个结点 (根所在结点为第一层 )。A3 B8 C5 D6 16一棵完全二叉树共有30 个结点，则该树一共有（）层 (根结点所在层为第一层)。A6 B4 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对二叉排序树进行（）遍历，遍历所得到的序列是有序序列。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 的线性表进行顺序查找，在等概率情况下，平均查找长度为（）。An B（ n+1）/2 C2n D n-125如图，若从顶点a 出发按广度优先搜索法进行遍历，则可能得到的顶点序列为（）。Aacebdgf Bacfedgb精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 12 页3 / 12 a b e c d f g Cabecdgf Dabecfdg26如图若从顶点a 出发按深度优先搜索法进行遍历，则可能得到的顶点序列为（）。 Aacfgedb Baedcbgf Cacfebdg Daecbdgf 27一棵哈夫曼树有10 个非叶子结点（非终端结点），该树总共有（）个结点。A21 B20C22D19 28一棵哈夫曼树有12 个叶子结点（终端结点），该树总共有（）个结点。A21 B22 C23 D24 29队列的插入操作在（）进行。A队头 B队尾 C队头或队尾 D在任意指定位置30队列的删除操作在（）进行。 A队尾 B队头 C队头或队尾 D在任意指定位置二、填空题1通常可以把某城市中各公交站点间的线路图抽象成_结构。2结构中的元素之间存在多对多的关系称为_结构。3要在一个单向链表中删除p 所指向的结点，已知q 指向p 所指结点的直接前驱结点，若链表中结点的指针域为next，则可执行 _。4设有一个单向循环链表，结点的指针域为next，头指针为head，指针p 指向表中某结点，若逻辑表达式_的结果为真，则p所指结点为尾结点。5设有一个链栈，栈顶指针为hs，现有一个s 所指向的结点要入栈，则可执行操作_和 hs=s；6设有一个链栈，栈顶指针为hs，现有一个s所指向的结点要入栈，则可执行操作s-next=hs。_。7在一个不带头结点的非空链队中，f 和 r 分别为队头和队尾指针，队结点的数据域为data，指针域为next，若要进行出队操作，并用变量x 存放出队元素的数据值，则相关操作为 _。 _。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 12 页4 / 12 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设线性表为（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 页8 / 12 （4）。 while( （5） )。 3以下函数在head为头指针的具有头结点的单向链表中删除第i 个结点，struct node int data 。struct node *next 。typedefstruct node NODE int delete(NODE *head,int i) NODE *p,*q 。 int j 。q=head。j=0。 while(q!=NULL)&(_(1)_) _(2)_。j+。 if(q=NULL) return(0)。 p=_(3)_。_(4)_=p-next 。 free(_(5)_)。 return(1)。 4以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为left 和 right，数据域data为字符型， BT 指向根结点）。void Inorder (struct BTreeNode *BT) if(BT!=NULL) （ 1）。（ 2）。（ 3）。 答案一、单项选择题（每小题2分，共 30 分）精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 12 页9 / 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 21 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 35 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* ）malloc(sizeof(NODE) 。s-data=1。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 12 页10 / 12 42 82 67 52 57 32 16 102 16 42 32 52 57 67 82 102 50 38 82 13 110 64 16 22 12 13019 150 25 15 20010010 （2）p-next=s。s-next= NULL ；free(s) （3）head =head -next；（4）p1-next= p-next ；p-next=p1；3（ 1）（2） 102，52，42，82，16， 67，32，57 4（ 1）（2）4 次； 3 次5（ 1）初始树堆精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 12 页11 / 12 （2）三次；四次6(1) (2)中序遍历中序 2，3，4，5，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）Inorder(BT-left) 2 4 6 16 7 3 18 5 14 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 12 页12 / 12 （2）printf(“%c ” ,BT-data) （3） Inorder(BT-right) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 12 页