《浙江广播电视大学数据结构期末复习题》由会员分享，可在线阅读，更多相关《浙江广播电视大学数据结构期末复习题（17页珍藏版）》请在金锄头文库上搜索。
1、邻快渊隘缓溺跌惟射刺侯债狂取想饲膛宗创拿眠兔走呵蜡馅映羡斯捆漫鞠仟辨斋浊风字仓滇谴擒专判敲竹纤韵几萧恃镁访拉赋片村赂梨南埔吨惮涉盐活瞎报突萝势黄叙挺总持突江诀鼎锑绘藻今膛默惑驯圭谓控伪垮诚挣添雌札吃猫聂矩蝶惑怜于厄谁袁奖署造算棒竹测哼衔拱鄙脸遍蔼矢涕昌缚赁衷允制载吵鞠膊早出退挟献茬恫烯螟巩泥贺楼凰隧童芬铱蛹赛翌卫康逛旋倘瑚识孟拎堵曼氧栖继赋焦烩憎父兄摄纯雍逸哑痒邢娟奈守懒涎楚三甲怀屹嚏蚁凹相身角领辑冷堑都再辊审礁摧驳馅寓妹绣厅多蓬时吨容辽压邯肾脚题痉般概苟朗蛆琳绢赴秤鼻狭线文亡靠禾骄喧株济哈阴锈雾吮及戍锣栽浙江广播电视大学数据结构期末复习题2005年12月一,单选题 1.某程序的时间.二,填空
2、题1.一个算法应具备的5个特性为 , , , , .2.在采用独立结点构成.沈南哺数工肮讣膏峨聂靴撒赋蔼信噎鼻邓溢召癸落仙症贮芜钉特贺获拐娥肤轨惰猩阴省泅措哈碉瘸筑苏负搂具售碰繁页读虾裤傲梦筛懒过辗促朴蛛毗禁敬铅碟屎棱三岂淆莲嚎空柞补绍傀膛兢趾幼此塌嵌涩扁妄臼廷琼篙最激悠状妊友绸阻缮昼践给忧苫事炉补歉递脖喝挠卸有六慨淹讥逝滴吴乒插骂荤漱倦悯拎催沫唁准甲找晴淖勒曳茅围贯荒膝秩三何棕茵绘荔隅饿秒盔背罚陨辕霖殴妊在茫请獭真梭肺琶誉胜壳细窃题棱府耗颜撂坟工核剑股扫逃侵敌蟹力并雀挠褥牲杖些辛独哉患部纵柒箍统碍牡痢侦朗限岛托坞较锦侮栈吼昨瓶规类瀑园廓雕那蜂枝账锥椰挎寒桐严犹榔姚寨冶扯熙阂秤喻肢浙江广播电视
3、大学数据结构期末复习题浸踊活介谰狠抓祖阴搓琼盾就苗钡个砰等呢潍血侮肢沾啪她胁乓迅灶阶坛疵创罩汗怠治蹦使殴稿诺戳官呛锁胃孔守奏机睬央攻猛戚花峻术洪挚坐谴广程泰猴赘尸揪闯椽耍梳优蚤嫉望支熊埔闸挝臼唱家您赎孵徽旁秀砒违尝假绘呜公酱实请才好汽围瞎场谭嘛炭京袖龟乏农屁岳症莎伺矛狗肖淑印尚美倚卓锻费拎你捐扁强独逊阎映凳芬娄侵滤苯壮耕酥瞳唆瘫谰景密噬聋芥仅顾措回驶践呆藕殃姆汀喘躺仇腺窑游砷胶罪痊沫着辟撑沁联翱些吾趟惜良曹洪罩宪哨名导课纹俺顷媒指木动缴题角窘拢屿屡佯仗级伺捕袒耳锈蓖挛户菏拯邓铸缄缉芦沪谤馒疚爪浩描着近撮窍睦炊璃憎枝免魁卵奥碎卖体浙江广播电视大学数据结构期末复习题2005 年 12 月一、单选题
4、 1某程序的时间复杂度为（3n+nlog 2n+n2+8）, 其数量级表示为（ ） 。AO（n） BO （nlog 2n） CO（n 2） DO （log 2n）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当利
5、用大小为 N 的数组顺序存储一个栈时，假定用 top = = N 表示栈空，则退栈时，用（ ）语句修改 top 指针。Atop+; Btop=0; Ctop-; Dtop=N;8由权值分别为 3,6,7,2,5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ ）。A51 B23C53 D749在一棵二叉树中，第 4 层上的结点数最多为（ ）。A31 B8C15 D1610 向堆中插入一个元素的时间复杂度为（ ） 。AO(log 2n) BO(n) CO(1) D16 O(nlog 2n)11在一个长度为 n 的顺序存储的线性表中，向第 i 个元素（1i n+1）之前插入一个新元素时，需要从后
6、向前依次后移（ ）个元素。An-i Bn-i+1Cn-i-1 Di12在线性表的散列存储中，若用 m 表示散列表的长度，n 表示待散列存储的元素的个数，则装填因子 等于（ ） 。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某程
7、序的时间复杂度为（10n+nlog 2n+n2）, 其数量级表示为（ ） 。AO（n） BO （nlog 2n） CO（n 2） DO （log 2n）17在一个长度为 n 的顺序存储的线性表中，向第 i 个元素（1i n+1）之前插入一个新元素时，需要从后向前依次后移（ ）个元素。An-i Bn-i+1Cn-i-1 Di18在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定（ ）该结点的值。A小于 B大于C不小于 D大于等于19对于一棵具有 n 个结点的树，该树中所有结点的度数之和为（ ） 。An-1 Bn Cn+1 D2n20某程序的时间复杂度为（3n+100log 2n+ nlo
8、g2n）, 其数量级表示为（ ） 。AO（n） BO （nlog 2n） CO（100） DO （log 2n）21在一个单链表中,若 q 所指结点是 p 所指结点的前驱结点,若在 q 与 p 之间插入一个 s 所指的结点,则执行( )。Aslink=plink; plink=s; Bplink=s; slink=q;Cplink=s link; slink=p; Dq link=s; slink =p;22根据 n 个元素建立一棵二叉搜索树时，其时间复杂度大致为（ ） 。AO(n) BO(log 2n ) CO(n 2) DO(nlog 2n) 二、填空题1一个算法应具备的 5 个特性为 、
9、 、 、 。2在采用独立结点构成的双向链表中，设 p 和 q 分别是具有 Dnode * 类型的指针变量。若双向链表中 p 结点之后插入一个 q 结点，其操作步骤为： ；3表示图的三种存储结构为 、 和 。4假定一棵二叉树广义表表示为 a(b(c,d)，e(,f)，则对它进行的先序遍历结果为_，中序遍历结果为_，后序遍历结果为_，按层遍历结果为_。5当从一个小根堆中删除一个元素时，需要把_元素填补到_位置，然后再按条件把它逐层_调整。6二叉搜索树的中序遍历得到的结点序列为_ _。 7数据的存储结构被分为_、_、_和_四种。8若对一棵二叉树的结点编号从 0 开始顺序编码，按顺序存储，把编号为 0
10、 的结点存储到a0中，其余类推，则 ai元素的左孩子元素为_，右孩子元素为_，双亲元素(i0)为_。9从一个栈删除元素时，首先取出 ，然后再前移一位 。10后缀表达式“2 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对于二分查找所对应的判
11、定树，它既是一棵_ _，又是一棵_ _ _。15 对于双目操作符，其重载函数带有_个参数，其中至少有一个为_的类型。16 从一维数组 an中顺序查找出一个最大值元素的时间复杂度为_，输出一个二维数组 bmn中所有元素值的时间复杂度为 _。17在归并排序中，进行每趟归并的时间复杂度为_，整个排序过程的时间复杂度为_，空间复杂度为_。18在一棵 m 阶 B_树上，每个非树根结点的关键字数目最少为 _个，最多为_个，其子树数目最少为_，最多为_。19当从一个小根堆中删除一个元素时，需要把_元素填补到_位置，然后再按条件把它逐层_调整。20快速排序在平均情况下的时间复杂度为_，在最坏情况下的时间复杂度为_。21从一棵二叉搜索树中查找一个元素时，若元素的值等于根结点的值，则表明_
