国家开放大学本科末考试数据结构历年试题与参考答案15秋至19秋

国家开放大学(中央广播电视大学)2015年秋季学期“开放本科”期末考试数据结构(本)试题2016年1月一、单项选择题(每小题2分，共30分)1.对稀疏矩阵进行压缩存储，可采用三元组表，一个有10行的稀疏矩阵A共有97个零元素，其相应的三元组表共有3个元素。该矩阵A有()列。A.8C.7B.9D.10答案：102.子串“acd”在主串“abdcacdefac”中的位置是()。A.3C.7B.5D.1答案：53.序列12，16，8，4按顺序依次进栈，按该栈的可能输出序列依次入队列，该队列的不可能输出序列是()。(进栈、出栈可以交替进行)。A.16，12，8，4B.4，8，12，16C.8，4，16，12D.16，12，4，8答案：B.4，8，12，164.在一个不带头结点的链队中，假设f和r分别为队头和队尾指针，对该队列进行出队操作，并把结点的值保存在变量e中，其运算为()。A.e=f->data；r=r->nextB.e=f->data；r->next=rC.e=f->data；f=f->nextD.e=f一>data；f一>next=f答案：C.e=f->data；f=f->next

5.数据的逻辑结构在计算机内存中的表示是()。A.给相关变量分配存储单元C.数据的逻辑结构B.数据的存储结构D.算法的具体体现答案：数据的存储结构6.以下说法正确的是()。A.线性表的链式存储结构必须占用连续的存储空间B.一种逻辑结构可以有不同的存储结构C.一种逻辑结构只能有唯一的存储结构D.线性表的顺序存储结构不必占用连续的存储空间答案：一种逻辑结构可以有不同的存储结构7.在一个单链表中要删除p所指结点的后继结点，可执行q=p一>next；和()。A.p一>next=q->nextB.p=q->nextC.p->next=qD.p->next=q答案：A.p一>next=q->next8.在数据结构和算法中，与所使用的计算机有关的是()。A.数据元数间的抽象关系C.算法的时间复杂度B.数据的存储结构D.数据的逻辑结构答案：数据的存储结构9.以下表中可以随机访问的是()。A.单向链表B.双向链表C.单向循环链表D.顺序表答案：顺序表10.头指针为head的不带头结点的单向链表为空的判定条件是逻辑表达式()为真。A.head==NULLB.head->next==NULLC.head->next=NULLD.head一>next!=NULL答案：head==NULL11.设有一个长度为32的顺序表，要在第5个元素之前插入1个元素(也就是插入元素作为新表的第5个元素)，需移动元素个数为()。A.25C.5B.28D.6答案：2812.设有一个长度为33的顺序表，要删除第10个元素(下标从1开始)需移动元素的个数为()。A.11B.10C.23D.14答案：2313.设有一个28阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中(数组下标从1开始)，则数组中第26号元素对应于矩阵中的元素是()。A.a7，5C.a6，5B.a7，6D.a7，4答案：a7，514.在一个不带头结点的单循环链表中，p、q分别指向表中第一个结点和尾结点，现要删除第一个结点，且p、q仍然分别指向新表中第一个结点和尾结点。可用的语句是p=p一>next；和()。A.p=q->nextB.p->next=qC.q=pD.q一>next=p答案：q一>next=p15.在一棵二叉树中，若编号为16的结点是其双亲结点的左孩子，则他的双亲结点的顺序编号为()。A.7B.8C.32D.33答案：8二、填空题(每小题2分，共24分)16.数据的逻辑结构在计算机中的表示称为（物理存储）结构。17.四类基本结构分别为（集合、线性、树形、图状）结构。18.队列的操作特点是先进（先出）。19.广义表((b，a，c)，c，d，(e，i，j，k))的表尾是（(c，d，(e，i，j，k))）。20.设有一个长度为20的顺序表，第8号元素到第20号元素依次存放的值为8，9，…，20。某人想要在第8号元素前插入1个元素7(也就是插入元素作为新表的第8个元素)，程序中他的做法是用语句for(i=8；i<=20；i++)a[i+1]=a[i]；a[8]=7；即从第8号元素开始，直到第20号元素，每个元素依次向后(右)移动1个位置，然后把7存放在第8号位置。事实上这样做是错误的.其结果是新表中第20号元素的值为（8）。21.设有一棵有38个结点的完全二叉树，该树共有（6）层。(根所在结点为第1层)22.一棵有18个结点的二叉树，其2度结点数的个数为8，则该树共有（1）个1度结点。23.对一组记录(1，3，9，2，12，7，5，4，6)进行直接插人排序(由小到大排序)，当把第6个记录7插人有序表，为寻找插人位置需比较（3）次。24.序列5，3，8，4，7，6，采用冒泡排序算法，经一趟冒泡后，序列的结果是（3，5，4，7，6，8）。(按升序排序)25.广义表(b，a，(c，b)，f，e，((i，j)，k))的长度是（6）。26.一棵有18个叶结点的哈夫曼树，则该树共有（17）个非叶结点。27.对稀疏矩阵进行压缩存储，可采用三元组表，一个8行7列的稀疏矩阵A共有51个零元素，其相应的三元组表共有（5）个元素。

三、问答和综合题(每小题10分，共30分)28.设数据集合a={6，17，10，13，8，15，12，18，14}(1)依次取a中各数据，构造一棵二叉排序树。(2)给出对该二叉树中序遍历的序列。(3)对该二叉树进行查找，成功查找到14要进行多少次元素间的比较?29.设有序表为(2，5，11，12，30，48，58)，元素的序号依次为1，2，3，…7.(1)画出对上述查找表进行折半查找所对应的判定树(树中结点用序号表示)。(2)说明成功查找到元素11需要经过多少次比较?(3)在等概率条件下，给出成功查找的平均查找长度?30.(1)如图1所示，若从顶点a出发，首先经过顶点c按广度优先搜索法进行遍历，给出可能得到的一种顶点序列。(2)如图1所示，给出从顶点h出发，首先经过顶点d和e按深度优先搜索法进行遍历，给出可能得到的一种顶点序列。(3)一组记录的关键字序列为(80，57，41，39，46，47)，利用堆排序的方法的方法建立小根堆(堆顶元素是最小元素)，给出按筛选法建立的的初始堆。

四、程序填空题(每空2分，共16分)31.以下冒泡法程序对存放在a[1]，a[2]，……，a[n]中的序列进行冒泡排序，完成程序中的空格部分，其中n是元素个数，程序按升序排列。voidbsort(NODEal，int){ NODEtemp；inti，j，flag；for(j=1；j<=n一1；①j++{ flag=0；for(i=1；②i<=n一j；i十十)if(a[i].key>a[i+1].key){ flag==1；③temp=a[i]；a[i]=ali+1]；④a[i+1]=temp； }if(flag==0)break； }}程序中flag的功能是⑤判断某一趟排序中是否有元素交换32.以下函数为链栈的出栈操作，出栈结点的数据由x返回structnode{ ElemTypedata；structnode*next；}；ElemTypePop(){ intx；if(top==①NULL){printf("栈下溢错误!\n")；exit(1)； }X=top→data;top=top-next;returnx；}四、程序填空题(每空2分，共16分)31.(10分)(1)(2)(3)(4)(5)32.(6分)(1)(2)(3)国家开放大学(中央广播电视大学)2016年春季学期“开放本科”期末考试数据结构(本)试题2016年7月一、单项选择题(每小题2分，共30分)1.对稀疏矩阵进行压缩存储，可采用三元组表，一个10行8列的稀疏矩阵A共有73个零元素，其相应的三元组表共有()个元素。A.8B.80C.7D.10参考答案：72.字符串()是“abcd321ABCD”的子串。A.“21AB”B.“abcD”C.“aBCD”D.“321a”参考答案：“21AB”3.栈和队列的共同特点是()。A.都是操作受限的线性结构C.都是先进后出B.元素都可以随机进出D.都是先进先出参考答案：都是操作受限的线性结构4.在一个链队中，假设f和r分别为队头和队尾指针，p指向一个新结点，要为结点p所指结点赋值x，并人队的运算为p->data=x；p->next=NULL；().A.f一>next=p；f=p；B.r一>next=p；r=p；C.r=p；p->next=r；D.p->next=f；f=p；参考答案：r一>next=p；r=p；5.数据结构中，与所使用的计算机无关的是数据的()结构。A.逻辑B.存储C.逻辑与存储D.物理参考答案：逻辑6.顺序表所具备的特点之一是()。A.可以随机访问任一结点B.不需要占用连续的存储空间C.插人元素的操作不需要移动元素D.删除元素的操作不需要移动元素参考答案：可以随机访问任一结点7.数据元素是数据的基本单位，它()。A.只能有一个数据项组成B.至少有二个数据项组成C.可以是一个数据项也可以由若干个数据项组成D.至少有一个数据项为指针类型参考答案：可以是一个数据项也可以由若干个数据项组成8.设有头指针为head的非空的单向链表，指针p指向其尾结点，要使该单向链表成为单向循环链表，则可利用下述语句()。A.p=head；B.p=NULL；C.p->next=head；D.head=p；参考答案：p->next=head；9.在线性表的顺序结构中，以下说法正确的是()。A.逻辑上相邻的元素在物理位置上不一定相邻B.数据元素是不能随机访问的C.逻辑上相邻的元素在物理位置上也相邻D.进行数据元素的插人、删除效率较高参考答案：逻辑上相邻的元素在物理位置上也相邻10.对链表，以下叙述中正确的是()。A.不能随机访问任一结点B.结点占用的存储空间是连续的C.插人删除元素的操作一定要要移动结点D.可以通过下标对链表进行直接访问参考答案：不能随机访问任一结点11.设有一个长度为35的顺序表，要在第5个元素之前插入1个元素(也就是插入元素作为新表的第5个元素)，则移动元素个数为()。A.30C.5B.31D.6参考答案：3112.设有一个长度为40的顺序表，要删除第10个元素(下标从1开始)需移动元素的个数为()。A.11B.10C.30D.31参考答案：3013.设有一个25阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中(数组下标从1开始)，则矩阵中元素ar，s在一维数组B中的下标是().A.25B.24C.26D.27参考答案：2614.线性表在存储后，如果相关操作中有要求：利用已知的指向某结点的指针或序号，访问该结点的前驱结点，则采用()的存储方式是不可行的。A.单向链表B.双向链表C.单向循环链表D.顺序表参考答案：单向链表15.在一棵二叉树中，若编号为i的结点存在左孩子，i结点的左孩子的顺序编号为()。A.i/2.0B.2*iC.2*i+1D.i十2参考答案：2*i二、填空题(每小题2分，共24分)16.广义表((b，a，c)，c，d，f，e，((i，j)，k))的长度是____________.参考答案：617.数据结构中，数据元素之间的抽象关系称为____________结构。参考答案：逻辑18.栈的操作特点是后进______________.参考答案：先出19.广义表((b，a，c)，c，d，f，e，((i，j)，k))的表头是________________.参考答案：(b，a，c)20.设有一个长度为18的顺序表，第8号元素到第18号元素依次存放的值为8，9，…，18.某人想要删除第8号元素，程序中他的做法是用语句for(i=18；i<=9；i--)a[i-1]=a[i]；即从第18号元素开始，直到第9号元素，每个元素依次向前(左)移动1个位置，事实上这样做是错误的，其结果新表中第9号元素的值为_________________________.参考答案：1821.一棵二叉树，有1个2度结点，2个1度结点，则该树共有________个结点。参考答案：522.设有一棵深度为5的完全二叉树，该树共有21个结点，第5层上有_____个结点。(根所在结点为第1层)参考答案：623.中序遍历______________树可得到一个有序序列。参考答案：二叉排序树24.序列12，10，13，11，16，14，采用冒泡排序算法，经一趟冒泡后，序列的结果是_____________________.(按升序排序)参考答案：10，12，11，13，14，1625.对16个元素的序列用冒泡排序法进行排序，共需要进行________趟冒泡。参考答案：1526.一棵有16个叶结点的哈夫曼树，则该树共有_________个非叶结点。参考答案：1527.在对一组记录(40，24，82，9，1，78，46，31，69)进行直接插人排序(由小到大排序)，当把第7个记录46插人到有序表时，为寻找插人位置需比较__次。参考答案：3三、问答和综合题(每小题10分，共30分)28.设有序表为(5，8，14，15，33，51，61，73，81，82，93)，元素的序号依次为1，2，3，……，11.(1)画出对上述查找表进行折半查找所对应的判定树(树中结点可用序号表示)(2)说明成功查找到元素33需要经过多少次比较?(3)在等概率条件下，给出成功查找的平均查找长度?参考答案：29.(1)如图1所示，若从顶点a出发，首先经过c按图的深度优先搜索法进行遍历，给出可能得到的一种顶点序列。(2)设有向图如图2所示下，写出首先删除顶点1的1种拓扑序列。参考答案：30.(1)设数据集合a={7，4，9，8，6，5，3}，依次取a中各数据，构造一棵二叉排序树。(2)对该二叉树进行查找，成功查找到5要进行多少次元素间的比较?(3)给出对上述二叉排序树进行中序遍历的序列参考答案：四、程序填空题(每空2分，共16分)31.以下函数在a[0]到a[n-1]中，用折半查找算法查找关键字等于k的记录，查找成功返回该记录的下标，失败时返回一1，完成程序中的空格typedefstruct{ intkey；…}NODE；intBinary_Search(NODEa[]，intn，intk){ intlow，mid，high；low=0；high=n一1；while①_________________{ mid=(low+high)/2；if(a[mid].key==k)return②________________;elseif③____________________low=mid+1；else④________________; } ⑤__________________;}参考答案：(1)low<=high(2)mid(3)a[mid].key<k(4)high=mid一1(5)return-132.以下函数为链栈的进栈操作，x是要进栈的结点的数据域，top为栈顶指针。structnode{ ElemTypedata；structnode*next；}；structnode*top；voidPush(ElemTypex){ structnode*p；p=(structnode*)malloc①______________;p->data=x；②___________________;③___________________;}参考答案：(1)sizeof(structnode)(2)p->next=top(3)top=p国家开放大学(中央广播电视大学)2017年春季学期“开放本科”期末考试数据结构(本)试题2017年6月一、单项选择题(每小题3分，共30分)1.设有一个长度为26的顺序表，要插人一个元素，并使它成为新表的第6个元素，需移动元素的个数为()。A.21B.22C.20D.19参考答案：212.头指针为head的带头结点的单向循环链表，p指向尾结点，要使该链表成为不带头结点的单向循环链表，可执行head=head->next；和()。A.p=head->nextB.head->next=pC.head->next=p->nextD.p->next=head；参考答案：p->next=head；3.元素111，113，115，117按顺序依次进栈，则该栈的不可能输出序列是()(进栈出栈可以交替进行)。A.117，115，113，111B.111，113，115.117C.117，115，111，113D.113，111，117，115参考答案：117，115，111，1134.设有一个20阶的对称矩阵A(第一个元素为a1.1)，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中(数组下标从1开始)，则矩阵元素a6.2在一维数组B中的下标是()。A.21B.17C.28D.23参考答案：17

5.设有串pl=”ABADF”，P2=”ABAFD”，P3=”ABADFA”，P4=”ABAF”，以下四个串中最大的是()。A.p3C.plB.p2D.p4参考答案：p26.在一棵二叉树中，若编号为i的结点存在左孩子，则左孩子的顺序编号为().A.2i+1C.2iB.2i-1D.2i+2参考答案：2i7.如图1所示，若从顶点a出发，按图的广度优先搜索法进行遍历，则可能得到的一种顶点序列为().A.abecdfB.aecbdfC.aebcfdD.aedfcb参考答案：aecbdf8.线性表以()方式存储，能进行折半查找。A.链接B.顺序C.关键字有序的顺序D.二叉树参考答案：关键字有序的顺序9.一棵具有38个结点的完全二叉树，最后一层有()个结点。A.7C.6B.5D.8参考答案：710.下图的拓扑序列是(A.52346B.23645C.56234D.23564参考答案：56234二、填空题(每小题2分，共24分)11.结构中的数据元素存在多对多的关系称为____________结构。参考答案：图状12.n个元素进行冒泡法排序，第j趟冒泡要进行__________次元素间的比较。参考答案：n-j13.中序遍历__________树可得到一个有序序列。参考答案：二叉排序树14.待排序的序列为8，3，4，1，2，5，9，采用直接选择排序算法，当进行了两趟选择后：结果序列为____________________.参考答案：1，2，4，8，3，5，915.广义表((a，b)，d，e，((i，j)，k))的长度是__________.参考答案：416.广义表的(c，a，(a，b)，d，e，((i，j)，k))深度是__________.参考答案：317.对稀疏矩阵进行压缩存储，可采用三元组表，一个有10行10列的稀疏矩阵A共有95个零元素，其相应的三元组表共有__________个元素。参考答案：518.在对一组记录(50，49，97，22，16，73，65，47，88)进行直接插人排序时，当把第7个记录65插人到有序表时，为寻找插人位置需比较__________次。参考答案：319.一棵有5个叶结点的哈夫曼树，该树中总共有________个结点。参考答案：920.设有一棵深度为4的完全二叉树，第四层上有5个结点，该树共有_________个结点。(根所在结点为第1层)。参考答案：1221.设有一个长度为40的顺序表，要删除第8个元素需移动元素的个数为____.参考答案：3222.有以下程序段chara[]="English”；char*p=a；intn=0；while(*p!=‘\0’){n++；p++；)结果中，n的值是________.参考答案：7三、综合题(每小题中每问5分，共30分)23.有一个长度为11的有序表(1，2，11，15，24，28，30，56，69，70，80)，元素的下标依次为1，2，3，……，11，按折半查找对该表进行查找。(1)画出对上述查找表进行折半查找所对应的判定树。(2)说出成功查找到元素56，需要依次经过与哪些元素的比较?(3)说出不成功查找元素72，需要进行元素比较的次数?参考答案：24.(1)一组记录的关键字序列为(57.90，67，50，51，56)，利用堆排序(堆顶元素是最小元素)的方法建立初始堆(要求以完全二叉树描述)。(2)对关键字序列(56.51，71，54，46，106)利用快速排序，以第一个关键字为分割元素，给出经过一次划分后的结果。(3)一组记录的关键字序列为(60，47，80，57，39，41，46，30)，利用归并排序的方法，分别给出(1，1)归并、(2，2)归并、(4，4)归并的结果序列。参考答案：四、程序填空题(每空2分，共16分)25.设线性表为(16，20，26，24)，以不带头结点的单向链表存储，链表头指针为head，以下程序的功能是输出链表中各结点中的数据域data。Structnode{ intdata；structnode*next；}；typedefstructnodeNODE；#defineNULLOvoidmain(){ NODE*head，*p；p=head；/*p为工作指针*/ do{ printf(“%d\n”，(1)_______________)；(2)______________________;}while((3)______________________)}参考答案：(1)p->data(2)p=p->next(3)p!=NULL26.以下函数为直接选择排序算法，对a[1]，a[2]，…a[n]中的记录进行直接选择排序，完成程序中的空格typedefstruct{ intkey;…}NODE；voidselsort(NODEa[]，intn){inti，j，k；NODEtemp；for(i=l；i<=(1)_____________；i十十){ k=i； for(j=i+1；j<=(2)______________；j十十) if(a[j].key<a[k].key)(3)___________________; if(i!=k){ temp=a[i]； (4)__________________________; (5)_____________________________;} }}参考答案：(1)n-1(2)n(3)k=j(4)a[i]=a[k](5)a[k]=temp国家开放大学(中央广播电视大学)2017年秋季学期“开放本科”期末考试数据结构(本)试题2018年1月一、单项选择题(每小题3分，共30分)1.设有头指针为head的带有头结点的非空单向循环链表，指针p指向其尾结点，要删除头结点，并使其仍为单向循环链表，则可利用下述语句head==head一>next；()。A.p=head；B.p=NULL；C.p一>next=head；D.head=p；参考答案：p一>next=head；2.以下说法不正确的是()。A.线性表的链式存储结构不必占用连续的存储空间B.一种逻辑结构只能有唯一的存储结构C.一种逻辑结构可以有不同的存储结构D.线性表的顺序存储结构必须占用连续的存储空间参考答案：一种逻辑结构只能有唯一的存储结构3.把数据存储到计算机中，并具体体现()称为物理结构。A.数据元素间的逻辑关系B.数据的处理方法C.数据的性质D.数据的运算参考答案：数据元素间的逻辑关系4.链表所具备的特点之一是()。A.可以随机访问任一结点B.需要占用连续的存储空间C.插人元素的操作不需要移动元素D.删除元素的操作需要移动元素参考答案：插人元素的操作不需要移动元素5.图状结构中数据元素的位置之间存在()的关系。A.一对一B.多对多C.一对多D.每一个元素都有一个直接前驱和一个直接后继参考答案：多对多6.元素15，9，11，13按顺序依次进栈，则该栈的不可能输出序列是()(进栈出栈可以交替进行)。A.13，11，9，15C.13，11，15，9B.15，9，11，13D.9，15，13，11参考答案：13，11，15，97.设有一个14阶的对称矩阵A(第一个元素为a1，1)，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中(数组下标从1开始)，则矩阵中元素a4.3在一维数组B中的下标是()。A.9B.10C.11D.8参考答案：98.在一棵二叉树中，若编号为8的结点存在右孩子，则右孩子的顺序编号为()。A.18B.16C.15D.17参考答案：179.设一棵哈夫曼树共有14个非叶结点，则该树总共有()个结点。A.29C.30B.27D.28参考答案：29

10.如图1所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为().A.abecdfC.aebcfdB.acfebdD.aedbfc参考答案：aedbfc二、填空题(每小题2分，共24分)11.队列的特点之一是：元素进、出队的次序是：先进_________。参考答案：先出12._________________结构中，数据元素间存在一对多的关系。参考答案：树形13.对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的三项信息是______________。参考答案：行下标、列下标、数组元素14.在对11个记录的序列(12，35，9，7，2，11，56，95，37，58，60)进行直接插入排序时，当把第6个记录11插入到有序表时，为寻找插入位置，元素间需比较____________次。(由小到大排列)参考答案：315.哈希函数是记录关键字的值与该记录____________之间所构造的对应关系。参考答案：存储位置16.20个元素进行冒泡法排序，通常需要进行19趟冒泡，其中第10趟冒泡共需要进行____________次元素间的比较。参考答案：1017.一棵有19个结点的二叉树，采用链式结构存储，该树结构中有__________个指针域为空。参考答案：2018.中序遍历一棵____________树可得到一个有序序列。参考答案：二叉排序树19.二叉排序树插人操作中，新插人的结点总是以树的____________结点被插人的。参考答案：叶20.广义表的(a，(d，a，b)，h，(e，((i，j)，k)))深度是____________。参考答案：421.序列4，2，5，3，8，6，7，9，采用归并排序算法(升序)，经一趟归并后，序列的结果：___________。参考答案：2，4，3，5，6，8，7，922.字符串al=“teijing”，a2=“tef”，a3=“teifang”，a4=“tefi”最小的是_______。参考答案：a2三、综合题(每小题中每问6分，共30分)23.设查找表为(1)画出对上述查找表进行折半查找所对应的判定树(树中结点用下标表示)。(2)说明成功查找到元素86需要经过多少次比较?(3)求在等概率条件下，成功查找的平均比较次数?参考答案：24.(1)一组记录的关键字序列为(26，59，36，18，20，25)，给出利用堆排序(堆顶元素是最小元素)的方法建立的初始堆(要求以完全二叉树描述)。(2)对关键字序列(26，59，36，18，20，64)采用快速排序，给出以第一个关键字为分割元素，经过一次划分后的结果。参考答案：四、程序填空题(每空2分，共16分)25.以下函数在a[0]到a[n-1]中，用折半查找算法查找关键字等于k的记录，查找成功返回该记录的下标，失败时返回一1，完成程序中的空格typedefstruct{ intkey；……}NODE；intBinary_Search(NODEa[]，intn，intk){intlow，mid，high；low=＝0；high=n一1；while((1)_____________){ mid=((2)_______________)if(a[mid].key==k)return(3)___________________; elseif((4)____________________) low=mid+1；else(5)_____________________; } Return-1}参考答案：(1)low<=high(2)(low+high)/2(3)mid；(4)a[mid].key<k(5)high=mid-1；26.以下程序是前序遍历二叉树的递归算法的程序，完成程序中空格部分(树结构中左、右指针域分别为left和right，数据域data为字符型，BT指向根结点)。voidInorder(structBTreeNode*BT){ if(BT!=NULL){ (1)_________________; (2)__________________; Inorder(BT一一>right)；}利用上述程序对图2进行先序遍历，结果是(3)_______________________.参考答案：(1)printf(“%c”，BT一>data)(2)Inorder(BT->left)(3)abdfec国家开放大学(中央广播电视大学)2018年春季学期“开放本科”期末考试数据结构(本)试题2018年7月一、单项选择题(每小题3分，共30分)1.数据的存储结构包括数据元素的表示和()。A.数据处理的方法B.相关算法C.数据元素的类型D.数据元素间的关系的表示参考答案：数据元素间的关系的表示2.在一个头指针为head的单向链表中，p指向尾结点，要使该链表成为单向循环链表可执行()。A.p=head->next；B.head->next=p；C.head一>next=p->next；D.p一>next=head；参考答案：p一>next=head；3.元素111，113，115，117按顺序依次进栈，则该栈的不可能输出序列是()(进栈出栈可以交替进行)。A.117，115，113，111B.111，113，115，117C.117，115，111，113D.113，111，117，115参考答案：117，115，111，1134.以下说法正确的是()。A.栈的特点是先进后出C.队列的特点是先进后出B.栈的特点是先进先出D.栈和队列的特点都是先进后出参考答案：栈的特点是先进后出5.设有一个20阶的对称矩阵A(第一个元素为a1.1)，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中(数组下标从1开始)，则矩阵中元素a6.2在一维数组B中的下标是()。A.24C.16B.17D.23参考答案：176.设一棵有2n+1个结点的二叉树，除叶结点外每个结点度数都为2，则该树共有()个叶结点。A.nB.n+1C.n+2D.n一1参考答案：n+17.已知如图1所示的一个图，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为()。A.abecdfC.aebcfdB.aecbdfD.aedfcb参考答案：aecbdf8.线性表以()方式存储，能进行折半查找。A.关键字有序的顺序C.链接B.顺序D.二叉树参考答案：关键字有序的顺序9.一棵具有38个结点的完全二叉树，最后一层有()个结点。A.7C.6B.5D.8参考答案：7

10.对一个栈顶指针为top的链栈进行出栈操作，用变量e保存栈顶元素的值，则执行()。A.e=top一>next；top->data=e；B.top=top->next；e=top->data；C.e=top一>data；top=top一>next；D.top=top一>next；e=data；参考答案：e=top一>data；top=top一>next；二、填空题(每小题2分，共24分)11.数组a经初始化chara[]="English”；a[7]中存放的是_______。参考答案：字符串结束符12.设有串pl=”ABADF”，P2=”ABAFD”，P3=”ABADFA”P4=”ABAF”，四个串中最大的是______。参考答案：P213.在一棵二叉树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为______。参考答案：2i+114.设有一个长度为20的顺序表，要插入一个元素，并作为第8个元素，需移动元素的个数为______。参考答案：1315.结构中的数据元素存在多对多的关系称为______结构。参考答案：图状16.设有一棵深度为4的完全二叉树，第四层上有5个结点，该树共有______个结点。(根所在结点为第1层)参考答案：1217.一棵二叉树中有n个非叶结点，每一个非叶结点的度数都为2，则该树共有______个叶结点。参考答案：n+118.在对一组记录(55，39，97，22，16，73，65，47，88)进行直接插入排序时，当把第7个记录65插入到有序表时，为寻找插入位置需比较______次。(由小到大排序)参考答案：319.n个元素进行冒泡法排序，第j趟冒泡要进行______次元素间的比较。参考答案：n-j20.一棵有n个叶结点的哈夫曼树，则该树共有______个结点。参考答案：2n-121.中序遍历______可得到一个有序序列。参考答案：二叉排序树22.广义表((a，b)，d，e，((i，j)，k))的长度是______。参考答案：4

三、综合题(每小题中每问6分，共30分)23.(1)设有数据集合{40，29，7，73，101，4，55，2，81，92，39}，依次取集合中各数据构造一棵二叉排序树。(2)一组记录的关键字序列为(5，8，6，3，4，7)，利用堆排序(堆顶元素是最小元素)的方法建立初始堆。(要求用完全二叉树表示)24.(1)以2，3，4，7，8，9作为叶结点的权，构造一棵哈夫曼树。(2)给出上述哈夫曼树叶结点的哈夫曼编码。(3)一组记录的关键字序列为(37，70，47，29，31，85)，利用快速排序，以第一个关键字为分割元素，给出经过一次划分后结果。(从小到大排序)

四、程序填空题(每空2分，共16分)25.设线性表为(6，10，16，4)，以下程序用说明结构变量的方法建立单向链表，并输出链表中各结点中的数据。#defineNULL0voidmain(){ NODEa，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(“%d\n”，(3)____________)；(4)______________________; }while((5)_______________)；}参考答案：(1)&a(2)d->>next=NULL(3)p->data(4)p=p->next(5)p!=NULL26.以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分(树结构中左、右指针域分别为left和right，数据域data为字符型，BT指向根结点)。voidInorder(structBTreeNode*BT){ if(BT!=NULL){(1)_______________;(2)_______________;Inorder(BT->right)；}}利用上述程序对右图进行遍历，结果是(3)________________________参考答案：(1)Inorder(BT->left)(2)printf(“%c”，BT一>data)(3)bedafc国家开放大学(中央广播电视大学)2018年秋季学期“开放本科”期末考试数据结构(本)试题2019年1月一、单项选择题(每小题3分，共30分)1.如下图所示，若从顶点a出发，按图的广度优先搜索法进行遍历，则可能得到的一种顶点序列为()。A.acebdfC.aecbdfB.aecbfdD.acefdb参考答案：aecbdf2.结构中的元素之间存在一对多的关系是()。A.集合B.线性结构C.树形结构D.图状结构参考答案：树形结构3.设有一个长度为18的顺序表，要在第4个元素之前插入1个元素(也就是插入元素作为新表的第4个元素)，则移动元素个数为()。A.15C.5B.16D.4参考答案：154.一个不带头结点的单循环链表，尾指针为rear，在链表中插人一个s所指向的新结点，并作为新的尾结点，可执行()。A.rear一>next=s；s一>next=rear一>next；rear=s；B.rear一>next=s一>next；rear=s；C.s一>next=rear一>next；rear一>next=s一>next；rear=s；D.s一>next=rear一>next；rear一>next=s；rear=s；参考答案：s一>next=rear一>next；rear一>next=s；rear=s；5.元素a，b，c，d按顺序依次进栈，则该栈的不可能输出序列是()(进栈出栈可以交替进行).A.c，b，a，dC.a，c，b，dB.d，c，b，aD.d，c，a，b参考答案：d，c，a，b6.在一个栈顶指针为top的链栈中进行出栈操作，用变量x保存栈顶元素的值，则执行()。A.x=top->data；top=top->next；C.top=top一>next；x=top一>data；B.x=top->data；D.top=top->next；x=data；参考答案：x=top->data；top=top->next；7.设有一个18阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中(数组下标从1开始)，则矩阵中a10.8元素对应于数组中第()号元素。(矩阵中的第1个元素是a1.1)A.51C.52B.53D.54参考答案：538.一棵采用链式存储的二叉树中，共有n个指针域被有效使用(即指针域为非空)。该二叉树有()个指针域为空。A.n+1C.n--1B.nD.n+2参考答案：n+29.在一棵二叉树中，若编号为9的结点存在右孩子，则右孩子的顺序编号为()。A.18C.15B.16D.19参考答案：1910.设一棵哈夫曼树共有15个非叶结点，则该树总共有()个结点。A.29C.31B.27D.28参考答案：31二、填空题(每小题2分，共24分)11.在n个整数中求最大数的算法中，其基本操作是_____________.参考答案：元素间的比较12.设有一个长度为20的顺序表，要删除第5个元素，则最少要移动元素的个数为_____________.参考答案：1513.在双向链表中，要删除p所指的结点，其中所用的一条语句(p->prior)->next=p->next；的功能是：使P所指结点的直接前驱的右指针指向_____________.参考答案：P所指结点的直接后继14.设有一个头指针为head的单向链表，p指向链表中的某结点，若要使该链表成为单向循环链表，可用语句while(p->next!=NULL)_____________.和p一>next=head；。参考答案：p=p->next15.在一个链队中，设front和rear分别为队头和队尾指针，则s所指结点(数据域已赋值)的人队操作为s一>next=NULL；_____________rear=s；。参考答案：rear->next=s；16.字符串al=“heijing”，a2=“hef”，a3=“heifang”，a4=“hefi”中最小的是_______.参考答案：a217.栈的特点之一是：元素进、出栈的次序是：后进_____________.参考答案：先出18.在对10个记录的序列(14，30，10，7，22，13，66，85，47，58)进行直接插人排序时，当把第6个记录13插人到有序表时，为寻找插人位置，元素间需比较_____________次。(由小到大排列)参考答案：419.18个元素进行冒泡法排序，通常需要进行17趟冒泡，其中第10趟冒泡共需要进行_____________次元素间的比较。参考答案：820.一棵有15个结点的哈夫曼树，采用链式结构存储，该树结构中有____________个叶结点。参考答案：821.广义表的(b，(a，b)，d，(c，((e，f)，j)))深度是_____________.参考答案：422.序列4，2，7，9，5，3，8，6采用归并排序算法(升序)，经一趟归并后，序列的结果为_____________.参考答案：2，4，7，9，3，5，6，8三、综合题(每小题6分，共30分)23.(1)已知某二叉树的后序遍历序列是febch，给出该二叉树的根结点?又该二叉树的中序遍历序列是fbehc，分别给出该二叉树的左、右子树的结点?(2)画出上述二叉树?若上述二叉树的各个结点的字符分别代表不同的整数(其中没有相等的)，并恰好使该树成为一棵二叉排序树，试给出h、b、c、f、e的大小关系。

24.设查找表为(1，2，3，4，5，6，7，8，9，10，11)(1)画出对上述查找表进行折半查找所对应的判定树(树中结点用数值表示)。(2)说明成功查找到元素5，9各需要经过多少次元素间的比较?(3)说明查找不到元素4.2，5.5各需要经过多少次元素间的比较?四、程序填空题(每空2分，共16分)25.以下程序是折半插人排序的算法设待排序的记录序列存放在a[1]，…a[n]中，以a[0]作为辅助工作单元，以下程序是要把a[i]插人到已经有序的序列a[1]，…a[i一1]中。voidbinsort(NODEa[]，intn){ intx，i，j，s，k，m；For(i=2；i<=(1)___________；i++){ a0]=a[i]；x=a[i].key；s=1；j=i-1；while(s<=j){ m=(2)_____________; if(x<a[m].key) (3)__________________; else (4)__________________;}for(k=i一1；k>=j+1；k--) (5)______________=a[k]；a[j+1]==a[0]； }}参考答案：(1)n(2)(s+j)/2；(3)j=m一1；(4)s=m+1；(5)a[k+1]26.以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分(树结构中，左、右指针域分别为left和right，数据域data为字符型，BT指向根结点)。voidInorder(structBTreeNode*BT){ aif(BT!=NULL)(1)_____________;(2)_____________;Inorder(BT->right)；}}利用上述程序对右图进行遍历，结果是(3)_____________________;参考答案：(1)Inorder(BT一>left)(2)printf(“%c”，BT->data)(3)bedfa国家开放大学2019年春季学期期末统一考试数据结构(本)试题2019年7月一、单项选择题(每小题3分，共30分)1.以下说法正确的是()。A.在顺序表中可以随机访问任一结点B.一种逻辑结构在存储时只能采用一种存储结构C.对链表进行插入、删除元素的操作一定要移动结点D.在链表中可以随机访问任一结点参考答案：在顺序表中可以随机访问任一结点2.线性表在存储后，如果要求：仅通过已知的指向第i个结点的指针，进行相关操作，访问到该结点的前驱结点，则采用()存储方式是不可行的。A.单链表B.双链表C.单循环链表D.顺序表参考答案：单链表3.栈和队列的共同特点是()。A.都是先进后出B.元素都可以随机进出C.只容许在端点处插人和删除元素D.都是先进先出参考答案：只容许在端点处插人和删除元素4.元素4，6，8，10按顺序依次进栈，按该栈的可能输出序列依次人队列，该队列的可能输出序列是()(进栈出栈可以交替进行)。A.10，8，4，6C.8，4，6，10B.10，6，4，8D.10，8，6，4参考答案：10，8，6，4

5.在一个不带头结点的链队中，假设f和r分别为队头和队尾指针，从该队列中进行出队操作，并把结点的值保存在变量x中的操作为()。A.x=r->data；r=r->next；B.r一r一>next；x=r一>data；C.x=f~>data；f=f->next；D.f一f->next；x-f一>data；参考答案：x=f~>data；f=f->next；6.设有一个18阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存到一维数组B中(数组下标从1开始)，则矩阵元素ag.2对应于数组B中第()号元素。(矩阵中的第1个元素是a1.1)A.42B.39C.38D.40参考答案：387.一棵采用链式存储的二叉树中，共有n一1个指针域被有效使用(即指针域为非空)。该二叉树中有()个指针域为空。A.n+1B.nC.n-1D.n一2参考答案：n+18.设一棵哈夫曼树共有n个非叶结点，则该树共有()个结点。A.2nB.2n+1C.2n一1D.2n+2参考答案：2n+1

9.如图所示，若从顶点a出发，按图的广度优先搜索法进行遍历，则可能得到的一种顶点序列为()。A.ahbedfcC.ahebcdfB.ahcfebdD.ahebcfd参考答案：ahebcdf10.线性表以()方式存储，能进行折半查找。A.关键字有序的链接C.关键字有序的顺序B.顺序D.数组参考答案：关键字有序的顺序二、填空题(每小题2分，共24分)11.n个元素进行冒泡法排序，通常需要进行(n-1)趟冒泡。12.在对一组序列(35，19，77，2，6，53，55，27，26，98)进行直接插入排序时，当把第9个记录26插入到有序表时，为寻找插入位置需进行(6)次元素间的比较。13.在C语言中，分别存储“S”和‘s’，各需要占用(两个和1个)字节。14.数据的逻辑结构在计算机中的表示称为(存储结构)结构。15.在一棵二叉树中，若编号为i的结点是其双亲结点的左孩子，则i结点的双亲结点的顺序编号为(i/2).16.设有一个头指针为head的单向链表，p指向表中某一个结点，且有p一>next为NULL，现要把该单向链表构造成单向循环链表，可通过操作(p一>next=head；).17.从一个栈顶指针为top的链栈中删除一个结点时，用d保存被删结点的值，可执行d=top->data；和(top=top->next；).(结点的指针域为next，数据域为data)。18.循环链队列中，设front和rear分别为队头和队尾指针，(最多元素为MaxSize，采用少用一个元素的模式)，判断循环链队列为满的条件为:(front==(rear+1)%MaxSize).19.一棵有7个权重值构造的哈夫曼树，共有(13)个结点。20.二叉树中有1个1度结点，8个2度结点，则该二叉树树共有(18)个结点。21.如图所示的二叉树，其先序遍历序列为(215934786).22.在查找表中，通过记录的某关键字能唯一地确定一个记录，该关键字称为(主关键字).三、综合题(每小题6分共30分)23.(1)对给定权值4，2，6，6，7，8，构造高度为4层的哈夫曼树。(设根为第1层)提示：构造中当出现有两个以上值相等的可选结点时，可适当选择结点组合，以控制树的高度。(2)求树的带权路径长度。(2)WPL=(4+2+6+6)*3十(7+8)*2=8424.如下的一棵二叉树，(1)请给出前序遍历序列?请给出中序遍历序列?(2)把1，2，3，4，5，6，7，8，9填人，使它成为一棵二叉排序树。提示：设图中的树是二叉排序树，则中序遍历序列是有序的，从而找出中序遍历序列与1，2，…9的对应关系。(3)在图中给出在二叉排序树中插入结点2.5的结果。

四、程序填空题(每空2分，共16分)25.以下函数为直接选择排序算法，对a[1]，a[2]，…a[n]中的记录进行直接选择排序，完成程序中的空格typedefstruct{intkey；…}NODE；voidselsort(NODEa[]，intn){Inti，j，k；NODEtemp；for(i=1；i<=(1)____________；i++) { k-i；for(j=i十1；j<=(2)____________；j++)if(a[j].key<alk].key)(3)______________;if(i!=k){ temp=ai； (4)____________________ (5)_____________________} }}参考答案：(1)n一1(2)n(3)k=j(4)a[i]=a[k](5)a[k]=temp

26.设有一个头指针为head的不带头结点单向链表，且p、q是指向链表中结点类型的指针变量，p指向链表中某结点a(设链表中没有结点的数据域与结点a的数据域相同)，在以下程序段中，写出相关语句(1)使该单向链表成为单向循环链表(2)删去a结点q＝p；x=p一>data；while(q一>next!=NULL)q=q一>next；(1)_____________________q=p；p=->next；while(p->data!l=x){ q一p；(2)______________________}(3)______________________________参考答案：(1)q->next=head；(2)p=p->next；(3)q->next=p->next；国家开放大学2019年秋季学期期末统一考试数据结构(本)试题2020年1月一、单项选择题(每小题3分，共30分)1.以下说法不正确的是()。A.线性表的链式存储结构不必占用连续的存储空间B.一种逻辑结构只能有唯一的存储结构C.一种逻辑结构可以有不同的存储结构D.线性表的顺序存储结构必须占用连续的存储空间参考答案：一种逻辑结构只能有唯一的存储结构2.单向链表所具备的特点之一是()。A.可以随机访问表中任一结点B.需要占用连续的存储空间C.插入元素和删除元素的操作不需