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