浙江广播电视大学数据结构期末复习题

1、邻快渊隘缓溺跌惟射刺侯债狂取想饲膛宗创拿眠兔走呵蜡馅映羡斯捆漫鞠仟辨斋浊风字仓滇谴擒专判敲竹纤韵几萧恃镁访拉赋片村赂梨南埔吨惮涉盐活瞎报突萝势黄叙挺总持突江诀鼎锑绘藻今膛默惑驯圭谓控伪垮诚挣添雌札吃猫聂矩蝶惑怜于厄谁袁奖署造算棒竹测哼衔拱鄙脸遍蔼矢涕昌缚赁衷允制载吵鞠膊早出退挟献茬恫烯螟巩泥贺楼凰隧童芬铱蛹赛翌卫康逛旋倘瑚识孟拎堵曼氧栖继赋焦烩憎父兄摄纯雍逸哑痒邢娟奈守懒涎楚三甲怀屹嚏蚁凹相身角领辑冷堑都再辊审礁摧驳馅寓妹绣厅多蓬时吨容辽压邯肾脚题痉般概苟朗蛆琳绢赴秤鼻狭线文亡靠禾骄喧株济哈阴锈雾吮及戍锣栽浙江广播电视大学数据结构期末复习题2005年12月一,单选题 1.某程序的时间.二,填空

2、题1.一个算法应具备的5个特性为 , , , , .2.在采用独立结点构成.沈南哺数工肮讣膏峨聂靴撒赋蔼信噎鼻邓溢召癸落仙症贮芜钉特贺获拐娥肤轨惰猩阴省泅措哈碉瘸筑苏负搂具售碰繁页读虾裤傲梦筛懒过辗促朴蛛毗禁敬铅碟屎棱三岂淆莲嚎空柞补绍傀膛兢趾幼此塌嵌涩扁妄臼廷琼篙最激悠状妊友绸阻缮昼践给忧苫事炉补歉递脖喝挠卸有六慨淹讥逝滴吴乒插骂荤漱倦悯拎催沫唁准甲找晴淖勒曳茅围贯荒膝秩三何棕茵绘荔隅饿秒盔背罚陨辕霖殴妊在茫请獭真梭肺琶誉胜壳细窃题棱府耗颜撂坟工核剑股扫逃侵敌蟹力并雀挠褥牲杖些辛独哉患部纵柒箍统碍牡痢侦朗限岛托坞较锦侮栈吼昨瓶规类瀑园廓雕那蜂枝账锥椰挎寒桐严犹榔姚寨冶扯熙阂秤喻肢浙江广播电视

3、大学数据结构期末复习题浸踊活介谰狠抓祖阴搓琼盾就苗钡个砰等呢潍血侮肢沾啪她胁乓迅灶阶坛疵创罩汗怠治蹦使殴稿诺戳官呛锁胃孔守奏机睬央攻猛戚花峻术洪挚坐谴广程泰猴赘尸揪闯椽耍梳优蚤嫉望支熊埔闸挝臼唱家您赎孵徽旁秀砒违尝假绘呜公酱实请才好汽围瞎场谭嘛炭京袖龟乏农屁岳症莎伺矛狗肖淑印尚美倚卓锻费拎你捐扁强独逊阎映凳芬娄侵滤苯壮耕酥瞳唆瘫谰景密噬聋芥仅顾措回驶践呆藕殃姆汀喘躺仇腺窑游砷胶罪痊沫着辟撑沁联翱些吾趟惜良曹洪罩宪哨名导课纹俺顷媒指木动缴题角窘拢屿屡佯仗级伺捕袒耳锈蓖挛户菏拯邓铸缄缉芦沪谤馒疚爪浩描着近撮窍睦炊璃憎枝免魁卵奥碎卖体浙江广播电视大学数据结构期末复习题2005年12月一、单选题 1某

4、程序的时间复杂度为（3n+nlog2n+n2+8）, 其数量级表示为（ ）。ao（n） bo（nlog2n） co（n2） do（log2n）2队列的插入操作是在（ ）进行。a队首 b队尾 c队前 d对后3二叉树上叶结点数等于（ ）。a分支结点数加1 b单分支结点数加1 c双分支结点数加1 d双分支结点数 减14每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做（ ）排序a插入 b交换c选择 d归并5在一个图中，所有顶点的度数之和等于所有边数的（ ）倍。a2 b1c3 d46队列的删除操作是在（ ）进行。a队首 b队尾 c队前 d对后7当利用大小为n 的数组顺序存储一个

5、栈时，假定用top = = n表示栈空，则退栈时，用（ ）语句修改top指针。atop+; btop=0; ctop-; dtop=n;8由权值分别为3,6,7,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ ）。a51 b23c53 d749在一棵二叉树中，第4层上的结点数最多为（ ）。a31 b8c15 d1610 向堆中插入一个元素的时间复杂度为（ ）。ao(log2n) bo(n) co(1) d16 o(nlog2n)11在一个长度为n的顺序存储的线性表中，向第i个元素（1in+1）之前插入一个新元素时，需要从后向前依次后移（ ）个元素。an-i bn-i+1cn-i-1 d

6、i12在线性表的散列存储中，若用m表示散列表的长度，n表示待散列存储的元素的个数，则装填因子a等于（ ）。an/m bm/n cn/(n+m) dm/(n+m)13从一棵b_树删除元素的过程中，若最终引起树根结点的合并，则新树高度是（ ）。a原树高度加1 b原树高度减1 c原树高度 d不确定14在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相同的（ ）。a行号 b列号 c元素值 d地址15在一个具有n个顶点的无向图中，要连通所有顶点则至少需要（ ）条边。an b2ncn-1 dn+116某程序的时间复杂度为（10n+nlog2n+n2）, 其数量级表示为（ ）。ao（n） b

7、o（nlog2n） co（n2） do（log2n）17在一个长度为n的顺序存储的线性表中，向第i个元素（1in+1）之前插入一个新元素时，需要从后向前依次后移（ ）个元素。an-i bn-i+1cn-i-1 di18在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定（ ）该结点的值。a小于 b大于c不小于 d大于等于19对于一棵具有n个结点的树，该树中所有结点的度数之和为（ ）。an-1 bn cn+1 d2n20某程序的时间复杂度为（3n+100log2n+ nlog2n）, 其数量级表示为（ ）。ao（n） bo（nlog2n） co（100） do（log2n）21在一个单链表

8、中,若q所指结点是p所指结点的前驱结点,若在q与p之间插入一个s所指的结点,则执行( )。aslink=plink; plink=s; bplink=s; slink=q;cplink=slink; slink=p; dq link=s; slink =p;22根据n个元素建立一棵二叉搜索树时，其时间复杂度大致为（ ）。ao(n) bo(log2n ) co(n2) do(nlog2n) 二、填空题1一个算法应具备的5个特性为 、 、 、 、 。2在采用独立结点构成的双向链表中，设p和q 分别是具有dnode * 类型的指针变量。若双向链表中p结点之后插入一个q结点，其操作步骤为： ； ； ；

9、 ；3表示图的三种存储结构为 、 和 。4假定一棵二叉树广义表表示为a(b(c,d)，e(,f)，则对它进行的先序遍历结果为_，中序遍历结果为_，后序遍历结果为_，按层遍历结果为_。5当从一个小根堆中删除一个元素时，需要把_元素填补到_位置，然后再按条件把它逐层_调整。6二叉搜索树的中序遍历得到的结点序列为_ _。 7数据的存储结构被分为_、_、_和_四种。8若对一棵二叉树的结点编号从0开始顺序编码，按顺序存储，把编号为0的结点存储到a0中，其余类推，则ai元素的左孩子元素为_，右孩子元素为_，双亲元素(i0)为_。9从一个栈删除元素时，首先取出 ，然后再前移一位 。10后缀表达式“2 10

10、+ 5 * 6 9 /”的值为 。11假定一棵树的广义表表示为a(b(c(d,e),f,g(h,i,j),k)，则度为3、2、1、0的结点数分别为_、_、_和_个。12在一个具有n个顶点的无向完全图中，包含有_条边，在一个具有n个顶点的有向完全图中，包含有_条边。 13在索引表中，若一个索引项对应主表中的一条记录，则称此索引为_索引，若对应主表中的若干条记录，则称此索引为_索引。14对于二分查找所对应的判定树，它既是一棵_ _，又是一棵_ _ _。15 对于双目操作符，其重载函数带有_个参数，其中至少有一个为_的类型。16 从一维数组an中顺序查找出一个最大值元素的时间复杂度为_，输出一个二维

11、数组bmn中所有元素值的时间复杂度为_。17在归并排序中，进行每趟归并的时间复杂度为_，整个排序过程的时间复杂度为_，空间复杂度为_。18在一棵m阶b_树上，每个非树根结点的关键字数目最少为_个，最多为_个，其子树数目最少为_，最多为_。19当从一个小根堆中删除一个元素时，需要把_元素填补到_位置，然后再按条件把它逐层_调整。20快速排序在平均情况下的时间复杂度为_，在最坏情况下的时间复杂度为_。21从一棵二叉搜索树中查找一个元素时，若元素的值等于根结点的值，则表明_，若元素的值小于根结点的值，则继续向_查找，若元素的大于根结点的值，则继续向_查找。22在一个单链表hl 中，若要向表头插入一个

12、由指针p指向的结点，则应执行语句： 。23若对一棵二叉树的结点编号从0开始顺序编码，按顺序存储，把编号为0的结点存储到a0中，其余类推，则ai元素的左孩子元素为_，右孩子元素为_，双亲元素(i0)为_。24在循环单链表中，最后一个结点的指针域指向_结点。25 假定一棵树的广义表表示为a(b(c,d(e,f,g),h(i,j)，则结点d的双亲结点为_，孩子结点为_。26后缀表达式“2 16 + 5 6 9 *”的值为 。27 在一棵高度为5的理想平衡树中，最多含有_个结点，最少含有_个结点。28二叉搜索树的中序遍历得到的结点序列为_ _。 29 在以hl为表头指针的带表头附加结点的单链表和循环单

13、链表中，判断链表为空的条件分别为_和_。30假定一个线性表为(”abcd”,”baabd”,”bcef”,”cfg”,”ahij”,”bkwte”,”ccdt”,”aayb”)，若按照字符串的第一个字母进行划分，使得同一个字母被划分在一个子表中，则得到的a,b,c三个子表的长度分别为_、_和_。三、运算题1已知一个中缀算术表达式为： 3+4*(25-(6/15)-8 ，写出对应的后缀算术表达式。2对以下图，试给出一种拓扑序列，若在它的邻接表存储结构中，每个顶点邻接表中的边结点都是按照终点序号从大到小链接的，则按此给出唯一一种拓扑序列。02531469873.空堆开始依次向堆中插入线性表（64,

14、52, 12,48,45,26）中的每个元素，请以线性表的形式给出每插入一个元素后堆的状态。（为小根堆）在一份电文中共使用五种字符：a，g，f，u，y，z，它们的出现频率依次为12,9,18,7,14，11，求出每个字符的哈夫曼编码。5假定一个待散列存储的线性表为 (37,65,25,73,42,91,45,36,18,75)， 散列地址空间为ht12，若采用除留余数法构造散列函数和链接法处理冲突，试求出每一元素的散列地址，画出最后得到的散列表，求出平均查找长度。6对于下图，若按照克鲁斯卡尔算法产生最小生成树，写出得到的各条边的次序。312314255106420198933753113341

15、57有七个带权结点，其权值分别为3,7,8,2,6,10,14，试以它们为叶子结点构造一棵哈夫曼树，并计算出带权路径长度wpl。8。已知一组记录的排序码为（46，79，56，38，40，80, 95，24），写出对其进行快速排序的每一次划分结果。9已知一个中缀算术表达式为： 25-（6/15）+（15/8） ，写出对应的后缀算术表达式。10在一份电文中共使用五种字符：a，g，f，u，y，z，它们的出现频率依次为4,9,8,17,14，11，求出每个字符的哈夫曼编码。11一个线性表为b=（12，23，45，57，20，03，78，31，15，36），设散列表为ht0.12，散列函数为h（key）

16、= key % 13并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。四、阅读算法，回答问题1int aa(lnode *hl , elemtype x) int n=0; lnode *p=hl;while (p!=null) if (p-data= =x) n+; p=p-next;return n;对于结点类型为lnode的单链表，以上算法的功能为：2int bb(elemtype a, int n, keytype k)for (int i=0;in;i+)if (ai.key = =k) break;if (in) return i;else retur

17、n 1;该算法的功能是：3 void cc( stack &s)pop(s);push(s,50);push(s,45);peek(s);假定调用算法时栈s 中已有2个元素（23，16）的栈，其中23时栈底，调用后得到的栈内容为（从栈底开始排列）：4void dd(elemtype a,int n)elemtype x;int i,j,flag;for(i=1;i=i;j_)if (aj.stndata=item; lnode *p=hl; while ( p-next!=hl ) p=p-next;newptr-next=hl;p-next=newptr;对于结点类型为lnode的单链表，以

18、上算法的功能为：6void ff(list &l)int i=0;while (il.size)int j=i+1;while (jl.size)if(l.listj = =l.list)for (int k=j+1;kl.size;k+)l.listk-1=l.listk;l.size-;else j+;i+;以上算法的功能为：7void gg(btreenode * & bst )elemtype a6 =45，23，78，35，77，25；bst=null；for( int i=0,i6;i+)insert(bst , ai);调用该算法后，生成的二叉搜索数的中序序列为：8void hh

19、 ( )elemtype a =1,3,5,7,9,2,4,6,8,10,b10;twomerge(a, b,0,4,9);for ( int i=0; i10; i+)coutbi” “;coutnext;q-next=hl;hl=q;对于结点类型为lnode的单链表，以上算法的功能为：10 void jj(list &la)initlist(la);int a=78,26,56,27,34,42;for(i=0; i3; i+)insertfront(la,ai);for(i=3; i6; i+)insertrear(la,ai);traverselist(la);该算法执行后得到的线性表

20、la为：11void kk (btreenode *bt)if(bt!=null)coutdata;if(bt-left!=null|bt-right!=null)coutleft);if (bt-right !=null)coutright);couttag= =true)int dep=ll(gl-sublist);if (depmax) max=dep;gl=gl-next;return max+1;以上算法的功能为：13 void cc( stack &s)pop(s);push(s,50);push(s,45);peek(s);假定调用算法时栈s 中已有2个元素（23，16）的栈，其

21、中23时栈底，调用后得到的栈内容为（从栈底开始排列）：14写出以下函数的功能。bool aa(btreenode * bst,elemtype & item) if (bst= = null) return false;else if (item= =bstdata) item =bstdta;return true; else if (item right=p-right; if (p-right) p-right-left=q; q-left=p; p-right=q;3邻接距阵、邻接表、边集数组4a b c d e f c b d a e f c d b f e a a b e c d

22、f 5堆尾、堆顶、向下6有序序列7顺序结构、链接结构、索引结构、散列结构82i+1、2i+2、9栈顶元素、栈顶指针106 112、2、0、712n(n-1)/2 、n(n-1)13稠密、稀疏 14二叉搜索树、理想平衡树152 、用户定义 16o(n)、o(m*n) 17o(n) 、o(nlog2n) 、 o(n)18 、 m-1 、 、 m 19堆尾、堆顶、向下20o(nlog2n) 、 o(n2)21查找成功、左子树、右子树22p-next=hl; hl=p;23 2i+1、2i+2、24 表头25 b、e f g26 6327 31、1628 有序序列29 hlnext =null、 hl

23、=hlnext30 3、3、2三、运算题1后缀算术表达式：3 4 25 6 15 / * 8 2拓扑序列为：1 4 0 2 3 6 5 7 8 93（64）（52，64）（12，64，52）（12，48，52，64）（12，45，52，64，48）（12，45，26，64，48，52）4 a：111 g：011 f：10u：010 y：00 z：110（或0、1 相反）50123456789101173652537189145364275平均查找长度asl=( 7*1+2*2+3*1)/10=1.46（3，4）5，（0，1）8，（4，5）9，（4，7）10，（2，4）14，（1，3）15，（4

24、，6）317.带权路径长度wpl=131。哈夫曼树为：502129101114155678328 38 24 40 46 56 80 95 7924 38 40 46 56 80 95 7924 38 40 46 56 80 95 7924 38 40 46 56 80 95 7924 38 40 46 56 79 80 9524 38 40 46 56 79 80 959后缀算术表达式：25 6 15 / -15 8 / +10带权路径长度wpl=158。哈夫曼树为：2663143717201291148a：000 g：100 f：001 u：11 y：01 z：101 （或0和1相反）11

25、 0 1 2 3 4 5 6 7 8 9 10 11 1278150357452031233612查找成功的平均查找长度：asl succ=14/10= 1.4四、阅读算法，回答问题1统计单链表中结点的值等于给定值x的结点数。2在具有n个元素的顺序表a中，顺序查找关键字为k 的元素。3栈内容为（从栈底开始排列）：23，50，45。4对数组a中的n个元素进行排序，称为起泡算法。5向单链表的末尾添加一个元素。6删除线性表中所有重复的元素。723 25 35 45 77 788 1 2 3 4 5 6 7 8 9 109将一个单链表按逆序链接。10（56，26，78，27，34，42）11把二叉树以

26、广义表形式输出。12计算广义表深度。13栈内容为（从栈底开始排列）：23，50，45。14在二叉搜索树上查找等于给定值 item的元素。五、编写算法1elemtype findmax (btreenode *bst)if (bst= =null)cerr”不能在空树上查找最小值！”left!=null)t=t-left;return t-data;2int binsch(indexlist b, int m, indexkeytype k)int low=0, high=m-1;while (low= high)int mid=(low+high)/2;if (k= =bmid. index

27、)return bmid.start;else if (kbmid.index)high=mid-1;elselow=mid+1;if (lowleft;if (top!=-1)p=stop;top-;coutdataright;4bool delete(list& l, elemtype x) for (int i=0; il.size;i+) if (l.listi=x) break; if (i=l.size) return false;for(int j=i+1;jdata=item;p-left=p-right=null;bst=p;else if (itemdata, item) insert(bst-left, i