国家开放大学数据结构机考（本）复习材料_2023春补充.docx

《国家开放大学数据结构机考（本）复习材料_2023春补充.docx》由会员分享，可在线阅读，更多相关《国家开放大学数据结构机考（本）复习材料_2023春补充.docx（23页珍藏版）》请在课桌文档上搜索。

1、本文件为2023年春季学习新增复习资料。同时之前的复习资料，以及总部教学平台上的直播教学活动也有很强的参考价值，建议各位老师和同学重视起来。祝每位同学都能够取得理想的成绩。判断题：数据元素是对数据操作的基本单位。OA. B. 答案：A判断题：数据项是对数据操作的基本单位。OA. B. 答案：B判断题：数据项是数据的最小单位。OA. B. 答案：A判断题：链接存储表示中数据元素之间的逻辑关系是由指针表示的。OA. B. X答案：A判断题：算法可以用不同的语言描述,如果用C语言或PASCAL语言等高级语言来描述,则算法实际上就是程序了。OA. B. 答案：B判断题：数据结构的抽象操作的定义与具体实

2、现有关。OA.B,答案：B判断题：多维数组实际上是由一维数组实现的。OA. B. X答案：A判断题：数组通常具有的操作是顺序存取。OA. JB. 答案：B判断题：递归算法执行时，每次递归可将原问题的规模缩小。OA. B. 答案：A单选题：对线性表进行二分查找时，要求线性表必须（）。A.以顺序存储方式B.以链接存储方式C.以顺序存储方式，且数据元素有序D.以链接存储方式，且数据元素有序答案：C单选题：有一个长度为10的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（）。A. 29/10B. 31/10C. 26/10答案：A判断题：二分查找是一种最简单的查找方法。OA.

3、 B. X答案：B判断题：散列技术中的冲突指的是两个元素具有相同的序号。OA. B. X答案：B判断题：使用折半查找算法的前提条件是，查找表中记录相应的关键字值必须按升序或降序排列。（）A. B. 答案:A判断题：按18,42,10,86,52,20的顺序构成的二叉排序树，其根结点为18。OA. B. X答案：A判断题：采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为“2。（）A. B. 判断题：假设在有序线性表AL.20上进行折半查找，则比较五次查找成功的结点数为5。()A. B. 答案：A判断题：采用分块查找时，若线性表中共有324个元素，查找每个元素的概率相同，假设采用顺

4、序查找来确定结点所在的块，每块应分12个结点最佳。OA. B. X答案：B判断题：采用顺序查找法对长度为n(n为偶数)的线性表进行查找，采用从前向后的方向查找。在等概率条件下成功查找到前n/2个元素的平均查找长度为(n+2)4OA. B. 答案:A判断题：哈希函数的构造方法中，除留余数法是最好的。OA. B. X答案：B综合题：设查找表为(1,10,11,14,23,27,29,55,68),对上述查找表进行折半查找，为了成功查找到元素14,需要依次与元素()进行比较。A.23,10,1,14B.23,29,27,14C. 23,10,11,14答案：C综合题：设有查找表为(5,14,2,6,

5、18,7,4,16,3),依次取表中数据，构造一棵二叉排序树，对该二叉树进行后序遍历的结果序列为()。A.3,4,2,7,6,16,18,14,5B.2,3,4,5,6,7,14,16,18C.5,2,14,4,6,18,3,7,16D.5,2,4,3,14,6,7,18,16答案：A综合题：序列状态为O时，快速排序达到最好的时间复杂度。A.序列基本有序B.序列逆序C.序列正序D.序列无序答案：D判断题：冒泡排序是一种比较简单的交换排序方法。()A. B. 答案：A判断题：在对一组记录(50,40,95,20,15,70,60,45,80)进行直接插入排序时，当把第7个记录60插入到有序表时，

6、为寻找插入位置需要比较2次。OA. B. 判断题：在堆排序和快速排序中，若原始记录接近正序和反序，则最好选用快速排序。OA. B. X答案：B综合题：一组记录的关键字序列为（36,69,46,28,30,84）,对该序列进行直接选择排序（每次选择最小关键字），第二趟排序后的结果序列为（）。A. 28,69, 46, 36, 30, 84B.28,30,46,36,69,84C.36,46,69,28,30,84D.28,30,36,69,46,84答案：B综合题：一组记录的关键字序列为（46,79,56,38,40,45,62）,利用堆排序（堆顶元素是最小元素）的方法建立的初始堆为（）。A.

7、40,38,45,46,56,79,62B. 38,40,45,79,46,56,62C. 38,79,45,46,40,62,56D. 38,46,45,62,79,40z56答案：B单选题：2.串是什么？（）。A.多个字母的序列B.任意个字母的序列C.有限个字符的序列D.无数个字符的序列单选题：3.下面关于串的叙述中，正确的是（A.串其实是字母序列B.空串是由空格构成的串答案：C）oC.模式匹配是串的一种重要运算D.串只能采用顺序存储答案：C单选题：4.下列是“abcd321ABCD”的子串的选项是（）。A.21ABC”BJabcABCD”C. abcDD. 321a答案：A单选题：5.两

8、个字符串相等的条件是（）。A.串的长度相等B.含有相同的字符集C.都是非空串D.两个串的长度相等且对应位置的字符相同答案：D单选题：6.某串的长度小于一个常数，则采用（B）存储方式最节省空间。A.链式B.顺序C.堆结构D.无法确定答案：B单选题：7.串采用节点大小为1的链表作为其存储结构，是指（）。A.链表的长度为1B.链表中只存放一个字符C,链表中每个节点的数据域中只存放一个字符D.以上都不对正确答案单选题：8.对于一个链串s,查找第一个字符值为X的算法的时间复杂度为()oA. 0(1)B. 0(n)C. o(n2)D.以上都不对答案：B判断题：串中字符的个数称为串的长度()。A. B. 答

9、案:A判断题：两个串的比较实际上是ASQl码的比较。A. B. X答案：A判断题：串中的元素只可能是字母。()A. B. 答案：B判断题：两个字符串比较时，较长的串比较短的串大A. B. 答案：B判断题：若一个强连通图有n个顶点，则该强连通图中至少含有n条有向边。A.判断题：强连通分量是有向图的极大连通子图。A. B. 答案：A单选题：树的（）没有前驱结点，其他结点有且仅有一个直接前驱结点。A.根结点B.分支结点C.终端结点D.叶子结点答案：A单选题:假定一棵二叉树中，叶子结点数为10,单分支结点数为30,则双分支结点数为（）.A.7B.8C.9D.19答案:C单选题:对一棵二叉树中顺序编号为

10、i的结点，若它存在左孩子，则左孩子结点的编号为（）。A. 2iB. 2i+lC. 2i-lD. i/2答案：A单选题：对一棵二叉树顺序编号，若一个结点是双亲结点的左孩子，双亲结点的编号为i,则这个结点的右孩子结点的编号为（）。A. 2iB. 2i+lC. 4iD. 4i+l答案：D单选题：由六个叶子结点a、b、c、d、e、f构造的哈夫曼树（）。A.唯一B.不唯一C.不确定D.以上都不对答案：B单选题：设一棵哈夫曼树有20个叶子结点，该树共有（）个非叶子结点。A. 19B. 20C. 39D. 40答案：A判断题：树是一种重要的非线性数据结构（）。A. B. 答案：A判断题：父亲李贵有两个儿子李

11、万胜和李万利，李万胜又有三个儿子李建新、李建中和李建国，这个家庭可以用树结构来描述（）。A. B. 答案：A判断题：树的所有结点有且只有一个前驱结点（）。A. B. 答案：B判断题：哈夫曼树叶结点数比非叶结点数多1（）。A. B. 答案：A单选题：下面的说法正确的是（）。A.栈的特点是后进先出B.栈的特点是先进先出C.栈的删除操作在栈底进行D.栈的插入操作在栈底进行答案：A单选题：如果以链表作为栈的存储结构，则入栈操作时（）。A,必须判断栈是否满B.判断栈元素类型C.必须判断栈是否空D.对栈不作任何判断答案：A单选题：关于栈和队列的说法中，错误的是（）。A.都是线性表B.基本运算中都不包含排序

12、运算C.只能在端点插入和删除操作D.栈是先进先出，队列是后进先出答案：D单选题：假设链队的队首和队尾指针是F和R,那么队空的条件是（）。A.F=RB. F!=NULLC. R=NULLD. F!=R答案：C判断题：顺序栈永远不会出现栈满的状态OA. B. 答案：B判断题：顺序栈永远不会出现栈空的状态OA. B. 答案：B判断题：链栈永远不会出现栈空的状态OA. B. X答案：B判断题：双向循环链表构建的队列，可以只设立队首指针，也可以只设队尾指针（）A. B. 答案：A假设队列顺序存储结构为:structSeqQueueEIemTypedataMaSize;intfront,rear;）；st

13、ructSeqQueue*sq;请补充下面入队算法（不考虑空间循环使用）。voidInQueuefstructSeqQueue*SqzEIemtType）if（1）Printf（“队列已满n”）；exit；）sq-datasq-rear=x;2）其中，1和2处应该补充的代码是OA. sq-front=Maxsize,sq-rear+;B. sq-rear=Maxsizezsq-rear+;C. sq-front=Masize,sq-front+;D. sq-rear=Masize,sq-front+;答案：B假设队列顺序存储结构为：structSeqQueueEIemTypedataMaSiz

14、e;intfront,rear;）；structSeqQueue*sq;请补充下面出队算法（不考虑空间循环使用）。voidOutQueuefstructSeqQueue*SqzEIemtType）if（1）Printf（“队列己空，不能出队n”）；exit；）2returnsq-datasq-front-l;)其中，1和2处应该补充的代码是OA. sq-front=sq-rear,sq-front+B. sq-rear=sq-front,sq-rear+;C. sq-front=sq-rear,sq-front+D. sq-rear=sq-front,sq-rear+;答案：A假设队列顺序存储

15、结构为：structSeqQueueEIemTypedataMaxSize;intfront,rear;)；structSeqQueue*sq;请补充下面入队算法(数组空间循环使用)。voidInQueuefstructSeqQueue*SqzEIemtTypex)if(1KPrintf(“队列已满n”)；exil);)sq-datasq-rear=x;2)其中，1和2处应该补充的代码是OA. (sq-front+l)%MaSize=sq-reaGsq-rear=(sq-rear+l)%MaSize;B. (sq-rear+l)%MaSize=sq-frontzsq-rear=(sq-rear

16、+l)%MaSize;C. (sq-rear+l)%MaSize=sq-rear,sq-front=(sq-front+l)%MaSize;D. (sq-rear+l)%MaxSize=sq-front,sq-rear=(sq-rear-l)%MaxSize;答案：B单选题：（）有两个指针域，分别指向直接前驱和直接后继，可以实现从前向后和从后向前查找。A.单向链表B.双向链表C.单向循环链表D.双向循环链表答案：D单选题：在一个带头结点的单向链表中，若要在指针q所指结点后插入P指针所指结点，则执行（）。A. p-next=q-next;q-next=p;B. q-next=p-next;p=q

17、;C. p-net=q-next;p-next=q;D. q-next=p-next;p-next=q;答案：A判断题：线性表是一个有限序列，不可以为空。A. B. 答案：B判断题：线性有采取链式存储时，其地址一定是连续的。A. B. 答案：B判断题：对于一个线性表，既要求能够较快地进行插入和删除，又要求存储结构能够反映数据元素之间的逻辑关系，则应采用链式存储方式。A. B. 答案：A判断题：在线性表的顺序存储中，元素之间的逻辑关系是通过物理存储位置决定的；在线性表的链式存储中，元素之间的逻辑关系是通过链域的指针值决定的。A. B. 答案：A判断题：单向循环链表L为空的条件是L-Xiext=L

18、A. B. 答案：A判断题：在单向循环链表中，从链表中任一个结点出发均可以访问到表中其他结点。A. B. 答案：A综合题：头插法建立单链表是指从一个空表开始，读取数组a中的元素，生成新结点，将读取的数据存放到新结点的数据域中,然后将新结点插入到当前链表的表头上,直到结束为止。请完成算法中空缺部分，并分析算法的时间复杂度。采用头插法建表的算法如下：voidCreateListFILinkList*&L,EIemTypeaJntn)(1.inklist*s;inti;1.=(LinkList*)malloc(sizeof(LinkList);创建头结点1.-net=NULL;for(i=0;ida

19、ta=ai;(1);将*s插在原开始结点之前，头结点之后;本算法的时间复杂度为(3)o答案：A. s-net=L-netB. 1.-net=sC. 0(n)综合题：尾插法可以使生成链表中结点的次序和原数组元素的顺序相同，将新结点插到当前链表的表尾上，为此必须增加一个尾指针r,使其始终指向当前链表的尾结点。请完成算法中空缺部分，并分析算法的时间复杂度。采用尾插法建表的算法如下：voidCreateListR(LinkList*&L,EIemTypea,intn)(1.inkList*s,*r;inti;1.=(LinkList*)malloc(sizeof(LinkList);创建头结点1.-n

20、et=NULL;(1);始终指向终端结点，开始时指向头结点for(i=0;idata=ai;(2);将*s插入*r之后r=s;)r-net=NULL;终端结点next域置为NULL)本算法的时间复杂度为(3)o答案：A. r=LB.r-next=sC.0(n)综合题：在单链表L中从头开始找第1个值域与e相等的结点，若存在这样的结点，则返回其逻辑序号，否则返回0。请完成算法中空缺部分，并分析算法的时间复杂度。查找结点的算法如下：intLocateElem(LinkList*LzElemTypee)(1.inkList*p=L-next;intn=l;while(p!=NULL&p-data!=e)(1)；n+;)if(2)return(0);elsereturn(n);)本算法的时间复杂度为(3)。答案：A.p=p-netB. P=NULLC. O(n)