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

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