[ppt模板]數(shù)據(jù)結(jié)構(gòu)線性表試題(已修改)
2025-01-27 06:15 本頁面
【正文】 第2章 選擇題1．對于線性表最常用的操作是查找指定序號的元素和在末尾插入元素，則選擇（ ）最節(jié)省時間 A）順序表 B）帶頭結(jié)點(diǎn)的雙循環(huán)鏈表 C）單鏈表 D）帶尾結(jié)點(diǎn)的單循環(huán)鏈表 【答案】A 2．若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個位置插入一個新元素的算法時間復(fù)雜度為（ ?。?1≤i≤n+1)。 A） O(0) B） O(1) C） O(n) D） O(n2) 【答案】C 3．雙向鏈表中有兩個指針域，prior和next，分別指向前驅(qū)及后繼，設(shè)p指向鏈表中的一個結(jié)點(diǎn)，q指向一待插入結(jié)點(diǎn)，現(xiàn)要求在p前插入q，則正確的插入為（ ） A） pprior=q。 qnext=p。 ppriornext=q。 qprior=pprior。 B） qprior=pprior。 ppriornext=q。 qnext=p。 pprior=qnext。 C） qnext=p。 pnext=q。 ppriornext=q。 qnext=p。 D） ppriornext=q。 qnext=p。 qprior=pprior。 pprior=q。 【答案】D 4．在一個具有n個結(jié)點(diǎn)的有序單鏈表中插入一個新結(jié)點(diǎn)并仍然保持有序的時間復(fù)雜度是（ ） A）O(nlog2n） B） O(1） C） O(n） D） O(n2） 【答案】C 5． 在一個以 h 為頭指針的單循環(huán)鏈中，p 指針指向鏈尾結(jié)點(diǎn)的條件是（ ） A）pnext==NULL B） pnext==h C）pnextnext==h D） pdata==1 【答案】B 6．對于一個具有n個結(jié)點(diǎn)的線性表，建立其單鏈表的時間復(fù)雜度是（ ） A）O(n) B） O(1) C）O(nlog2n) D） O(n2) 【答案】A 8．在雙向鏈表存儲結(jié)構(gòu)中，刪除p所指的結(jié)點(diǎn)時須修改指針（ ） A）ppriornext=pnext pnextprior=pprior。 B）pprior=ppriorprior ppriornext=p。 C）pnextprior=p pnext=pnextnext D）pnext=ppriorprior pprior=pnextnext。 【答案】A 9．線性表采用鏈?zhǔn)酱鎯r，其元素地址（ ?。?A）必須是連續(xù)的 B）一定是不連續(xù)的 C）部分地址是連續(xù)的 D）連續(xù)與否均可 【答案】D 填空題1．線性表L=（a1，a2，…，an）用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個元素平均需要移動元素的個數(shù)是_____________。 【答案】（n1）/2 2．在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是_____________。 【答案】主要是使插入和刪除等操作統(tǒng)一，在第一個元素之前插入元素和刪除第一個結(jié)點(diǎn)不必另作判斷。另外，不論鏈表是否為空，鏈表頭指針不變。 3．線性表的順序存儲是通過_____________來反應(yīng)元素之間的邏輯關(guān)系，而鏈?zhǔn)酱鎯Y(jié)構(gòu)是通過_____________來反應(yīng)元素之間的邏輯關(guān)系。 【答案】（1）數(shù)據(jù)元素的前后順序 （2）元素中的指針 4．當(dāng)對一個線性表經(jīng)常進(jìn)行的是存取操作，而很少進(jìn)行插入和刪除操作時，則采用_____________存儲結(jié)構(gòu)最節(jié)省時間，相反當(dāng)經(jīng)常進(jìn)行插入和刪除操作時，則采用_____________存儲結(jié)構(gòu)最節(jié)省時間。 【答案】（1）順序 （2）鏈?zhǔn)?5．對于一個具有n個結(jié)點(diǎn)的單鏈表，在已知的結(jié)點(diǎn)*p后插入一個新結(jié)點(diǎn)的時間復(fù)雜度為_____________，在給定值為x的結(jié)點(diǎn)后插入一個新結(jié)點(diǎn)的時間復(fù)雜度為_____________。 【答案】（1）O(1) （2）O(n) 7. 對于雙向鏈表，在兩個結(jié)點(diǎn)之間插入一個新結(jié)點(diǎn)需修改的指針共_____________個，單鏈表為_____________個。 【答案】（1）4 （2）2 8. 循環(huán)單鏈表的最大優(yōu)點(diǎn)是_____________。 【答案】從任一結(jié)點(diǎn)出發(fā)都可訪問到鏈表中每一個元素。 9．若要在一個不帶頭結(jié)點(diǎn)的單鏈表的首結(jié)點(diǎn)*p結(jié)點(diǎn)之前插入一個*s結(jié)點(diǎn)時，可執(zhí)行下列操作： snext=_____________。 pnext=s。 t=pdata。 pdata= _____________。 sdata=_____________。 【答案】（1）pnext （2）sdata （3） t 10．某線性表采用順序存儲結(jié)構(gòu)，每個元素占據(jù)4個存儲單元，首地址為100，則下標(biāo)為11的（第12個）元素的存儲地址為_____________。 【答案】144 11．帶頭結(jié)點(diǎn)的雙循環(huán)鏈表L中只有一個元素結(jié)點(diǎn)的條件是_____________。 【答案】Lnextnext==L 判斷題1．取線性表的第i個元素的時間同i的大小有關(guān)（ ?。?【答案】 2．線性表的特點(diǎn)是每個元素都有一個前驅(qū)和一個后繼（ ?。?【答案】 3． 順序存儲方式的優(yōu)點(diǎn)是存儲密度大，且插入、刪除運(yùn)算效率高（ ?。?【答案】 4．線性表采用鏈表存儲時，結(jié)點(diǎn)的存儲空間可以是不連續(xù)的（ ?。?【答案】√ 5．鏈表是采用鏈?zhǔn)酱鎯Y(jié)構(gòu)的線性表，進(jìn)行插入、刪除操作時，
試題試卷相關(guān)推薦
鄂ICP備17016276號-1