搜索
1/102008年1月一、单项选择题（本大题共15小题,每小题2分,共30分）在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。1.逻辑上通常可以将数据结构分为（C）P3A.动态结构和静态结构B.顺序结构和链式结构C.线性结构和非线性结构D.初等结构和组合结构2.在下列对顺序表进行的操作中,算法时间复杂度为O(1)的是（A）P16A.访问第i个元素的前驱（1ni）B.在第i个元素之后插入一个新元素(ni1)C.删除第i个元素(ni1)D.对顺序表中元素进行排序3.假设带头结点的单向循环链表的头指针为head,则该链表为空的判定条件是（D）P26A.head==NULLB.head–next==NULLC.head!=NULLD.head–next==head4.已知栈的最大容量为4。若进栈序列为1,2,3,4,5,6,且进栈和出栈可以穿插进行,则可能出现的出栈序列为（C）A.5,4,3,2,1,6B.2,3,5,6,1,4C.3,2,5,4,1,6D.1,4,6,5,2,35.与线性表相比,串的插入和删除操作的特点是（D）P54A.通常以串整体作为操作对象B.需要更多的辅助空间C.算法的时间复杂度较高D.涉及移动的元素更多6.假设以三元组表表示稀疏矩阵,则与如图所示三元组表对应的4×5的稀疏矩阵是（注：矩阵的行列下标均从1开始）（B）P64A.00405000000000706080B.00000004053000706080C.00405000073000006080D.000003040500007060807.以下有关广义表的表述中,正确的是（A）P66A.由0个或多个原子或子表构成的有限序列B.至少有一个元素是子表C.不能递归定义D.不能为空表8.树的先根序列等同于与该树对应的二叉树的（A）A.先序序列B.中序序列C.后序序列D.层序序列9.假设有．向图含n个顶点及e条弧,则表示该图的邻接表中包含的弧结点个数为（B）P105A.nB.eC.2eD.n·e10.如图所示的有向无环图可以得到的不同拓扑序列的个数为（C）A.1B.2C.3D.411.下列排序方法中,稳定的排序方法为（D）P139A.希尔排序B.堆排序C.快速排序D.直接插入排序12.对下列关键字序列进行快速排序时,所需进行比较次数最少的是（C）P147A.（1,2,3,4,5,6,7,8）B.（8,7,6,5,4,3,2,1）2/10C.（4,3,8,6,1,7,5,2）D.（2,1,5,4,3,6,7,8）13.含n个关键字的二叉排序树的平均查找长度主要取决于（B）P180A.关键字的个数B.树的形态C.关键字的取值范围D.关键字的数据类型14.下列查找算法中,平均查找长度与元素个数n不直接相关的查找方法是（D）P202A.分块查找B.顺序查找C.二分查找D.散列查找15.可有效提高次关键字查找效率的文件是（B）P219A.顺序文件B.倒排文件C.散列文件D.VSAM文件二、填空题（本大题共10小题,每小题2分,共20分）请在每小题的空格中填上正确答案。错填、不填均无分。16.数据的存储结构是其逻辑结构映象。P117.输入线性表的n个元素建立带头结点的单链表,其时间复杂度为O（n）。P2218.假设循环队列的元素存储空间大小为m,队头指针f指向队头元素,队尾指针r指向队尾元素的下一个位置,则在少用一个元素空间的前提下,表示“队满”的条件是(r+1)%m==f。P3819.给定串的联接操作函数：char*strcat(char*to,char*from);//将串from联接到串to的末尾,并返回联接后的串若字符串s1=〞point〞,s2=〞of〞,则strcat(s1,strcat)(s2,s1))的操作结果是Pointofpoint。20.假设二维数组A[8][10]按行优先顺序存储,若每个元素占2个存储单元,元素A[0][0]的存储地址为100,则元素A[4][5]的存储地址为190。=100+（4*10+5）*221.假设一棵完全二叉树含1000个结点,则其中度为2的结点数为498。22.已知一个有向网如图所示,从顶点1到顶点4的最短路径长度为55。23.在快速排序、堆排序和归并排序中,最坏时间复杂度为O(n2)的排序算法有快速排序。P15624.假设散列表的表长为11,散列函数为H(key)=key%7,若用线性探测处理冲突,则探查地址序列hi的计算公式为Hi=(H(key)+i)%11i=0,1,….10)10,,2,1(i。25.VSAM文件由索引集、顺序集和数据集三部分组成。P215三、解答题（本大题共4小题,每小题5分,共20分）26.已知广义表的图形表示如图所示,(1)写出该广义表L;((e),(),(a,(b,c,d),(b,c,d))(2)分别写出该广义表的深度和长度。3,427.已知二叉树的先序序列和中序序列分别为ABDEHCFI和DBHEACIF,(1)画出该二叉树的二叉链表存储表示;(2)写出该二叉树的后序序列。DHEBIFCA(15460,1523455,123460,前9层完整29-1=511第10层489个n0+n1+n2=1000n1=1n0=n2+13/1028.已知有向图的邻接表如图所示,(1)写出从顶点A出发,对该图进行广度优先搜索遍历的顶点序列;ABDCE(2)画出该有向图的逆．邻接表。29.依次读入给定的整数序列{7,16,4,8,20,9,6,18,5},完成下列操作：1)构造一棵二叉排序树,计算在等概率情况下该二叉排序树的平均查找长度ASL;2)若变更序列中元素的排列,可构造出平均查找长度达到最小的二叉排序树。写出满足上述要求的序列中的第一个元素。(1)ASL=（1+2*2+3*4+4*2）/9=25/9(2)7,16,4,8,20,9,6,18,54,5,6,7,8,9,16,18,20四、算法阅读题（本大题共4小题,每小题5分,共20分）30.假设以带头结点的单链表表示线性表,阅读下列算法f30,并回答问题:(1)设线性表为(a1,a2,a3,a4,a5,a6,a7),写出执行算法f30后的线性表；(1)a2,a4,a6(2)简述算法f30的功能。(2)删除编号为奇数的节点voidf30(LinkListL){//L为带头结点单链表的头指针LinkListp,q;P=L;while(p&&p–next){q=p–next;p–next=q–next;p=q–next;free(q);}}31.算法f31的功能是借助栈结构实现整数从10进制到8进制的转换,阅读算法并回答问题：(1)画出n为十进制的1348时算法执行过程中栈的动态变化情况;(2)说明算法中while循环完成的操作。voidf31(intn)//n为非负的十进制整数{inte;SeqStackS;4/10InitStack(&S);do{Push(&S,n%8);n=n/8;}while(n);while(!StackEmpty(&S)){e=Pop(&S);printf(〞%ld〞,e);}}(1)右图(2)将栈中的数依次输出32.已知以二叉链表作二叉树的存储结构,阅读算法f32,并回答问题：(1)设二叉树T如图所示,写出执行f32(T)的返回值;4(2)简述算法f32的功能。求二叉树T的深度intf32(BinTreeT){intm,n;if(!T)return0;else{m=f32(T–lchild);n=f32(T–rchild);if(mn)returnm+1;elsereturnn+1;}}33.设有向图邻接表定义如下；typedefstruct{VertexNodeadjlist[MaxVertexNum];intn,e;//图的当前顶点数和弧数}ALGraph;//邻接表类型其中顶点表结点VertexNode结构为：边表结点EdegNode结构为：阅读下列算法f33,并回答问题：(1)已知有向图G的邻接表如图所示,写出算法f33的输出结果;(2)简述算法f33的功能。vertexfirstedgeadjvexnext5/10voiddfs(ALGraph*G,intv){EdgeNode*p;visited[v]=TRUE;printf(〞%c〞,G–adjlist[v]·vertex);for(p=G–adjlist[v])·firstedge;p;p=p–next)if(!visited[p–adjvex])dfs(G,p–adjvex);}voidf33(ALGraph*G){intv,w;for(v=0;vG–n;v++){for(w=0;wG–n;w++)visited[w]=FALSE;printf(〞%d:〞,v);dfs(G,v);printf(〞﹨n〞);}}(1)ABCED(2)深度优先搜索有向图五、算法设计题(本大题10分)34.假设以单链表表示线性表,单链表的类型定义如下:typedefstructnode{DataTypedata;structnode*next;}LinkNode,*LinkList;编写算法,将一个头指针为head且不带头结点的单链表改造为一个含头结点且头指针仍为head的单向循环链表,并分析算法的时间复杂度。LinkListModifyList(head){LinkNodep;p=(LinkList)malloc(sizeof(LinkNode));p-next=head;head=p;while(p-next)p=p-nextp-next=head;}6/102008年10月数据结构一、单项选择题(本大题共15小题,每小题2分,共30分)在每小题列出的四个备选项中只有一个是最符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。1.如果在数据结构中每个数据元素只可能有一个直接前驱,但可以有多个直接后继,则该结构是（C）A.栈B.队列C.树D.图2.下面程序段的时间复杂度为（C）for(i=0;im;i++)for(j=0;jn;j++)A[i][j]=i*j;A.O(m2)B.O(n2)C.O(m*n)D.O(m+n)3.在头指针为head的非空单循环链表中,指针p指向尾结点,下列关系成立的是（A）A.p-next==headB.p-next-next==headC.p-next==NULLD.p==head4.若以S和X分别表示进栈和退栈操作,则对初始状态为空的栈可以进行的栈操作系列是（D）A.SXSSXXXXB.SXXSXSSXC.SXSXXSSXD.SSSXXSXX5.两个字符串相等的条件是（D）A.串的长度相等B.含有相同的字符集C.都是非空串D.串的长度相等且对应的字符相同6.如果将矩阵An×n的每一列看成一个子表,整个矩阵看成是一个广义表L,即L=((a11,a21,…,an1),(a12,a22,…,an2),…,（a1n,a2n,…,ann）),并且可以通过求表头head和求表尾tail的运算求取矩阵中的每一个元素,则求得a21的运算是（A）A.head(tail(head(L)))B.head(head(head(L)))C.tail(head(tail(L)))D.head(head(tail(L)))7.已知一棵含50个结点的二叉树中只有一个叶子结点,则该树中度为1的结点个数为（D）A.0B.1C.48D.498.在一个具有n个顶点的有向图中,所有顶点的出度之和为Dout,则所有顶点的入度之和为（A）A.DoutB.Dout-1C.Dout+1D.n9.如图所示的有向无环图可以得到的拓扑序列的个数是（C）A.3B.4C.5D.62653426354256346253