西南财经大学电子商务学院

1、第2页 共 3 页密2009-2010-1学期第 PAGE 1 页 共 NUMPAGES 5 页西南财经大大学天府学学院试卷(B卷)考试科目：数据结构构_本年级 层次 教学班 姓名： 学号：记分表试题号一二三四五六总分考分阅卷人注意：1、本次考考试为A卷考试，考考试时间1120分钟钟。 2、请将将答案依次次写在专用用 答题纸 上。3、全卷共共一部分，满满分为1000分。一、单项选选择题（共共15题，每每题2分，共共计30分分）1、在数据据结构学科科中，伪代代码是（ ）A、描述算算法且容易易理解的一一种语言B、能够方方便描述算算法中的分分支与循环环等结构化化语句C、不能直直接编译或或解释执行行D

2、、以上都都正确2、若进栈栈序列为11、2、33、4，进进栈过程中中可以出栈栈，则以下下不可能的的出栈序列列是（）A、1、44、3、22B、2、3、4、1 C、3、1、4、2 D、3、4、2、13、设语句句x+的的时间是单单位时间，则则以下语句句的时间复复杂度为（ ）。for(i=1; i=n; ii+)forr(j=11; j neextB、rearr = rrearnexxtC、frrontnexxt = rearr ; rrear = reearnexxtD、fronnt = fronntnexxt; frrontnexxt = rearr5、向一个个栈顶指针针为hs的的链栈中插插入一个s

3、s 结点时时，应执行行（ ）。A、hss-neext=ss;B、s-nextt=hs; hs=s;C、s-nextt=hs-nexxt; hhs-nnext=s;D、s-nextt=hs; hs=hs-nextt;6、对于顺顺序存储的的有序表 5，112，200，26，337，422，46，550，644，若采采用折半查查找，则查查找元素226的比较较次数为（ ）。A、2B、3C、4D、57、对一组组数据（886，488，26，115，233）排序，数数据的排列列次序在排排序过程中中的变化为为： 866 448 26 15 233 155 448 26 86 233 15 233 226 86

4、 48 15 233 226 48 86 这个排序过过程采用的的排序方法法是（ ）。A、冒泡 B、选择择 C、快速 D、插入8、若根根据查找表表（23，444，366，48，552，733，64，558）建立立哈希表，采采用h(KK)=K%7计算哈哈希地址，则则哈希地址址等于3的的元素个数数为（ ）。A、1B、2C、3D、49、若一个个元素序列列基本有序序，则选用用（ ）方法法较快。A、直接插插入排序 BB、简单选选择排序C、堆排序序 D、快速排序序10、在一一个长度为为n的顺序序表中向第第i个元素素(0iilc=NNULLB、p-ltaag=1C、p-lc=NNULL且且p-lltag=1

5、D、以上上都不对二、是非题题（下列叙述述正确的写写上T，否否则，写上上F。共110题，每题题1分，共计计10分）1、在有向向图G中，和是两两条不同的的边。（ ）2、线性表表中的每个个结点最多多只有一个个前驱和一一个后继。（ ）3、线性表表简称为“顺序表”。（ ）4、线性的的数据结构构可以顺序序存储，也也可以链式式存储。非非线性的数数据结构只只能连接存存储。（ ）5、从单链链表的任一一结点出发发，都能访访问到所有有结点。（ ）6、在有序序的顺序表表和有序的的链表上，均均可使用折折半查找来来提高查找找效率。（ ）7、如果某某种排序方方法是不稳稳定的，那那么该排序序方法不具具有实用价价值。（ ）8、

6、满二叉叉树一定是是完全二叉叉树。（ ）9、若二叉叉树的中序序遍历序列列与后序遍遍历序列相相同，则该该二叉树一一定是任何何结点都没没有右子树树。（ ）10、数据据结构概念念包括数据据之间的逻逻辑结构、数据在计计算机中的的存储方式式和数据的的运算三个个方面。（ ）三、填空题题（共10空，每空1分，共共计10分）1、队列和和堆栈最大大的相同点点在于，它它们都同属属于【1】;队列和栈栈最大的不不同点在于于，队列元元素的删除除和插入遵遵循【2】规则；而而栈元素的的删除和插插入遵循后后进先出（LLIFO）规规则。2、如果经经常对线性性表进行插插入和删除除运算，则则最好采用用【3】存储结构构。3、已知二二维

7、数组AA53，其其每个元素素占2个存存储单元，并并且A000的存储地地址为10000。则则元素A322的存储储地址为【4】。4、假定一一个顺序循循环队列的的存储空间间长度为QQueueeSizee，队首和和队尾指针针分别用ffrontt和reaar表示，如果采用少用一个存储空间的方式来区分循环队列是队空还是队满，则判断队空的条件是【5】；判断队满的条件是 【6】。5、数据结结构按结点点间的关系系，可分为为4中逻辑辑结构，它它们分别是是【7】、【8】、【9】和【10】。四、算法填填空题（每空2分，共20分）1、已知二二叉树中的的结点类型型BinTTreeNNode定定义为：strucct Bii

8、nTreeeNoddeElemTType dataa;BinTrreeNoode *leftt,*riight;其中datta为结点点值域，lleft和和righht分别为为指向左、右子女结结点的指针针域。下面面函数的功功能是返回回二叉树BBT中值为为X的结点点所在的层层号，请在在画有横线线的地方填填写合适内内容。int NodeeLeveel(BinTTreeNNode *BT,ElemmTypee X)int c1,cc2;if(BTT=NUULL) retuurn 00; /*空空树的层号号为0*/elsse iff(BT-datta = X) retturn 1; /*根结点点的层号为

9、为1*/elssec11=NoddeLevvel(BBT-lleft,X)if(c11=1) rreturrn c11+1;c2= 【1】 ;if ( 【2】 ) retuurn 【3】 ; else retturn 0; /*若若树中不存存在X结点点则返回00*/2、下列算算法片段是是矩阵快速速转置算法法，请在划划线的位置置填入适当当的内容。#deffine ARRAAYSIZZE 10024typeedef struuctintt roww,coll; /*非零元素素的行号和和列号*/ DattaTyppe vaalue; /*非零零元素的值值*/TriTType; typeddef ss

10、truccttriTType itemmsARRRAYSIIZE+11; /*非非零元三元元组，ittem00未用*/int rowss,colls; /*稀疏矩阵阵的行数、列数*/int nnums; /*稀疏矩阵阵的非零元元素个数*/TriAArrayy;FasttTrannsMattrix(TriAArrayy TA, TriiArraay TBB)/*TAA为转置前前的三元组组属性表，TTB为转置置后的三元元组顺序表表*/int i, j=0, kk=0;int posARRAATSIZZE+1, numARRAATSIZZE+1;if(TTA.nuums)for(i=1;i=TTA.

11、cools;ii+) numi=00;for(i=1;i=TTA.nuums;ii+) /*求求TA中每每一列非零零元个数*/ 【4】 ;pos1=11;for(i=2;i=TTA.cools;ii+) /*计算算第i列第第一个非零零元的位置置 【5】 ;for(ii=1;iiST.eelemmid.keyy) 【9】 ; /*继续在在前一半查查找*/else 【10】 ; /*继续在在后一半查查找*/returrn 0; /*顺顺序表中不不存在待查查元素*/五、算法应应用题（共共15分）1、模式匹匹配的KMMP算法应应用设目标为ss=”abcaaabbaabcabbaacbbacbaa”，模式pp=”abcaabaa”。(1)计算算模式p的的nexttj函数值值。（3分）(2)不写写出KMPP算法，只只画出采用用nexttj函函数进行模模式匹配时时每一趟的的匹配过程程。（2分）2、若一棵棵二叉树后后序遍历为为DHEBBFIGCCA，中序序遍历序列列为DBEEHAFCCIG。试试画出这棵棵二叉树。（5分）3、对于给给定的一组组记录的关关键字223，133，17，221，300，60，5