1.選擇題

(1)設某數據結構的二元組形式表示為A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>， <01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，則數據結構A是( B )。

(A) 線性結構

(B) 樹型結構

(C) 物理結構

(D) 圖型結構

(2)下面程序的時間復雜為( B )

for（i=1,s=0; i<=n;i++） 
{
     t=1；
     for(j=1;j<=i;j++)
        t=t*j；
     s=s+t；
}

(A) O(n)

(B) O(n2)

(C) O(n3)

(D) O(n4)

(3)設指針變量p指向單鏈表中結點A，若刪除單鏈表中結點A，則需要修改指針的操作序列為( A)。

(A) q=p->next;p->data=q->data;p->next=q->next;free(q);

(B) q=p->next;q->data=p->data;p->next=q->next;free(q);

(C) q=p->next;p->next=q->next;free(q);

(D) q=p->next;p->data=q->data;free(q);

(4)設有n個待排序的記錄關鍵字，則在堆排序中需要( A )個輔助記錄單元。

(A) 1

(B) n

(C) nlog2n

(D) n2

(5)設一組初始關鍵字記錄為(20，15，14，18，21，36，40，10)，則以20為基準記錄的一趟快速排序結束后的結果為( A )。

(A) 10，15，14，18，20，36，40，21

(B) 10，15，14，18，20，40，36，21

(C) 10，15，14，20，18，40，36，21

(D) 15，10，14，18，20，36，40，21

(6)設二叉排序樹中有n個結點，則在二叉排序樹的平均平均查找長度為( B )。

(A) O(1)

(B) O(log2n)

(C) n

(D) O(n2)

(7)設無向圖G中有n個頂點e條邊，則其對應的鄰接表中的表頭結點和表結點的個數分別為( D)。

(A) n，e

(B) e，n

(C) 2n，e

(D) n，2e

(8)設某強連通圖中有n個頂點，則該強連通圖中至少有(C )條邊。

(A) n(n-1)

(B) n+1

(C) n

(D) n(n+1)

(9)設有5000個待排序的記錄關鍵字，如果需要用最快的方法選出其中最小的10個記錄關鍵字，則用下列( B )方法可以達到此目的。

(A) 快速排序

(B) 堆排序

(C) 歸并排序

(D) 插入排序

(10)下列四種排序中( D )的空間復雜度最大。

(A) 插入排序

(B) 冒泡排序

(C) 堆排序

(D) 歸并排序

2.填空題

(1)數據的物理結構主要包括_____________和______________兩種情況。

參考答案是：

順序存儲結構、鏈式存儲結構

(2)設一棵完全二叉樹中有500個結點，則該二叉樹的深度為__________;若用二叉鏈表作為該完全二叉樹的存儲結構，則共有 ___

個空指針域。

參考答案是：

9，501

(3)設輸入序列為1、2、3，則經過棧的作用后可以得到___________種不同的輸出序列。

參考答案是：

5

(4)設有向圖G用鄰接矩陣A[n][n]作為存儲結構，則該鄰接矩陣中第 i 行上所有元素之和等于頂點i的________，第i列上所有元素之和等于頂點 i 的________。

參考答案是：

出度，入度

(5)設哈夫曼樹中共有n個結點，則該哈夫曼樹中有________個度數為1的結點。

參考答案是：

0

(6)設有向圖G中有n個頂點e條有向邊，所有的頂點入度數之和為d，則e和d的關系為________。

參考答案是：

e=d

(7)__________遍歷二叉排序樹中的結點可以得到一個遞增的關鍵字序列(填先序、中序或后序)。

參考答案是：

中序

(8)設查找表中有100個元素，如果用二分法查找方法查找數據元素X，則最多需要比較________次就可以斷定數據元素X是否在查找表中。

參考答案是：

7

分析：二分查找的過程可以用一棵二叉樹來描述，該二叉樹稱為二叉判定樹。在有序表上進行二分查找時的查找長度不超過二叉判定樹的高度1+log2n。

(9)不論是順序存儲結構的棧還是鏈式存儲結構的棧，其入棧和出棧操作的時間復雜度均為________。

參考答案是：

O(1)

(10)設有n個結點的完全二叉樹，如果按照從自上到下、從左到右從1開始順序編號，則第i個結點的雙親結點編號為___________右孩子結點的編號為___________。

參考答案是：

i/2，2i+1

(11)設一組初始記錄關鍵字為(72，73，71，23，94，16，5)，則以記錄關鍵字72為基準的一趟快速排序結果為____________。

參考答案是：

(5，16，71，23，72，94，73)

(12)設有向圖G中有向邊的集合E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，則該圖的一種拓撲序列為______________。

參考答案是：

(1，4，3，2)

3.算法設計題

(1)設計在單鏈表中刪除值相同的多余結點的算法。

typedef int datatype;
typedef struct node 
{
    datatype data; 
    struct node *next;
}lklist;
void delredundant(lklist *&head)
{
   lklist *p,*q,*s;
   for(p=head;p!=0;p=p->next)
   {
     for(q=p->next,s=q;q!=0;)
     	if(q->data==p->data) 
        {
            s->next=q->next; 
            free(q);q=s->next;
        }
     	else {s=q,q=q->next;}
   }
}

(2)設計一個求結點x在二叉樹中的雙親結點算法。

typedef struct node 
{
    datatype data; 
    struct node *lchild,*rchild;
}bitree;
bitree *q[20]; 
int r=0,f=0,flag=0;
void preorder(bitree *bt, char x)
{
    if (bt!=0 && flag==0)
    if (bt->data==x) 
    { 
        flag=1; 
        return;
    }
    else 
    {
        r=(r+1)% 20; 
        q[r]=bt; 
        preorder(bt->lchild,x); 
        preorder(bt->rchild,x); 
    }
}
void parent(bitree *bt,char x)
{
   int i;
   preorder(bt,x);
   for(i=f+1; i<=r; i++) 
       if (q[i]->lchild->data==x || q[i]->rchild->data) 
           break;
       if (flag==0) 
           printf("not found x\n");
       else if (i<=r) 
           printf("%c",bt->data); 
       else 
           printf("not parent");
}

以上就是動力節點小編介紹的"數據結構試題及答案"，希望對大家有幫助，如有疑問，請在線咨詢，有專業老師隨時為您服務。