《数据结构模拟试题5》由会员分享，可在线阅读，更多相关《数据结构模拟试题5（12页珍藏版）》请在金锄头文库上搜索。
1、选择题(30分)1下列程序的时间复杂度为()。for (i = 0; im ; i+ )for (j =0; jt; j+)c : i: : j =0；for (i = 0; jm ; i+ )for (j = 0; jt; j+ )for ( k= 0; jnext=s;s_prior=p;p-next-prior=s;s-next=p-next;(B) s_prior=p;s-n ext=p-n ext;p-n ext=s;p-n ext-prior=s;(C) p-n ext=s;p-n ext-prior=s;s-prior=p;s-n ext=p-n ext;(D) s-prior=
2、p;s-n ext=p-n ext;p-n ext-prior=s;p-n ext=s;6串的长度是()(A)串中不同字符的个数(B)串中不同字母的个数(C)串中所含字符的个数(n0)( D )串中所含字符的个数n(n =0)7. 若有一个栈的输入序列是1, 2,oooooo, n,输出序列的第一个兀素是n,则第i个输出兀素是()(A) n-i(B) n-i-1(C) n-i+1(D)不确定8. 设有一个栈，元素的进栈次序为A,B,C,D,E,下列()是不可能的出栈序列。(A ) A,B,C,D,E(B)B,C,D,E,(C)E,A,B,C,D(D)E,D,C,B,A9. 在一棵度为3的树中，
3、度为3的结点数有2个，度为2的结点数有1个，度为1的结点数 有2个，那么度为0的结点数有()个。(A) 4(B)5(C)6(D)710在一个具有n个结点的无向完全图中，包含有()条边。(A) n(n-1)/2(B)n(n-1)(C)n(n +1)/2(D)nn11采用顺序查找法查找长度为n的线性表，则查找每个元素的平均比较次数为() o(A) n(B)n/2(C)(n+1)/2(D)(n-1)/212已知一个有序表为（13, 18, 24, 35, 47, 50, 62, 83, 90, 115, 134）,当二分查找值 为90的元素时，需（）次比较可查找成功。（A）1（B）2（C）3（D）4
4、13. 在顺序存储的线性表R029上进行顺序查找的平均查找长度为（1）,进行二分查找的平均查找长度为（2）,进行分块查找（设分为5块）的平均查找长度为（3）。1, （ A）15（B）15.5（C）16（D）202, （A）4（B）62/15（C）64/15（D）25/63, （A）6（B）11（C）5（D）6.514. 在所有排序方法中，关键码的比较次数与记录的初始排无关的是（）（A）Shell排序（B）冒泡排序（C）直接插入排序（D）直接选择排序15. 已知8个元素（34, 76, 45, 18, 26, 54, 92, 65）,按照依次插入结点的方法生成一棵 二叉排序树，该树的深度为（）（
5、A） 4（B）5（C）6（D）72, 填空题1，若要一个单链表的*p结点之前插入一个*s结点时，可执行下列操作：s-next=;p-next=s;t=p-data;p-data=;s-data=;.2, 计算机软件系统中有两种处理字符串长度的方法，一种是采用,另一种是3. 假定对线性表 R059进行分块查找，共分 10块，每块长度等于 6。若假定查找索引表和块均用顺序查找法，则查找每一个元素的平均查找时间为（）。4. 一组记录（50, 40, 95, 20, 15, 70, 60, 45, 80）进行冒泡排序时，第一趟需进行相邻记录的交换次数为,在整个排序过程中共需进行 趟才可以完成。5. 在
6、堆排序、快速排序和归并排序中， 若从节省存储空间考虑， 则应首先选取 方法，其次选 方法，最后选 方法；若从排序结构的稳定性考虑，则应选择方法；若只从平均情况下排序的速度来考虑，则选择方法；若只从最坏情况下排序最快并且要节省内存考虑，则应该取 方法。3, 判断题1，数据元素是数据的最小单元。（）2. 在单链表中任何两个元素的存储位置之间都有固定的联系，因此可以从首结点进行查找任何一个元素。（）3. 设有两个串p和q,其中q是p的子串，把q和p中首次出现的位置作为 q和p中 的位置的算法称为匹配。（）4. 若有一个叶子结点是某子树的中序遍历的最后一个结点，则它必须是该子树的先序遍历的最后一个结点
7、。（）5. 对于n个记录的集合进行冒泡排序，在最坏情况下的时间复杂度为O（n*n）。（）6. 用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间与图中结点的个数有关，而与图的边数无关。 （）7. 哈希表的查找效率主要取决于哈希建表时所取的哈希函数和处理冲突的方法。（ ）8. 因为算法和程序没有区别，所以在数据结构中二者是通用的。（）9. 按中序遍历一棵二叉排序树所得到的中序遍历序列是一个递增序列。（）10. 进栈操作push（x,s）作用于链接栈时，无需判满。（）4, 应用题1，已知一个长度为 12 的表Jan ,Feb,Mar,Apr,May,June,July,Aug,S
8、eq,Oct,Nov,Dec。（1 ）试按表中元素的次序依次插入一棵初始为空的二叉排序树，字符之间以字典 顺序比较大小，并画出对应的二叉排序树，且求出在等概率情况下查找成功的平均查找长度。（2）若对表中元素先排序构成有序表，试求在等概率情况下对此有序表进行折半查找成功 的平均查找长度。2已知一棵二叉树的中序序列和后序序列分别为BCDEAFHG和DECBHGFA,画出这棵二叉树。3假设用于通信的电文仅有8个字母组成，字母在电文中出现的频率分别为7，19, 2, 6，32，3，3，21，10，试为这8个字母设计哈夫曼编码。4判别以下序列是否为堆，如果不是，则把它调整为堆。（1）（ 100，86，4
9、8，73，35，49，42，57，66，21）；（2）（ 12，70，33，65，24，56，48，92，86，33）；（3）（ 103，97，56，38，66，23，42，12，30，52，06，20）;5, 算法设计1。已知线性表的元素按递增顺序排列，并以带首结点的单链表作为存储结构。试编写一个删除表中所有值大于min且小于max的元素算法。2. 试设计一个算法，求出指定结点在给定的二叉树中的层次。3在含有n个元素的堆中增加一个元素，且调整为堆。4. 试设计将数组 A : 0N 1 中所有奇数移到所有偶数之前的算法，要求不另外增加 存储空间，且时间复杂度为0（n ）。F面是古文鉴赏，不需要
10、的朋友可以下载后编辑删除！谢谢！九歌湘君屈原朗诵：路英君不行兮夷犹，蹇谁留兮中洲。 美要眇兮宜修，沛吾乘兮桂舟。令沅湘兮无波，使江水兮安流。望夫君兮未来，吹参差兮谁思。驾飞龙兮北征，邅吾道兮洞庭。薜荔柏兮蕙绸，荪桡兮兰旌。望涔阳兮极浦，横大江兮扬灵。扬灵兮未极，女婵媛兮为余太息。横流涕兮潺湲，隐思君兮陫侧。桂棹兮兰枻，斫冰兮积雪。采薜荔兮水中，搴芙蓉兮木末。心不同兮媒劳，恩不甚兮轻绝。石濑兮浅浅，飞龙兮翩翩。交不忠兮怨长，期不信兮告余以不闲。朝骋骛兮江皋，夕弭节兮北渚。她含着笑，切着冰屑悉索的萝卜,她含着笑，用手掏着猪吃的麦糟， 她含着笑，扇着炖肉的炉子的火， 她含着笑，背了团箕到广场上去晒好
11、那些大豆和小麦，大堰河，为了生活， 在她流尽了她的乳液之后,她就用抱过我的两臂，劳动了。大堰河，深爱着她的乳儿；在年节里，为了他，忙着切那冬米的糖， 为了他，常悄悄地走到村边的她的家里去, 为了他，走到她的身边叫一声妈， 大堰河，把他画的大红大绿的关云长 贴在灶边的墙上，大堰河，会对她的邻居夸口赞美她的乳儿; 大堰河曾做了一个不能对人说的梦： 在梦里，她吃着她的乳儿的婚酒，坐在辉煌的结彩的堂上，而她的娇美的媳妇亲切的叫她“婆婆” 大堰河，深爱她的乳儿！ 大堰河，在她的梦没有做醒的时候已死了。 她死时，乳儿不在她的旁侧，她死时，平时打骂她的丈夫也为她流泪， 五个儿子，个个哭得很悲，她死时，轻轻地
12、呼着她的乳儿的名字， 大堰河，已死了，她死时，乳儿不在她的旁侧。 大堰河，含泪的去了！ 同着四十几年的人世生活的凌侮， 同着数不尽的奴隶的凄苦， 同着四块钱的棺材和几束稻草， 同着几尺长方的埋棺材的土地， 同着一手把的纸钱的灰， 大堰河，她含泪的去了。 这是大堰河所不知道的： 她的醉酒的丈夫已死去， 大儿做了土匪， 第二个死在炮火的烟里， 第三，第四，第五 而我，我是在写着给予这不公道的世界的咒语。 当我经了长长的飘泊回到故土时， 在山腰里，田野上，兄弟们碰见时，是比六七年 鸟次兮屋上，水周兮堂下。捐余玦兮江中，遗余佩兮澧浦。 采芳洲兮杜若，将以遗兮下女。 时不可兮再得，聊逍遥兮容与。注释湘君
13、：湘水之神，男性。一说即巡视南方时死于苍梧的舜。君：指湘君。夷犹：迟疑不决。蹇(jian3简)：发语词。洲：水中陆地。要眇(miao3秒):美好的样子。宜修：恰到好处的修饰。 沛：水大而急。桂舟：桂木制成的船。 沅湘：沅水和湘水，都在湖南。无波：不起波浪。- 夫：语助词。 参差：高低错落不齐，此指排箫，相传为舜所造。 飞龙：雕有龙形的船只。北征：北行。 邅(zhan1沾)：转变。洞庭：洞庭湖。(11) 薜荔：蔓生香草。柏(bo2伯)：通“箔”，帘子。蕙：香草名。绸：帷帐。(12) 荪：香草，即石菖蒲。桡 (rao2饶):短桨。兰：兰草：旌：旗杆顶上的饰物。(13) 涔(cen2岑)阳：在涔水北岸，洞庭湖西北。极浦：遥远的水边。(18) 陫(pei2培)侧：即“悱恻”，内心悲痛的样子。(19) 櫂(zhao4棹)：同“棹”，长桨。枻(yi4弈)：短桨。(20) 斲(zhuo2 琢):砍。(21) 搴(qian1千):拔取。芙蓉：荷花。木末：树梢。(22) 媒：媒人。劳：徒劳。(23) 甚：深厚。轻绝：轻易断绝。(24) 石濑：石上急流。浅(jian1间)浅：水流湍急的样子。(25)
