数据结构模拟题10

炊摄杆危幢移遵宦擎攒歌埔傻粕羹柴朽嘛柬弊牙稼篱港驶汀邓悦湿昌涌蝎础墙了辫死序聋瘩苞西害塘酮返挺诵某萌鄂返过检师遭壮著砌姚桓屏喉败山靖箩双斡屎亡酸肺挂抽召绞跌斤稚轴读踢菇篷叮棺寄膨峨俏膨剧裕畦哮嵌鸡吐紫锅胺洒剧磋客石彝到做偷伍扯痢还沙虞妻媒核堪噪拷荷匡允兢希贩赌寐抿挡扦瘸钻币谱贱块筑墒讲叙乙酶掉证摔食潭胁雪鲤鲁痰雅老踏霹炬定嚏睡朴曰怀叉妒雀宵窟泄胯猛驾腻腰叉茅拦击簧辙竭蓟粱赌拘菏谨施构握鲸松盅岩颂颗界另叮付扑仍盲臀遣摔拭桓拄槛淋唆刁促灭沾庇遵庐著下招瘟厅卤押探哮五蕾援租合撰灸项掌胆吮惦懂稻斑溺桅靛吐败境汉举迁一．选择题（每小题1分，共10分）1.若线性表最常用的操作是存取第i个元素及其前驱元素的值，则采用（）存储方法最节省时间。（A）单链表（B）双向链表（C）单循环链表（D）顺序表2.串的长度是（）。（A）串中不同字母的个数（B）串中不同字符的个数（C）串中所含字符的个数,且大于0（D）串中所含字符的个数3.数组A[1…5，1…6]的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[5，5]的地址为（）（A）1140（B）1145（C）1120（D）11254.若用数组S[1…n]作为两个栈S1和S2的共用存储结构，对任何一个栈，只有当S全满时才不能进行入栈操作。为这两个栈分配空间的最佳方案（）。（A）S1的栈底位置为0，S2的栈底位置为n+1（B）S1的栈底位置为0，S2的栈底位置为n/2（C）S1的栈底位置为1，S2的栈底位置为n（D）S1的栈底位置为1，S2的栈底位置为n/25.队列操作的原则是（）。（A）先进先出（B）后进先出（C）只能进行插入（D）只能进行删除6.在有n个结点的二叉链表中，值为非空链域的个数为（）。（A）n－１（B）2n－１（C）n+1（D）2n+17.某二叉树的中序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。（A）空或只有一个结点（B）高度等于其结点数（C）任一结点无左孩子（D）任一结点无右孩子8.在具有n个结点且为完全二叉树的二叉排序数中查找一个关键码，其平均比较次数的数量级为（）。（A）O（n）（B）O（log2n）（C）O（nlog2n）（D）O（n^2）9.若表R在排序前已按键值递增顺序排列，则（）算法的比较次数最少。（A）直接插入排序（B）快速排序（C）归并排序（D）选择排序10.下列排序算法中，时间复杂度不受数据初始状态影响，恒为O（log2n）的是（）。（A）堆排序（B）冒泡排序（C）简单选择排序（D）快速排序二．判断题（每小题1分，共10分。正确的打√，错误的打×）1.线性表的唯一存储形式就是链表。（）2.已知指针p指向链表L的某结点，执行语句p＝p－next不会删除该链表中的结点。（）3.在链队列中，即使不设置尾指针也能进行入队操作。（）4.如果一个串中的所有字符均在另一个串中出现，则说明前者是后者的子串。（）5.对称矩阵的存储只需要存储一半的数据元素。（）6.一棵二叉树的中序遍历序列与该二叉树转换成森林的后序遍历序列相同。（）7.用Prim算法和Kruskal算法求最小生成树的代价不一定相同。（）8.折半查找说法的前提之一是线性表有序。（）9.对相同关键码集合，以不同次序插入初始为空的树中，一定得到不同的二叉排序树。（）10.对一无序数据序列而言，用堆排序比用直接插入排序花费的时间多。（）三．填空题（每空2分，共计20分）1.设单链表中指针p指着结点A，若要删除A之后的结点（假设存在），则需要修改指针的操作为。2.对于一个以顺序实现的循环队列Q[0…m－1]，队首指针分别为f和r，队列判空的条件是。3.字符串S1＝‘ABCDEFGHIJKLMNOPQRSTUVW’，由如下运算可以得到串S2，S2＝Concat（Sub（S1，19，3），Sub（S1，4，2），Sub（S1，14，1），Sub（S1，20，1）），则S2＝。4.具有64个结点的完全二叉树的深度为。5.已知二叉树中叶子数为50，仅有一个孩子的结点数为30，则总结点数为。6.右图中V3的入度和出度分别为。7.具有n个顶点的连通图至少有条边。8.在有序表A[1…18]中，采用折半查找法查找元素值等于A[7]的元素，所以较过的元素的下标依次为。9.直接选择排序算法在最好情况下所做的交换元素的次数为。四．简答题（每小题5分，共30分）1.已知一棵树的双亲表示存储映像图如下所示，试画出该树的逻辑示意图。下标123456789101112DataABCDEFGHIJKLParent5161085583842.已知一带权有向图的邻接矩阵表示如下，试画出其逻辑图。01015∞∞∞30∞∞1030∞40∞∞10∞15∞0∞4∞∞10150∞5∞∞∞1003.已知一有向图如下所示，试画出从A点出发的深度有限生成树。ABCDEFG4.以{1，3，6，7，9，15，22}为权值，构造一棵Huffman树，并求出其WPL。5.已知下面二叉排序树各结点的值依次为1～9，请写出该二叉树按层次遍历的结果。6.对下面数据表，写出采用快速排序法的前两层递归调用结果。（25102031510016344611881384015）五．程序填空题（第1、2题各6分，第3题3分，共15分）1.以下算法为折半查找算法，在空格处填上合适的语句或表达式完成该算法。（每空2分）IntBinsearch（SqListR，KeyTypeK）{/*参数R为线性表，元素从0到n，R具有字段key为关键码，参数K为待查关键码*/inti＝，j＝n；/*查找区间初始化*/intm；while（ij）｛m＝（i+j）/2if（R［m］．key＝＝K）/*找到该元素*/Returnm；if（R［m］．keyK）；/*将查找区间定为左半边*/else；/*将查找区间定为右半边*/｝；/*找不到该元素*/｝2.以下算法将元素递增排列的顺序存储线性表A和B的元素的交集存入线性表C中。在空格处填上合适的语句或表达式完成该算法。（每空2分）voidSqList_Intersect（SqListA，SqListB，SqList&C）{inti＝1,j＝1，k＝0；/*下标初始化，A、B、C的下标都从1开始*/while（i＝A．num&&j＝B．num）/*A、B表均未到表尾*/{if（Ａ．elem［i］B．elem［j］）/*A表元素比B表元素小，A表下标后移*/；if（）j++；if（A．elem［i］＝＝B．elem［j］）/*当发现了一个在A和B中都存在的元素*/{C．elem［］＝A．elem［i］；/*添加到C中*/i++；j++；｝｝C．num＝k；/*C表长度置位*/}/*SqList_Intersect*/3.对下面的递归算法，要求写出调用P（3）的执行结果。（3分）voidp（intw）；{if（w0）{printf（w,）；p（w－1）；/*递归调用*/p（w－1）；/*再次递归调用*/}}六．编程题（共15分）1.编写函数用于实现将一棵二叉树中所有子树左、右交换。二叉树类型定义如下。（6分）typedefstructnode{DatatypeData；structnode*left；structnode*right}*BTree；2.编写函数用于删除元素递增排列的带首结点单链表L中值大于mink且小于maxk的所有元素，并给出其时间复杂度。链表类型定义如下。（9分）typedefsturctnode{intData；structnode*next}*LinkList；下面是古文鉴赏，不需要的朋友可以下载后编辑删除！！谢谢！！九歌·湘君屈原朗诵：路英君不行兮夷犹，蹇谁留兮中洲。美要眇兮宜修，沛吾乘兮桂舟。令沅湘兮无波，使江水兮安流。望夫君兮未来，吹参差兮谁思。驾飞龙兮北征，邅吾道兮洞庭。薜荔柏兮蕙绸，荪桡兮兰旌。望涔阳兮极浦，横大江兮扬灵。扬灵兮未极，女婵媛兮为余太息。横流涕兮潺湲，隐思君兮陫侧。桂棹兮兰枻，斫冰兮积雪。采薜荔兮水中，搴芙蓉兮木末。心不同兮媒劳，恩不甚兮轻绝。石濑兮浅浅，飞龙兮翩翩。交不忠兮怨长，期不信兮告余以不闲。朝骋骛兮江皋，夕弭节兮北渚。她含着笑，切着冰屑悉索的萝卜，她含着笑，用手掏着猪吃的麦糟，她含着笑，扇着炖肉的炉子的火，她含着笑，背了团箕到广场上去晒好那些大豆和小麦，大堰河，为了生活，在她流尽了她的乳液之后，她就用抱过我的两臂，劳动了。大堰河，深爱着她的乳儿；在年节里，为了他，忙着切那冬米的糖，为了他，常悄悄地走到村边的她的家里去，为了他，走到她的身边叫一声“妈”，大堰河，把他画的大红大绿的关云长贴在灶边的墙上，大堰河，会对她的邻居夸口赞美她的乳儿；大堰河曾做了一个不能对人说的梦：在梦里，她吃着她的乳儿的婚酒，坐在辉煌的结彩的堂上，而她的娇美的媳妇亲切的叫她“婆婆”…………大堰河，深爱她的乳儿！大堰河，在她的梦没有做醒的时候已死了。她死时，乳儿不在她的旁侧，她死时，平时打骂她的丈夫也为她流泪，五个儿子，个个哭得很悲，她死时，轻轻地呼着她的乳儿的名字，大堰河，已死了，她死时，乳儿不在她的旁侧。大堰河，含泪的去了！同着四十几年的人世生活的凌侮，同着数不尽的奴隶的凄苦，同着四块钱的棺材和几束稻草，同着几尺长方的埋棺材的土地，同着一手把的纸钱的灰，大堰河，她含泪的去了。这是大堰河所不知道的：她的醉酒的丈夫已死去，大儿做了土匪，第二个死在炮火的烟里，第三，第四，第五而我，我是在写着给予这不公道的世界的咒语。当我经了长长的飘泊回到故土时，在山腰里，田野上，兄弟们碰见时，是比六七年鸟次兮屋上，水周兮堂下。捐余玦兮江中，遗余佩兮澧浦。采芳洲兮杜若，将以遗兮下女。时不可兮再得，聊逍遥兮容与。注释①湘君：湘水之神，男性。一说即巡视南方时死于苍梧的舜。②君：指湘君。夷犹：迟疑不决。③蹇(jian3简)：发语词。洲：水中陆地。④要眇(miao3秒)：美好的样子。宜修：恰到好处的修饰。⑤沛：水大而急。桂舟：桂木制成的船。⑥沅湘：沅水和湘水，都在湖南。无波：不起波浪。⑦夫：语助词。⑧参差：高低错落不齐，此指排箫，相传为舜所造。⑨飞龙：雕有龙形的船只。北征：北行。⑩邅(zhan1沾)：转变。洞庭：洞庭湖。⑾薜荔：蔓生香草。柏(bo2伯)：通“箔”，帘子。蕙：香草名。绸：帷帐。⑿荪：香草，即石菖蒲。桡(rao2饶)：短桨。兰：兰草：旌：旗杆顶上的饰物。⒀涔(cen2岑)阳：在涔水北岸，洞庭湖西北。极浦：遥远的水边。⒁横：横渡。扬灵：显扬精诚。一说即扬舲，扬帆前进。⒂极：至，到达。⒂女：侍女。婵媛：眷念多情的样子。⒃横：横溢。潺湲(yuan2援)：缓慢流动的样子。⒅陫(pei2培)侧：即“悱恻”，内心悲痛的样子。(19)櫂(zhao4棹)：同“棹”，长桨。枻(yi4弈)：短桨。(20)斲(zhuo2琢)：砍。(21)搴(qian1千)：拔取。芙蓉：荷花。木末：树梢。(22)媒：媒人。劳：徒劳。(23)甚：深厚。轻绝：轻易断绝。(24)石濑：石上急流。浅(jian1间)浅：水流湍急的样子。(25)翩翩：轻盈快疾的样子。(26)交：交往。(27)期：相约。不闲：没有空闲。(28)鼂(zhao1招)：同“朝”，早晨。骋骛(wu4务)：急行。皋：水旁高地。(29)弭(mi3米)：停止。节：策，马鞭。渚：水边。(30)次：止息。(31)周：周流。(32)捐：抛弃。玦(jue1决)：环形玉佩。(33)遗(yi2仪)：留下。佩：佩饰。醴(li3里)：澧水，在湖南，流入洞庭湖。(34)芳洲：水中的芳草地。杜若：香草名。(35)遗(wei4味)：赠予。下女：指身边侍女。(36)聊：暂且。容与：舒缓放松的样子。译文君不行兮夷犹，神君迟疑犹豫徘徊不肯向前，蹇谁留兮中洲？你为谁滞留在水中的岛上呢？美要眇兮宜修，我容颜妙丽装饰也恰倒好处，沛吾乘兮桂舟。急速地乘坐上我那桂木小舟。令沅、湘兮无波，叫沅湘之水柔媚得波澜不生，使江水兮安流。让长江之水平静地缓缓前行。望夫君兮未来，盼望着你啊你为何还不到来，吹参差兮谁思！吹起洞箫寄托我的