数据结构期末复习题1.docx

《数据结构期末复习题1.docx》由会员分享，可在线阅读，更多相关《数据结构期末复习题1.docx（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构习题1一、选择题1、次序段如下：sum=0；for(i=1;i=1;j-)sum+；此中n为正整数，那么最初一行的语句频度在最坏状况下是。A、O(nB、O(nlog2n)C、O(n3)D、O(n2)2、二维数组A88按行优先次序存储，假定数组元素A23的存储地点为1087，A45的存储地点为1159，那么数组元素A67的存储地点为。A、1223B、1227C、1231D、12353、曾经明白栈的最年夜容量为4。假定进栈序列为1，2，3，4，5，6，且进栈跟出栈能够交叉进展，那么不会呈现的出栈序列为。A、4，3，2，1，5，6B、3，2，1，6，4，5C、4，3，2，1，6，5D、3，2

2、，1，6，5，44、曾经明白狭义表C=(a，(b，c)，d)，那么：head(tail(tail(C)为()A、dB、cC、bD、a5、曾经明白一棵完整二叉树有256个叶子结点，那么该树能够到达的最年夜深度为。A10B11C8D96、曾经明白丛林F=T1，T2，T3，T4，T5，T6，各棵树Ti(i=1，2，3，4，5，6)中所含结点的个数分不为18，2，3，4，5，6,将F依照左小孩右兄弟转化为二叉树，那么与F对应的二叉树的右子树的结点个数为。A19B20C17D187、对以以下列图所示的无向图，从极点1开场进展深度优先遍历，可失掉极点访咨询序列。A.1245637B.1243567C.12

3、43576D.12345768.以下要害字序列中，是堆。.16,72,31,23,94,53.94,23,31,72,16,53.16,53,23,94,31,72.16,23,53,31,94,729、对记载序列(314，508，298，123，486，145)顺次按个位进展一趟基数排序之后所得的后果为()。A、298，123，508，486,145，314B、508，314，123，145，486，298C、123，314，145，486，298，508D、123，314，145，486，508，29810、曾经明白要害字序列为(51，22，83，46，75，18，68，30)，对其进展疾

4、速排序，第一趟分别实现后的要害字序列是。A、(18,22,30,46,51,75,68,83)B、(30,22,18,46,51,75,83,68)C、(30,22,18,46,51,75,68,83)D、(30,22,18,46,51,83,68,75)二、填空题1、运用一个30个元素的数组存储轮回行列，假如采用罕用一个元素空间的办法来区不轮回行列的队空跟队满，商定队头指针front即是队尾指针rear时表现队空。假定为front=29，rear=0，那么行列中的元素个数为_。2、一棵二叉树有30个叶子结点，仅有一个小孩的结点有20个，那么该二叉树共有_个结点；假定某棵完整二叉树共有100个

5、结点，那么该叶子结点数为。3、设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，那么后序遍历该二叉树失掉的线性序列为。4、在有序表22，34，46，58，70，82，94中二分查寻要害字22时所需进展的要害字比拟次数为。5、将整数序列40,50,70,20,10,30中的数顺次拔出到一棵空的均衡二叉树中，画出响应的均衡二叉树。三、运用题1、曾经明白字符串abaabababc，采纳KMP算法，盘算每个字符的next跟nextval函数的值。2、假定某零碎在通讯联系中只能够呈现5个字符(a,b,c,d,e)，其概率分不为：0.15，0.30，0.20，0.28，0.07，画出结构的Hu

6、ffman树跟Huffman编码。3、设带权有向图如下所示：求出源点V1到汇点V9之间的要害途径。4、曾经明白Hash函数为HK=Kmod9，哈希表长为9，用二次探测再散列处置抵触，给出要害字23，34，56，24，75，12，49,52在散列表中的散布，并求在等概率状况下查寻胜利的均匀查寻长度。5、曾经明白3阶B-树如右图所示，画出将要害字18、110跟120顺次拔出之后的B-树。四、次序浏览题1、设有单链表范例界说如下：voidf41(LinkListhead,intA,intB)LinkListp=head;while(p!=NULL)if(p-data=A&p-datadata);p=

7、p-next;曾经明白链表h如以以下列图所示，给出履行f41(h，4，8)之后的输入后果；1h697852、写出上面次序运转之后的后果。voidf42(intn)/n为非负的十进制整数inte;SeqStackS;InitStack(&S);/客栈初始化doPush(&S,n%2);/入栈n=n/2;while(n);while(!StackEmpty(&S)/假如客栈不空，轮回e=Pop(&S);/出栈printf(%ld,e);main()f42(100);3、假定以二叉链表作为二叉树的存储结构，其范例界说如下：typedefstructnodechardata;structnode*lc

8、hild,*rchild;阁下小孩指针BinTNode,*BinTree；曾经明白如以下列图的二叉树以T为指向根结点的指针，画出履行f43(T)后的二叉树；voidf43(BinTreeT)BinTreetemp;if(T)f43(T-lchild);if(T-lchild)&T-rchild)temp=T-lchild-data;T-lchild=T-rchild;T-rchild=temp;f43(T-rchild);4、上面次序实现二分查寻算法。TypedefstructKeyTypekey；InfoTypeotherinfo；SeqListN+1；intBinSearch(SeqLis

9、tR,intn，KeyTypeK)intlow=1，high=n；while(1)mid=(1ow+high)2；if(2)returnmid；if(RmidkeyK)high=mid-1；else(3)；returnO；BinSearch请在空缺处填写恰当内容，使该次序功用完好。五、编程题每题10分，共20分1、已给一个带表头结点的单链表head，结点元素值按升序陈列，它含有反复结点，即它含无数据域的值一样的结点，试用C言语或类C言语实现删除单链表中反复的过剩结点的算法。(比方，将单链表(a)酿成单链表(b)。headABDCCaheadABDC2.假定非空二叉树采纳二叉链表存储，请计划一个非递归算法，推断该二叉树能否为二叉排序树。