數(shù)據(jù)結(jié)構(gòu)習(xí)題及答案.doc

數(shù)據(jù)結(jié)構(gòu)習(xí)題及答案,全國(guó)2010年1月自考數(shù)據(jù)結(jié)構(gòu)試題及答案
全國(guó)年月自考數(shù)據(jù)結(jié)構(gòu)試題及答案表格
全國(guó)年月自考數(shù)據(jù)結(jié)構(gòu)試題及答案
課程代碼：

一、單項(xiàng)選擇題本大題共小題，每小題分，共分
在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無(wú)分。
若一個(gè)算法的時(shí)間復(fù)雜度用表示，其中的含義是
問題規(guī)模語(yǔ)句條數(shù)
循環(huán)層數(shù)函數(shù)數(shù)量
具有線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)是
樹圖
棧和隊(duì)列廣義表
線性結(jié)構(gòu)有：順序表、棧和隊(duì)列、串
將長(zhǎng)度為的單鏈表連接在長(zhǎng)度為的單鏈表之后，其算法的時(shí)間復(fù)雜度為


+在帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表中插入一個(gè)新結(jié)點(diǎn)，需要修改的指針域數(shù)量是
個(gè)個(gè)
個(gè)個(gè)
中
在帶頭結(jié)點(diǎn)的雙鏈表中，將值為的新結(jié)點(diǎn)插入結(jié)點(diǎn)之前，設(shè)≠

①
②
③
④
⑤
⑥

假設(shè)以數(shù)組存放循環(huán)隊(duì)列的元素，其頭指針是，當(dāng)前隊(duì)列有個(gè)元素，則隊(duì)列的尾指針值為


輔導(dǎo)書中
對(duì)于循環(huán)向量中的循環(huán)隊(duì)列，寫出通過(guò)隊(duì)頭隊(duì)尾指針表示的隊(duì)列長(zhǎng)度公式。指向?qū)嶋H隊(duì)頭，指向?qū)嶋H隊(duì)尾的下一元素位置。
當(dāng)≥時(shí)，隊(duì)列長(zhǎng)度；當(dāng)時(shí)，+。這兩種情況可統(tǒng)一為+，這里為向量的大小。本題中
若棧采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，則下列說(shuō)法中正確的是
需要判斷棧滿且需要判斷棧空
不需要判斷棧滿但需要判斷�；�?br>需要判斷棧滿但不需要判斷�？�
不需要判斷棧滿也不需要判斷�？�
中
因?yàn)殒湕Ｖ械慕Y(jié)點(diǎn)是動(dòng)態(tài)分配的，可以不考慮上溢，所以無(wú)需定義運(yùn)算。
若串””，其子串的數(shù)目是


中
任意個(gè)連續(xù)字符組成的子序列稱為該串的子串。
設(shè)有一個(gè)階的下三角矩陣，采用行優(yōu)先壓縮存儲(chǔ)方式，為第一個(gè)元素，其存儲(chǔ)地址為，每個(gè)元素占一個(gè)地址單元，則的地址為


中
在階方陣這個(gè)下三角矩陣中，第從開始行≤有+個(gè)元素，元素總數(shù)為：+，并將元素放在一個(gè)向量+中。
若≥，則在左下三角矩陣中，與的對(duì)應(yīng)關(guān)系是++。
若，則在右上三角矩陣中，與的對(duì)應(yīng)關(guān)系是++。
若為第一個(gè)元素，與為第一個(gè)元素時(shí)的位置一樣，+，則的地址+；
若為第一個(gè)元素，與為第一個(gè)元素時(shí)的位置一樣，+，則的地址+；
允許結(jié)點(diǎn)共享的廣義表稱為
純表線性表
遞歸表再入表
下列數(shù)據(jù)結(jié)構(gòu)中，不屬于二叉樹的是樹是一種平衡的多叉樹
樹樹樹是自平衡二叉查找樹
二叉排序樹哈夫曼樹哈夫曼樹是最優(yōu)二叉樹
對(duì)下面有向圖給出了四種可能的拓?fù)湫蛄�，其中錯(cuò)誤的是輔導(dǎo)書中第題

，，，，，，，，，，
，，，，，，，，，，
以為起始結(jié)點(diǎn)對(duì)下圖進(jìn)行深度優(yōu)先遍歷，正確的遍歷序列是

，，，，，，，，，，，，
，，，，，，，，