东北大学13春学期《数据结构II》考前复习题

谋学网

一、单选题
1．数据结构被形式地定义为（D,R），其中D 是
A. 算法                    B. 操作的集合   
C. 数据元素的集合          D. 数据关系的集合           [ C  ]
2．顺序表是线性表的
A. 顺序存储结构            B. 链式存储结构   
C. 索引存储结构            D. 散列存储结构             [ A  ]
3．循环队列A[O..m-1]存放其元素值，用front和rear分别表示队头及队尾，则循环队列满的条件是
    A．(Q.rear+1)％m==Q.front   B．Q.rear==Q.front+1
    C．Q.rear+l=Q.front         D．Q.real==Q.front         [ A ]
4．如果以链栈为存储结构，则出栈操作时
A．必须判栈满               B．必须判别栈空  
    C. 判别栈中元素类型         D. 不必作任何判别          [ B ]
5．对矩阵压缩存储是为了
A.方便运算                  B.节省空间     
C.方便存储                  D.提高运算速度              [ B ]
二、填空题
11．在线性结构中，最后一个元素没有（ 后继       ）结点。
12．线性表中所含结点的个数称为线性表的 （  长度         ）。
13．栈的特性是（ 后入先出            ）。
17．求图的最小生成树有两种算法，（   克鲁斯卡尔          ） 算法适合于求稀疏图的最小生成树。
19．回溯方法采用（  深度           ）优先搜索策略。

三、应用题
21. 已知一棵二叉树的先序序列和中序序列分别为：abdgicefhj及bgidaecfjh，画出该的二叉树的先序线索二叉树。
参考资料：
1    2    3    4    5    6    7    8   9   10   11      
A        C        B                        E        D                               




22．有字符串次序为3*-ya/2，利用栈，给出将次序改为3y-*a2/的操作步骤。（可用X代表扫描改字符串过程中顺序取一个字符进栈的操作，用S代表从栈中取出一个字符加入到新字符串尾的出栈操作。例如，ABC变为BCA的操作步骤为XXSXSS）。
参考资料
    XSXXSSSXSXXSS












23. 已知有一个10个顶点的连通图，顶点编号为1至10，其边的关系集合表示为{（1，2）（1，3），（1，8），（2，4），（3，9），（3，10），（5，7），（6，7），（7，8），（8，9）}，试求：画出该连通图及以顶点③为根的广度优先生成树。
参考资料：


24. 对下面的关键字集{35，15，21，99，25，26，36，37，01，18}写出二路归并排序的每趟结果和最终结果。
参考资料：
初始    35，15，21，99，25，26，36，37，01，18
1趟    18，15，21，01，25，26，35，37，36，99
2趟    01，15，18，21，25，26，35，37，36，99
3趟    01，15，18，21，25，26，35，36，37，99











25．设一哈希表长为11，采用链地址法解决冲突，哈希函数H(key)=key%11,
（1）画出在空表中依次插入关键字25，20，36，15，41，52，29，
     72，67后的哈希表。
（2）求在等概率情况下，查找成功的平均查找长度。
参考资料：

（1）  0      1    2    3    4    5    6    7    8    9     10
        67        15        25        36                72        20        41        52        29
             1    1     1    2          1   1     1    2    4
（2）平均查找长度
　　　　查找成功的平均查找长度=(1*6+2*2+1*4)/9=14/9
　　　　
四、算法阅读题
26. 设有一个由正整数组成的无序单链表，阅读下面的算法，指出该算法的功能，并在“//”后面加上必要的注释。
void F1(Linklist &L){  
p=L→next; pre=p;    //pre为结点指针
while(p){ if(p→data > pre→data)
pre=p;// （1）指向最小结点
p=p→next; //
}//while
printf(pre→data);
if(pre→next && pre→data%2==0) { //（2）判断
temp=pre→data; pre→data=pre→next→data;
pre→next→data=temp;// （3）交换
}//if
}//F1
参考资料：
    功能：查找最小值结点。若该结点为奇数，则与其直接后继交换数据。


五、算法阅读题
27. 已知二叉树的存储结构为二叉链表，LinkList和BiTree为已定义的指针类型，ListNode为已定义的结点类型，阅读下面算法并回答：
      LinkList L=Null; p;
void F2(BiTree T){
           if(T){ F2(T→rchild);
                  if((!T→lchild)&&(!T→child){
                     p=(ListNode *)malloc(sizeof(ListNode));
                     p→data=T→data; p→next=L;L=p;
                  }//if
                  F2(T→lchild);
           }//if
}//F2
（1）        说明该算法的功能。
（2）        对于一棵有8个结点的完全二叉数（假设结点顺序为A、B、C、D、E、F、G、H），画出执行上述算法后建立的结构。
参考资料：
（1）按中序遍历二叉树，逆序建立以叶子结点为链表结点、以L为头指针的无头结点的单链表。
（2）L ↓
G       
      ↓  
G       
       ↓
G       
      ↓
G       
      ↓
G        ∧


七、算法设计题
29. 设计算法int connect(ALGraph G)，功能是判断一个以逆邻接表为存储结构的无向图G是否连通有，若连通，则返回1，否则，返回0。
（1）        逆邻接表ALGraph 存储结构定义。
（2）        算法实现。
参考资料：
int connect(ALGraph G){
          //判断以邻接表为存储结构的有向图是否连通
flag=1;
    for(i=0;i<G.vexnum;i++) visited[i]=0;
           dfs(G,visited,0); (2分)   
    for(i=0;i<G.vexnum;i++)
                if(visited[i]=0){
                  flag==0; breek;
              }
            return flag;
}
   Void dfs(ALGraph G,int visited[],int v){
              //采用深度优先遍历的算法思想
              visited[v]=1;
         p=G.ver[v].firstarc;
        while(p){
    if(visited[p→adjvex]==0)
        dfs(G,visited,p→adjvex);
p=p→next;
}//whike
}//dfs





























规范，每一道题要标眀正确或错误（√、×）并给出分数，最后添写到各题的上分栏和总分栏内。
任课老师出题卷面总分为100分，按70％记录成绩，平时作业、出勤、课堂纪律30