數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)知到智慧樹期末考試答案題庫2025年北京航空航天大學(xué)非空線性鏈表中，若要在由p所指的鏈結(jié)點(diǎn)后面插入新結(jié)點(diǎn)q，則應(yīng)執(zhí)行語句（）。結(jié)點(diǎn)結(jié)構(gòu)為structNode{intvalue;structNode*link;};

答案:q->link=p->link;p->link=q;閱讀程序，程序的運(yùn)行結(jié)果為（）。#includeinttry(int);intmain(){intx;x=try(5);printf("%d\n",x);return0;}inttry(intn){if(n>0)return(n*try(n-2));elsereturn(1);}

答案:15遞歸過程或函數(shù)調(diào)用時(shí)，處理參數(shù)及返回地址，要用一種稱為（）的數(shù)據(jù)結(jié)構(gòu)。

答案:棧選擇：對(duì)有8個(gè)元素的序列（49，38，65，97，76，13，27，50）按從小到大順序進(jìn)行排序，（）是選擇排序法的第一趟的結(jié)果。

答案:13,38,65,97,76,49,27,50說法正確的是：（）。

答案:OLD是一個(gè)結(jié)構(gòu)類型設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1，e2，e3，e4,e5和e6依次通過棧S，一個(gè)元素出棧后即進(jìn)隊(duì)列Q，若6個(gè)元素出隊(duì)的序列是e2，e4，e3,e6,e5,e1則棧S的容量至少應(yīng)該是（）。

答案:3設(shè)有以下說明語句：structstrutype{inta;floatb;}var;則下面敘述中錯(cuò)誤的是（）。

答案:var是用戶定義的結(jié)構(gòu)類型名設(shè)有一順序棧S，元素a,b,c,d,e,f,g,h依次進(jìn)棧，如果8個(gè)元素出棧的順序是d,f,e,c,h,g,b,a，則棧的容量至少應(yīng)該是（）。

答案:5設(shè)有一組記錄的關(guān)鍵字為{19，14，23，1，68，20，84，27，55，11，10，79}，用鏈地址法構(gòu)造散列表，散列函數(shù)為H（key）=keyMOD13,散列地址為1的鏈中有（）個(gè)記錄。

答案:4設(shè)一個(gè)棧的輸入序列是1，2，3，4，5,則下列序列中，是棧的合法輸出序列的是（）

答案:32154設(shè)n是描述問題規(guī)模的非負(fù)整數(shù)，下列程序片段的時(shí)間復(fù)雜度是（）x=2；while(x答案:O(1og2n)若長度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為（）(1<=i<=n+1)。

答案:O(n)若要進(jìn)行從小到大排序，數(shù)據(jù)元素序列11,12,13,7,8,9,23,4,5是采用下列排序方法之一得到的第二趟排序后的結(jié)果，則該排序算法只能是（）。

答案:插入排序若棧和隊(duì)都采用順序存儲(chǔ)結(jié)構(gòu)，則下述說法正確的是（）。

答案:隊(duì)不為空時(shí)可以進(jìn)行出隊(duì)操作。若某線性表采用順序存儲(chǔ)結(jié)構(gòu)，每個(gè)元素占4個(gè)存儲(chǔ)單元，首地址為100，則第10個(gè)元素的存儲(chǔ)地址為（）。

答案:136若某棧初始為空，PUSH與POP分別表示對(duì)棧進(jìn)行一次進(jìn)棧與出棧操作，那么對(duì)于進(jìn)棧序列a,b,c,d,e,經(jīng)過PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH以后，得到的出棧序列是（）。

答案:b,c若有說明:char*language[]={"FORTRAN","BASIC","PASCAL","JAVA","C"};則以下不正確的敘述是（）。

答案:language包含5個(gè)相同長度的數(shù)組若有以下說明和語句:structstudent{intage;intnum;;}std,*p;p=&std;則以下對(duì)結(jié)構(gòu)變量std中成員age的引用方式不正確的是（）。

答案:*p.age若有以下程序段structdent{intn;int*m;};inta=1,b=2,c=3;structdents[3]={{101,&a},{102,&b},{103,&c}};structdent*p=s;則以下表達(dá)式值為2的是（）。

答案:*(++p)->m若有以下定義,則數(shù)值不為3的表達(dá)式是（）。intx[10]={0,1,2,3,4,5,6,7,8,9},*p1;

答案:p1=x+2,*(p1++)若已知一個(gè)棧的入棧序列是1,2,3…，30，其輸出序列是p1,p2,p3,…pn,若p1=30,則p10為（）。

答案:21若利用快速排序算法進(jìn)行從小到大排序，下列選項(xiàng)中，不可能是經(jīng)過兩次選擇分界元素并確定其最終位置后的排序結(jié)果的是（）。

答案:3,2,5,4,7,6,9若具有n個(gè)頂點(diǎn)的無向圖采用鄰接矩陣存儲(chǔ)方法，該鄰接矩陣一定為一個(gè)（）。

答案:對(duì)稱矩陣若具有n個(gè)結(jié)點(diǎn)的二叉樹采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，則該鏈表中有（）個(gè)指針域。

答案:2*n若以{4，5，6，7，8}作為葉子結(jié)點(diǎn)的權(quán)值構(gòu)造哈夫曼樹，則其帶權(quán)路徑長度是（）。

答案:69若二叉樹的前序序列與后序序列的次序正好相反，則該二叉樹一定是（）的二叉樹。

答案:其分支結(jié)點(diǎn)的度都為1若一個(gè)非連通的無向圖最多有28條邊，則該無向圖至少有（）個(gè)頂點(diǎn)。

答案:9給出一組關(guān)鍵字序列{12,2,16,30,8,28,4,10,20,6,18}，當(dāng)用快速排序（選第一個(gè)記錄為基準(zhǔn)點(diǎn)進(jìn)行劃分，采用課堂中描述的“快速排序”算法）從小到大進(jìn)行排序第一趟結(jié)束時(shí)的序列為（）。

答案:4，2，6，10，8，12，28，30，20，16，18線性表中的插入、刪除操作，在順序存儲(chǔ)方式下平均移動(dòng)近一半的元素，時(shí)間復(fù)雜度為O(n)（）

答案:對(duì)線性表中的插入、刪除操作，在鏈?zhǔn)酱鎯?chǔ)方式下，若要在某個(gè)結(jié)點(diǎn)后插入和刪除一個(gè)結(jié)點(diǎn)，其時(shí)間復(fù)雜度都是O(1)。（）

答案:對(duì)線性表L=（a1,a2,…,an）用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個(gè)元素平均需要移動(dòng)元素的個(gè)數(shù)是（）。

答案:(n-1)/2用鄰接表表示圖進(jìn)行廣度優(yōu)先遍歷時(shí)，通常是采用（）來實(shí)現(xiàn)算法。

答案:隊(duì)列用S表示入棧操作，X表示出棧操作，若元素入棧的順序?yàn)?234，為了得到1342出棧順序，相應(yīng)的S和X的操作串為（）。

答案:SXSSXSXX棧和隊(duì)都是（）

答案:限制存取點(diǎn)的線性結(jié)構(gòu)棧R,從頂?shù)降?{2,4,6,8,10},逐個(gè)取出放入隊(duì)列Q中，再從Q中逐個(gè)取出放入R中，問現(xiàn)在棧R中從頂?shù)降椎捻樞驗(yàn)椋ǎ?/p>

答案:{10,8,6,4,2}某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則采用（）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。

答案:僅有尾指針的單循環(huán)鏈表有向圖G用鄰接矩陣存儲(chǔ)，其第i行的所有非無窮大元素個(gè)數(shù)等于頂點(diǎn)i的出度（）。

答案:對(duì)有下面的程序段：chara[3],b[]="China";a=b;printf("%s",a);則（）。

答案:編譯出錯(cuò)有8個(gè)頂點(diǎn)的無向圖最多有（）條邊。

答案:28有11個(gè)葉結(jié)點(diǎn)的哈夫曼樹共有（）個(gè)結(jié)點(diǎn)。

答案:21數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)通常有（）。

答案:順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)、索引結(jié)構(gòu)和散列結(jié)構(gòu)折半查找過程可以利用一棵稱之為“判定樹”的二叉樹來描述。在長度為12的序列中（假如第一個(gè)元素在序列中的位置為0）進(jìn)行折半查找，對(duì)應(yīng)判定樹的根結(jié)點(diǎn)右孩子的值（即：某元素在序列中的位置）是（）。

答案:8快速排序在平均情況下的時(shí)間復(fù)雜度為（）。

答案:.O(nlogn)當(dāng)一棵有n個(gè)結(jié)點(diǎn)的二叉樹按層次從上到下，同層次從左到右將數(shù)據(jù)存放在一維數(shù)組A[l..n]中時(shí)，數(shù)組中第i個(gè)結(jié)點(diǎn)的左孩子為（）。

答案:無法確定度為k的樹中，第i層最多有（）個(gè)結(jié)點(diǎn)（i≥1）。（2的冪指數(shù)可表示為形如2^(n+1)形式）

答案:k^(i-1)已知某有向圖G=(V,E)，其中V={v1,v2,v3,v4,v5,v6}，E={,,,,,,,}，G的拓?fù)湫蛄惺牵ǎ?/p>

答案:v3v1v4v5v2v6已知序列25,13,10,12,9是大頂堆，在序列尾部插入新元素18，將其再調(diào)整為大頂堆。調(diào)整過程中元素之間進(jìn)行的比較次數(shù)是（）。

答案:2已知二叉樹的前序遍歷序列為ABDCEFG,中序遍歷序列是DBCAFEG,則其后序遍歷序列為（）。

答案:DCBFGEA已知一算術(shù)表達(dá)式的中綴形式為A+B*C-D/E，后綴形式為ABC*+DE/-，其前綴形式為（）。

答案:-+A*BC/DE已知一個(gè)長度為16的順序表L，其元素按關(guān)鍵字有序排列。若采用折半查找法查找一個(gè)L中不存在的元素，則關(guān)鍵字比較次數(shù)最多為（）。

答案:5己知循環(huán)隊(duì)列存儲(chǔ)在一維數(shù)組A[0-n-1]中，且隊(duì)列非空時(shí)front和rear分別指向隊(duì)頭元素和隊(duì)尾元索。若初始時(shí)隊(duì)列為空，且要求第1個(gè)進(jìn)入隊(duì)列的元素存儲(chǔ)在A[0]處，則初始時(shí)front和rear的值分別是（）。

答案:0,n-1將森林F轉(zhuǎn)換為對(duì)應(yīng)的二叉樹T，F(xiàn)中葉結(jié)點(diǎn)的個(gè)數(shù)等于（）。

答案:T中左孩子指針為空的結(jié)點(diǎn)個(gè)數(shù)將數(shù)據(jù)元素2,4,6,8,10,12,14,16,18,20依次存放于一個(gè)一維數(shù)組中，然后采用折半查找方法查找元素12，被比較過的數(shù)組元素的下標(biāo)依次為（）。

答案:4,7,5對(duì)序列(49,38,65,97,76,13,47,50)采用折半插入排序法進(jìn)行排序，若把第7個(gè)元素47插入到已排序序列中，為尋找插入的合適位置需要進(jìn)行（）次元素間的比較。

答案:3對(duì)含有n條邊的無向圖而言，其鄰接表中邊數(shù)為（）。

答案:2n對(duì)具有n個(gè)結(jié)點(diǎn)的完全二叉樹按照層次從上到下，每一層從左到右的次序?qū)λ薪Y(jié)點(diǎn)進(jìn)行編號(hào)，編號(hào)為i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為（）。（從1開始編號(hào)，用[x]表示對(duì)x向下取整）

答案:[i/2]對(duì)于長度為9的有序順序表，若采用折半搜索，在等概率情況下搜索成功的平均搜索長度為（）的值除以9。

答案:25對(duì)于含有n個(gè)頂點(diǎn)e條邊的無向連通圖，利用Kruskal算法生成最小生成樹，其時(shí)間復(fù)雜度為（）。

答案:O(elog2e)對(duì)一組數(shù)據(jù)（84，47，25，15，21）排序，數(shù)據(jù)的排列次序在排序的過程中的變化為（1）8447251521（2）1547258421（3）1521258447（4）1521254784則采用的排序是（）。

答案:選擇對(duì)N個(gè)元素的表做順序查找時(shí)，若查找每個(gè)元素的概率相同，則平均查找長度為（）。

答案:（N+1）/2如果n個(gè)頂點(diǎn)的圖是一個(gè)環(huán)，則它有（）棵生成樹。

答案:n在非空雙向循環(huán)鏈表中由q所指的那個(gè)鏈結(jié)點(diǎn)前面插入一個(gè)由p所指的鏈結(jié)點(diǎn)的動(dòng)作所對(duì)應(yīng)的語句依次為：p->rlink=q;p->llink=q->llink;q->llink=p;（）。(此處為一條賦值語句)

答案:p->llink->rlink=p;在有序表(k1,k2,...,k99)中采用折半查找方法查找99次，其中至少有一個(gè)元素被比較了99次，該元素是（）。

答案:k50在二叉查找樹中進(jìn)行查找的效率與（）有關(guān)。

答案:二叉查找樹的深度在一棵度為4的樹T中，若有20個(gè)度為4的結(jié)點(diǎn)，10個(gè)度為3的結(jié)點(diǎn)，1個(gè)度為2的結(jié)點(diǎn)，10個(gè)度為1的結(jié)點(diǎn)，則樹T的葉節(jié)點(diǎn)個(gè)數(shù)是（）。

答案:82在一個(gè)長度為n的順序表中第i個(gè)元素（1≤i≤n）之前插入一個(gè)元素時(shí)，需向后移動(dòng)（）個(gè)元素。

答案:n-i+1在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于圖的邊數(shù)的（）倍。

答案:2在一個(gè)單向循環(huán)鏈表中，若要在p所指向的結(jié)點(diǎn)之后插入一個(gè)新結(jié)點(diǎn)，則需要相繼修改（）個(gè)指針域的值。

答案:2在一個(gè)具有n個(gè)鏈結(jié)點(diǎn)的線性鏈表中查找某一個(gè)鏈結(jié)點(diǎn)，若查找成功，需要平均比較（）個(gè)鏈結(jié)點(diǎn)。

答案:(n+1)/2在一個(gè)以h為頭節(jié)點(diǎn)的單循環(huán)鏈表中，p指針指向鏈尾節(jié)點(diǎn)的條件是（）。

答案:p->next==h圖的深度優(yōu)先遍歷類似于二叉樹的（）。

答案:前序遍歷圖中頂點(diǎn)的度是指依附于該頂點(diǎn)的邊的數(shù)目，有向圖中的頂點(diǎn)還有出度和入度之分。在圖G的鄰接表表示中，每個(gè)頂點(diǎn)鄰接表中所含的結(jié)點(diǎn)數(shù)，對(duì)于無向圖來說等于該頂點(diǎn)的度（）。

答案:對(duì)函數(shù)squeez(chars[],charc)的功能是刪除字符串s中所出現(xiàn)的與變量c相同的字符。補(bǔ)全下面程序，請(qǐng)選擇（）。voidsqueez(chars[],charc){inti,j;for(i=j=0;s[i]!=‘\0’;i++)if(s[i]!=c)______;s[j]=‘\0’;}

答案:s[j++]=s[i]函數(shù)index(chars[],chart[])檢查字符串s中是否包含字符串t，若包含，則返回t在s中的開始位置(下標(biāo)值)，否則返回-1。補(bǔ)全下面程序請(qǐng)選擇（）。intindex(chars[],chart[]){inti,j,k;for(i=0;s[i]!=‘\0’;i++){for(j=i,k=0;t[k]!=‘\0’&&s[j]==t[k];j++,k++);if(_______)returni;}return-1;}

答案:t[k]==‘\0’任何一個(gè)無向連通圖的最小生成樹（）。

答案:一棵或多棵以下給字符數(shù)組str定義和賦值正確的是（）。

答案:charstr[]="China";以下正確的說明語句是（）。

答案:inta[5],*num[5]={&a[0],&a[1],&a[2],&a[3],&a[4]};以下與int*q[5];等價(jià)的定義語句是（）。

答案:int*(q[5]);為解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問題，通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是（）。

答案:隊(duì)列為實(shí)現(xiàn)快速排序算法，待排序序列宜采用的存儲(chǔ)方式是（）。

答案:順序存儲(chǔ)中綴表達(dá)式A-(B+C/D)×E的后綴形式是（）。

答案:ABCD/+E×-中綴表達(dá)式3+x*(2.4/5-6)所對(duì)應(yīng)的后綴表達(dá)式為（）。

答案:3x2.45/6-*+下面能正確進(jìn)行字符串賦值，并且能確保字符串以’\0’結(jié)尾的操作是（）。

答案:char*s;s="ABCDE";下面程序段的運(yùn)行結(jié)果是（B）。charc[]="\t\v\\\0will\n";printf("%d",strlen（）);

答案:9下面的函數(shù)invert的功能是將一個(gè)字符串的內(nèi)容顛倒過來。補(bǔ)全下面函數(shù)請(qǐng)選擇（）。voidinvert(charstr[]){inti,j,k;for(i=0,j=strlen(str)-1;i答案:i++,j—下面有關(guān)本節(jié)圖的遍歷算法的描述中，正確的是（）。

答案:廣度優(yōu)先遍歷算法要利用一個(gè)隊(duì)列數(shù)據(jù)結(jié)構(gòu)來保證頂點(diǎn)的訪問順序下面有關(guān)本節(jié)圖的遍歷算法應(yīng)用的描述中，正確的是（）。

答案:應(yīng)用代碼實(shí)現(xiàn)中采用是鄰接表來存儲(chǔ)圖數(shù)據(jù)的下面關(guān)于線性