計(jì)算機(jī)組成原理 唐朔飛 考研真題詳解

計(jì)算機(jī)組成原理-唐朔飛-考研真題詳解1已知程序如下：intS（intn）{return（n<＝0）?0:s（n-1）+n;}voidmain（）{cout<<S（1）;}程序運(yùn)行時使用棧來保存調(diào)用過程的信息，自棧底到棧頂保存的信息依次對應(yīng)的是（??）。A．main（??）->S（1）->S（0）B．S（0）->S（1）->main（??）C．main（??）->S（0）->S（1）D．S（1）->S（0）->main（??）【答案】A查看答案【解析】函數(shù)S（intn）是一個遞歸函數(shù)：①當(dāng)實(shí)際參數(shù)小于等于零時則返回0，并終止遞歸；②當(dāng)實(shí)際參數(shù)大于零時則遞歸調(diào)用S（n-1），并將S（n-1）的結(jié)果加上n作為返回值。程序從main（??）函數(shù)開始，首先調(diào)用main（??）函數(shù)；在main（??）函數(shù)中調(diào)用S（1）函數(shù)時，將main（??）函數(shù)的上下文保存到棧中，并進(jìn)入函數(shù)S（1）；由于函數(shù)S（1）的實(shí)際參數(shù)大于零，需要調(diào)用S（0），故將S（1）函數(shù)的上下文保存到棧中，進(jìn)入S（0）；在S（0）中，實(shí)際參數(shù)小于等于零，遞歸終止。2先序序列為a，b，c，d的不同二叉樹的個數(shù)是（??）。A．13B．14C．15D．16【答案】B查看答案【解析】二叉樹的先序遍歷定義為：若二叉樹為空，則空操作；否則，訪問根節(jié)點(diǎn)，然后先序遍歷左子樹，最后先序遍歷右子樹。本題中，結(jié)點(diǎn)a為二叉樹的根節(jié)點(diǎn)，左右子樹的先序遍歷可能存在下面四種情況：①左子樹為空，bcd為右子樹；②b為左子樹，cd為右子樹；③bc為左子樹，d為右子樹；④bcd為左子樹，右子樹為空。然后將左右子樹繼續(xù)分解，如第①種情況的右子樹先序遍歷（bcd）可能有：a．左子樹為空，右子樹為cd；b．左子樹為c，右子樹為d；c．左子樹為cd，右子樹為空。按照這種方法繼續(xù)分解左右子樹，直到不能再分解為止，可得第①和④種情況各包含5種不同情況，第②和③種情況各包含2種情況，因此總共有14種不同的二叉樹。3下列選項(xiàng)給出的是從根分別到達(dá)兩個葉節(jié)點(diǎn)路徑上的權(quán)值序列，能屬于同一棵哈夫曼樹的是（??）。A．24，10，5和24，10，7B．24，10，5和24，12，7C．24，10，10和24，14，11D．24，10，5和24，14，6【答案】D查看答案【解析】哈夫曼樹是帶權(quán)路徑長度最短的二叉樹。由根節(jié)點(diǎn)出發(fā)到兩個葉子節(jié)路徑中，第二個被訪問的兩個節(jié)點(diǎn)的權(quán)值要么相等，要么和為根節(jié)點(diǎn)的權(quán)值，故B項(xiàng)錯誤。同理，通過第三個被訪問的節(jié)點(diǎn)排除A項(xiàng)。C項(xiàng)，由兩條路徑可推出三個葉子節(jié)點(diǎn)的權(quán)值分別是：3、10和11，而根據(jù)哈夫曼樹的定義可知，權(quán)值為3的節(jié)點(diǎn)應(yīng)該和權(quán)值為10的結(jié)點(diǎn)結(jié)合，故C項(xiàng)錯誤。D項(xiàng)，反推出有四個葉子節(jié)點(diǎn)，權(quán)值分別為：5、5、6和8，滿足哈夫曼樹的條件。4現(xiàn)在有一顆無重復(fù)關(guān)鍵字的平衡二叉樹（AVL樹），對其進(jìn)行中序遍歷可得到一個降序序列。下列關(guān)于該平衡二叉樹的敘述中，正確的是（??）。A．根節(jié)點(diǎn)的度一定為2B．樹中最小元素一定是葉節(jié)點(diǎn)C．最后插入的元素一定是葉節(jié)點(diǎn)D．樹中最大元素一定是無左子樹【答案】D查看答案【解析】二叉樹的中序遍歷定義是“若二叉樹為空，則空操作；否則：①中序遍歷左子樹；②訪問根節(jié)點(diǎn)；③中序遍歷右子樹”。A項(xiàng)錯誤，當(dāng)樹中僅有一個或者兩個結(jié)點(diǎn)時，根節(jié)點(diǎn)的度就可能不為2；B項(xiàng)錯誤，樹中最小元素是中序遍歷時最后訪問的節(jié)點(diǎn)，當(dāng)沒有右子樹時，最后訪問的節(jié)點(diǎn)是根節(jié)點(diǎn)；C項(xiàng)錯誤，當(dāng)最后插入的元素破壞樹的平衡后，樹會進(jìn)行調(diào)整，使其成為中間節(jié)點(diǎn)；D項(xiàng)正確，由中序遍歷的特點(diǎn)可知，左子樹的值大于根節(jié)點(diǎn)，所以最大元素一定沒有左子樹。5設(shè)有向圖G＝（V，E），頂點(diǎn)集V＝{V0，V1，V2，V3}，邊集E＝{<V0,V1>，<V0,V2>，<V0,V3>，<V1,V3>}，若從頂點(diǎn)V0開始對圖進(jìn)行深度優(yōu)先遍歷，則可能得到的不同遍歷序列個數(shù)是（?）。A．2B．3C．4D．5【答案】D查看答案【解析】根據(jù)題意知有向圖的結(jié)構(gòu)如圖所示。深度優(yōu)先遍歷的特點(diǎn)是盡可能先對縱深方向進(jìn)行搜索，所以可能得到的不同遍歷序列分別是：①V0→V2→V1→V3；②V0→V2→V3→V1；③V0→V1→V3→V2；④V0→V3→V2→V1；⑤V0→V3→V1→V2。6暫缺7下列選項(xiàng)中，不能構(gòu)成折半查找中關(guān)鍵字比較序列的是（?）。A．500，200，450，180B．500，450，200，180C．180，500，200，450D．180，200，500，450【答案】A查看答案【解析】折半查找的過程是：先確定待查找記錄所在的范圍，然后逐步縮小范圍直到找到或找不到該記錄為止。折半查找的關(guān)鍵字序列