第一部分西安交通大學2017年招收攻 入學考試試題（回憶版 西安交通大學2016年招收攻 入學考試試 西安交通大學2015年招收攻 入學考試試 西安交通大學2014年招收攻 入學考試試 西安交通大學2013年招收攻 入學考試試 西安交通大學2008年招收攻 入學考試試 西安交通大學2007年招收攻 入學考試試 西安交通大學2006年招收攻 入學考試試 西安交通大學2005年招收攻 入學考試試 第二部分答西安交通大學2017年招收攻 入學考試試題答 西安交通大學2016年招收攻 入學考試試題答 西安交通大學2015年招收攻 入學考試試題答 西安交通大學2014年招收攻 入學考試試題答 西安交通大學2013年招收攻 入學考試試題答 西安交通大學2008年招收攻 入學考試試題答 西安交通大學2007年招收攻 入學考試試題答 西安交通大學2006年招收攻 入學考試試題答 西安交通大學2005年招收攻 入學考試試題答 西安交通大學2017年招收攻讀入學考試題（回憶版注:2017年考試題目較之前變動很大，最重要的是增加了10分填空題，沒有判 百分之80相似。且其中含有百分之百中的難題以科目代碼 科目名稱：計算機軟件基（注：所有答案必須寫在答題紙上，寫在本試題紙或草稿紙上一律無效一、選擇題(每小題2分，共24分下列哪個時間復雜度與其他不0 B.0(nn)C.0II注:此題原本就只有三個選項，并非本卷錯字符串"abcde"有()個子A.32B.24C.30C.26經過以下校的操作后，變量X的值變?yōu)镮nitStack(st);Push(st，a);Push(st，b);Pop(st，x);Top(st，x)ab下面關于線性表的一些說法中，正確的D.取線性表低i元素的時間與i大小有關已知關鍵宇序列5，812，19，28，20，1522小根堆，插入關鍵字3，調整好后得到的小根堆是()具有12個關鍵字的有序表中，對每個關鍵字的查找概率相同，折半查找成功的平均查找長度為()，折半查找失敗的平均查找長度為A.37/12B.35/12C.39/13在下列排序算法中，平均情況下空間復雜度為O(n)的是();情況下空間復雜度為O(n)的是()1)希爾排序2)堆排序3)冒泡排序4)歸并排序5)快速排序6)基數A.1)4) B.2) C.4) D.設無向圖G(V，E)和G’=(V’，E')，如果G’是G生成樹，G’為G的子 B.G’是G的連通分C.G’為G的極小連通子圖且 D.G’是G的一個無環(huán)子關于圖的結構，()是錯誤的使用鄰接矩陣一個圖時在不考慮壓縮的情況下所占用鄰接表只用于有向圖的，鄰接矩陣適用于有向圖和無向無向圖的鄰接矩陣是對稱的故只需鄰接矩陣的下(或上)D.層稀疏矩陣一般地壓縮方法有()兩種二、填空題(每小題2分，共10分散列表中H(key)=keymodp(p<=m)，其中p的選取規(guī)則 DAG的全稱 。在單向鏈表中，在單鏈表中設置頭節(jié)點的作用 除首結點外，任何一個節(jié)點的位置 表示數據的結構可用四種基本的方法，它們 方法

方法

方法 方法n個元素的順序檢查(檢索)的平均查找長度為 有三個結點的二叉樹共有幾種形態(tài)?請畫出寫出一個時間復雜度為o(n*n)和o(n*logn)的算法:寫出一個為徑長度則是所有葉結點深度的綜合，用歸納法證明，包含n個分支結點的哈夫曼樹如果內部路徑長度為1，外部路徑長度為E，則E=I+2口，對n>二O請利用兩個核sl和s2來模擬一個隊列己知校的三個運算定義如push(stx)元素xstpop(st，&x)st出校頂元素，賦值變量xsempty(st)，判斷st是否溝空如何利用占得運算實現該隊列的三個運算，enqueue元素入隊dequeue素出隊queue_empty判空給出基本設計思根據設計思想采用c描述算法，關鍵處給出注(2)寫出完全二叉樹的定義，并證明具有n個結點的完全二叉樹，若按照從上到下，從左到右進行編號，其編號最小的葉結點序號為按照斯特拉算法求出下圖中從頂點O到其他各頂點的最短路若空指針指的是不指向其他結點的指針，且指針占2字節(jié)，數據4字節(jié)，請回答下列問(1)有n個結點的哈夫曼樹，求空指針占全部空間的百分(2)一棵n結點的，左子樹為空的二叉樹在先序線索化四、算法寫折半查找的算法寫出基本思想代碼實現的前提下，請設計一個盡可能高效的算法，查找鏈表中倒數第k位并返回1;否則，只返回0。要求:描述算法的基本設計思描述算法的詳細實現步根據設計思想步驟，采用程序設計語言描述算法(使用CC++或Java語言實現)，關鍵之處請給出簡要注釋為了充分利用空間，順序棧sO.sl共個區(qū)elem[1，sO.sl假設校中元素為int。要求:給出基本設計思想根據設計思想，采用CC++語言描述算法(對于共享校要寫出結構定義)，關鍵之R給出注釋。設有n個活動的集合E={1'-2…時，其中每個活動都要求使用→資源，而在同一時間內只有一個活動能使用這一資源。每個活動i都有一個更求使用該資源的起始時間Sl和一個結束時間口，且Sl<fi。如果選擇了活動1，則它在半開時間區(qū)間（si，fi)內占用資源。若區(qū)間（si，fi)與區(qū)間（sj，fj)不相交，則稱活動i與活動j是相容的。也就是說Sl>=fj或SJ>=fi活動i與活動j西安交通大學2016年招收攻讀入學考試題科目代碼 科目名稱：計算機軟件基（注：所有答案必須寫在答題紙上，寫在本試題紙或草稿紙上一律無效一、選擇從線性表中移除一個元素，情況下的時間復雜度是多少 在一個單鏈表中，若q所指結點是p所指結點的前驅結點，若q與p之間插入一個s所指的結點，則執(zhí)行A.s—>link=p—>link; B.p—>link=s;s—>link=q;C.p— D.q—>link=s;s—>link=p;5、3、4、6、1、 B.3、2、5、6、4、3、1、2、5、4、 D.1、5、4、6、2、字符串的長度是指串中不同字符的個 B.串中不同字母的個C.串中所含字符的個 D.串中不同數字的個A.24B.71C.48在一棵度為3的樹中，度為3的結點數為2個，度為2的結點1個，度為1的結點數為2個，則度為0的結點數為（） B.5C.6是完全二叉 B.不是完全二叉C.是滿二叉 D.不是滿二叉若一個圖的邊集為{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}從頂點A開始對該圖進行深度優(yōu)先搜索，得到的頂點序列可能（A. 下列中排序最快的排序算法是A.冒泡排 B.歸并排 C.選擇排 D.快速排二、判斷基于比較排序的算法時間復雜度下限是折半查找僅需要連續(xù)數據空間就可求拓撲排序可以使用深度優(yōu)先遍歷或者最短路徑方折半搜索適用于有序表，包括有序的順序表和有序的鏈表不結點的單向循環(huán)鏈表head為空表的條件是具有n個結點的滿二叉樹，其葉結點的個數為用一維數組二叉樹時，總是以前序遍歷結點三、解答評價一個算法可以從哪幾方面入手請對比分析棧和隊列這兩種線性結構，說出其相同點和不同點設計一個增長速度為O(logn)的循環(huán)程序？設計一個增長速度為有一系列數字（、、、、、、5，按構造二叉檢索求平均查找長構造H=key%11的散列求其平均查找長比較兩個平均查找長度，闡述你對二叉檢索樹和散列表的理解有如下的鄰接矩陣（無向帶權圖ABCDEA03SB025SC320S3D5S03ESS330畫出其對應的無向帶權應用prim算法，找到最小生成應用dijskra算法，從A點開始，找到最短路畫出其鄰接闡述對鄰接矩陣和鄰接表的理 >,<A,D>,<C,A>}后序遍歷序列為畫出該將該樹轉化為二叉樹，并畫出二叉四、編程題編寫一個函數，功能是：將字符串s中的所有數字字符去掉，保留其余的字符，并將形成的新字符串在原s的空間中。編寫一個函數，功能：從一個整數m，統(tǒng)計其中各位上等于n的數字數目，并返回，其中0<=n<=9，若n界，則返回-1，并提示‘第二個參數越界例如：03建立一個學生在某一個課程到課情況統(tǒng)計程序。功能要求可統(tǒng)計所有學生的上課率，率，并輸出寫出所用的數據結寫出算法描寫出源程序西安交通大學2015年招收攻讀入學考試題科目代碼 科目名稱：計算機軟件基（注：所有答案必須寫在答題紙上，寫在本試題紙或草稿紙上一律無效一．選擇題（每空2，共20數據結構是一門研究非數值計算程序設計問題的（以及他們之A.作對象B.算方法C.輯運算D.據映下面程序的時間復雜度是（for(inti=0;i<m;i=i+2)for(intj=n;j>1;j=j-2)A.O(mlogn)B. C.O(mn)D.棧和隊列的共同特點是（只允許端點處插入和刪除B.是先進先C.都是先進后 D.沒有共同快速排序法在（）的情況下，最利于發(fā)揮其長處參加排序的數據量過參加排序的數據中包含過多的相同元參加排序的數據已基本按值有參加排序的數據過于分n2,則（A.n0=n2+1 C.n0=2n2+1 A.生改變B.發(fā)生改變C.能確定D.上都不設G=(V1，E1)和G=(V2，E2)為兩個圖，如果 包含包含E1，則稱（G2G1通分量B.G1G2連通分C.G1是G2的 D.G1是G2的子采用鄰接表的圖的廣度優(yōu)先遍歷類似于二叉樹 A.序遍歷B.序遍歷C.序遍歷D.序遍二叉樹排序樹（）二叉樹A.定是滿B.一定是滿C.是D.能是求字符串T字符串S首次出現的位置的操作為（A.求子 B.求串的長度C.串的連接D.模式匹二．判斷題（T示正確F示錯誤（每題2分索可以到圖的每個項（）鏈表不具有的特點是可隨機一個元素（一個帶權的無向連通圖的最小生成樹的樹X后是唯一的（有n個頂點的的六項圖，采用鄰接矩陣表示，圖中的邊數等于接矩陣中非零元和的一半（節(jié)點-6x的值，其右子樹根結點的值大于等于該結點（x）的值，則此二叉樹是二叉檢索樹（）直接插入排序在最好情況下的時間復雜度為O(nlogn（若哈希表的穴載因子a>1,則可避免碰撞的產生（遍歷二叉樹的某結點若無左孩子，則它必是葉子節(jié)點（折半查找法適用于所有的有序表（一個6行10列的二維數組，如果用行優(yōu)法的方式，那么第三行第四列的位置將和列優(yōu)先時第4行第3列的位置相同（）三．簡答題（20什么叫拓撲排序？其一般的應用場景是什么給出A,B,C個元素所構成的二叉樹檢索樹的所有樹形什么是哈夫曼樹？簡述哈編碼過程，并證明有n個葉子的哈夫曼樹，共有2n-1結點。四．解答題（每題1050設循環(huán)隊列Q[10]的當前狀態(tài)如圖1示rear(隊尾)指針指向元素C,front（隊頭）指針指向序號的數組元素，請回答下列問題寫出隊列Q空和判滿的邏輯表達式寫出隊列出隊操作和入隊操作的偽代碼描述結構畫出出列兩個元素并入隊H,I元素后隊列Q的狀態(tài)，圖中必須標明rear和front示的位置。已知一顆二叉樹T,如圖2請寫出這棵二叉樹T中序遍歷序列和后序遍歷序列請給出這棵二叉樹T應的森林請給出森林的夫序遍歷序列已知一個帶權無向圖的鄰接矩陣如圖3所示，請回答下列問題根據該鄰接矩陣畫出所描述的圖從字母C發(fā)，給出該圖進行廣度優(yōu)先遍歷的樹利用kncskal算法為該圖求出所有最小撐樹要有求解過程用流程圖的方式寫出選擇排序的算法的數據序列進行第一趟至第四趟每趟的排序結果；按照從小到大的排序方式進行基數排序，選擇基數為10，請寫出題目中的數據序列進行排序的過程。已知有關鍵字序列{25,15,26,7,13,23,19,48,32,15列問題構造長度為11的散列表，該散列表的解決策略為線性探測法解決，散列函數為hash(k)=（(ka)*2+1)mod7,請畫出該散列表（1）五．按題目要求編寫程序（每題10，共40（注：可選用任意一種程序語言編寫程序編寫一個候選人的票的統(tǒng)計程序。設有m個人，n個候選人，structLnode{ 編寫一個函數intcaortx(structLNode*HL,intx),函數的功能為統(tǒng)計出單鏈表的中結點的值，等于給值x的結點數。西安交通大學2014年招收攻讀入學考試題科目代碼 科目名稱：計算機軟件基（注：所有答案必須寫在答題紙上，寫在本試題紙或草稿紙上一律無效一、選擇A實在參B條件參C語句形D局部參E全局參F表達G形式參H變量常A實在參B條件參C語句形D局部參E全局參F表達G形式參H變量常2.在許多高級語言中函數可以遞歸調用通常 來實現遞歸用中的分配的A數 B C D鏈線性表的鏈式結構與順序結構相比，其優(yōu)點 A所有操作的算法實現簡 B便于隨機存C便于插入和刪除操 D需要較少的空線性表采用鏈式時，其地址 A必須是連續(xù)B部分地址必須是連續(xù)C一定是不連續(xù)D連續(xù)與否均 方式最節(jié)省運算時間A單鏈C雙鏈B僅有頭指針的單向循環(huán)鏈D僅有尾指針的單向循環(huán)鏈 A樹 B C二叉樹D生成下列結 是正確的A二叉樹的度為B二叉樹中的結點的度可以小于C二叉樹中至少有一個結點的度為D二叉樹中任何一個結點的度都為一棵具有124個葉子節(jié)點的完全二叉樹，最多 個結點ABCD A順序查找B散列查找 C折半查找 順序方式的優(yōu)點是密度大，且插入、刪除效率高鏈表的每個主吉點中都恰好包含一個指針中共有n+1空指針。k>=l時，高度為k的二叉樹至多有2(k-l)個結點線索二叉樹的優(yōu)點是便于查找前驅結點和后繼結點無向完全圖有n(n-1)/2條邊折半查找法既可以用于有序表，也可以用于無序表衡量算法的優(yōu)劣主要有哪幾個標準?請簡述其內容給出三種常用的查找方法，并簡述它們的優(yōu)缺點maxsize示，請寫出判斷循環(huán)隊列滿的條件。一棵樹的先根序列為ABCEFGHDJ根序列為BFGHECDA，這樣的樹四、解答數組A[8][4]的每一個元素占4個字節(jié)，下標從0開始。己知A起始地址為3072，按采用行優(yōu)先的方 時，A[6][3]的始地址為多少?按采用列優(yōu)先的方式時，A[6][3]的起始地址為多少?若某個元素的起始地址為3140則這個元素的下標為多少?給出根據下面給定的字母和權簡歷哈夫曼編碼樹，并回答如下問給出每個字母的哈夫曼編碼長根據這樣的分布頻率，如果包含n個字母的消息，其預期長定義二叉樹的內部路徑長度為所有分支結點深度的綜合外部路徑長度則是所有葉結點深度的綜合，用歸納法證明:包含n個分支結1E對n>=O立。己知有關鍵字序列{34，侶，14，32，84，21，8，5}，按要求回用流程圖的方式寫出冒泡排序，的算為關鍵字(2，8，31，20，19，18，53，27)構造長度為13的散列hash(k)=kmod13，如果計算結果超過了13，則對13取模。請回答給出插入8個關鍵碼以后的散列某需要統(tǒng)計本社目前最暢銷的30本書的售書情況設:每一輸入一本書的書名(假設該的讀者有100人);程序根據輸入的書名，使該書的庫存量減少一本，售書統(tǒng)計數增加1;按售書統(tǒng)要求(1)設計出該程序的數據結構:(2)編寫程序，實現上述所有要求西安交通大學2013年招收攻讀入學考試題科目代碼 科目名稱：計算機軟件基（注：所有答案必須寫在答題紙上，寫在本試題紙或草稿紙上一律無效C一、填空題（本題共20，每小題各2注：第7題由于錯誤在此刪從總體上說數據結構”課程主要研究（）三個方面的內容（在長度為n的非空隊列中進行插入或者刪除操作的時間復雜度用大O號表示為（。若一棵度為4樹中度為1,2,34結點個數分別為4,2,11，則該樹中葉節(jié)點的個數為（若某二叉樹的中序遍歷為BAFDGCE,按層次遍歷序列為則該二叉樹的后序遍歷為（將一顆結點總數為n，且具有m個葉節(jié)點的樹轉換為一顆二叉樹找元素37，與表中進行過比較的元素依次是（。n探再散列法處理，那么，將著n個關鍵字值全部散列到初始為空（ n的序列 K=（k1,k2,k3,....，kn）當且僅當滿足ki<=k2i并且ki<=k2i+1(1<=i<=n/2)時，則該序列為一個小頂（Heap（二、簡答題（本題共20，每小題各5如果一個具有100個頂點，200條邊的有向圖采用鄰接矩陣，零元素的數目小于整個矩陣總元素的數目的5%時認為該矩陣為稀疏1排序的結果（2,12,16,5,10,882排序的結果（2,12,5,10,16,883排序的結果（2,5,10,12,16,88三、綜合題（本題 20分，每小題各5分若非空雙向循環(huán)鏈表中點結構為llinkdatarlink,則依次執(zhí)行下列4語句的目的是在該鏈表中由q的結點后面插入一個由p的結點，其中條語句有錯誤，請出該語句，并寫出正確的語句P- /*1語句 /*第2條語句*/ /*第3條語句*/q->rlink- /*4語句已知某完全二叉樹的第7有10葉節(jié)點，請求出該完全二叉樹證明：具有n頂點的無向圖最多有n(n-1)/2邊四、算法設計題（本 15分已知某具有n個頂點的有向圖采用鄰接表方法，其中，用以存Typedefstructedge{Intadjvex;Struct /*指向下一個邊結點用以頂點信息的頂點結點類型typedefstructver{Intindegree;Vertype /*某頂點的數據信息ELink /*指向以該頂點為出發(fā)點的第一個邊結點/*某頂點的入度并且n頂點結點構成一個數組結構G[0..n-1]。請寫一個算法，該算法判斷給定的頂點序列V[0..n-1]={v1,v2,v3,..,vn}是否是該有向圖的一個拓撲序列若是該有向圖的一個拓撲序列算法返回1，否則，算法返回0.五、單項選擇題（本題 20分，每小題各2分在C言中，標識符只能由字母、數字和下劃線三種字符組成，（必須是字母或下劃可以是字母、數字和下劃線之若整型變量x初值為6，則計算表達式”x+=x-=x*x”之后，x值是（。--下列4程序段中，不是無限循環(huán)的是（for(b=0,a=1;a>++b;a=k++)C.while(1){for(;;D.for(k=10;;k--)說明”double(*ptr)[N];”中的標識符ptr（N指向double型變量的指指向Ndouble型變量的函數指一個指向由Ndouble型元素組成的一維數組的指具有Ndouble類型變下列4敘述中，正確的是（char*r=”china”;等價于char*r;char*ptr=”china”;等價于char*ptr;charstring[10]={china價于charstring[10];string[]={“china”};charstr[4]=abc,temp[4]=abcchar在C序中，語句”char*func(intx,inty);”表示（對函數func定對函數func調對函數func回值類型的說對函數func原型說#include<stdio.h>#include<malloc.h>main(){charp=(char*)malloc(sizeof(char)*20);}abcdD.各成員所需內存量的總和（#defineABC（x）x*xmain({inta,k=3;}A.B.9D.若要以a+方式打開一個已經存在的文件，則下列敘述中，正確（六、簡答題（本題 20分，每小題各5分在c言中，頭文件的作用是什么在includefilename.h的區(qū)別是什么在c言中，全局變量和局部變量的主要區(qū)別是什么七、填空題（本題 20分，每小題各2分（說明：本大題中的填空處用（i）表示第i個空下列代碼的功能包括：定義一個x數組，說明一個結構體，同時對變量tt的a成員的值為5b成員的值為x（方框內intstruct{inta,int*b下列函數的功能是根據公式s=1-1/3+1/5-1/7+...+1/(2n+1)計s值，其中，n過形參傳入（n>=0）,計算結果通過形參指針voidfun(float*sn,int{floats=0,w,f=-1;inti;f=(}}下列程序實現將輸入的一個小寫字母循環(huán)后移5位置輸出。例’bmain({charc;c=getchar();else}{charstr1[]=”acegikm”;charstr2[]=”bdfhjlnpq”;charstr3[],*p;inti=0,j=0,k=0; if((2))p=str2+j;elsep=str1+i;}對于下列main函數，經過編譯、連接后得到的可執(zhí)行文件名為file.exe,并且已知在系統(tǒng)令狀態(tài)下輸入命令行”fileBeijing請在函數空白處填入合適的內容，使函數完整main(intargc,char*argv[--}下列程序的功能是打開兩個已存在的文件file1和file2，并將file2接到file1的后面。請在程序的空白處填入合適的內容，使程序完整#include<stdio.h>intmain(){FILE*fp1,*fp2;printf(“cannotopenfile1!\n”);return0;}printf(“cannotopenfile2!\n”);return0;}}設n>0.下列函數的功能是 intfun(intn){intcount=0;returncount;}#include<stdio.h>{charstr[81],*ptr1,*ptr2;intn;}else}（ voidmain(){FILE*fp;longposition;}八、程序設計題（本題15請編寫一C語言程序，該程序的功能是確定字符串中首次出現的謀，字符的刪除，并且顯示刪除前后的字符串通過鍵盤輸入字符串以及被確定的字符西安交通大學2008年招收攻讀入學考試題科目代碼 科目名稱：計算機軟件基（注：所有答案必須寫在答題紙上，寫在本試題紙或草稿紙上一律無效一、填空題（20分不寫解答過程，將正確答案與題目編號寫在答題紙上僅允許在同一端進行插入刪除的線性表稱為((1)在一個長度為n順序表中第i元素(1<i<n)之前插入元素時，需向后移動元素個數是((2))。將長度為n的單鏈表接在長度為m的單鏈表之后的算法時間復雜度為((3))。設數組data[m]作為循環(huán)隊列SQ的空間，front為隊頭指針，rear為隊尾指針，則執(zhí)行出隊操作后其頭指針front的值為((4))。對于前序遍歷與中序遍歷結果相同的二叉樹為((5))；對于序遍歷與后序遍歷結果相同的二又樹為((6)在用于表示有向圖的鄰接矩陣中，對第i行的元素進行累加，可得到第i頂點的((7))度，而對第j的元素進行累加，可得到第j頂點的((8))度。已知一棵完全二叉樹中共有768結點，則該樹中共有((9)個葉子結點堆排序是一種高效的內部排序算法，它的時間復雜度是((10)二、判斷題(10分線性表的邏輯順序與物理順序總是一致的31中序遍歷一棵二叉排序樹的節(jié)點就可得到排好序的節(jié)點序列直接選擇排序是一種穩(wěn)定的排序方法三、簡答題(16分簡述順序表與鏈表的優(yōu)缺點判斷一個算法的優(yōu)劣，主要有哪幾個標準？簡述其內容什么是平衡二叉樹若有n個元素以構成一個小根堆（也稱小頂堆，那么如果增加一個元素為K(n+1)，請用文字簡要說明你如何在log2(n)的時間內將其四、解答題（58分什么？當f=38，r=14時，該隊列當前有多少元素？（6分）2)如圖一所示，要求對該圖的做如下工作（10）圖一將圖一的森林轉換為一棵二叉樹圖二向圖的鄰接畫出這個圖設n個元素的有序表為RK為一個給定的值二分查找算法如下intbinsearch(sqlistRkeytypewhile(j<=th)&&(!suc)){caseK=R[mid].key:suc=l;break;caseK<R[mid].key:h=mid-1;break;caseK>R[mid].key.j=mid+l}}if(suc)return(mid):else將上述算法中劃線語句改為改動后，算法能否正常工作？請說明原因（10）從空樹起，依次插入關鍵字32，構造一棵二叉排序樹（10分面出該二叉排序畫出刪去該樹中元素值為90的結點之后的二又排序樹有一組鍵值25，84，21，47，15，27，68，35，24，采用快速排過程中鍵值的移動情況。(10)五、算法閱讀題（6分利用同一循環(huán)向量空間實現兩個隊列，其類型Queue2定義如下typedefDataTypedata[MaxSize];intfront[2],}Queue對于i=01，font[ilength[i]分別為第i隊列的頭指針和長intEnQueue(Queue2*Q,inti,DataTypex){//，若第i隊列不滿，則元素x隊列，并返回l，否則返回Oif(i<Olli>1)returnO;if returnQ->data[(20)Q->length[(3)return}六、閱讀下列函數說明和C程序，將應填入(n)處的內容寫在答題紙上（10）[說明]本程序中的函數factor(m，fac，cp)用來計算正整數m(m)2)按從小到大依次存放在數組fac中，其因子個數存在形參指針變量cp指的變量中。[程序#include<stdio.h>#defineN100longfactor(int ;int{intcl,c2,1,k;longs;fac[0]=for(c]=s=1,c2=N-l,i=2:; if(i!= }fac[cl++l=i;} }for(c2++;c2<=N- return(s);}main{intfactors[N],i,count;longintsum;sum=factor(16,factors, for(i=0;i<count;i++)printf("factoris:%5d".factors[i]);printf(“sum= count=%5d\n”,sum,}七、編程題(30分程序，可以使用pascalC編寫（類pascalC均可，也可以數據結構j對程序要加以適當的注解，程序應有良好的結構，不得使用goto句。有15個人圍成一圈-順序從l到I5編號。從第一個人開始報數，凡報到n人退出圈子C言寫出程序，輸入n(n>=1)的值，輸出最后留在圈子里的人的編號假設有兩個按元素值遞增有序排列的線性表A和B，均以單鏈表作結構請編寫算法將表A和表B歸并成一個按元素非遞減有（允許值相同）排列的線性表C，并要求利用原表（即表A和表B）的結點空間存放表C。右遍歷的過程中將連接方向逆轉，如圖三所示。在圖中的指針p指向當前正在的節(jié)點，指針pr指向指針p所指節(jié)點的左側的節(jié)點。此時，指針p指節(jié)點左側的所有節(jié)點的連接方向都已逆轉。使用Pascal或C語言編寫一個算法，從任一給定位置(pr，p)開始，將指針p右移1個節(jié)點。如果p移出鏈表，則將p置為NULL，并讓pr在鏈表最右邊的節(jié)點上。使用Pascal或C語言編寫一個算法，從任一給定位置(pr，p)開始，將指針p左移一個節(jié)點。如果P移出鏈表，則將p置為NULL，并讓pr留在鏈表最左邊的節(jié)點上。西安交通大學2007年招收攻讀入學考試題科目代碼 科目名稱：計算機軟件基（注：所有答案必須寫在答題紙上，寫在本試題紙或草稿紙上一律無效一、簡答題（20分（l）什么是結構化程序設計什么是面向對象程序設計在程序設計中，說明與定義有什么不同算法有哪些特點①（4）循環(huán)隊列squeue[45]的頭尾指為f、r，請問該隊列滿的條件是什么？當f=38，r=14時，該隊列當前有多少元素？②（6分）求出next函數值K123456789模式串aaabaaaaba③（10）已知遍歷一棵二叉樹后，其中序遍歷序列為CIBHDAFGE，后序遍歷序列為：ICHDBGFEA，試完成：構造這棵二叉樹結出其先序遍歷序列結出該二叉樹所對應的森林④（10分）已知一無向圖G的鄰接矩陣為011100101010110001100011010101001110請畫出這個無向圖請寫出這個無向圖G的鄰接表寫出從v1開始的DFS序列寫出從v1開始的BFS序列⑤（10分）已知有關鍵字序列用選擇排序法寫出第四趟排序結束后，關鍵字序列用快速排序法寫出第一趟排序結束后．關鍵字序列歸并排序法寫出第三趟排序結束后，關鍵字序列（32，13，49，55，22，38，21，按線性探測法解決，產生的散列表是地0123456（在地址0～6對應的表格內填入相關的關鍵字關鍵比較次關鍵比較次三、算法設計（每題15分，共30分注：本題由于非常復雜且涉及的知識較多，所以在此不予給出（1、函數，函數首部為voidstrcat(char*s1,char*s2),實現將兩個字符串合并后存到s1。五、設計算法并編寫程序題（30分1、設計算法并編寫程序完成如下功能（15分從鍵盤輸入100個整數數據請統(tǒng)計這100個數中非負數個最終程序應該輸出這個個數，并且以每行輸出10數據的要求輸出所有的負數（包括0寫出程序中的數據結構用描述算法中四種方法之一，描述你所設計的算法2、設計算法并編寫函數intfindMax_Min(inta],intn),有如下功能（15）寫出該函數中的形參的數據結構用描述算法的四種方法之一。描述你所設計的算法西安交通大學2006年招收攻讀入學考試題科目代碼 科目名稱：計算機軟件基（注：所有答案必須寫在答題紙上，寫在本試題紙或草稿紙上一律無效一、判斷下列敘述是否正確，正確填√，不正確填×(每小題2分) )4、對稀疏矩陣進行壓縮是為了便于矩陣的運算 )9、快速排序在情況下的時間復雜度為O(n2) 二、選擇填空題(每小題2分l、假設以數組A[48]存放循環(huán)隊列的元素，其頭指針是當前隊列有35個素，則隊列的尾指針值為( 2、已知二叉樹如圖所示，此二叉樹的順序的結點序列是 ) C、 D、 A、 B、 C、14； C、head- D、5、如果根的層次為1，具有61個結點的完全二叉樹高度為 )A．5B．6C．7 A.順序查找B．散列查找C．折半查找D.動態(tài)查找 A．通過該頂點的簡單路徑數B．通過該頂點的回路C．與該頂點相鄰接的頂點數D．與該頂點連通的頂點8、利用逐點插入法建立關鍵字序列 B．7C．49、如果具有n個頂點的有向圖中最多有多少條?。? B．n(n-1)/2C．nD．n-l 三、填空題(20)1假設一個12階的下三角矩陣A按行優(yōu)先順序壓縮在一維數B中，則非零元素a7,6在B中的位置k= (注：矩陣元素下標從1算起，數組B的下標從0算起)2、在長度為n的順序的線性表中插入一個元素，平均需要移 個元素 4、給出下列程序段中語句的執(zhí)行次 }} 6、深度為5的二叉樹至少 結點，最多 結點 四、簡答題(40分l、(4分)請回答樹與二叉樹的區(qū)別，并舉例說明之2、(8分)已知一棵二叉樹，如圖1所示，試完成3、(6設有向圖，如圖2示，給出該圖的拓撲排序序列，并用0101010100010111010100110還原圖G，并寫出圖G的鄰接表結構寫出從Vl開始的深度優(yōu)先遍歷和廣度優(yōu)先遍歷序列及其相應的[06]請畫出相應的散列表求出查找各關鍵字的比較次數計算出等概率情況下，查找成功的平均查找長度6、(6設某系統(tǒng)的通信聯(lián)絡中僅有5字符：a，b，c，d，e,組給出相應的哈夫曼樹設計出這5字符的哈夫曼編碼；五、算法設計(20)l、已知下列算法中，Ls時不帶表頭結點的單鏈表typedefstruct 鏈表結點類型定義｛ElemTypedata;structLnodeStatusFun(LinkListLs){ /*針對鏈表的操作函數*/LinkListp,c;if(Ls&&LS->next) Ls=Ls->next;p-Ls;while(p->next)p=p->next; }return}/*Funend請回答下列問題語句(b)執(zhí)行之后，p指向鏈表中的那個結點2、已知二叉樹采用二叉鏈表，其結點結構定義為typedefstruct 二叉樹結點類型定義｛ElemTypestructNode*lchild,請采用遞歸方式編寫算法Sua-Node(BiTreeT)，返回二叉樹T中結點總數六，采用任意一種編程語言編寫程序(30分1、編寫函數，用冒泡排序法或選擇排序法對輸入的100整數按從小2、采用遞歸法，編寫實現n!的函數3、編寫統(tǒng)計候選人得票的程序。設有十個候選人，有100個人參加西安交通大學2005年招收攻讀入學考試題科目代碼 科目名稱：計算機軟件基（注：所有答案必須寫在答題紙上，寫在本試題紙或草稿紙上一律無效一、判斷下列敘述是否正確，正確填√，不正確填×（15分數據對象是一組數據元素的集合 判定一個圖是否存在回路，只能使用拓撲排序算法 任何一棵前序線索二叉樹，都可以不用棧實現前序遍歷 用快速排序算法中，不可以用隊列代替棧 二、填空題（15分①算法的時間復雜度是 ③數組G[9][5]的每一個元素占4個字節(jié)，下標從0開始，已知G的起始地址2072，按行優(yōu)先方式的G[6][3]的地址為 若某個元素的起始地址為2140，則這個元素的下標是 ④具有n各頂點的無向連通圖至少 條邊⑤深度為k的二叉樹至多有個 三、解答題（60分）①（10分）循環(huán)隊列squeue[45]的頭尾指針為f、r，請問該隊列的條件是什么？f=38，r=14時，該隊列當前有多少元素②（6分）求出next函數值K123456789模式串aaabaaaaba③（10）已知遍歷一棵二叉樹后，其中序遍歷序列為CIBHDAFGE，后序遍歷序列為：ICHDBGFEA，試完成：構造這棵二叉樹結出其先序遍歷序列結出該二叉樹所對應的森林④（10分）已知一無向圖G的鄰接矩陣為011100101010110001100011010101001110請畫出這個無向圖請寫出這個無向圖G的鄰接表寫出從v1開始的DFS序列寫出從v1開始的BFS序列⑤（10分）已知有關鍵字序列用選擇排序法寫出第四趟排序結束后，關鍵字序列用快速排序法寫出第一趟排序結束后．關鍵字序列歸并排序法寫出第三趟排序結束后，關鍵字序列（32，13，49，55，22，38，21，按線性探測法解決，產生的散列表是地0123456（在地址0～6對應的表格內填入相關的關鍵字關鍵比較次關鍵比較次四、程序填空題（15分[程序說明]本程序用古典的Eratosthenes篩選法求從2到指定范圍內的素數。如果要找出2至10中的素數，開始時篩中有2到10的數，然后取走篩中最小數2，宣布它是素數，并把該素數的倍數取走。這樣，第一步后，篩子中還留下奇數3、5、7、9；重復上述步驟，再取走篩中最小數3，宣布它是素數，并取走3倍數，于是留至10中的全部素數程序中用數組sieve表示篩子數組元素的值為1時，表示數i在篩子中，值為-1時表示數i已被取走#defineMAX22500main（）unsignedinti,range,factor,k;intsieve[MAX]；printf(“Pleaseinputthescanf(“%d，&range)；／*range在多大的范圍內尋找素數for(i=2;i<=range;i++)／*篩子初始化 printf(“d/t",factor);while(k<=range){／*移走素數的倍數 ；／*篩中的個數減一 }} }}五、算法設計（20分設有兩個一元多項式，如下所示P(x)=3x17+5x8+19x2-Q(x)=3x16-5x8+9x2-(1)上述多項式采取什么樣的結構好，請說明理由，并畫出的結構六、用任意一種編程語言編寫程序（25分(2)給出程序流程圖西安交通大學2017年招收攻讀入學考試題答注:2017年考試題目較之前變動很大，最重要的是增加了10分填空值不固定，除此之外，本試卷并未直接程序設計，而是將40分程序設計變?yōu)?0分算法題。此試卷為回憶版本，保證與百分之80相似。且其中含有百分之百中的難題以及算法題。一、選擇題(每小題2分下列哪個時間復雜度與其他不同0 B.0(n2)C.0II注:此題原本就只有三個選項，并非本卷錯n!=n(n-1)*(-2)*...勺=n^n+An^(-1)+Bn^n-2其中A，Bn^n時間復雜度與n!在同一個數量級字符串"abcde"有(A)個子A.32B.24C.30C.26特別注意空串和串本身也算一個子串經過以下校的操作后，變量X的值變?yōu)镮nitStack(st);Push(st，a);Push(st，b);Pop(st，x);Top(st，x)abA【解析】:執(zhí)行前三句后，枝st的值為a，b，其中b核頂針，執(zhí)行第4后，x值為b，執(zhí)行最后一句后x值為a。下面關于線性表的一些說法中，正確的是D.取線性表低i元素的時間與i大小有關C【解析】:雙鏈表能很方便的前驅和后繼，故插入和刪除數據較為方便。A顯然錯誤。B表中第一個和最后一個元素不滿足題設要求。D未考慮順序的情況。已知關鍵宇序列5，8，12，19，28，20，15，22是小根堆，插入關鍵字3，調整好后得到的小根堆是(A)A【解析】:根據題目建立小根堆如下圖1所示19的右子樹插入關鍵字3后的小根堆如圖2所示由小根堆的定義可知圖2需要調整所以自下而上調整過后的小根如圖3所示具有12個關鍵字的有序表中，對每個關鍵字的查找概率相同，折A.37/12B.35/12C.39/13AD【解析】:假設有序表中元素為A[0...11]，不難畫出對它進行的ASL=(1+2*2+3*4+4*5)/12，查找失敗的在下列排序算法中，平均情況下空間復雜度為O(n)的是(D);情況下空間復雜度為O(n)的是(C)希爾排序2)堆排序3)冒泡排序4)歸并排序5)快速排序6)基數A.1)4)6)B.2)5)C.4)5)D.DC【解析】:歸并排序算法在平均情況和情況下空間復雜度都會達到O(n)，快速排序只有在情況下才會達到O(n)，平均情況下為O(log2n)。所以歸并排序算法可以看做所有排序算法中占輔助設無向圖G二(V，E)和G’=(V’，E')，如果G’是G的生成樹，G’為G的子 B.G’是G的連通分C.G’為G極小連通子圖且V=v'D.G’是G一個無環(huán)子圖B【解析】:連通分量是無向圖的極大連通子圖，其中極大的含義是關于圖的結構，(B)是錯誤的使用鄰接矩陣一個圖時在不考慮壓縮的情況下所占用鄰接表只用于有向圖的，鄰接矩陣適用于有向圖和無向無向圖的鄰接矩陣是對稱的故只需鄰接矩陣的下(或上)B【解析】4:n頂點的圖，若采用鄰接矩陣表刁言，不考慮壓縮存只是把每條邊看做是兩條方向相反的有向邊，因此需要兩次，B錯誤。由于鄰接矩陣中對角線以下元素全為0，若存在<i，j>則必i->……->j-功，由題知k<j<k，，故不存在環(huán)，拓撲序列必定存在，C確。選項D然正確。D.層B【解析】:稀疏矩陣一般地壓縮方法有(C)兩種D.散列和十字鏈二、填空題(每小題2，共10)散列表中H(key)=keymodp(p<=m)，其中p的選取規(guī)則是P選小于等于表長的最大素DAG全稱是有向無環(huán)圖作除首結點外，任何一個節(jié)點的位置由前驅節(jié)點的后繼指針表數據的結構可用四種基本的方法，它們是順序方法、方法、索引方法、散列方法。寫出一個時間復雜度為on*n)和o(n*logn)的算法:寫出一為答for(inti=O;i<n;i++)for(intj=O;j<n;j++)for(inti=O;i<n;i++)for(intj=1;j<n;j=j*2)徑長度則是所有葉結點深度的綜合，用歸納法證明，包含n個分支結點的哈夫曼樹如果內部路徑長度為1，外部路徑長度為E，則E=I+2口，對n>=O立。答①當n=l時，易知E=2，I=O，所以E=I+2n成立②假設n<=k(k>O)肘，E=I+2n立:則當n=k+l，不妨假定找到某個內結點x葉結點(根據二元擴展樹的定義，一定存在這樣的結點x，且設該結點的層數為h)，將結點x其左右子結點(外結點)從原樹中摘除，生成新二元擴展樹.此時新二元擴展樹內部結點為k，則滿足Ek=lk+2k，原樹的外部路徑長度Ek+l=Ek-(h-l)+2h，l)請利用兩個核sls2模擬一個隊列己知校的三個運算定義push(stx)元素xstpop(st，&x)st出校頂元素，賦值變量xsempty(st)，判斷st是否溝空如何利用占得運算實現該隊列的三個運算，enqueue元素入隊dequeue素出隊queue_empty判空給出基本設計思根據設計思想采用c描述算法，關鍵處給出注略(2)寫出完全二叉樹的定義，并證明具有n個結點的完全二叉樹，若按照從上到下，從左到右進行編號，其編號最小的葉結點序號為答先:BEFACDG中答:若設二叉樹的深度為h，除第h層外其它各層(1——h-1)的結點數都達到最大個數，第h層所有的結點都連續(xù)集中在最左邊，這注意:上的定義為:對于深度為K的，有η個結點的二叉樹，當且僅當其每一個結點都與深度為K的滿二叉樹中編號從1至n的結點一證明:完全二滅樹中只有度為0，1，2的結點，記為n0，n1，n2，其中nO=n2+1，n1=01.若n1=1n為偶數，n=n0+n1+n2，代入nO=n2+1n1=1，則化簡為n2=n/2-1，顯然，n2的個數即為最后一個度為2的結點的下標。那么n1下標為n/2，第一個nO下標為n/2+1.n1=0，則n奇數n=nO+n1+n2，代入n0=n2+1，和n1=0，則化簡為n2=(n-l)/2=n/2(因為n是奇數，/代表取整)，顯然，n2的個數即為最后一個度為2的結點的下標那么第一個口0的下標為按照斯特拉算法求出下圖中從頂點O到其他各頂點的最短路已并入頂ABCDEFGA0∞∞∞A0∞∞AB0∞ABG0∞ABG0∞ABGF0ABGFE0ABGFEC0若空指針指的是不指向其他結點的指針，且指針占2字節(jié)，數據4字節(jié)，請回答下列問(1)有n個結點的哈夫曼樹，求空指針占全部空間的百分(2)一棵n結點的，左子樹為空的二叉樹在先序線索化7..(1)哈夫曼樹只有度為02結點且滿足口O=n2+1.度為0點左右指針均為空，只包含數據。度為2的結點左右指針及數據項那么空指針的個數為2*n，空指針所占空間為2*n*2，總結點數為2n-1，每個結點均占據2+2+4=8宇節(jié)(左指針右指針數據項)，比例(4n)/(8(2n-1))=n/(4n-(2)對左子樹為空的二叉樹進行先序線索化根節(jié)點的左子樹為空為空且有前驅和后繼結點。故線索化后，其空鏈為2個。所以比例為4/(4n-2)=2/(2n-1)四、算法1.寫折半查找的算法寫出基本思想代碼實現答intBinary_Search(SeqListL，ElemTypekey)intlow=O，high=L.TableLen-1,mid;while(low<=high){mid=(low+high)/2;if(L.elem[mid]==key)returnelseif(L.elem[mid]>key)high=mid-1; low=mid+1}return-的前提下，請設計一個盡可能高效的算法，查找鏈表中倒數第k位并返回1;否則，只返回0。要求:描述算法的基本設計思描述算法的詳細實現步根據設計思想步驟，采用程序設計語言描述算法(使用CC++或Java語言實現)，關鍵之處請給出簡要注釋為了充分利用空間，順序棧sO.sl共個區(qū)elem[1，sO.sl假設校中元素為int。要求:給出基本設計思想根據設計思想，采用CC++語言描述算法(對于共享校要寫出結構定義)，關鍵之R處給出注釋設有n個活動的集合E={1'-2…時，其中每個活動都要求使用→資源，而在同一時間內只有一個活動能使用這一資源。每個活動i都有一個更求使用該資源的起始時間Sl和一個結束時間口，且Sl<fi。如果選擇了活動1，則它在半開時間區(qū)間（si，fi)內占用資源。若區(qū)間（si，fi)與區(qū)間（sj，fj)不相交，則稱活動i與活動j是相容的。也就是說Sl>=fj或SJ>=fi活動i與活動j西安交通大學2016年招收攻讀入學考試題答一、選擇從線性表中移除一個元素，情況下的時間復雜度是O(n)插入一個結點：q—>link=s;s—出棧字符串的長度：串中所含字符的個數帶權路徑長度為設度為0的結點個數為題有問題，不是滿二叉樹和不是完全二叉樹無向圖快速排序O(n 冒泡排序O(選擇排序O( 歸并排序O(n 二、判斷 最快O(n 折半查找：連續(xù)數據空間，查找序列有序 求拓撲排序：深度優(yōu)先遍歷（逆拓撲排序1 快速排序最快，但附加空間多，涉及到遞歸，平均空間度為O() 折半查找：有序表，順序表 不結點的單向循環(huán)鏈表head為空表的條件head==NULL 具有n個結點的滿二叉樹，其葉結點個數為(n+1)/2 用一維數組二叉樹時是根據結點編號之間的關系來 三、解答評價一個算法：健壯性，正確性，可讀性，高效率和低量需高為h的堆，最多有-1個結點，最少有個結點。小頂堆最大值的編號為：?n/2?+1~nvoid{intI; 時間復雜度：O(void{inti,j,k=0; 時間復雜度：O( 9②平均查找長度（1+2x2+3x3+3x4+5）/10=3.1③散列表地0123456789值9比較次233④度與處理的方法有關。 步SV-1A001311∞0200533116330053312634D0053319563注：Dis[]用來距離，Pre[]用來前驅結點；S集合是剛加入到最短路徑BBC3AC2A3E3AB5C3D3^EDCBAD^D5^B2^E3^題目改為：后序遍歷序列為 四、編程voidsub(char*str){inti,m;{{//i=i-}//else}}void{char//printf("%s",str);}voidsts(intnum,int{intcharstr[100];inti,k=0;printf("數字%d中%d的個數為}intintnum,n;printf("請輸入要統(tǒng)計的數字 return-1;}}} 將數字轉換為字符p=num+’0’;頭文件西安交通大學2015年招收攻讀入學考試題答一、選擇 CA 待排序序列接近無序，快速排序效率越高ABD BD二、判斷 無向圖是連通的，有向圖的一個頂點到其余頂點都有邊√ √√AACX直接插入排序在最好情況下的時間復雜度為X時不可避免的，與裝填因子有關。產生概率與裝填XX有序表，順序 按行優(yōu)先，三行四列為第24個數。按列優(yōu)先，四行三為第16數。三、簡答題n個結點，構成Cn/n+1種不同的二叉樹ABC ABCABCABCABCABC哈夫曼樹：帶權路徑長度WPL最小的二叉樹哈夫曼編碼：對構造好的哈夫曼樹，約定左分支表示0，右分支表示1.從根結點到葉子結點的路徑上的編碼組成該葉子結點的哈夫曼樹，只有度為0和度為2的結點。n個葉子結點，n-1個度為2的結點，一共2n-1個結點。度為m的哈夫曼樹，葉子點為n，則非葉子結點數四、解答題①判空 判滿②進隊：Q.rear=(q.rear+1)%10;出隊：Q.front=(Q.front+1)%10;③0123456789ABCHI ①中序 后序②AB②ABCDEFGHIJ③森林的前序：ABCDEFGHIJ；中序①②由于給定了結構，則的先后順序就確定了③①voidselect(intR[],int{intI,j,k;inttemp;{if(R[k]>R[j])k=j;}}12345678913261810131822262835①②地0123456789值7比較次388五、編程voidadd(ints[100][100],intn){inti,j,sum1=0,sum2=0;if(i==j)sum1+=s[i][j];for(j=n-1;j>=0;j--if((i+j)==(n-1))printf("副對角線和為}voidmain(){intint}voidselect(char*str){inti,j=0,k=0,m=0;{else}}voidchar}3intcaortx(structLNode*HL,int{intLNode*p=HL—>next;/HL頭結{if(p—elsep=p—>next;}return}西安交通大學2014年招收攻讀入學考試題答一、選擇A,G【解析】:形式參數是函數定義中的，系統(tǒng)沒有為其分配內存空間，但是在定義里面可以使用的參數。例如:fun(inta)。這里a就是形式參數;實際參數是函數調用的時候傳給函數的變量。這個是:fun(a)。轉換為非遞歸算法通常需要借助棧來實現。隊列的應用:扮層次遍每個結點值的同時，還必須指示其直接后繼結點的地址(或位置)，稱為指針。而順序表插入和刪除需要移動大量元素，故選C。D【解析】:見第三題D【解析I:在最后一個元后插入元素，需要先找到最后一個元素，故A,B，C的時間復雜度均為O(n)}。B因為沒有特殊的指針指入和刪除的位置，時間復雜度也為O(n)D兩種算法的時間復雜度均為O(1