山東省專升本考試數據構造真題一、判斷題（10分。本大題共10小題，每題1分，在小題左面用√表達是，×表達否）1.線性表的次序存儲構造是一種隨機存儲構造。（）2.一種棧的入棧序列是a,b,c,d,e，則dceab是一種不也許的輸出序列。（）3.廣義表(a,(a,b),d,e,((i,j),k))的深度是2。（）4.樹是一種重要的線性數據構造。（）5.按照二叉樹的定義，具有三個結點的二叉樹有5種。（）6.已知一種有向圖的鄰接矩陣表達，計算第i個結點的出度的措施是求矩陣第i列非零元的個數。（）7.將遞歸算法轉換為對應的非遞歸算法時，一般需要使用隊列。（）8.在哈夫曼編碼中，當兩個字符出現的頻率相似時，其編碼也相似。（）9.散列法存儲的基本思想是由關鍵字的值決定數據的存儲地址。（）10.（101，88，46，70，34，39，45，58，66，10）是堆。（）二、填空題（15分。本大題共5小題，5個空，每個空3分，將對的答案填在空格處）。1.將下三角矩陣A[1..8,1..8]的下三角部分逐行地存儲到起始地址為1000的內存單元中，已知每個元素占4個單元，則A[7,5]的地址為___________。2.若某二叉樹有20個葉結點，有30個只有一種孩子的結點，則該二叉樹的總結點數為___________。3.假如以{4，5，6，7，8}作為葉子結點的權值構造哈夫曼樹，則其帶權途徑長度是___________。4.在次序存儲的二叉樹中，編號為i和編號為j的結點處在同一層的條件是___________。5.有一種有序表為{1，3，9，12，32，41，45，62，75，77，82，95，100}，當折半查找值為82的結點時，___________次比較後查找成功。三、（10分）已知關鍵字序列為{46，57，84，32，73，36，15，48，90，20}，規定：（1）構造一棵二叉排序樹；（2）在等概率狀況下，該二叉排序樹查找成功的平均查找長度。四、（8分）假設在長度不小于1的循環鏈表中，既無頭結點，也無頭指針，p為指向該鏈表中某個結點的指針。設計一種算法，刪除p指向結點的前趨結點。五.（7分）設算術體現式由字符串b表達，其中可以包括三種括號：圓括號、方括號和花括號，嵌套的次序任意，如{[()]()}是對的的。請編寫一種算法，實現鑒別給定體現式中所含括號與否對的配對。山東省專升本考試數據構造真題一、單項選擇題（10分、每題1分）1、在一種單鏈表，已知p所指向的是q所指向結點的前驅結點，若在q和p之間插入s所指向的結點，則執行（）A、s->next=q->next;q->next=sB、q->next=s->next;s->next=qC、p->next=s;s->next=qD、q->next=s;s->next=p2、串是（）A、某些符號構成的序列B、某些字母構成的序列C、一種以上的字符構成的序列D、任意有限個字符構成的序列3、數組A[10][10]的下標下界為1，每個元素占2個字節，存儲在起始地址為100的持續內存單元，則元素A[3][8]的地址為（）A、138B、154C、111D、1454、已知廣義表L=((x,y,z),a,(u,t,w)),則從L中取出原子項y的操作是（）A、head(tail(head(L)))B、head(head(tail(tail(tail(L)))))C、head(tail(tail(tail(tail(L)))))D、head(tail(tail(head(tail(L)))))5、已知完全二叉樹有80個結點，則整個二叉樹有____個度為2的結點。（）A、39B、41C、40D、386、赫夫曼樹中度為1的結點個數為（）A、0B、1C、2D、不確定7、具有n個頂點的有向完全圖，邊的總數為（）A、nB、n(n-1)C、n-1D、n(n-1)/28、二分查找法合用于存儲構造為____的，且按關鍵字排好序的線性表。（）A、次序存儲B、鏈接存儲C、次序存儲或鏈接存儲D、索引存儲9、下列排序算法中，第一趟排序結束後，其最大或最小元素一定在其最終位置上的算法是（）A、歸并排序B、直接插入排序C、迅速排序D、起泡排序10、一種有向無環圖的拓撲序列個數是（）A、1個B、1個或多種C、0個D、多種二、正誤判斷題（10分，對的打√，錯誤打×，每題1分）1、鏈表中結點數據域占的存儲空間越多，存儲密度越小。（）2、帶頭結點和不帶頭結點的單鏈表在查找、刪除、求長度等操作上無區別。（）3、假如兩個串串長相等且對應字符也相似，則這兩個串相等。（）4、壓縮存儲的三角矩陣和對稱矩陣的存儲空間不相似。（）5、滿二叉樹是完全二叉樹。（）6、對于給定的樹，與其對應的二叉樹是唯一的。（）7、線索二叉樹的指針域中，指向前驅或後繼的個數少于指向孩子的個數。（）8、給定圖的鄰接矩陣存儲不一定唯一。（）9、若一種有向圖的鄰接矩陣主對角線如下的元素均為0，則該圖拓撲有序序列存在。（）10、對n個記錄進行直接插入排序，其平均時間復雜度為O(nlog2n）。（）三、填空題（10分，1題每空2分，其他題每空1分）1、下列函數的功能是實現帶頭結點的單鏈表逆置。voidturn(slink*L){slink*p,*q;p=_____________________________;L->next=NULL;while(___________________________){q=p;p=___________________________;q->next=L->next;L->next=q;}}2、“算法”（Algorithm）就是對求解問題環節的一種描述，也稱為算法設計。它具有如下五個特性有窮性，_____________,_______________，輸入和輸出。3、評價算法好壞的五個方面_______________,_______________,對的性，可讀性，強健性。四、操作計算題（10分，每題5分）1、有一組關鍵字序列（24，19，56，13，97，59，41，85，1，87），寫出用堆排序法進行升序排序的初始堆序列及第一趟排序後的堆序列。2、給定如下圖所示的帶權無向圖G1。（1）畫出該圖的鄰接矩陣（2）給出采用普裏姆算法從頂點3出發構造最小生成樹的的過程。五、算法設計題（10分）給定二叉樹，采用鏈式構造存儲，編寫算法voidcount(BitTreebt),實現功能：記錄二叉樹中度為1的結點數目。山東省專升本考試數據構造真題一、填空題（10分，每空0.5分）1、根據數據元素之間關系的不一樣，數據的邏輯構造劃分為______、______、______、______。2、棧是一種特殊的線性表，它容許在表的一端進行____________操作，棧中元素的進出原則為__________________。深度為k的二叉樹其結點數最多有______個結點。4、一般象交通、道路問題的數學模型是一種稱為____________的數據構造。5、算法的五個重要的特性是______、______、______、______、______。6、兩個字符串相等的充足必要條件是____________________________________。7、在一棵二叉樹中，度為零的結點個數為，度為2的結點個數為，則有=______。8、樹的度是指__________________________________________的最大值。9、在一種有向圖中，某個結點的度是指該結點的______和______之和。10、在線性表的二分查找法中規定線性表的存儲構造必須是采用____________，且表中的元素必須是____________。二、選擇題（10分，每題1分）一種具有10個頂點的無向完全圖應有______條邊。()A.9 B.45 C.55 D.90長度為n（1…n）的次序循環隊列中，front和rear分別指示隊首和對尾，判斷隊列為滿隊列的條件是()A.rear=front B.(rear+1)%n=frontC.rear=0 D.front=0由______構成的集合是一種數據對象。()A.不一樣類型的數據項 B.不一樣類型的數據元素C.相似類型的數據項 D.相似類型的數據元素______是表達線性數據構造的。()A.循環鏈表 B.鄰接多重表C.孩子鏈表 D.單鏈表設一種棧的入棧元素序列為a，b，c，d，e，則不可得到出棧的元素序列有()。A.edcba B.decba C.dceab D.abcde______又是一棵滿二叉樹。()A.二叉排序樹 B.深度為5有31個結點的二叉樹C.有15個結點的完全二叉樹 D.哈夫曼（Huffman）樹折半查找有序表（2，5，8，20，25，36，40，60），若查找元素60，需依次與表中元素______進行比較。()A.20，36，40，60 B.25，40C.25，40，60 D.20，36，40查找哈希（Hash）表，處理沖突的措施有()。A.鏈地址法 B.線性探測再散列法C.直接地址法 D.除留余數法一種排序算法時間復雜度的大小______有關。()A.不與所需移動記錄的數目B.與該算法的穩定性C.與所需比較關鍵字的次數D.與所需輔助存儲空間的大小數據的基本單位是。()A.結點 B.數據元素 C.數據類型 D.數據項三、求解下列問題（10分，每題5分）1.將下面的一種一般書轉換成一棵二叉樹，并寫出它先序、中序、後序三種遍歷的遍歷序列。轉換後的二叉樹：先序遍歷序列：中序遍歷序列：後序遍歷序列：2.用克魯斯卡爾算法將下面的圖構導致最小生成樹，畫出生成過程。四、程序填空（10分，每空1分）1.將下面折半查找算法補充完整算法闡明：已知r[1…n]是n個記錄的遞增有序表，用折半查找法查找關鍵字為k的記錄，若查找失敗返回零；否則返回該記錄的序號值。查找表次序存儲構造定義如下：#define MAXSIZE 100typedef struct{ keytype key;}Nodetype;typedef Nodetype Sqlist[MAXSIZE];算法（C函數）：int binsearch(Sqlistr,datatypek,intn){ intlow=1,high=n,mid; while(_______________) { _______________; if(r[mid].key==k) _______________; elseif(r[mid].key>k) _______________ else _______________ } return(0);}2.將下面單鏈表的插入算法補充完整。算法闡明：在帶有頭結點的單鏈線性表中第i個位置之前插入元素x:typedef_______________{ DataTypedata; structnode*next;}LNode,*LinkList;intlistinsert(LinkListhead,inti,DataTypex){ LinkListp=head.s intj=0; while(p!=NULL&&j<i-1) { _______________; j++; } if(p==NULL)return(0); s=_______________malloc(sizeof(LNode)); s->data=x; _______________; _______________; return(1);}五、算法設計（10分）已知S為次序棧。寫出S的存儲構造類型描述。編寫算法實現將元素x入棧操作Push(S,x)，入棧成功返回1，否則返回0和刪除棧頂元素的出棧操作Pop(S)出棧成功返回1，否則返回0。山東省專升本考試數據構造真題一、判斷題（每題1分，共5分）1.算法的執行時間和所需的存儲空間都是問題規模的函數，進行算法分析就是要找出這種函數關系。（）2.完全二叉樹只能采用次序存儲措施，不能采用鏈表存儲措施。（）3.在次序循環隊列的第i個元素之後插入一種元素是次序循環隊列的基本運算。（）4.若一種葉子是某二叉樹的中序遍歷的最終一種結點，則它必是該二叉樹的前序遍歷的最終一種結點。（）5.直接插入排序的關鍵碼比較次數與初始排列有關。（）二、單項選擇題（每題2分，共10分）1.如下數據構造中哪一種是線性構造（）A.棧B.線索二叉樹C.AOV網D.二叉排序樹2.若有a，b，c三個字符的字符序列執行入棧操作，則其所有也許的輸出排列共有（）A.4種B.5種C.6種D.其他3.一棵樹的廣義表表達為a(b,c(e,f(g)),d)，當用左孩子—右兄弟鏈表表達時，右指針域非空的節點個數為（）A.1B.2C.3D.44.下面有關圖的存儲的論述中對的的是（）A.用鄰接矩陣法存儲圖，占用的存儲空間大小與圖中結點個數和邊數均有關B.用鄰接矩陣法存儲圖，占用的存儲空間大小只與圖中邊數有關，而與結點個數無關C.用鄰接表法存儲圖，占用的存儲空間大小只與圖中邊數有關，而與結點個數無關D.用鄰接表法存儲圖，占用的存儲空間大小與圖中邊數和結點個數均有關5.對長度為12的有序表采用次序存儲構造，折半查找技術，在等概率狀況下，查找成功的平均查找長度是（）A.37/12B.62/13C.49/12D.其他三、應用題（每題5分，共20分）1、已知一棵三叉樹的存儲構造如下表所示，其中root=0，n=7。畫出該二叉樹。2、用克魯斯卡爾算法求下圖的最小生成樹。3、下圖是一棵二叉排序樹，規定當二叉排序樹被刪除的結點既有左子樹，又有右子樹時，以其中序前驅替代。畫出刪除55後的二叉排序樹。4、已知散列表地址空間為HT[0..8]，散列函數為H(key)=key%7，采用線性探測法處理沖突，將數據序列{107,27,28,42,3,25,99,38}依次存入散列表中。試畫出對應的散列表；并計算等概率下搜索成功的平均搜索長度。散列表及其查找各關鍵字要比較的次數如下所示：012345678關鍵字比較次數搜索成功的平均搜索長度為：ASL=四、算法設計題（每題5分，共15分）1.已知次序棧s，簡述f1函數功能，當輸入80時，輸出成果是多少？f1(){initstack(s);scanf(“%d”,&n);while(n){push(s,n%8);n=n/8)}while(!Emptystcak(s)){pop(s,x);printf(“%d”,x);}}2.寫出二叉樹前序遍歷非遞歸算法的設計思想，然後寫出算法。3.寫出直接插入排序算法。山東省專升本考試數據構造真題一、選擇題（本大題共10小題，每題1分，共10分）1.數據構造，與所使用的計算機無關的是數據的哪種構造（）A.存儲B.物理C.邏輯D.物理和存儲2.線性表是（）A.一種有限序列，可認為空B.一種有限序列，不能為空C.一種無限序列，可認為空D.一種無限序列，不能為空3.下列哪個選項的鄰接矩陣必然是對稱矩陣（）A.有向圖B.無向圖C.AOV網D.AOE網4.串是一種特殊的線性表，其特殊性體目前（）A.可以次序存儲B.數據元素是一種字符C.可以鏈式存儲D.數據元素可以是多種字符5.不含任何結點的空樹是（）A.是一棵樹B.是一棵二叉樹C.是一棵樹也是一棵二叉樹D.既不是樹也不是二叉樹6.已知一維數組A采用次序存儲構造，每個元素占用4個存儲單元，第9個元素的地址為144，則第一種元素的地址是（）A.108B.180C.176D.1127.鏈表合用于哪種查找措施（）A.次序B.二分法C.次序，也能二分法D.隨機8.用鄰接表表達圖，進行廣度優先遍歷時，一般是采用哪種構造來實現算法的。（）A.棧B.隊列C.樹D.圖9.任何一種無向連通圖的最小生成樹是（）A.只有一棵B.一棵或多棵C.一定有多棵D.也許不存在10.若某完全二叉樹的結點個數為100，則第60個結點的度為（）A.0B.1C.2D.不確定二、填空題（本大題共5小題，每題2分，共10分）1、一棵深度為6的滿二叉樹有個分支點和個葉子。2、一種字符串相等的充要條件是和。3、從鄰接矩陣A=可以看出，該圖共有個頂點。假如是有向圖，該圖共有條弧。4、棧的特點是，隊列的特點是。5、三元組表中的每個節點對應與稀疏矩陣的一種非零元素，它包具有三個數據項，分別表達該元素的、和值。三、簡答題（本大題共2小題，每題5分，共10分）1、已知二叉樹（如圖）請給出它的3種遍歷序列先序：中序：後序2、簡述數據構造的概念？在討論數據構造時，一般會從哪三個方面進行？四、操作題（本大題共2小題，每題10分，共20分）1、已知一組關鍵字為{19,14,23