溫州大學(xué)2022年數(shù)據(jù)結(jié)構(gòu)考研真題

溫州大學(xué)2022年[數(shù)據(jù)結(jié)構(gòu)]考研真題一、單項(xiàng)選擇題1.計(jì)算機(jī)所處理的數(shù)據(jù)一般具有某種內(nèi)在聯(lián)系，這是指()o數(shù)據(jù)和數(shù)據(jù)之間存在某種關(guān)系數(shù)據(jù)元素和數(shù)據(jù)元素之間存在某種關(guān)系數(shù)據(jù)元素內(nèi)部具有某種結(jié)構(gòu)數(shù)據(jù)項(xiàng)和數(shù)據(jù)項(xiàng)之間存在某種關(guān)系順序存儲(chǔ)方式只能用于線性結(jié)構(gòu)，不能用于非線性結(jié)構(gòu)。這個(gè)斷言是()o正確的錯(cuò)誤的設(shè)某算法完成對(duì)n個(gè)元素進(jìn)行處理，所需的時(shí)間是：TOC\o"1-5"\h\zT(n)=100nlog2n+200n+500,則該算法的時(shí)間復(fù)雜度是( )。O(l)O(n)O(nlogn)O(nlogn+n)采用順序存儲(chǔ)的兩個(gè)棧它的共享空間為top[i]R表第i個(gè)棧(i=l,2)的棧頂，棧1的底在S[l],棧2的底在S[m],則棧滿的條件是()。top[2]-top[l]=0top[l]+l=top[2]top[l]+top[2]=mtop[l]=top[2]已知二叉樹有50個(gè)葉子結(jié)點(diǎn)，則該二叉樹的總結(jié)點(diǎn)數(shù)至少應(yīng)有（）個(gè)。99TOC\o"1-5"\h\z100101102無向圖G有16條邊，度為4的頂點(diǎn)有3個(gè)，度為3的頂點(diǎn)有4個(gè)，其余頂點(diǎn)的度均小于3,則圖G至少有（ ）個(gè)頂點(diǎn)。10111213對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無向圖，若采用鄰接矩陣表示，則該矩陣的大小是（）。n（n-l）/2n-1n2適合于折半查找的表的存儲(chǔ)方式及元素排列要求為（）。A.鏈接存儲(chǔ)，元素?zé)o序B.鏈接存儲(chǔ)，兀素有序C.順序存儲(chǔ),元素?zé)o序D.順序存儲(chǔ),元素有序排序算法的穩(wěn)定性是指（）o經(jīng)過排序之后，能使值相同的數(shù)據(jù)保持原順序中的相對(duì)位置不變經(jīng)過排序之后，能使值相同的數(shù)據(jù)保持原順序中的絕對(duì)位置不變排序算法的性能與待排序元素的數(shù)量關(guān)系不大排序算法的性能與待排序元素的數(shù)量關(guān)系密切10.5個(gè)不同的數(shù)據(jù)元素進(jìn)行直接插入排序，最多需要進(jìn)行( )次比較。A.8 B.14C.15 D.25二、簡(jiǎn)答題找出滿足以下條件的所有二叉樹：二叉樹的前序序列與中序序列相同；二叉樹的中序序列與后序序列相同；二叉樹的前序序列與后序序列相同。假設(shè)通訊電文中只用到A,B,C,D,E,F六個(gè)字母，它們?cè)陔娢闹谐霈F(xiàn)的相對(duì)頻率分別為：8,3,16,10,5,20o構(gòu)造哈夫曼樹。計(jì)算該哈夫曼樹的帶權(quán)路徑長(zhǎng)度WPLO己知序列{355,672,91,83,781,34,410,76,125,320),建大根堆。已知序列{12,2,16,30,8,28,4,10,20,6,18},請(qǐng)按照下面的快速排序算法,給出該序列作升序排列時(shí)前三趟的結(jié)果。intpartition(ElementTyper[]zintlow,inthigh){intpivot;.pivot=r[low];while(low<high){while(low<high&&r[high]>=pivot)(high-;TOC\o"1-5"\h\z}.r[low]=r[high];while(low<high&&r[low]<=pivot)(low++;}r[high]=r[low];}r[low]=pivot;returnlow;}voidqSort(ElementTyper[]zintlow,inthigh){intpos;if(low<high){pos=partition(rzlowzhigh);/*將r[low..high]—分為二*/qSortfr,low,pos-1);/*對(duì)左邊子表快速排序*/qSort(rzpos+Lhigh);/*對(duì)右邊子表快速排序*/}■}voidquickSort(ElementTyper[],intn)(qSort(r,bn);}三、算法設(shè)計(jì)題］編寫一個(gè)算法，實(shí)現(xiàn)單鏈表原地逆轉(zhuǎn)，逆轉(zhuǎn)操作不使用額外的鏈表結(jié)點(diǎn)。單鏈表的存儲(chǔ)結(jié)構(gòu)描述如下：typedefintElementType;typedefstructNode(/*結(jié)點(diǎn)類型定義*/ElementTypedata;structNode*next;}Nodez*LinkList;/*LinkList為結(jié)構(gòu)指針類型*/給定的函數(shù)原型如下：voidreverseList(LinkListL);設(shè)計(jì)判斷二叉樹是否為二叉排序樹的算法。二叉排序樹的結(jié)構(gòu)如下：typedefintKeyType;typedefstructNode{KeyTypekey;/*關(guān)鍵字的值*/structNode*left;/*左扌旨針*/structNode*right;/*右指針*/}BSTNodez*BSTree;編寫一個(gè)算法，對(duì)順序表進(jìn)行二分查找。順序表的存儲(chǔ)結(jié)構(gòu)描述如下：typedefintElementType;typedefstruct(ElementType*array;/*存放元素的數(shù)組*/intlength; /*已經(jīng)有多少元素*/intcapacity; /*容量*/}SeqList;給定的函數(shù)原型如下：intbinarySearch(SeqListlist,ElementTypek);給定無向帶權(quán)圖，編寫最小生成樹算法(Prim)。預(yù)置代碼如下：#include<stdio.h>#include<stdlib.h>#include<limits.h>#defineMAXVEX200/*最大頂點(diǎn)數(shù)*/typedefcharVertexType;structGraphStruct;typedefstructGraphStruct*Graph;typedefstructENode(intadjVertex;/*該邊所指的頂點(diǎn)的位置*/intweight; /*邊的權(quán)*/structENode*nextEdge;/*指向下一條邊的指針*/}ENode;typedefstructVNode{VertexTypedata;/*頂點(diǎn)信息*/ENode*firstEdge;/*指向第一條依附該頂點(diǎn)的邊的弧指針*/JVNode;structGraphStruct{VNodevexs[MAXVEX];intvertexNum,edgeNum;/*圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)*/)；intPrim(Graphg,VertexTypeu);intmain()(Graphg=createGraph();/*此處由測(cè)試代碼自動(dòng)添加，用于測(cè)試intPrim(Gra