数据结构试题及答案

1、?数据结构?自考复习思考试题一鼻单项选择题本大题共15小题每题2分,共30分 在毎小题列岀的四个备选项中只有一个是符合题目要求的*请将其代码填写在题后的括号内.错选、多项选择或未选均无分。1 假设将徽据结构形式定义为二元组KR,其中K是数据元素的有限集合.那么R是K EA.操作的有限集合0OC.类型的宥限集合2.在长度为n的顺序我中删除第n个元扌B映象的有限集合D.关茶的壽赊合皑时.元董移动的次数为A mi+】B. 1C. i+1D n-i篥 环 U的单i"的头指针为血述 那么瀏糠为空的判定条件是IA head=NULLB head->next=NTJLLCl head!mUL

2、LD head-next=head4.引起循环關列賦头位置发生变化的操作啟A. 册队B.入队C取队头元素D取队尾元素5 著进栈序死富阳2.玉斗* S?6丄进栈和出栈可臥需 那么不叮能出珊|J'列忍 )A. 2* 4* 31 1« 5* 66.字符串通常采用的两种存储方式敏A_散列存储和盍引存储B, 索引存餚和链式存睹C.顺序存储和链式存,D敬列存储和顺序存鯨工设生弗长为n麒式車孫为uXmWQ那么在匹配失败悟况下朴素匹配算法迸行的无效位 移嵌数为EL n«mD. nU nm+l&二维数组A C12 18用列优先的存储方淑 假设每个元素各占3个存储单元且第1个无

3、素的地址为150,那么元素A 9 7的地址为C. 435D 4389对广义表LN乩b,cQ仗f执行操作tailtail功的结果是f010. TFJR示的瞰序存赭黠构表示的二買树忌B.11. m个顶点的强建通图申奎少會儆Ae n-1条有向边C-11口-1/2条有向边Bm条有向边D. 1111-1条有向边IX对关犍字序列(56* 2务78, 92. S3, 67,19, 34进行熾量为3的一趟希尔挣序的结果为A(19岁 2 氛 56, 34> 78, 67, 88， 92)0.(19, 23j 34f 56, 67. 78, 8& 92)BQ弟 56, 78, 66® 88

4、> 92. 19 34)D4191 23, 67, 56. 349 78. 92. 88)G假设在9阶3树申插入关键字弓I起第点分裂,那么该箱点在播入前含有的关键字个数为A.4C. 8D. 914. 由同一黄键字集令构埋的备棵;叉排序树A.其不一定相同，II平均査找托度相同B其形蠡不一宦相阿普均查找长度也不一定相阿U记形态均相同,但平均行找2度退相同 _ *D. 其形态均相同罰平均査找长度也都相同15. ISAM文件和VSAM文件的区别之一是()A.前者是索刑顺序文件，后者是索刖非顺序文件 b川出只 海nm理u后春貝般应I诵陣c.前者建立静态濫引華檄引釘ID.前者的存储介质aaa,后者的

5、存储介质不晁磁盘二髦填空题(本大题共10小题，每空2分，共go分)16. 数据的逻辑结构在计肆机存储器内的表汞，称为数据的17. 删除與向循环链表中甲的前驱结点(存在)应执行的语句是1 &栈下溢是指在时遴行出栈操作«仗 已规$ub$tr(HleD)函数的功能是返回串&中第i个字符开始长度为len的子串，sulen(s)数的功能是邂同串s的长度营假设s= " ABCDEFGHUK懵=两ABCD " /执行运算subs&Cs.strlenCt), strlen(t)W 的遞風值为20.去除广义表LS=(丸忌屈严& aj中第1个元素扌由其

6、余元素构成的广Jl表称为LS的2L完全二叉树T的第5层貝有7牛绪就 那么该树转有个叶子第点眇排序.22-在有向閤申I以顶点*为终点的边的数目称为中的 23-当黄擁字的取值范围是实数集W.无袪进抒箱排序和 24.产生冲究现象的两个关键字称为该披列函数的 25.假设散列文件中一个桶能存旗in个记录那么桶亶溢HT的含文也 当需要插入新的讪录时，该桶中，三.解答题(本大题共4小题，每题为分，共20分)维 鮭以卿 呷啤钟循环佻列曲元素.设费jtn$ar和 啊硼指示循环队列申队尾元素的位置和元索的卜数祐(1) 写出仏满的条件表达式1Q)写出賦空的条件表达式: 设 m=40jeai-1 .queleiiRg

7、K头元素的位置f写岀-般悄况下队头元素位置的衷达式.27.一棵二又树的中序序列为ABCDEFG.层序序列为BAFEGCD,请画出该二叉树$ ©28.涌出下掏所汞有向图的所有强建過分出顾28用29】对7个关犍字进殍快速排序胃在疑好的情况下仅需逬行10次关键字的比拟©假设关犍字集合为口占点?试举出能到达上迷结果的初始关键字序殊(2) 对所举序列进行快速排序甲写出排序过程.算法阅读题(本大题共4小题克每题5分.共20分)30. 阅读以下算法费井答复以下问题,设爛序我L=C3,7J144M51).写出拗f nO(&L,之后的L； (2)设顺序表LWJCM巴20,51)写出执

8、行f30(&LM)之后的Li简述算:法的功能諒void fiO(SeqList*L. DataTpe x)mti=0j;xiiile (i<L->lengtfi && x>L->data 订 Ji+七； if(i<L->length && x=L->data i ) fbi(j=i-i-l ;j<L->length;j-H-)L->data j-1 =L->data j ; else for=L->lengtli;j>i ;j -)>L->data j =L->

9、;data 卜1詐 L->data i =x;L->length+;31. 己彌图的邻接表表示的堆武说明如丘define MaxNiun 50“斟的最大顶点数typedef struct node oiiit adjvex;struct node next. EdgeNode；"边表结点结构描述typettef struct chai* veitex;EdgeNode *firstedge;"边表头扌旨针 rtexNode;.羽顶点表绪点蜡构描述拠接表typedef struct *rertexNode adjlist Ma?<Nu:附国中当前的顶点数和边

10、数 ALGraph制接表结构描述下到鄴法输出图G的深度优先生成树或森林的边.阅读算法銅井崔空缺处填入會适的内容使其成为一个完搭的算法。typedef enuin FALSE. TRUE) Boolean.Boolean Msited MaxNuni;void DF SF orest( ALGraph «G)int i;for(i=O;i<G->n;i+) Msited i=:foiXi=03<O->n,i+) if (!visited i ) DFSTree(Gi); oid DFSTree(ALGraph *G mt i) EdgeNode p;visite

11、d Ei =TRUE;p=G->adjlist i firstedge;wlule(p!=NULL)1 罠!visited p->adjvex )printf( r7G->adjlist 订.vertex,G->adjlist p->adjvex , vertex)Ol:32. 阖读以下算法發并答复以下问题假设数?IIL 8 FQ5J6427,写出执行函数调W f32(L, 8)后的L；写出止述崗数调用过程申迸行无素交换操作的总次数。void f32(int R ,int n)mt址forwhile (R 11 !=i) t=R R ill <R R 订=R

12、 Li；R 订=1；S3.己知帝头结点的单链表中的关键字为整数为提高查找效率.需将它改建为采用拉链法处理冲突的散列表堆较散列表的快度为m散列函数为HaSh(key>kem.链表的结壷结构 为:key tiext | »稱在空缺处填入适当内容?骰其成为=个完整煽谁笹VQid B3 (LmkList L, LmkList H int m)也由帯头结点的单链表L生成散列表H散列表空成之后原链表不再存在LmkList p、q; for (i=O;i<m;H)H i =；p=L->next; while(p)q=p->next; j 乎 >key%in;H j于(

13、3L五.算法设计题本大题10分34.假设以帶双亲指针的二JL链我作为二义树的存储结构其结点结构的类型说明如卜所typedef char DataTpe*otypedef struct node ；DataType data, struct node *lchildl, *rchildt struct node +parent;於左右撲子指針 舟指向取亲的指针 BiaTNtyp亡def BmTNode *BinTree.假设px为指向菲空二叉树中某个结点的指th可借助该第构求得px所播鰭点在二叉树的中序 序列中的后继作 就后维的不同情况简要表达实现求后継操作的方法星数据结构标准答案D-S单项选择

14、题1-( B )2(D)34 A )4( A )5( D )6 J C )7 ( C )8( A )9( B 10( A )1k( B )124 D )134 c )144 B )15X C )二 填空题本大趣共忆小题，每空2分.共20分16,存储结构亿 q = p->pre;q->pre->next = p;op->pre 二 q->pre;feo( q);19 HDEFG""注意取引号不樹20_表尾 21.2 A(l-2)+M/2 叶予结就22. 523-基数24, 同义斓25. 己有m个同义词记永 三、解答题(本大题共4小题每题5分*共2

15、0分)26 (1) quelen = m(2) quelen = 0(3) (13-19+40)%40 = 34(4) (rear - queien + m ) % m27.Bf A. F/E. GD28. 3 个：a - bcs dfg 29.我们知道，对n桦犍負序列进行一趟快速排序.要进行rM次比做 也就是棊准和其他n-1个芙键字比拟.这里要求10矢 而7 " * 2气3 - 1) = 1山 这就要求2趟快速排序后鼻算法睹束旷 所虬 列举出来的序列*夏求在做partition的时驗 正好将序列專分(1) 4 1 3 2 6 & 7 4 1 37652 fit 4 5376

16、12或 4 1 35627. (2自己列吧：)咏 算法阅读题(本人题共4小甌 每题5分共20分)30(1)1-(37.114.15,20,51) L-(47#14,20.51)(3)在顺序我L申查找数X没找越h那么在适署的僅覽播入X.插入后 L依然疽序；31.(1) FALSE 初始化为未访间DSFTree( G, ph>adjvex );"从相嘟結点越下讎续深度搜索(3) p = "next； 下一个未讶同的相邻谿点32. L = W 2,3, 4, 5, 6,7;(2) 5 次(1) NULL祠始化p->next =和F面一旬売成头插法(3) p= q；继续遍历La*®3L算法设计题(本大题10分)34nam 有右攒孔 那么其右薇予为其中序序列中的后継 找到.那么该结点的父錯