数据结构考试题目及答案

1、数据结构试题6一、单项选择题(每小题3分，共30分) TOC o 1-5 h z 设栈的输入序列是1、2、3、4，贝U 不可能是其出栈序列。()A 1234B 2134C 1432D 4312在一个具有n个结点的线性链表中查找某个结点，若查找成功，需要平均比较 个结点。()A nB n/2C (n+1)/2D (n-1)/2设每个字符占一个字节，二维数组A中每个元素有6个字符组成，其行下标从0到9,列下标从0到3,元素 当A按行优先存储起始地址与当A按列优先存储的起始地址相同。()A A30B A31C A3 皿D A 23 具有2000个结点的非空二叉树的最小深度为。()A 9B 10C 1

2、1D 12 已知某二叉树的后根序列是dabec，中根序列是debac，则先根序列是。()A acbed B decab C deabc D cedba无向图中所有边的数目等于所有顶点的度数之和的 倍。()A 1B 2C 1/2D不一定 递归函数F(n)=F(n-1)+n+1(n1)的递归体是。()A F(0)=0B F(1)=1C F(n)=n+1D F(n)=F(n-1)+n+1若需要在O(nlog2n)的时间内完成对n个元素的排序，且要求排序是稳定的,则可选择的排序方法是。()A快速排序 B堆排序 C归并排序 D直接插入排序在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是_。()

3、A O(1)B O(log2n)C O(n)D O(n log2n)假定有K个关键字互为同义词，若用线性探查法把这K个关键字存入散列表中，则总的探查次数至少为。()A K-1B KC K+1D K (K+1) /22二、填空题(每小题2分，共20分)对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为，在表尾插入元素的时间复杂度为。在一棵二叉树中，第5层(根结点为1层)上的结点数最多为。一棵高度为h的理想平衡树中，最少含有 个结点，最多含有个结点。在一个小根堆中，堆顶结点的值是所有结点中的，在一个大根堆中， 堆顶结点的值是所有结点中的。在一个具有n个顶点的无向图中，要连通所有顶点则

4、至少需要 条边。假定一个图具有n个顶点和e条边，贝采用邻接矩阵、邻接表表示时，其相应的空间复杂度分别为 和。7 .以二分查找方法查找一个线性表时，此线性表必须是 存储的 表。 在线性表的散列存储中，处理冲突有 和 两种方法。 快速排序在平均情况下的空间复杂度为，在最坏情况下的空间复杂度为在一棵20阶B_树中，每个非树根结点的关键字数目最少为 个，最多为。三、判断题（认为对的，在题后的括号内打“”错的打“X”，每小题1分， 共1。） TOC o 1-5 h z 线性表中，每个结点都有一个前驱和一个后继。（） 有向图的邻接表和逆邻接表中的结点数一定相同。（）单链表中要取得某个元素，只要知道该元素的

5、指针即可，因此单链表是随机存取的存储结构。（）在快速排序、归并排序和shell排序中，稳定的是shell排序。（）对不同的存储结构，检索的方法不同。（）在散列表中，负载因子值越小则存元素时发生冲突的可能性就越大。（）由于二叉树中每个结点的度最大为2,所以二叉树是一种特殊的树。（）若一棵二叉树的树叶是某子树对称序周游序列中的第一个结点，则它必是该子树后序周游序列中的第一个结点。（）二叉树按线索化后，任一结点均有指向其前驱和后继的线索。（） 在采用线性探查法处理冲突的散列表中，所有同义词在表中相邻。（）四、简答题（每题10分，共60分）说明数组和链表的区别，各有何优缺点？回答下列关于堆的一些问题：

6、（1）堆的定义是什么？（2）存储表示是顺序的，还是链式的？（3）设有一个最小堆，其具有最小值、最大值的元素分别可能在什么地方？完全二叉树用什么数据结构实现最合适，为什么？在直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序 和归并排序中，哪些易于在链表（包括各种单、双、循环链表）上实现？用下列三种表示法画出下图G的存储结构（1）相邻矩阵（2）邻接表（3） 邻接多重表一6.已知序列（70，83，100，65，10，32，7），请给出采用插入排序法对该 序列作升序排序时的每一趟结果。五、算法设计题（每题15分，共30分）说明：可以使用任何高级程序设计语言或伪（类）程序设计语言。已知非

7、空单链表第一个结点由list指出，写一算法，交换p所指结点（不 是链表中第一个结点，也不是链表中最后的那个结点）与其下一个结点在链 表中的位置，并给出算法的时间复杂度。设计一个算法，统计一个采用邻接矩阵存储、具有n个顶点的无向无权图所 有顶点的度。数据结构试题6答案一、1. D 2. C 3.B 4. C 5.D 6.C 7.D 8. C 9.A 10. D二、1. O (n) O (1)2. 163. 2h 12 h 14.最小值 最大值5. n 一 16. O (n 2 ) O (n十e)、顺序有序8.开放定址法链接法(次序无先后)9. O (1og2n)O (n)10. 919三、1.X

8、2.” 3.X 4.X5.” 6.X7.X8.” 9.X10.X四、1.区别：数组占用连续的内存空间，链表不要求结点的空间连续。各有何优缺点：(1)插入和删除操作。数组插入和删除需移动数据元素，链 表插入和删除不移动数据元素，链表比数组易于实现插入和删除操作；在空间占用方面，数组优于链表；在数据存取方面，数组是随机存取方式，而2链表是顺序存取方式。(1)堆是n个元素的有限序列K1，K2，KN，且满足以下条件：Ki= K2i 且 Ki = K21 且 Ki=膈1IT,2，,n/2 (最大堆)因为完全二叉树采用顺序存储更加有效，所以堆应采用顺序存储结构。最小堆的最小值元素必在堆顶，最大值的元素只有

9、在叶结点上。完全二叉树用一维数组实现最合适。(1)不存在空间浪费问题；(2)顺序存 储方式下，父子结点之间的关系可用公式描述，访问结点方便。采用链表存 储存在空间浪费问题，且不易寻找父结点。在上述排序方法中，只有直接插入排序、冒泡排序、直接选择排序易于在链表上实现。相邻矩阵：0 111A= 101111001100邻接表：VIV2V3V42111332A2A4A4A邻接多重表:6.初始第1趟 第2趟 第3趟 第4趟第5趟第6趟VIV2V3V4(70), 83,(70(70(65(10(10(0783)8370653210100,100,100),8370653265,65,65,12N：!N4

10、13N：；N414ANf23Nf24AA,N4N510,10,10,10,N1N2N332,32,32,32,32,100),100), 83,100), 70,83,837065070707070707100)五、算法的ADL描述如下：算法 CHANGE(list,p)qlistWHILE(next(q)p) DOqnext(q)rnext(p)next(q)rnext(p)next(r) next(r)p算法的时间复杂度为O(n)顶点的度保存在一维数组A中。2.假设邻接矩阵为adjacency (二维数组)， 算法的ADL描述如下：初始化FOR i=1 TO n DOAi0FOR i=1

11、TO n DOFOR j=1 TO n DOIF adjacencyi,j=1 THENAiAi+1数据结构试题7一、单项选择题(每小题2分，共20分)D.DECAB序列A,B,C,D,E顺序入栈,不能获得的序列是:(A. ABCDE B. CDEBA C. EDCBA通常算法分析中算法的空间复杂度是指:()A.所需全部空间大小B.完成运算所需辅助空间大小C.待处理数据所需全部空间大小D. 存储空间的复杂程度Huffman 树是:（）A.最佳二叉树B.路径长度最短的二叉树C,最佳二叉排序树D,加权路径长度最短的二叉树在单链表中删除P指针废的节点Q需要修改的指针域个数为:（）A. 2B. 4C.

12、 6D. 1设n0,n1,n2分别是二叉树中度为0,1,2的结点数,则有:（）A. n0=n2+1B. n0=n2-1C. n0=n1+1D. n0=n1-1下列说法中错误的是：（）A. n个结点的树的各结点度数之和为n-1 B. n个结点的有向图最多有n*（n-1）条边 C.用相邻矩阵存储图时所需存储空间大小与图中边数有关D.散列表中碰撞的可能性大小 与负载因子有关若线性表采用顺序存储结构，每个元素占用4个存储单元，第一个元素的存储地址 为100,则第12个元素的存储地址是：（）A. 113B. 144 C. 148 D. 412下列哪一种排序方法的比较次数与纪录的初始排列状态无关？（）A.

13、直接插入排序B.起泡排序C.快速排序D.直接选择排序设有5000个无序的元素，希望用最快的速度挑选出其中前50个最大的元素，最好选用:（） A.冒泡排序B.快速排序C.堆排序D.基数排序用某种排序方法对序列（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，84A.选择排序B.希尔排序C.归并排序D.快速排序二、判断题（每小题1分，共10分，对的打J,错的打X）给出不

14、同输入序列建造二叉排序树，一定得到不同二叉排序树。（）有向图的邻接表和逆邻接表中的结点数一定相同。（）图G的拓扑序列唯一，则其弧数必为n-1（其中n为G的顶点数）。（）在索引顺序文件中插入新的记录时，必须复制整个文件。（）如果某种排序算法是不稳定的，则该方法没有实际的应用价值。（）对n个记录进行冒泡排序，在最坏情况下所需要的时间是O（n 2 ）（）在线性结构中，每个结点都有一个直接前驱和一个直接后继。（）AVL树的任何子树都是AVL树。（）B +树既适于随机检索，也适于顺序检索。（）两个字符串相等的充要条件是两个串包含的字符相同。（）三、填空题（每空1分，共15分） 用起泡法对n个关键码排序，

15、在最好情况下，只需做_次比较和 次移动；在 最坏的情况下要做 次比较。若按层次顺序将一棵有n个结点的完全二叉树的所有结点从1到n编号，那么当i为 且大于1时，结点I的左兄弟是结点，否则结点i没有左兄弟。 具有N个结点的完全二叉树的深度为。树的三种主要的遍历方法是： 、 和层次遍历。 采用散列技术实现散列表时，需要考虑的两个主要问题是：和解决。在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用 p 表示为 head=。 栈顶的位置是随着、操作而变化的。 已知一棵完全二叉树中共有768结点，则该树中共有个叶子结点。四、简答题(第1、2题每小题6分，第3、4、5题每

16、小题8分，共36分)1.已知一个无向图的顶点集为a, b, c, d, e，其邻接矩阵如下图1所示画出该图的图形；根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历，写出相应的遍历序列。0 10 0 1 TOC o 1-5 h z 1001()0 ()0110 1I0II )1I)_(图1)将上图2所示的二叉树转换为树或树林3：设有一组关键码序列：6097,3485,8129,407,8136,6615,6617,526,12287,9535,9173,2134,1903,99和散列函数：H(key)=key MOD 19。采用线性探测法解决冲突，试在018的散列地址 空间中对该关键码序列

17、构造散列表。设有关键码集合K=72，73，71，23，94，16，05，68，将其建成一个堆(画出每步 所得的图即可)。从一棵空的AVL树开始，将关键码xal,wan,wil,zol,yo,xum逐个插入，画出每插入一个 关键码后得到的AVL树。五、算法设计(19分)用类PASCAL语言或类C语言写出将n个记录用冒泡排序法进行升序排序的算法(第 一次冒泡将排序码最小的记录放在第一个位置，第二次冒泡将排序码次最小的记录放在第 二个位置)。数据结构试题7答案1. D 2. A 3. D 4. D 5. A6. C 7. B 8. D 9. C 10. D1.X 2. J 3. J 4. X5. X

18、 6.J 7. X 8.J 9.X 10. X1. n-1 0 n(n-1)/22. 奇数 i-13. log2N+14. 先根后根5.选取好的散列函数冲突(碰撞)6. P f .next f .next 7.进栈 退栈8. 3841.2、深度：a,b,d,e,c 广度：a,b,e,d,c3、21343月占407099173坦90 1 2 3456789 10 1112 13 14 15 16 1718五、TYPE node=RECORDkey:integer;info:datatypeEND;FOR i:=1 TO n DOVAR i,j:integer;flag:0.1;X:node;R:

19、arrar1.n of node;Beginflag:=0;FOR j:=n-1 TO I DOif Rj+1.keyRj.keythen beginflag:=1;X:=Rj;Rj:=Rj+1;Rj+1:=X End;if flagthen算法结束End数据结构试题8一.单项选择题(每小题1分,15分)编号为A,B,C,D的四辆列车，顺序开进栈式结构的站台，则开出车站的顺序中，不可能出 TOC o 1-5 h z 现的次序为:()A. BDAC B. CBAD C. ACBD D. DCBA两个同义词子表结合在一起的现象称为:()A.碰撞B.拉链C,链接D.堆积一棵二叉树若前序和对称序周游得

20、到的节点序列相同,则这棵二叉树满足：()A.只能是一个节点的二叉树B.为空二叉树或者该树所有节点的左子树为空二叉树C.只能是空二叉树D.为空二叉树或者该树所有节点的右子树为空二叉树一棵深度为m的满三叉树定义为:或者是空三叉树，或者是第m层有3 1 ? m个叶节点，其余 各层的节点均有三棵(左，中，右)非空子三叉树.对该树按层自左向右从1开始顺序编号, 则编号为n的节点，其父节点若存在，则父节点编号为:()5.有n个节点的有向完全图的边数为:()A. nB. n(n-1) C. 2nD. n(n-1)/2 TOC o 1-5 h z 广义表 L=(),(),(),()的长度为:()A. 3B.

21、0C. 4D. 5设H(key)为散列函数,key为记录的关键字.在散列表中，记录R1和R2的关键字分别为key 1和key 2，称他们为同义词的条件是:()A. key 1 =key 2 B. key 1 =key 2 且 H(key 1 )=(key 2 )C. R1=R2 D. key 1 尹 key 2 且 H(key 1 )=(key 2 )下面那一个不是存储管理考虑的问题:()A.压缩碎片问题B.无用节点收集C.表节点的顺序D.空间溢出管理不能存储二叉树的存储结构为:()A.三叉链表B.散列表C.顺序表D.二叉链表2AVL数不平衡后要调整的情形有:()A. 2种B. 4种C. 6种

22、D. 8种在排序过程序中,使用辅助存储空间为O (n)的算法是:()A.插入排序B.归并排序C.起泡排序D.快速排序 若无向图中有n个结点,e条边,则它的邻接表需要表节点数目为:()A. 2eB. 2e+nC. 2e+1D.e+2n 字符串的紧缩存储形式是每个字符占:()A. 1个二进制位B. 1个字节C. 1个字D. 1个结点单元 循环队列SQ有m个单元，其满队条件是:()A. (SQ.rear+1) MOD M=SQ.frontB. SQ.rear=SQ.frontC. SQ.rear=mD. SQ.front=m 通常算法分析中算法的空间复杂度是指:()A.所需全部空间大小C.完成运算所

23、需辅助空间大小B.待处理数据所需全部空间大小D. 存储空间的复杂程度填空题(每空1分，共10分)数据结构中的节点可分为两大类:和. 结构的 是指数据本身所占存储量/整个结构所占存储量.散列存储方法的关键问题是和.一棵树删去根节点就变.用二分检索法进行检索时，要求节点事先.设图G有n个节点,t条边，若d i为节点v i的度数，则t=.对于不连通的无向图和不是强连通的有向图进行周游，得到的是:.排序方法的稳定性是指排序关键字值相同的记录在排序过程中不改变其原有的 关系.多项选择题(错选，多选，漏选均不得分.每小题2分，共6分)根据描述算法的语言不同，可将算法分为：()A.形式算法B.非形式算法C.

24、伪语言算法3 D.运行不终止的程序可执行部分E.运行终 止的程序可执行部分 能够从任意节点出发访问到其余结点的结构有:()A.单链表B.循环链表C.双链表D.二叉链表E.邻接表图的常见存储结构可以选取:()A.邻接表B.邻接矩阵C.逆邻接表D.邻接多重表E.散列表简答题(每小题4分，共12分)快速排序算法是否稳定?举一个具有六个记录(只考虑排序码)的例子予以说明.穿线树的最大优点是什么？简述关键码和排序码的概念.五.分析计算题(每小题7分，共21分)计算如下程序段的时间复杂度.s:=0;FOR i:=1 TO n DO BEGINt:=1;WHILE trmid.key THEN 3ELSE

25、4END;Binfind:=y;END;修改起泡排序算法，反方向进行扫描,即第一趟把排序码最小的记录放到最前头，第二趟把 排序码次小的放到第二个位置，第三趟把排序码第三小的放到第三个位置，如此反复进行. 用类pascal语言给出该算法的程序.(类型说明与上面第3小题相同)试编写一个交换二叉树T中节点的左右子树的类PASCAL语言算法，设节点的类型为:TYPE bitree=Anode;Node=RECORDData:datatype;Lchild,rchild:bitreeEND;数据结构试题8答案一、1、A2、D3、B 4、C 5、B 6、A7、D8、C 9、B10、B 11、B12、B 1

26、3、B 14、A 15、A二、1、初等，组合2、存储密度3、散列函数的选取，冲突(碰撞)的解决4、树(森)林5、按关键码排序6、1/2E di 7、生成树林8、相对位置三、1、B C E2、B C3、A B C D四、1、快速排序是不稳定的 如对初始类排序码：81 2 5 82 4 1经第一趟快排后为:12582 481经第二趟快排后为:12 582 481经第三趟快排后为：12582 481经第四趟快排后为：1245828181和82相对位置发生了变化2、由于有了线索的存在而使的周游树形结构和找结点在指定次序下的前驱、后继的算法变 得很简单、直截了当。3、关键码是其值能唯一确定一个记录的字段

27、或字段组合，两个记录的关键码不可能相等排 序码是排序运算的依据，是结构中的一个或多个字段，两个记录的排序码可以相同五、1、I=1时WHILE循环执行1次故总排序时间为：Z log 2(i+1)=Z log 2iI=2时 WHILE循环执行2次en log 2 nI=3时 WHILE循环执行2次I=4时 WHILE循环执行3次I=5, 6, 7时 WHILE循环执行3次I=8时 WHILE循环执行4次2、k=n+(n-1)+(n-2)+n-(i-2)+(j-i+1)=n(i-1)-i+2+(i-1)+j=ni-n-(i+1)(i+2)/2+j=i 2 +(2n+3)i/2+j-(n+1)所以 f

28、1(i)=i 2 +(2n+3)i/2 ; f2(j)=j ; c=-(n+1)3、Apr, Aug, Dec, Feb, Jan, Jul, Jun, Mar, May Nov, Oct, Sep3次 4次2次3次4次1次3次 4次2次 4次 3次 4次 检索次数平均查找长度为：1/12 (1+2*2+3*4+4*5) =37/12深度遍历结果为：1，2，3，5, 4，6，7，83、 1、Y=02、Low W High3、Low： =Mid+14、High： =Mid-14、VAR R： table;X:node;j:integer;flag:0.1;循环，i以-1为步长，从1至U n-1,

29、执行(n-1次冒泡)(1) flag - 0(2)循环,j以-1为步长，从n到i+1执行若 Rj.keyVRj-1.key则 flagV-1x - Rj；Rj一 Rj-1；Rj-1 x(3)若flag=0则跳出循环算法结束5、Procedure exchange_lr_node(t:bitree);beginif t=nilthen算法结束else beginq - t f .lchild;t f .lchild。t f .rchild;t f .rchild-q;exchange_lr_node(t f.lchild);exchange_lr_node(t f .rchild)end;end

30、;数据结构试题9一.单项选择题(每小题1分,15分) TOC o 1-5 h z 作为一个算法必须满足:()A. 2个要素B. 4个要素C. 5个要素D. 7个要素双链表中，删除节点P之后的节点Q需要修改的指针域的个数为:()1B. 2C. 3D. 4队列是一种:()A.链表B. LIFO表C.顺序表D. FIFO表串的求子串运算SUBSTR( ABCDEF ,2,3)的引用结果是:()A.BCD B. BC C. CDE D. CD5.循环队列SQ有m个单元，其满队条件是:()A. SQ.rear=SQ.frontC. SQ.rear MOD M+1=SQ.front B. SQ.rear+

31、1=SQ.frontD. SQ.rear =SQ.front MOD M+16.在列主序下顺序的存储数组A 4 * 4的上三角元素A(3,2)的位置是第:()A. 10 个 B. 7 个 C. 6 个 D. 5 个7.广义表D=(a,D)的深度为:()A. 2B. 1C. +D.-8.有三个节点A,B,C可以构成多少种二叉树:()A. 5B. 8C. 32D. 30有n个节点的完全二叉树，其深度为：()D. log n +1A. log. +1J B. logn n C. log n 中序序列和后序序列相同的二叉树是()完全二叉树B,满二叉树C,所有结点无左孩子的二叉树D,所有结点无右孩子的二

32、叉树若有向图中有n个结点,e条边,则它的邻接表需要表节点数目为：()A. e TOC o 1-5 h z 2eC. e-1D.e+1 克鲁斯卡尔(KRUSKAL)算法求最小生成树，是针对那种图的:()A.无向图B.有向图C,连通无向图D.连通带权图在排序过程中，使用辅助空间为O(n)的算法是:()A,插入法B,归并法C.快速D,分配 在散列结构中,同义词是指:()R1.KEY尹R2.KEY 且 HASH(RI.KEY)=HASH(R2.KEY)R1.KEY=R2.KEYR1.KEY=R2.KEY 且 HASH(RI.KEY)=HASH(R2.KEY)R1.DATA=R2.DATA 15.ISA

33、M 文件属于:()A.顺序文件B.散列文件C.索引文件D.多关键字文件多项选择题(错选，多选，漏选均不得分.每小题1分，共5分)在下列算法中，涉及到栈运算的有:()A.二叉树的遍历B.广度优先搜索遍历C.深度优先搜索遍历D.表达式求值E.基数排序排序算法在最坏执行情况下，算法的时间复杂度是O(n 2 )的有:()冬插入排序法B.块序排序法C.堆排序法D.归并排序法E.基数排序法稀疏矩阵通常采用的存储方式有:()A.单链表B.循环链表C.三元组表D.散列表E.十字链表根据排序期间数据规模的大小及数据所处存储器的不同，可以将排序分为:()A.插入排序B.希尔排序C.交换排序D.内部排序E.外部排序

34、 能够从任一节点访问到其余节点的结构有:()A.单链表B.循环链表C.双链表D.二叉链表E.邻接表填空题(每空1分，共10分)数据的基本存储结构有，四种.排序方法的稳定性是值排序关键字值相同的记录在排序过程中不改变其原有的 关系. TOC o 1-5 h z 算法的确定性是指每条.散列结构中处理冲突的方法基本上可分为两大类:和.文件的操作主要有:和 两类.判断改错题(对的打”J”，错的打”X”，并说明理由.每小题2分，判断和说明各得1分， 判断3错误，全题无分.共10分)1.二叉树是度为2的树.()2.堆排序是不稳定的，其时间复杂度为O(n log 2 n).()队列是受限的线性表，限制在于节

35、点的位置相对固定.()要完成树的层次遍历一般要利用栈作为辅助结构.()图的最小生成树如果存在,则一般唯一.()解释概念题(每小题3分，共9分)1.三元组表2.拓扑排序3.AVL树简答题(共31分)1.把下图森林转化为一棵二叉树，并画出主要转化过程图示.(4分)给定权集W=2,3,4,7,8，试构造关于W的一棵哈夫曼树,并求其加权路径长度WPL的 值.（6分）对于下图给出其邻接表，并从顶点1出发依据存储结构进行广度遍历，写出遍历结果.有一棵二叉树其前序序列为ABCDEF,中序序列为BCAEDF,画出此二叉树的示意图,并 给出其后序序列的线索树.（6分）对于关键字集合51,28,36,86,7，请

36、建立一个堆，要求画出堆形成的示意图.（6分）在双链表H中,现在要在节点P之后插入一个节点Q,请写出插入动作的具体语句.（4分） 七.算法设计（共20分）数组A1.m作为循环队列的存储区域,试编写一个出队的类PASCAL语言算法.（6分）利用类pascal语言写出统计二叉树中节点个数的算法（6分）.3.利用类pascal语言 写出快速排序中一趟块排的算法（8分）.数据结构试题9答案一、1、C2、B3、D4、A 5、D 6、B7、C8、D9、A 10、D 11、A 12、D13、B 14、A 15、C二、1、A C D2、A B 3、A C D E4、D E 5、B C三、1、顺序，链接，索引，散

37、列2、相对位置3、指令必须有确切含义，无歧义性4、开地址法, 拉链法5、修改，检索四、1、X 2、J 3、X 4、X 5、X五、1、三元组表P244 2、拓扑排序P229 3、AVL树P180六、七、p f .rlinkq算法设计(6+6+8=20)1、1. ifthenelseR=F print( underflow ) FF MOD m+1算法结束2、TYPE pointer= f nodenode=RECORDinfo: datatype;llink, rlink: pointerENDVAR t: pointer;Count: integer;进入算法时，二叉树已用二叉链表存储,t指向

38、根结点,count初值为0 Procedure node_Count (t: pointer; VAR count: integer);beginif t=nilthen算法结束elsebegin count:=count+1;node_count(t f .llink,count);node_count(t f .rlink,count) end end;3、TYPE node=RECORDKey: integer;Info: datatypeEnd;List=ARRAP1.NOF node;VAR X:node; j:0.n;Procedure quickpass(VAR R:list;l

39、,r:integer;VAR i:integer);begini:=l;j:=r;x:=Ri;repeatwhile (Ri.key=x.key)and(iVj = doj:=j-1; if ij thenRj：=Rj；i:=i+1;while (Ri.key=x.key=and (ij=do i:=i+1; if ij thenRj：= Ri；j:=j-1until i=j Ri：=x end注:整个快速排序 Procedure quicksort (VAR R:list;s,t:integer);Begin If st Then quickpass(R,s,t,i); quicksort(

40、R,s,i-1); quicksort(R,i+1,t) end;数据结构试题10一.单项选择题(每小题1分，共20分)设n为正整数,以下程序段的执行次数是：()k:=0;s:=1;REPEATs:=s+k; k:=k+1UNTIL (k=-n)A. (2n+3)次 B. 2(n+1 )次C.无限多次 D.1次序列A,B,C,D,E顺序入栈,不能获得的序列是：()A. ABCDE B. CDEBA C. EDCBA D.DECAB数据结构的内容包括：()三层次五要素C.五层次三要素三层次三要素D.五层次五要素 TOC o 1-5 h z 在双链表中要在p所指的结点后插入一个新结点q,要修改的指

41、针域个数为:（）A, 2个B. 4个 C. 6个 D. 8个在列主序下顺序的存储数组A 4 * 4的下三角元素A（3,2）的位置是第：（）A, 5 个B. 6 个 C. 7 个 D. 10 个n个结点顺序存储的完全二叉树，i （1i W n）结点的父结点的位置是（）a Fl B W c 111 D 1对任何二叉树，设n0,n1,n2 |分别是度数为0,1,2的结点数,则有：（2）A. n0=n2+1 B. n0=n2-1 C. n0=n1+1 D. n0=n1-1对图（一）的二叉树,其后续遍历结果为：（）图（一）A. ABDCEF B. ABCDEF C. DBAECF D . DBEFCA

42、结点可以排在拓扑序列中的图是：（）A.无向图 B.有向图C.有向无环图 D.无向有环图 串的求子串运算SUBSTR（ ABCDEFGH ,4,5）的引用结果是：（）A. DEB. DEFGHC. EFGHD. BCDE对于记录R1,R2其健值分别是K1和K2,数据为D1和D2,称 R1和R2是同义词的条件是（）K1=K2C. K1=K2 且 H（K1）尹H（K2）D1=D2D.K1 尹K2 且 H（K1）=H（K2） TOC o 1-5 h z 快速排序属于：（）A.插入排序B.交换排序 C.选择排序D.归并排序AVL数不平衡后要调整的情形有：（）A. 2种B. 4种C. 6种 D. 8种PR

43、IM算法是求图的：（）A.连通分量B.最短路径C.最小生成树D.拓扑序列在排序过程序中,使用辅助存储空间为O （n）的算法是：（）A.插入排序B.归并排序C.起泡排序D.快速排序 若无向图中有n个结点,e条边,则它的邻接表需要表节点数目为：（）A. 2eB. 2e+nC. 2e+1D.e+2n字符串的紧缩存储形式是每个字符占：（）A. 1个二进制位B. 1个字节 C. 1个字 D. 1个结点单元循环队列SQ有m个单元，其满队条件是：（）（SQ.rear+1） MOD M=SQ.front C. SQ.rear=mSQ.rear=SQ.front D. SQ.front=mVSAM文件属于：（）A.顺序文件B.散列文件 C.多关键字文件D.索引文件 下列说法中错误的是：（）n个结点的有向图最多有n*（n-1）条边用相邻矩阵存储图时所需存储空间大小与图中边数有关散列表中碰撞的可能性大小与负载因子有关多项选择题（错选，多选，漏选均不得分,每小题2分，共14分） TOC o 1-5 h z 根据描述算法的语言不同，可将算法分为：（）A,形式算法B.非形式算法C.伪语言算法D.运行终止的程序可执行部分E,运行不终止的程序可执行部分图的常见存储结构可以选取：（）A.邻接表 B.邻接矩阵C