数据结构历年真题.pdf

《数据结构历年真题.pdf》由会员分享，可在线阅读，更多相关《数据结构历年真题.pdf（50页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、全国2001年 10月自考数据结构试题一、单项选择题(本大题共15小题，每小题2 分，共 30分)1.算法指的是()A.计 算 机 程 序 B.解决问题的计算方法 C.排序算法 D.解决问题的有限运算序列2.线性表采用链式存储时，结点的存储地址()A.必须是不连续的 B.连续与否均可 C.必须是连续的 D.和头结点的存储地址相连续3.将 长 度 为 n 的单链表链接在长度为m 的单链表之后的算法的时间复杂度为()A.O(1)B.O(n)C.O(m)D.O(m+n)4.由两个栈共享一个向量空间的好处是：()A.减少存取时间，降低下溢发生的机率 B.节省存储空间，降低上溢发生的机率C.减少存取时间

2、，降低上溢发生的机率 D.节省存储空间，降低下溢发生的机率5.设数组datam作为循环队列SQ 的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值 为()A.front=front+1 B.front=(front+1 )%(m-1)C.front=(front-1 )%m D.front=(front+1 )%m6.如下陈述中正确的是()A.串是一种特殊的线性表B.串的长度必须大于零 C.串中元素只能是字母 D.空串就是空白串7.若目标串的长度为n,模式串的长度为n/3,则执行模式匹配算法时，在最坏情况下的时间复杂度是n,A.O(-)B.O(n)C.O

3、(n2)D.O(n3)38.一个非空广义表的表头()A.不 可 能 是 子 表 B.只能是子表 C.只能是原子D.可以是子表或原子9.假咚以产勺表的型,组表表示稀疏矩阵,则和下列行表1。|2|3 1 3|5|对应的稀疏矩阵是()0-8060-80670007000A.0000B.-5040-5040000000000300-0-806一-0-80600000000C.0200D.7000-5040-50400000030010.在一棵度为3 的树中，度为3 的结点个数为2,度为2 的结点个数为1,则度为0 的结点个数为()A.4 B.5 C.6 D.711.在含n 个顶点和e 条边的无向图的邻

4、接矩阵中，零元素的个数为()A.e B.2e C.n2e D.n22e12.假设一个有n 个顶点和e 条弧的有向图用邻接表表示，则删除与某个顶点叫相关的所有弧的时间复杂度是()A.O(n)B.0(e)C.O(n+e)D.O(n*e)13.用某种排序方法对关键字序列(25,84,21,47,15,27,68,35,2 0)进行排序时，序列的变化情况如下：2 0,1 5,2 1,2 5,4 7,2 7,6 8,3 5,8 41 5,2 0,2 1,2 5,3 5,2 7,4 7,6 8,8 41 5,2 0,2 1,2 5,2 7,3 5,4 7,6 8,8 4则所采用的排序方法是()A.选择排序

5、 B.希尔排序 C.归并排序 D.快速排序1 4 .适于对动态查找表进行高效率查找的组织结构是()A.有序表 B,分块有序表 C.三 叉 排 序 树 D.线性链表1 5 .不定长文件是指()A.文件的长度不固定B.记录的长度不固定C.字段的长度不固定 D.关键字项的长度不固定二、填空题(本大题共1 0 小题，每小题2分，若有两个空格，每个空格1 分，共 2 0 分)1 6 .数据的逻辑结构是从逻辑关系上描述数据，它与数据的 无关，是独立于计算机的。1 7 .在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则 指 向 头 结 点 的 指 针 h e a d 可 用 p表示为h e a d=

6、。1 8 .栈顶的位置是随着 操作而变化的。1 9 .在串S=s t r u c t u r e”中，以t 为首字符的子串有 个。20.假设一个9 阶的上三角矩阵A按列优先顺序压缩存储在一维数组B中，其中B 0 存储矩阵中第1 个元素的,则B 31|中存放的元素是。21 .已知一棵完全二叉树中共有7 6 8 结点，则该树中共有_ _ _ _ _ _ _个叶子结点。22.已知一个图的广度优先生成树如右图所示，则与此相 必应 的 广 度 优 先 遍 历 序 列 为。23.在单链表上难以实现的排序方法有 和。24 .在有序表(1 2,24,36,4 8,6 0,7 2,8 4)中二分查找关键字7 2

7、时所需进行的关键字比较次数为25.多重表文件和倒排文件都归属于 文件。三、解答题(本大题共4小题，每小题5 分，共 20分)26 .画出下列广义表的共享结构图形表示P=(z),(x,y),(x,y),x),(z)27 .请画出与下列二叉树对应的森林。己知一个无向图的顶点集为 a,b,c,d,e ,其邻接矩阵如下所示)1 O O 11 O O 1 O 1 1 c(1)画出该图的图形；(2)根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历，写出相应的遍历序列。29.已知二个散利J表,下用所示：|35|20|33|4 8|丁0 1 2 3 4 5 6 7 8 9 1 0 1 1 1 2其散列函

8、数为h(ke y)=ke y%1 3,处理冲突的方法为双重散列法，探查序列为：h j=(h(ke y)+i *h 1 (ke y)%m i =0 1,m 1其中h 1 (ke y)=ke y%1 1+1回答下列问题：(1)对表中关键字35,20,3 3和48进行查找时，所需进行的比较次数各为多少？(2)该散列表在等概率查找时查找成功的平均查找长度为多少？四、算法阅读题(本大题共4小题，每小题5分，共2 0分)30.下列算法的功能是比较两个链串的大小，其返回值为：-1 当 S S 2c o m s t r(s i,S 2)=s2请在空白处填入适当的内容。i n t c o m s t r(L i

9、 n kS t r i n g s i,L i n kS t r i n g s 2)/s i和s 2为两个链串的头指针w h i le(s l&s 2)i f(s l d a t e d a t e)r e t u r n 1 ；i f(s l d a t e s 2 d a t e)r e t u r n l；31 .阅读下面的算法L i n kL i s t m yn o t e(L i n kL i s t L)/L是不带头结点的单链表的头指针i f(L&L-n e x t)q=L；L=L-n e x t；p=L；S I：w h i le(p-n e x t)p=p n e x t；S

10、 2：p n e x t=q；q n e x t=NU L L；)r e t u r n L；请回答下列问题:(I)说明语句s i 的功能；(2)说明语句组S 2的功能:(3)设链表表示的线性表为(aha2,-,an)，写出算法执行后的返回值所表示的线性表。3 2.假设两个队列共享一个循环向量空间(参见右下图)，r r o n t i J.丽区/其类型Queue2定义如下：”,冷 皿 笠typedef struct (!)IDateType datafMaxSize；交 出 夕、f r o n t f 0 int front2,rear2；rea“ojQueue2；对于i=0或 1,front

11、s和 reari分别为第i 个队列的头指针和尾指针。请对以下算法填空，实现第i 个队列的入队操作。int EnQueue(Queue2*Q,int i,DateType x)若第i 个队列不满，则元素x 入队列，并返回1；否则返回0if(il)return 0；if(Qreari1=O-front IretumO；Q-data =x；Q-rearFil=r()1;return 1 ；)3 3.已知二叉树的存储结构为二叉链表，阅读下面算法。typedef struct node DateType data；Struct node*next；JListNode；typedef ListNode*L

12、inkList；LinkList Leafhead=NULL；Void Inorder(BinTree T)(LinkList s；If(T)Inorder(Tlchild)；If(!T-lchild)&(!T-rchild)s=(ListNode*)malloc(sizeof(ListNode)；sdata=Tdata；s-next=Leafhead；Leafhead=s；)Inorder(T-rchild)；)对 于 如下所示的二叉树(AY/滔(B)DGHF(1)画出执行上述算法后所建立的结构；(2)说明该算法的功能。五、算法设计题(本题共10分)3 4.阅读下列函数arrange()in

13、t arrange(int a,int l,int h,int x)/l和 h 分别为数据区的下界和上界int i,j,t；i=l；j=h；while(ij)while(i=x)j；while(i=x)i+；if(ij)t=aj；aj=ai；ai=t；)if(aijnext=P;S-prior=P-prior;P-prior=S;9.对广义表 A=(x,(a,b),c,d)的运算 head(head(tail(A)的结果是。10.判断线索二叉树中某结点指针P 所指结点有左孩子的条件是四、简答题(每小题5 分，共 15分)I.求出下图的一棵最小生成树。(70,12,20,31,1,5,44,66

14、,61,200,30,80,150,4,28)3.已知一棵二叉树的先序序列是ABCDEFGHIJK,中序序歹I 是 CDBGFEAHJIK,请构造出该二叉树。五、综合应用题(共17分)1.已知一树的双亲表示法如下，其中各兄弟结点是依次出现的，画出该树及对应的二叉树。(满分7 分)。1 2 3 4 5 6 7 8 9 10 11 12 13 14 15dataABCDEFGHIJKLMN0parent0111223344566782.计算二叉树的深度的算法。(10分)浙江省2002年 1 月高等教育自学考试数据结构试题参考答案课程代码：02331一、单项选择题(每小题2 分，共 38分)l.A2

15、.B3.C4.B5.D6.C7.A8.B9.A10.C11.D12.B13.D14.D15.C16.A17.B18.A19.C二、判断题(每小题1分，共 10分)1.V2.X3 V4.V5.X6.X7.V8.X9.X10.X三、填空题(每空2 分，共 20分)1.n-12.左右子树空3.12254.n(n-1 )/25.head(A)6.节省空间7.L-next=L-prior8.S-prior-next=S9.(a)10.P-ltag=l四、简答题(每小题5 分,1.最小生成树：或 Lnext=L共 15分）2.小头堆:1 123.二叉树：43130 5 20 66 61 20070 80

16、150 44 28AB/C ED F八G五、综合应用题（共 17分）1.从森林转换为二叉树：（7 分）2.计算二叉树的深度的算法:(10 分)int depth（tree*T）if(!T)return 0;elsereturn 1 +max(depth(T-Lchild),depth(-Rchild);全国2002年10月高等教育自学考试一、单项选择题1.若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为（）A.顺序存储结构B.链 式 存 储 结 构 C.索引存储结构D.散列存储结构2.在长度为n 的顺序表的第i（lWiWn+l）个位置上插入一个元素，元素的移动次数为（）A.n

17、-i+1B.n-i C.iD.i-13.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为（）A.顺序表B.用头指针表示的单循环链表 C 用尾指针表示的单循环链表D.单链表4.若进栈序列为a,b,c,则通过入出栈操作可能得到的a,b.c的不同排列个数为（）A.4B.5C.6D.75.为查找某一特定单词在文本中出现的位置，可应用的串运算是（）A.插入B.删除C.串联接D.子串定位6.已知函数Sub（s,i,j）的功能是返回串s 中从第i 个字符起长度为j 的子串，函数Scopy（s,t）的功能为复制串t 到 s。若字符串 S=SCIENCESTUDY,则调用函数$。丫 出 5 此6

18、1,7）后得到（）A.P=SCIENCE B.P=STUDYH C.S=SCIENCE，z D.S=STUDY”7.三维数组A456按行优先存储方法存储在内存中，若每个元素占2 个存储单元，且数组中第一个元素的存储地址 为 1 2 0,则元素A 3 45的存储地址为（）A.356B.3588.如右图所示广义表是一种（A.线性表B.纯表C.结点共享表D.递归表9.下列陈述中正确的是（）A.二叉树是度为2 的有序树C.360)D.362B.二叉树中结氏只另一1、修寸叫无左右之分C.二叉树中必有度为2 的 结 点 D.二叉树中最多只有两棵子树，并且有左右之分10.n个顶点的有向完全图中含有向边的数目

19、最多为（）A.n-1B.nC.n(n-l)/2D.n(n-l)11.已知一个有向图如右所示，则从顶点a 出发进行深度优先偏历，不可能得到的DFS序列为（）A.adbefc B.a dc e f bC.a d c b f e D.a d e f c b12.在最好和最坏情况下的时间复5A.快速排序B.堆排序C.归并排序内排序方法是（）D.基数排序13.不可能生成右图所示二叉排序树的关键字序列是（)A.4 5 3 1 2B.4 2 5 3 1C.4 5 2 1 3D.4 2 3 1 54114.ALV树是一种平衡的二叉排J（3）题 13图)A.左、右子树的高度均相同 B.左、右子树高度差的绝对值不

20、超过1C.左子树的高度均大于右子树的高度D.左子树的高度均小于右子树的高度15.在VSAM文件的控制区间中，记录的存储方式为()A.无序顺序 B.有 序 顺 序 C.无序链接 D.有序链接二、填空题(本大题共10小题，每小题2 分，若有两个空格，每个空格1分，共 20分)16.若一个算法中的语句频度之和为T(n)=3720n+4nlogn,则 算 法 的 时 间 复 杂 度 为。17.在如图所示的链表中，若在指针p 所指的结点之后插入数据域值相继为a 和 b 的两个结点，则可用下列两个语句实现该操作，它们依次是 和 oa i-M 5nl lAl题17图18.假 设 以 S 一一 和 X 分别表

21、示进栈和退栈操作，则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX之后，得 到 的 输 出 序 列 为。19.串 S=I am a worker的长度是。20.假设一个10阶的下三角矩阵A 按列优顺序压缩存储在一维数组C 中，则 C 数组的大小应为 o21.在n 个结点的线索二叉链表中，有 个线索指针。22.若采用邻接矩阵结构存储具有n 个顶点的图，则 对 该 图 进 行 广 度 优 先 遍 历 的 算 法 时 间 复 杂 度 为。23.对关键字序列(52,80,63,44,48,91)进 行 一 趟 快 速 排 序 之 后 得 到 的 结 果 为。24.由10000个结点构

22、成的二叉排序树，在等概率查找的假设下，查 找 成 功 时 的 平 均 查 找 长 度 的 最 大 值 可 能 达 到。25.若要找出所有工资低于1500元,职称是副教授，及所有工资低于2000元,职称是教授的记录,则查询条件是 o三、解答题(本大题共4 小题，每小题5 分，共 20分)26.已知一个6 行 5 列的稀疏矩阵中非零元的值分别为：-90,41,-76,28,-54,65和-8,它们在矩阵中的列号依次为：1,4,5,1,2,4 和 5。当以带行表的三元组表作存储结构时，其行表RowTab中的值依次为0,0,2,2,3 和 5。请写出该稀疏矩阵(注：矩阵元素的行列下标均从1开始)。27

23、.已知树T 的先序遍历序列为ABCDEFGHJKL,后序遍历序列为CBEFDJIKLHGAo请画出树T。28.对关键字序列(72,87,61,23,94,16,05,58)进行堆排序，使之按关键字递减次序排列。请写出排序过程中得到的初始堆和前三趟的序列状态。初始堆：第 1趟：第 2 趟：第 3 趟：29.在关键字序列(07,12,15,18,27,32,41,92)中用二分查找法查找和给定值92相等的关键字，请写出查找过程中依次和给定值“92”比较的关键字。四、算法阅读题(本大题共4 小题，每小题5 分，共 20分)30.以下函数中，h 是带头结点的双向循环链表的头指针、(1)说明程序的功能；

24、(2)当链表中结点数分别为1和 6(不包括头结点)时，请写出程序中while循环体的执行次数。int f(DListNode*h)(DListNode*p,*q;int j=l;p=h-next;q=h-prior;while(p!=q&p-prior!=q)if(p-data=q-data)p=p-next;q=q-prior;)else j=0;return j;)31.设栈S=(1,234,5,6,7)淇 中 7 为栈顶元素。请写出调用algo(&s)后栈S的状态。void algo(Stack*S)(int i=0;Queue Q;Stack T;InitQueue(&Q);InitS

25、tack(&T);while(!StackEmpty(S)(if(i=!i)!=0)Push(&T,Pop(&S);else EnQueue(&Q,Pop(&S);)while(!QueueEmpty(Q)Push(&S,DeQueue(&Q);while(!StackEmpty(T)Push(&S,Pop(&T)；)32.已知带权图的邻接矩阵表示和邻接表表示的形式说明分别如下：#define MaxNum 50 图的最大顶点数#define INFINITY INT_MAX/INT.MAX 为最大整数，表示8typedef struct char vexsMaxNum);字符类型的顶点表in

26、t edgesMaxNumMaxMum;权值为整型的邻接矩阵int n,e;图中当前的顶点数和边数MGraph;邻接矩阵结构描述typedef struct node int adjvex;邻接点域int weight;边的权值struct node*next;链指针域 EdgeNode;边表结点结构描述typedef struct char vertex;顶点域EdgeNode*fkstedge;边表头指针 VertexNode;顶点表结点结构描述typedef struct VertexNode adjlistMaxNum;邻接表int n,e;图中当前的顶点数和边数 ALGraph;邻接

27、表结构描述下列算法是根据一个带权图的邻接矩阵存储结构G 1建立该图的邻接表存储结构G 2,请填入合适的内容，使其成为一个完整的算法。void convertM(MGraph*Gl,ALGraph*G2)int i,j;EdgeNode*p;G2-n=Gl-n;G2-e=Gl-e;for(i=0;in;i+)(G2-adjlisti.vertex=Gl-vexsi;G2-adjlistliJ.firstedge=;)for(i=0;in;i+)for(j=O;jn;j+)if(Gl-edgesijweight=(2);p-adjvex=j;p-next=G2-adjlisti.firstedge

28、;；)(1)(2)(3)33.阅读下列算法，并回答下列问题：(1)该算法采用何种策略进行排序？算法中Rn+1的作用是什么？Typedef struct KeyType key;infoType otherinfo;nodeType;typedef nodeType SqList M AXLEN;void sort(SqList R,int n)(/n 小于 MAXLEN-1int k;i;for(k=n-1 ;k=1 ;k)if(Rk.keyRk+1.key)(Rn+l=Rk;for(i=k+1 ;Ri.keyRn+1 .key;i+)Ri-l=Ri;Ri-l=RLn+l;)五、算法设计题(本

29、题共10分)34.假设二叉树T 采用如下定义的存储结构：typedef struct node DataType data;struct node*lchild,*rchild,*parent;JPBinTree;其中，结点的Ichiki域和rchild域已分别填有指向其左、右孩子结点的指针，而 parent域中的值为空指针(拟作为指向双亲结点的指针域)。请编写一个递归算法，将该存储结构中各结点的parent域的值修改成指向其双亲结点的指针。全国2003年 1 月高等教育自学考试一、单项选择题1.下面程序段的时间复杂度是()for(i=0;in;i+)for(j=l;jnext;B.p-nex

30、t=p-next-next;C.p-next=p;D.p=p-next-next;3.在头指针为head且表长大于1 的单循环链表中，指针p 指向表中某个结点，若 p-next-next=head,5ij()A.p指 向 头 结 点 B.p指向尾结点C.*p的直接后继是头结点 D.*P的直接后继是尾结点4.判定“带头结点的链队列为空”的条件是()A.Q.front=NULL B.Q.rear=NULLC.Q.lront=Q.rear D.Q.front!=Q.rear5.设有两个串T 和 P,求 P 在 T 中首次出现的位置的串运算称作()A.联接 B.求子串 C.字符定位 D.子串定位6.广

31、义表人=6,8),(),(:,(1劭的长度为()A.4 B.5 C.6 D.77.一棵含18个结点的二叉树的高度至少为()A.3 B.4 C.5 D.68.已知二叉树的先序序列为ABDECF,中序序列为DBEAFC,则后序序列为()A.DEBAFC B.DEFBCA9.无向图中一个顶点的度是指图中(A.通过该顶点的简单路径数C.通过该顶点的回路数C.DEBCFA D.DEBFCA)B.与该顶点相邻接的顶点数D.与该顶点连通的顶点数10.已知一个图如下所示，从顶点a 出发进行广度优先遍历可能得到的序列为()A.a c e f b dB.a c b d f eC.a c b d e fD.a c

32、d b f e题 10图11.在下列排序方法中，平均时间性能为O(nlogn)且空间性能最好的是()A.快速排序 B.堆排序 C.归并排序 D.基数排序1 2.已知一组关键字为 2 5,4 8,3 6,7 2,7 9,8 2,2 3,4 0,1 6,3 5 ,其中每相邻两个为有序子序列。对这些子序列进行一趟两两归并的结果是（）A.2 5,3 6,4 8,7 2,2 3,4 0,7 9,8 2,1 6,3 5 B.2 5,3 6,4 8,7 2,1 6,2 3,4 0,7 9,8 2,3 5）C.2 5,3 6,4 8,7 2,1 6,2 3,3 5,4 0,7 9,8 2 D.1 6,2 3,

33、2 5,3 5,3 6,4 0,4 8,7 2,7 9,8 2）1 3.设顺序存储的线性表共有1 2 3 个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为（）A.2 1 B.2 3 C.4 11 4.索引非顺序文件的特点是（A.主文件无序，索引表有序C.主文件有序，索引表有序1 5.倒排文件的主要优点是（A.便于进行插入和删除运算C.便于进行多关键字查询D.6 2）B.主文件有序，索引表无序D.主文件无序，索引表无序B.便于进行文件的恢复D.节省存储空间二、填空题（本大题共1 0 小题，每小

34、题2分，若有两个空格，每个空格1 分，共 2 0 分）1 6.抽象数据类型的特点是将 和 封装在一起，从而现实信息隐藏。1 7 .从顺序表中删除一个元素时，表中所有在被删元素之后的元素均需 一个位置。1 8 .在队列中，允 许 进 行 插 入 操 作 的 一 端 称 为,允 许 进 行 删 除 操 作 的 一 端 称 为。1 9 .如图两个栈共享一个向量空间，topi和 top分别为指向两个栈顶元素的指针，则“栈满”的判定条件是题 1 9 图2 0 .设 S l=good ,S 2=,S 3=b ook ,则 S b S 2 和 S 3 依 次 联 接 后 的 结 果 是。2 1 .假设三维数

35、组A 1 0 9 8 按行优先顺序存储，若每个元素占3个存储单元，且首地址为1 0 0,则元素A 9 的存储地址是。2 2 .已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点，则该树中含有的叶子结点的数目为2 3 .能 够 成 功 完 全 拓 扑 排 序 的 图 一 定 是 一 个。2 4 .如果在排序前，关键字序列已接近正序或逆序，则在堆排序和快速排序两者之中，选用 较为适当。2 5 .假设哈希表的表长为m,哈希函数为H（k e y）,若用线性探查法解决冲突，则 探 查 地 址 序 列 的 形 式 表 达 为。三、解答题（本大题共4小题，每小题5分，共 2 0 分）2 6

36、.假设通信电文使用的字符集为 a,b,c,d,e,f ,名字符在电文中出现的频度分别为：3 4,5,1 2,23,8,1 8,试 为 这 6个字符设计哈夫曼编码。请先画出你所构造的哈夫曼树（要求树中左孩子结点的权值小于右孩子结点的权值），然后分别写出每个字符对应的编码。2 7 .已知一个图如下所示，其顶点按a、b、c、d、e、f 顺序存放在邻接表的顶点表中，请画出该图的邻接表，使得按此邻接表进行深度优先遍历时得到的顶点序列为a c b e f d,进行广度优先遍历时得到的顶点序列为a c b d f e a题 27图28.已知两个4 X 5 的稀疏矩阵的三元组表分别如下:1416221834-

37、2 54228113222-2 2256934254251请画出这两个稀疏矩阵之和的三元组表。29.从空树起，依次插入关键字40,8,90,15,62,95,12,23,56,3 2,构造一棵二叉排序树。(1)画出该二叉排序树(2)画出删去该树中元素值为9 0 的结点之后的二叉排序树。四、算法阅读题(本大题共4 小题，每小题5 分，共 20分)30.如图所示，利用同一循环向量空间实现两个队列，其类型Queue2定义如下：typedef struct DataType dataMaxSize;int front2,length2;Queue2;对于 i=0 或 l,fronti和 lengthi

38、分别为第 i 个队列的头指针和长度域。请在空缺处填入合适的内容，实现第i 个循环队列的入队操作。int EnQueue(Queue2*Q,int i,DataType x)若第i 个队列不满，则元素X入队列，并返回1,否则返回0if(il)return 0;if(1)return 0;Q-data (2)1=x;0-length(3)1+;return 1;)(1)(2)(3)31.某二叉树的线索链表存储结构如图(b)所示，其中p 为指向根结点的指针:图(a)为结点结构。阅读下列算法，并回答问题：写出执行函数调用f(p)的输出结果;简述函数f 的功能。void f(BinThrTree t)w

39、hile(t)flchild data|卜child(a)Q)printf(t-data);if(t-lchild)t=t-lchild;elset=t-rchild;/-IA bl图BZN囚F卜丘/闪G MI.,I(b)题3 1图32.下 歹 U 函数FindCycle(Gi)的功能是，对一个采用邻接表作存储结构的有向图G,利用深度优先搜索策略寻找一条经过顶点片的简单回路。数组cycle_path用于保存搜索过程中形成的回路，cycle_pathk=j(j，O)表示在回路中顶点vk的下一个顶点是请在空缺处填入合适的内容，使其成为一个完整的算法。已知邻接表的顶点表结点结构为：-vertexfi

40、rstedge边表结点EdgeNode结构为:adj vex nextint cycle_pathMaxNum;int FindCycle(ALGraph*Gjnl i)若回路存在，则返回1,否则返回0intj;for(j=0;j n;j+)cycle_path|j=-l;return DFSPath(Qi,i);)int DFSPath(ALGraph*G,int j,int i)EdgeNode*p;int cycled=0;for(p=G-adjlist|j.firstedge;p&!cycled;p=p-next)cycle_pathj=p-adjvex;if(1)cycled=1;/

41、已找到回路elseif(cycle_pathf p-adj vex=-1 )cycied=(2)return(1)(2)(3)33.阅读下列函数algo,并回答问题。(1)假设整型数组AL.8中的元素依次为(3,8,9,1,7,4,2,6)。执行函数调用algo(A,8)时，外层while的循环体执行多少次?函数的返回值是多少？(2)简述函数algo(L,n)的功能。int algo(int Ljntn)(int i=O,j,s=l,t=n;while(i!=(n+l)/2)(int x=Ls；i=s；j=t;while(ij)while(i=x)j;Li=Lj;while(ij&Li=x)i

42、+;Ujl=Li;)Li=x;if(idata);if(T-rchild)Push(&S,T-rchild);if(T-lchild)T=T-lchild;else T=Pop(&S);)(1)(2)32.已知邻接表的顶点表结点结构为题 31图vertex firstedge边表结点EdgeNode的结构为adj vex next下列算法计算有向图G 中顶点片的入度。请在空缺处填入合适的内容，使其成为一个完整的算法。int FindDegree(ALGraph*G,int i)/ALGraph 为图的邻接表类型(int dgree,j;EdgeNode*p;degree=;for(j=0;jn

43、;j+)p=G-adjlist Ej.firstedge;while(_)(if()(degree+;break;)p=p-next;)return degree;(1)(2)(3)33.已知单链表的结点结构为 data next下列算法对带头结点的单链表L 进行简单选择排序，使得L 中的元素按值从小到大排列。请在空缺处填入合适的内容，使其成为完整的算法。void SelectSort(LinkedList L)(LinkedList p,q,min;DataType red;p=(1)；while(p!=NULL)min=p;q=p-next;while(q!=NULL)iff(2)min=

44、q;q=q-next;)i f()rcd=p-data;p-data=mi n-data;min-data=rcd;)：(1)(2)(3)(4)五、算法设计题(本题10分)34.设线性表A=(aa2,a3,a j 以带头结点的单链表作为存储结构。编写一个函数，对 A 进行调整，使得当n 为奇数时A=(a2,a4,an.|,a,a3,an),当 n 为偶数时 A=(a2,a4,an,ai,a31全国2004年1月高等教育自学考试一 单项选择题1.在数据结构中，数据的逻辑结构可以分成()A.内部结构和外部结构 B.线性结构和非线性结构C.紧凑结构和非紧揍结构 D.动态结构和静态结构2.在以单链表为

45、存储结构的线性表中，数据元素之间的逻辑关系用()A.数据元素的相邻地址表示 B.数据元素在表中的序号表示C.指向后继元素的指针表示 D.数据元素的值表示3.设 p 指向单链表中的一个结点，s 指向待插入的结点，则下述程序段的功能是()s-next=p-next;p-next=s;t=p-data;p-data=s-data;s-data=t;A.结点*p 与结点*s 的数据域互换B.在 p 所指结点的元素之前插入元素C.在 p 所指结点的元素之后插入元素D.在结点*p 之前插入结点*s4.栈和队列都是()A.限制存取位置的线性结构 B.顺序存储的线性结构C.链式存储的线性结构 D,限制存取位置

46、的非线性结构5.若数组sO.n-l为两个栈s i 和 S2的共用存储空间，且仅当sO.n-l全满时，各栈才不能进行进栈操作，则为这两个栈分配空间的最佳方案是：s i 和 s2 的栈顶指针的初值分别为A.1 和 n+1 B.1 和 n/2c.-1 和 n D.-1 和 n+16.执行下列程序段后，串 X 的 值 为()S=abcdefgh;T=xyzw;substr(X,S,2,strlen(T);substr(Y,S,stelen(T),2);strcat(X,Y);A.cdefgh B.cdxyzw C.cdefxy D.cdefef”7.多维数组之所以有行优先顺序和列优先顺序两种存储方式是

47、因为()A.数组的元素处在行和列两个关系中 B.数组的元素必须从左到右顺序排列C.数组的元素之间存在次序关系 D.数组是多维结构，内存是一维结构8.从广义表LS=(p,q),r,s)中分解出原子q 的运算是()A.tail(head(LS)B.head(tail(head(LS)C.head(tail(LS)D.tail(tail(head(LS)9.在 具 有 n 个叶子结点的严格二叉树中，结点总数为()A.2n+l B.2nC.2n-l D.2n-210.若Wi,Vj是有向图的一条边，则 称()A.Vj邻接于V j B.Vj邻接于VjC.Vj和 Vj相互邻接 D.Vj与 Vj不相邻接11.

48、在一个带权连通图G 中，权值最小的边一定包含在G 的()A.最小生成树中 B.深度优先生成树中C.广度优先生成树中 D.深度优先生成森林中12.当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为()A.左子树的叶子结点B.左子树的分支结点C.右子树的叶子结点D.右子树的分支结点13.希尔排序的增量序列必须是()A.递增的 B.随机的C.递减的 D.非递减的14.如果在排序过程中，每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置，则该排序方法称为()A.插入排序 B.归并排序C.冒泡排序 D.堆

49、排序15.设置溢出区的文件是()A.索引非顺序文件 B.ISAM文件C.VSAM文件 D.顺序文件二、填空题(本大题共10小题，每小题2 分，共 20分)请在每小题的空格中填上正确答案。错填、不填均无分。16.下 列 程 序 段 的 时 间 复 杂 度 为。product=1;for(i=n;i0;i-)for(j=i+1;j next=p-next-next的作用是。18.假设元素只能按a,b,c,d的顺序依次进栈，且得到的出栈序列中的第一个元素为c,则可能得到的出栈序列为，不可能得到的出栈序列为19.若链串结点中的指针占4 个字节，每个字符占1个字节，则结点大小为2 的链串的存储密度为20

50、.右图表示的广义表为。21.若一棵满三叉树中含有121个结点，则该树的深度为。22.若以邻接矩阵表示有向图，则邻接矩阵上题 20图第 i 行中非零元素的个数即为顶点V i的。23.若希望只进行8 趟排序便能在4800个元素中找出其中值最小的8 个元素，并且要求排序过程中所进行的关键字比较次数尽可能少，则应该选用 排序方法。24.在含20个关键字的3 阶 B 树（23 树）上查找一个关键字，至多需要访问 次外存。25.文件上的两类主要操作为 和。三、解 答 题（本大题共4 小题，每小题5 分，共 20分）26.设栈S 1的入栈序列为1 2 34（每个数字为13个元素），则不可能得到出栈序列314