數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)試題2(編輯修改稿)
2025-05-14 01:47 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 （19） 廣義表LS=（a,(b),((c,(d)))）的深度是 4 。（21） 廣義表LS=（a,(b),((c,(d)))）的表尾是 ((b),((c,(d)))) 。(22)數(shù)組元素a[0..2][0..3]的實(shí)際地址上2000，元素長(zhǎng)度是4，則LOC[1,2]= 2024 。（23） n階下三角矩陣，因?yàn)閷?duì)角線的上方是同一個(gè)常數(shù)，需要 n（n1）/2+1 個(gè)存儲(chǔ)單元。（24）稀疏矩陣的三元組有 3 列。（25）稀疏矩陣的三元組中第1列存儲(chǔ)的是數(shù)組中非零元素所在的 行數(shù) 。（26）n階對(duì)稱矩陣，如果只存儲(chǔ)下三角元素，只需要 n（n1）/2 個(gè)存儲(chǔ)單元。(27)哈夫曼樹是帶權(quán)路徑長(zhǎng)度 最小 的二叉樹。(28)由二叉樹的后序和 中序 遍歷序列，可以唯一確定一棵二叉樹。（29）某二叉樹的中序遍歷序列為: DEBAC，后序遍歷序列為：EBCAD。則前序遍歷序列為：DABEC 。（30）設(shè)一棵二叉樹結(jié)點(diǎn)的先序遍歷序歷為：ABDECFGH，中序遍歷序歷為：DEBAFCHG，則二叉樹中葉結(jié)點(diǎn)是： E、F、H 。（31）對(duì)于二叉樹來說，第i層上至多有 2i1 個(gè)結(jié)點(diǎn)。（32）深度為h的二叉樹至多有 2h1 個(gè)結(jié)點(diǎn)。（33）采用二叉鏈表存儲(chǔ)的n個(gè)結(jié)點(diǎn)的二叉樹，一共有 2n 個(gè)指針域。（34）采用二叉鏈表存儲(chǔ)的n個(gè)結(jié)點(diǎn)的二叉樹，共有空指針 n+1 個(gè)。（35）將一棵完全二叉樹按層次編號(hào)，對(duì)于任意一個(gè)編號(hào)為i的結(jié)點(diǎn)，其左孩子結(jié)點(diǎn)的編號(hào)為： 2*i 。（36）圖常用的存儲(chǔ)方式有鄰接矩陣和 鄰接表 等。（37）圖的遍歷有： 深度優(yōu)先搜 和廣度優(yōu)先搜等方法。（38）設(shè)有一稀疏圖G，則G采用 _鄰接表____存儲(chǔ)比較節(jié)省空間。(39)設(shè)有一稠密圖G，則G采用 _鄰接矩陣____存儲(chǔ)比較節(jié)省空間。(40)在關(guān)鍵字序列（7，10，12，18，28，36，45，92）中，用二分查找法查找關(guān)鍵字92，要比較 4 次才找到。(41)二叉排序樹是一種 動(dòng)態(tài) 查找表。(42)哈希表是按 散 列 存儲(chǔ)方式構(gòu)造的存儲(chǔ)結(jié)構(gòu)(43)哈希法既是一種存儲(chǔ)方法，又是一種 查找 方法。(44)散列表的查找效率主要取決于散列表造表時(shí)選取的散列函數(shù)和處理 沖突 的方法。三、程序填空（1）在帶頭結(jié)點(diǎn)head的單鏈表的結(jié)點(diǎn)a之后插入新元素x，試完成下列程序填空。struct node{ elemtype data。 node *next。}。void lkinsert (node *head, elemtype x){ node *s, *p。s= new node 。sdata= x 。 p=headnext。while (p!=NULL) amp。amp。 ( pdata!=a )____p=pnext 。if (p==NULL)cout 不存在結(jié)點(diǎn)a! 。 else {_____snext=pnext______。___ pnext=s __________。}}(2)假定用一個(gè)循環(huán)單鏈表表示一個(gè)循環(huán)隊(duì)列，該隊(duì)列只設(shè)一個(gè)隊(duì)尾指針rear，試填空完成向循環(huán)隊(duì)列中插入一個(gè)元素為x的結(jié)點(diǎn)的函數(shù)。typedef struct queuenode // 定義隊(duì)列的存儲(chǔ)結(jié)構(gòu){ int data。 struct queuenode *next。}QueueNode。InQueue(QueueNode *rear,int x) // 向隊(duì)列插入元素為x的函數(shù){ QueueNode *rear。QueueNode *head,*s。 s= new QueueNode 。 sdata= x 。 if(rear==NULL) // 循環(huán)隊(duì)列為空，則建立一個(gè)結(jié)點(diǎn)的循環(huán)隊(duì)列 { rear=s。 rearnext。} else{ head= rearnext 。 // 循環(huán)隊(duì)列非空，則將s插到后面rearnext= s 。rear=s。rearnext =head。}}（3）下面程序是把兩個(gè)串r1和r2首尾相連的程序，即：r1=r1+r2，試完成程序填空。typedef Struct{ char vec[MAXLEN]。 // 定義合并后串的最大長(zhǎng)度int len。 // len為串的長(zhǎng)度}St 。void ConcatStr(Str *r1,Str *r2) // 字符串連接函數(shù){ int i。 coutr1vecr2vec。 if(r1len+r2len MAXLEN ) cout兩個(gè)串太長(zhǎng)，溢出！。 else { for(i=0。i r2len 。i++) // 把r2連接到r1 r1vec[ r1len+i ]=r2vec[i]。 r1vec[r1len+i]= 39。\039。 。 // 添上字符串結(jié)束標(biāo)記 r1len= r1len+r2len 。 // 修改新串長(zhǎng)度 }}(4)下面算法是判斷字符串是否為回文（即正讀和倒讀相同），試完成程序填空。include typedef struct{ char vec[MAXLEN]。 int len。}str。void Palindrome (str s)
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1