离散数学本)试题资料

1试卷代号：B中央广播电视大学学年度第学期期末考试理工级第学期数据结构（本）试题2009年3月一、单项选择题（每小题2分，共30分）1．一种逻辑结构（）存储结构。A．可以有不同的B．只能有唯一的C．的数据元素在计算机中的表示称为D．的数据元素之间的关系称为2．以下说法中不正确的是（）。A．双向循环链表中每个结点需要包含两个指针域B．已知单向链表中任一结点的指针就能访问到链表中每个结点C．顺序存储的线性链表是可以随机访问的D．单向循环链表中尾结点的指针域中存放的是头指针3．双向循环链表结点的数据类型为：structnode{intdata;structnode*next;/*指向直接后继*/structnode*prior;}；设p指向表中某一结点，要显示p所指结点的直接前驱结点的数据元素，可用操作（）。A．printf(“%d”,p-next-data);B．printf(“%d”,p-prior-data);C．printf(“%d”,p-prior-next);D．printf(“%d”,p-data);4．一个栈的进栈序列是efgh，则栈的不可能的出栈序列是（）（进出栈操作可以交替进行）。A．hgfeB．gfehC．fgehD．ehfg5．设top是一个链栈的栈顶指针，栈中每个结点由一个数据域data和指针域next组成，设用x接收栈顶元素，则取栈顶元素的操作为（）。A．top-data=x;B．top=top-next;C．x=top-data;D．x=top-data;top=top-next;6．以下说法不正确的是（）。A．栈的特点是后进先出B．队列的特点是先进先出C．栈的删除操作在栈底进行，插入操作在栈顶进行题号一二三四总分分数得分评卷人2bcgdafeD．队列的插入操作在队尾进行，删除操作在队头进行7．char*p;p=StrCat(“ABD”,”ABC”);Printf(“%s”,p);的显示结果为（）。A．-1B．ABDABCC．ABD．18．深度为5的满二叉树至多有（）个结点（根结点为第一层）A．40B．31C．34D．359．已知一个图的所有顶点的度数之和为m，则该图的边数为（）。A．2mB．mC．2m+1D．m/210．以下说法不正确的是（）。A．连通图G的生成树一定是唯一的B．连通图G一定存在生成树C．连通图G的生成树中一定要包含G的所有顶点D．连通图G的生成树一定是连通而且不包含回路11．有序表为{1，2，4，6，10，18，20，32}，用课本中折半查找算法查找值18，经（）次比较后成功查到。A．3B．2C．4D．512．在排序过程中，可以通过某一趟排序的相关操作所提供的信息，判断序列是否已经排好序，从而可以提前结束排序过程的排序算法是()。A．冒泡B．选择C．直接插入D．折半插入13．用折半查找法，对长度为12的有序的线性表进行查找，最坏情况下要进行（）次元素间的比较A．4B．3C．5D．614．如图若从顶点a出发按深度优先搜索法进行遍历，则可能得到的顶点序列为（）。A．acfgedbB．aedbgfcC．acfebdgD．aecbdgf15．一棵哈夫曼树总共有25个结点，该树共有（）个非叶结点（非终端结点）。A．12B．13C．14D．15二、填空题（每小题2分，共24分）1．结构中的元素之间存在多对多的关系称为________结构。得分评卷人32．设有一个单向循环链表，结点的指针域为next，头指针为head，指针p指向表中某结点，若逻辑表达式________的结果为真，则p所指结点为尾结点。3．设有一个链栈，栈顶指针为hs，现有一个s所指向的结点要入栈，则可执行操作s-next=hs;________。4．在一个链队中，f和r分别为队头和队尾指针，队结点的指针域为next，s指向一个要入队的结点，则入队操作为________；________；5．循环队列的最大存储空间为MaxSize=6，采用少用一个元素空间以有效地判断栈空或栈满，若队头指针front=4，当队尾指针rear=________时队满，队列中共有________个元素。6．程序段char*s=”aBcD”;n=0;while(*s!=’\0’){if(*s＝’a’&&*s＝’z’)n++;s++;}执行后n=________7．一棵二叉树中顺序编号为5的结点（树中各结点的编号与等深度的完全二叉中对应位置上结点的编号相同），若它存在左孩子，则左孩子的编号为________。8．根据搜索方法的不同，图的遍历有________两种方法。9．结构中的数据元素存在多对多的关系称为________结构。10．一棵有n个叶结点的二叉树，其每一个非叶结点的度数都为2，则该树共有_______个结点。11．串的两种最基本的存储方式分别是_______和________。12．按某关键字对记录序列排序，若关键字的记录在排序前和排序后仍保持它们的前后关系，则排序算法是稳定的，否则是不稳定的。三、综合题（每小题10分，共30分）1．（1）已知某二叉树的先序遍历序列是aecdb，中序遍历序列是eadcb，试画出该二叉树（2）给出上述二叉树的后序遍历序列（3）若上述二叉树的各个结点的字符分别是1，2，3，4，5，并恰好使该树成为一棵二叉排序树，试问a、b、c、d、e的值各为多少？得分评卷人42．（1）给定数列{8，17，5，9，21，10，7，19，6}，依次取序列中的数构造一棵二叉排序树（2）对上述二叉树给出中序遍历得到的序列3．（1）以给定权重值1，2，12，13，20，25为叶结点，建立一棵哈夫曼树（2）若哈夫曼树有n个非叶子结点，则树中共有多少结点。对给定的一组权重值建立的棵哈夫曼树是否一定唯一四、程序填空题（每空2分，共16分）1．以下函数是二叉排序树的查找算法，若二叉树为空，则返回根结点的指针，否则，返回值是指向树结点的结构指针p（查找成功p指向查到的树结点，不成功p指向为NULL）完成程序中的空格typedefstructBnode得分评卷人5{intkey;structBnode*left;structBnode*right;}Bnode;Bnode*BSearch(Bnode*bt,intk)/*bt用于接收二叉排序树的根结点的指针，k用以接收要查找的关键字*/{Bnode*p;if(bt==___(1)_____)return(bt);p=bt;while(p-key!=__(2)______){if(kp-key)___(3)_____;else___(4)_____;if(p==NULL)break;}Return(___(5)_____);}2．以下函数为链队列的出队操作（链队列带有头结点），出队结点的数据域的值由x返回，front、rear分别是链队列的队头、队尾指针structnode{ElemTypedata;structnode*next;};structnode*front，*rear;ElemTypeOutQueue(){ElemTypex;if(___(1)_____){printf(队列下溢错误！\n);exit(1);}else{structnode*p=front-next;x=p-data;front-next=___(2)_____;if(p-next==NULL)rear=front;free(p);___(3)_____;}}6aecbd试卷代号：B中央广播电视大学学年度第学期期末考试理工级第学期数据结构（本）试题答案及评分标准（供参考）2009年3月一、单项选择题（每小题2分，共30分）1．A2．B3．B4．D5．C6．C7．B8．B9．D10．A11．B12、A13．A14．B15．A二、填空题（每题2分，共24分）1．图状2．p-next==head;3．hs=s；4．r-next=s；r=s；5．3；56．27．108、深度优先；广度优先9．图状（网状）10．2n-111．顺序存储链式存储12．关键字相等的记录三、综合应用题（每小题10分，共30分）1．（1）（2）edbca（3）e=1,a=2,d=3,c=4,b=5785176219719102845132135732091315250123212．（1）（2）5，6，7，8，9，10，17，18，19，213．（1）（2）2n-1不一定唯一四、程序填空题（每空2分，共16分）1．（1）NULL（2）k（3）p=p-left（4）p=p-right（5）p2．（1）front==rear（2）p-next（3）return(x)