面試題數(shù)據(jù)結(jié)構(gòu)2003.pdf

嵌入式系統(tǒng)開發(fā)人員C語(yǔ)言測(cè)試題 數(shù)據(jù)結(jié)構(gòu)與算法 姓名 得分 一 選擇題 共15題 每題3分 1 下面關(guān)于算法說(shuō)法錯(cuò)誤的是 a 算法最終必須由計(jì)算機(jī)程序?qū)崿F(xiàn) b 為解決某問(wèn)題的算法同為該問(wèn)題編寫的程序含義是相同的 c 算法的可行性是指指令不能有二義性 d 以上幾個(gè)都是錯(cuò)誤的 2 下面說(shuō)法錯(cuò)誤的是 a 算法原地工作的含義是指不需要任何額外的輔助空間 b 在相同的規(guī)模n下 復(fù)雜度O n 的算法在時(shí)間上總是優(yōu)于復(fù)雜度O 2n 的算法 c 所謂時(shí)間復(fù)雜度是指最壞情況下 估算算法執(zhí)行時(shí)間的一個(gè)上界 d 同一個(gè)算法 實(shí)現(xiàn)語(yǔ)言的級(jí)別越高 執(zhí)行效率就越低 3 在下面的程序段中 對(duì)x的賦值語(yǔ)句的頻度為 for int i i n i for int j o jLlink q q Rlink p p Llink Rlink q q Llink q b p Llink q p Llink Rlink q q Rlink p q Llink p Llink c q Rlink p q Llink p Llink p Llink Rlink q p Llink q d q Llink p Llink q Rlink q p Llink q p Llink q 13 下面說(shuō)法正確的是 a 順序存儲(chǔ)結(jié)構(gòu)的主要缺點(diǎn)是不利于插入或刪除操作 b 線性表采用鏈表存儲(chǔ)時(shí) 結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲(chǔ)空間可以是不連續(xù)的 c 順序存儲(chǔ)方式插入和刪除時(shí)效率太低 因此它不如鏈?zhǔn)酱鎯?chǔ)方式好 d 順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu) 14 下面說(shuō)法正確的是 a 線性表只能用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn) b 為了很方便的插入和刪除數(shù)據(jù) 可以使用雙向鏈表存放數(shù)據(jù) c 順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大 且插入 刪除運(yùn)算效率高 d 鏈表是采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表 進(jìn)行插入 刪除操作時(shí) 在鏈表中比在順序存儲(chǔ)結(jié) 構(gòu)中效率高 15 下面說(shuō)法正確的是 a 數(shù)據(jù)元素是數(shù)據(jù)的最小單位 b 隊(duì)列邏輯上是一個(gè)下端口和上端能增加又能減少的線性表 c 任何一個(gè)遞歸過(guò)程都可以轉(zhuǎn)換成非遞歸過(guò)程 d 只有那種使用了局部變量的遞歸過(guò)程在轉(zhuǎn)換成非遞歸過(guò)程時(shí)才必須使用棧 二 填空題 共5題 每題5分 1 下列程序的功能是創(chuàng)建單向鏈表 請(qǐng)補(bǔ)充完整 include include struct link char name 10 int mark struct link next void insert char name int mark struct link head NULL main char name 10 int mark struct link t while 1 scanf s d name if strcmp name 0 break 1 for t head 2 printf d n t name t mark void insert char name int mark struct link p p 3 strcpy p name name p mark mark 4 if head NULL 5 head p 2 用循環(huán)鏈表表示的隊(duì)列長(zhǎng)度為n 若只設(shè)頭指針 則出隊(duì)和入隊(duì)的時(shí)間復(fù)雜度分 別是 和 若只設(shè)尾指針 則出隊(duì)和入隊(duì)的時(shí)間復(fù)雜度分別是 和 3 在n個(gè)記錄的有序順序表中進(jìn)行折半查找 最大的比較次數(shù)是 4 仔細(xì)閱讀下列程序 在空白處填入適當(dāng)?shù)恼Z(yǔ)句 函數(shù)match s t 完成在字符串s中尋找與t匹配的字符 若存在一個(gè)匹配 則返回t在字符 串s中的下標(biāo) 否則 返回 1 其中 字符指針 b始終指向s的第一元素 Match s t Char s t char b s char p r for for p s r t r 0 p r if return s b return 1 5 補(bǔ)充下列程序 設(shè)一棵二叉序列樹b 下列算法函數(shù)是實(shí)現(xiàn)在b中插入一個(gè)結(jié)點(diǎn) s 函數(shù) void insert btree b btree s if b NULL b s else if s data b data return else if s data data else 三 簡(jiǎn)答題 共3題 每題10分 1 在一個(gè)包含 n 個(gè)元素的數(shù)組 M 中查找一個(gè)元素 x 算法假設(shè) M 已經(jīng)按升序 排列了