国家开放大学2020年（202001-202007）《1252数据结构（本）》期末考试真题及答案完整版（共2套）

试卷代号：1252座位号□□国家开放大学2019年秋季学期期末统一考试数据结构（本）试题2020年1月一、单项选择题(每小题3分，共30分)1．以下说法不正确的是()。A．线性表的链式存储结构不必占用连续的存储空间B．一种逻辑结构只能有唯一的存储结构C.一种逻辑结构可以有不同的存储结构D．线性表的顺序存储结构必须占用连续的存储空间2．单向链表所具备的特点之一是()。A．可以随机访问表中任一结点B．需要占用连续的存储空间C．插入元素和删除元素的操作不需要移动元素D．可以通过指向某元素的指针操作，直接访问到该结点的直接前驱结点3．线性结构中数据元素的位置之间存在()的关系。A．多对多B．一对多C．一对一D．每一个元素都有一个直接前驱和一个直接后继4．在一个单向链表中，p和q分别是指向结点类型的指针，要删除p所指结点的直接后继结点，可执行()。A.q=p->next;p->next=q->nextB．q=p;p=q->nextC.q-p->next;p->next=qD．q-p；p->next=q5．设有带头结点的且头指针为head的非空的单向链表，指针p指向其尾结点，要使该单向链表成为不蒂头结点的单向循环链表，则可利用下述语句：head=head->next;和()。A．p-headB.p=NULLC.p->next=headnhead=p6．元素20，14·160，180按顺序依次进栈，则该栈的不可能输出序列是()。（进栈出栈可以交替进行）。A.180,160,14,20 B.20,14,160,180C.180,160,20,14 D.14,20,180,1607．设有一个15阶的对称矩阵A(第一个元素为a1，1)，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a5，3在一维数组B中的下标是()。A．11 B．13C．14 D．128．设一棵有n个叶结点的二叉树，度数为1的结点有4个，则该树共有()个结点。A．2n B．2n+3C．2n+2 D．2n+49．设根结点所在层为第一层，一棵具有5层的完全二叉树，最后一层有6个结点，则该树总共有()个结点。A．22 B．20C.21 D.1010．已知如图l所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为()。图1A．abecdfg B．acfebdgC．aebcfdg D．aedfcbg二、填空题（每小题2分，共24分）11．把数据存储到计算机中，并具体体现数据元素间的逻辑关系称为____结构。12．设有一个长度为22的顺序表，要删除第8个元素需移动元素的个数为____。13．在一棵二叉树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为____。14．设一棵哈夫曼树共有18个非叶结点，则该树总共有____个结点。15．栈元素的进、出栈次序是：后进一。16．在对10个记录的序列(8，36，19，78，4，10，53，45，27，68)进行直接插入排序时，当把第6个记录10插入到有序表时，为寻找插入位置，元素间需比较____次。17．n个元素进行冒泡法排序，通常需要进行n-l趟冒泡，其中第j趟冒泡共需要进行次元素间的比较。18．序列7，1，4，2，5，3，8，6用归并法排序（升序），经一次归并后的结果序列是。19．中序遍历一棵____树可得到一个有序序列。20．广义表(h，(b，a)．f，e，（（i，j)，k））的深度是____。21．____结构中，数据元素间存在一对多的关系。22．字符串al="beijing”，a2一“bef”，a3一“beifang”，a4一“befi”最小的是____。三、综合题（每小题中每问6分，共30分）23．设查找表为序号1234567891011序列11162425436171839192123(1)画出对上述查找表进行折半查找所对应的判定树（树中结点用下标表示）。(2)说明不成功查找元素45需要经过多少次比较？(3)求在等概率条件下，成功查找的平均比较次数？24．(1)一组记录的关键字序列为(37，67,43，25，27，32)，给出利用堆排序（堆顶元素是最小元素）的方法建立的初始堆（要求以完全二叉树描述）。(2)对关键字序列(40，73，49，31·33，77)采用快速排序，给出以第一个关键字为分割元素，经过一次划分后的结果。四、程序填空题（每空2分，共16分）25.以下函数在a[0]到a[n-l]中，用折半查找算法查找关键字等于k的记录，查找成功返回该记录的下标，失败时返回-l，完成程序中的空格。typedefstruct{intkey,……｝NODE;intBinary_Search(NODEa[],intn,intk){intlow,mid,high;low=0：(l)while(_low<=high){Mid=(2)if(a[mid].key==k)return(3)elseif(a[mid].key<k)low=mid+l;else(4)｝(5)｝26.以下程序是先序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为left和right，数据域data为字符型，BT指向根结点）。voidPreorder(structBTreeNode*BT){if(BT!=NULL)((l)(2)Preorder(BT->right);)}利用上述程序对下图进行遍历，结果是(3)；图2试卷代号：1252国家开放大学2020年春季学期期末统一考试数据结构（本）试题2020年7月一.单项选择题（每小题3分，共30分）1.设主串为“DBcCDABcdEFdBc”，以下模式串能与主串成功匹配的是（）。 A.dBc B.BCd C.DBC D.Abc2.顺序表所具备的特点之一是（）。 A.可以随机访问任一结点 B.不用占用连续的存储空间 C.插入删除操作不需要移动元素 D.必须要有头指针3.在一个链队中，假设f和r分别为队头和队尾指针，p指向一个已生成的结点，现要为该结点的数据域赋值e，并使结点入队的运算为p->data=e;p->next一NULL;和（）。 A.f->next=p;f=p B.r->next=p;r=p C.p->next=r;r=p D.p->next=f;f=p4.在一个头指针为head的带头结点的单向循环链表中，p指向尾结点，要使该链表成为不带头结点的单向链表，可执行（）。 A.head=head->next;p=NULL B.head—head->next;P->next=head C.head->next=p->next D.head-head->next;p->next=NULL5。元素212，214，216，218按顺序依次进栈，则该栈的不可能输出序列是（）（进栈出栈可以交替进行）。 A.212,214,216,218 B.216,214,212,218 C.214,212,218,216 D.218,216,212,2146.设有一个25阶的对称矩阵A(第一个元素为ai，，，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中(数组下标从1开始)，则矩阵中元素a4，s在一维数组B中的下标是（）。 A.10 B.9 C.7 D.87.在一棵二叉树中，编号为19的结点的双亲结点的顺序编号为（）。 A.9 B.8 C.34 D.358.线性表以（）方式存储，能进行折半查找。 A.关键字有序的 B.顺序 C.链接 D.关键字有序的顺序9.如图1所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。 A.abecdfg B.aecbdfg C.aebcfdg D.aedfcbg10.设一棵哈夫曼树共有31个结点，则该树共有（）个非叶子结点。 A.14 B.15 C.16 D.17二、填空题（每小题2分，共24分）II.____结构中，数据元素的位置之间存在多对多的关系。12.设有一个长度为20的顺序表，要插入一个元素，并作为第6个元素，需移动元素的个数为____。13.数组a经初始化chara[]一“fhglisp”；a[6]中存放的是________。14.序列4，2，15，13，18，16，采用冒泡排序算法，经一趟冒泡后，序列的结果是。15.对19个元素的序列用冒泡排法进行排序，通常第7趟冒泡中，共需要进行次元素间的比较。16.对一组记录(41，25，93，20，12，78，46，51，89)进行直接插入排序（由小到大排序），当把第7个记录46插入有序表，为寻找插入位置需比较____次。17.设有一棵深度为5的完全二叉树，第5层上有4个结点，该树共有一个结点。（根所在结点为第1层）18.设有串pl=”DEADFG”，P2=”DEAFDF”，P3=”DEADFAB”P4=”DEAFE”，四个串中最大的是____。19.一棵有8个叶结点的哈夫曼树，则该树共有__个结点。20.____遍历二叉排序树可得到一个有序序列。21.广义表(g，(a，b，d，c)，d，e，((i，j)，k》的长度是____。22.在一个单向链表中，已知q指向p所指结点的直接前驱结点，现要删除p所指结点，则可以用操作q->next=________。三、综合题（每小题中每问6分，共30分） 23.(1)设有数据集合{50，39，17，83，111，14，65，13，91，102，49}，依次取集合中各数据构造一棵二叉排序树。 (2)-组记录的关键字序列为(6，9，7，4，5，8)，利用堆排序（堆顶元素是最小元素）的方法建立初始堆。（要求用完全二叉树表示） 24.(1)如下为一个长度为10的有序表，给出按折半查找对该表进行查找的判定树。 (2)按折半查找对该表进行查找，求在等概率情况下查找成功的平均比较次数。 (3)以1，2，3，6，7，8作为叶结点的权，构造一棵哈夫曼树。序号12345678910序列28356075798086909599四、程序填空题（每空2分，共16分） 25.设线性表以不带头结点的单向链表存储，链表头指针为head，以下程序的功能是：(1)输出链表中各结点中的数据域data。(2)把该单向链表改为以p作为尾指针的单向循环链表。(链表中结点的指针域为next，数据域为data)。#defineNULL0voidmain（）{NODE*head，*p；p=head；/*p为工作指针*／do{printf(“%d\n”，(1))；(2)；｝while(p->next!=(（3）);printf(“%d\n”p->data);（（4））｝ 26.以下程序是后序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为left和right，数据域data为字符型，BT指向根结点）。完成程序中空格部分。voidpostorder(structBTreeNode*BT){if((1))｛postorder(BT->left)；(2)(3)｝利用上述程序对下图所示二叉树遍历的结果为(4)试卷代号：1252国家开放大学2019年秋季学期期末统一考试数据结构（本）试题答案及评分标准（供参考）2020年1月一、单项选择题（每小题3分，共30分）1．B2．C3．C4．A5．C6．C7．B8．B9．C10．D二、填空题（每小题2分，共24分）11．存储（物理）12.1413.2i+114.3715．先出16.417．n-j18.1,7,2.4,3,5.6,819．二叉排序树20.321．树形22．a2三、综合题（每小题中每问6分，共30分）23．(1)(2)4次(3)平均查找长度=(1+2*2+3*4+4*4)/11=324.(1)25,27,32,67.37.43(2)33，31,40,49,73,77四、程序填空题（每空2分，共16分）25.(1)high=n-1(2)low+high)/2(3)mid(4)high=mid-1(5)ret