清華大學(xué) - 話題

    清華大學(xué)2005年計(jì)算機(jī)專業(yè)-數(shù)據(jù)結(jié)構(gòu)試題
    查看(1410) 回復(fù)(0)
    小白楊
    • 積分:482
    • 注冊(cè)于:
    發(fā)表于
    樓主
    數(shù)據(jù)結(jié)構(gòu):
    第一題:15分
    1。線性表的定義,表中元素是否必須是同一個(gè)類型,為什么?

    2。線性表有兩種存儲(chǔ)形式,定義如下,然后給了一個(gè)線性鏈表類的空架字,一個(gè)
    靜態(tài)數(shù)組實(shí)現(xiàn)類,一個(gè)單鏈表實(shí)現(xiàn)類,后兩個(gè)繼承于第一個(gè)。問使用時(shí)如何選用哪
    種類型的實(shí)現(xiàn)。

    3。二叉樹給你前序和中序排列,求后序
    所給序列已經(jīng)記不清了,可能是前序ABDEFCFHIJ,中序DBCEAFCHIJ。

    4。B樹相關(guān)計(jì)算
    一個(gè)磁盤塊大小4,000(實(shí)際為4096,但是為計(jì)算方便,按4000算),一個(gè)地址指
    針需要5個(gè)字節(jié)。有一個(gè)有20,000,000條記錄的文件。一個(gè)關(guān)鍵字占5個(gè)字節(jié),求
    B樹的最大階數(shù),當(dāng)記錄不是按順序排列時(shí),求索引需要占用的磁盤塊數(shù)。

    5。散列有n個(gè)位置,0~n-1。判斷散列函數(shù)是否正確,插入和查找是否能正確執(zhí)行
    ,如正確,判斷好壞,不正確說明原因。random(n)函數(shù)能隨機(jī)產(chǎn)生0~n-1之間的數(shù)

    1) H(Key)=Key/n;
    2) H(Key)=1;
    3) H(Key+random(n))%n;
    4) H(Key)%p(n),其中p(n)是比n小的素?cái)?shù)


    第2題:5分
    證明:在前序序列、中序序列和后序序列中葉節(jié)點(diǎn)相對(duì)(前后)的排列位置不變

    第3題:15分
    AVL樹的插入和刪除
    1) 從空樹開始插入數(shù)值,(數(shù)值序列也記不清楚了,只能寫個(gè)大概,大家參考20,12,
    9,27,22,17,16,15,18,10),畫出插入后的狀態(tài),如需旋轉(zhuǎn),標(biāo)明旋轉(zhuǎn)的種類(有單右
    旋轉(zhuǎn),單左旋轉(zhuǎn),先左后右旋轉(zhuǎn),先右后左旋轉(zhuǎn)).
    2) 從剛才生成的AVL樹中刪除22,...,9和10,畫出刪除后的狀態(tài)和旋轉(zhuǎn)的類型.刪除
    的非葉子結(jié)點(diǎn)用中序前趨結(jié)點(diǎn)代替.

    第4題:
    圖類
    template class Graph{
    int numberOfVectise(Graph G){}//返回圖中頂點(diǎn)數(shù)
    .
    .
    .
    }
    1) 在圖中用dijsktla算法求從u點(diǎn)出發(fā)到各個(gè)點(diǎn)的最短路徑算.5分
    template void shortestdist(Graph G,int v, float
    *dist,int *path){
    //在圖G中求由點(diǎn)c出發(fā)到各點(diǎn)的最點(diǎn)路徑,路徑長度放在數(shù)組dist中,路徑放在數(shù)組
    path里,maxWeight是float型所能表示的最大值
    int n=numberOfVectise(G);
    int *S=new int[n];
    for(int i=0;i {
    ......
    if(value(u,i) else path=-1;
    ....

    后面有兩個(gè)空是if()中&&之前的第一個(gè)判斷條件

    }
    }
    整個(gè)函數(shù)太長,我記不得了,書上應(yīng)該是有的.

    2) 在一個(gè)圖中,從u點(diǎn)出發(fā),到圖中各個(gè)點(diǎn)的最短路徑中距離最長的叫做點(diǎn)u在這個(gè)
    圖中的偏心距.圖中偏心距最小的點(diǎn)叫做中心.設(shè)計(jì)算法求一個(gè)圖的中心.函數(shù)頭為
    template int centre(Graph G, float &mindist);
    函數(shù)返回值是中心點(diǎn)編號(hào),mindist返回的是最小偏心距.10分
    這個(gè)題我記得練習(xí)冊(cè)上有原題,只是換了一種表述,實(shí)質(zhì)是一樣的.

    回復(fù)話題
    上傳/修改頭像

    武漢是哪個(gè)省的省會(huì)城市(答案為兩個(gè)字)?

    考研論壇提示:
    1、請(qǐng)勿發(fā)布個(gè)人聯(lián)系方式或詢問他人聯(lián)系方式,包括QQ和手機(jī)等。
    2、未經(jīng)允許不得發(fā)布任何資料出售、招生中介等廣告信息。
    3、如果發(fā)布了涉及以上內(nèi)容的話題或跟帖,您在考研網(wǎng)的注冊(cè)賬戶可能被禁用。

    網(wǎng)站介紹 | 關(guān)于我們 | 聯(lián)系方式 | 廣告業(yè)務(wù) | 幫助信息
    ©1998-2015 ChinaKaoyan.com Network Studio. All Rights Reserved.

    中國考研網(wǎng)-聯(lián)系地址:上海市郵政信箱088-014號(hào) 郵編:200092 Tel & Fax:021 - 5589 1949 滬ICP備12018245號(hào)

    中文字幕人妻无码一夲道| 亚洲AV永久无码精品网站在线观看| 最近中文字幕大全2019| 水蜜桃av无码一区二区| 忘忧草在线社区WWW中国中文 | 国99精品无码一区二区三区| 中文字幕AV一区中文字幕天堂| 中文字幕无码精品三级在线电影| 毛片一区二区三区无码| 精品亚洲AV无码一区二区| 亚洲AV无码之日韩精品| 亚洲日韩激情无码一区| 波多野结衣中文在线| 成人无码区在线观看| 国产成人无码精品久久久性色| 五月天无码在线观看| 无码中文av有码中文a| 中文字幕天天躁日日躁狠狠躁免费| 亚洲AV无码AV男人的天堂| 中文字幕日韩在线| 亚洲AⅤ无码一区二区三区在线 | 国产成人无码综合亚洲日韩| 中文无码vs无码人妻| 日韩亚洲国产中文字幕欧美| 日木av无码专区亚洲av毛片 | 亚洲熟妇中文字幕五十中出| 国产成年无码久久久久毛片| 久久精品无码一区二区WWW| 中文成人无字幕乱码精品区| gogo少妇无码肉肉视频| 超清无码熟妇人妻AV在线电影| 久久最近最新中文字幕大全| 免费无码又爽又黄又刺激网站| 亚洲AV无码国产精品色午友在线| 亚洲国产综合精品中文字幕| 中文有码vs无码人妻| 伊人久久大香线蕉无码麻豆| 精品无码国产污污污免费网站| 亚洲AV无码一区二区二三区软件 | 亚洲AV永久无码天堂影院| 99精品人妻无码专区在线视频区 |