可做奧鵬院校所有作業(yè)，畢業(yè)論文，咨詢請?zhí)砑観Q：3230981406      微信：aopopenfd777

東 北 大 學 繼 續(xù) 教 育 學 院

數(shù)據(jù)結(jié)構(gòu)II 試 卷（作業(yè)考核 線上1）  A  卷

學習中心：            院校學號：             姓名            

（共    6    頁）         
總分        題號        一        二        三        四        五        六        七        八        九        十
        得分                                                                               
一、單選題（共30題，每題2分）
[ ]1．抽象數(shù)據(jù)類型的三個組成部分分別為
A．數(shù)據(jù)對象、數(shù)據(jù)關(guān)系和基本操作
      B．數(shù)據(jù)元素、邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)
      C．數(shù)據(jù)項、數(shù)據(jù)元素和數(shù)據(jù)類型
      D．數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型
[ ]2．要求相同邏輯結(jié)構(gòu)的數(shù)據(jù)元素具有相同的特性，其含義為
A. 數(shù)據(jù)元素具有同一的特點
B. 不僅數(shù)據(jù)元素包含的數(shù)據(jù)項的個數(shù)相同，而且其對應數(shù)據(jù)項的類型要一致
C. 每個數(shù)據(jù)元素都一樣
D. 僅需要數(shù)據(jù)元素包含的數(shù)據(jù)項的個數(shù)相同
[ ]3．下列各式中，按增長率由小至大的順序正確排列的是
A． ，n！，2n ，n3/2                    
B．n3/2，2n，nlogn，2100
      C．2n，log n，nlogn，n3/2               
D．2100，logn, 2n, nn
[ ]4. 在下列哪種情況下，線性表應當采用鏈表表示為宜
      A.經(jīng)常需要隨機地存取元素         
B.經(jīng)常需要進行插入和刪除操作
      C.表中元素需要占據(jù)一片連續(xù)的存儲空間   
D.表中元素的個數(shù)不變
[ ]5．設(shè)指針p指向雙鏈表的某一結(jié)點，則雙鏈表結(jié)構(gòu)的對稱性是
A. p->prior->next=p->next->next;      
B.  p->prior->prior=p->next->prior;
C. p->prior->next=p-> next->prior;     
D.  p->next->next= p->prior->prior;
[ ]6. 已知指針p和q分別指向某帶頭結(jié)點的單鏈表中第一個結(jié)點和最后一個結(jié)點。假設(shè)指針s指向另一個單鏈表中某個結(jié)點，則在s所指結(jié)點之后插入上述鏈表應執(zhí)行的語句為
    A. s->next=q；p->next=s->next；
    B. s->next=p；q->next=s->next；
C. p->next=s->next；s->next=q；
D. q->next=s->next；s->next=p；
[ ]7. 棧和隊列的共同特點是
A.只允許在端點處插入和刪除元素
B.都是先進后出   
C.都是先進先出
D.沒有共同點
[ ]8. 對于鏈隊列，在進行插入運算時.
      A. 僅修改頭指針         
B. 頭、尾指針都要修改
      C. 僅修改尾指針              
D.頭、尾指針可能都要修改
[ ]9．設(shè)有一個順序棧的入棧序列是1、2、3，則3個元素都出棧的不同排列個數(shù)為
      A．4      B．5     C. 6     D. 7
[ ]10．設(shè)一個棧的輸入序列為A，B，C，D，則借助一個棧所得到的輸出序列不可能是
A．A，B，C，D               B．D，C，B，A   
C. A，C，D，B               D. D，A，B，C
[ ]11．表達式a*(b+c)-d的后綴表達式是
      A．a(chǎn)bcd*+-    B．a(chǎn)bc*+d-  C．a(chǎn)bc+*d-   D．-+*abcd
[ ]12．某二叉樹的先序序列和后序序列正好相反，則該二叉樹的特點一定是
A. 空或只有一個結(jié)點             B.高度等于其結(jié)點數(shù)
C. 任一結(jié)點無左孩子             D.任一結(jié)點無右孩子
[ ]13．下面的說法中正確的是
    (1)任何一棵二叉樹的葉子結(jié)點在種遍歷中的相對次序不變。
    (2)按二叉樹定義，具有三個結(jié)點的二叉樹共有6種。
A．(1)，(2)                       B．(1)   
C．(2)                            D．(1)，(2)都錯
[ ]14．樹有先序遍歷和后序遍歷，樹可以轉(zhuǎn)化為對應的二叉樹。下面的
說法正確的是
      A．樹的后序遍歷與其對應的二叉樹的先序遍歷相同     
B．樹的后序遍歷與其對應的二叉樹的中序遍歷相同
C．樹的先序序遍歷與其對應的二叉樹的中序遍歷相同      
D．以上都不對
[ ]15．下列說法正確的是
    (1)二又樹按某種方式線索化后，任一結(jié)點均有前趨和后繼的線索
    (2)二叉樹的先序遍歷序列中，任意一個結(jié)點均處于其子孫結(jié)點前
    (3)二叉排序樹中任一結(jié)點的值大于其左孩子的值，小于右孩子的值
A．(1)(2)(3)                     B．(1)(2)   
C．(1)(3)                        D．都不對
[ ]16. 二叉樹的第k層的結(jié)點數(shù)最多為
      A．2k-1                          B.2K+1      
C.2K-1                           D. 2k-1
[ ]17．以下說法不正確的是
     A．無向圖中的極大連通子圖稱為連通分量
     B．連通圖的廣度優(yōu)先搜索中一般采用隊列來暫存剛訪問過的頂點
     C．圖的深度優(yōu)先搜索中一般要采用棧來暫存剛訪問過的頂點
     D．有向圖的遍歷不可采用廣度優(yōu)先搜索
[ ]18．有向圖G用鄰接矩陣A存儲，則頂點i的入度等于A中
A. 第i行1的元素之和            B. 第i列1的元素之和
C. 第i行0的元素個數(shù)            D. 第i列非0的元素個數(shù)
[ ]19. 設(shè)有6個結(jié)點的無向圖，該圖確保是一個連通圖的有效邊條數(shù)至
少應是
A.5              B.6              C.7             D.8
[ ]20．.下圖的鄰接表中，從頂點V1 出發(fā)采用深度優(yōu)先搜索法遍歷該圖，則可能的頂點序列是
  
A. V1V2V3V4V5          B. V1V2V3V5V4
C. V1V4V3V5V2          D.V1V3V4V5V2
[ ]21．關(guān)鍵路徑是事件結(jié)點網(wǎng)絡(luò)中
      A．從源點到匯點的最長路徑    B．從源點到匯點的最短路徑
      C．最長的回路                D．最短的回路
[ ]22．設(shè)哈希表長為14，哈希函數(shù)H(key)=key％11，表中已有數(shù)據(jù)的關(guān)鍵字為15，38，61，84，四個，現(xiàn)將關(guān)鍵字為49的結(jié)點加到表中，用二次探測再散列法解決沖突，則放入的位置是
      A．8       B．3        C．5        D．9
[ ]23．.在平衡二叉樹中插入一個結(jié)點后造成了不平衡，設(shè)最低的不平衡結(jié)點為A，并已知A的左孩子的平衡因子為0，右孩子的平衡因子為1，則應調(diào)整以使其平衡，所作的平衡旋轉(zhuǎn)是
A. LL型           B. LR型       C. RL型       D. RR型
[ ]24．下列排序算法中，在待排序數(shù)據(jù)已基本有序時，效率最高的排序方法是
      A．插入排序                           B．選擇排序   
C．快速排序                           D．堆排序
[ ]25．下列排序算法中，時間復雜度不受數(shù)據(jù)初始狀態(tài)影響，恒為0(nlog2n)是
A. 堆排序                              B. 冒泡排序   
C. 直接選擇排序                        D. 快速排序
[ ]26. 有一程序段:i=1；WHILE(i<n) i=i*2;其中帶下劃線語句的執(zhí)行次數(shù)的數(shù)量級是
A. O(n)                                 B. O(log2n)   
  C. O(nlog2n)                             D. O(n2)
[ ]27.無頭結(jié)點的鏈隊列Q為空的條件是
A. Q->front->next==Q->real=NULL                             
B. Q->front==Q->real<>NULL      
C. Q->real==Q->front=NULL                              
D. Q->real->next==Q->front<>NULL
[ ]28. 有向圖G可拓撲排序的判別條件是
A. 不存在環(huán)                  B. 存在環(huán)        
C. 存在入度為零的結(jié)點        D. 存在出度為零的結(jié)點   
[ ]29. 對n個記錄的文件進行快速排序，所需要的輔助存儲空間
      A. O（1）        B. O（n）      C. O（1og2n）       D. O（n2）
[ ]30. 下列排序算法中，在待排序數(shù)據(jù)已基本有序時，效率最高的排序方法是
       A．插入排序                    B．選擇排序     
C．快速排序                    D．堆排序
二、綜合題（共4題，每題10分）
31、閱讀算法，在橫線處填入語句或注釋。
void exchange_L( Linklist &L，int m ) {
// 帶頭結(jié)點的單鏈表中前m個結(jié)點和后n個結(jié)點的整體互換
       if ( m && L->next ) { // 鏈表非空
            p = L->next;
            （1）// k取值
             while( k< m && p ) { //（2）
           p = p->next; ++k;
       } // while
             if (p && （3）) { // n!=0 時才需要修改指針
             ha = L->next;  //  以指針 ha 記a1結(jié)點的位置
                 L->next= p->next; // 將 b1 結(jié)點鏈接在頭結(jié)點后
                 p->next =（4）;  // 設(shè)am的后繼
                 
  q = L->next; // 令q 指向 b1結(jié)點
                 while (q->next)
                      q = q->next; // 查找 bn 結(jié)點
                 q->next =（5）//將第 a1 結(jié)點鏈接到 bn 結(jié)點之后
} // if(p)
                              } // if(m)
                             } // exchange_L











32．一個僅包含二元運算符的算術(shù)表達式，以二叉鏈表形式存儲在二叉樹T中，設(shè)計算法F1實現(xiàn)求值，并指出遍歷的方式。
















33．設(shè)計算法實現(xiàn)以逆鄰接表為存儲結(jié)構(gòu)的有向圖的拓撲排序。
逆鄰接表存儲結(jié)構(gòu)定義如下：
頂點結(jié)構(gòu)                       表結(jié)點結(jié)構(gòu)
vexdata        firstin
adjvex        nfo        firstarc
















34. 設(shè)哈希表長為13，采用線性探測法解決沖突，哈希函數(shù)定義為：H(key)=key%13。
試求：（1）填上依次插入關(guān)鍵字25，20，36，15，41，52，29，72，67后的哈希表。
（2）計算等概率情況下，查找成功的平均查找長度。