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

1、第1章概論概論練習題練習題一、單項選擇題一、單項選擇題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動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)2若結(jié)點的存儲地址與其關(guān)鍵字之間存在某種映射關(guān)系，則稱這種存儲結(jié)構(gòu)為（D）A順序存儲結(jié)構(gòu)B鏈式存儲結(jié)構(gòu)C索引存儲結(jié)構(gòu)D散列存儲結(jié)構(gòu)3算法分析的兩個主要方面是（B）A正確性和簡明性B時間復雜性和空間復雜性C可讀性和可維護性D數(shù)據(jù)復雜性和程序復雜性4線性表采

2、用鏈式存儲結(jié)構(gòu)時，要求內(nèi)存中可用存儲單元地址（A）A不一定連續(xù)的B部分地址必須是連續(xù)的C必須是連續(xù)的D一定是不連續(xù)的5算法指的是（C）A計算機程序B解決問題的計算方法C解決問題的有限運算序列D排序算法二、填空題二、填空題6數(shù)據(jù)結(jié)構(gòu)一般包括邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和數(shù)據(jù)運算三個方面的內(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)、鏈式存儲結(jié)構(gòu)、索引存儲結(jié)構(gòu)及散列存儲結(jié)構(gòu)等四種存儲方法表示9

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

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

5、若刪除p指向結(jié)點的后繼結(jié)點，則執(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在一個長度為n的順序表中刪除第i個元素，需要向前移動n??i個元素8在順序表中插入或刪除一個元素，需要平均移動表長的一半個