数据构造试卷〔一〕
三、计算题〔每题 6 分，共24分〕
1.在如下数组A中链接存储了一个线性表，表头指针为A [0].next，试写出该线性表。
                  A    0    1    2    3    4    5    6    7
data
60
50
78
90
34
40
next
3
5
7
2
0
4
1
2.请画出以下列图的邻接矩阵和邻接表。
          先序中序后序遍历二叉树
3.一个图的顶点集V和边集E分别为：V={1,2,3,4,5,6,7};
        E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,
(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};
  用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。
4.画出向小根堆中参加数据4, 2, 5, 8, 3时，每参加一个数据后堆的变化。
四、阅读算法〔每题7分，共14分〕
1.LinkList mynote(LinkList L)
      {//L是不带头结点的单链表的头指针
            if(L&&L->next){
                  q=L；L=L－>next；p=L；
        S1：      while(p－>next) p=p－>next；
        S2：      p－>next=q；q－>next=NULL；
              }
              return  L；
            }
    请答复以下问题：
  〔1〕说明语句S1的功能；
  〔2〕说明语句组S2的功能；
      〔3〕设链表表示的线性表为〔a1,a2, …,an〕,写出算法执行后的返回值所表示的线性表。
2.void ABC(BTNode * BT)
{
        if  BT {
          ABC (BT->left);
          ABC (BT->right);
          cout<<BT->data<<' ';
          }
        }
        该算法的功能是：
五、算法填空〔共8分〕
二叉搜索树的查——递归算法:
bool Find(BTreeNode* BST,ElemType& item)
{
  if (BST==NULL)
    return false; //查失败
  else {
        if (item==BST->data){
              item=BST->data;//查成功
              return  ___________;}
      else if(item<BST->data)
              return  Find(______________,item);
      else  return Find(_______________,item);
        }//if
}
六、编写算法〔共8分〕
统计出单链表HL中结点的值等于给定值X的结点数。
    int CountX(LNode* HL,ElemType x)
数据构造试卷〔二〕
三、应用题(36分)
1．设一组初始记录关键字序列为(45，80，48，40，22，78)，那么分别给出第4趟简单项选择择排序和第4趟直接插入排序后的结果。
2．设指针变量p指向双向链表中结点A，指针变量q指向被插入结点B，要求给出在结点A的后面插入结点B的操作序列〔设双向链表中结点的两个指针域分别为llink和rlink〕。
3．设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查方法用二分查，要求计算出查关键字62时的比较次数并计算出查成功时的平均查长度。
4．设一棵树T中边的集合为{(A，B)，(A，C)，(A，D)，(B，E)，(C，F)，(C，G)}，要求用孩子兄弟表示法〔二叉链表〕表示出该树的存储构造并将该树转化成对应的二叉树。
5．设有无向图G，要求给出用普里姆算法构造最小生成树所走过的边的集合。
6．设有一组初始记录关键字为(45，80，48，40，22，78)，要求构造一棵二叉排序树并给出构造过程。
四、算法设计题(16分)
1．设有一组初始记录关键字序列〔K1，K2，…，Kn〕，要求设计一个算法可以在O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于Ki，右半部分的每个关键字均大于等于Ki。
2．设有两个集合A和集合B，要求设计生成集合C=A∩B的算法，其中集合A、B和C用链式存储构造表示。
数据构造试卷〔三〕
二．填空题
1.以下算法实如今顺序散列表中查值为x的关键字，请在下划线处填上正确的语句。
struct record{int key; int others;};
int hashsqsearch(struct record hashtable[ ],int k)
{
int i,j;  j=i=k % p;
while (hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____) %m; if (i==j) return(-1);}
  if (_______________________ ) return(j); else return(-1);
}
2.以下算法实如今二叉排序树上查关键值k，请在下划线处填上正确的语句。
typedef struct node{int key; struct node *lchild; struct node *rchild;}bitree;
bitree  *bstsearch(bitree *t, int k)
{    
if (t==0 ) return(0);else  while (t!=0)

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。