第一部分 選擇題 (共分)
一單項選擇題(本大題共小題每小題分共分)
在每小題列出的四個備選項中只有一個是符合題目要求的請將其代碼填寫在題後的括號內錯選多選或未選均無分
數據元素及其關系在計算機存儲器內的表示稱為數據的( )
A邏輯結構 B存儲結構 C線性結構 D非線性結構
某帶頭結點的單鏈表的頭指針為head判定該鏈表為非空的條件是( )
Ahead==NULL Bhead>next==NULL Chead!=NULL Dhead>next!=NULL
導致棧上溢的操作是( )
A棧滿時執行的出棧 B棧滿時執行的入棧
C棧空時執行的出棧 D棧空時執行的入棧
設數組A[m]為循環隊列Q的存儲空間front為隊頭指針rear為隊尾指針則判定Q為空隊列的條件是( )
A(rearfront)%m= = Bfront= =rear
C(rearfront)%m= =m Dfront= =(rear+)%m
假設S=″I AM A STUDENT″則運算substr(S)的結果為( )
A″M A S″ B″M A STUD″ C″A STUDEN″ D″STUD″
在執行簡單的串匹配算法時最壞的情況為每次匹配比較不等的字符出現的位置均為( )
A模式串的最末字符 B主串的第一個字符
C模式串的第一個字符 D主串的最末字符
從廣義表L=(((d)cd))中分解得到(d)的操作為( )
Ahead(head(head(L))) Bhead(tail(head(L)))
Ctail(head(head(L))) Dtail(tail(head(L)))
假設一棵完全二叉樹按層次遍歷的順序依次存放在數組BT[m]中其中根結點存放在BT[]若BT[i]中的結點有左孩子則左孩子存放在( )
ABT[i/] BBT[*i] CBT[*i] DBT[*i+]
右圖所示二叉樹的中序序列是( )
ADHEBAFIJCG BDHEBAFJICG CDBHEAFCJIG DDBHEAFJICG
連通圖是指圖中任意兩個頂點之間( )
A都連通的無向圖 B都不連通的無向圖
C都連通的有向圖 D都不連通的有向圖
下圖所示帶權無向圖的最小生成樹的權為( )
A B C D
對記錄序列()依次按個位和十位進行兩趟基數排序之後所得結果為( )
A B
C D
在待排關鍵字序列基本有序的前提下效率最高的排序方法是( )
A直接插入排序 B快速排序 C直接選擇排序 D歸並排序
在下列各棵二叉樹中二叉排序樹是( )
采用ISAM或VSAM組織的文件是( )
A索引非順序文件 B順序文件 C索引順序文件 D散列文件
第二部分 非選擇題 (共分)
二填空題(本大題共小題每小題分共分)
請在每小題的空格中填上正確答案錯填不填均無分
在一個長度為n的循環鏈表中刪除其元素值為x的結點的時間復雜度為______
已知指針p指向某單鏈表中的一個結點則判別該結點有且僅有一個後繼結點的條件是______
如果入棧序列是…且出棧序列的第一個元素為則出棧序列中第個元素為______
已知廣義表LS為空表則其深度為______
假設以行優先順序存儲三維數組A[][][]其中元素A[][][]的地址為且每個元素占個存儲單元則A[][][]的地址是______
已知一棵二叉樹的先序序列為ABCD中序序列為BCAD則它的後序序列為______
在含n個頂點的連通圖中任意兩個不同頂點之間的一條簡單路徑最多包含______條邊
對關鍵字序列()進行直接插入排序當將第個關鍵字插入到當前的有序子表中時為尋找插入位置需進行______次關鍵字之間的比較
對有序表進行二分查找的過程可用判定樹來描述其判定樹的形態只取決於______
將有序表中n個元素依次插入到一棵空的二叉排序樹中則在等概率查找的情況下該二叉排序樹在查找成功時的平均查找長度是______
三解答題(本大題共小題每小題分共分)
()寫出右側圖形表示的廣義表L
()畫出其表頭與表尾均為(a(bc))的廣義表L的圖形表
()
()
試推導一棵滿k叉樹上的葉子結點數a與非葉子結點數b之間滿足以下關系
a=(k)b+
假設用迪傑斯特拉(Dijkstra)算法求下列圖中從頂點a到其余各頂點的最短路徑按求解過程依次寫出各條最短路徑及其長度
已知關鍵字序列在R[]中的初始狀態為
R
寫出在將它調整為大根堆的過程中每一次篩選後R的狀態
四算法閱讀題(本大題共小題每小題分共分)
如果希望循環隊列中的向量單元都能得到利用則可設置一個標志域tag每當尾指針和頭指針值相同時以tag的值為或來區分隊列狀態是空還是滿請對下列函數填空使其分別實現與此結構相應的入隊列和出隊列的算法
int EnQueue(CirQueue *QDataType x){
if( () ) return ;
Q>data[Q>rear]=x;
Q>rear=(Q>rear+)% MAXQSIZE
()
return ;
}
int DeQueue(CirQueue *QDataType *x){
if( () ) return ;
*x=Q>data[Q>front];
Q>front= () ;
() ;
return ;
}
()
()
()
()
()
已知具有n個結點的完全二叉樹采用順序存儲結構存儲在向量BT[n]中結點的數據元素為字符類型請閱讀下列算法並回答問題
()假設向量BT中的內容為
BT
A
B
C
D
E
F
寫出執行f(BT)後的輸出結果;
()說明該算法的功能
void f(char BT[]int n)
{ int i=;
while(i>)
if(i<=n) {
printf(″%c″ BT[i]);
i=i*;
}else{
do {i=i/;} while(i%);
if(i>) i++;
}
}
()
()
設數組f的初始元素序列為
f[]=()
閱讀下列算法並回答問題其中算法f中調用的函數swap(ab)用以完成交換a和b的值
()寫出執行f(f)之後f[]中的元素序列並寫出在執行過程中調用swap函數的次數
()簡述算法f的功能
void f(int f[]int nint xint y) {
int i=j=k=n;
while (j<=k)
if (f[j]==y)j++;
else if (f[j]==x)
{ swap(f[i]f[j]);i++;j++;}
else {swap(f[k]f[j];k;}
}
()
()
下列算法利用二分查找方法在有序表r中插入元素x並保持表r的有序性其中參數*n為表r的長度請在空缺處填入合適的內容使其成為一個完整的算法
void BinInsert(SeqList rint *nDataType x)
{ int low=high=*nmidi;
while(low<=high)
{ mid= () ;
if (xkey
else (2) ;
}
for(i=*n; (3) ;i--)
r[i+1]=r[i];
(4) ;
*n++;
}
(1)
(2)
(3)
(4)
五、算法設計題(本題共10分)
34.假設一元多項式以循環鏈表表示，鏈表的結點結構為：
typedef struct PNode {
float coef; //系數
int exp; //指數
struct PNode *next;
}*LinkList;
現需要將一個用循環鏈表h表示的代數多項式拆分成兩個多項式循環鏈表h1和h2，其中h1僅含多項式的奇次項，h2僅含多項式的偶次項。TW.winGWIt.COm要求利用原鏈表中的結點構成鏈表h1和h2。例如多項式7x8+5x3-4x的循環鏈表為
經拆分之後的情況應是：
請編寫完成上述拆分的算法，並進行算法分析。
From:http://tw.wingwit.com/Article/program/sjjg/201311/23380.html
