武汉大学数据结构-2005真题

数据结构部分（共75分）一. 单项选择题（2×10分，共20分）1. 某线性表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点，故采用 d 存储方式最节省运算时间。

A. 单链表B.循环单链表C. 双链表D.仅有尾结点指针的循环单链表2. 栈和队列的共同点是c 。

A. 都是先进后出B. 都是先进先出C. 只允许在端点处插入和删除元素D. 没有共同点3．对于含有n个互不相同字符的串，则真子串（不包括串自身）的个数是c 。

A. nB.n2C.n(n+1)/2D.n(n-1)/24. 在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为 cA. 4B. 5C. 6D. 75. 某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是d 。

A. 空或只有一个结点B. 完全二叉树C. 二叉排序树D. 高度等于其结点数6. 对图1所示的无向图，从顶点1开始进行深度优先遍历；可能得到顶点访问序列是a 。

A.1 2 4 3 5 7 6B.1 2 4 3 5 6 7C.1 2 4 5 6 3 7D.1 2 3 4 5 7 6图1 一个无向图7. 对于含有n个顶点的带权无向连通图，它的最小生成树是指该图中任意一个d。

A.由n-1条权值最小的边构成的子图B.由n-l条权值之和最小的边构成的子图C.由n条权值之和最小的边构成的连通子图D.由n个顶点构成的边的权值之和最小的连通子图8. 有一组数据{15,9,7,8,20,1,7,4}，用堆排序的筛选方法建立的初始小根堆为c 。

A.{1,4,8,9,20,7,15,7}B.{1,7,15,7,4,8,20,9}C.{1,4,7,8,20,15,7,9}D.以上都不对9. 在含有27个结点的二叉排序树上，查找关键字为35的结点，则依次比较的关键字有可能是 d 。

A.28,36,18,46,35B.18,36,28,46,35C.46,28,18,36,35D.46,36,18,28,3510. 采用败者树进行k路平衡归并的外排序算法，其总的归并效率与k b 。

计算机专业基础综合数据结构（概论）历年真题试卷汇编2(总分：88.00，做题时间：90分钟)一、单项选择题(总题数：11，分数：22.00)1.数据元素之间的关系称为( )。

【北京理工大学2006九、2(1分)】（分数：2.00）A.操作B.结构√C.数据对象D.数据集合解析：2.(多选)一个算法具有( )等特点。

【华中科技大学2007二、17(2分)】（分数：2.00）A.有0个或多个输入量B.健壮性√C.正确性D.可行性解析：3.下面程序的时间复杂性为( )。

【南京理工大学2004一、4(1分)】for(int i=0；i（分数：2.00）A.O(n 2 )B.O(m*n) √C.O(m 2 )D.O(m+n)解析：4.在下列算法中，“x=x*2”的执行次数是( )。

【华中科技大学2006一、16(2分)】int suanfa]．(int n){int i，j，x=1;for(i=0；i（分数：2.00）A.m(n+1)／2 √B.Nlog 2 nC.n 2D.n(n一1)／2解析：5.执行下列算法suanfa2(1000)，输出结果是( )。

【华中科技大学2006一、17(2分)】void suanfa2(int n){int i=i;while(i<=n)i*=2；printf(“％d”，i);}（分数：2.00）A.2000B.512C.1024 √D.2 1000解析：6.当n足够大时下述函数中渐近时间最小的是( )。

【哈尔滨工业大学2005二、4(1分)】（分数：2.00）A.T(n)=nlog 2 n=1000log 2 nB.T(n)=nlog 2 3=1 000log 2 n √C.T(n)=n 2 =1000log 2 nD.T(n)=2nlog 2 n=1 000log 2 n解析：7.下面算法时间复杂度是( )。

【华中科技大学2006一、18(2分)】int suanfa3(int n){int i=i，s=l；while(s（分数：2.00）A.O(n) √B.O(2 2 )C.O(log 2 n)解析：8.下列函数中渐进时间复杂度最小的是( )。

1998一、选择1、世界上第一个地理信息系统产生于：A.中国B.美国C.加拿大D.澳大利亚2、判断点是否在多边形内常用：A.空间内插B.半线理论C.平板技术D.维数变化3、空间集合分析主要完成：A.地形分析B.缓冲区分析C.逻辑运算D.叠置分析4、以线性四*树表示8*8的栅格矩阵时，第6行第5列位置处的栅格的MORTON码值为：A.57B.39C.54D.365、建立空间要素之间的拓扑关系属于____功能A.空间分析B.图形分析C.空间查询D.地图整饰二、简述在栅格数据中提取多边形边界的一般方法三、地理信息系统中的数据输入包含几项内容？输入过程中可能产生的误差有几种？四、图画题给出一个四*树要求画出栅格矩阵，并用线性四*树和二维行程编码表示七、简答题1、地理坐标2、地图投影研究的主要内容3、地理信息系统中的地图投影配置应遵循的原则八、介绍两种商用GIS基础软件的主要特性和适应的场合九、某城市由于人口增长较快，原有的地下基础设施已经不能满足要求，为此须重新进行规划，目的是为了满足今后10—20年内城市人口发展的需要。

现用GIS辅助规划其要求是：1、能随时知道任意地方的地下管线的各类指标2、能随时了解那些管线需要重新建设3、能随时了解任意区域的人口指标4、管线应铺设在道路的两侧、单侧或中央。

5、管线铺设时应距离附近的建筑至少10米6、管线铺设和指标计算应结合地形进行7、输出规划成果，主要包括人口分布图和规划后的底下综合管线图现提供如下条件：1、规划区域的地形图及属性数据2、规划区域的道路图及属性数据3、规划区域的地下综合管线现状图及属性数据4、规划区域的人口分布规划图及属性数据5、规划区域的建筑分布分布图几属性数据6、已提供了由人口计算相应管线的负载的全套公式7、已提供了计算管线各种指标的公式8、所有的图件都已经入库根据以上的条件，设计用地理信息系统实现上述规划要求的方法，分别说明其中使用了哪些数据和GIS的那些主要功能。

2005级数据结构试题A卷注：回答问题，请在答题卡上回答，不要回答在试题上。

一、是非判断（回答’Y’或者’N’即可，不许多答、不许用其他符号替代24分）（1）线性表的逻辑顺序与物理顺序总是一致的。

（2）线性表的顺序存储表示优于链式存储表示。

（3）线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。

（4）二维数组是其数组元素为线性表的线性表。

（5）每种数据结构都应具备三种基本运算：插入、删除和搜索。

(6 ) 二叉树必须有父结点、但不一定有左孩子结点或是右孩子结点。

（7）用n个结点构造Huffman树，这个树有2n个结点。

（8）有n个顶点的有向图，各个顶点完全连通则有n-1条边。

（9）拓扑排序的有向图，要求图入度为0的顶点只能有一个。

（10）在二叉排序树上查找，其效率总是高于顺序表上查找。

（11）归并排序是稳定排序且时间复杂度为O(nLogn)。

（12）Floyd最短路计算需要深度遍历图、且仅仅适合于有向图。

二，选择判断（每个题目仅有一个答案30分）1．算法指的是A．计算机程序 B．解决问题的计算方法C．排序算法 D．解决问题的有限运算序列2．关于以下图问题的计算，使用深度编历算法的是：A．Dijkstra最短路B．拓扑排序C．关键路径计算D．Prim最小生成树3．将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为A．O（1） B．O（n） C．O（m） D．O（m+n）4．哈希表查找中，填充因子和查找效率的关系是：A．填充因子越大、查找效率越好B．填充因子越小、查找效率越好C．填充因子要根据查找对象计算D．填充因子和查找效率没直接关系5．图的拓扑排序中，主要使用了哪种数据结构存储来暂存顶点?A．顺序表 B．栈C．队列 D．数组6．如下陈述中正确的是A．串是一种特殊的线性表 B．串的长度必须大于零C．串中元素只能是字母 D．空串就是空白串7．图的顶点个数是n，深度遍历该图，时间复杂度是：A．O（1） B．O（n） C．O（n2） D．O（n3）8、有数组char A[3][3][3]，按行存放于一个连续的存储空间中,如A[0][0][0] 存储地址是200（10进制），则它的数组元素A[1][1][2]在内存中的位置是：A．212 B．211 C．214 D．2159．对一个单向链表，下列程序段中，p指针类型为：struct Node {int X;struct Node *next;}如p开始指向链表头结点，最后p一定指向尾结点的是：A．while(p!=NULL) p=p->next;B．while(p!=NULL) p++；C．while(p->next!=NULL) p++;D．while(p++ ->next!=NULL);10．索引文件通常由索引表和主文件两部分构成，其中A．索引表和主文件均必须是有序文件B．索引表和主文件均可以是无序文件C．索引表必须是有序文件D．主文件必须是有序文件11．在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为A．e B．2*e C．n2－e D．n2－2*e12．假设一个有n个顶点和e条弧的有向图用邻接矩阵表示,则删除与某个顶点Vi相关的所有弧的时间复杂度是A．O(n) B．O(e) C．O(n+e) D．O(n*e)13．用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下：20，15，21，25，47，27，68，35，8415，20，21，25，35，27，47，68，8415，20，21，25，27，35，47，68，84则所采用的排序方法是A．选择排序 B．希尔排序 C．归并排序 D．快速排序14．对n个不同值元素的集合，找到最大/最小元的算法，应该进行多少种比较?A．n B．n-1 C．n2 D．n2-115．下列排序方法中，属于不稳定的排序方法是A．直接插入排序法B．快速排序法C．冒泡排序法D．希尔排序法三、计算、简答题(28分)1 有二叉树，先序遍历结果EBADCFHGIKJ，中序遍历结果为ABCDEFGHIJK，则后序遍历结果是什么？2 有数字序列（40，28，16，56，50，32，30，63），按次序插入每个对象生成一棵A VL树，对该树插入完成后，给出该树的后序遍历结果。

数据结构真题2005年下半年(总分：154.98，做题时间：90分钟)一、{{B}}单项选择题{{/B}}(总题数：15，分数：30.00)1.若将数据结构形式定义为二元组(K,R)，其中K是数据元素的有限集合，则R是K上( )（分数：2.00）A.操作的有限集合B.映象的有限集合C.类型的有限集合D.关系的有限集合√解析：2.在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为 ( )（分数：2.00）A.n-i+1B.iC.i+1D.n-i √解析：3.若不带头结点的单链表的头指针为head，则该链表为空的判定条件是 ( )（分数：2.00）A.head==NULL √B.head—＞next==NULLC.head!=NULLD.head—＞next==head解析：4.引起循环队列队头位置发生变化的操作是 ( )（分数：2.00）A.出队√B.入队C.取队头元素D.取队尾元素解析：5.若进栈序列为1,2,3,4,5,6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是( )（分数：2.00）A.2,4,3,1,5,6B.3,2,4,1,6,5C.4,3,2,1,5,6D.2,3,5,1,6,4 √解析：6.字符串通常采用的两种存储方式是 ( )（分数：2.00）A.散列存储和索引存储B.索引存储和链式存储C.顺序存储和链式存储√D.散列存储和顺序存储解析：7.设主串长为n，模式串长为m(m≤n)，则在匹配失败情况下，朴素匹配算法进行的无效位移次数为 ( ) （分数：2.00）A.mB.n-mC.n-m+1 √D.n解析：8.二维数组A[12][18]采用列优先的存储方法，若每个元素各占3个存储单元，且第1个元素的地址为150，则元素A[9][7]的地址为 ( )（分数：2.00）A.429 √B.432C.435D.438解析：9.对广义表L=((a,b)，(c,d)，(e,f))执行操作tail(tail(L))的结果是 ( )（分数：2.00）A.(e,B.((e,) √C.(D.()解析：10.下列图示的顺序存储结构表示的二叉树是 ( )（分数：2.00）A. √B.C.D.解析：11.n个顶点的强连通图中至少含有 ( )（分数：2.00）A.n-1条有向边B.n条有向边√C.n(n-1)/2条有向边D.n(n-1)条有向边解析：12.对关键字序列(56,23,78,92,88,67,19,34)进行增量为3的一趟希尔排序的结果为( )（分数：2.00）A.(19,23,56,34,78,67,88,92)B.(23,56,78,66,88,92,19,34)C.(19,23,34,56,67,78,88,92)D.(19,23,67,56,34,78,92,88) √解析：13.若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为( )（分数：2.00）A.4B.5C.8 √D.9解析：14.由同一关键字集合构造的各棵二叉排序树 ( )（分数：2.00）A.其形态不一定相同，但平均查找长度相同B.其形态不一定相同，平均查找长度也不一定相同√C.其形态均相同，但平均查找长度不一定相同D.其形态均相同，平均查找长度也都相同解析：15.ISAM文件和VSAM文件的区别之一是 ( )（分数：2.00）A.前者是索引顺序文件，后者是索引非顺序文件B.前者只能进行顺序存取，后者只能进行随机存取C.前者建立静态索引结构，后者建立动态索引结构√D.前者的存储介质是磁盘，后者的存储介质不是磁盘解析：二、{{B}}填空题{{/B}}(总题数：10，分数：20.00)16.数据的逻辑结构在计算机存储器内的表示，称为数据的 1。

全国2005年10月高等教育自学考试全国统一命题考试数据结构试题课程代码：2331一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。

错选、多选或未选均无分。

1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上【】A. 操作的有限集合B. 映象的有限集合C. 类型的有限集合D. 关系的有限集合2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为【】A. n-i+1B. iC. i+1D. n-i3. 若不带头结点的单链表的头指针为head，则该链表为空的判定条件是【】A. head==NULLB. head->next==NULLC. head!=NULLD. head->next==head4. 引起循环队列队头位置发生变化的操作是【】A. 出队B. 入队C. 取队头元素D. 取队尾元素5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是【】A. 2，4，3，1，5，6B. 3，2，4，1，6，5C. 4，3，2，1，5，6D. 2，3，5，1，6，46. 字符串通常采用的两种存储方式是【】A. 散列存储和索引存储B. 索引存储和链式存储C. 顺序存储和链式存储D. 散列存储和顺序存储7. 设主串长为n，模式串长为m(m≤n)，则在匹配失败情况下，朴素匹配算法进行的无效位移次数为【】第 1 页共12 页A. mB. n-mC. n-m+1D. n8. 二维数组A［12］［18］采用列优先的存储方法，若每个元素各占3个存储单元，且第1个元素的地址为150，则元素A［9］［7］的地址为【】A. 429B. 432C. 435D. 4389. 对广义表L=((a,b),(c,d),(e,f))执行操作tail(tail(L))的结果是【】A. (e,f)B. ((e,f))C. (f)D. ( )10. 下列图示的顺序存储结构表示的二叉树是【】11. n个顶点的强连通图中至少含有【】A. n-1条有向边B. n条有向边C. n(n-1)/2条有向边D. n(n-1)条有向边12. 对关键字序列(56，23，78，92，88，67，19，34)进行增量为3的一趟希尔排序的结果为【】A. (19，23，56，34，78，67，88，92)B. (23，56，78，66，88，92，19，34)C. (19，23，34，56，67，78，88，92)D. (19，23，67，56，34，78，92，88)13. 若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为【】第 2 页共12 页A. 4B. 5C. 8D. 914. 由同一关键字集合构造的各棵二叉排序树【】A. 其形态不一定相同，但平均查找长度相同B. 其形态不一定相同，平均查找长度也不一定相同C. 其形态均相同，但平均查找长度不一定相同D. 其形态均相同，平均查找长度也都相同15. ISAM文件和VSAM文件的区别之一是【】A. 前者是索引顺序文件，后者是索引非顺序文件B. 前者只能进行顺序存取，后者只能进行随机存取C. 前者建立静态索引结构，后者建立动态索引结构D. 前者的存储介质是磁盘，后者的存储介质不是磁盘二、填空题(本大题共10小题，每空2分，共20分)16. 数据的逻辑结构在计算机存储器内的表示，称为数据的____________。

1. 下面程序段的执行次数为Afori=0;i＜n-1;i++forj=n;j＞i;j--state;A. nn+22 B .n-1n+22 C. nn+12 D. n-1n+22. 一个向量第一个元素的存储地址是100;每个元素的长度为2;则第5个元素的地址是 B A. 110 B .108 C. 100 D. 1203. 一个栈的入栈序列是a;b;c;d;e;则栈的不可能的输出序列是 C A. edcba B .decba C. dceab D. abcde4. 循环队列用数组A0;m－1存放其元素值;已知其头尾指针分别是front和rear;则当前队列中的元素个数是 DA. rear-front+m%m B .read-front+1C. read-front-1 D. read-front5．不带头结点的单链表head为空的判定条件是 A A. head=NULL B .head-next=NULLC. head-next=head D. head=NULL6．在一个单链表中;若p所指的结点不是最后结点;在p之后插入s所指结点;则执行BA.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;7. 从一个具有n个结点的单链表中查找其值等于x结点时;在查找成功的情况下;需平均比较多少个结点 D A. n B .n2 C. n-12 D. n+128．从一个栈顶指针为HS的链栈中删除一个结点时;用x保存被删结点的值;则执行 D A. x=HS;HS=HS-next;B .x=HS-data;C.HS=HS-next;x=HS-data;D. x=HS-data;HS=HS-next; 9．串是一种特殊的线性表;其特殊性体现在BA. 可以顺序存储 B .数据元素是一个字符C. 可以链接存储 D. 数据元素可以是多个字符11．二维数组M的元素是4个字符每个字符占一个存储单元组成的串;行下标i的范围从0到4;列下标j的范围从0到5;M按行存储时元素M35的起始地址与M按列存储时下列哪一元素的起始地址相同 B A. M24 B .M34 C. M35 D. M4412. 数组A中;每个元素A的长度为3个字节;行下标i从1到8;列下标j从1到10;从首地址SA 开始连续存放在存储器内;该数组按行存放时;元素A85的起始地址为 C A. SA+144B .SA+180 C. SA+222 D. SA+22513. 设高度为h的二叉树上只有度为0和度为2的结点;则此类二叉树中所包含的结点数至少为：B A. 2h B .2h-1 C. 2h+1 D. h+114. 已知某二叉树的后序遍历序列是dabec;中序遍历序列是debac;它的前序遍历序列是 D A. acbed B .decab C. deabc D. cedba15. 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历..这里;我们把由树转化得到的二叉树叫做这棵树对应的二叉树..下列结论哪个正确 A A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同B .树的后根遍历序列与其对应的二叉树的后序遍历序列相同C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同D. 以上都不对16. 具有6个顶点的无向图至少应有多少条边才能确保是一个连通图 AA. 5 B .6 C. 7 D. 817. 顺序查找法适合于存储结构为 B 的线性表 A. 散列存储B .顺序存储或链接存储C. 压缩存储 D. 索引存储18.采用顺序查找方法查找长度为n的线性表每个元素的平均查找长度为C A. n B .n2 C. n+12 D. n-1219. 有一个长度为12的有序表;按二分查找法对该表进行查找;在表内各元素等概率情况下查找成功所需的平均比较次数为 BA. 3512 B .3712 C. 3912 D. 431220.有一个有序表为{1;3;9;12;32;41;45;62;75;77;82;95;100};当二分查找值82为的结点时;几次比较后查找成功 C二、填空题每空1分;共20分1.在线性表的顺序存储中;元素之间的逻辑关系是通过物理存储位置;决定的；在线性表的链接存储中;元素之间的逻辑关系是通过链域的指针值决定的..2．对于一个具有N个结点的单链表;在已知的结点P后插入一个新结点的时间复杂度为O1;在给定值为X的结点后插入一个新结点的时间复杂度为ON.. 3.有一空桟;现有输入序列1;2;3;4;5;经push;push;pop;push;pop;push;push后;输出序列为2;3 ..4．在一个无向图中;所有顶点的度数之和等于所有边数的2 倍 5.对于一棵具有n个结点的树;该树中所有结点的度数之和为n-1..6. 在一棵三叉树中;度为3的结点数有2个;度为2的结点数有1个;度为1的结点数为2个;那么度为0的结点数有6个7.在霍夫曼编码中;若编码长度只允许小于等于4;则除了已对两个字符编码为0和10外;还可以最多对 4 个字符编码..8. 对于一个具有n个顶点和e条边的连通图;其生成树中的顶点数和边数分别为n 和n-1 ..9. 对20个记录进行归并排序时;共需要进行5 趟归并;在第三趟归并时是把长度为4 的有序表两两归并为长度为8 的有序表..三、问答题 1. 简述下面算法的功能栈和队列的元素类型均为intvoid algo3Queue &Q{Stack S; int d;InitStackS;whileQueueEmptyQ{DeQueueQ;d;PushS;d;}whileStackEmptyS{PopS;d; EnQueueQ;d;}}算法的功能：利用栈作辅助;将队列中的数据元素进行逆置2. 已知一棵二叉树的中序遍历序列和先序遍历序列为;试问能不能唯一确定一棵二叉树..若给定先序遍历序列和后序遍历序列;能不能唯一确定呢由中序遍历序列和先序遍历序列能唯一确定一棵二叉树..由先序遍历和后序遍历序列不能唯一确定一棵二叉树...一、选择题1. 下面程序段的执行次数为fori=0;i＜n-1;i++forj=n;j＞i;j--state;A. nn+22 B .n-1n+22 C. nn+12 D. n-1n+22. 判定一个栈ST最多元素为m0为空的条件是： A. ST-top0 B .ST-top＝0C. ST-topm0D. ST-top＝m03. 一个栈的入栈序列是a;b;c;d;e;则栈的不可能的输出序列是 A. edcba B .decba C. dceab D. abcde4. 在一个单链表中;若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．在一个链队中;假设f和r分别为队首和队尾指针;则删除一个结点的运算时 A. r=f-next;B .r=r-next; C. f=f-next;D. f=r-next;6．串是一种特殊的线性表;其特殊性体现在 A. 可以顺序存储 B .数据元素是一个字符 C. 可以链接存储 D. 数据元素可以是多个字符7. 稀疏矩阵一般的压缩方法有两种;即 A. 二维数组和三维数组 B .三元组和散列C. 三元组和十字链表D. 散列和十字链表8．将递归算法转换成对应的非递归算法时;通常需要使用 A. 栈 B .队列 C. 链表 D. 树9．二维数组M的元素是4个字符每个字符占一个存储单元组成的串;行下标i的范围从0到4;列下标j的范围从0到5;M按行存储时元素M35的起始地址与M按列存储时下列哪一元素的起始地址相同 A. M24 B .M34 C. M35 D. M4410. 数组A中;每个元素A的长度为3个字节;行下标i从1到8;列下标j从1到10;从首地址SA开始连续存放在存储器内;该数组按行存放时;元素A85的起始地址为 A. SA+144 B .SA+180 C. SA+222 D. SA+22511. 如果T2是由有序树T转换而来的二叉树;那么T中结点的后序就是T2中结点的 A. 前序 B .中序 C. 后序 D. 层次序12.一个有n个顶点的无向图最多有多少边 A. n B .nn-1 C. nn-12 D. 2n13.按照二叉树的定义;具有3个结点的二叉树有种A. 3 B .4 C. 5 D. 6 14.在一非空二叉树的中序遍历序列中;根结点的右边 A. 只有右子树上的所有结点 B .只有右子树上的部分结点 C. 只有左子树上的部分结点 D. 只有左子树上的所有结点15. 在一个图中;所有顶点的度数之和等于所有边数的多少倍 A. 12 B .1 C. 2 D. 416.采用邻接表存储的图的深度优先遍历算法类似于二叉树的 A. 先序遍历 B .中序遍历C. 后序遍历D. 按层遍历17.采用顺序查找方法查找长度为n的线性表每个元素的平均查找长度为 A. n B .n2C. n+12D. n-12二、填空题1. 算法的计算量的大小称为计算的___ _..2．数据结构是研究数据的和以及他们之间的相互关系;并对这种结构定义相应的运算;设计出相应的;而确保经过这些运算后所得的新结构是结构类型..3．在一个单链表中删除p结点;应执行下列操作：q=p-next;p-data=p-next-data;p-next= ;freeq;4.有一空桟;现有输入序列5;4;3;2;1;经push;push;pop;push;pop;push;push后;输出序列为..5．在双向链表中每个结点包含两个指针域;一个指向结点;另一个指向结点..6．一维数组的逻辑结构是;存储结构是.. 7.对于一棵含有40个结点的理想平衡树;它的高度为____ ..8.假定对长度n＝50的有序表进行折半搜索;则对应的判定树高度为;判定树中前5层的结点数为;最后一层的结点数为.. 9. 假定一组记录的排序码为46;79;56;38;40;80;对其进行归并排序的过程中;第二趟归并后的结果为____ ..10. 假定一组记录的排序码为46;79;56;38;40;80;对其进行快速排序的一次划分的结果为____..三、简答题 1.假定有四个元素A;B;C;D依次进栈;进栈过程中允许出栈;试写出所有可能的出栈序列 2.一棵含有n个结点的k叉树;可能达到的最大深度和最小深度各为多少 3. 设有5000个无序的元素;希望用最快速度挑选出其中前10个最大的元素;在以下的排序方法中;采用哪种方法最好为什么快速排序;堆排序;基数排序一、选择题1. B 2. B 3. C 4. B 5．C 6．B 9．C 10．A 11．B 12. C 13. B 14.C 15. C 16. A 17. C 18. A 19. C二、填空题1.复杂度2．物理结构; 逻辑结构;算法; 原来的3．q-next; 4. 4;3 5. 前驱; 后续6．线性结构; 顺序结构7. 5 8. 5 ; 31 ;19 .. 9. 38 46 56 7940 84 ..10. 84;79;56;38;40;46 ..三、问答题 1.答：共有14种可能的出栈序列为：ABCD; ABDC; ACBD; ACDB; BACD; ADCB; BADC; BCAD;BCDA;BDCA;CBAD;CBDA;CDBA;DCBA 2. 答：显然能达到最大深度的是单支树其深度为n；深度最小的是完全k叉树..3. 答：用堆排序最好;因为堆排序不需要等整个排序结束就可挑出前10个最大元素;而快速排序和基数排序都需等待整个排序结束才能知道前10个最大元素..1. 下面程序段的执行次数为Afori=0;i＜n-1;i++forj=n;j＞i;j--state;A. nn+22 B .n-1n+22 C. nn+12 D. n-1n+22. 一个向量第一个元素的存储地址是100;每个元素的长度为2;则第5个元素的地址是 B A. 110 B .108 C. 100 D. 1203. 一个栈的入栈序列是a;b;c;d;e;则栈的不可能的输出序列是 C A. edcba B .decba C. dceab D. abcde4. 循环队列用数组A0;m－1存放其元素值;已知其头尾指针分别是front和rear;则当前队列中的元素个数是 DA. rear-front+m%m B .read-front+1C. read-front-1 D. read-front5．不带头结点的单链表head为空的判定条件是 A A. head=NULL B .head-next=NULLC. head-next=head D. head=NULL6．在一个单链表中;若p所指的结点不是最后结点;在p之后插入s所指结点;则执行BA.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;7. 从一个具有n个结点的单链表中查找其值等于x结点时;在查找成功的情况下;需平均比较多少个结点 D A. n B .n2 C. n-12 D. n+128．从一个栈顶指针为HS的链栈中删除一个结点时;用x保存被删结点的值;则执行 D A. x=HS;HS=HS-next;B .x=HS-data;C.HS=HS-next;x=HS-data;D. x=HS-data;HS=HS-next; 9．串是一种特殊的线性表;其特殊性体现在BA. 可以顺序存储 B .数据元素是一个字符C. 可以链接存储 D. 数据元素可以是多个字符11．二维数组M的元素是4个字符每个字符占一个存储单元组成的串;行下标i的范围从0到4;列下标j的范围从0到5;M按行存储时元素M35的起始地址与M按列存储时下列哪一元素的起始地址相同 B A. M24 B .M34 C. M35 D. M4412. 数组A中;每个元素A的长度为3个字节;行下标i从1到8;列下标j从1到10;从首地址SA 开始连续存放在存储器内;该数组按行存放时;元素A85的起始地址为 C A. SA+144B .SA+180 C. SA+222 D. SA+22513. 设高度为h的二叉树上只有度为0和度为2的结点;则此类二叉树中所包含的结点数至少为：B A. 2h B .2h-1 C. 2h+1 D. h+114. 已知某二叉树的后序遍历序列是dabec;中序遍历序列是debac;它的前序遍历序列是 D A. acbed B .decab C. deabc D. cedba15. 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历..这里;我们把由树转化得到的二叉树叫做这棵树对应的二叉树..下列结论哪个正确 A A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同B .树的后根遍历序列与其对应的二叉树的后序遍历序列相同C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同D. 以上都不对16. 具有6个顶点的无向图至少应有多少条边才能确保是一个连通图 AA. 5 B .6 C. 7 D. 817. 顺序查找法适合于存储结构为 B 的线性表 A. 散列存储B .顺序存储或链接存储C. 压缩存储 D. 索引存储18.采用顺序查找方法查找长度为n的线性表每个元素的平均查找长度为C A. n B .n2 C. n+12 D. n-1219. 有一个长度为12的有序表;按二分查找法对该表进行查找;在表内各元素等概率情况下查找成功所需的平均比较次数为 BA. 3512 B .3712 C. 3912 D. 431220.有一个有序表为{1;3;9;12;32;41;45;62;75;77;82;95;100};当二分查找值82为的结点时;几次比较后查找成功 C二、填空题每空1分;共20分1.在线性表的顺序存储中;元素之间的逻辑关系是通过物理存储位置;决定的；在线性表的链接存储中;元素之间的逻辑关系是通过链域的指针值决定的..2．对于一个具有N个结点的单链表;在已知的结点P后插入一个新结点的时间复杂度为O1;在给定值为X的结点后插入一个新结点的时间复杂度为ON.. 3.有一空桟;现有输入序列1;2;3;4;5;经push;push;pop;push;pop;push;push后;输出序列为2;3 ..4．在一个无向图中;所有顶点的度数之和等于所有边数的2 倍 5.对于一棵具有n个结点的树;该树中所有结点的度数之和为n-1..6. 在一棵三叉树中;度为3的结点数有2个;度为2的结点数有1个;度为1的结点数为2个;那么度为0的结点数有6个7.在霍夫曼编码中;若编码长度只允许小于等于4;则除了已对两个字符编码为0和10外;还可以最多对 4 个字符编码..8. 对于一个具有n个顶点和e条边的连通图;其生成树中的顶点数和边数分别为n 和n-1 ..9. 对20个记录进行归并排序时;共需要进行5 趟归并;在第三趟归并时是把长度为4 的有序表两两归并为长度为8 的有序表..三、问答题 1. 简述下面算法的功能栈和队列的元素类型均为intvoid algo3Queue &Q{Stack S; int d;InitStackS;whileQueueEmptyQ{DeQueueQ;d;PushS;d;}whileStackEmptyS{PopS;d; EnQueueQ;d;}}算法的功能：利用栈作辅助;将队列中的数据元素进行逆置2. 已知一棵二叉树的中序遍历序列和先序遍历序列为;试问能不能唯一确定一棵二叉树..若给定先序遍历序列和后序遍历序列;能不能唯一确定呢由中序遍历序列和先序遍历序列能唯一确定一棵二叉树..由先序遍历和后序遍历序列不能唯一确定一棵二叉树...一、选择题1. 下面程序段的执行次数为fori=0;i＜n-1;i++forj=n;j＞i;j--state;A. nn+22 B .n-1n+22 C. nn+12 D. n-1n+22. 判定一个栈ST最多元素为m0为空的条件是： A. ST-top0 B .ST-top＝0C. ST-topm0D. ST-top＝m03. 一个栈的入栈序列是a;b;c;d;e;则栈的不可能的输出序列是 A. edcba B .decba C. dceab D. abcde4. 在一个单链表中;若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．在一个链队中;假设f和r分别为队首和队尾指针;则删除一个结点的运算时 A. r=f-next;B .r=r-next; C. f=f-next;D. f=r-next;6．串是一种特殊的线性表;其特殊性体现在 A. 可以顺序存储 B .数据元素是一个字符 C. 可以链接存储 D. 数据元素可以是多个字符7. 稀疏矩阵一般的压缩方法有两种;即 A. 二维数组和三维数组 B .三元组和散列C. 三元组和十字链表D. 散列和十字链表8．将递归算法转换成对应的非递归算法时;通常需要使用 A. 栈 B .队列 C. 链表 D. 树9．二维数组M的元素是4个字符每个字符占一个存储单元组成的串;行下标i的范围从0到4;列下标j的范围从0到5;M按行存储时元素M35的起始地址与M按列存储时下列哪一元素的起始地址相同 A. M24 B .M34 C. M35 D. M4410. 数组A中;每个元素A的长度为3个字节;行下标i从1到8;列下标j从1到10;从首地址SA开始连续存放在存储器内;该数组按行存放时;元素A85的起始地址为 A. SA+144 B .SA+180 C. SA+222 D. SA+22511. 如果T2是由有序树T转换而来的二叉树;那么T中结点的后序就是T2中结点的 A. 前序 B .中序 C. 后序 D. 层次序12.一个有n个顶点的无向图最多有多少边 A. n B .nn-1 C. nn-12 D. 2n13.按照二叉树的定义;具有3个结点的二叉树有种A. 3 B .4 C. 5 D. 6 14.在一非空二叉树的中序遍历序列中;根结点的右边 A. 只有右子树上的所有结点 B .只有右子树上的部分结点 C. 只有左子树上的部分结点 D. 只有左子树上的所有结点15. 在一个图中;所有顶点的度数之和等于所有边数的多少倍 A. 12 B .1 C. 2 D. 416.采用邻接表存储的图的深度优先遍历算法类似于二叉树的 A. 先序遍历 B .中序遍历C. 后序遍历D. 按层遍历17.采用顺序查找方法查找长度为n的线性表每个元素的平均查找长度为 A. n B .n2C. n+12D. n-12二、填空题1. 算法的计算量的大小称为计算的___ _..2．数据结构是研究数据的和以及他们之间的相互关系;并对这种结构定义相应的运算;设计出相应的;而确保经过这些运算后所得的新结构是结构类型..3．在一个单链表中删除p结点;应执行下列操作：q=p-next;p-data=p-next-data;p-next= ;freeq;4.有一空桟;现有输入序列5;4;3;2;1;经push;push;pop;push;pop;push;push后;输出序列为..5．在双向链表中每个结点包含两个指针域;一个指向结点;另一个指向结点..6．一维数组的逻辑结构是;存储结构是.. 7.对于一棵含有40个结点的理想平衡树;它的高度为____ ..8.假定对长度n＝50的有序表进行折半搜索;则对应的判定树高度为;判定树中前5层的结点数为;最后一层的结点数为.. 9. 假定一组记录的排序码为46;79;56;38;40;80;对其进行归并排序的过程中;第二趟归并后的结果为____ ..10. 假定一组记录的排序码为46;79;56;38;40;80;对其进行快速排序的一次划分的结果为____..三、简答题 1.假定有四个元素A;B;C;D依次进栈;进栈过程中允许出栈;试写出所有可能的出栈序列 2.一棵含有n个结点的k叉树;可能达到的最大深度和最小深度各为多少 3. 设有5000个无序的元素;希望用最快速度挑选出其中前10个最大的元素;在以下的排序方法中;采用哪种方法最好为什么快速排序;堆排序;基数排序一、选择题1. B 2. B 3. C 4. B 5．C 6．B 9．C 10．A 11．B 12. C 13. B 14.C 15. C 16. A 17. C 18. A 19. C二、填空题1.复杂度2．物理结构; 逻辑结构;算法; 原来的3．q-next; 4. 4;3 5. 前驱; 后续6．线性结构; 顺序结构7. 5 8. 5 ; 31 ;19 .. 9. 38 46 56 7940 84 ..10. 84;79;56;38;40;46 ..三、问答题 1.答：共有14种可能的出栈序列为：ABCD; ABDC; ACBD; ACDB; BACD; ADCB; BADC; BCAD;BCDA;BDCA;CBAD;CBDA;CDBA;DCBA 2. 答：显然能达到最大深度的是单支树其深度为n；深度最小的是完全k叉树..3. 答：用堆排序最好;因为堆排序不需要等整个排序结束就可挑出前10个最大元素;而快速排序和基数排序都需等待整个排序结束才能知道前10个最大元素..。

浙江工商大学2006/2007学年第一学期考试试卷课程名称：《数据结构》考试方式：闭卷完成时限：120分钟班级名称：学号：姓名：题号一二三四五六总分分值10 10 10 14 20 36 100得分阅卷人一.判断题（每题1分，共10分）1、数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面。

................................()2、数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储结构相关，是依赖于计算机的。

................................()3、线性表中的每个结点最多只有一个直接前驱和一个直接后继。

..................................................()4、线性的数据结构可以顺序存储，也可以链接存储。

非线性的数据结构只能链接存储。

........................................()5、二维数组是其数组元素为线性表的线性表。

................()6、单链表形式的队列，头指针F指向队列的第一个结点，尾指针R指向队列的最后一个结点。

..................................()7、由一棵二叉树的前序序列和后序序列可以唯一确定它。

......(错)8、在数据的存放无规律而言的线性表中进行查找的最佳方法是顺序查找（线性查找）。

......................................()9、多重表文件和倒排文件都归属于多关键字文件。

............()10、不定长文件是指文件的长度不固定。

..................... ()二.填空题（每题1分，共10分）1、若将数据结构形式定义为二元组(D，R)，其中D是数据元素的有限集合，则R是D上关系的有限集合。

2、在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为。

武汉大学
2005年攻读硕士学位研究生入学考试试题
考试科目：结构力学
注明：所有的答题内容必须在答题纸上，凡答在试题上的一律无效
一、试对图1、图2所示体系进行几何组成分析。

（共2小题，每小题6分，共12分）
二、作图3所示刚架的内力图。

（25分）
三、求图4、图5所示结构指定杆件的内力。

（共3问，每问7分，共21分）
图1图2
图3图4图5
四、作图6、图7所示结构的弯矩图，E为常量。

（共2小题，每小题25分，共50分。

）
图6 图7
五、用矩阵位移法计算图8所示桁架，求①杆内力。

EA为常量。

（18分）
六、求图9所示结构的自振频率。

（12分）
图8 图9 七、求图10所示移动荷载作用下梁的支座反力R Bmax。

（12分）。