數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題目

1、第1章概論概論練習(xí)題練習(xí)題一、單項(xiàng)選擇題一、單項(xiàng)選擇題1在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（B）A緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)B線性結(jié)構(gòu)和非線性結(jié)構(gòu)C內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)D動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)2若結(jié)點(diǎn)的存儲地址與其關(guān)鍵字之間存在某種映射關(guān)系，則稱這種存儲結(jié)構(gòu)為（D）A順序存儲結(jié)構(gòu)B鏈?zhǔn)酱鎯Y(jié)構(gòu)C索引存儲結(jié)構(gòu)D散列存儲結(jié)構(gòu)3算法分析的兩個(gè)主要方面是（B）A正確性和簡明性B時(shí)間復(fù)雜性和空間復(fù)雜性C可讀性和可維護(hù)性D數(shù)據(jù)復(fù)雜性和程序復(fù)雜性4線性表采

2、用鏈?zhǔn)酱鎯Y(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲單元地址（A）A不一定連續(xù)的B部分地址必須是連續(xù)的C必須是連續(xù)的D一定是不連續(xù)的5算法指的是（C）A計(jì)算機(jī)程序B解決問題的計(jì)算方法C解決問題的有限運(yùn)算序列D排序算法二、填空題二、填空題6數(shù)據(jù)結(jié)構(gòu)一般包括邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和數(shù)據(jù)運(yùn)算三個(gè)方面的內(nèi)容7數(shù)據(jù)的邏輯結(jié)構(gòu)可分為線性結(jié)構(gòu)、非線性結(jié)構(gòu)兩大類8數(shù)據(jù)的存儲結(jié)構(gòu)（物理結(jié)構(gòu)）一般可以用順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)、索引存儲結(jié)構(gòu)及散列存儲結(jié)構(gòu)等四種存儲方法表示9

3、在選用求解一個(gè)問題的算法時(shí)，除了首先考慮算法是“正確的”之外，還主要考慮執(zhí)行算法所需要的時(shí)間、執(zhí)行算法所需要的存儲空間及算法應(yīng)易于理解、易于編程、易于調(diào)試等三點(diǎn)。10設(shè)有一批數(shù)據(jù)元素，為了最快地存取某元素，宜用順序結(jié)構(gòu)存儲，為了方便的插入一個(gè)元素，宜用鏈?zhǔn)浇Y(jié)構(gòu)存儲三、應(yīng)用題三、應(yīng)用題設(shè)n為正整數(shù)，利用大“O”記號，寫出下列各程序段的時(shí)間復(fù)雜度11f(i=1inext==headChead?next==NULLDhead==NULL4在單

4、循環(huán)鏈表中，p指向表任一結(jié)點(diǎn)，判斷表不是訪問結(jié)束的條件是（B）Ap!=NULLBp!=headCp?next!=headDp?next!=NULL5在一個(gè)單鏈表中，已知q指向p所指向結(jié)點(diǎn)的前趨結(jié)點(diǎn)，若在p、q所指結(jié)點(diǎn)之間插入一個(gè)s所指向的新結(jié)點(diǎn)，則執(zhí)行的操作是（A）Aq?next=ss?next=pBp?next=ss?next=qCs?next=p?nextp?next=sDp?next=s?nexts?next=p6在一個(gè)單鏈表中，

5、若刪除p指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行的操作是（A）Aq=p?nextp?next=p?next?nextfree(q)Bp=p?nextq=p?nextp=q?nextfree(q)Cq=p?next?nextp=p?nextfree(q)Dp=p?next?nextq=p?nextfree(q)二、填空題二、填空題7在一個(gè)長度為n的順序表中刪除第i個(gè)元素，需要向前移動(dòng)n??i個(gè)元素8在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng)表長的一半個(gè)