试卷三

试卷三一、单项选择题(在下列每小题四个备选答案中选出一个正确答案，并将其字母标号填入题干的括号内。每小题2分，共30分)1．数据结构可以形式化地定义为（S，△），其中S指某种逻辑结构，△是指（）A.S上的算法B.S的存储结构C.在S上的一个基本运算集D.在S上的所有数据元素2．下列说法正确的是（）A.线性表的逻辑顺序与存储顺序总是一致的B.线性表的链式存储结构中，要求内存中可用的存储单元可以是连续的，也可以不连续C.线性表的线性存储结构优于链式存储结构D.每种数据结构都具有插入、删除和查找三种基本运算3．稀疏矩阵一般采用（）方法压缩存储。A.三维数组B.单链表C.三元组表D.散列表4.在一个单链表中，若p↑结点不是最后结点，在p↑之后插入s↑结点，则实行()。A.s↑.next:=p；p↑.next=s;B.s↑.next:=p↑.next;p↑.next:=s；C.s↑.next:=p↑.next;p:=s;D.p↑.next:=s;s↑.next=p;5.某个向量第一元素的存储地址为100，每个元素的长度为2，则第五个元素的地址是()。A.110B.108C.100D.1206.下面的二叉树中，()不是完全二叉树。7.一组记录的排序码为(47、78、61、33、39、80)，则利用堆排序的方法建立的初始堆为()。A.78、47、61、33、39、80B.80、78、61、33、39、47C.80、78、61、47、39、33D.80、61、78、39、47、338.假设left和right为双向链表中指向直接前趋结点和直接后继结点的指针域，现要把一个指针s所指的新结点作为非空双链表中q所指地点(中间结点)的直接后继结点插入到该双向链表中，则下列算法段能正确完成上述要求的是()A.q-right=s;s-left=q;q-right-left=s;s-right=q-right;B.s-left=q;q-right=s;q-right-left=s;s-right=q-right;C.s-left=q;s-right=q-right;q-right-left=s;q-right=s;D.以上都不对9.由下列三棵树组成转的森林换成一棵二叉树为()10.for（i=0；im；i++）for（j=0；jt；j++）c［i］［j］=0；for（i=0；im；i++）for（j=0；jt；j++）for（k=0；kn；k++）c［i］［j］=c［i］［j］+a［i］［k］*b［k］［j］；上列程序的时间复杂度为（）A.O（m+n×t）B.O（m+n+t）C.O（m×n×t）D.O（m×t+n）11.设循环队列的元素存放在一维数组Q［0‥30］中，队列非空时，front指示队头元素的前一个位置，rear指示队尾元素。如果队列中元素的个数为11，front的值为25，则rear应指向的元素是（）A.Q［4］B.Q［5］C.Q［14］D.Q［15］12.定义二维数组A［1‥8，0‥10］，起始地址为LOC，每个元素占2L个存储单元，在以行序为主序的存储方式下，某数据元素的地址为LOC+50L，则在以列序为主序的存储方式下，该元素的存储地址为（）A.LOC+28LB.LOC+36LC.LOC+50LD.LOC+52L13.采用排序算法对n个元素进行排序，其排序趟数肯定为n-1趟的排序方法是（）A.插入和快速B.冒泡和快速C.选择和插入D.选择和冒泡14.设h是指向非空带表头结点的循环链表的头指针，p是辅助指针。执行程序段p=h;while(p-next-next!=h)p=p-next;p-next=h;后（其中，p-next为p指向结点的指针域），则()A.p-next指针指向链尾结点B.h指向链尾结点C.删除链尾前面的结点D.删除链尾结点15.某二叉树的先根遍历序列和后根遍历序列正好相反，则该二叉树具有的特征是()A.高度等于其结点数B.任一结点无左孩子C.任一结点无右孩子D.空或只有一个结点二、填空题(本大题共13小题，每小题2分，共26分)请在每小题的空格中填上正确答案。错填、不填均无分。16.数据的逻辑结构通常包括集合、线性结构、____________和图状结构。17．给定n个值构造哈夫曼树。根据哈夫曼算法，初始森林中共有n棵二叉树，经过次合并后才能使森林中的二叉树的数目由n棵减少到只剩下一棵最终的哈夫曼树。18．树型结构结点间通过“父子”关系相互关联，这种相互关联构成了数据间的关系。19.在一个具有n个结点的单链表中查找值为m的某结点，若查找成功，则需平均比较的结点数为____________。20.数据表示和________________是程序设计者所要考虑的两项基本任务。21.在循环队列中，存储空间为0~n-1。设队头指针front指向队头元素前一个空闲元素，队尾指针指向队尾元素，那么其队空标志为rear=front，队满标志为_________。22.深度为k的二叉树至多有_________个结点，最少有_________个结点。23．在堆排序和快速排序中，若原始记录已基本有序，则较适合选用。24.在一棵二叉排序树上按____________遍历得到的结点序列是一个有序序列。25.实现二分查找的存储结构仅限于顺序存储结构，且其中元素排列必须是____________的。26.三个结点可构成________种不同形态的二叉树。27.设需将一组数据按升序排序。在无序区中依次比较相邻两个元素ai和ai+1的值，若ai的值大于ai+1的值，则交换ai和ai+1。如此反复，直到某一趟中没有记录需要交换为止，该排序方法被称为_________。28.对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为2n个，其中________个用于链接孩子结点。三、应用题（本大题共5小题，每小题6分，共30分）29.已知一棵二叉树的前序序列是ABCDEFG，中序序列是CBDAEGF。请构造出该二叉树，并给出该二叉树的后序序列。30．有一字符串序列为5*-x-y/x+2，利用栈的运算将其输出结果变为5x-*yx+/-2，试写出该操作的入栈和出栈过程（采用push(a)表示a入栈，pop(a)表示a出栈）。31.已知某二叉树的顺序存储结构如图所示，试画出该二叉树，并画出其二叉链表表示。ABCDEFG32.已知一组键值序列为(38，64，73，52，40，37，56，43)，试采用快速排序法对该组序列作升序排序，并给出每一趟的排序结果。33.请按照数列{28，45，33，12，37，20，18，55}的先后插入次序，生成一棵二叉排序树。四、算法设计题(本大题共3小题，共14分)34.试编写一算法，以完成在带头结点单链表L中第i个位置前插入元素X的操作。（4分）35.某带头结点的单链表的结点结构说明如下：（6分）typedefstructnode1{intdata;structnode1*next}node；试设计一个算法intcopy(node*head1,node*head2)，将以head1为头指针的单链表复制到一个不带头结点且以head2为头指针的单链表中。36.若二叉树存储结构采用二叉链表表示，试编写一算法，计算一棵二叉树的所有结点数。（4分）参考答案一、选择题（本题共30分,每题2分）1、C2、B3、C4、B5、B6、C7、B8、C9、A10、C11、B12、D13、C14、D15、A二、填空题（本题共26分,每小题2分）16、树状结构17、n-118、逻辑19、n/220、数据处理21、front==(rear+1)%n22、2k-1，k23、堆排序24、中序25、有序26、527、冒泡排序28、n-1三、应用题（本题共30分，每小题6分）29、后序序列：CDBGFEA(3分)(3分)30、push(5);pop(5);push(*);push(-);push(x);pop(x);pop(-);pop(*);push(-);push(y);pop(y);push(/);push(x);pop(x);push(+);pop(+);pop(/);pop(-);push(2);pop(2);32、第1趟：[37]38[735240645643]第2趟：3738[4352406456]73第3趟：3738[40]43[526456]73第4趟：3738404352[6456]73FEABCDG第5趟：3738404352[56]6473第6趟：373840435256647331、33、四、算法设计题（本题共14分）34、(4分)typedefstructnode*pointer;structnode{datatypedata;pointernext;};typedefpointerlklist;voidinsert_lklist(lklisthead,datatypex,inti){pointer*p,*s;p=head;j=0;while((p-next!=NULL)&&(ji-1)){p=p-next;j++;}AB∧NULL∧C∧ROOT∧DE∧F∧∧G∧2812452018335537BACDEFGif(j!=i-1){printf(不存在第i个位置);break();}else{s=malloc(size);s-data=x;s-next=p-next;p-next=s;}}35、(6分)intcopy(node*head1,node*head2){Node*p,*s;P=head1-next;If(p!=NULL){*r=malloc(size);r-data=p-data;head2=r;p=p-next;}else{head2=NULL;Return(0);}While(p!=NULL){*s=malloc(size);s-data=p-data;r-next=s;r=s;p=p-next;}r-next=NULL;return(1);}36、（4分）typedefcharDataType;typedefstructnode{DataTypedata;structnode*lchild,*rchild;}BinTNode;typedefBinTNode*BinTree;intnodes(BinTreeT){intnum1,num2;if(T==NULL)return(0);elseif(T-lchild==NULL&&T-rchild==NULL)return(1);else{num1=nodes(T-lchild);num2=nodes(T-rchild);return(num1+num2+1);}}