第一部分 選擇題 (共分)
一單項選擇題 (本大題共小題每小題分共分)
某算法的空間花費s(n)=nlogn+n+n+其空間復雜度為 [ ]
AO() BO(n)
CO(n) DO(nlogn)
在單項鏈表中刪除一個指定結點的後繼的時間復雜度為 [ ]
AO(n) BO(nlogn)
CO() DO(√n)
在n(n>)個元素的順序棧中刪除個元素的時間復雜度為 [ ]
AO() BO(√n)
CO(nlogn) DO(n)
對長度為n的字符串進行字符定位運算的時間復雜度為 [ ]
AO() BO(√n)
CO(nlogn) DO(n)
廣義表的深度是 [ ]
A廣義表中子表個數 B廣義表括號個數
C廣義表展開後所含的括號層數 D廣義表中元素個數
高度為h(h>)的二叉樹最少有________個結點 [ ]
Ah Bh
Ch+ Dh
n個頂點的帶權無向連通圖的最小生成樹包含________個頂點 [ ]
An Bn
Cn/ Dn+
冒泡排序在最好情況下時間復雜度為 [ ]
AO() BO(nlogn)
CO(n) DO(n)
采用拉鏈法解決沖突的散列表中查找的平均查找長度 [ ]
A直接與關鍵字個數有關 B直接與裝填因子a有關
C直接與表的容量有關 D直接與散列函數有關
經常修改的索引文件宜采用________做索引
A二叉排序樹 B滿二叉樹
C多叉樹 DB+樹
第二部分 非選擇題 (共分)
二填空題 (本大題共小題每空分共分)
某算法需要的輔助空間為s(n)=logn+/n+則該算法的空間復雜度為_______________
在n個結點的單鏈表中在P指向的結點之後插入一個結點的時間復雜度為_______________
設SQ為循環隊列存儲在數組d[m]中則SQ出隊操作對其隊頭指針front的修改是_______________
串中所含字符個數稱為該串的_______________
tail(tail(ab))=_______________
n(n>)個結點二叉樹對應的森林最多包含_______________棵非空樹
深度為n(n>)的二叉樹最多有_______________個結點
n(n>)個結點(n)條邊的連通無向圖中頂點度數最大值為_______________
堆排序的空間復雜度_______________
倒排文件有_______________和主文件構成
三簡答題 (本大題共小題每小題分共分)
設有函數
void fuc(int n)
{int i;
for(i=;i*i*i<=n;i++)
prinft(%di*i*i);
}
函數fuc餓時間復雜度是多少?
把依次進棧(棧初始為空)任何時刻(只要棧不空)都可以出(退)棧試寫出所有可能的出棧序列(如)
若一二叉樹有度結點個則其葉結點有多少個?該二叉樹可以有多少個度頂點?
請畫出廣義表D的圖形表示
D=(D(ab)((ab)c)())
有向圖(帶權)G如下所示
試給出用迪傑斯特拉(Dijkstra)算法求上圖A到其它各頂點最短路徑得到的數組P各元素值(ABCDEF編號依次是)
四理解題 (本大題共小題每小題分共分)
指出下面函數f的功能及返回值的含義
int f(char s[]char s[])
{
int i=j=;
while(s &&s[j]){
if(s >s[j])
return ;
else if(s
return ;
else i++j++;
}
if(s )
return ;
else if(s[j])
return ;
else return ;
}
指出下面函數FS的功能其中p指向先序線索二叉樹的某個結點
typedef enum{LINKTHERAD}flag;
typedef char DataType;
typedef struct node{
DataType data;
flag ltagrtag;
struct node * lchild * rchild;
}BinNode;
BinNode * FS(BinNode *p)
{
if(p>ltag==LINK)
return p>lchild;
else
return p>rchild;
}
五算法填充題 (本大題共小題分)
下面函數diff的功能是根據兩個由整數(都大於)按升序構成的單鏈表L和L(分別由AB指向)構造一個單鏈表L(由*r指向)要求L中的所有整數都是L並且不是L中的整數還要求L中的所有整數都兩兩不等在空缺處填上適當字句使其能正確工作
#include
typedef struct node {
int d;
struct node *next
} Node;
void diff (Node *A Node *B Node **r)
{
int lastnum;
Node * p;
*r=NULL;
if(!A)return;
while(_____________)
if (A>d < B>d)
_____________;
p=(Node*) malloc (sizeof(Node));
p>d=lastnum;
p>next=*r_____________;
do A=A>next;while(_____________);
}
else if (A>d > B>d)
B=B>next
else {
_____________;lastnum=A>d;
while (A&&A>d==lastnum)A=A>next;
}
while (A) {
lastnum=A>d;
p=(Node*) malloc (sizeof(Node));
p>d=lastnum;
_____________*r=p;
while (A&&A>d==lastnum) A=A>next;
}
}
From:http://tw.wingwit.com/Article/program/sjjg/201311/23384.html
