國開形成性考核02272《數(shù)據(jù)結(jié)構(gòu)（本）》考試題庫（含答案）

PAGEPAGE1國開形成性考核02272《數(shù)據(jù)結(jié)構(gòu)（本）》考試題庫（含答案）判斷題1.哈夫曼樹葉結(jié)點數(shù)比非葉結(jié)點數(shù)多1。A、正確B、錯誤答案：A2.數(shù)據(jù)項是數(shù)據(jù)的最小單位。A、正確B、錯誤答案：A3.使用鄰接矩陣存儲圖的時候，占用空間大小與圖的結(jié)點個數(shù)沒有關(guān)系。A、正確B、錯誤答案：B4.樹最適合表示元素之間具有層次關(guān)系的數(shù)據(jù)。A、正確B、錯誤答案：A5.在歸并排序中，在第3趟歸并中，是把長度為4的有序表歸并為長度為8的有序表。A、正確B、錯誤答案：A6.在有序表A[1…18]中，采用二分查找算法查找元素值等于A[17]的元素，所比較過的元素的下標依次是9、14、16、17。A、正確B、錯誤答案：A7.冒泡排序是一種比較簡單的交換排序方法。A、正確B、錯誤答案：A8.二叉排序樹中某一結(jié)點的左兒子一定小于樹中任一個結(jié)點的右兒子。A、正確B、錯誤答案：B9.AOV網(wǎng)是一個帶權(quán)的有向圖。A、正確B、錯誤答案：B10.對連通圖進行深度優(yōu)先遍歷可以訪問到該圖中的所有頂點。A、正確B、錯誤答案：A11.用數(shù)組實現(xiàn)順序棧，棧底可以是數(shù)組空間的任何一端A、正確B、錯誤答案：A12.用字符數(shù)組存儲長度為n的字符串，數(shù)組長度至少為n+1。A、正確B、錯誤答案：A13.兩個字符串比較時，較長的串比較短的串大A、正確B、錯誤答案：B14.循環(huán)隊列隊頭指針在隊尾指針后一個位置，隊列是“滿”狀態(tài)。A、正確B、錯誤答案：A15.循環(huán)隊列是將隊列想象成一個首尾相接的圓環(huán)。A、正確B、錯誤答案：A16.樹是一種線性結(jié)構(gòu)。A、正確B、錯誤答案：B17.對于一棵深度為h，度為3的樹最多有（3h-1）/2個結(jié)點。A、正確B、錯誤答案：B18.數(shù)據(jù)的邏輯結(jié)構(gòu)是與存儲該結(jié)構(gòu)的計算機相關(guān)的。A、正確B、錯誤答案：B19.隊列的特性是先進后出。A、正確B、錯誤答案：B20.在歸并排序中，在第3趟歸并中，是把長度為4的有序表歸并為長度為8的有序表。A、正確B、錯誤答案：A21.數(shù)組通常具有的操作是順序存取。A、正確B、錯誤答案：B22.具有n個結(jié)點的二叉樹，采用二叉鏈表存儲，共有n-1個空鏈域。A、正確B、錯誤答案：B23.在單鏈表中，要刪除某一指定的結(jié)點，必須找到該結(jié)點的直接前驅(qū)結(jié)點。A、正確B、錯誤答案：A24.設(shè)廣義表L=（（），（）），則其表頭是（（））。A、正確B、錯誤答案：B25.圖的廣度優(yōu)先搜索序列是惟一的。A、正確B、錯誤答案：B26.具有10個結(jié)點的完全二叉樹有5個葉子。A、正確B、錯誤答案：A27.在一個順序存儲的循環(huán)隊列中,隊頭指針指向隊頭元素的后一個位置。A、正確B、錯誤答案：B28.采用分塊查找時，數(shù)據(jù)的組織方式是把數(shù)據(jù)分成若干塊，塊內(nèi)數(shù)據(jù)不必有序，但塊間必需有序，每塊內(nèi)最大（或最?。┑臄?shù)據(jù)組成索引表。A、正確B、錯誤答案：A29.設(shè)有一個不帶頭結(jié)點的單向循環(huán)鏈表，結(jié)點的指針域為next，指針p指向尾結(jié)點，現(xiàn)要使p指向第一個結(jié)點，可用語句p=p->next;。A、正確B、錯誤答案：A30.序列15,13,16,14,19,17，采用冒泡排序算法(升序)，經(jīng)一趟冒泡后，結(jié)果序列是13,15,14,16,17,19。A、正確B、錯誤答案：A31.用數(shù)組實現(xiàn)順序棧，棧底可以是數(shù)組空間的任何一端A、正確B、錯誤答案：A32.若讓元素a,b,c依次進棧，則出棧次序c,a,b是不可能出現(xiàn)的情況。A、正確B、錯誤答案：A33.各種鏈表只需定義有兩個域的結(jié)點。A、正確B、錯誤答案：B34.若樹中各結(jié)點的子樹是按照一定的次序從左向右安排的，則稱之為有序樹。A、正確B、錯誤答案：A35.圖的連通分量是無向圖的極大連通子圖。A、正確B、錯誤答案：A36.對于一棵深度為h，度為3的樹最多有（3h-1）/2個結(jié)點。A、正確B、錯誤答案：B37.采用順序查找法對長度為n（n為偶數(shù)）的線性表進行查找，采用從前向后的方向查找。在等概率條件下成功查找到前n/2個元素的平均查找長度為(n+2)/4。A、正確B、錯誤答案：A38.在一個查找表中，能夠唯一地確定一個記錄的關(guān)鍵字稱為主關(guān)鍵字。A、正確B、錯誤答案：A39.采用順序查找法對長度為n（n為偶數(shù)）的線性表進行查找，采用從前向后的方向查找。在等概率條件下成功查找到前n/2個元素的平均查找長度為(n+2)/4。A、正確B、錯誤答案：A40.設(shè)某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為BCDA。A、正確B、錯誤答案：B41.數(shù)據(jù)項是數(shù)據(jù)的最小單位。A、正確B、錯誤答案：A42.圖的最小生成樹只有一棵。A、正確B、錯誤答案：B43.線性表是一個有限序列，不可以為空。A、正確B、錯誤答案：B44.使用三元組表示稀疏矩陣中的非零元素能節(jié)省存儲空間。A、正確B、錯誤答案：A45.森林是m（m≥0）棵互不相交的樹的集合。A、正確B、錯誤答案：A46.各種鏈表只需定義有兩個域的結(jié)點。A、正確B、錯誤答案：B47.遞歸算法可讀性差，但是效率高A、正確B、錯誤答案：B48.序列15,13,16,14,19,17，采用冒泡排序算法(升序)，經(jīng)一趟冒泡后，結(jié)果序列是13,15,14,16,17,19。A、正確B、錯誤答案：A49.如果一個葉子結(jié)點是某二叉樹中序遍歷序列的最后一個結(jié)點，那么它也是該二叉樹的先序遍歷序列的最后一個結(jié)點。A、正確B、錯誤答案：A50.父親李貴有兩個兒子李萬勝和李萬利，李萬勝又有三個兒子李建新、李建中和李建國，這個家庭可以用樹結(jié)構(gòu)來描述。A、正確B、錯誤答案：A51.哈夫曼樹一定是完全二叉樹或滿二叉樹。A、正確B、錯誤答案：B52.采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為n/2A、正確B、錯誤答案：B53.字符串a(chǎn)1=〝heijing〞,a2=〝hen〞,a3=〝heifang〞,a4=“heni〞，其中最小的是a2。A、正確B、錯誤答案：B54.字符串屬于線性的數(shù)據(jù)結(jié)構(gòu)A、正確B、錯誤答案：A55.設(shè)有一個單向循環(huán)鏈表，結(jié)點的指針域為next，頭指針為head，指針p指向表中某結(jié)點，若邏輯表達式p->next==head;的結(jié)果為真，則p所指結(jié)點為尾結(jié)點。A、正確B、錯誤答案：A56.若讓元素1,2,3依次進棧，則出棧次序1,3,2是不可能出現(xiàn)的情況；A、正確B、錯誤答案：B57.AOV網(wǎng)是一個帶權(quán)的有向圖。A、正確B、錯誤答案：B58.深度為k的完全二叉樹至少有2k-1個結(jié)點。A、正確B、錯誤答案：B59.按照一定規(guī)則，在二叉排序樹上插入、刪除結(jié)點，仍能保持二叉排序樹的性質(zhì)。A、正確B、錯誤答案：A60.一個有向圖的鄰接表和逆鄰接表中的節(jié)點個數(shù)一定相等。A、正確B、錯誤答案：A61.棧是限定在表的兩端進行插入和刪除操作的線性表，又稱為先進先出表。A、正確B、錯誤答案：B62.線性表用順序方式存儲可以隨機訪問。A、正確B、錯誤答案：A63.采用分塊查找時，數(shù)據(jù)的組織方式為把數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序，每塊內(nèi)最大（或最?。┑臄?shù)據(jù)組成索引表。A、正確B、錯誤答案：B64.順序查找是一種最簡單的查找方法。A、正確B、錯誤答案：A65.樹的所有結(jié)點有且只有一個前驅(qū)結(jié)點。A、正確B、錯誤答案：B66.線性表用順序方式存儲可以隨機訪問。A、正確B、錯誤答案：A67.散列技術(shù)中的沖突指的是兩個元素具有相同的序號。A、正確B、錯誤答案：B68.樹是一種重要的非線性數(shù)據(jù)結(jié)構(gòu)。A、正確B、錯誤答案：A69.序列3,1,7,18,6,9,13,12經(jīng)一趟歸并排序的結(jié)果為1,3,7,18,6,9,13,12。A、正確B、錯誤答案：B70.哈夫曼樹只存在著雙支結(jié)點，不存在單支結(jié)點。A、正確B、錯誤答案：A71.隊列的特性是先進后出。A、正確B、錯誤答案：B72.設(shè)有一個單向鏈表，結(jié)點的指針域為next，頭指針為head，p指向尾結(jié)點，為了使該單向鏈表改為單向循環(huán)鏈表，可用語句p->next=head。A、正確B、錯誤答案：A73.在線性表的順序存儲中，元素之間的邏輯關(guān)系是通過物理存儲位置決定的；在線性表的鏈式存儲中，元素之間的邏輯關(guān)系是通過鏈域的指針值決定的。A、正確B、錯誤答案：A74.計算機所處理的數(shù)據(jù)一般具有某種關(guān)系,這是指數(shù)據(jù)元素與數(shù)據(jù)元素之間存在的某種關(guān)系。A、正確B、錯誤答案：A75.設(shè)有一個長度為40的順序表，要刪除第8個元素需移動元素的個數(shù)為33。A、正確B、錯誤答案：B76.在隊列的順序存儲結(jié)構(gòu)中，當插入一個新的隊列元素時，尾指針后移，當刪除一個元素隊列時，頭指針后移。A、正確B、錯誤答案：A77.遞歸的算法簡單、易懂、容易編寫，而且執(zhí)行效率也高。A、正確B、錯誤答案：B78.存儲圖的鄰接矩陣中，鄰接矩陣的大小不但與圖的頂點個數(shù)有關(guān)，而且與圖的邊數(shù)也有關(guān)。A、正確B、錯誤答案：B79.對稀疏矩陣進行壓縮存儲，矩陣中每個非零元素對應(yīng)的三元組包括該元素的行號、列號和元素值三項A、正確B、錯誤答案：A80.二叉樹中任一結(jié)點的值均大于其左孩子的值，小于其右孩子的值，則它是一棵二叉排序樹。A、正確B、錯誤答案：B81.在各種查找方法中，平均查找長度與結(jié)點個數(shù)n無關(guān)的查找方法是哈希表查找。A、正確B、錯誤答案：A82.在雙向循環(huán)鏈表上，刪除最后一個結(jié)點，其算法的時間復(fù)雜度為0(1)。A、正確B、錯誤答案：A83.已知一棵樹的先序序列和后序序列，一定能構(gòu)造出該樹。A、正確B、錯誤答案：B84.循環(huán)隊列是將隊列想象成一個首尾相接的圓環(huán)。A、正確B、錯誤答案：A85.用字符數(shù)組存儲長度為n的字符串，數(shù)組長度至少為n+1。A、正確B、錯誤答案：A86.若一個強連通圖有n個頂點，則該強連通圖中至少含有n條有向邊。A、正確B、錯誤答案：A87.待排序的序列為8,3,4,1,2,5,9，采用直接選擇排序算法，當進行了兩趟選擇后，結(jié)果序列為1,2,8,3,4,5,9。A、正確B、錯誤答案：B88.分塊查找分為兩個步驟：第一步是要對索引表進行查找；第二步是在塊中查找。這兩步查找都可以采用折半查找或者順序查找方法。A、正確B、錯誤答案：B89.完全二叉樹中沒有度為1的結(jié)點。A、正確B、錯誤答案：B90.兩個字符串比較時，較長的串比較短的串大A、正確B、錯誤答案：B91.對稀疏矩陣進行壓縮存儲，矩陣中每個非零元素對應(yīng)的三元組包括該元素的行號、列號和元素值三項信息。A、正確B、錯誤答案：A92.數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計算機內(nèi)的實際存儲形式。A、正確B、錯誤答案：A93.數(shù)據(jù)結(jié)構(gòu)中,元素之間存在多對多的關(guān)系稱為樹狀結(jié)構(gòu)。A、正確B、錯誤答案：B94.對于一個具有n個結(jié)點的單鏈表，在?p結(jié)點后插入一個新結(jié)點的時間復(fù)雜度是O(n)。A、正確B、錯誤答案：B95.冒泡排序是一種比較簡單的插入排序方法。A、正確B、錯誤答案：B96.順序查找是一種最簡單的查找方法。A、正確B、錯誤答案：A97.長度為0的線性表稱為空表。A、正確B、錯誤答案：A98.哈夫曼樹一定是完全二叉樹或滿二叉樹。A、正確B、錯誤答案：B99.哈夫曼樹只存在著雙支結(jié)點，不存在單支結(jié)點。A、正確B、錯誤答案：A100.對于一個無向圖，每個頂點的入度等于出度。A、正確B、錯誤答案：A101.在隊列的順序存儲結(jié)構(gòu)中，當插入一個新的隊列元素時，尾指針后移，當刪除一個元素隊列時，頭指針后移。A、正確B、錯誤答案：A102.設(shè)有6個結(jié)點的無向圖，該圖至少應(yīng)有6條邊才能確保是一個連通圖。A、正確B、錯誤答案：B103.二叉樹的根結(jié)點值大于其左子樹結(jié)點的值，小于右子樹結(jié)點的值，則它是一棵二叉排序樹。A、正確B、錯誤答案：B104.一個空格的串的長度是0。A、正確B、錯誤答案：B105.樹是一種重要的非線性數(shù)據(jù)結(jié)構(gòu)。A、正確B、錯誤答案：A106.遞歸算法執(zhí)行時，每次遞歸可將原的規(guī)模縮小。A、正確B、錯誤答案：A107.一個廣義表的表頭總是一個廣義表。A、正確B、錯誤答案：B108.一個廣義表的表頭總是一個廣義表。A、正確B、錯誤答案：B109.二叉樹的遍歷就是按照一定次序訪問樹中所有結(jié)點，并且每個結(jié)點的值僅被訪問一次的過程。A、正確B、錯誤答案：A110.由一個具有n個頂點的連通圖生成的最小生成樹中，具有n-1條邊。A、正確B、錯誤答案：A111.一棵二叉樹每一層的結(jié)點數(shù)都達到最大值，則這個二叉樹是完全二叉樹。A、正確B、錯誤答案：B112.用鄰接矩陣存儲圖的時候，占用空間大小不但與圖的結(jié)點個數(shù)有關(guān)還與圖的邊數(shù)有關(guān)。A、正確B、錯誤答案：B113.對于一棵深度為4的滿三叉樹，其結(jié)點數(shù)為40。A、正確B、錯誤答案：A114.串中的元素只可能是字母。A、正確B、錯誤答案：B115.圖的深度優(yōu)先搜索序列和廣度優(yōu)先搜索序列不是惟一的。A、正確B、錯誤答案：A填空題1.設(shè)a，b為一棵二叉樹的兩個結(jié)點，在后續(xù)遍歷中，a在b前的條件是（）。答案：a在b下方2.二叉排序樹結(jié)點類型定義如下：typedefstructBnode{intkey;structBnode?left;structBnode?right;}Bnode;以下為二叉排序樹的查找算法，完成程序中空格部分。Bnode?BSearch(Bnode?bt,intk){Bnode?p;if(bt==NULL)return(bt);p=bt;while(()){if(k<p->key)p=p->left;elsep=p->right;if(p==NULL)break;}return(p);}答案：p->key!=k3.已知某帶權(quán)圖的鄰接矩陣如下所示：從頂點1出發(fā)的廣度優(yōu)先搜索序列為（）。答案：1，2，3，4，5，64.在一非空二叉樹的中序遍歷序列中，根結(jié)點的右邊（）。答案：只有右子樹上的所有結(jié)點5.已知某二叉樹的后續(xù)遍歷序列是dabec，中序遍歷是debac，則它的先序遍歷序列是（）。答案：cedba6.一般情況下，將遞歸算法轉(zhuǎn)換成等價的非遞歸算法應(yīng)該設(shè)置（）。答案：棧7.假定一棵二叉樹中，葉子結(jié)點數(shù)為10，單分支結(jié)點數(shù)為30，則雙分支結(jié)點數(shù)為（）。答案：98.鏈表不具有的特點是（）。答案：可隨機訪問任一元素9.在下面空格處填寫一條語句，以使下面的出棧算法完整。ElemTypePop(structSeqStack?s,ElemTypex){if(StackEmpty(s)){printf(“棧下溢錯誤！\n”);exit(1);}x=s->data[s->top];()returnx;}答案：s->top--;10.一組記錄的關(guān)鍵字序列為（46，79，56，38，40，45，62），利用堆排序（堆頂元素是最小元素）的方法建立的初始堆為（）。答案：38,40,45,79,46,56,6211.以下為求二叉樹深度的算法，完成程序中空格部分。intBTreeDepth(BTreeNode?BT){if(BT==NULL)return0;else{intdep1=BTreeDepth(BT->left);/?計算左子樹的深度?/intdep2=BTreeDepth(BT->right);/?計算右子樹的深度?/if(________)returndep1+1;elsereturndep2+!;}}答案：dep1>dep212.有一個長度為10的有序表，按折半查找對該表進行查找，在等概率情況下查找成功的平均比較次數(shù)為（）。答案：29/1013.對線性表進行二分查找時，要求線性表必須（）。答案：以順序存儲方式，且數(shù)據(jù)元素有序14.有一個長度為12的有序表，按折半查找對該表進行查找，在等概率情況下查找成功的平均比較次數(shù)為（）。答案：37/1215.下面關(guān)于棧的基本運算算法中，復(fù)雜度最高的是（）。答案：鏈棧清空運算16.以下數(shù)據(jù)結(jié)構(gòu)中（）是線性結(jié)構(gòu)。答案：棧17.非空的單向循環(huán)鏈表的尾結(jié)點滿足（）（設(shè)頭指針為head，指針p指向尾結(jié)點）答案：p->next==head18.設(shè)線性表以不帶頭結(jié)點的單向鏈表存儲，鏈表頭指針為head。以下程序的功能是輸出鏈表中各結(jié)點中的數(shù)據(jù)域data，完成程序中空格部分。#defineNULL0voidmain(){NODE?head,?p;p=head;/?p為工作指針?/do{printf(“%d\n”,p->data);p=p->next;}while();}答案：p!=NULL|19.依次將每兩個相鄰的有序表合并成一個有序表的排序方法稱為（）。答案：歸并排序20.以下為求二叉樹深度的算法，完成程序中空格部分。intBTreeDepth(BTreeNode?BT){if(BT==NULL)return0;else{intdep1=BTreeDepth(BT->left);/?計算左子樹的深度?/intdep2=BTreeDepth(BT->right);/?計算右子樹的深度?/if()returndep1+1;elsereturndep2+!;}}答案：dep1>dep221.如果以鏈表作為棧的存儲結(jié)構(gòu)，則退棧操作時（）。答案：必須判斷棧是否空22.帶頭結(jié)點的雙向循環(huán)鏈表L為空表的條件是（）。答案：L->next==L23.以下是冒泡排序算法對存放在a[1],a[2],..,a[n]中序列按關(guān)鍵字key由小到大排序，完成程序中空格部分。voidbsort(NODEa[],intn){inti,j,flag;NODEtemp;for(j=1;j<=n-1;j++){flag=0;for(i=1;i<=n-j;i++)if(){flag=1;temp=a[i];a[i]=a[i+1];a[i+1]=temp;}if(flag==0)break;}}答案：a[i].key>a[i+1].key24.一組記錄的關(guān)鍵字序列為（36，69，46，28，30，84），對該序列進行直接選擇排序（每次選擇最小關(guān)鍵字），第二趟排序后的結(jié)果序列為（）。答案：28，30，46，36，69，8425.廣義表(f,h,(a,b,D,c),d,e,((i,j),k))的長度是()。答案：626.設(shè)有數(shù)據(jù)集合{50，39，17，83，91，14，65}，依次取集合中各數(shù)據(jù)構(gòu)造一棵二叉排序樹，是如下的（）。答案：27.向順序棧中壓入新元素時，應(yīng)當（）。答案：先移動棧頂指針，再存入元素28.串是（）。答案：有限個字符的序列29.在長度為n（n>1）的（）上，刪除第一個元素，其算法的時間復(fù)雜度為O(n)。答案：只有首結(jié)點指針h的不帶頭結(jié)點的單向循環(huán)鏈表30.如果進行串的比較，下列哪個串最大？（）答案：“BEIJING”31.下列廣義表中的線性表是（）。答案：E(a,b)32.設(shè)有一個廣義表A(a)，其表尾為（）。答案：()33.序列狀態(tài)為（）時，快速排序達到最好的時間復(fù)雜度。答案：序列無序34.棧的操作特性決定了它是一種（）的線性表。答案：先進后出35.以下程序段的結(jié)果是：c的值為（）chara[]=”abcdefgjh”；int?p=a,c=0;While(?p++)c++;答案：936.有一個長度為10的有序表，按折半查找對該表進行查找，在等概率情況下查找成功的平均比較次數(shù)為（）。答案：29/1037.在下面空格處填寫一條語句，以使下面的出棧算法完整。ElemTypePop(structSeqStack?s,ElemTypex){if(StackEmpty(s)){printf(“棧下溢錯誤！\n”);exit(1);}x=s->data[s->top];()returnx;}答案：s->top--;38.棧的基本運算包括（）答案：取棧頂元素39.以1，2，3，6，7，8作為葉結(jié)點的權(quán)，構(gòu)造一棵哈夫曼樹是如下哪個圖？（）答案：假設(shè)隊列順序存儲結(jié)構(gòu)為：structSeqQueue{ElemTypedata[MaxSize];intfront,rear;};structSeqQueue?sq;請補充下面出隊算法（不考慮空間循環(huán)使用）。voidOutQueue(structSeqQueue?sq,ElemtTypex){if(1){printf(“隊列已空，不能出隊\n”);exit(1);}2returnsq->data[sq->front-1];}40.當利用大小為N的數(shù)組順序存儲一個棧時，假定用top==-1表示?？眨瑒t入棧應(yīng)該執(zhí)行（）語句修改top指針。答案：top++41.已知一個有序表為{11,22,33,44,55,66,77,88,99}，則順序查找元素55需要比較（）次。答案：542.任何一棵二叉樹的葉結(jié)點在先序、中序和后序遍歷序列中的（）。答案：相對次序不改變43.設(shè)頭指針為head的非空的單向鏈表，指針p指向尾結(jié)點,則通過以下操作（)可使其成為單向循環(huán)鏈表。答案：p->next=head;44.在下面空格處填寫一條語句，以使下面的循環(huán)隊列出隊算法完整。ElemTypeOutQueue(structSeqQueue?sq){if(sq->rear==sq->front){printf(“隊列已空，不能進行出隊操作！\n”);exit(1);}()sq->front=(sq->front+1)%MaxSize;returnx;}答案：x=sq->data[sq->front];45.判斷一個順序隊列sq（最多元素為m）為空的條件是（）。答案：sq->front==sq->rear46.下列說法不正確的是（）。答案：串不是線性結(jié)構(gòu)47.在一個圖G中，所有頂點的度數(shù)之和等于所有邊數(shù)之和的（）倍。答案：248.在一個帶頭結(jié)點的單向鏈表中，若要在指針q所指結(jié)點后插入p指針所指結(jié)點，則執(zhí)行（）。答案：p->next=q->next;q->next=p;49.下面的應(yīng)用中，不符合棧的后進先出特點的是（）。答案：算數(shù)運算、邏輯運算和關(guān)系運算50.串的長度是指（）。答案：串中所含字符的個數(shù)51.設(shè)有一個頭指針為head的單向鏈表中（結(jié)點類型為NODE），p為指向該鏈表中某個結(jié)點的指針。以下程序段為插入一個指針為s的結(jié)點，使它成為p結(jié)點的直接前驅(qū)，請選擇其中空格的選項。NODE?q;q=head;while(q->next!=p)();s->next=p;q->next=s;答案：q=q->next52.稀疏矩陣采用壓縮存儲的目的主要是（）。答案：減少不必要的存儲空間的開銷53.當利用大小為N的數(shù)組順序存儲一個棧時，假定用top==N表示棧空，則入棧應(yīng)該執(zhí)行（）語句修改top指針。答案：top--54.下面的操作不是?；具\算的是（）。答案：排序操作55.（）不屬于線性表的基本操作。答案：求子表56.設(shè)有兩個長度為n的單向鏈表，結(jié)點類型相同，分別是循環(huán)鏈表和非循環(huán)鏈表，則（）。答案：對于兩個鏈表來說，刪除最后一個結(jié)點的操作，其時間復(fù)雜度都是O(n)57.設(shè)有數(shù)據(jù)集合{50，39，17，83，91，14，65}，依次取集合中各數(shù)據(jù)構(gòu)造一棵二叉排序樹，是如下的（）。答案：58.若Head為一個帶表頭結(jié)點的單鏈表的表頭指針，則該表為空表的條件是（）。答案：Head->next==NULL判斷題59.以下程序是快速排序的算法，完成程序中空格部分。設(shè)待排序的記錄序列存放在a[start],…a[end]中，按記錄的關(guān)鍵字進行快速排序，先進行一次劃分，再分別進行遞歸調(diào)用。voidquicksort(NODEa[],intstart,intend){inti,j;NODEmid;if(start>=end)return;i=start;j=end;mid=a[i];while(i<j){while(i<j&&a[j].key>mid.key)j--;if(i<j){a[i]=a[j];i++;}while(i<j&&a[i].key<=mid.key)i++;if(i<j){a[j]=a[i];j--;}}a[i]=mid;()quicksort(a,i+1,end);}答案：quicksort(a,start,i-1);60.向順序棧中壓入新元素時，應(yīng)當（）。答案：先移動棧頂指針，再存入元素61.一個具有n個頂點的有向完全圖包含（）條邊。答案：n（n-1）62.設(shè)關(guān)鍵字序列為：（36，69，46，28，30，74），將此序列用快速排序的方法，以第一個記錄為基準得到的一趟劃分的結(jié)果為（）。答案：30，28，36，46，69，7463.圖的深度優(yōu)先遍歷算法類似于二叉樹的（）遍歷。答案：先序64.下面關(guān)于串的敘述中，正確的是（）。答案：模式匹配是串的一種重要運算65.一棵二叉樹采用鏈式存儲，n個結(jié)點的二叉樹共有（）個指針域為空。答案：n+1。66.在一個長度為n的順序表中為了刪除第5個元素，由第6個元素開始從后到前依次移動了15個元素。則原順序表的長度為（）。答案：2067.某串的長度小于一個常數(shù)，則采用（）存儲方式最節(jié)省空間。答案：順序68.廣義表(f,h,(a,b,D,c),d,e,((i,j),k))的長度是()。答案：669.判斷向上增長型的順序?？盏臈l件是（）。答案：top=-170.其中，1和2處應(yīng)該補充的代碼是（）答案：sq->front==sq->rear,sq->front++71.權(quán)值為{1，2，6，8}的四個結(jié)點構(gòu)成的哈夫曼樹的帶權(quán)路徑長度是（）。答案：2972.有關(guān)線性表的正確說法是（）。答案：除了一個和最后一個元素外，其余元素都有一個且僅有一個直接前驅(qū)和一個直接后繼73.從未排序序列中依次取出元素與已經(jīng)排好序的序列中的元素作比較。將其放入已排序序列的正確的位置上，此方法稱為（）。答案：插入排序74.采用折半查找方法查找長度為n的線性表時，其算法的時間復(fù)雜度為（）。答案：O(log2n)75.已知10個數(shù)據(jù)元素為（54，28，16，34，73，62，95，60，26，43），對該數(shù)列從小到大排序，經(jīng)過一趟冒泡排序后的序列為（）。答案：28，16，34，54，62，73，60，26，43，9576.隊列是一種操作受限的線性表，其限制是（）。答案：僅允許在表的一端進行插入，而在另一端進行刪除操作77.在下面空格處填寫一條語句，以使下面的串比較算法完整。intstrcmp(char?s1,char?s2){inti;for(i=0;s1[i]!='\0'&&s2[i]!='\0';i++)if(s1[i]>s2[i])return1;elseif(s1[i]<s2[i])return-1;if(s1[i]=='\0'&&s2[i]=='\0')()elseif(s1[i]!='\0')return1;elsereturn-1;}答案：return0;78.兩個字符串相等的條件是（）。答案：兩串的長度相等，并且對應(yīng)位置上的字符相同79.如圖所示二叉樹的中序遍歷序列是（）。答案：dgbaechf80.數(shù)據(jù)的存儲結(jié)構(gòu)包括數(shù)據(jù)元素的表示和（）。答案：數(shù)據(jù)元素間的關(guān)系的表示81.在非空雙向循環(huán)鏈表的?p結(jié)點之前插入?q結(jié)點的操作是（）。答案：q->next=p;q->prior=p->prior;p->prior->next=q;p->prior=q;82.線性結(jié)構(gòu)中數(shù)據(jù)元素之間的關(guān)系是（）答案：一對一83.無向圖的鄰接矩陣是一個（）。答案：對稱矩陣84.對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表表示，則所有頂點鄰接表中的結(jié)點總數(shù)為（）。答案：2e85.有關(guān)線性表的正確說法是（）。答案：除了一個和最后一個元素外，其余元素都有一個且僅有一個直接前驅(qū)和一個直接后86.（）的一個重要應(yīng)用是解決主機和打印機之間速度不匹配的。答案：隊列87.假設(shè)鏈隊的隊首和隊尾指針是F和R，那么隊空的條件是（）。答案：R=NULL88.在雙向循環(huán)雙鏈表中，刪除?p結(jié)點需要（）。答案：p->prior->next=p->next;p->next->prior=p->prior;89.就排序算法所用的輔助空間而言，堆排序、快速排序、歸并排序的關(guān)系是（）。答案：堆排序<快速排序<歸并排序90.表達式a?(b+c)-d的后綴表達式是（）。答案：abc+?d-91.以下為求二叉樹深度的算法，完成程序中空格部分。intBTreeDepth(BTreeNode?BT){if(BT==NULL)return0;else{intdep1=BTreeDepth(BT->left);/?計算左子樹的深度?/intdep2=BTreeDepth(BT->right);/?計算右子樹的深度?/if(())returndep1+1;elsereturndep2+!;}}答案：dep1>dep292.（）的一個重要應(yīng)用是解決主機和打印機之間速度不匹配的。答案：隊列93.二叉排序樹結(jié)點類型定義如下：typedefstructBnode{intkey;structBnode?left;structBnode?right;}Bnode;以下為二叉排序樹的查找算法，完成程序中空格部分。Bnode?BSearch（）{Bnode?p;if（）return（）;p=bt;while（）p=p->left;elsep=p->right;if（）break;}return（）;}答案:p->key!=k答案：Bnode?bt,intk|bt==NULL|bt|){if(k<p->key|p==NULL|p94.對二叉排序樹進行（）遍歷，可以使遍歷所得到的序列是有序序列。答案：中序95.設(shè)有一個長度為n的順序表，要刪除第i個元素,則需移動元素的個數(shù)為（）。答案：n-i96.利用2、4、5、10這四個值作為葉子結(jié)點的權(quán)，生成一棵哈夫曼樹，該樹的帶權(quán)路徑長度為（）。答案：3897.串函數(shù)Strcat（a,b）的功能是進行串（）。答案：連接98.鏈棧和順序棧相比，有一個比較明顯的優(yōu)點，即（）。答案：通常不會出現(xiàn)棧滿的情況99.在下面空格處填寫一條語句，以使下面的串比較算法完整。intstrcmp(char?s1,char?s2){inti;for(i=0;s1[i]!='\0'&&s2[i]!='\0';i++)if(s1[i]>s2[i])return1;elseif(s1[i]<s2[i])return-1;if(s1[i]=='\0'&&s2[i]=='\0')()elseif(s1[i]!='\0')return1;elsereturn-1;}答案：return0;4.100.設(shè)查找表為：用折半查找在該查找表成功查找到元素55需要經(jīng)過（）次比較。答案：2101.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的（）。答案：邏輯結(jié)構(gòu)102.鏈表不具有的特點是（）。答案：可隨機訪問任一元素103.以下是直接插入排序算法對存放在a[0],a[1],……,a[n-1]中，長度為n的記錄序列按關(guān)鍵字key由小到大排序，完成程序中空格部分。voiddisort(NODEa[],intn){inti,j;NODEtemp;for(i=1;i<n;i++){temp=a[i];j=i-1;while(j>=0&&temp.key<a[j].key){a[j+1]=a[j];();}a[j+1]=temp;}}答案：j--104.鏈表所具備的特點是（）。答案：插入刪除元素的操作不需要移動元素結(jié)點105.在下面空格處填寫一條語句，以使下面的進棧算法完整。voidPush(structSeqStack?s,ElemTypex){if(s->top==MaxSize-1){printf(“棧滿溢出錯誤！\n”);exit(1);}()s->data[s->top]=x;}答案：s->top++;106.在下面空格處填寫一條語句，以使下面的串連接算法完整。char?strcat(char?s1,char?s2){char?p=s1;while(?p!='\0')p++;while(?s2!='\0'){?p=?s2;p++;()}?p='\0';returns1;}答案：s2++;107.廣義表（a，d，e，（i，j），k）的表尾是（）。答案：（d，e，（i，j），k）108.某串的長度小于一個常數(shù)，則采用（）存儲方式最節(jié)省空間。答案